{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Benjamin_Midterm_Notes.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "s3Uk9gQTevcj"
      ]
    },
    "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/",
          "height": 0
        },
        "outputId": "af56fd1a-4369-4148-c431-18a1a4843a37"
      },
      "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": 1,
      "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/",
          "height": 0
        },
        "outputId": "e307684a-0928-478f-f287-7b03a5fd10aa"
      },
      "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": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 3,
      "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 = \"\"\"AI was coined in 1956. Definitions of AI are organized into four \\\n",
        "categories: 1) Systems that think like humans, 2) Systems that think rationally, 3) Systems that \\\n",
        "act like humans, and 4) Systems that act rationally. Two are focused on thought process \\\n",
        "and reasonsing, measuring success in terms of human performance, while the other two \\\n",
        "are focused on behavior, measuring success against an ideal concept of intelligence \\\n",
        "called rationality. \n",
        "\n",
        "Acting humanly: Alan Turing proposed his test in 1950 to perceive human-level performance \\\n",
        "in cognitive tasks. A human would interrogate a computer with a teletype, and the computer \\\n",
        "would pass if it fools the human. To Turing, physcial simulation of a person was irrelevant \\\n",
        "for computer intelligence. The computer would need to know NLP, knowledge representation \\\n",
        "to store information, automated reasoning to answer questions, and machine learning to adapt to \\\n",
        "new patterns. The total Turing test would include video signal to test perceptual abilities \\\n",
        "and grab an item through the hatch. This would require computer vision and robotics.\n",
        "\n",
        "Thinking humanly: Cognitive science melds AI and psychology experiments to construct \\\n",
        "theories about the mind. Some want computer's to solve the problem correctly, while \\\n",
        "others want them to solve it how a human would through reasoning.\n",
        "\n",
        "Thinking rationally: Aristotle's syllogisms constructed right thinking based on \\\n",
        "correct premises leading to correct conclusions, defining the field of logic and \\\n",
        "the logicist method of AI. Difficulty is stating informal knowledge in logical \\\n",
        "terms, and solving in principle vs practice. \n",
        "\n",
        "Acting rationally: acting to achieve one's goals given one's beliefs. An agent is \\\n",
        "something that perceives andacts. AI is viewed as the construction of rational agents \\\n",
        "Correct inferences is not all of rationality bc there are situations where nothing \\\n",
        "is correct, or taking too long to decide is bad. AI as rational agents has two \\\n",
        "advantages over laws of thought bc correct inference is useful but not necessary, so it \\\n",
        "is a more general approach, and secondly, bc it is easier for scientific development.\n",
        "\n",
        "Achieving perfect rationality is not always possible in complicated environments. \\\n",
        "Limited rationality is acting rationally when there is not enough time to compute. \"\"\" \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 = \"\"\"Can we build a complete, general-purpose intelligent agent? \\\n",
        "Decision making ranges from reflex responses to knowledge-informed deliberation. \\\n",
        "Explanation-based learning includes compilation processes to convert declarative \\\n",
        "information at the deliberative level into efficient representations that eventually \\\n",
        "become reflex, e.g. the SOAR and THEO architectures. When they solve a problem through \\\n",
        "deliberation, they'll save it for reflex later. \n",
        "\n",
        "Real-time AI deals with when agents need to control their deliberation time, e.g. a car \\\n",
        "is crashing. Alpha-beta pruning can elimiate irrelevant deliberations and depth.\n",
        "\n",
        "Anytime algorithms improve their output quality over time so it has an okay decision \\\n",
        "if interrupted, allowing it to decide if more computation is worthwhile. An example \\\n",
        "of this would be iterative deepening search. \n",
        "\n",
        "Decision-theoretic metareasoning applies information value to computations to balance \\\n",
        "the cost of delaying action vs the expected improved decision quality. \n",
        "\n",
        "Finally there is learning mechanisms in general intelligent agents, e.g. inductive, \\\n",
        "reinforcement learning. It's not currently possible to self-learn from scratch just \\\n",
        "by pointing the computer towards a dictionary (a large knowledge base).\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"If we design a desirable property P, then we should be able to \\\n",
        "design a system that possesses property P. There are three choices for P: \\\n",
        "1) Perfect rationality: a perfectly rational agent acts to maximize its expected \\\n",
        "utility given the environmental information. Perfectly rational agents do not exist \\\n",
        "outside of non-trivial environments. 2) Calculative rationality: how we design \\\n",
        "logical and decision-theoretic agents, which eventually return what would have \\\n",
        "been the rational choice for when it began deliberating. In principle, this would \\\n",
        "do the right thing, but if you apply the brakes long after you've crashed, it's \\\n",
        "irrational. 3) Bounded optimality (BO): a BO agent behaves rationally given its \\\n",
        "compuational resources. The expected utility is at least as high as the expected \\\n",
        "utility of any other agent on the same machine. We don't want the design of the \\\n",
        "computer however (e.g. how much memory), to impact how we deisng the BO system. \\\n",
        "Bounded optimality indicates optimal programs rather than actions.  \n",
        "\n",
        "Asymptotic bounded optimality (ABO): if we have a program B bouned optimally for a \\\n",
        "machine M in an environment E, with unbounded complexity, then program P' is ABO \\\n",
        "for M in E if it can outperform P by running on a machin ekM that is k times better \\\n",
        "(faster/larger). \n",
        "\n",
        "Shifting from descirbing actions to programs is in other fields of rationality. \\ \n",
        "Act utilitarianism is the rationality of individual acts, but is shifting to \\\n",
        "rule utilitariansim, the rationality of general policies for how to act. \n",
        "\n",
        "Game theory and the prisoner's dilemma offer an example of simultaneous decisions. \\\n",
        "we can bound on space rather than time if we only do a few rounds.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"An agent is anything that percieves its environment with sensors \\\n",
        "and acts upon that environment with effectors. Humans have ears/eyes, but robots \\\n",
        "have cameras and other sensors, plus motors as effectors. Software agent has \\\n",
        "code as its percepts and actions. Agents should also know things. \n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\" A rational agent does the right thing, meaning it will cause the agent to be the \\\n",
        "most successful. Performance measure is how we determine if an agent is successful. \\\n",
        "We could ask a Rumba to clean the whole floor, in an amount of time, quietly, and \\\n",
        "with minimal electricity. When we evaluate our performance measure is also important. \\\n",
        "Do we value speed or consistency? \n",
        "\n",
        "Omniscience is an agent that knows the actual outcome of its actions and acts accordingly. \\\n",
        "Rationality is expected success given what has been percieved.  This should take into account \\\n",
        "four things: 1) Performance measure that defines success, 2) Perceptual history (percept sequence) \\\n",
        ", 3) what the agent knows about their environment, and 4) actions that it can perform. \n",
        "\n",
        "An ideal rational agent does whatever action is expected to maximize its performance \\\n",
        "measure for each possible percept sequence, using the evidence provided and the \\\n",
        "built-in knowledge it has. This requires you take actions to obtain useful information. \n",
        "Clocks are simple agents, but degenerate in that their percept sequence is empty.\n",
        "\n",
        "A mapping is a list of percept sequences to actions. An ideal mapping describes \\\n",
        "ideal agents by specifying which action to take in response to any scenario. \n",
        "\n",
        "Autonomy: if an ideal rational agent only uses built in knowledge, then it lacks autonomy. \\\n",
        "If its behaviour is determined by its own experience, then it is autonomous. \"\"\"\n",
        "\n",
        "chapter2_3 = \"\"\" AI must design the agent program, a function that implements a \\\n",
        "mapping from percepts to actions. The computing device on which it runs is the \\\n",
        "architecture. Agent = architecture + program.\n",
        "\n",
        "Artificial environments might be what we do in homeowork (keyboard + console), but \\\n",
        "this is a real environment. Some software agents (e.g. bots) exist in complex domains. \\\n",
        "PAGE = percepts, actions, goals, environment. \n",
        "\n",
        "Although a mapping is from percept sequences to actions, the agent program receives \\\n",
        "one percept as an input and must construct the sequence in memory. \n",
        "\n",
        "A skeleton agent function takes in a percept and returns an action. A look-up agent \\\n",
        "has no autonomy and simply looks up its mapping, but would take too long to build \\\n",
        "and may not have enough memory for all actions.\n",
        "\n",
        "Four types of agent programs: 1) simple reflex agents, 2) agents that keep track \\\n",
        "of the world, 3) goal-based agents, and 4) utility based agents. \n",
        "\n",
        "Simple-reflex agents: have condition-action rule, e.g. brake for pedestrian. \\\n",
        "This uses interpret-input, rule-match, and rule-action functions. \n",
        "\n",
        "Agents that keep track of the world: maintain internal state, e.g. first picture \\\n",
        "shows car in front without brake lights, and then next shows it with them. Or if a \\\n",
        "car is overtaking it based on where it was before. UPDATE-STATE function.\n",
        "\n",
        "Goal based agents: search and planning are example programs to get taxi to destination. \\\n",
        "This involves looking into the future, what will happen if I do this next step. \\\n",
        "What happens if it starts raining. \n",
        "\n",
        "Utility based agents: goals are not enough because you can get to a destination faster \\\n",
        "or cheaper. Performance measure should take into account other states to define higher \\\n",
        "utility for the agent. Utility is a function mapping a state onto a number, e.g. a degree \\\n",
        "of happiness. Utility function allows for when their on conflicting goals (e.g. speed \\\n",
        "and safety). Utility functions can be translated to goals so that you can have a \\\n",
        "goal based and utility based agent making the same decisions. \n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"Environments: actions are done by the agent to an environment, which provides percepts back. \\\n",
        "Environments have several properties: 1) accessible vs. inaccessible, if the agent can detect \\\n",
        "all percepts relevant to the choice of an action. 2) Determinisitc vs. nondeterministic, if \\\n",
        "the next state is determined by the current state, from the point of view of the agent. \\\n",
        "3) Episodic vs. non-episodic, if the decision is not impacted by the next \"round\". \\\n",
        "4) Static vs. dynamic, if the environment does not change during deliberation. Semi-dynamic \\\n",
        "is if the performance score changes during time, but the environment does not. 5) \\\n",
        "Discrete vs. continouse, chess vs. taxi driving, if there are distinct, clearly defined percepts.\n",
        "\n",
        "Hardest environment is inaccessible, nonepisodic, dynamic, and continous. \n",
        "\n",
        "Environment programs are RUN-ENVIRONMENT and RUN-EVAL-ENVIRONMENT. Agents are designed to work \\\n",
        "in an environment class, a whole set of different environments, e.g. chess against a variety \\ \n",
        "of opponents.\n",
        "\n",
        "Agent programs maps from a percept to an action, updating an internal state. \\\n",
        "\n",
        "Reflex agents respond immediately to percepts, but goal-based agents act to achieve goals \\\n",
        "and utility based agents try to maximize happiness defined by utility. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "Strong AI vs weak AI: actually thinking versus merely simulating thinking.\\ \n",
        "Agent is anything that percieves its environment through sensors and can \\\n",
        "act on its environment with actuators. Percept is the agent's inputs at \\\n",
        "any given time. Agent is specified by an agent function f that maps a \\\n",
        "sequence of percepts to an action. Agent is composed of agent program \\\n",
        "and architecture.\n",
        "\n",
        "Consequentialism: evaluating an agent's behaviour based on its consequences.\\\n",
        "We should think about performance measures as what we want the agent to achieve \\\n",
        "rather than how we think it should behave. Ideal agent maximizes actual \\\n",
        "performance, but would need omniscience. \n",
        "\n",
        "Revised definition: rational agent maximizes the expected value of its \\\n",
        "performance measure.\n",
        "\n",
        "PEAS: task environment specifications: 1) performance measure; 2) environment \\\n",
        "3) actuators, 4) sensors. Reflex agent selects an action based on current \\\n",
        "percept and ignores rest of percept history. Problem solving agent plans ahead \\\n",
        "and considers sequence from path to goal using search.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "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": 2197
        },
        "outputId": "59d4f8c7-dd55-439f-eff5-6f7ca762a2bc"
      },
      "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": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nAI was coined in 1956. Definitions of AI are organized into four categories: 1) Systems that think like humans, 2) Systems that think rationally, 3) Systems that act like humans, and 4) Systems that act rationally. Two are focused on thought process and reasonsing, measuring success in terms of human performance, while the other two are focused on behavior, measuring success against an ideal concept of intelligence called rationality. \n\nActing humanly: Alan Turing proposed his test in 1950 to perceive human-level performance in cognitive tasks. A human would interrogate a computer with a teletype, and the computer would pass if it fools the human. To Turing, physcial simulation of a person was irrelevant for computer intelligence. The computer would need to know NLP, knowledge representation to store information, automated reasoning to answer questions, and machine learning to adapt to new patterns. The total Turing test would include video signal to test perceptual abilities and grab an item through the hatch. This would require computer vision and robotics.\n\nThinking humanly: Cognitive science melds AI and psychology experiments to construct theories about the mind. Some want computer's to solve the problem correctly, while others want them to solve it how a human would through reasoning.\n\nThinking rationally: Aristotle's syllogisms constructed right thinking based on correct premises leading to correct conclusions, defining the field of logic and the logicist method of AI. Difficulty is stating informal knowledge in logical terms, and solving in principle vs practice. \n\nActing rationally: acting to achieve one's goals given one's beliefs. An agent is something that perceives andacts. AI is viewed as the construction of rational agents Correct inferences is not all of rationality bc there are situations where nothing is correct, or taking too long to decide is bad. AI as rational agents has two advantages over laws of thought bc correct inference is useful but not necessary, so it is a more general approach, and secondly, bc it is easier for scientific development.\n\nAchieving perfect rationality is not always possible in complicated environments. Limited rationality is acting rationally when there is not enough time to compute. \n\n## AIMA Chapter 27.1 The Limits of AI\nCan we build a complete, general-purpose intelligent agent? Decision making ranges from reflex responses to knowledge-informed deliberation. Explanation-based learning includes compilation processes to convert declarative information at the deliberative level into efficient representations that eventually become reflex, e.g. the SOAR and THEO architectures. When they solve a problem through deliberation, they'll save it for reflex later. \n\nReal-time AI deals with when agents need to control their deliberation time, e.g. a car is crashing. Alpha-beta pruning can elimiate irrelevant deliberations and depth.\n\nAnytime algorithms improve their output quality over time so it has an okay decision if interrupted, allowing it to decide if more computation is worthwhile. An example of this would be iterative deepening search. \n\nDecision-theoretic metareasoning applies information value to computations to balance the cost of delaying action vs the expected improved decision quality. \n\nFinally there is learning mechanisms in general intelligent agents, e.g. inductive, reinforcement learning. It's not currently possible to self-learn from scratch just by pointing the computer towards a dictionary (a large knowledge base).\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nIf we design a desirable property P, then we should be able to design a system that possesses property P. There are three choices for P: 1) Perfect rationality: a perfectly rational agent acts to maximize its expected utility given the environmental information. Perfectly rational agents do not exist outside of non-trivial environments. 2) Calculative rationality: how we design logical and decision-theoretic agents, which eventually return what would have been the rational choice for when it began deliberating. In principle, this would do the right thing, but if you apply the brakes long after you've crashed, it's irrational. 3) Bounded optimality (BO): a BO agent behaves rationally given its compuational resources. The expected utility is at least as high as the expected utility of any other agent on the same machine. We don't want the design of the computer however (e.g. how much memory), to impact how we deisng the BO system. Bounded optimality indicates optimal programs rather than actions.  \n\nAsymptotic bounded optimality (ABO): if we have a program B bouned optimally for a machine M in an environment E, with unbounded complexity, then program P' is ABO for M in E if it can outperform P by running on a machin ekM that is k times better (faster/larger). \n\nShifting from descirbing actions to programs is in other fields of rationality. \\ \nAct utilitarianism is the rationality of individual acts, but is shifting to rule utilitariansim, the rationality of general policies for how to act. \n\nGame theory and the prisoner's dilemma offer an example of simultaneous decisions. we can bound on space rather than time if we only do a few rounds.\n\n## AIMA 2.1 Agents and Environments\nAn agent is anything that percieves its environment with sensors and acts upon that environment with effectors. Humans have ears/eyes, but robots have cameras and other sensors, plus motors as effectors. Software agent has code as its percepts and actions. Agents should also know things. \n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n A rational agent does the right thing, meaning it will cause the agent to be the most successful. Performance measure is how we determine if an agent is successful. We could ask a Rumba to clean the whole floor, in an amount of time, quietly, and with minimal electricity. When we evaluate our performance measure is also important. Do we value speed or consistency? \n\nOmniscience is an agent that knows the actual outcome of its actions and acts accordingly. Rationality is expected success given what has been percieved.  This should take into account four things: 1) Performance measure that defines success, 2) Perceptual history (percept sequence) , 3) what the agent knows about their environment, and 4) actions that it can perform. \n\nAn ideal rational agent does whatever action is expected to maximize its performance measure for each possible percept sequence, using the evidence provided and the built-in knowledge it has. This requires you take actions to obtain useful information. \nClocks are simple agents, but degenerate in that their percept sequence is empty.\n\nA mapping is a list of percept sequences to actions. An ideal mapping describes ideal agents by specifying which action to take in response to any scenario. \n\nAutonomy: if an ideal rational agent only uses built in knowledge, then it lacks autonomy. If its behaviour is determined by its own experience, then it is autonomous. \n\n## AIMA 2.3 The Nature of Environments\n AI must design the agent program, a function that implements a mapping from percepts to actions. The computing device on which it runs is the architecture. Agent = architecture + program.\n\nArtificial environments might be what we do in homeowork (keyboard + console), but this is a real environment. Some software agents (e.g. bots) exist in complex domains. PAGE = percepts, actions, goals, environment. \n\nAlthough a mapping is from percept sequences to actions, the agent program receives one percept as an input and must construct the sequence in memory. \n\nA skeleton agent function takes in a percept and returns an action. A look-up agent has no autonomy and simply looks up its mapping, but would take too long to build and may not have enough memory for all actions.\n\nFour types of agent programs: 1) simple reflex agents, 2) agents that keep track of the world, 3) goal-based agents, and 4) utility based agents. \n\nSimple-reflex agents: have condition-action rule, e.g. brake for pedestrian. This uses interpret-input, rule-match, and rule-action functions. \n\nAgents that keep track of the world: maintain internal state, e.g. first picture shows car in front without brake lights, and then next shows it with them. Or if a car is overtaking it based on where it was before. UPDATE-STATE function.\n\nGoal based agents: search and planning are example programs to get taxi to destination. This involves looking into the future, what will happen if I do this next step. What happens if it starts raining. \n\nUtility based agents: goals are not enough because you can get to a destination faster or cheaper. Performance measure should take into account other states to define higher utility for the agent. Utility is a function mapping a state onto a number, e.g. a degree of happiness. Utility function allows for when their on conflicting goals (e.g. speed and safety). Utility functions can be translated to goals so that you can have a goal based and utility based agent making the same decisions. \n\n\n## AIMA 2.4 The Structure of Agents\nEnvironments: actions are done by the agent to an environment, which provides percepts back. Environments have several properties: 1) accessible vs. inaccessible, if the agent can detect all percepts relevant to the choice of an action. 2) Determinisitc vs. nondeterministic, if the next state is determined by the current state, from the point of view of the agent. 3) Episodic vs. non-episodic, if the decision is not impacted by the next \"round\". 4) Static vs. dynamic, if the environment does not change during deliberation. Semi-dynamic is if the performance score changes during time, but the environment does not. 5) Discrete vs. continouse, chess vs. taxi driving, if there are distinct, clearly defined percepts.\n\nHardest environment is inaccessible, nonepisodic, dynamic, and continous. \n\nEnvironment programs are RUN-ENVIRONMENT and RUN-EVAL-ENVIRONMENT. Agents are designed to work in an environment class, a whole set of different environments, e.g. chess against a variety \\ \nof opponents.\n\nAgent programs maps from a percept to an action, updating an internal state. \nReflex agents respond immediately to percepts, but goal-based agents act to achieve goals and utility based agents try to maximize happiness defined by utility. \n\n## Module 1 Lecture Notes\n \nStrong AI vs weak AI: actually thinking versus merely simulating thinking.\\ \nAgent is anything that percieves its environment through sensors and can act on its environment with actuators. Percept is the agent's inputs at any given time. Agent is specified by an agent function f that maps a sequence of percepts to an action. Agent is composed of agent program and architecture.\n\nConsequentialism: evaluating an agent's behaviour based on its consequences.We should think about performance measures as what we want the agent to achieve rather than how we think it should behave. Ideal agent maximizes actual performance, but would need omniscience. \n\nRevised definition: rational agent maximizes the expected value of its performance measure.\n\nPEAS: task environment specifications: 1) performance measure; 2) environment 3) actuators, 4) sensors. Reflex agent selects an action based on current percept and ignores rest of percept history. Problem solving agent plans ahead and considers sequence from path to goal using search.\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"Python invented by Guido van Rossum in 1989, the \\\n",
        "Benevolent Dictator for Life. PEP8 is the python style guide. REPL is \\\n",
        "read, evaluate, print, loop. Whitespace is meaningful in Python. \\\n",
        "\n",
        "Java is static typing in that variables can only refer to objects of the \\\n",
        "declared type, and methods use type signatures to force types. Python, \\\n",
        "however, is dynamically typed (meaning the type of a variable can change), \\\n",
        "and functions have not type signatures. Drawback is that type errors are \\\n",
        "caught at runtime.\n",
        "\n",
        "Three sequences are 1) strings, 2) lists, 3) tuples.\n",
        "\n",
        "Strings can have single or double quotes. Triple quotes for multi-line strings \\\n",
        "and docstrings. Strings are immmutable, but can be concatenated with +. \\\n",
        "Strings are unicode and use 2-byte characters\n",
        "\n",
        "== checks if variables point to objects of the same value, while 'is' checks \\\n",
        "if they are the same object. Lists are mutable. Use 'y=x[:]' to get a shallow \\\n",
        "copy of something.\n",
        "\n",
        "Tuples are immutable, but can be of mixed type. \n",
        "\n",
        "Slicing returns copy of a subsequence. Nevative lookup from right is myList[-3].\\\n",
        "t[1:-1] uses negative index. t[1:-1:2] selectes every nth item. t[:2] copies from \\\n",
        "beginning of sequence. t[2:] copies to end of sequence.\n",
        "\n",
        "Lists have append, insert, index, count, remove, reverse, and sort methods. \n",
        "\n",
        "Strings have split, join, capitalize, upper, lower, strip methods.\n",
        "\n",
        "Dictionaries are undordered and work by hashing, with immutable keys. \\\n",
        "There is constant average time to add, lookup, and update. d = {'user: 'ben', 'pass: 123} \\\n",
        "Dictionary has keys, values, items methods. \n",
        "\n",
        "Python functions can return multiple values, but have no function overloading. \\\n",
        "You can provide default values for arguments. Non-default arguments must proceed \\\n",
        "default arguments. The *args argument accepts a variable number of non-keyword \\\n",
        "arguments to the function. The **kwargs argument accepts a variable number of \\\n",
        "keyword arguments. \n",
        "\n",
        "Python uses dynamic scope. Memoization is using prior arguments to the funciton \\\n",
        "e.g. used in recursion. Functions are first-class objects which can be dynamically \\\n",
        "passed to other functions or returned as a value. So you could pass a function \\\n",
        "to a higher order one, or store a function in a data structure. \n",
        "\n",
        "Classes have __init__ methods. All class methods begin with self. Subclasses \\\n",
        "extend the definition of another class. Define it by putting name of \\\n",
        "superclass in parentheses after classs name. class AI_Student(Student). \\\n",
        "Def __init(self, name, dept): Student.__init__(self, name, dept). \\\n",
        "Only time to pass self as argument is calling method of an ancestor. \n",
        "\n",
        "Magic method of classes are __init__, __len__, __copy__, __cmp__, _add__, __neg__ \\\n",
        "to override Python defaults.  \n",
        "\n",
        "Python main method:: if __name__ == '__main__': do stuff\n",
        "\n",
        "Duck typing establishes suitability of an object by determining presence of methods.\n",
        "\n",
        "List comprehension: li = [3, 6, 2, 7]. [elem * 2 for elem in li] = [6, 12, 4, 14]. \\\n",
        "li = [('a', `, ('b', 2), ('c', 7))], [n * 3 for (x, n) in li] = [3, 6, 21]\n",
        "\n",
        "Generators are iterators created using 'yield'. After a yield statement, the \\\n",
        "function will return the value and then resume where it left off. __next__() is \\\n",
        "the how you access the returned value. while True: try print(g.__next__()), \\\n",
        "except StopIteration: break. \n",
        "\n",
        "Imports: from math import sqrt, from math import *, import numpy as np (alias). \\\n",
        "pip is package installer for python.\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 821
        },
        "outputId": "067cf7ba-4581-407a-8f64-4c4052c91622"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\nPython invented by Guido van Rossum in 1989, the Benevolent Dictator for Life. PEP8 is the python style guide. REPL is read, evaluate, print, loop. Whitespace is meaningful in Python. \nJava is static typing in that variables can only refer to objects of the declared type, and methods use type signatures to force types. Python, however, is dynamically typed (meaning the type of a variable can change), and functions have not type signatures. Drawback is that type errors are caught at runtime.\n\nThree sequences are 1) strings, 2) lists, 3) tuples.\n\nStrings can have single or double quotes. Triple quotes for multi-line strings and docstrings. Strings are immmutable, but can be concatenated with +. Strings are unicode and use 2-byte characters\n\n== checks if variables point to objects of the same value, while 'is' checks if they are the same object. Lists are mutable. Use 'y=x[:]' to get a shallow copy of something.\n\nTuples are immutable, but can be of mixed type. \n\nSlicing returns copy of a subsequence. Nevative lookup from right is myList[-3].t[1:-1] uses negative index. t[1:-1:2] selectes every nth item. t[:2] copies from beginning of sequence. t[2:] copies to end of sequence.\n\nLists have append, insert, index, count, remove, reverse, and sort methods. \n\nStrings have split, join, capitalize, upper, lower, strip methods.\n\nDictionaries are undordered and work by hashing, with immutable keys. There is constant average time to add, lookup, and update. d = {'user: 'ben', 'pass: 123} Dictionary has keys, values, items methods. \n\nPython functions can return multiple values, but have no function overloading. You can provide default values for arguments. Non-default arguments must proceed default arguments. The *args argument accepts a variable number of non-keyword arguments to the function. The **kwargs argument accepts a variable number of keyword arguments. \n\nPython uses dynamic scope. Memoization is using prior arguments to the funciton e.g. used in recursion. Functions are first-class objects which can be dynamically passed to other functions or returned as a value. So you could pass a function to a higher order one, or store a function in a data structure. \n\nClasses have __init__ methods. All class methods begin with self. Subclasses extend the definition of another class. Define it by putting name of superclass in parentheses after classs name. class AI_Student(Student). Def __init(self, name, dept): Student.__init__(self, name, dept). Only time to pass self as argument is calling method of an ancestor. \n\nMagic method of classes are __init__, __len__, __copy__, __cmp__, _add__, __neg__ to override Python defaults.  \n\nPython main method:: if __name__ == '__main__': do stuff\n\nDuck typing establishes suitability of an object by determining presence of methods.\n\nList comprehension: li = [3, 6, 2, 7]. [elem * 2 for elem in li] = [6, 12, 4, 14]. li = [('a', `, ('b', 2), ('c', 7))], [n * 3 for (x, n) in li] = [3, 6, 21]\n\nGenerators are iterators created using 'yield'. After a yield statement, the function will return the value and then resume where it left off. __next__() is the how you access the returned value. while True: try print(g.__next__()), except StopIteration: break. \n\nImports: from math import sqrt, from math import *, import numpy as np (alias). pip is package installer for python.\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" One kind of goal-based agent is the problem-solving agent, \\\n",
        "which finds a sequence of actions to lead to a desirable state. Goal \\\n",
        "formulation is the first step in problem solving. Multiple factors can \\\n",
        "affect the desirability of differing ways of achieving the goal. Problem \\\n",
        "formulation is the process of deciding what actions and states to consider after \\\n",
        "goal formulation. The process of looking for a sequence that leads to goal state \\\n",
        "is called search. This algorithm takes a problem and returns a solution in the \\\n",
        "form of an action sequence. Execution phase is where it carries out the action. \"\"\"\n",
        "\n",
        "chapter3_2 = \"\"\" Formulating problems:  a single-state problem is when you find the \\\n",
        "solution on the first state-change. When the world is not fully accessible, the agent \\\n",
        "reasons about the set of states to get to, making it a multiple-state problem.\\ \n",
        "Agent must calculate a tree of actions, where each branch deals with possible contingencies \\\n",
        "making this a contingency problem. I.e. you go to clean up dirt, but there is not dirt. \n",
        "\n",
        "Interleaving of search and execution to achieve goal. Exploration problems are when \\\n",
        "the agent has no information about it surroundings, and must experiment to solve its goal.\n",
        "\n",
        "A problem is a collection of information used by the agent to decide what do do. \\\n",
        "These are the components of a problem definition: 1) initial state of agent, 2) set \\\n",
        "of possible actions. Operator enotes the action in terms of which state will be \\\n",
        "reached by carrying out an action in a state. Also called successor function S, where \\\n",
        "S(x) returns states reachable from x an action. \n",
        "\n",
        "The state space of a problem is the set of states reachable from the initial state in a \\\n",
        "sequence of actions. A path in the state space is a sequence. The goal test is applied \\\n",
        "to a single state, letting the agent know if it has reached its goal. A path cost \\\n",
        "function is a function that assigns a cost to a path. Path cost function denoted by g.\n",
        "\n",
        "initial state, operator set, goal test, and path cost function define a problem. Output of \\\n",
        "a search algo is a solution, the path from initial state to goal state.  \n",
        "\n",
        "A path connects sets of states and a solution is a path that leads to a set of states, all of \\\n",
        "which are goal states. The state space is then replaced by state set space. \n",
        "\n",
        "Performance: does a solution exist, is it a low path cost solution, and third, what is \\\n",
        "the search cost (time and memory). Total cost is sum of path cost and search cost. \\\n",
        "Offline cost is search cost and online cost is path cost.\n",
        "\n",
        "Process of removing detail from a representation is called abstraction. \n",
        "\n",
        "NP completeness is nondeterministic polynomial time. Concret way to solve.\\\n",
        "TSP = travelling salesperson problem. NP-hard = at least as hard as the hardest problem \\\n",
        "in NP. VLSI chips have cell layout and channel routing problems to minimize area and \\\n",
        "connection lengths to maximize speed.\n",
        "\n",
        "Generate action sequences by applying operators to the current state \\\n",
        "and expanding the state. We conitinue choosing and expanding until the solution is found, \\\n",
        "or there are no more states to expand. Choosing which state to expand first is up to  the \\\n",
        "search strategy. Search tree is the state space, with the root being the initial state. \\\n",
        "Difference between state space and search tree is that there are finite states, but \\\n",
        "potentially infinite nodes in search tree if you get caught in a loop.\n",
        "\n",
        "Fringe or frontier is the collection of nodes waiting to be expanded. This is \\\n",
        "implemented as a queue.\n",
        "\"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\" \n",
        "Evaluating search strategies: 1) completeness - is the \\\n",
        "strategy guaranteed to find a solution if exists, 2) time complexity - how \\\n",
        "long does it take, 3) space complexity - how much memory does it need, 4) \\\n",
        "optimality - does it find the highest quality solution if multiple exist?\n",
        "\n",
        "Uninformed search strategies: no information about the number of steps or the \\\n",
        "path cost from current to goal. They just distinguish goal and non-goal. Also \\\n",
        "called blind search. This is in contrast to informed search, or heuristic search.\n",
        "\n",
        "Breadth first search: first expand root, then its immediate children, and then \\\n",
        "their successors. Nodes at depth d are expanded before nodes at depth d + 1. We \\ \n",
        "can implement BFS using general-search by adding newly generated states to the end \\\n",
        "of the queue, after all previously generated states.  If solution exists, BFS will \\\n",
        "find it, and it will always find the shallowest solution. Therefore BFS is complete. \\\n",
        "BFS uses FIFO (first in first out) queue. Put successors at the end of the frontier \\\n",
        "successor list.\n",
        "\n",
        "Branching factor b: when every state expands to b new states. If solution is at \\\n",
        "depth d, then # of nodes expanded is 1 + b + b^2 +...+ b^d at a maximum, \\\n",
        "depending on where solution is found at depth d. This is a exponential complexity \\\n",
        "bound of O(b^d), with time and space complexity being the same, since all nodes \\\n",
        "must be maintained in memory. Memory is a bigger issue than time for BFS. \\\n",
        "Exponential complexity search problems can only be solved for small depths.\n",
        "\n",
        "Uniform cost search (UCS): BFS finds the shallowest goal state, but that might not be \\\n",
        "the least cost.  UCS modifies BFS by expanding the lowest-cost node in the frontier, \\\n",
        "as measured by path cost g(n), rather than the lowest-depth node. BFS is just UCS \\\n",
        "where g(n) = DEPTH(n). UFS will find the cheapest solution provided that the cost of a \\\n",
        "path must never decrease as we go, i.e. g(SUCCESSOR(n)) > g(n). \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "Repeated States: unavoidable when operators are reversible. \\\n",
        "Possible solutions include (in order of increasing effectiveness): \\\n",
        "1) Do not return to the state you just came room by not expanding a successor that is the parent. \\\n",
        "2) Do not create paths with cycles, \\\n",
        "3) Do not generate a state that was generated before. This mean all states have ot be kept in memory, \\\n",
        "with a potential space complexity of O(b^d), or O(s) where S is the number of sates in the space state.\n",
        "\n",
        "In practice, we use hash tables to store generated nodes and avoid duplication. If the state \\\n",
        "space is 'loopier', then it will pay off to store and check states.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "Problem is defined by 1) states, 2) initial state, 3) actions, 4) transition model, \\\n",
        "5) path cost, 6) goal test. Optimal solution is one in which no other solution \\\n",
        "has a lower path cost.\n",
        "\n",
        "Depth first search (DFS) expands the deepest level node. Once it hits a non-goal node \\\n",
        "with no expansion, it goes and expands shallower nodes. We implement DFS with queuing \\\n",
        "function that puts new states at the front of the queue, since its successors will be \\\n",
        "even deeper. DFS has low memory requirements since we only store the path from the root \\\n",
        "to the leaf node, and the remaining unexpanded siblings. For a branching factor b and \\\n",
        "depth m, DFS will have bm nodes to store. Time complexity is O(b^m). DFS is not complete \\\n",
        "or optimal, because it can get stuck in a loop or find a longer solution than is optimal. \\\n",
        "Avoid DFS for deep trees.  DFS is LIFO (last in first out) queue: put succesors \\\n",
        "at the front of the frontier successor list.\n",
        "\n",
        "Depth limited search: imposes a maximum depth on a path, e.g. if we have ten cities, \\\n",
        "then path cannot be greater than 9, the diameter of the state space. \\\n",
        "This is guaranteed to find a solution if exists,\\\n",
        "but still not guaranteed to be optimal. If cutoff is too small, depth limited search \\\n",
        "may not be complete. Given depth limit l, time is O(b^l) and space is O(bl).\n",
        "\n",
        "Iterative deepening search: combines benefits of DFS and BFS by starting at depth 0 \\\n",
        "and then increasing. It is optimal and complete, but has good memory like DFS. \\\n",
        "Order of expansion is similar to BFS, but states are expanded multiple times at \\\n",
        "each iteration. At the bottom level, nodes are expanded once, and a level above \\\n",
        "they are expanded twice. Root is epxanded d + 1 times. Total # of expansions is \\\n",
        "(d + l)l + (d)b + (d - l)b^2 + ... + 3b^(d-2) + 2b^(d-1) + lb^d. \\\n",
        "Time complexity is still O*b^d) and space complexity is still O(bd). \\\n",
        "It is the preferred search method when there is large search space and depth \\\n",
        "of the solution is not known.\n",
        "\n",
        "Bidirectional search: search both forward from initial and backward from goal, \\\n",
        "and stop when you meet in the middle. If solution is at depth d, then solution \\\n",
        "will be found in O(b^(d/2)) steps. Space complexity of uninformed bidirectional \\\n",
        "search is also O(b^(d/2))\n",
        "\n",
        "Time: BFS = b^d, UCS = b^d, DFS = b^m, Depth-limited = b^l, Iter. Deepening = b^d, Bidirect = b^(d/2) \n",
        "Space: BFS = b^d, UCS = b^d, DFS = bm, Depth-limited = bl, Iter. Deepening = bd, Bidirect = b^(d/2) \n",
        "Optimal: BFS = yes, UCS = yes, DFS = no, Depth-limited = no, Iter. Deepening = yes, Bidirect = yes\n",
        "Complete: BFS = yes, UCS = yes, DFS = no, Depth-limited = yes if l > d, Iter. Deepening = yes, Bidirect = yes \n",
        "\n",
        "Graph search: we use an explored list to keep track of nodes so that they are not visited again.\n",
        "\n",
        "Tree search: we don't keep a list, and nodes can be visited multiple times. The tree can contain the same node multiple times.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1626
        },
        "outputId": "d66e2123-554b-4593-c9f0-f31f0222396a"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n One kind of goal-based agent is the problem-solving agent, which finds a sequence of actions to lead to a desirable state. Goal formulation is the first step in problem solving. Multiple factors can affect the desirability of differing ways of achieving the goal. Problem formulation is the process of deciding what actions and states to consider after goal formulation. The process of looking for a sequence that leads to goal state is called search. This algorithm takes a problem and returns a solution in the form of an action sequence. Execution phase is where it carries out the action. \n\n## AIMA Chapter 3.2 Example Problems\n Formulating problems:  a single-state problem is when you find the solution on the first state-change. When the world is not fully accessible, the agent reasons about the set of states to get to, making it a multiple-state problem.\\ \nAgent must calculate a tree of actions, where each branch deals with possible contingencies making this a contingency problem. I.e. you go to clean up dirt, but there is not dirt. \n\nInterleaving of search and execution to achieve goal. Exploration problems are when the agent has no information about it surroundings, and must experiment to solve its goal.\n\nA problem is a collection of information used by the agent to decide what do do. These are the components of a problem definition: 1) initial state of agent, 2) set of possible actions. Operator enotes the action in terms of which state will be reached by carrying out an action in a state. Also called successor function S, where S(x) returns states reachable from x an action. \n\nThe state space of a problem is the set of states reachable from the initial state in a sequence of actions. A path in the state space is a sequence. The goal test is applied to a single state, letting the agent know if it has reached its goal. A path cost function is a function that assigns a cost to a path. Path cost function denoted by g.\n\ninitial state, operator set, goal test, and path cost function define a problem. Output of a search algo is a solution, the path from initial state to goal state.  \n\nA path connects sets of states and a solution is a path that leads to a set of states, all of which are goal states. The state space is then replaced by state set space. \n\nPerformance: does a solution exist, is it a low path cost solution, and third, what is the search cost (time and memory). Total cost is sum of path cost and search cost. Offline cost is search cost and online cost is path cost.\n\nProcess of removing detail from a representation is called abstraction. \n\nNP completeness is nondeterministic polynomial time. Concret way to solve.TSP = travelling salesperson problem. NP-hard = at least as hard as the hardest problem in NP. VLSI chips have cell layout and channel routing problems to minimize area and connection lengths to maximize speed.\n\nGenerate action sequences by applying operators to the current state and expanding the state. We conitinue choosing and expanding until the solution is found, or there are no more states to expand. Choosing which state to expand first is up to  the search strategy. Search tree is the state space, with the root being the initial state. Difference between state space and search tree is that there are finite states, but potentially infinite nodes in search tree if you get caught in a loop.\n\nFringe or frontier is the collection of nodes waiting to be expanded. This is implemented as a queue.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n \nEvaluating search strategies: 1) completeness - is the strategy guaranteed to find a solution if exists, 2) time complexity - how long does it take, 3) space complexity - how much memory does it need, 4) optimality - does it find the highest quality solution if multiple exist?\n\nUninformed search strategies: no information about the number of steps or the path cost from current to goal. They just distinguish goal and non-goal. Also called blind search. This is in contrast to informed search, or heuristic search.\n\nBreadth first search: first expand root, then its immediate children, and then their successors. Nodes at depth d are expanded before nodes at depth d + 1. We \\ \ncan implement BFS using general-search by adding newly generated states to the end of the queue, after all previously generated states.  If solution exists, BFS will find it, and it will always find the shallowest solution. Therefore BFS is complete. BFS uses FIFO (first in first out) queue. Put successors at the end of the frontier successor list.\n\nBranching factor b: when every state expands to b new states. If solution is at depth d, then # of nodes expanded is 1 + b + b^2 +...+ b^d at a maximum, depending on where solution is found at depth d. This is a exponential complexity bound of O(b^d), with time and space complexity being the same, since all nodes must be maintained in memory. Memory is a bigger issue than time for BFS. Exponential complexity search problems can only be solved for small depths.\n\nUniform cost search (UCS): BFS finds the shallowest goal state, but that might not be the least cost.  UCS modifies BFS by expanding the lowest-cost node in the frontier, as measured by path cost g(n), rather than the lowest-depth node. BFS is just UCS where g(n) = DEPTH(n). UFS will find the cheapest solution provided that the cost of a path must never decrease as we go, i.e. g(SUCCESSOR(n)) > g(n). \n\n\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nRepeated States: unavoidable when operators are reversible. Possible solutions include (in order of increasing effectiveness): 1) Do not return to the state you just came room by not expanding a successor that is the parent. 2) Do not create paths with cycles, 3) Do not generate a state that was generated before. This mean all states have ot be kept in memory, with a potential space complexity of O(b^d), or O(s) where S is the number of sates in the space state.\n\nIn practice, we use hash tables to store generated nodes and avoid duplication. If the state space is 'loopier', then it will pay off to store and check states.\n\n## Module 3 Lecture Notes\n \nProblem is defined by 1) states, 2) initial state, 3) actions, 4) transition model, 5) path cost, 6) goal test. Optimal solution is one in which no other solution has a lower path cost.\n\nDepth first search (DFS) expands the deepest level node. Once it hits a non-goal node with no expansion, it goes and expands shallower nodes. We implement DFS with queuing function that puts new states at the front of the queue, since its successors will be even deeper. DFS has low memory requirements since we only store the path from the root to the leaf node, and the remaining unexpanded siblings. For a branching factor b and depth m, DFS will have bm nodes to store. Time complexity is O(b^m). DFS is not complete or optimal, because it can get stuck in a loop or find a longer solution than is optimal. Avoid DFS for deep trees.  DFS is LIFO (last in first out) queue: put succesors at the front of the frontier successor list.\n\nDepth limited search: imposes a maximum depth on a path, e.g. if we have ten cities, then path cannot be greater than 9, the diameter of the state space. This is guaranteed to find a solution if exists,but still not guaranteed to be optimal. If cutoff is too small, depth limited search may not be complete. Given depth limit l, time is O(b^l) and space is O(bl).\n\nIterative deepening search: combines benefits of DFS and BFS by starting at depth 0 and then increasing. It is optimal and complete, but has good memory like DFS. Order of expansion is similar to BFS, but states are expanded multiple times at each iteration. At the bottom level, nodes are expanded once, and a level above they are expanded twice. Root is epxanded d + 1 times. Total # of expansions is (d + l)l + (d)b + (d - l)b^2 + ... + 3b^(d-2) + 2b^(d-1) + lb^d. Time complexity is still O*b^d) and space complexity is still O(bd). It is the preferred search method when there is large search space and depth of the solution is not known.\n\nBidirectional search: search both forward from initial and backward from goal, and stop when you meet in the middle. If solution is at depth d, then solution will be found in O(b^(d/2)) steps. Space complexity of uninformed bidirectional search is also O(b^(d/2))\n\nTime: BFS = b^d, UCS = b^d, DFS = b^m, Depth-limited = b^l, Iter. Deepening = b^d, Bidirect = b^(d/2) \nSpace: BFS = b^d, UCS = b^d, DFS = bm, Depth-limited = bl, Iter. Deepening = bd, Bidirect = b^(d/2) \nOptimal: BFS = yes, UCS = yes, DFS = no, Depth-limited = no, Iter. Deepening = yes, Bidirect = yes\nComplete: BFS = yes, UCS = yes, DFS = no, Depth-limited = yes if l > d, Iter. Deepening = yes, Bidirect = yes \n\nGraph search: we use an explored list to keep track of nodes so that they are not visited again.\n\nTree search: we don't keep a list, and nodes can be visited multiple times. The tree can contain the same node multiple times.\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\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 = \"\"\"Informed search strategies use problem specific knowledge to find \\\n",
        "more efficient solutions than uninformed search.\n",
        "\n",
        "Best-first search a graph-search algo that selects nodes based on an evaluation \\\n",
        "function: f(n). Eval function is a cost estimate, so we select the lowest node \\\n",
        "to expand first. Implementation of best-first search is identical to uniform-\\\n",
        "cost search with the exception of using f instead of g to order the priority \\\n",
        "queue. These algos include a component of f called a heuristic function h(n). \\\n",
        "h(n) = est. cost of the chepaest path from node n to goal state. If n is the goal \\\n",
        "node, then h(n) = 0. \n",
        "\n",
        "Greedy best first search: expands the node that is closest to the goal thinking \\\n",
        "that it will quickly solve it. It purely uses the heuristic function: f(n) = h(n). \\\n",
        "Greedy best first search is not optimal and not complete, much like DFS. It can \\\n",
        "get stuck in infinite loops. Graph search version is complete in finite spaces, \\\n",
        "but not in infinite ones. For the tree search, if m is the maximum depth of the \\\n",
        "search space, the worst case time and space complexity is O(b^m).\n",
        "\n",
        "A* search: minimizes the total estimated solution cost and is the best known \\\n",
        "implementation of best first search. It combines the path cost g(n) and the \\\n",
        "cost to get to the goal h(n). f(n) = h(n) + g(n). This is essentially the \\\n",
        "estimated cost of the cheapest solution to the goal through n.\n",
        "A* space complexity is effectively O(b^d)\n",
        "\n",
        "The first thing we would try is to expand the node with the lowest f(n). A* is \\\n",
        "both complete and optimal and identical to uniform cost search with the \\\n",
        "exception that A* uses g + h rather than just g. \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\"Branching factor: one way to characterize the quality of a heuristic \\\n",
        "is the effective branching factor b*. If nodes generated by A* is N and the solution \\\n",
        "depth is d, then b* is the branching factor that a uniform tree of depth d would have \\\n",
        "in order to contain N+1 nodes. A good heuristic would have a value of b* close to 1. \n",
        "\n",
        "Domination: if for any node h2(n) >= h1(n), we say that h2 dominates h1. Domination \\\n",
        "directly translates to efficiency. Every node with f(n) < C* will be expanded. \\\n",
        "Generally better to use a heuristic function with higher values, provided it is \\\n",
        "consistent.\n",
        "\n",
        "A problem with fewer restrictions on the actions is called a relaxed problem. It \\\n",
        "will however add eges to the state space, and any optimal solution in the original \\\n",
        "problem will be a solution in the relaxed problem, but the relaxed solution might \\\n",
        "be better since there are new edges. Consequently, the cost of an optimal solution \\\n",
        "to a relaxed problem is an admissible heuristic for the original problem. It is \\\n",
        "also consistent.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "UCS is a tree search algorithm using a weighted tree. Extends BFS by expanding \\\n",
        "node with lowest path cost. Implements priority queue ordered by g(n). \\\n",
        "UCS test if node is goal state when it is selected for expansion, not when it is \\\n",
        "added to the frontier. \n",
        "\n",
        "For optimality, we require that h(n) is an admissible heuristic, one that never \\\n",
        "overestimates the cost to reach the goal. Since g(n) is the actual cost to reach \\\n",
        "n, and f(n) = g(n) + h(n), we must have that f(n) never overestimates the true \\\n",
        "cost of a solution through n. Admissible heuristics are optimistic bc they \\\n",
        "think the cost to solve is less than reality. Straight line distance is \\\n",
        "admissible, bc the actual distance can never be less. \n",
        "\n",
        "A 2nd stronger condition is consistency (or monotonicity) which is required for \\\n",
        "graph search implementations of A*. A heuristic is consistent iff for every node \\\n",
        "the estimated cost of reaching the goal is no greater than the step cost of getting \\\n",
        "to its child, plus the estimate of getting from the child to the goal. This is \\\n",
        "like the triangle inequality in that each side of the triangle cannot be greater \\\n",
        "than the sum of the other two sides. Every consistent heuristic is also admissible.\n",
        "\n",
        "Tree-search version of A* is optimial if h(n) is admissible, while graph search \\\n",
        "is optimal if heuristic is consistent. Since A* stores all nodes in memory, \\\n",
        "it will run out of memory before time usually.\n",
        "\n",
        "IDA* (iterative deepening A*): main difference between standard iterative deepening \\\n",
        "and IDA* is that the cutoff is the f-cost rather than the depth. This avoids the \\\n",
        "overhead of storing all nodes.\n",
        "\n",
        "Recursive Best First Search (RCBFS): mimics best-first search in linear space. \\\n",
        "It's similar to recursive depth first search, but rather than going down in depth, \\\n",
        "it uses the f_limit variable to keep track of the f-value of the best alternative \\\n",
        "path from any ancestor to the current node. If the recursion exceeds the limit \\\n",
        "we wind back to the alternative path. RBFS will replace the f-value of each node with a \\\n",
        "backed-up value, the best f-value of its children. This means RBFS will remember the \\\n",
        "best f-value of the leaf in the subtree and can decide to expand later.\n",
        "\n",
        "RBFS is a little more efficient than IDA*, but suffers from node re-exploration. It \\\n",
        "is optimal if the heuristic is admissible. \n",
        "\n",
        "IDA* and RBFS suffer from using too little memory. They forget most of what they \\\n",
        "have done.\n",
        "\n",
        "To use all available memory, we would use MA* (memory bounded A*) and \\\n",
        "simplified memory bounded A* (SMA*). SMA will expand best leaf until memory is full, \\\n",
        "after which it starts dropping the worst leaf from memory. If those are the same, \\\n",
        "SMA will expand the newest best leaf and delete the oldest worst leaf.\n",
        "\n",
        "SMA is complete if there are reachable solutions given the memory constraints. \n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1043
        },
        "cellView": "form",
        "outputId": "0e5fa472-cb81-44e8-8489-7260eb997d2d"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nInformed search strategies use problem specific knowledge to find more efficient solutions than uninformed search.\n\nBest-first search a graph-search algo that selects nodes based on an evaluation function: f(n). Eval function is a cost estimate, so we select the lowest node to expand first. Implementation of best-first search is identical to uniform-cost search with the exception of using f instead of g to order the priority queue. These algos include a component of f called a heuristic function h(n). h(n) = est. cost of the chepaest path from node n to goal state. If n is the goal node, then h(n) = 0. \n\nGreedy best first search: expands the node that is closest to the goal thinking that it will quickly solve it. It purely uses the heuristic function: f(n) = h(n). Greedy best first search is not optimal and not complete, much like DFS. It can get stuck in infinite loops. Graph search version is complete in finite spaces, but not in infinite ones. For the tree search, if m is the maximum depth of the search space, the worst case time and space complexity is O(b^m).\n\nA* search: minimizes the total estimated solution cost and is the best known implementation of best first search. It combines the path cost g(n) and the cost to get to the goal h(n). f(n) = h(n) + g(n). This is essentially the estimated cost of the cheapest solution to the goal through n.\nA* space complexity is effectively O(b^d)\n\nThe first thing we would try is to expand the node with the lowest f(n). A* is both complete and optimal and identical to uniform cost search with the exception that A* uses g + h rather than just g. \n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\nBranching factor: one way to characterize the quality of a heuristic is the effective branching factor b*. If nodes generated by A* is N and the solution depth is d, then b* is the branching factor that a uniform tree of depth d would have in order to contain N+1 nodes. A good heuristic would have a value of b* close to 1. \n\nDomination: if for any node h2(n) >= h1(n), we say that h2 dominates h1. Domination directly translates to efficiency. Every node with f(n) < C* will be expanded. Generally better to use a heuristic function with higher values, provided it is consistent.\n\nA problem with fewer restrictions on the actions is called a relaxed problem. It will however add eges to the state space, and any optimal solution in the original problem will be a solution in the relaxed problem, but the relaxed solution might be better since there are new edges. Consequently, the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. It is also consistent.\n\n## Module 4 Lecture Notes\n\nUCS is a tree search algorithm using a weighted tree. Extends BFS by expanding node with lowest path cost. Implements priority queue ordered by g(n). UCS test if node is goal state when it is selected for expansion, not when it is added to the frontier. \n\nFor optimality, we require that h(n) is an admissible heuristic, one that never overestimates the cost to reach the goal. Since g(n) is the actual cost to reach n, and f(n) = g(n) + h(n), we must have that f(n) never overestimates the true cost of a solution through n. Admissible heuristics are optimistic bc they think the cost to solve is less than reality. Straight line distance is admissible, bc the actual distance can never be less. \n\nA 2nd stronger condition is consistency (or monotonicity) which is required for graph search implementations of A*. A heuristic is consistent iff for every node the estimated cost of reaching the goal is no greater than the step cost of getting to its child, plus the estimate of getting from the child to the goal. This is like the triangle inequality in that each side of the triangle cannot be greater than the sum of the other two sides. Every consistent heuristic is also admissible.\n\nTree-search version of A* is optimial if h(n) is admissible, while graph search is optimal if heuristic is consistent. Since A* stores all nodes in memory, it will run out of memory before time usually.\n\nIDA* (iterative deepening A*): main difference between standard iterative deepening and IDA* is that the cutoff is the f-cost rather than the depth. This avoids the overhead of storing all nodes.\n\nRecursive Best First Search (RCBFS): mimics best-first search in linear space. It's similar to recursive depth first search, but rather than going down in depth, it uses the f_limit variable to keep track of the f-value of the best alternative path from any ancestor to the current node. If the recursion exceeds the limit we wind back to the alternative path. RBFS will replace the f-value of each node with a backed-up value, the best f-value of its children. This means RBFS will remember the best f-value of the leaf in the subtree and can decide to expand later.\n\nRBFS is a little more efficient than IDA*, but suffers from node re-exploration. It is optimal if the heuristic is admissible. \n\nIDA* and RBFS suffer from using too little memory. They forget most of what they have done.\n\nTo use all available memory, we would use MA* (memory bounded A*) and simplified memory bounded A* (SMA*). SMA will expand best leaf until memory is full, after which it starts dropping the worst leaf from memory. If those are the same, SMA will expand the newest best leaf and delete the oldest worst leaf.\n\nSMA is complete if there are reachable solutions given the memory constraints. \n \n\n## Module 4 Definitions\n* **Concept** - definition\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 = \"\"\" Adversarial search is games. Chess is a perferct information game.\\\n",
        "Zero sum game is one in which the payoff to each player is the same for each \\\n",
        "iteration of the game. i.e. chess.\n",
        "Opponents introduce uncertainty. Game-playing programs must \\\n",
        "deal with the contingency problem. Pruning allows us to ignore the parts of \\\n",
        "the search tree that have no impact. Heuristic evaluation functions let us \\\n",
        "approximate the true utility of a state without completely searching. \"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\" MAX and MIN: max moves first. We can define a game as a \\\n",
        "search problem with these components: 1) Initial state of the board and whose \\\n",
        "move it is. 2) Set of operators defining legal moves, 3) Terminal test for \\\n",
        "when the game is over. 4) Utility function (payoff function) which gives a \\\n",
        "numerical outcome to the game. i.e. win/lose = 1/0.\n",
        "\n",
        "MAX must find a strategy that leads to win including the correct move for MAX \\\n",
        "for every possible move by MIN. Two ply is a half move.\n",
        "\n",
        "Minimax algorithm has five steps: 1) generate whole game tree down to terminal states, \\\n",
        "2) apply utility function to get each state's value, 3) use utility to determine value \\\n",
        "of nodes one level higher in the search tree, up until the root, 4) MAX chooses the \\\n",
        "move that leads to the highest value. This is the mininiax decision, using the \\\n",
        "assumption that the opponent will play perfectly to minimize MAX's score.\n",
        "\n",
        "If the max depth of tree is m and there are b legal moves, the time complexity of \\\n",
        "minimax is O(b^m). Algo is a DFS implemented using recursion rather than queue. \\\n",
        "Space req is linear in m and b.\"\"\"\n",
        "\n",
        "chapter5_3 = \"\"\" Evaluation function: gives us an estimate of the expected utility \\\n",
        "of a game from a position. Material value of pawn is 1, knight is 3, etc. A minimax \\\n",
        "algo will be able to determine te exact value of the position based on the terminal \\\n",
        "state, but that takes too long. Evaluation function must balance accuracy of evaluation \\\n",
        "versus the time cost.\n",
        "\n",
        "Material advantage evaluation function would count the values of board pieces as a \\\n",
        "weighted linear function, where w is weights and f is features of a position. \\\n",
        "W would be the value of the pieces (i.e. 1 for pawn), and f would be the number of \\\n",
        "those pieces on the board.\n",
        "\n",
        "Cutting off search: at depth d so that the computer has the alloted time to make \\\n",
        "a move. We could also do iterative deepening and select the move of the deepest \\\n",
        "completed search when time runs out. \n",
        "\n",
        "Quiescent: positions appropriate for the evaluation function that are unlikely \\\n",
        "to exhibit big changes in value in the near future. This extra search is a \\\n",
        "quiescence search.\n",
        " \n",
        "Horizon problem is when opponent is about to cause unavoidable damage. i.e. \\\n",
        "Stalling moves to prevent a pawn from becoming a queen, pushing the queening \\\n",
        "move over the horizon to where it is not detected. This is yet unsolved for \\\n",
        "general approaches. \n",
        "\n",
        "Position evalution function must be a positive linear transformation of the \\\n",
        "liklihood of winning from a position. Expectiminimax must consider all possible \\\n",
        "dice rolls, giving us O(b^m x n^m) complexity, where n is the number of distinct rolls.\n",
        "\n",
        "Alpha-beta pruning: reutrns the same move as minimax, but prunes branches that \\\n",
        "couldn't influence the final decision. Alpha is the value of the best choice we have found \\\n",
        "at any point along the path for MAX. Beta is the best choice we have for MIN. \\\n",
        "Alpha-beta needs to examine only O(b^(m/2)) nodes to pick the best move, while \\\n",
        "minimax needs O(b^m).\n",
        "\n",
        "Transpositions: different permutations of move sequences leading to the same position. \\\n",
        "Hash table of previously seen positions is a transposition table.\"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\" \n",
        "Stochastic games are games of chance.\n",
        "\n",
        "Games of chance: must include chance nodes in addition to MAX \\\n",
        "and MIN nodes. We calculate an expected value, where the average is taken over \\\n",
        "all the possible dice rolls, for instance. Expectimax value is used to assign \\\n",
        "value to chance nodes, after which we compute the expectimin value.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Decision networks are also known as influence diagrams, extending \\\n",
        "belief networks by incorporating actions and utilities. \n",
        "\n",
        "Agents preferences b/n world states are defined by a utility function. U(S) is the \\\n",
        "utility of state S. Nondeterminisitc action A will have possible states Resulti(A), \\\n",
        "where i ranges over the outcomes. Agent assigns probability to each outcome: \\\n",
        "P(Resulti(A)|Do(A),E), where E summarizes the evidence of the world available \\\n",
        "to the agent. Do(A) is the proposition that action A is executed. Then \\ \n",
        "the expected utility of action given evidence EU(A|E) is the sum of \\\n",
        "P(Resulti(A)|Do(A),E) U(Resulti(A)).\n",
        "\n",
        "Maximum expected utility (MEU) says a rational agent chooses the action that \\\n",
        "maximizes expected utility. If an agent maximizes a utility function reflecting \\\n",
        "the performance measure by which it is judged, then it will achieve the highest \\\n",
        "score if we average over possible environments in which to place the agent.\n",
        "\n",
        "This chapter looks at one-shot decisions rather than sequential decisions. \"\"\"\n",
        "\n",
        "chapter16_2 = \"\"\" In utility theory, scenarios are lotteries to emphasize that \\\n",
        "outcomes are like prizes and depende on chance. Lottery L with states A, B and \\\n",
        "probability p for A is L = [p, A; 1 - p, B]. A one outcome lottery would be\\\n",
        "L = [1, A]. A > B means A is preferred to B. A ~ is indifferent to A and B. \\\n",
        "A bigger underscore ~ B is agent prefers A to B or is indifferent. \n",
        "\n",
        "Preferences should be transitive, i.e. A > B, B > C implies A > C.\n",
        "\n",
        "Six constraints of utility theory.  1) Orderability, a rational agent must \\\n",
        "prefer either A or B, or rate them equally. (A > B) V (B > A) V (A ~ B). \\\n",
        "2) Transitivity: (A > B) AND (B > C) --> (A > C). 3) Continuity: if state B is \\\n",
        "between A and C in preference, then there is a probability p for which the agent \\\n",
        "will be indifferent b/n getting B for certain and the lottery that yields A with \\\n",
        "probability p and C with probability 1 - p. A > B ? C --> there exists  \\\n",
        "p [p,A; 1-p, C] ~  B. 4) Substitutability: if an agent is indifferent, then \\\n",
        "the agent is indifferent b/n more complex lotteries where it gets B vs. A. \\\n",
        "5) Monotonicity: if there are two lotteries that have the same outcomes, and an \\\n",
        "agent prefers A to B, then the agent must prefer the lottery that has a higher \\\n",
        "probability for A. 6) Decomposability: compound lotteries can be reduced to simpler \\\n",
        "ones using the laws of probability. No fun in gambling rule. \n",
        "\n",
        "Preference is the basic property of rational agents. Utility principle: if an \\\n",
        "agent's preferences obey the axioms of utility, then there is a real function U that \\\n",
        "operates on states s.t. U(A) ? U(B) iff A > B and U(A) - U(B) iff agent is indifferent \\\n",
        "between A and B. U(A) > U(B) <--> A > B, U(A) = U(B) <--> A ~ B.\n",
        "\n",
        "Maximum expected utility principle: the utility of a lottery is the sum of the probs \\\n",
        "of each outcome times the utility of that outcome.\"\"\"\n",
        "\n",
        "chapter16_3 = \"\"\" Utility func maps states to numbers. \n",
        "\n",
        "Utility of money: agent exhibits monotonic preference for money. Money is a value function \\\n",
        "or oridinal utility measure, meaning we just prefer to have more than less when \\\n",
        "thinking about definite amounts.\n",
        "\n",
        "Risk averse: preferring a sure payoff less than expected value of gamble. Risk-seeking. \\\n",
        "The value an agent will take before a lottery is the certainty equivalent. Difference \\\n",
        "between the expected value and the certainty equivalent is the insurance premium. Kinda \\\n",
        "like car insurance. Risk-neutral is linear curve.\n",
        "\n",
        "Normalized utilities have a 0 to 1 scale of best possible prize and worst case.\n",
        "\n",
        "Decision theory is normative theory describing how a rational agent should act. \\\n",
        "Opposite is descriptive theory of actual human decisions.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Simplest game environment is multi-agent, static, discret, fully obverable, \\\n",
        "and strategic.\n",
        "\n",
        "For minimax, even levels are MAX turns, and odd levels are MIN turns.\\ \n",
        "Evaluation function f assigns number scores to board states without \\\n",
        "reference to the path. Backed up value of each node is determined by the value \\\n",
        "of its children. For MAX node, value is th emax of its children. For MIN node, \\\n",
        "value is the min of its children. \n",
        "\n",
        "Alpha-beta pruning keeps track of two additional values: alpha, MAX's current \\\n",
        "upper bound. and beta, MIN's current upper bound. Max will never allow for a \\\n",
        "move that could lead to a worse score than alpha. Min will never allow for a \\\n",
        "move that could lead to a better score than beta. \n",
        "\n",
        "Expectimax search computes the average score under the optimal play by \\\n",
        "including max nodes as in minimax and chance nodes are like min nodes but \\\n",
        "the outcome is uncertain. We calculate their expected utilities by taking \\\n",
        "weighted average of children. This could be built into Markov Decision process.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1844
        },
        "outputId": "0be175e0-3469-41b1-8971-694f0e6daad8"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Adversarial search is games. Chess is a perferct information game.Zero sum game is one in which the payoff to each player is the same for each iteration of the game. i.e. chess.\nOpponents introduce uncertainty. Game-playing programs must deal with the contingency problem. Pruning allows us to ignore the parts of the search tree that have no impact. Heuristic evaluation functions let us approximate the true utility of a state without completely searching. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n MAX and MIN: max moves first. We can define a game as a search problem with these components: 1) Initial state of the board and whose move it is. 2) Set of operators defining legal moves, 3) Terminal test for when the game is over. 4) Utility function (payoff function) which gives a numerical outcome to the game. i.e. win/lose = 1/0.\n\nMAX must find a strategy that leads to win including the correct move for MAX for every possible move by MIN. Two ply is a half move.\n\nMinimax algorithm has five steps: 1) generate whole game tree down to terminal states, 2) apply utility function to get each state's value, 3) use utility to determine value of nodes one level higher in the search tree, up until the root, 4) MAX chooses the move that leads to the highest value. This is the mininiax decision, using the assumption that the opponent will play perfectly to minimize MAX's score.\n\nIf the max depth of tree is m and there are b legal moves, the time complexity of minimax is O(b^m). Algo is a DFS implemented using recursion rather than queue. Space req is linear in m and b.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Evaluation function: gives us an estimate of the expected utility of a game from a position. Material value of pawn is 1, knight is 3, etc. A minimax algo will be able to determine te exact value of the position based on the terminal state, but that takes too long. Evaluation function must balance accuracy of evaluation versus the time cost.\n\nMaterial advantage evaluation function would count the values of board pieces as a weighted linear function, where w is weights and f is features of a position. W would be the value of the pieces (i.e. 1 for pawn), and f would be the number of those pieces on the board.\n\nCutting off search: at depth d so that the computer has the alloted time to make a move. We could also do iterative deepening and select the move of the deepest completed search when time runs out. \n\nQuiescent: positions appropriate for the evaluation function that are unlikely to exhibit big changes in value in the near future. This extra search is a quiescence search.\n \nHorizon problem is when opponent is about to cause unavoidable damage. i.e. Stalling moves to prevent a pawn from becoming a queen, pushing the queening move over the horizon to where it is not detected. This is yet unsolved for general approaches. \n\nPosition evalution function must be a positive linear transformation of the liklihood of winning from a position. Expectiminimax must consider all possible dice rolls, giving us O(b^m x n^m) complexity, where n is the number of distinct rolls.\n\nAlpha-beta pruning: reutrns the same move as minimax, but prunes branches that couldn't influence the final decision. Alpha is the value of the best choice we have found at any point along the path for MAX. Beta is the best choice we have for MIN. Alpha-beta needs to examine only O(b^(m/2)) nodes to pick the best move, while minimax needs O(b^m).\n\nTranspositions: different permutations of move sequences leading to the same position. Hash table of previously seen positions is a transposition table.\n\n## AIMA Chapter 5.5 Stochastic Games\n \nStochastic games are games of chance.\n\nGames of chance: must include chance nodes in addition to MAX and MIN nodes. We calculate an expected value, where the average is taken over all the possible dice rolls, for instance. Expectimax value is used to assign value to chance nodes, after which we compute the expectimin value.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Decision networks are also known as influence diagrams, extending belief networks by incorporating actions and utilities. \n\nAgents preferences b/n world states are defined by a utility function. U(S) is the utility of state S. Nondeterminisitc action A will have possible states Resulti(A), where i ranges over the outcomes. Agent assigns probability to each outcome: P(Resulti(A)|Do(A),E), where E summarizes the evidence of the world available to the agent. Do(A) is the proposition that action A is executed. Then \\ \nthe expected utility of action given evidence EU(A|E) is the sum of P(Resulti(A)|Do(A),E) U(Resulti(A)).\n\nMaximum expected utility (MEU) says a rational agent chooses the action that maximizes expected utility. If an agent maximizes a utility function reflecting the performance measure by which it is judged, then it will achieve the highest score if we average over possible environments in which to place the agent.\n\nThis chapter looks at one-shot decisions rather than sequential decisions. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n In utility theory, scenarios are lotteries to emphasize that outcomes are like prizes and depende on chance. Lottery L with states A, B and probability p for A is L = [p, A; 1 - p, B]. A one outcome lottery would beL = [1, A]. A > B means A is preferred to B. A ~ is indifferent to A and B. A bigger underscore ~ B is agent prefers A to B or is indifferent. \n\nPreferences should be transitive, i.e. A > B, B > C implies A > C.\n\nSix constraints of utility theory.  1) Orderability, a rational agent must prefer either A or B, or rate them equally. (A > B) V (B > A) V (A ~ B). 2) Transitivity: (A > B) AND (B > C) --> (A > C). 3) Continuity: if state B is between A and C in preference, then there is a probability p for which the agent will be indifferent b/n getting B for certain and the lottery that yields A with probability p and C with probability 1 - p. A > B ? C --> there exists  p [p,A; 1-p, C] ~  B. 4) Substitutability: if an agent is indifferent, then the agent is indifferent b/n more complex lotteries where it gets B vs. A. 5) Monotonicity: if there are two lotteries that have the same outcomes, and an agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A. 6) Decomposability: compound lotteries can be reduced to simpler ones using the laws of probability. No fun in gambling rule. \n\nPreference is the basic property of rational agents. Utility principle: if an agent's preferences obey the axioms of utility, then there is a real function U that operates on states s.t. U(A) ? U(B) iff A > B and U(A) - U(B) iff agent is indifferent between A and B. U(A) > U(B) <--> A > B, U(A) = U(B) <--> A ~ B.\n\nMaximum expected utility principle: the utility of a lottery is the sum of the probs of each outcome times the utility of that outcome.\n\n## AIMA Chapter 16.3 Utility Functions\n Utility func maps states to numbers. \n\nUtility of money: agent exhibits monotonic preference for money. Money is a value function or oridinal utility measure, meaning we just prefer to have more than less when thinking about definite amounts.\n\nRisk averse: preferring a sure payoff less than expected value of gamble. Risk-seeking. The value an agent will take before a lottery is the certainty equivalent. Difference between the expected value and the certainty equivalent is the insurance premium. Kinda like car insurance. Risk-neutral is linear curve.\n\nNormalized utilities have a 0 to 1 scale of best possible prize and worst case.\n\nDecision theory is normative theory describing how a rational agent should act. Opposite is descriptive theory of actual human decisions.\n\n## Module 5 Lecture Notes\n\nSimplest game environment is multi-agent, static, discret, fully obverable, and strategic.\n\nFor minimax, even levels are MAX turns, and odd levels are MIN turns.\\ \nEvaluation function f assigns number scores to board states without reference to the path. Backed up value of each node is determined by the value of its children. For MAX node, value is th emax of its children. For MIN node, value is the min of its children. \n\nAlpha-beta pruning keeps track of two additional values: alpha, MAX's current upper bound. and beta, MIN's current upper bound. Max will never allow for a move that could lead to a worse score than alpha. Min will never allow for a move that could lead to a better score than beta. \n\nExpectimax search computes the average score under the optimal play by including max nodes as in minimax and chance nodes are like min nodes but the outcome is uncertain. We calculate their expected utilities by taking weighted average of children. This could be built into Markov Decision process.\n\n\n\n## Module 5 Definitions\n* **Concept** - definition\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 = \"\"\" Using a factored representation for each state, a set of variables each of which has a value. \\\n",
        "Problem is solved when each variable has a value that satisfies all the constraints on the variable. This is a \\\n",
        "constraint satisfaction problem (CSP). CSP uses general-purpose rather than problem-specific heuristics. Idea \\\n",
        "is to eliminate large portions of the search space by identifying variable that violate the constraints.\n",
        "\n",
        "CSP problems consists of three components: X, D, and C, where X is a set of variables, D is a set of domains, \\\n",
        "one for each variable, and C is a set of constraints that specify valid values. Each state in a CSP is defined \\\n",
        "by an assignemtn of values to some or all of the variables. A consistent or legal assignment does not violate \\\n",
        "any constraints. A complete assignment is where all variables have been assigned and a solution to a CSP \\\n",
        "is a consistent, complete assignment. A partial assignment is one where they're not all assigned. \n",
        "\n",
        "CSP solvers can be faster than state-space searchers bc CSP can eliminate large swathes of the search space. \\\n",
        "Precedence constraints can represent timing of tasks for instance. We could say that we have a disjunctive \\\n",
        "constraint if employees have to share the same tool for two different tasks for instance.\n",
        "\n",
        "Simple CSP involves discrete, finite domains. Some discrete domains can be infinite (ie. list all numbers), \\\n",
        "so we can't list all the allowed combinations. Here we use a constraint language (i.e. linear constraints). \\\n",
        "No algo exists to solve nonlinear constraints on integer variables.\n",
        "\n",
        "Unary constraints restrict variable to one valuei, i.e. Melbourne can't be green. Binary constraints relate \\\n",
        "two variables,i.e. Canberra cannot be same color as Queensland. Global constraint involves arbitrary number \\\n",
        "of variables (not ~all~ variables.) Common one would be all different colors or variables constraint. They can \\\n",
        "be represented in a constraint hypergraph with nodes as circles and constraints as squares. Real world also \\\n",
        "includes preferene constraints where solutions are not invalid, but preferred. This turns the problem into \\\n",
        "a constraint optimization problem.\"\"\"\n",
        "\n",
        "chapter6_2 = \"\"\" Constraint propogation. In state-space search, the algo can only search, but in CSP, we can \\\n",
        "choose and search or do inference called constraint propogation. This is reducing the number of legal values \\\n",
        "for a variable.\n",
        "\n",
        "Local consistency: if we treat a variable as a node and constriants as arcs, we enforce local consistency. There \\\n",
        "are different kinds of local consistency listed below. 1) Node consistency: if all values in the variable's \\\n",
        "domain satisfy the variable's unary constraints. 2) Arc consistency: if every value in the domain satsifies \\\n",
        "the variable's binary constraints. This wouldn't solve the Australia map coloring scenario since there would \\\n",
        "be no change in the values.\n",
        "\n",
        "AC-3 is the most popular arc-consistent algo. It maintains a queue of arcs to consider (really a set since order \\\n",
        "does not matter). If it pops an arc and reduces the domain to be consistent, and nothing happens, we just \\\n",
        "continue to the next arc. Otherwise it adds all the neighboring arcs to the queue. If something is revised \\\n",
        "down to nothing, then we know the algo has failed and there is no solution. Worst case time consistency is \\\n",
        "O(cd^3), where d is the number of times an arc is inserted into the queue (since it has at most d values to delete).\n",
        "\n",
        "Arc consistency tightens down the domains (unary constraints) using arcs (binary constraints). To solve the \\\n",
        "Australia coloring though when each has two options, we need path consistency. Path consistency tightens the \\\n",
        "binary constraints by using implicit constraints that are inferred by looking at triples of variables. i.e. \\\n",
        "make Queensland and Canberra path consistent relative to Melbourne. PC-2 is the path consistency algo.\n",
        "\n",
        "K-consistency: a CSP is k-consistent, if for any set of k - 1 variables and for consistent assignments, \\\n",
        "a consistent value can always be assigned to any kth variable. 1-consistency is node consistency, \\\n",
        "2-consistency is arc consistency. 3-consistency is path consistency. CSP is strongly k-consistent, \n",
        "if for any k it is also consistent down to k-1 all the way to 1-consistent. i.e. 1,2,3,4 consistent.\n",
        "\n",
        "In addition to Alldiff, there is the resource-constraint called atmost constraint. Bounds propogation \\\n",
        "is used when we can't list all the options, so just have bounds. \"\"\"\n",
        "\n",
        "chapter6_3 = \"\"\" Some CSPs can be solved just by inference, but sometimes we do have to search for a solution along \\\n",
        "partial assignments. CSPs have commutativity - a problem is commutative if the order of application of any given \\\n",
        "action has no effect on the outcome, i.e. we'll reach the same partial assignment regardless of the order we \\\n",
        "filled it in. Therefore we only to consider a ginle variable at each node in the search tree. This gives us a \\\n",
        "number of leaves of d^n. \n",
        "\n",
        "Backtracking search: is a DFS that chooses values for one variable at a time and backtracks when it has no legal values. \\\n",
        "We can solve CSPs without domain specific knowledge, i.e. heuristics(informed search). We start by choosing the value \\\n",
        "with the fewest legal moves left. This is minimum remaining values (MRV) heuristic, or the most constrained value, \\\n",
        "or fail first. For instance, if we pick one with 0 remaining values, we'll return failure immediately.\n",
        "\n",
        "For Australia, where each had 3 remaining options, we use degree heuristic. Select the variable that is \\\n",
        "involved with the largest number of constraints. Once we've selected something, it's useful to explore in the \\\n",
        "least constraining value heuristic because we rule out the fewest choices for neighbors. \n",
        "\n",
        "Interleaving search and inference: AC-3 runs before we begin searching, and after which we can re-run it. \\\n",
        "Alternatively, forward checking occurs after we assign X a variable, we forward check to establish arc consistency for it. \\\n",
        "There is no need to do forward checking if we pre-process with AC-3 arc consistency. Forward checking also doesn't \\\n",
        "make all variables arc-consistent, just the current one. This is solved with MAC (Maintaining Arc Consistency) \\\n",
        "which calls AC-3 but instead of a queue of all arcs, we only do unassigned neighbors. MAC is more powerful than \\\n",
        "forward checking.\n",
        "\n",
        "Backtracking search uses chronological backtracking because the most recent decision point is revisited after \\\n",
        "something fails. A better approach would be to go to the node that caused the conflict, by keeping track of \\\n",
        "a conflict set. This backjumping method backtracks to the most recent assignment in the conflict set.  We \\\n",
        "could populate the conflict set with forward checking by adding what was deleted. Every branch pruned by \\\n",
        "backjumping is also pruned by forward checking, so single backjumping is redundant to forward checking. \\\n",
        "One implementation is conflict-directed backjumping. Constraint learning is the idea of finding a min \\\n",
        "set of variables from the conflict set that cause problems. This new set of variables is the no-good.\n",
        " \"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\" Local search: when we choose a new value for a variable, it makes sense to select \\\n",
        "the value that results in the min number of conflicts. This is the min-conflicts heuristic. \"\"\"\n",
        "\n",
        "chapter6_5 = \"\"\"  In the Australia coloring problem, Tasmania is an independent subproblem since \\\n",
        "it's not a connected component. To solve a tree-structured CSP, pick any variable to be the root \\\n",
        "and choose an ordering of the variables appears after its parent in the tree. This is called \\\n",
        "a topological sort. Any tree-structured CSP can be solved in time linear to the number of variables. \\\n",
        "Directed arc consistency (DAC) is an ordering of variables. \n",
        "\n",
        "Cutset conditioning can reduce a general CSP to a tree-structured one and is efficient if a small \\\n",
        "cutset is found. Tree decomposition transform the CSP into a tree of sub-problems and are efficient \\\n",
        "if the tree width of the constraint graph is small.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "\n",
        "CSPs can vary by discrete variables (finite domains and infinite domains), and \\\n",
        "continous variables (e.g. start end times for hubble observations)\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1475
        },
        "outputId": "e2735e7b-c7ef-41a3-81cc-ab22718c5b3f"
      },
      "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": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Using a factored representation for each state, a set of variables each of which has a value. Problem is solved when each variable has a value that satisfies all the constraints on the variable. This is a constraint satisfaction problem (CSP). CSP uses general-purpose rather than problem-specific heuristics. Idea is to eliminate large portions of the search space by identifying variable that violate the constraints.\n\nCSP problems consists of three components: X, D, and C, where X is a set of variables, D is a set of domains, one for each variable, and C is a set of constraints that specify valid values. Each state in a CSP is defined by an assignemtn of values to some or all of the variables. A consistent or legal assignment does not violate any constraints. A complete assignment is where all variables have been assigned and a solution to a CSP is a consistent, complete assignment. A partial assignment is one where they're not all assigned. \n\nCSP solvers can be faster than state-space searchers bc CSP can eliminate large swathes of the search space. Precedence constraints can represent timing of tasks for instance. We could say that we have a disjunctive constraint if employees have to share the same tool for two different tasks for instance.\n\nSimple CSP involves discrete, finite domains. Some discrete domains can be infinite (ie. list all numbers), so we can't list all the allowed combinations. Here we use a constraint language (i.e. linear constraints). No algo exists to solve nonlinear constraints on integer variables.\n\nUnary constraints restrict variable to one valuei, i.e. Melbourne can't be green. Binary constraints relate two variables,i.e. Canberra cannot be same color as Queensland. Global constraint involves arbitrary number of variables (not ~all~ variables.) Common one would be all different colors or variables constraint. They can be represented in a constraint hypergraph with nodes as circles and constraints as squares. Real world also includes preferene constraints where solutions are not invalid, but preferred. This turns the problem into a constraint optimization problem.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint propogation. In state-space search, the algo can only search, but in CSP, we can choose and search or do inference called constraint propogation. This is reducing the number of legal values for a variable.\n\nLocal consistency: if we treat a variable as a node and constriants as arcs, we enforce local consistency. There are different kinds of local consistency listed below. 1) Node consistency: if all values in the variable's domain satisfy the variable's unary constraints. 2) Arc consistency: if every value in the domain satsifies the variable's binary constraints. This wouldn't solve the Australia map coloring scenario since there would be no change in the values.\n\nAC-3 is the most popular arc-consistent algo. It maintains a queue of arcs to consider (really a set since order does not matter). If it pops an arc and reduces the domain to be consistent, and nothing happens, we just continue to the next arc. Otherwise it adds all the neighboring arcs to the queue. If something is revised down to nothing, then we know the algo has failed and there is no solution. Worst case time consistency is O(cd^3), where d is the number of times an arc is inserted into the queue (since it has at most d values to delete).\n\nArc consistency tightens down the domains (unary constraints) using arcs (binary constraints). To solve the Australia coloring though when each has two options, we need path consistency. Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. i.e. make Queensland and Canberra path consistent relative to Melbourne. PC-2 is the path consistency algo.\n\nK-consistency: a CSP is k-consistent, if for any set of k - 1 variables and for consistent assignments, a consistent value can always be assigned to any kth variable. 1-consistency is node consistency, 2-consistency is arc consistency. 3-consistency is path consistency. CSP is strongly k-consistent, \nif for any k it is also consistent down to k-1 all the way to 1-consistent. i.e. 1,2,3,4 consistent.\n\nIn addition to Alldiff, there is the resource-constraint called atmost constraint. Bounds propogation is used when we can't list all the options, so just have bounds. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Some CSPs can be solved just by inference, but sometimes we do have to search for a solution along partial assignments. CSPs have commutativity - a problem is commutative if the order of application of any given action has no effect on the outcome, i.e. we'll reach the same partial assignment regardless of the order we filled it in. Therefore we only to consider a ginle variable at each node in the search tree. This gives us a number of leaves of d^n. \n\nBacktracking search: is a DFS that chooses values for one variable at a time and backtracks when it has no legal values. We can solve CSPs without domain specific knowledge, i.e. heuristics(informed search). We start by choosing the value with the fewest legal moves left. This is minimum remaining values (MRV) heuristic, or the most constrained value, or fail first. For instance, if we pick one with 0 remaining values, we'll return failure immediately.\n\nFor Australia, where each had 3 remaining options, we use degree heuristic. Select the variable that is involved with the largest number of constraints. Once we've selected something, it's useful to explore in the least constraining value heuristic because we rule out the fewest choices for neighbors. \n\nInterleaving search and inference: AC-3 runs before we begin searching, and after which we can re-run it. Alternatively, forward checking occurs after we assign X a variable, we forward check to establish arc consistency for it. There is no need to do forward checking if we pre-process with AC-3 arc consistency. Forward checking also doesn't make all variables arc-consistent, just the current one. This is solved with MAC (Maintaining Arc Consistency) which calls AC-3 but instead of a queue of all arcs, we only do unassigned neighbors. MAC is more powerful than forward checking.\n\nBacktracking search uses chronological backtracking because the most recent decision point is revisited after something fails. A better approach would be to go to the node that caused the conflict, by keeping track of a conflict set. This backjumping method backtracks to the most recent assignment in the conflict set.  We could populate the conflict set with forward checking by adding what was deleted. Every branch pruned by backjumping is also pruned by forward checking, so single backjumping is redundant to forward checking. One implementation is conflict-directed backjumping. Constraint learning is the idea of finding a min set of variables from the conflict set that cause problems. This new set of variables is the no-good.\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search: when we choose a new value for a variable, it makes sense to select the value that results in the min number of conflicts. This is the min-conflicts heuristic. \n\n## AIMA Chapter 6.5 The Structure of Problems\n  In the Australia coloring problem, Tasmania is an independent subproblem since it's not a connected component. To solve a tree-structured CSP, pick any variable to be the root and choose an ordering of the variables appears after its parent in the tree. This is called a topological sort. Any tree-structured CSP can be solved in time linear to the number of variables. Directed arc consistency (DAC) is an ordering of variables. \n\nCutset conditioning can reduce a general CSP to a tree-structured one and is efficient if a small cutset is found. Tree decomposition transform the CSP into a tree of sub-problems and are efficient if the tree width of the constraint graph is small.\n\n## Module 6 Lecture Notes\n \n\nCSPs can vary by discrete variables (finite domains and infinite domains), and continous variables (e.g. start end times for hubble observations)\n\n \n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"We make a knowledge based agent by TELLing it what it needs to know. \\\n",
        "Declarative approach to system building is adding sentences that represent the \\\n",
        "designer's knowledge of the environment, i.e. background knowledge. \\\n",
        "We can also design learning mechanisms that \\\n",
        "output knowledge about the environment given a series of percepts. Adding a learning \\\n",
        "mechanism to a knowledge-based agent can make it autonomous.\n",
        "\n",
        "Knowledge Base (KB) is a set of representations of facts of the world. \\\n",
        "Each one is called a sentence, expressed in a knowledge representatoin language. \\\n",
        "TELL is giving knowledge, and ASK is querying knoweldge.\n",
        "\n",
        "Inference mechanism determines what follows from what the KB has told the agent.\n",
        "\n",
        "Knowledge-based agents have three levels: 1) knoledge level (epistemological) is most abstract \\\n",
        "describing what an agent knows (i.e. automated taxi knows how to get between two cities.) \\\n",
        "2) Logical level is where knowledge is encoded in sentences, e.g. Link(City1, City2). \\\n",
        "3) Implementation level is level that runs on architecture\"\"\"\n",
        "\n",
        "chapter7_2 = \"\"\"Wumpus world of cave systems with pits and gold.\"\"\"\n",
        "\n",
        "chapter7_3 = \"\"\"Knowledge representation is how we express knowledge in computer form. \\\n",
        "It has two aspects; 1) the syntax, 2) the semantics - an agent believes a corresponding \\\n",
        "sentence in its KB. e.g. x > y means nothing if the semantic of greater than does not exist. \\\n",
        "Correctly combined, the synatax and semantics make a logic.\n",
        "\n",
        "Since sentences are physical configurations of an agent, reasoning must construct new \\\n",
        "configurations from old ones. Proper reasoning is that facts actually follow from \\\n",
        "older facts. \n",
        "\n",
        "Entailment is the relationship between sentences in which new sentences are true \\\n",
        "given older sentences. KB entails alpha, or KB = alpha. An inference procedure \\\n",
        "that generates only entailed sentences is sound or truth preserving. Record of \\\n",
        "operation of a sound inference procedure is a proof. \n",
        "\n",
        "An inference procedure is complete if it can prove any sentence that is entailed. \\\n",
        "Proof theory of the language specifies which reasoning stpes are sound. A sentence \\\n",
        "does not mean something by itself. Compositional - the meaning of a sentence is a \\\n",
        "function of the meaning of its parts.\n",
        "\n",
        "Sound reasoning is logical inference or deduction, implementing the entailment \\\n",
        "relation between sentences. Necessarily true sentence: sentence is valid iff it \\\n",
        "is true under all interpretations in all possible worlds. Also called analytic \n",
        "sentences or tautologies for valid sentences.\n",
        "\n",
        "Sentence is satisfiable iff there is an interpretation in some world in which \\\n",
        "it is true. Unsatisfiable includes self-contradictions.\n",
        "\n",
        "Logic consists of 1) a formal system for describing things that is composed of \\\n",
        "(a) the syntax of the language which describes how to make sentences, and (b) \\\n",
        "the semantics of the language on how sentences relate to states, and 2) the proof \\\n",
        "theory for deducing the entailment of a set of sentences.\n",
        "\n",
        "Two kinds of logic: propositional or boolean, and first-order logic. Propositional \\\n",
        "logic is represented with symbols and boolean connectives. First order logic \\\n",
        "represents the world as objects and predicates on objects, as well as connectives \\\n",
        "and quantifiers. \n",
        "\n",
        "Ontological commitments are concerned with nature of reality that do or do not hold. \\\n",
        "Temporal logic is time based. Epistemological commitments concern the states of knowledge \\\n",
        "an agent can have using types of logic. There can be range on the degree of belief \\\n",
        "of a truth. i.e. 50% sure this is right. Fuzzy logic is degrees of truth \n",
        "\n",
        "Language | Ontological Commitment (what exists in the world) | Epistemological Commitment (what an agent believes) \\\n",
        "Propositional Logic  | facts | true/false/unknown\n",
        "First-order logic | facts/objects/relation |  true/false/unknown\n",
        "Temporal Logic | facts/objects/relations/time |  true/false/unknown\n",
        "Probability theory | facts | degree of believe 0 to 1\n",
        "Fuzzy logic | degree of truth | degree of believe 0 to 1\n",
        "\"\"\"\n",
        "\n",
        "chapter7_4 = \"\"\" Rules of propositional logic: 1) logical constants true and false are sentences \\\n",
        "by themselves, 2) propositional symbols P and Q are sentences, 3) wrapping parentheses forms a \\\n",
        "sentence. e.g. (P and Q), 4) sentence can be formed by combined simpler sentences.\n",
        "\n",
        "Five logical connectives: 1) And (A), 2) Or (V). In 'A V (P AND Q)' we have a disjunction \\\n",
        "of the disjuncts A and (P AND Q). 3) Implies (-->). In '(P AND Q) --> R', we have an \\\n",
        "implication where the premise (antecedent) is (P AND Q) and the conclusion or consequent \\\n",
        "is R. Implication is also called rules or if-then. 4) Equivalent (<-->) creates an equivalence \\\n",
        "or a biconditional. 5) Not. Negation is the only connective that operates on a single sentence.\n",
        "\n",
        "Atomic sentences consist of one symbol. Complex sentences contain connectives or parentheses. \\\n",
        "Literal is an atomic sentence or a negated atomic sentence.\n",
        "\n",
        "Order of precedence is: negation, AND, OR, implies, equivalent.\n",
        "\n",
        "A sentence containing just a propositional symbol is satisfiable but not valid. \n",
        "\n",
        "Implication is different in that if P is true, then I am claiming Q is true. Otherwise, \\\n",
        "I am making no claim.  \n",
        "\n",
        "A world in which a sentence is true given an interpretation is called a model \\\n",
        "of that sentence given the interpretation. \n",
        "\n",
        "Entailment: a sentence a is entailed by a KB if the models of the KB are all models of a.\n",
        "\n",
        "Inference rules are classes of inferences that can be generalized for similar patterns. \\\n",
        "Here are 7 such rules: 1) modus ponens or implication-elimination: from an implication \\\n",
        "and the premise of the implication, you can infer the conclusion. 2) and-elimination: \\\n",
        "from a conjunction, you can infer the conclusion. 3) and-introduction: from a list of \\\n",
        "sentences, you can infer their conjunction. 4) or-introduction: from a sentence, you \\\n",
        "can infer its disjunction with anything else at all. 5) double-negation elimination: \\\n",
        "from a doubly negated sentence, you can infer a positive sentence. 6) unit resolution: \\\n",
        "from a disjunction, if one of the disjuncts is false, then you can infer the other is true.\\\n",
        " 7) resolution: bc 0 cannot be both true and false, on of the other disjuncts must be true in \\\n",
        " one of the premises. Equivalently, implication is transitive.\n",
        " \n",
        " Monotonicity: if you add sentences to a KB and everything is still entailed.  \"\"\"\n",
        "\n",
        "chapter7_5 = \"\"\" \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "\n",
        "Two kinds of sentences: 1) axioms, a sentence that is given, 2) derived sentences, \\\n",
        "which are infered from other sentences.\n",
        "\n",
        "sound - the inference algo only derives entailed sentences. \\\n",
        "complete - an inference algorithm is complete if it can derive all sentneces \\\n",
        "that are entailed.\n",
        "\n",
        "(a and b) = (b and a): commutativity of and\n",
        "(a or b) = (b or a): commutativity of or \n",
        "((a and b) and c) = (a and (b and c)): associativity of and \n",
        "((a or b) or c) = (a or (b or c)): associativity of or \n",
        "not(not a) = a: double negation elimination \n",
        "(a implies b) = (not b implies not a): contraposition\n",
        "(a <==> b) = ((a implies b) and (b implies a)): biconditional elimination\n",
        "not(a and b) = (not a or not b): de morgan\n",
        "not(a or b) = (not a and not b): de morgan\n",
        "((a and b) or c) = ((a and b) or (a and c)): distributivity of and over or\n",
        "((a or b) and c) = ((a or b) and (a or c)): distibutivity of or over and \n",
        "\n",
        "Monotonicity implies soundness. resolution yields a complete inference algorithm.\n",
        "\n",
        "CNF: conjunctive normal form: every sentence of propositional logic is equivalent \\\n",
        "to a conjunction of clauses. Clauses are disjunctions of literals. Steps: \\\n",
        "1) Eliminate <==> by replacing (A <==> B) with (a ==> B) and (B implies A). \\\n",
        "2) Elminate ==> implies by replacing A ==> B with (not A or B).\n",
        "3) move not inwards by elminating double negations and apply de morgan's rules. \n",
        "4)Apply distibutivity laws to distibute or over and whenever possible. \n",
        "\n",
        "Definite clause: disjunction of literals where exactly one is postive. Horn clause:\n",
        "disjunction of literals wher eat most one is positive. This includes definite clauses, \\\n",
        "and clauses with no positive literals. \n",
        "\n",
        "Forward chaining: is data driven reasoning to derive new conclusions. Backward chaining: \\\n",
        "works backwards from a query. If it is true, no work is needed. Otherwise, if all \\\n",
        "premises can be proven, then the quey is true. \n",
        "\n",
        "Following are in CNF (conjunctive normal form): (A), (A or B), (A or B) and (C), \\\n",
        "(A or not B or not C) and (not D or E or F). \n",
        "\n",
        "The following are not in CNF: not (B or C), since or is nested within a not, (A and B) or C, \\\n",
        "A and (B or (D and E)), since an AND is nested within a OR.\n",
        "\n",
        "To convert: 1) convert to negation normal form by replacing P --> Q with not P or Q, \\\n",
        "replace P <--> Q with (P or not Q) and (not P or Q). Move NOTs inward by replacing \\\n",
        "not(P or Q) with (not P) and (not Q). Replace  \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1735
        },
        "outputId": "cb2f77a8-58da-4398-c111-1d1339afb839"
      },
      "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": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nWe make a knowledge based agent by TELLing it what it needs to know. Declarative approach to system building is adding sentences that represent the designer's knowledge of the environment, i.e. background knowledge. We can also design learning mechanisms that output knowledge about the environment given a series of percepts. Adding a learning mechanism to a knowledge-based agent can make it autonomous.\n\nKnowledge Base (KB) is a set of representations of facts of the world. Each one is called a sentence, expressed in a knowledge representatoin language. TELL is giving knowledge, and ASK is querying knoweldge.\n\nInference mechanism determines what follows from what the KB has told the agent.\n\nKnowledge-based agents have three levels: 1) knoledge level (epistemological) is most abstract describing what an agent knows (i.e. automated taxi knows how to get between two cities.) 2) Logical level is where knowledge is encoded in sentences, e.g. Link(City1, City2). 3) Implementation level is level that runs on architecture\n\n## AIMA Chapter 7.2 The Wumpus World\nWumpus world of cave systems with pits and gold.\n\n## AIMA Chapter 7.3 Logic\nKnowledge representation is how we express knowledge in computer form. It has two aspects; 1) the syntax, 2) the semantics - an agent believes a corresponding sentence in its KB. e.g. x > y means nothing if the semantic of greater than does not exist. Correctly combined, the synatax and semantics make a logic.\n\nSince sentences are physical configurations of an agent, reasoning must construct new configurations from old ones. Proper reasoning is that facts actually follow from older facts. \n\nEntailment is the relationship between sentences in which new sentences are true given older sentences. KB entails alpha, or KB = alpha. An inference procedure that generates only entailed sentences is sound or truth preserving. Record of operation of a sound inference procedure is a proof. \n\nAn inference procedure is complete if it can prove any sentence that is entailed. Proof theory of the language specifies which reasoning stpes are sound. A sentence does not mean something by itself. Compositional - the meaning of a sentence is a function of the meaning of its parts.\n\nSound reasoning is logical inference or deduction, implementing the entailment relation between sentences. Necessarily true sentence: sentence is valid iff it is true under all interpretations in all possible worlds. Also called analytic \nsentences or tautologies for valid sentences.\n\nSentence is satisfiable iff there is an interpretation in some world in which it is true. Unsatisfiable includes self-contradictions.\n\nLogic consists of 1) a formal system for describing things that is composed of (a) the syntax of the language which describes how to make sentences, and (b) the semantics of the language on how sentences relate to states, and 2) the proof theory for deducing the entailment of a set of sentences.\n\nTwo kinds of logic: propositional or boolean, and first-order logic. Propositional logic is represented with symbols and boolean connectives. First order logic represents the world as objects and predicates on objects, as well as connectives and quantifiers. \n\nOntological commitments are concerned with nature of reality that do or do not hold. Temporal logic is time based. Epistemological commitments concern the states of knowledge an agent can have using types of logic. There can be range on the degree of belief of a truth. i.e. 50% sure this is right. Fuzzy logic is degrees of truth \n\nLanguage | Ontological Commitment (what exists in the world) | Epistemological Commitment (what an agent believes) Propositional Logic  | facts | true/false/unknown\nFirst-order logic | facts/objects/relation |  true/false/unknown\nTemporal Logic | facts/objects/relations/time |  true/false/unknown\nProbability theory | facts | degree of believe 0 to 1\nFuzzy logic | degree of truth | degree of believe 0 to 1\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Rules of propositional logic: 1) logical constants true and false are sentences by themselves, 2) propositional symbols P and Q are sentences, 3) wrapping parentheses forms a sentence. e.g. (P and Q), 4) sentence can be formed by combined simpler sentences.\n\nFive logical connectives: 1) And (A), 2) Or (V). In 'A V (P AND Q)' we have a disjunction of the disjuncts A and (P AND Q). 3) Implies (-->). In '(P AND Q) --> R', we have an implication where the premise (antecedent) is (P AND Q) and the conclusion or consequent is R. Implication is also called rules or if-then. 4) Equivalent (<-->) creates an equivalence or a biconditional. 5) Not. Negation is the only connective that operates on a single sentence.\n\nAtomic sentences consist of one symbol. Complex sentences contain connectives or parentheses. Literal is an atomic sentence or a negated atomic sentence.\n\nOrder of precedence is: negation, AND, OR, implies, equivalent.\n\nA sentence containing just a propositional symbol is satisfiable but not valid. \n\nImplication is different in that if P is true, then I am claiming Q is true. Otherwise, I am making no claim.  \n\nA world in which a sentence is true given an interpretation is called a model of that sentence given the interpretation. \n\nEntailment: a sentence a is entailed by a KB if the models of the KB are all models of a.\n\nInference rules are classes of inferences that can be generalized for similar patterns. Here are 7 such rules: 1) modus ponens or implication-elimination: from an implication and the premise of the implication, you can infer the conclusion. 2) and-elimination: from a conjunction, you can infer the conclusion. 3) and-introduction: from a list of sentences, you can infer their conjunction. 4) or-introduction: from a sentence, you can infer its disjunction with anything else at all. 5) double-negation elimination: from a doubly negated sentence, you can infer a positive sentence. 6) unit resolution: from a disjunction, if one of the disjuncts is false, then you can infer the other is true. 7) resolution: bc 0 cannot be both true and false, on of the other disjuncts must be true in  one of the premises. Equivalently, implication is transitive.\n \n Monotonicity: if you add sentences to a KB and everything is still entailed.  \n\n## AIMA 7.5 Propositional Theorem Proving\n \n\n## Module 7 Lecture Notes\n \n\nTwo kinds of sentences: 1) axioms, a sentence that is given, 2) derived sentences, which are infered from other sentences.\n\nsound - the inference algo only derives entailed sentences. complete - an inference algorithm is complete if it can derive all sentneces that are entailed.\n\n(a and b) = (b and a): commutativity of and\n(a or b) = (b or a): commutativity of or \n((a and b) and c) = (a and (b and c)): associativity of and \n((a or b) or c) = (a or (b or c)): associativity of or \nnot(not a) = a: double negation elimination \n(a implies b) = (not b implies not a): contraposition\n(a <==> b) = ((a implies b) and (b implies a)): biconditional elimination\nnot(a and b) = (not a or not b): de morgan\nnot(a or b) = (not a and not b): de morgan\n((a and b) or c) = ((a and b) or (a and c)): distributivity of and over or\n((a or b) and c) = ((a or b) and (a or c)): distibutivity of or over and \n\nMonotonicity implies soundness. resolution yields a complete inference algorithm.\n\nCNF: conjunctive normal form: every sentence of propositional logic is equivalent to a conjunction of clauses. Clauses are disjunctions of literals. Steps: 1) Eliminate <==> by replacing (A <==> B) with (a ==> B) and (B implies A). 2) Elminate ==> implies by replacing A ==> B with (not A or B).\n3) move not inwards by elminating double negations and apply de morgan's rules. \n4)Apply distibutivity laws to distibute or over and whenever possible. \n\nDefinite clause: disjunction of literals where exactly one is postive. Horn clause:\ndisjunction of literals wher eat most one is positive. This includes definite clauses, and clauses with no positive literals. \n\nForward chaining: is data driven reasoning to derive new conclusions. Backward chaining: works backwards from a query. If it is true, no work is needed. Otherwise, if all premises can be proven, then the quey is true. \n\nFollowing are in CNF (conjunctive normal form): (A), (A or B), (A or B) and (C), (A or not B or not C) and (not D or E or F). \n\nThe following are not in CNF: not (B or C), since or is nested within a not, (A and B) or C, A and (B or (D and E)), since an AND is nested within a OR.\n\nTo convert: 1) convert to negation normal form by replacing P --> Q with not P or Q, replace P <--> Q with (P or not Q) and (not P or Q). Move NOTs inward by replacing not(P or Q) with (not P) and (not Q). Replace  \n\n\n## Module 7 Definitions\n* **Concept** - definition\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": 10602
        },
        "id": "T3cm1WV542_a",
        "outputId": "89663644-5b49-4392-8b99-0c6e3a6ae590"
      },
      "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": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nAI was coined in 1956. Definitions of AI are organized into four categories: 1) Systems that think like humans, 2) Systems that think rationally, 3) Systems that act like humans, and 4) Systems that act rationally. Two are focused on thought process and reasonsing, measuring success in terms of human performance, while the other two are focused on behavior, measuring success against an ideal concept of intelligence called rationality. \n\nActing humanly: Alan Turing proposed his test in 1950 to perceive human-level performance in cognitive tasks. A human would interrogate a computer with a teletype, and the computer would pass if it fools the human. To Turing, physcial simulation of a person was irrelevant for computer intelligence. The computer would need to know NLP, knowledge representation to store information, automated reasoning to answer questions, and machine learning to adapt to new patterns. The total Turing test would include video signal to test perceptual abilities and grab an item through the hatch. This would require computer vision and robotics.\n\nThinking humanly: Cognitive science melds AI and psychology experiments to construct theories about the mind. Some want computer's to solve the problem correctly, while others want them to solve it how a human would through reasoning.\n\nThinking rationally: Aristotle's syllogisms constructed right thinking based on correct premises leading to correct conclusions, defining the field of logic and the logicist method of AI. Difficulty is stating informal knowledge in logical terms, and solving in principle vs practice. \n\nActing rationally: acting to achieve one's goals given one's beliefs. An agent is something that perceives andacts. AI is viewed as the construction of rational agents Correct inferences is not all of rationality bc there are situations where nothing is correct, or taking too long to decide is bad. AI as rational agents has two advantages over laws of thought bc correct inference is useful but not necessary, so it is a more general approach, and secondly, bc it is easier for scientific development.\n\nAchieving perfect rationality is not always possible in complicated environments. Limited rationality is acting rationally when there is not enough time to compute. \n\n## AIMA Chapter 27.1 The Limits of AI\nCan we build a complete, general-purpose intelligent agent? Decision making ranges from reflex responses to knowledge-informed deliberation. Explanation-based learning includes compilation processes to convert declarative information at the deliberative level into efficient representations that eventually become reflex, e.g. the SOAR and THEO architectures. When they solve a problem through deliberation, they'll save it for reflex later. \n\nReal-time AI deals with when agents need to control their deliberation time, e.g. a car is crashing. Alpha-beta pruning can elimiate irrelevant deliberations and depth.\n\nAnytime algorithms improve their output quality over time so it has an okay decision if interrupted, allowing it to decide if more computation is worthwhile. An example of this would be iterative deepening search. \n\nDecision-theoretic metareasoning applies information value to computations to balance the cost of delaying action vs the expected improved decision quality. \n\nFinally there is learning mechanisms in general intelligent agents, e.g. inductive, reinforcement learning. It's not currently possible to self-learn from scratch just by pointing the computer towards a dictionary (a large knowledge base).\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nIf we design a desirable property P, then we should be able to design a system that possesses property P. There are three choices for P: 1) Perfect rationality: a perfectly rational agent acts to maximize its expected utility given the environmental information. Perfectly rational agents do not exist outside of non-trivial environments. 2) Calculative rationality: how we design logical and decision-theoretic agents, which eventually return what would have been the rational choice for when it began deliberating. In principle, this would do the right thing, but if you apply the brakes long after you've crashed, it's irrational. 3) Bounded optimality (BO): a BO agent behaves rationally given its compuational resources. The expected utility is at least as high as the expected utility of any other agent on the same machine. We don't want the design of the computer however (e.g. how much memory), to impact how we deisng the BO system. Bounded optimality indicates optimal programs rather than actions.  \n\nAsymptotic bounded optimality (ABO): if we have a program B bouned optimally for a machine M in an environment E, with unbounded complexity, then program P' is ABO for M in E if it can outperform P by running on a machin ekM that is k times better (faster/larger). \n\nShifting from descirbing actions to programs is in other fields of rationality. \\ \nAct utilitarianism is the rationality of individual acts, but is shifting to rule utilitariansim, the rationality of general policies for how to act. \n\nGame theory and the prisoner's dilemma offer an example of simultaneous decisions. we can bound on space rather than time if we only do a few rounds.\n\n## AIMA 2.1 Agents and Environments\nAn agent is anything that percieves its environment with sensors and acts upon that environment with effectors. Humans have ears/eyes, but robots have cameras and other sensors, plus motors as effectors. Software agent has code as its percepts and actions. Agents should also know things. \n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n A rational agent does the right thing, meaning it will cause the agent to be the most successful. Performance measure is how we determine if an agent is successful. We could ask a Rumba to clean the whole floor, in an amount of time, quietly, and with minimal electricity. When we evaluate our performance measure is also important. Do we value speed or consistency? \n\nOmniscience is an agent that knows the actual outcome of its actions and acts accordingly. Rationality is expected success given what has been percieved.  This should take into account four things: 1) Performance measure that defines success, 2) Perceptual history (percept sequence) , 3) what the agent knows about their environment, and 4) actions that it can perform. \n\nAn ideal rational agent does whatever action is expected to maximize its performance measure for each possible percept sequence, using the evidence provided and the built-in knowledge it has. This requires you take actions to obtain useful information. \nClocks are simple agents, but degenerate in that their percept sequence is empty.\n\nA mapping is a list of percept sequences to actions. An ideal mapping describes ideal agents by specifying which action to take in response to any scenario. \n\nAutonomy: if an ideal rational agent only uses built in knowledge, then it lacks autonomy. If its behaviour is determined by its own experience, then it is autonomous. \n\n## AIMA 2.3 The Nature of Environments\n AI must design the agent program, a function that implements a mapping from percepts to actions. The computing device on which it runs is the architecture. Agent = architecture + program.\n\nArtificial environments might be what we do in homeowork (keyboard + console), but this is a real environment. Some software agents (e.g. bots) exist in complex domains. PAGE = percepts, actions, goals, environment. \n\nAlthough a mapping is from percept sequences to actions, the agent program receives one percept as an input and must construct the sequence in memory. \n\nA skeleton agent function takes in a percept and returns an action. A look-up agent has no autonomy and simply looks up its mapping, but would take too long to build and may not have enough memory for all actions.\n\nFour types of agent programs: 1) simple reflex agents, 2) agents that keep track of the world, 3) goal-based agents, and 4) utility based agents. \n\nSimple-reflex agents: have condition-action rule, e.g. brake for pedestrian. This uses interpret-input, rule-match, and rule-action functions. \n\nAgents that keep track of the world: maintain internal state, e.g. first picture shows car in front without brake lights, and then next shows it with them. Or if a car is overtaking it based on where it was before. UPDATE-STATE function.\n\nGoal based agents: search and planning are example programs to get taxi to destination. This involves looking into the future, what will happen if I do this next step. What happens if it starts raining. \n\nUtility based agents: goals are not enough because you can get to a destination faster or cheaper. Performance measure should take into account other states to define higher utility for the agent. Utility is a function mapping a state onto a number, e.g. a degree of happiness. Utility function allows for when their on conflicting goals (e.g. speed and safety). Utility functions can be translated to goals so that you can have a goal based and utility based agent making the same decisions. \n\n\n## AIMA 2.4 The Structure of Agents\nEnvironments: actions are done by the agent to an environment, which provides percepts back. Environments have several properties: 1) accessible vs. inaccessible, if the agent can detect all percepts relevant to the choice of an action. 2) Determinisitc vs. nondeterministic, if the next state is determined by the current state, from the point of view of the agent. 3) Episodic vs. non-episodic, if the decision is not impacted by the next \"round\". 4) Static vs. dynamic, if the environment does not change during deliberation. Semi-dynamic is if the performance score changes during time, but the environment does not. 5) Discrete vs. continouse, chess vs. taxi driving, if there are distinct, clearly defined percepts.\n\nHardest environment is inaccessible, nonepisodic, dynamic, and continous. \n\nEnvironment programs are RUN-ENVIRONMENT and RUN-EVAL-ENVIRONMENT. Agents are designed to work in an environment class, a whole set of different environments, e.g. chess against a variety \\ \nof opponents.\n\nAgent programs maps from a percept to an action, updating an internal state. \nReflex agents respond immediately to percepts, but goal-based agents act to achieve goals and utility based agents try to maximize happiness defined by utility. \n\n## Module 1 Lecture Notes\n \nStrong AI vs weak AI: actually thinking versus merely simulating thinking.\\ \nAgent is anything that percieves its environment through sensors and can act on its environment with actuators. Percept is the agent's inputs at any given time. Agent is specified by an agent function f that maps a sequence of percepts to an action. Agent is composed of agent program and architecture.\n\nConsequentialism: evaluating an agent's behaviour based on its consequences.We should think about performance measures as what we want the agent to achieve rather than how we think it should behave. Ideal agent maximizes actual performance, but would need omniscience. \n\nRevised definition: rational agent maximizes the expected value of its performance measure.\n\nPEAS: task environment specifications: 1) performance measure; 2) environment 3) actuators, 4) sensors. Reflex agent selects an action based on current percept and ignores rest of percept history. Problem solving agent plans ahead and considers sequence from path to goal using search.\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\nPython invented by Guido van Rossum in 1989, the Benevolent Dictator for Life. PEP8 is the python style guide. REPL is read, evaluate, print, loop. Whitespace is meaningful in Python. \nJava is static typing in that variables can only refer to objects of the declared type, and methods use type signatures to force types. Python, however, is dynamically typed (meaning the type of a variable can change), and functions have not type signatures. Drawback is that type errors are caught at runtime.\n\nThree sequences are 1) strings, 2) lists, 3) tuples.\n\nStrings can have single or double quotes. Triple quotes for multi-line strings and docstrings. Strings are immmutable, but can be concatenated with +. Strings are unicode and use 2-byte characters\n\n== checks if variables point to objects of the same value, while 'is' checks if they are the same object. Lists are mutable. Use 'y=x[:]' to get a shallow copy of something.\n\nTuples are immutable, but can be of mixed type. \n\nSlicing returns copy of a subsequence. Nevative lookup from right is myList[-3].t[1:-1] uses negative index. t[1:-1:2] selectes every nth item. t[:2] copies from beginning of sequence. t[2:] copies to end of sequence.\n\nLists have append, insert, index, count, remove, reverse, and sort methods. \n\nStrings have split, join, capitalize, upper, lower, strip methods.\n\nDictionaries are undordered and work by hashing, with immutable keys. There is constant average time to add, lookup, and update. d = {'user: 'ben', 'pass: 123} Dictionary has keys, values, items methods. \n\nPython functions can return multiple values, but have no function overloading. You can provide default values for arguments. Non-default arguments must proceed default arguments. The *args argument accepts a variable number of non-keyword arguments to the function. The **kwargs argument accepts a variable number of keyword arguments. \n\nPython uses dynamic scope. Memoization is using prior arguments to the funciton e.g. used in recursion. Functions are first-class objects which can be dynamically passed to other functions or returned as a value. So you could pass a function to a higher order one, or store a function in a data structure. \n\nClasses have __init__ methods. All class methods begin with self. Subclasses extend the definition of another class. Define it by putting name of superclass in parentheses after classs name. class AI_Student(Student). Def __init(self, name, dept): Student.__init__(self, name, dept). Only time to pass self as argument is calling method of an ancestor. \n\nMagic method of classes are __init__, __len__, __copy__, __cmp__, _add__, __neg__ to override Python defaults.  \n\nPython main method:: if __name__ == '__main__': do stuff\n\nDuck typing establishes suitability of an object by determining presence of methods.\n\nList comprehension: li = [3, 6, 2, 7]. [elem * 2 for elem in li] = [6, 12, 4, 14]. li = [('a', `, ('b', 2), ('c', 7))], [n * 3 for (x, n) in li] = [3, 6, 21]\n\nGenerators are iterators created using 'yield'. After a yield statement, the function will return the value and then resume where it left off. __next__() is the how you access the returned value. while True: try print(g.__next__()), except StopIteration: break. \n\nImports: from math import sqrt, from math import *, import numpy as np (alias). pip is package installer for python.\n\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 One kind of goal-based agent is the problem-solving agent, which finds a sequence of actions to lead to a desirable state. Goal formulation is the first step in problem solving. Multiple factors can affect the desirability of differing ways of achieving the goal. Problem formulation is the process of deciding what actions and states to consider after goal formulation. The process of looking for a sequence that leads to goal state is called search. This algorithm takes a problem and returns a solution in the form of an action sequence. Execution phase is where it carries out the action. \n\n## AIMA Chapter 3.2 Example Problems\n Formulating problems:  a single-state problem is when you find the solution on the first state-change. When the world is not fully accessible, the agent reasons about the set of states to get to, making it a multiple-state problem.\\ \nAgent must calculate a tree of actions, where each branch deals with possible contingencies making this a contingency problem. I.e. you go to clean up dirt, but there is not dirt. \n\nInterleaving of search and execution to achieve goal. Exploration problems are when the agent has no information about it surroundings, and must experiment to solve its goal.\n\nA problem is a collection of information used by the agent to decide what do do. These are the components of a problem definition: 1) initial state of agent, 2) set of possible actions. Operator enotes the action in terms of which state will be reached by carrying out an action in a state. Also called successor function S, where S(x) returns states reachable from x an action. \n\nThe state space of a problem is the set of states reachable from the initial state in a sequence of actions. A path in the state space is a sequence. The goal test is applied to a single state, letting the agent know if it has reached its goal. A path cost function is a function that assigns a cost to a path. Path cost function denoted by g.\n\ninitial state, operator set, goal test, and path cost function define a problem. Output of a search algo is a solution, the path from initial state to goal state.  \n\nA path connects sets of states and a solution is a path that leads to a set of states, all of which are goal states. The state space is then replaced by state set space. \n\nPerformance: does a solution exist, is it a low path cost solution, and third, what is the search cost (time and memory). Total cost is sum of path cost and search cost. Offline cost is search cost and online cost is path cost.\n\nProcess of removing detail from a representation is called abstraction. \n\nNP completeness is nondeterministic polynomial time. Concret way to solve.TSP = travelling salesperson problem. NP-hard = at least as hard as the hardest problem in NP. VLSI chips have cell layout and channel routing problems to minimize area and connection lengths to maximize speed.\n\nGenerate action sequences by applying operators to the current state and expanding the state. We conitinue choosing and expanding until the solution is found, or there are no more states to expand. Choosing which state to expand first is up to  the search strategy. Search tree is the state space, with the root being the initial state. Difference between state space and search tree is that there are finite states, but potentially infinite nodes in search tree if you get caught in a loop.\n\nFringe or frontier is the collection of nodes waiting to be expanded. This is implemented as a queue.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n \nEvaluating search strategies: 1) completeness - is the strategy guaranteed to find a solution if exists, 2) time complexity - how long does it take, 3) space complexity - how much memory does it need, 4) optimality - does it find the highest quality solution if multiple exist?\n\nUninformed search strategies: no information about the number of steps or the path cost from current to goal. They just distinguish goal and non-goal. Also called blind search. This is in contrast to informed search, or heuristic search.\n\nBreadth first search: first expand root, then its immediate children, and then their successors. Nodes at depth d are expanded before nodes at depth d + 1. We \\ \ncan implement BFS using general-search by adding newly generated states to the end of the queue, after all previously generated states.  If solution exists, BFS will find it, and it will always find the shallowest solution. Therefore BFS is complete. BFS uses FIFO (first in first out) queue. Put successors at the end of the frontier successor list.\n\nBranching factor b: when every state expands to b new states. If solution is at depth d, then # of nodes expanded is 1 + b + b^2 +...+ b^d at a maximum, depending on where solution is found at depth d. This is a exponential complexity bound of O(b^d), with time and space complexity being the same, since all nodes must be maintained in memory. Memory is a bigger issue than time for BFS. Exponential complexity search problems can only be solved for small depths.\n\nUniform cost search (UCS): BFS finds the shallowest goal state, but that might not be the least cost.  UCS modifies BFS by expanding the lowest-cost node in the frontier, as measured by path cost g(n), rather than the lowest-depth node. BFS is just UCS where g(n) = DEPTH(n). UFS will find the cheapest solution provided that the cost of a path must never decrease as we go, i.e. g(SUCCESSOR(n)) > g(n). \n\n\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nRepeated States: unavoidable when operators are reversible. Possible solutions include (in order of increasing effectiveness): 1) Do not return to the state you just came room by not expanding a successor that is the parent. 2) Do not create paths with cycles, 3) Do not generate a state that was generated before. This mean all states have ot be kept in memory, with a potential space complexity of O(b^d), or O(s) where S is the number of sates in the space state.\n\nIn practice, we use hash tables to store generated nodes and avoid duplication. If the state space is 'loopier', then it will pay off to store and check states.\n\n## Module 3 Lecture Notes\n \nProblem is defined by 1) states, 2) initial state, 3) actions, 4) transition model, 5) path cost, 6) goal test. Optimal solution is one in which no other solution has a lower path cost.\n\nDepth first search (DFS) expands the deepest level node. Once it hits a non-goal node with no expansion, it goes and expands shallower nodes. We implement DFS with queuing function that puts new states at the front of the queue, since its successors will be even deeper. DFS has low memory requirements since we only store the path from the root to the leaf node, and the remaining unexpanded siblings. For a branching factor b and depth m, DFS will have bm nodes to store. Time complexity is O(b^m). DFS is not complete or optimal, because it can get stuck in a loop or find a longer solution than is optimal. Avoid DFS for deep trees.  DFS is LIFO (last in first out) queue: put succesors at the front of the frontier successor list.\n\nDepth limited search: imposes a maximum depth on a path, e.g. if we have ten cities, then path cannot be greater than 9, the diameter of the state space. This is guaranteed to find a solution if exists,but still not guaranteed to be optimal. If cutoff is too small, depth limited search may not be complete. Given depth limit l, time is O(b^l) and space is O(bl).\n\nIterative deepening search: combines benefits of DFS and BFS by starting at depth 0 and then increasing. It is optimal and complete, but has good memory like DFS. Order of expansion is similar to BFS, but states are expanded multiple times at each iteration. At the bottom level, nodes are expanded once, and a level above they are expanded twice. Root is epxanded d + 1 times. Total # of expansions is (d + l)l + (d)b + (d - l)b^2 + ... + 3b^(d-2) + 2b^(d-1) + lb^d. Time complexity is still O*b^d) and space complexity is still O(bd). It is the preferred search method when there is large search space and depth of the solution is not known.\n\nBidirectional search: search both forward from initial and backward from goal, and stop when you meet in the middle. If solution is at depth d, then solution will be found in O(b^(d/2)) steps. Space complexity of uninformed bidirectional search is also O(b^(d/2))\n\nTime: BFS = b^d, UCS = b^d, DFS = b^m, Depth-limited = b^l, Iter. Deepening = b^d, Bidirect = b^(d/2) \nSpace: BFS = b^d, UCS = b^d, DFS = bm, Depth-limited = bl, Iter. Deepening = bd, Bidirect = b^(d/2) \nOptimal: BFS = yes, UCS = yes, DFS = no, Depth-limited = no, Iter. Deepening = yes, Bidirect = yes\nComplete: BFS = yes, UCS = yes, DFS = no, Depth-limited = yes if l > d, Iter. Deepening = yes, Bidirect = yes \n\nGraph search: we use an explored list to keep track of nodes so that they are not visited again.\n\nTree search: we don't keep a list, and nodes can be visited multiple times. The tree can contain the same node multiple times.\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nInformed search strategies use problem specific knowledge to find more efficient solutions than uninformed search.\n\nBest-first search a graph-search algo that selects nodes based on an evaluation function: f(n). Eval function is a cost estimate, so we select the lowest node to expand first. Implementation of best-first search is identical to uniform-cost search with the exception of using f instead of g to order the priority queue. These algos include a component of f called a heuristic function h(n). h(n) = est. cost of the chepaest path from node n to goal state. If n is the goal node, then h(n) = 0. \n\nGreedy best first search: expands the node that is closest to the goal thinking that it will quickly solve it. It purely uses the heuristic function: f(n) = h(n). Greedy best first search is not optimal and not complete, much like DFS. It can get stuck in infinite loops. Graph search version is complete in finite spaces, but not in infinite ones. For the tree search, if m is the maximum depth of the search space, the worst case time and space complexity is O(b^m).\n\nA* search: minimizes the total estimated solution cost and is the best known implementation of best first search. It combines the path cost g(n) and the cost to get to the goal h(n). f(n) = h(n) + g(n). This is essentially the estimated cost of the cheapest solution to the goal through n.\nA* space complexity is effectively O(b^d)\n\nThe first thing we would try is to expand the node with the lowest f(n). A* is both complete and optimal and identical to uniform cost search with the exception that A* uses g + h rather than just g. \n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\nBranching factor: one way to characterize the quality of a heuristic is the effective branching factor b*. If nodes generated by A* is N and the solution depth is d, then b* is the branching factor that a uniform tree of depth d would have in order to contain N+1 nodes. A good heuristic would have a value of b* close to 1. \n\nDomination: if for any node h2(n) >= h1(n), we say that h2 dominates h1. Domination directly translates to efficiency. Every node with f(n) < C* will be expanded. Generally better to use a heuristic function with higher values, provided it is consistent.\n\nA problem with fewer restrictions on the actions is called a relaxed problem. It will however add eges to the state space, and any optimal solution in the original problem will be a solution in the relaxed problem, but the relaxed solution might be better since there are new edges. Consequently, the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. It is also consistent.\n\n## Module 4 Lecture Notes\n\nUCS is a tree search algorithm using a weighted tree. Extends BFS by expanding node with lowest path cost. Implements priority queue ordered by g(n). UCS test if node is goal state when it is selected for expansion, not when it is added to the frontier. \n\nFor optimality, we require that h(n) is an admissible heuristic, one that never overestimates the cost to reach the goal. Since g(n) is the actual cost to reach n, and f(n) = g(n) + h(n), we must have that f(n) never overestimates the true cost of a solution through n. Admissible heuristics are optimistic bc they think the cost to solve is less than reality. Straight line distance is admissible, bc the actual distance can never be less. \n\nA 2nd stronger condition is consistency (or monotonicity) which is required for graph search implementations of A*. A heuristic is consistent iff for every node the estimated cost of reaching the goal is no greater than the step cost of getting to its child, plus the estimate of getting from the child to the goal. This is like the triangle inequality in that each side of the triangle cannot be greater than the sum of the other two sides. Every consistent heuristic is also admissible.\n\nTree-search version of A* is optimial if h(n) is admissible, while graph search is optimal if heuristic is consistent. Since A* stores all nodes in memory, it will run out of memory before time usually.\n\nIDA* (iterative deepening A*): main difference between standard iterative deepening and IDA* is that the cutoff is the f-cost rather than the depth. This avoids the overhead of storing all nodes.\n\nRecursive Best First Search (RCBFS): mimics best-first search in linear space. It's similar to recursive depth first search, but rather than going down in depth, it uses the f_limit variable to keep track of the f-value of the best alternative path from any ancestor to the current node. If the recursion exceeds the limit we wind back to the alternative path. RBFS will replace the f-value of each node with a backed-up value, the best f-value of its children. This means RBFS will remember the best f-value of the leaf in the subtree and can decide to expand later.\n\nRBFS is a little more efficient than IDA*, but suffers from node re-exploration. It is optimal if the heuristic is admissible. \n\nIDA* and RBFS suffer from using too little memory. They forget most of what they have done.\n\nTo use all available memory, we would use MA* (memory bounded A*) and simplified memory bounded A* (SMA*). SMA will expand best leaf until memory is full, after which it starts dropping the worst leaf from memory. If those are the same, SMA will expand the newest best leaf and delete the oldest worst leaf.\n\nSMA is complete if there are reachable solutions given the memory constraints. \n \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Adversarial search is games. Chess is a perferct information game.Zero sum game is one in which the payoff to each player is the same for each iteration of the game. i.e. chess.\nOpponents introduce uncertainty. Game-playing programs must deal with the contingency problem. Pruning allows us to ignore the parts of the search tree that have no impact. Heuristic evaluation functions let us approximate the true utility of a state without completely searching. \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n MAX and MIN: max moves first. We can define a game as a search problem with these components: 1) Initial state of the board and whose move it is. 2) Set of operators defining legal moves, 3) Terminal test for when the game is over. 4) Utility function (payoff function) which gives a numerical outcome to the game. i.e. win/lose = 1/0.\n\nMAX must find a strategy that leads to win including the correct move for MAX for every possible move by MIN. Two ply is a half move.\n\nMinimax algorithm has five steps: 1) generate whole game tree down to terminal states, 2) apply utility function to get each state's value, 3) use utility to determine value of nodes one level higher in the search tree, up until the root, 4) MAX chooses the move that leads to the highest value. This is the mininiax decision, using the assumption that the opponent will play perfectly to minimize MAX's score.\n\nIf the max depth of tree is m and there are b legal moves, the time complexity of minimax is O(b^m). Algo is a DFS implemented using recursion rather than queue. Space req is linear in m and b.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Evaluation function: gives us an estimate of the expected utility of a game from a position. Material value of pawn is 1, knight is 3, etc. A minimax algo will be able to determine te exact value of the position based on the terminal state, but that takes too long. Evaluation function must balance accuracy of evaluation versus the time cost.\n\nMaterial advantage evaluation function would count the values of board pieces as a weighted linear function, where w is weights and f is features of a position. W would be the value of the pieces (i.e. 1 for pawn), and f would be the number of those pieces on the board.\n\nCutting off search: at depth d so that the computer has the alloted time to make a move. We could also do iterative deepening and select the move of the deepest completed search when time runs out. \n\nQuiescent: positions appropriate for the evaluation function that are unlikely to exhibit big changes in value in the near future. This extra search is a quiescence search.\n \nHorizon problem is when opponent is about to cause unavoidable damage. i.e. Stalling moves to prevent a pawn from becoming a queen, pushing the queening move over the horizon to where it is not detected. This is yet unsolved for general approaches. \n\nPosition evalution function must be a positive linear transformation of the liklihood of winning from a position. Expectiminimax must consider all possible dice rolls, giving us O(b^m x n^m) complexity, where n is the number of distinct rolls.\n\nAlpha-beta pruning: reutrns the same move as minimax, but prunes branches that couldn't influence the final decision. Alpha is the value of the best choice we have found at any point along the path for MAX. Beta is the best choice we have for MIN. Alpha-beta needs to examine only O(b^(m/2)) nodes to pick the best move, while minimax needs O(b^m).\n\nTranspositions: different permutations of move sequences leading to the same position. Hash table of previously seen positions is a transposition table.\n\n## AIMA Chapter 5.5 Stochastic Games\n \nStochastic games are games of chance.\n\nGames of chance: must include chance nodes in addition to MAX and MIN nodes. We calculate an expected value, where the average is taken over all the possible dice rolls, for instance. Expectimax value is used to assign value to chance nodes, after which we compute the expectimin value.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Decision networks are also known as influence diagrams, extending belief networks by incorporating actions and utilities. \n\nAgents preferences b/n world states are defined by a utility function. U(S) is the utility of state S. Nondeterminisitc action A will have possible states Resulti(A), where i ranges over the outcomes. Agent assigns probability to each outcome: P(Resulti(A)|Do(A),E), where E summarizes the evidence of the world available to the agent. Do(A) is the proposition that action A is executed. Then \\ \nthe expected utility of action given evidence EU(A|E) is the sum of P(Resulti(A)|Do(A),E) U(Resulti(A)).\n\nMaximum expected utility (MEU) says a rational agent chooses the action that maximizes expected utility. If an agent maximizes a utility function reflecting the performance measure by which it is judged, then it will achieve the highest score if we average over possible environments in which to place the agent.\n\nThis chapter looks at one-shot decisions rather than sequential decisions. \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n In utility theory, scenarios are lotteries to emphasize that outcomes are like prizes and depende on chance. Lottery L with states A, B and probability p for A is L = [p, A; 1 - p, B]. A one outcome lottery would beL = [1, A]. A > B means A is preferred to B. A ~ is indifferent to A and B. A bigger underscore ~ B is agent prefers A to B or is indifferent. \n\nPreferences should be transitive, i.e. A > B, B > C implies A > C.\n\nSix constraints of utility theory.  1) Orderability, a rational agent must prefer either A or B, or rate them equally. (A > B) V (B > A) V (A ~ B). 2) Transitivity: (A > B) AND (B > C) --> (A > C). 3) Continuity: if state B is between A and C in preference, then there is a probability p for which the agent will be indifferent b/n getting B for certain and the lottery that yields A with probability p and C with probability 1 - p. A > B ? C --> there exists  p [p,A; 1-p, C] ~  B. 4) Substitutability: if an agent is indifferent, then the agent is indifferent b/n more complex lotteries where it gets B vs. A. 5) Monotonicity: if there are two lotteries that have the same outcomes, and an agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A. 6) Decomposability: compound lotteries can be reduced to simpler ones using the laws of probability. No fun in gambling rule. \n\nPreference is the basic property of rational agents. Utility principle: if an agent's preferences obey the axioms of utility, then there is a real function U that operates on states s.t. U(A) ? U(B) iff A > B and U(A) - U(B) iff agent is indifferent between A and B. U(A) > U(B) <--> A > B, U(A) = U(B) <--> A ~ B.\n\nMaximum expected utility principle: the utility of a lottery is the sum of the probs of each outcome times the utility of that outcome.\n\n## AIMA Chapter 16.3 Utility Functions\n Utility func maps states to numbers. \n\nUtility of money: agent exhibits monotonic preference for money. Money is a value function or oridinal utility measure, meaning we just prefer to have more than less when thinking about definite amounts.\n\nRisk averse: preferring a sure payoff less than expected value of gamble. Risk-seeking. The value an agent will take before a lottery is the certainty equivalent. Difference between the expected value and the certainty equivalent is the insurance premium. Kinda like car insurance. Risk-neutral is linear curve.\n\nNormalized utilities have a 0 to 1 scale of best possible prize and worst case.\n\nDecision theory is normative theory describing how a rational agent should act. Opposite is descriptive theory of actual human decisions.\n\n## Module 5 Lecture Notes\n\nSimplest game environment is multi-agent, static, discret, fully obverable, and strategic.\n\nFor minimax, even levels are MAX turns, and odd levels are MIN turns.\\ \nEvaluation function f assigns number scores to board states without reference to the path. Backed up value of each node is determined by the value of its children. For MAX node, value is th emax of its children. For MIN node, value is the min of its children. \n\nAlpha-beta pruning keeps track of two additional values: alpha, MAX's current upper bound. and beta, MIN's current upper bound. Max will never allow for a move that could lead to a worse score than alpha. Min will never allow for a move that could lead to a better score than beta. \n\nExpectimax search computes the average score under the optimal play by including max nodes as in minimax and chance nodes are like min nodes but the outcome is uncertain. We calculate their expected utilities by taking weighted average of children. This could be built into Markov Decision process.\n\n\n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Using a factored representation for each state, a set of variables each of which has a value. Problem is solved when each variable has a value that satisfies all the constraints on the variable. This is a constraint satisfaction problem (CSP). CSP uses general-purpose rather than problem-specific heuristics. Idea is to eliminate large portions of the search space by identifying variable that violate the constraints.\n\nCSP problems consists of three components: X, D, and C, where X is a set of variables, D is a set of domains, one for each variable, and C is a set of constraints that specify valid values. Each state in a CSP is defined by an assignemtn of values to some or all of the variables. A consistent or legal assignment does not violate any constraints. A complete assignment is where all variables have been assigned and a solution to a CSP is a consistent, complete assignment. A partial assignment is one where they're not all assigned. \n\nCSP solvers can be faster than state-space searchers bc CSP can eliminate large swathes of the search space. Precedence constraints can represent timing of tasks for instance. We could say that we have a disjunctive constraint if employees have to share the same tool for two different tasks for instance.\n\nSimple CSP involves discrete, finite domains. Some discrete domains can be infinite (ie. list all numbers), so we can't list all the allowed combinations. Here we use a constraint language (i.e. linear constraints). No algo exists to solve nonlinear constraints on integer variables.\n\nUnary constraints restrict variable to one valuei, i.e. Melbourne can't be green. Binary constraints relate two variables,i.e. Canberra cannot be same color as Queensland. Global constraint involves arbitrary number of variables (not ~all~ variables.) Common one would be all different colors or variables constraint. They can be represented in a constraint hypergraph with nodes as circles and constraints as squares. Real world also includes preferene constraints where solutions are not invalid, but preferred. This turns the problem into a constraint optimization problem.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Constraint propogation. In state-space search, the algo can only search, but in CSP, we can choose and search or do inference called constraint propogation. This is reducing the number of legal values for a variable.\n\nLocal consistency: if we treat a variable as a node and constriants as arcs, we enforce local consistency. There are different kinds of local consistency listed below. 1) Node consistency: if all values in the variable's domain satisfy the variable's unary constraints. 2) Arc consistency: if every value in the domain satsifies the variable's binary constraints. This wouldn't solve the Australia map coloring scenario since there would be no change in the values.\n\nAC-3 is the most popular arc-consistent algo. It maintains a queue of arcs to consider (really a set since order does not matter). If it pops an arc and reduces the domain to be consistent, and nothing happens, we just continue to the next arc. Otherwise it adds all the neighboring arcs to the queue. If something is revised down to nothing, then we know the algo has failed and there is no solution. Worst case time consistency is O(cd^3), where d is the number of times an arc is inserted into the queue (since it has at most d values to delete).\n\nArc consistency tightens down the domains (unary constraints) using arcs (binary constraints). To solve the Australia coloring though when each has two options, we need path consistency. Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. i.e. make Queensland and Canberra path consistent relative to Melbourne. PC-2 is the path consistency algo.\n\nK-consistency: a CSP is k-consistent, if for any set of k - 1 variables and for consistent assignments, a consistent value can always be assigned to any kth variable. 1-consistency is node consistency, 2-consistency is arc consistency. 3-consistency is path consistency. CSP is strongly k-consistent, \nif for any k it is also consistent down to k-1 all the way to 1-consistent. i.e. 1,2,3,4 consistent.\n\nIn addition to Alldiff, there is the resource-constraint called atmost constraint. Bounds propogation is used when we can't list all the options, so just have bounds. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Some CSPs can be solved just by inference, but sometimes we do have to search for a solution along partial assignments. CSPs have commutativity - a problem is commutative if the order of application of any given action has no effect on the outcome, i.e. we'll reach the same partial assignment regardless of the order we filled it in. Therefore we only to consider a ginle variable at each node in the search tree. This gives us a number of leaves of d^n. \n\nBacktracking search: is a DFS that chooses values for one variable at a time and backtracks when it has no legal values. We can solve CSPs without domain specific knowledge, i.e. heuristics(informed search). We start by choosing the value with the fewest legal moves left. This is minimum remaining values (MRV) heuristic, or the most constrained value, or fail first. For instance, if we pick one with 0 remaining values, we'll return failure immediately.\n\nFor Australia, where each had 3 remaining options, we use degree heuristic. Select the variable that is involved with the largest number of constraints. Once we've selected something, it's useful to explore in the least constraining value heuristic because we rule out the fewest choices for neighbors. \n\nInterleaving search and inference: AC-3 runs before we begin searching, and after which we can re-run it. Alternatively, forward checking occurs after we assign X a variable, we forward check to establish arc consistency for it. There is no need to do forward checking if we pre-process with AC-3 arc consistency. Forward checking also doesn't make all variables arc-consistent, just the current one. This is solved with MAC (Maintaining Arc Consistency) which calls AC-3 but instead of a queue of all arcs, we only do unassigned neighbors. MAC is more powerful than forward checking.\n\nBacktracking search uses chronological backtracking because the most recent decision point is revisited after something fails. A better approach would be to go to the node that caused the conflict, by keeping track of a conflict set. This backjumping method backtracks to the most recent assignment in the conflict set.  We could populate the conflict set with forward checking by adding what was deleted. Every branch pruned by backjumping is also pruned by forward checking, so single backjumping is redundant to forward checking. One implementation is conflict-directed backjumping. Constraint learning is the idea of finding a min set of variables from the conflict set that cause problems. This new set of variables is the no-good.\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search: when we choose a new value for a variable, it makes sense to select the value that results in the min number of conflicts. This is the min-conflicts heuristic. \n\n## AIMA Chapter 6.5 The Structure of Problems\n  In the Australia coloring problem, Tasmania is an independent subproblem since it's not a connected component. To solve a tree-structured CSP, pick any variable to be the root and choose an ordering of the variables appears after its parent in the tree. This is called a topological sort. Any tree-structured CSP can be solved in time linear to the number of variables. Directed arc consistency (DAC) is an ordering of variables. \n\nCutset conditioning can reduce a general CSP to a tree-structured one and is efficient if a small cutset is found. Tree decomposition transform the CSP into a tree of sub-problems and are efficient if the tree width of the constraint graph is small.\n\n## Module 6 Lecture Notes\n \n\nCSPs can vary by discrete variables (finite domains and infinite domains), and continous variables (e.g. start end times for hubble observations)\n\n \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nWe make a knowledge based agent by TELLing it what it needs to know. Declarative approach to system building is adding sentences that represent the designer's knowledge of the environment, i.e. background knowledge. We can also design learning mechanisms that output knowledge about the environment given a series of percepts. Adding a learning mechanism to a knowledge-based agent can make it autonomous.\n\nKnowledge Base (KB) is a set of representations of facts of the world. Each one is called a sentence, expressed in a knowledge representatoin language. TELL is giving knowledge, and ASK is querying knoweldge.\n\nInference mechanism determines what follows from what the KB has told the agent.\n\nKnowledge-based agents have three levels: 1) knoledge level (epistemological) is most abstract describing what an agent knows (i.e. automated taxi knows how to get between two cities.) 2) Logical level is where knowledge is encoded in sentences, e.g. Link(City1, City2). 3) Implementation level is level that runs on architecture\n\n## AIMA Chapter 7.2 The Wumpus World\nWumpus world of cave systems with pits and gold.\n\n## AIMA Chapter 7.3 Logic\nKnowledge representation is how we express knowledge in computer form. It has two aspects; 1) the syntax, 2) the semantics - an agent believes a corresponding sentence in its KB. e.g. x > y means nothing if the semantic of greater than does not exist. Correctly combined, the synatax and semantics make a logic.\n\nSince sentences are physical configurations of an agent, reasoning must construct new configurations from old ones. Proper reasoning is that facts actually follow from older facts. \n\nEntailment is the relationship between sentences in which new sentences are true given older sentences. KB entails alpha, or KB = alpha. An inference procedure that generates only entailed sentences is sound or truth preserving. Record of operation of a sound inference procedure is a proof. \n\nAn inference procedure is complete if it can prove any sentence that is entailed. Proof theory of the language specifies which reasoning stpes are sound. A sentence does not mean something by itself. Compositional - the meaning of a sentence is a function of the meaning of its parts.\n\nSound reasoning is logical inference or deduction, implementing the entailment relation between sentences. Necessarily true sentence: sentence is valid iff it is true under all interpretations in all possible worlds. Also called analytic \nsentences or tautologies for valid sentences.\n\nSentence is satisfiable iff there is an interpretation in some world in which it is true. Unsatisfiable includes self-contradictions.\n\nLogic consists of 1) a formal system for describing things that is composed of (a) the syntax of the language which describes how to make sentences, and (b) the semantics of the language on how sentences relate to states, and 2) the proof theory for deducing the entailment of a set of sentences.\n\nTwo kinds of logic: propositional or boolean, and first-order logic. Propositional logic is represented with symbols and boolean connectives. First order logic represents the world as objects and predicates on objects, as well as connectives and quantifiers. \n\nOntological commitments are concerned with nature of reality that do or do not hold. Temporal logic is time based. Epistemological commitments concern the states of knowledge an agent can have using types of logic. There can be range on the degree of belief of a truth. i.e. 50% sure this is right. Fuzzy logic is degrees of truth \n\nLanguage | Ontological Commitment (what exists in the world) | Epistemological Commitment (what an agent believes) Propositional Logic  | facts | true/false/unknown\nFirst-order logic | facts/objects/relation |  true/false/unknown\nTemporal Logic | facts/objects/relations/time |  true/false/unknown\nProbability theory | facts | degree of believe 0 to 1\nFuzzy logic | degree of truth | degree of believe 0 to 1\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Rules of propositional logic: 1) logical constants true and false are sentences by themselves, 2) propositional symbols P and Q are sentences, 3) wrapping parentheses forms a sentence. e.g. (P and Q), 4) sentence can be formed by combined simpler sentences.\n\nFive logical connectives: 1) And (A), 2) Or (V). In 'A V (P AND Q)' we have a disjunction of the disjuncts A and (P AND Q). 3) Implies (-->). In '(P AND Q) --> R', we have an implication where the premise (antecedent) is (P AND Q) and the conclusion or consequent is R. Implication is also called rules or if-then. 4) Equivalent (<-->) creates an equivalence or a biconditional. 5) Not. Negation is the only connective that operates on a single sentence.\n\nAtomic sentences consist of one symbol. Complex sentences contain connectives or parentheses. Literal is an atomic sentence or a negated atomic sentence.\n\nOrder of precedence is: negation, AND, OR, implies, equivalent.\n\nA sentence containing just a propositional symbol is satisfiable but not valid. \n\nImplication is different in that if P is true, then I am claiming Q is true. Otherwise, I am making no claim.  \n\nA world in which a sentence is true given an interpretation is called a model of that sentence given the interpretation. \n\nEntailment: a sentence a is entailed by a KB if the models of the KB are all models of a.\n\nInference rules are classes of inferences that can be generalized for similar patterns. Here are 7 such rules: 1) modus ponens or implication-elimination: from an implication and the premise of the implication, you can infer the conclusion. 2) and-elimination: from a conjunction, you can infer the conclusion. 3) and-introduction: from a list of sentences, you can infer their conjunction. 4) or-introduction: from a sentence, you can infer its disjunction with anything else at all. 5) double-negation elimination: from a doubly negated sentence, you can infer a positive sentence. 6) unit resolution: from a disjunction, if one of the disjuncts is false, then you can infer the other is true. 7) resolution: bc 0 cannot be both true and false, on of the other disjuncts must be true in  one of the premises. Equivalently, implication is transitive.\n \n Monotonicity: if you add sentences to a KB and everything is still entailed.  \n\n## AIMA 7.5 Propositional Theorem Proving\n \n\n## Module 7 Lecture Notes\n \n\nTwo kinds of sentences: 1) axioms, a sentence that is given, 2) derived sentences, which are infered from other sentences.\n\nsound - the inference algo only derives entailed sentences. complete - an inference algorithm is complete if it can derive all sentneces that are entailed.\n\n(a and b) = (b and a): commutativity of and\n(a or b) = (b or a): commutativity of or \n((a and b) and c) = (a and (b and c)): associativity of and \n((a or b) or c) = (a or (b or c)): associativity of or \nnot(not a) = a: double negation elimination \n(a implies b) = (not b implies not a): contraposition\n(a <==> b) = ((a implies b) and (b implies a)): biconditional elimination\nnot(a and b) = (not a or not b): de morgan\nnot(a or b) = (not a and not b): de morgan\n((a and b) or c) = ((a and b) or (a and c)): distributivity of and over or\n((a or b) and c) = ((a or b) and (a or c)): distibutivity of or over and \n\nMonotonicity implies soundness. resolution yields a complete inference algorithm.\n\nCNF: conjunctive normal form: every sentence of propositional logic is equivalent to a conjunction of clauses. Clauses are disjunctions of literals. Steps: 1) Eliminate <==> by replacing (A <==> B) with (a ==> B) and (B implies A). 2) Elminate ==> implies by replacing A ==> B with (not A or B).\n3) move not inwards by elminating double negations and apply de morgan's rules. \n4)Apply distibutivity laws to distibute or over and whenever possible. \n\nDefinite clause: disjunction of literals where exactly one is postive. Horn clause:\ndisjunction of literals wher eat most one is positive. This includes definite clauses, and clauses with no positive literals. \n\nForward chaining: is data driven reasoning to derive new conclusions. Backward chaining: works backwards from a query. If it is true, no work is needed. Otherwise, if all premises can be proven, then the quey is true. \n\nFollowing are in CNF (conjunctive normal form): (A), (A or B), (A or B) and (C), (A or not B or not C) and (not D or E or F). \n\nThe following are not in CNF: not (B or C), since or is nested within a not, (A and B) or C, A and (B or (D and E)), since an AND is nested within a OR.\n\nTo convert: 1) convert to negation normal form by replacing P --> Q with not P or Q, replace P <--> Q with (P or not Q) and (not P or Q). Move NOTs inward by replacing not(P or Q) with (not P) and (not Q). Replace  \n\n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}