{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "midterm notes",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "344222ad-a216-45e3-9726-b566dead59fe"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ef81cd11-e574-43c8-fb57-4c2e2e3d803c"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"Schools of thought: human vs rational + thought vs behavior. 2 ways to measure intelligence: empirical science w/observations + hypotheses about human behavior \\\n",
        "and thought process, or a rationalist approach combining math + engineering w/statistics, control theory, economics.\n",
        "Turing test approach: acting humanly - TTT: natural language processing for successful communication, knowledge representation to store info, automated reasoning to draw conclusions, machine learning to adapt + learn + find patterns. \\\n",
        "TTT also requires interaction w/objects and people in the real world, requiring: computer vision + speech recognition, and robotics to manip objects + move around.\n",
        "Thinking humanly - cognitive model approach: can learn about humans through introspection, psychological experiments, \\\n",
        "brain imaging. Precise theory of mind -- possible to express mind as a computer program. When program's in-out behavior matches corresponding human behavior, there is evidence \\\n",
        "that the program's mechanisms can also operate in humans. Cog. model more concerned w/comparing sequence + timing of reasoning steps to those of human subjects solving the same problems (models from AI \\\n",
        "+ experimental techniques from psychology to construct precise + testable theories of the human mind). This is separated from schools of thought that algos perform well on tasks = good model of human performance, \\\n",
        "as separation leads to cohesion.\n",
        "Thinking rationally: \"laws of thought\" approach, influenced by Aristotle and \"right thinking\". Syllogisms provide patterns for argument structures that yield \"correct\" \\\n",
        "conclusions, which are notations for statements about objects and relationships between objects. Logic requires knowledge \\\n",
        "the world that is certain - theory of probability fills in gap of uncertainty, allowing for construction of rational thought (does generate rational behavior, which requires rational action).\n",
        "Acting rationally: rational agent approach (act to achieve the best outcome). Skills needed for Turing test also allow an agent to act rationally - knowledge representation and reasoning enable agents to reach good decisions \\\n",
        "aka learning for functionality. Two advantages over other approaches are that it's more general than “laws of thought” approach: correct inference is just one of many \\\n",
        "mechanisms for achieving rationality, and it's more amenable to scientific development: mathematically defined and general. Standard model: study and construction of agents that \\\n",
        "do the right thing. Issue of limited rationality arises: acting appropriately when there is not enough time to do all the computations. \n",
        "Beneficial machines address that the standard model assumes that we will supply a fully specified objective to the machine. Tradeoffs with unexpected circumstances? Can't just always have one goal in mind.\\\n",
        " Value alignment problem deals w/achieving agreement between our \\\n",
        "true preferences and objective we put into the machine--those put into machine must align with human's.\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"Weak AI is the idea that machines could act as if they were intelligent. Strong AI is the assertion that machines are actually consciously thinking (not simulating thinking/human-level AI or general AI). \\\n",
        "Turing’s argument from informality: human behavior is far too complex to be captured by formal sets of rules. Humans must be using some informal guidelines that could never be captured in a formal set of rules \\\n",
        "and thus could never be codified in computer programs (according to Turing). Good Old-Fashioned AI: AI pursued in computational terms (GOFAI). Qualification problem: difficulty of capturing every contingency \\\n",
        "of appropriate behavior in a set of necessary and sufficient logical rules. Embodied cognition approach: brain is part of the body--it is thus embedded in an environment and should not be considered separately. \\\n",
        "Need to study the system as a whole: brain’s functioning exploits regularities in its environment: robotics, vision, sensory experiences are central.\n",
        "The argument from disability: machine can never do X. Turing’s examples: be kind, resourceful, friendly, enjoy ice cream, fall in love, etc., so they can’t be exactly human. The mathematical objection between \\\n",
        "Turing and Godel is that certain mathematical questions are in principle unanswerable by particular formal systems. Godel’s incompleteness theorem:\n",
        "G(F) is a sentence of F, but cannot be proved within F\n",
        "If F is consistent, then G(F) is true\n",
        "Lucas: theorem shows that machines are inferior to humans bc formal systems are limited by the incompleteness theorem and cannot establish the truth of their own Godel sentence, while humans don’t have this \\\n",
        "limitation but this statement has problems. Agent should not be ashamed that it cannot establish the truth while other agents can. Ex: “Lucas can’t consistently assert that this sentence is true.”, \\\n",
        "but if he asserts this sentence, he contradicts himself. There is already a true sentence that Lucas cannot assert while other people/machines can, but we don’t think less of Lucas.\n",
        "Godel’s incompleteness theorem and results apply to math and not to computers. No entity (human or machine) can prove things that are impossible to prove. Godel’s incompleteness theorem only applies to formal \\\n",
        "systems that are powerful enough to do arithmetic. This includes Turing machines, and Lucas assumes all machines are equivalents to Turing machines. Turing machines are infinite, whereas computers and brains \\\n",
        "are finite, and any computer can be described as a system in proposition logic, which is not subject to Godel’s incompleteness theorem. Humans can change their minds but so could machines after further \\\n",
        "deliberation with new info; upgrades in hardware; changes in its decision-making processes w/machine learning or software rewriting. We measure AI with Turing test, but no well-trained judge has been fooled yet. \\\n",
        "Point isn’t to fool judges, it’s to provide useful functionalities.\"\"\"\n",
        "chapter27_2 = \"\"\"Can Machines Really Think? The polite convention: assumption that systems are intelligent\n",
        "The Chinese Room: John Searle rejecting the polite convention. No one in the room understands Chinese--they’re just following the rule book (which also does not understand Chinese, but spells out conventions), \\\n",
        "therefore the people don’t understand Chinese. \n",
        "Proponent of biological naturalism--mental states are high-level features caused by low-level physical processes in the neurons, and it’s the properties of the neurons that matter. Neurons have “it” \\\n",
        "and transistors do not. Consciousness: awareness of the outside world, and of the self, and the subjective experience of living. Qualia: intrinsic nature of experiences. Can machines have qualia? \\\n",
        "Turing: interested in creating programs that behave intelligently, while aspects of consciousness (awareness) can be programmed and part of an intelligent machine\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"Four views of AI: thinking humanly, thinking rationally, acting humanly, acting rationally. An agent: anything that can perceive its environment and act on it. Sensors perceive \\\n",
        "the environment using these. Actuators allow the agent to act on its environment. Percept is agent’s perceptual inputs at any given instance. Vector of all inputs received from sensors. \\\n",
        "Agent functions map vector of inputs to an output action. This model of inputs to map of outputs can change over time depending on whether the environment is fully observable and depends \\\n",
        "on environment’s behavior--deterministic or stochastic (randomly determined)\n",
        "Agent program runs the physical architecture to produce the function. The agent = architecture + program. Easiest solution: lookup table of sorts for sequence P (sequence of percepts) to action a. \\\n",
        "This problem is exponential length of P and is too difficult to explicitly enumerate every possibility--solution: more sophisticated algorithms.\n",
        "Agent is generic and is anything that can be viewed as perceiving its actions through sensors; acting upon that environment using actuators. This can be humans, robots, software, thermostats, etc.\n",
        "Rational agent perceives its environment and behaves rationally/does the right thing. Consequentialism: evaluate the behavior of an agent/person based on the consequences of the actions it takes. \\\n",
        "We want only desirable consequences. This definition does not require omniscience (like predicting something bad before it happens, like freak accidents).\n",
        "Rational choice theory (Herbert Simon) states that agents can only make decisions based on the info available to them. They have their own preferences and opinions that create bias in behavior. \\\n",
        "There is no singular right choice with limited computational ability.\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"Performance measure is an object criterion for success of an agent’s behavior given the evidence provided by the percept sequence. Did the agent take the right action to maximize performance? \\\n",
        "Better to measure this by whether the performance you want from the agent is achieved, rather than how you think the agent should behave.\n",
        "Rational agent (redefined): for each possible percept sequence P, a rational agent selects action a that maximizes the expected value of the performance measure. rationality != omniscience. In actuality, \\\n",
        "computational limitations make complete rationality unachievable.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"Task environment: problem specification for which a rational agent is the solution. PEAS: to specify a task environment include performance measure, environment, actuators, sensors. \\\n",
        "Rational agent designer goals when given a PEAS task environment include abstract mathematical description: construct agent function f that gets the maximum expected value of performance measure; \\\n",
        "concrete implementation in which we design agent program that implements f on a particular architecture.\n",
        "Task environments are fully observable or partially observable. They describe task environments (for ex, a chess board is fully observable, while a elf driving car’s environment is partially observable). \\\n",
        "They are deterministic vs non deterministic vs stochastic (probabilistic); chess vs someone liking chocolate vs wheel of fortune. They are also episodic vs sequential, where episodic means the agent \\\n",
        "needs to process self-contained episodes and then performs a single action and choice of action is not dependent on previous action. In sequential environments, agents plan multiple steps ahead to \\\n",
        "determine the next best step. They are static vs dynamic (crossword puzzle vs self-driving car). They are discrete vs continuous, where there is a discrete number of distinct states in discrete environments, \\\n",
        "and have a finite set of actions. Continuous environments are ones that can go through a continuous range of values smoothly over time. Thy are single agent vs multi agent, where ulti agent environments \\\n",
        "are deterministic but need to take other agents (players in games) into account.\n",
        "When is something considered an agent? The thing’s behavior can be described as having its own performance measure. Telephone pole is environment and another car is an agent. Hardest environment is continuous, \\\n",
        "partially observable, stochastic, multiagent. For example, a self-driving car would be an agent. Simple task environments are static, fully observable, deterministic, discrete.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"An agent = architecture + program. There is a lookup table (map) that maps certain input to behavior output (table-driven-agent function). A key challege for AI is to find out how to \\\n",
        "design programs that produce rational behavior from a small program rather than table--should be able to make determinations. 4 agent programs embody the principles underlying all \\\n",
        "intelligent systems: simple reflex, model-based reflex, goal-based, and utility-based. \n",
        "Simple reflex agents selection actions based on the current percept and ignore the previous percept history (ex: vacuum). These behaviors occur in more complex environments often. \\\n",
        "They implement a condition-action rule, written as if-then statements. \n",
        "Model-based reflex agents handle partial observability by keeping track of the part of the world it can't see now. It maintains an internal state dependent on percept history and reflects \\\n",
        "some of the unobserved aspects of the current state. Updating state requires two kinds of knowledge: info about how the world changes over time (effects of agents's actions + how the world evolves \\\n",
        "independntly of the agent/transition model of the world), and info about how state of the world is reflected in percepts (using sensor models).\n",
        "Goal-based agents require goal information (describes desirable outcomes). Agent program combines with this model to choose actions to achieve that desirable goal. Search and planning are fields in AI that \\\n",
        "help determine action sequences to achieve agent goals.\n",
        "Utility-based agents make decisions and chooses between actions based on how happy it'd make the agent. Agent has a utility function that internalizes such performance measures \\\n",
        "for each environment, allowing the agent to maximize its utility on that state. Conflicting goals lead to tradeoffs and several uncertain goals exist means utility can help measure \\\n",
        "a greater likelihood of success (vs importance of goals). Learning agents can be divided into four components: the learning element (makes improvements), the performance element \\\n",
        "(responsible for selecting external actions), the critic (determines performanc element), the problem generator (which suggets actions that lead to new + informative experiences). \\\n",
        "Performance standard must determine a percept as a reward or penatly and provides feedback to the agent about its behavior.\n",
        "Factored representations split up states into variables and attributes, and each have a value (fixed). We can also have structured \\\n",
        "representations, which objects and their various/varying relationships are defined explicitly. These representations lie along an axis of increasing expressiveness, \\\n",
        "and more expressive representation is more detailed and concise (reasoning + learning are more complex). Another axis for \\\n",
        "representation is mapping of concepts to locations in memory--localist representation. When memory location is spread out for a representation of a concept = a distributed representation.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\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": 22,
      "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": 2765
        },
        "outputId": "bbb615ab-1edc-42c4-d637-f37944e2f5de"
      },
      "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": 23,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nSchools of thought: human vs rational + thought vs behavior. 2 ways to measure intelligence: empirical science w/observations + hypotheses about human behavior and thought process, or a rationalist approach combining math + engineering w/statistics, control theory, economics.\nTuring test approach: acting humanly - TTT: natural language processing for successful communication, knowledge representation to store info, automated reasoning to draw conclusions, machine learning to adapt + learn + find patterns. TTT also requires interaction w/objects and people in the real world, requiring: computer vision + speech recognition, and robotics to manip objects + move around.\nThinking humanly - cognitive model approach: can learn about humans through introspection, psychological experiments, brain imaging. Precise theory of mind -- possible to express mind as a computer program. When program's in-out behavior matches corresponding human behavior, there is evidence that the program's mechanisms can also operate in humans. Cog. model more concerned w/comparing sequence + timing of reasoning steps to those of human subjects solving the same problems (models from AI + experimental techniques from psychology to construct precise + testable theories of the human mind). This is separated from schools of thought that algos perform well on tasks = good model of human performance, as separation leads to cohesion.\nThinking rationally: \"laws of thought\" approach, influenced by Aristotle and \"right thinking\". Syllogisms provide patterns for argument structures that yield \"correct\" conclusions, which are notations for statements about objects and relationships between objects. Logic requires knowledge the world that is certain - theory of probability fills in gap of uncertainty, allowing for construction of rational thought (does generate rational behavior, which requires rational action).\nActing rationally: rational agent approach (act to achieve the best outcome). Skills needed for Turing test also allow an agent to act rationally - knowledge representation and reasoning enable agents to reach good decisions aka learning for functionality. Two advantages over other approaches are that it's more general than “laws of thought” approach: correct inference is just one of many mechanisms for achieving rationality, and it's more amenable to scientific development: mathematically defined and general. Standard model: study and construction of agents that do the right thing. Issue of limited rationality arises: acting appropriately when there is not enough time to do all the computations. \nBeneficial machines address that the standard model assumes that we will supply a fully specified objective to the machine. Tradeoffs with unexpected circumstances? Can't just always have one goal in mind. Value alignment problem deals w/achieving agreement between our true preferences and objective we put into the machine--those put into machine must align with human's.\n\n## AIMA Chapter 27.1 The Limits of AI\nWeak AI is the idea that machines could act as if they were intelligent. Strong AI is the assertion that machines are actually consciously thinking (not simulating thinking/human-level AI or general AI). Turing’s argument from informality: human behavior is far too complex to be captured by formal sets of rules. Humans must be using some informal guidelines that could never be captured in a formal set of rules and thus could never be codified in computer programs (according to Turing). Good Old-Fashioned AI: AI pursued in computational terms (GOFAI). Qualification problem: difficulty of capturing every contingency of appropriate behavior in a set of necessary and sufficient logical rules. Embodied cognition approach: brain is part of the body--it is thus embedded in an environment and should not be considered separately. Need to study the system as a whole: brain’s functioning exploits regularities in its environment: robotics, vision, sensory experiences are central.\nThe argument from disability: machine can never do X. Turing’s examples: be kind, resourceful, friendly, enjoy ice cream, fall in love, etc., so they can’t be exactly human. The mathematical objection between Turing and Godel is that certain mathematical questions are in principle unanswerable by particular formal systems. Godel’s incompleteness theorem:\nG(F) is a sentence of F, but cannot be proved within F\nIf F is consistent, then G(F) is true\nLucas: theorem shows that machines are inferior to humans bc formal systems are limited by the incompleteness theorem and cannot establish the truth of their own Godel sentence, while humans don’t have this limitation but this statement has problems. Agent should not be ashamed that it cannot establish the truth while other agents can. Ex: “Lucas can’t consistently assert that this sentence is true.”, but if he asserts this sentence, he contradicts himself. There is already a true sentence that Lucas cannot assert while other people/machines can, but we don’t think less of Lucas.\nGodel’s incompleteness theorem and results apply to math and not to computers. No entity (human or machine) can prove things that are impossible to prove. Godel’s incompleteness theorem only applies to formal systems that are powerful enough to do arithmetic. This includes Turing machines, and Lucas assumes all machines are equivalents to Turing machines. Turing machines are infinite, whereas computers and brains are finite, and any computer can be described as a system in proposition logic, which is not subject to Godel’s incompleteness theorem. Humans can change their minds but so could machines after further deliberation with new info; upgrades in hardware; changes in its decision-making processes w/machine learning or software rewriting. We measure AI with Turing test, but no well-trained judge has been fooled yet. Point isn’t to fool judges, it’s to provide useful functionalities.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nCan Machines Really Think? The polite convention: assumption that systems are intelligent\nThe Chinese Room: John Searle rejecting the polite convention. No one in the room understands Chinese--they’re just following the rule book (which also does not understand Chinese, but spells out conventions), therefore the people don’t understand Chinese. \nProponent of biological naturalism--mental states are high-level features caused by low-level physical processes in the neurons, and it’s the properties of the neurons that matter. Neurons have “it” and transistors do not. Consciousness: awareness of the outside world, and of the self, and the subjective experience of living. Qualia: intrinsic nature of experiences. Can machines have qualia? Turing: interested in creating programs that behave intelligently, while aspects of consciousness (awareness) can be programmed and part of an intelligent machine\n\n\n## AIMA 2.1 Agents and Environments\nFour views of AI: thinking humanly, thinking rationally, acting humanly, acting rationally. An agent: anything that can perceive its environment and act on it. Sensors perceive the environment using these. Actuators allow the agent to act on its environment. Percept is agent’s perceptual inputs at any given instance. Vector of all inputs received from sensors. Agent functions map vector of inputs to an output action. This model of inputs to map of outputs can change over time depending on whether the environment is fully observable and depends on environment’s behavior--deterministic or stochastic (randomly determined)\nAgent program runs the physical architecture to produce the function. The agent = architecture + program. Easiest solution: lookup table of sorts for sequence P (sequence of percepts) to action a. This problem is exponential length of P and is too difficult to explicitly enumerate every possibility--solution: more sophisticated algorithms.\nAgent is generic and is anything that can be viewed as perceiving its actions through sensors; acting upon that environment using actuators. This can be humans, robots, software, thermostats, etc.\nRational agent perceives its environment and behaves rationally/does the right thing. Consequentialism: evaluate the behavior of an agent/person based on the consequences of the actions it takes. We want only desirable consequences. This definition does not require omniscience (like predicting something bad before it happens, like freak accidents).\nRational choice theory (Herbert Simon) states that agents can only make decisions based on the info available to them. They have their own preferences and opinions that create bias in behavior. There is no singular right choice with limited computational ability.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nPerformance measure is an object criterion for success of an agent’s behavior given the evidence provided by the percept sequence. Did the agent take the right action to maximize performance? Better to measure this by whether the performance you want from the agent is achieved, rather than how you think the agent should behave.\nRational agent (redefined): for each possible percept sequence P, a rational agent selects action a that maximizes the expected value of the performance measure. rationality != omniscience. In actuality, computational limitations make complete rationality unachievable.\n\n\n## AIMA 2.3 The Nature of Environments\nTask environment: problem specification for which a rational agent is the solution. PEAS: to specify a task environment include performance measure, environment, actuators, sensors. Rational agent designer goals when given a PEAS task environment include abstract mathematical description: construct agent function f that gets the maximum expected value of performance measure; concrete implementation in which we design agent program that implements f on a particular architecture.\nTask environments are fully observable or partially observable. They describe task environments (for ex, a chess board is fully observable, while a elf driving car’s environment is partially observable). They are deterministic vs non deterministic vs stochastic (probabilistic); chess vs someone liking chocolate vs wheel of fortune. They are also episodic vs sequential, where episodic means the agent needs to process self-contained episodes and then performs a single action and choice of action is not dependent on previous action. In sequential environments, agents plan multiple steps ahead to determine the next best step. They are static vs dynamic (crossword puzzle vs self-driving car). They are discrete vs continuous, where there is a discrete number of distinct states in discrete environments, and have a finite set of actions. Continuous environments are ones that can go through a continuous range of values smoothly over time. Thy are single agent vs multi agent, where ulti agent environments are deterministic but need to take other agents (players in games) into account.\nWhen is something considered an agent? The thing’s behavior can be described as having its own performance measure. Telephone pole is environment and another car is an agent. Hardest environment is continuous, partially observable, stochastic, multiagent. For example, a self-driving car would be an agent. Simple task environments are static, fully observable, deterministic, discrete.\n\n\n## AIMA 2.4 The Structure of Agents\nAn agent = architecture + program. There is a lookup table (map) that maps certain input to behavior output (table-driven-agent function). A key challege for AI is to find out how to design programs that produce rational behavior from a small program rather than table--should be able to make determinations. 4 agent programs embody the principles underlying all intelligent systems: simple reflex, model-based reflex, goal-based, and utility-based. \nSimple reflex agents selection actions based on the current percept and ignore the previous percept history (ex: vacuum). These behaviors occur in more complex environments often. They implement a condition-action rule, written as if-then statements. \nModel-based reflex agents handle partial observability by keeping track of the part of the world it can't see now. It maintains an internal state dependent on percept history and reflects some of the unobserved aspects of the current state. Updating state requires two kinds of knowledge: info about how the world changes over time (effects of agents's actions + how the world evolves independntly of the agent/transition model of the world), and info about how state of the world is reflected in percepts (using sensor models).\nGoal-based agents require goal information (describes desirable outcomes). Agent program combines with this model to choose actions to achieve that desirable goal. Search and planning are fields in AI that help determine action sequences to achieve agent goals.\nUtility-based agents make decisions and chooses between actions based on how happy it'd make the agent. Agent has a utility function that internalizes such performance measures for each environment, allowing the agent to maximize its utility on that state. Conflicting goals lead to tradeoffs and several uncertain goals exist means utility can help measure a greater likelihood of success (vs importance of goals). Learning agents can be divided into four components: the learning element (makes improvements), the performance element (responsible for selecting external actions), the critic (determines performanc element), the problem generator (which suggets actions that lead to new + informative experiences). Performance standard must determine a percept as a reward or penatly and provides feedback to the agent about its behavior.\nFactored representations split up states into variables and attributes, and each have a value (fixed). We can also have structured representations, which objects and their various/varying relationships are defined explicitly. These representations lie along an axis of increasing expressiveness, and more expressive representation is more detailed and concise (reasoning + learning are more complex). Another axis for representation is mapping of concepts to locations in memory--localist representation. When memory location is spread out for a representation of a concept = a distributed representation.\n\n## Module 1 Lecture Notes\n Your summary here \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 = \"\"\"Strings + tuples (which can be mixed type) are immutable (have to reassign as with Java). We use Is to check pointer in memory vs == for the same value. Lists are mutable and we can use \\\n",
        "Y = x[:] to get and assign a shallow copy. Python 3 strings: Unicode (vs 8-bit in the past). Slicing is inclusive, exclusive.\n",
        "For lists, sorted(list) needs to be reassigned, while li.sort() sorts in place (no need to reassign)\n",
        "For dicts, values can be reassigned, cannot do lookup by value\n",
        "For functions: no declaration of arg or return types, and can return multiple values as a tuple.\n",
        "No function overloading in Python (whereas Java can have multiple functions w/the same name), but operator overloading is possible when implementing a class.\n",
        "We can provide default values for arguments--these are optional arguments when function is called. Non default arguments should precede default arguments. Keyword arguments are arguments that \\\n",
        "can be called out of order if specified when called. *args allows functions to accept a variable num of non-keyword arguments, **kwargs same but keyword arguments\n",
        "Dynamic scope: takes the most value for the variable.\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 379
        },
        "outputId": "3128a39b-b177-4f12-ca63-cc500eb3e1db"
      },
      "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": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\nStrings + tuples (which can be mixed type) are immutable (have to reassign as with Java). We use Is to check pointer in memory vs == for the same value. Lists are mutable and we can use Y = x[:] to get and assign a shallow copy. Python 3 strings: Unicode (vs 8-bit in the past). Slicing is inclusive, exclusive.\nFor lists, sorted(list) needs to be reassigned, while li.sort() sorts in place (no need to reassign)\nFor dicts, values can be reassigned, cannot do lookup by value\nFor functions: no declaration of arg or return types, and can return multiple values as a tuple.\nNo function overloading in Python (whereas Java can have multiple functions w/the same name), but operator overloading is possible when implementing a class.\nWe can provide default values for arguments--these are optional arguments when function is called. Non default arguments should precede default arguments. Keyword arguments are arguments that can be called out of order if specified when called. *args allows functions to accept a variable num of non-keyword arguments, **kwargs same but keyword arguments\nDynamic scope: takes the most value for the variable.\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 = \"\"\"For problem-solving agents, unknown environments mean uninformed decisions--> all possibilities must be explored. In four-phase problem solving we require goal formulation (agent adopts \\\n",
        "a goal such that goal limits objective and the actions to be considered); problem formulation (agent formulates description of the states and actions needed to achieve described states and goals; abstract \\\n",
        "model of the relevant part of the world); search (agent simulates sequences to find the one that is the solution (leads to the goal state) and either finds that there is or isn’t a solution); \\\n",
        "execution  (agent executes the actions in the solution, one at a time).\n",
        "In fully observable, deterministic, known environments, there is always a solution to the problem that is a fixed sequence of events (or no solution). An open-loop system is when percepts of an agent \\\n",
        "are separated from the environment. This happens when a solution is found--an agent can execute the solution without further regarding its environment. It is generally safer to use a closed-loop solution, \\\n",
        "which allows agent to monitor its environment in case the model is incorrect or the environment is indeterministic.\n",
        "Search problem definition is made of state space (set of possible states the environment can be in); initial state; goal state (can be one or more); actions(s): set of executable actions in s (the state space) \\\n",
        "where finite set of actions are applicable in s; ation cost function (determines the cost of a particular action in the state in a numeric form); path (set of actions) where a solution is a path from initial \\\n",
        "state to the goal state, and an optimal solution has the lowest cost from the initial to goal state; state space can be represented as a graph, where vertices are states and edges are actions.\n",
        "A model is a formulation of a problem. Abstractions are models of a problem with the fine details removed where the level of abstraction should be appropriate so that the user is able to understand \\\n",
        " the instructions without being too overly detailed.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"Standardized problem illustrates/exercises various problem solving methods and can be given in explicit terms and suitable for researchers to compare solutions and optimality in the algorithm. \n",
        "A real-world problem finds solutions that people actually use, and often are idiosyncratic, non-standardized. Grid world problem is usually represented in a 2D rectangular array of cells where agent traverses \\\n",
        "from cell to cell.\n",
        "Route-finding problems in real life are websites and in-car systems that often use these methods.\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"Search algorithm takes a search problem as an input and returns a solution/indication of failure. Many of these algorithms utilize a search tree superimposed over the state-space graph that \\\n",
        "forms many paths from the initial state to try and a find a path that reaches the goal state. Node = state; edges = actions; root = initial state. Expanding a particular node creates a child/successor node \\\n",
        "(available actions for that particular state); every child node also has a parent node. Frontier of search tree = child nodes that are leaf nodes. \n",
        "Best-first search process occurs such that 1. we choose a node n, with some minimum value of an evaluation function f(n) and 2. for each iteration, we choose the node on the frontier with min f(n) value \\\n",
        "and expand from there. 3 kinds of queues to support this are the priority queue (ordered by min cost), FIFO: first in, first out (BFS), and LIFO: last in, first out (DFS).\n",
        "Repeated state means that redundant paths form cycles and can cause a complete infinite search tree, and redundant paths are not optimal. We can measure problem-solving performance by completeness (does \\\n",
        "the algorithm find a solution/report when no solution is available?); cost optimality (does it find the solution with the lowest path cost of all solutions?); time complexity (how long does it take to find \\\n",
        "the solution?); and space complexity (how much memory is needed to perform the search?).\n",
        "A complete search algorithm should also be systematic and should explore a finite state space. For implicit state space, complexity can be measured in terms of d, \\\n",
        "depth (# of actions in optimal solution), m, number of maximum actions in any path, b, branching factor (number of successors of a node that must be considered).\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"Uninformed search strategies means the agent has no clue about how close the state is to the goal\n",
        "Breadth-first search can make a better algorithm by performing early goal test, which is checking for the solution as we go along; vs best-first search’s late goal test. Space and time is both O(b^d), \\\n",
        "where b = successors and d = depth.\n",
        "Dijkstra’s algorithm/uniform-cost search is a best-first search where the evaluation function is the cost of the path from the root to the current node\n",
        "Depth-first search always expands the deepest node in the frontier first. It is not an optimal solution--may return a non-optimal solution, but has much smaller needs for memory. Memory is O(bm), where \\\n",
        "b is the branching factor and m is the maximum depth of the tree. A variant of depth-first search uses backtracking, which only expands one successor at a time, such that memory becomes O(m).\n",
        "Depth-limited search is depth-first search but we stop at a limit l, which we treat as frontier nodes with no successors. The time = O(b^l) and space = O(bl), but we may  not necessarily find a solution. This \\\n",
        "algorithm is not complete! The diameter of state-space graph: max number of actions to reach goal state.\n",
        "Iterative deepening search has memory of O(bd) with a solution and O(bm) when there is not a solution. This is good for when all actions have the same cost. It essentially is a depth-limited search but reaches failure instead of cutoff if no solution is found\n",
        "Time is O(b^d) when there is a solution and O(b^m) when there is not. In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory \\\n",
        "and the depth of the solution is not known.\n",
        "Bidirectional search searches forward from the initial state and backwards from the goal state, hoping the two searches will meet\n",
        "Optimality of different algorithms: depth-first and depth-limited are not complete and not optimal, while others are.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\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": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1358
        },
        "outputId": "dde0ec7a-10cd-431a-93bd-92c50e28dcc2"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nFor problem-solving agents, unknown environments mean uninformed decisions--> all possibilities must be explored. In four-phase problem solving we require goal formulation (agent adopts a goal such that goal limits objective and the actions to be considered); problem formulation (agent formulates description of the states and actions needed to achieve described states and goals; abstract model of the relevant part of the world); search (agent simulates sequences to find the one that is the solution (leads to the goal state) and either finds that there is or isn’t a solution); execution  (agent executes the actions in the solution, one at a time).\nIn fully observable, deterministic, known environments, there is always a solution to the problem that is a fixed sequence of events (or no solution). An open-loop system is when percepts of an agent are separated from the environment. This happens when a solution is found--an agent can execute the solution without further regarding its environment. It is generally safer to use a closed-loop solution, which allows agent to monitor its environment in case the model is incorrect or the environment is indeterministic.\nSearch problem definition is made of state space (set of possible states the environment can be in); initial state; goal state (can be one or more); actions(s): set of executable actions in s (the state space) where finite set of actions are applicable in s; ation cost function (determines the cost of a particular action in the state in a numeric form); path (set of actions) where a solution is a path from initial state to the goal state, and an optimal solution has the lowest cost from the initial to goal state; state space can be represented as a graph, where vertices are states and edges are actions.\nA model is a formulation of a problem. Abstractions are models of a problem with the fine details removed where the level of abstraction should be appropriate so that the user is able to understand  the instructions without being too overly detailed.\n\n\n## AIMA Chapter 3.2 Example Problems\nStandardized problem illustrates/exercises various problem solving methods and can be given in explicit terms and suitable for researchers to compare solutions and optimality in the algorithm. \nA real-world problem finds solutions that people actually use, and often are idiosyncratic, non-standardized. Grid world problem is usually represented in a 2D rectangular array of cells where agent traverses from cell to cell.\nRoute-finding problems in real life are websites and in-car systems that often use these methods.\n\n\n## AIMA Chapter 3.3 Search Algorithms\nSearch algorithm takes a search problem as an input and returns a solution/indication of failure. Many of these algorithms utilize a search tree superimposed over the state-space graph that forms many paths from the initial state to try and a find a path that reaches the goal state. Node = state; edges = actions; root = initial state. Expanding a particular node creates a child/successor node (available actions for that particular state); every child node also has a parent node. Frontier of search tree = child nodes that are leaf nodes. \nBest-first search process occurs such that 1. we choose a node n, with some minimum value of an evaluation function f(n) and 2. for each iteration, we choose the node on the frontier with min f(n) value and expand from there. 3 kinds of queues to support this are the priority queue (ordered by min cost), FIFO: first in, first out (BFS), and LIFO: last in, first out (DFS).\nRepeated state means that redundant paths form cycles and can cause a complete infinite search tree, and redundant paths are not optimal. We can measure problem-solving performance by completeness (does the algorithm find a solution/report when no solution is available?); cost optimality (does it find the solution with the lowest path cost of all solutions?); time complexity (how long does it take to find the solution?); and space complexity (how much memory is needed to perform the search?).\nA complete search algorithm should also be systematic and should explore a finite state space. For implicit state space, complexity can be measured in terms of d, depth (# of actions in optimal solution), m, number of maximum actions in any path, b, branching factor (number of successors of a node that must be considered).\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nUninformed search strategies means the agent has no clue about how close the state is to the goal\nBreadth-first search can make a better algorithm by performing early goal test, which is checking for the solution as we go along; vs best-first search’s late goal test. Space and time is both O(b^d), where b = successors and d = depth.\nDijkstra’s algorithm/uniform-cost search is a best-first search where the evaluation function is the cost of the path from the root to the current node\nDepth-first search always expands the deepest node in the frontier first. It is not an optimal solution--may return a non-optimal solution, but has much smaller needs for memory. Memory is O(bm), where b is the branching factor and m is the maximum depth of the tree. A variant of depth-first search uses backtracking, which only expands one successor at a time, such that memory becomes O(m).\nDepth-limited search is depth-first search but we stop at a limit l, which we treat as frontier nodes with no successors. The time = O(b^l) and space = O(bl), but we may  not necessarily find a solution. This algorithm is not complete! The diameter of state-space graph: max number of actions to reach goal state.\nIterative deepening search has memory of O(bd) with a solution and O(bm) when there is not a solution. This is good for when all actions have the same cost. It essentially is a depth-limited search but reaches failure instead of cutoff if no solution is found\nTime is O(b^d) when there is a solution and O(b^m) when there is not. In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and the depth of the solution is not known.\nBidirectional search searches forward from the initial state and backwards from the goal state, hoping the two searches will meet\nOptimality of different algorithms: depth-first and depth-limited are not complete and not optimal, while others are.\n\n## Module 3 Lecture Notes\n Your summary here \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 = \"\"\"Greedy best-first expands first node with lowest h(n) value that seems to lead most quickly to solution. Space/time is O(|V|).\n",
        "For A*, f(n) = complete path and admissible + cost-optimal, as A* expands all nodes that can be reached \\\n",
        "from the initial state on a path where every node on the path has (surely-expanded nodes). Efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution. \\\n",
        "A* expands all nodes that can be reached from the initial state on a path where every node on the path has f(n) < C* (surely expanded nodes), where C* is cost of the optimal solution path. A* w/a \\\n",
        "consistent heuristic is optimally efficient: extends paths from the initial state and uses the same heuristic information and expands all nodes that are surely expanded by A*.\n",
        "Satisficing solutions are less optimal solutions that explore less nodes and take less time. Inadmissible heuristic is more accurate but not optimal.\n",
        "Suboptimal search algorithms include bounded suboptimal search (solution guaranteed to be within constant factor W of optimal cost); bounded-cost search (solution whose cost is less than some constant C); \\\n",
        "unbounded-cost search (solution of any cost, as long as we can find it quickly) (ex: speedy search, a GBF that uses the estimated number of \\\n",
        "actions required to reach a goal as a heuristic, same as GBF when actions have equal cost. Otherwise, it finds a solution more quickly w/higher cost).\n",
        "Memory-bounded search is when memory is split between frontier and reached states. Duplicating states in the frontier requires a trivial amount of memory (bc size of frontier is smaller than reached).\n",
        "Reference counts is the num of times a state has been reached and remove it from the reached table when there are no more ways to reach the state. Algorithms that conserve memory usage include \\\n",
        "beam search (limits the size of the frontier) and keeps only the k nodes with the best f-scores, discarding any other expanded nodes. This is incomplete and suboptimal, but k can be a good use of \\\n",
        "available memory and the algorithm executes fast bc it expands fewer nodes. Essentially a focused part of the concentric contours of uniform-cost or A* search, which will contain the k best candidates.\n",
        "Iterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth-first: benefits of A* w/o requirement to keep all reached states in memory at cost of visiting redundant states.\n",
        "Recursive best-first search is recursive DFS with limit to keep track of best alternative path from any ancestor of the current node (keeps backed-up value)\n",
        "MA* (memory-bounded A*) and SMA* (simplified MA*) are A* but, respectively, expanding the best leaf until memory is full; dropping the worst leaf node (the one with the highest f-value)\n",
        "Bidirectional heuristic search is f_F(n) = gF(n) + hF(n) for forward and f_B(n) = gB(n) + hB(n) for nodes in the backward direction\n",
        "Front-to-front search attempts to estimate the distance to the other frontier\"\"\"\n",
        "chapter3_6 = \"\"\"Effective branching factor b*: one way to characterize the quality of a heuristic. Another way to characterize the effect of A* pruning with the given heuristic h because it reduces \\\n",
        "the effective depth by a constant kh compared to the true depth, and H2 dominates H1 in that it’s always better. \n",
        "State-space graph is a supergraph of the original state space. Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. It must obey the triangle inequality \\\n",
        "and be consistent. Admissible heuristics can be derived from the solution cost of a subproblem of a given problem\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Relaxed problem\" : \"problem with fewer restrictions on actions\",\n",
        "\"Pattern databases\" : \"store exact solution costs for every possible subproblem instance\", \n",
        "\"Disjoint pattern databases\" : \"sum of two costs is still a lower bound on the cost of solving the entire problem\", \n",
        "\"precomputation\" : \"done once and can be amortized over billions of search requests (the precomputation is time consuming but is helpful later)\",\n",
        "\"metalevel state space\" : \"each state in space captures internal (computational) state of a program that is searching in an ordinary state space\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 953
        },
        "cellView": "form",
        "outputId": "a1849c06-97ef-4281-fd84-ea3d77ff2882"
      },
      "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": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nGreedy best-first expands first node with lowest h(n) value that seems to lead most quickly to solution. Space/time is O(|V|).\nFor A*, f(n) = complete path and admissible + cost-optimal, as A* expands all nodes that can be reached from the initial state on a path where every node on the path has (surely-expanded nodes). Efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution. A* expands all nodes that can be reached from the initial state on a path where every node on the path has f(n) < C* (surely expanded nodes), where C* is cost of the optimal solution path. A* w/a consistent heuristic is optimally efficient: extends paths from the initial state and uses the same heuristic information and expands all nodes that are surely expanded by A*.\nSatisficing solutions are less optimal solutions that explore less nodes and take less time. Inadmissible heuristic is more accurate but not optimal.\nSuboptimal search algorithms include bounded suboptimal search (solution guaranteed to be within constant factor W of optimal cost); bounded-cost search (solution whose cost is less than some constant C); unbounded-cost search (solution of any cost, as long as we can find it quickly) (ex: speedy search, a GBF that uses the estimated number of actions required to reach a goal as a heuristic, same as GBF when actions have equal cost. Otherwise, it finds a solution more quickly w/higher cost).\nMemory-bounded search is when memory is split between frontier and reached states. Duplicating states in the frontier requires a trivial amount of memory (bc size of frontier is smaller than reached).\nReference counts is the num of times a state has been reached and remove it from the reached table when there are no more ways to reach the state. Algorithms that conserve memory usage include beam search (limits the size of the frontier) and keeps only the k nodes with the best f-scores, discarding any other expanded nodes. This is incomplete and suboptimal, but k can be a good use of available memory and the algorithm executes fast bc it expands fewer nodes. Essentially a focused part of the concentric contours of uniform-cost or A* search, which will contain the k best candidates.\nIterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth-first: benefits of A* w/o requirement to keep all reached states in memory at cost of visiting redundant states.\nRecursive best-first search is recursive DFS with limit to keep track of best alternative path from any ancestor of the current node (keeps backed-up value)\nMA* (memory-bounded A*) and SMA* (simplified MA*) are A* but, respectively, expanding the best leaf until memory is full; dropping the worst leaf node (the one with the highest f-value)\nBidirectional heuristic search is f_F(n) = gF(n) + hF(n) for forward and f_B(n) = gB(n) + hB(n) for nodes in the backward direction\nFront-to-front search attempts to estimate the distance to the other frontier\n\n## AIMA Chapter 3.6 Heuristic Functions\nEffective branching factor b*: one way to characterize the quality of a heuristic. Another way to characterize the effect of A* pruning with the given heuristic h because it reduces the effective depth by a constant kh compared to the true depth, and H2 dominates H1 in that it’s always better. \nState-space graph is a supergraph of the original state space. Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. It must obey the triangle inequality and be consistent. Admissible heuristics can be derived from the solution cost of a subproblem of a given problem\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Relaxed problem** - problem with fewer restrictions on actions\n* **Pattern databases** - store exact solution costs for every possible subproblem instance\n* **Disjoint pattern databases** - sum of two costs is still a lower bound on the cost of solving the entire problem\n* **Precomputation** - done once and can be amortized over billions of search requests (the precomputation is time consuming but is helpful later)\n* **Metalevel state space** - each state in space captures internal (computational) state of a program that is searching in an ordinary state space\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 = \"\"\"What is search for? Assumptions about the world: a single agent, deterministic actions, fully observed state, discrete state space. Path to goal is the important thing \\\n",
        "(paths have various costs, depths), and heuristics give problem-specific guidance. Identification is assignments to variables, and the oal itself is important, not the path.\n",
        "All paths are at the same depth (for some formulations), and CSPs are specialized for identification problems\n",
        "CSPs represent the constraints that solutions must satisfy in a uniform declarative language. It must find solutions by general purpose search algorithms with no changes from problem to problem. There are \\\n",
        "no hand-build transition functions and no hand-built heuristics. We specify the problem in a formal declarative language, and a general-purpose algorithm does everything else\n",
        "CSP consists of a finite set of variables; a nonempty domain of possible values for each variable where D1, D2, Dn where Di = {v1, ..., vk}; a finite set of constraints (C2, C2, ..., Cm) where each \\\n",
        "constraint Ci limits the values that variables can take. A state is defined as an assignment of values to some or all variables, and a consistent assignment does not violate the constraints\n",
        "Assignment is complete when every variable is assigned a value: solution to a CSP is a complete, consistent, assignment and can be found.\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"Minimax search: derived as solution for nondeterministic planning problems; desirable outcome must be guaranteed no matter what the “other side” does and is for \\\n",
        "games with multiple score outcomes. Optimal strategy given a game tree determined by working out the minimax value of each state n the tree. The minimax value of a terminal state = utility. \\\n",
        "Minimax is the utility of being in that state (for MAX), assuming that both players play optimally from there to the end of the game. It is a recursive algorithm that proceeds all the way down to the leaves of \\\n",
        "tree and backs up the minimax values through the tree as the recursion unwinds. It performs a complete depth-first exploration of the game tree. If max depth of the tree is m and there are b legal moves at each \\\n",
        "point, then the time-complexity of the minimax algorithm is O(b^m). Space complexity is O(bm) for an algorithm that generates all actions, or O(m) for one that generates actions one at a time (not good \\\n",
        "for games like chess).\n",
        "Optimal decisions in multiplayer games involves using a vector to replace single value for each node, and a utility function can return a vector of utilities\n",
        "Alpha-beta pruning uses pruning to get rid of large parts of the tree  that make no difference to the outcome. The value of root and minimax decision are independent of the values of the arbitrary leaves \\\n",
        "x, y, so they can be pruned. Consider a node n somewhere in the tree, such that a player has a chance of moving to n 1. If the  player has a better choice either at the same level, or any point higher up \\\n",
        "in the tree, player will never have to move to n. Minimax is depth-first, so we have to consider the nodes along a single path in the tree\n",
        "Alpha-beta pruning gets its name from the two extra params in MAX-VALUE, where alpha is the value of the best choice we have found at any choice point allong the path for max (alpha = at least) and \\\n",
        "beta is the value of the best (loweset value) choice we have found so for at any choice point along the path for MIN (beta = at most). It is O(b^m) such that branching becomes sqrt(b) instead of b\n",
        "Iterative deepening searches one ply deep, record running of moves, then continue to go deeper.\n",
        "Transpositions are different permutations of the same move sequence that end up in the same position, and the problem can be addressed w/a transposition table that caches the heuristic values of states\n",
        "Type A: considers all possible moves to a certain depth in the search tree and uses h(n) to estimate the utility of states at that depth -- wide but shallow\n",
        "Type B:: ignores moves that look bad and follows promising lines as far as possible -- deep but narrow \n",
        "Chess is A, and Go is B (higher branching factor)\"\"\"\n",
        "chapter5_3 = \"\"\"Heuristic AB tree cuts off search early and apply h(n). Nodes become terminal, eval + cutoff test to cut search by the search depth and property of the state.\n",
        "Material value helps determine value of positions for eval functions (weighted linear function). Cutting off search checks if max depth reached and can lead to errors due to \\\n",
        "approximate nature of eval function (should only be applied to quiescent positions). Quiescence search is restricted to consider only certain types of moves, such as capture moves\n",
        "Horizon effect allows for singular extensions--clearly better move than all other moves in a given positions, even when the search would normally be cut off at that point\n",
        "Forward pruning prunes moves that appear to be poor moves, but might possibly be good ones to save computation time at risk of making errors.\n",
        "Beam search: consider only a beam of the n best moves rather than all possible moves. ProbCut prunes nodes that are probably outside of the window. Late move reduction assumes that \\\n",
        "move ordering is done well and moves that appear later in the list are less likely to be good--this redueces depth of searched moves, saving time. If reduced search comes \\\n",
        "back w/value above current alpha, we can re-run the search with the full depth\n",
        "Search vs lookup policy maps from every possible state to the best move in that state. The computer can play perfectly by lookup in the table constructed by retrograde minimax search.\n",
        "MCTS looks at value of state estimated as the average utility over a number of simulations of complete games starting from the state. Simulation/playout/rollout chooses moves first \\\n",
        "for one player, then for other, repeating until terminal position reached. Playout policy biases the moves towards good ones. Do N simulations \\\n",
        "from current state of game and track which moves has the highest win percentage. For stochastic games, this converges to optimal play as N increases, \\\n",
        "a selection policy that focuses the computational resources on the important parts of the game tree is needed. Balances 2 factors: exploration of states that have had few playouts, and \\\n",
        "exploitation of states that have done well in past playouts to get more accurate estimate of their value. Steps are selection \\\n",
        "(choose move and repeat down the tree to leaf); expansion (grow search tree by generating new child of \\\n",
        "selected node, shows new node marked with 0/0); simulation (perform playout from newly generated child node, choosing moves for both players according to the playout policy, and moves \\\n",
        "are not recorded in the search tree); back-propagation (use result of simulation to update all the search tree nodes going up to the root). Repeat these for a set number of iterations, \\\n",
        "or until the allotted time has expired, and return the move with the highest number of playouts\n",
        "Effective selection policy is called “upper confidence bounds applied to trees”, or UCT. Policy ranks possible move based on an upper confidence bound formula called UCDB1\"\"\"\n",
        "chapter5_5 = \"\"\"Stochastic games invokes the unpredictability of real life y including a random element, such as the throwing of dice (backgammon is  a good example: combines luck and skill). \\\n",
        "Chance nodes are present in stochastic games in addition to max and min nodes. Positions dont have definite minimax values--we can only calculate the expected value of a position, which is the \\\n",
        "average over all possible outcomes of the chance nodes. Expectiminimax value: for games with chance nodes, this is a generalization of the minimax value for deterministic games. Terminal \\\n",
        "max and min work the same except that legal moves for max and min are dependent on the outcome of the dice roll in the previous chance node. For chance nodes: compute expected value = \\\n",
        "sum of the value over all outcomes, weighted by the probability of each chance action. Eval function for games of chance must return values that are a positive linear transformation of \\\n",
        "the probability of winning. The relation to probability is an important and general property of situations in which uncertainty is involved, and big oh of xpectiminimax = O(b^m*n^m), \\\n",
        "where n is the number of distinct rolls.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"Decision theory: deals with choosing among actions based on the desirability of their immediate outcomes; the environment is assumed to be episodic. The agent’s preferences \\\n",
        "are captured by a utility function, which assigns a single number to express the desirability of a state. Expected utility of an action given the evidence, EU(a) = average utility value of the \\\n",
        "outcomes weighted by the probability that the outcome occurs. MEU: maximum expected utility - a rational agent should choose the action that maximizes the agent’s expected utility, and action \\\n",
        "= argmax EU(a). This formalizes the general notion that an intelligent agent should “do the right thing”, but does not operationalize that advice\n",
        "Decision theory provides the beginnings of a basic mathematical framework general enough to define the AI problem\n",
        "MEU principle’s central justification is that if an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest \\\n",
        "possible performance score (averaged over all the possible environments). The performance measure gives a score for a history--a sequence of states. This is applied retrospectively after an \\\n",
        "agent completes a sequence of actions\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"Constraints on rational preferences are lottery (set of outcomes for each action when there is uncertainty about what is being offered); outcome of lottery (atomic state or another lottery). \\\n",
        "Primary issue for utility theory is to understand how preferences between complex lotteries are related to preferences between the underlying states in those lotteries. There are six constraints to address \\\n",
        "this issue: orderability (given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable--agent cannot avoid deciding); transitivity (given any three lotteries, \\\n",
        "if an agent prefers A to  B and prefers B to C, then the agent prefers A to C); continuity (if some lottery B is between A and C in preference, then some probability p exists for which the rational agent \\\n",
        "will be indifferent between getting B for sure and the lottery that yields A w/probability p and C w/probability 1 - p); substitutability (if agent is indifferent between lotteries A and B, then the agent \\\n",
        "is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them); monotonicity (two lotteries A and B have the same outcomes--if agent prefers A to B, \\\n",
        "then the agent must prefer the lottery that has a higher probability for A); decomposability (compound lotteries can be reduced to simpler ones using the laws of probability)\n",
        "No fun in gambling rule, and rational preferences lead to utility\n",
        "Existence of utility function checks if agent’s preferences obey the axioms of utility, then there is a function such that U(A) > U(B) iff A is preferred to B and U(A) = U(B) \\\n",
        "iff agent is indifferent between A and B. The expected utility of a lottery is the sum of the probability of each outcome times the utility of that outcome. Value function/ordinal utility function: an \\\n",
        "agent needs only a preference ranking on states and the numbers don’t matter\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"Utility functions look at preference elicitation, which presents choices to human and using the observed preferences to pin down underlying utility function. Given a utility scale, \\\n",
        "it’s possible to assess the utility of any particular prize S by asking the agent to choose between S and a standard lottery. Probability p is adjusted until the agent is indifferent between S and the \\\n",
        "standard lottery. The value of a statistical life is the value that is assigned to a life. A micromort is a one in a million chance of death. QALY: quality-adjusted life year -- people accept a shorter \\\n",
        "life expectancy to avoid a disability. Utility of money: monotonic preference for money, meaning that agent prefers more money to less, all other things being equal.\n",
        "Some qualities of risk include: risk-averse, risk seeking, certainty equivalent (value an agent will accept in lieu of a lottery), instance premium (difference between EMV of a lottery and \\\n",
        "its certainty equivalent). An agent with a linear curve is risk-neutral. The expected utility and post-decision disappointment are determined by order statistic (distribution of any particular \\\n",
        "ranked element of a sample) and optimizer’s curse (tendency for estimated expected utility of the best choice to be too high).\n",
        "Human judgment and irrationality are implemented by decision theory/normative theory, which describes how a rational agent should act. Descriptive theory describes how actual agents really do act. \\\n",
        "One explanation for the apparently irrational preferences is the certainty effect; people are strongly attracted to gains that are not certain. Framing effect is the wording of a decision problem \\\n",
        "having an impact on the agent’s choices. Evolutionary psychology\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"planning\" : \"sequences of actions\",    \n",
        "\"Move\" : \"both players have taken an action--ply brings us one level deeper into a game\",\n",
        "\"Killer moves\" : \"best moves--trying to find them first is called the killer move heuristic\",\n",
        "\"Ambiguity aversion\" : \"people elect the known probability rather than the unknown unknowns\",\n",
        "\"Anchoring effect\" : \" given expensive option and a cheaper (not cheap) option so users will go for less expensive option\" \n",
        "}\n",
        "\n"
      ],
      "execution_count": 27,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2612
        },
        "outputId": "02e360f5-3ccb-41c9-dd40-9af7a6f01846"
      },
      "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": 28,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nWhat is search for? Assumptions about the world: a single agent, deterministic actions, fully observed state, discrete state space. Path to goal is the important thing (paths have various costs, depths), and heuristics give problem-specific guidance. Identification is assignments to variables, and the oal itself is important, not the path.\nAll paths are at the same depth (for some formulations), and CSPs are specialized for identification problems\nCSPs represent the constraints that solutions must satisfy in a uniform declarative language. It must find solutions by general purpose search algorithms with no changes from problem to problem. There are no hand-build transition functions and no hand-built heuristics. We specify the problem in a formal declarative language, and a general-purpose algorithm does everything else\nCSP consists of a finite set of variables; a nonempty domain of possible values for each variable where D1, D2, Dn where Di = {v1, ..., vk}; a finite set of constraints (C2, C2, ..., Cm) where each constraint Ci limits the values that variables can take. A state is defined as an assignment of values to some or all variables, and a consistent assignment does not violate the constraints\nAssignment is complete when every variable is assigned a value: solution to a CSP is a complete, consistent, assignment and can be found.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nMinimax search: derived as solution for nondeterministic planning problems; desirable outcome must be guaranteed no matter what the “other side” does and is for games with multiple score outcomes. Optimal strategy given a game tree determined by working out the minimax value of each state n the tree. The minimax value of a terminal state = utility. Minimax is the utility of being in that state (for MAX), assuming that both players play optimally from there to the end of the game. It is a recursive algorithm that proceeds all the way down to the leaves of tree and backs up the minimax values through the tree as the recursion unwinds. It performs a complete depth-first exploration of the game tree. If max depth of the tree is m and there are b legal moves at each point, then the time-complexity of the minimax algorithm is O(b^m). Space complexity is O(bm) for an algorithm that generates all actions, or O(m) for one that generates actions one at a time (not good for games like chess).\nOptimal decisions in multiplayer games involves using a vector to replace single value for each node, and a utility function can return a vector of utilities\nAlpha-beta pruning uses pruning to get rid of large parts of the tree  that make no difference to the outcome. The value of root and minimax decision are independent of the values of the arbitrary leaves x, y, so they can be pruned. Consider a node n somewhere in the tree, such that a player has a chance of moving to n 1. If the  player has a better choice either at the same level, or any point higher up in the tree, player will never have to move to n. Minimax is depth-first, so we have to consider the nodes along a single path in the tree\nAlpha-beta pruning gets its name from the two extra params in MAX-VALUE, where alpha is the value of the best choice we have found at any choice point allong the path for max (alpha = at least) and beta is the value of the best (loweset value) choice we have found so for at any choice point along the path for MIN (beta = at most). It is O(b^m) such that branching becomes sqrt(b) instead of b\nIterative deepening searches one ply deep, record running of moves, then continue to go deeper.\nTranspositions are different permutations of the same move sequence that end up in the same position, and the problem can be addressed w/a transposition table that caches the heuristic values of states\nType A: considers all possible moves to a certain depth in the search tree and uses h(n) to estimate the utility of states at that depth -- wide but shallow\nType B:: ignores moves that look bad and follows promising lines as far as possible -- deep but narrow \nChess is A, and Go is B (higher branching factor)\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nHeuristic AB tree cuts off search early and apply h(n). Nodes become terminal, eval + cutoff test to cut search by the search depth and property of the state.\nMaterial value helps determine value of positions for eval functions (weighted linear function). Cutting off search checks if max depth reached and can lead to errors due to approximate nature of eval function (should only be applied to quiescent positions). Quiescence search is restricted to consider only certain types of moves, such as capture moves\nHorizon effect allows for singular extensions--clearly better move than all other moves in a given positions, even when the search would normally be cut off at that point\nForward pruning prunes moves that appear to be poor moves, but might possibly be good ones to save computation time at risk of making errors.\nBeam search: consider only a beam of the n best moves rather than all possible moves. ProbCut prunes nodes that are probably outside of the window. Late move reduction assumes that move ordering is done well and moves that appear later in the list are less likely to be good--this redueces depth of searched moves, saving time. If reduced search comes back w/value above current alpha, we can re-run the search with the full depth\nSearch vs lookup policy maps from every possible state to the best move in that state. The computer can play perfectly by lookup in the table constructed by retrograde minimax search.\nMCTS looks at value of state estimated as the average utility over a number of simulations of complete games starting from the state. Simulation/playout/rollout chooses moves first for one player, then for other, repeating until terminal position reached. Playout policy biases the moves towards good ones. Do N simulations from current state of game and track which moves has the highest win percentage. For stochastic games, this converges to optimal play as N increases, a selection policy that focuses the computational resources on the important parts of the game tree is needed. Balances 2 factors: exploration of states that have had few playouts, and exploitation of states that have done well in past playouts to get more accurate estimate of their value. Steps are selection (choose move and repeat down the tree to leaf); expansion (grow search tree by generating new child of selected node, shows new node marked with 0/0); simulation (perform playout from newly generated child node, choosing moves for both players according to the playout policy, and moves are not recorded in the search tree); back-propagation (use result of simulation to update all the search tree nodes going up to the root). Repeat these for a set number of iterations, or until the allotted time has expired, and return the move with the highest number of playouts\nEffective selection policy is called “upper confidence bounds applied to trees”, or UCT. Policy ranks possible move based on an upper confidence bound formula called UCDB1\n\n## AIMA Chapter 5.5 Stochastic Games\nStochastic games invokes the unpredictability of real life y including a random element, such as the throwing of dice (backgammon is  a good example: combines luck and skill). Chance nodes are present in stochastic games in addition to max and min nodes. Positions dont have definite minimax values--we can only calculate the expected value of a position, which is the average over all possible outcomes of the chance nodes. Expectiminimax value: for games with chance nodes, this is a generalization of the minimax value for deterministic games. Terminal max and min work the same except that legal moves for max and min are dependent on the outcome of the dice roll in the previous chance node. For chance nodes: compute expected value = sum of the value over all outcomes, weighted by the probability of each chance action. Eval function for games of chance must return values that are a positive linear transformation of the probability of winning. The relation to probability is an important and general property of situations in which uncertainty is involved, and big oh of xpectiminimax = O(b^m*n^m), where n is the number of distinct rolls.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nDecision theory: deals with choosing among actions based on the desirability of their immediate outcomes; the environment is assumed to be episodic. The agent’s preferences are captured by a utility function, which assigns a single number to express the desirability of a state. Expected utility of an action given the evidence, EU(a) = average utility value of the outcomes weighted by the probability that the outcome occurs. MEU: maximum expected utility - a rational agent should choose the action that maximizes the agent’s expected utility, and action = argmax EU(a). This formalizes the general notion that an intelligent agent should “do the right thing”, but does not operationalize that advice\nDecision theory provides the beginnings of a basic mathematical framework general enough to define the AI problem\nMEU principle’s central justification is that if an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments). The performance measure gives a score for a history--a sequence of states. This is applied retrospectively after an agent completes a sequence of actions\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nConstraints on rational preferences are lottery (set of outcomes for each action when there is uncertainty about what is being offered); outcome of lottery (atomic state or another lottery). Primary issue for utility theory is to understand how preferences between complex lotteries are related to preferences between the underlying states in those lotteries. There are six constraints to address this issue: orderability (given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable--agent cannot avoid deciding); transitivity (given any three lotteries, if an agent prefers A to  B and prefers B to C, then the agent prefers A to C); continuity (if some lottery B is between A and C in preference, then some probability p exists for which the rational agent will be indifferent between getting B for sure and the lottery that yields A w/probability p and C w/probability 1 - p); substitutability (if agent is indifferent between lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them); monotonicity (two lotteries A and B have the same outcomes--if agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A); decomposability (compound lotteries can be reduced to simpler ones using the laws of probability)\nNo fun in gambling rule, and rational preferences lead to utility\nExistence of utility function checks if agent’s preferences obey the axioms of utility, then there is a function such that U(A) > U(B) iff A is preferred to B and U(A) = U(B) iff agent is indifferent between A and B. The expected utility of a lottery is the sum of the probability of each outcome times the utility of that outcome. Value function/ordinal utility function: an agent needs only a preference ranking on states and the numbers don’t matter\n\n\n## AIMA Chapter 16.3 Utility Functions\nUtility functions look at preference elicitation, which presents choices to human and using the observed preferences to pin down underlying utility function. Given a utility scale, it’s possible to assess the utility of any particular prize S by asking the agent to choose between S and a standard lottery. Probability p is adjusted until the agent is indifferent between S and the standard lottery. The value of a statistical life is the value that is assigned to a life. A micromort is a one in a million chance of death. QALY: quality-adjusted life year -- people accept a shorter life expectancy to avoid a disability. Utility of money: monotonic preference for money, meaning that agent prefers more money to less, all other things being equal.\nSome qualities of risk include: risk-averse, risk seeking, certainty equivalent (value an agent will accept in lieu of a lottery), instance premium (difference between EMV of a lottery and its certainty equivalent). An agent with a linear curve is risk-neutral. The expected utility and post-decision disappointment are determined by order statistic (distribution of any particular ranked element of a sample) and optimizer’s curse (tendency for estimated expected utility of the best choice to be too high).\nHuman judgment and irrationality are implemented by decision theory/normative theory, which describes how a rational agent should act. Descriptive theory describes how actual agents really do act. One explanation for the apparently irrational preferences is the certainty effect; people are strongly attracted to gains that are not certain. Framing effect is the wording of a decision problem having an impact on the agent’s choices. Evolutionary psychology\n\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Planning** - sequences of actions\n* **Move** - both players have taken an action--ply brings us one level deeper into a game\n* **Killer moves** - best moves--trying to find them first is called the killer move heuristic\n* **Ambiguity aversion** - people elect the known probability rather than the unknown unknowns\n* **Anchoring effect** -  given expensive option and a cheaper (not cheap) option so users will go for less expensive option\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 = \"\"\"Three components include X (set of variables), D (set of domains, one for each variable), C (set of constraints that specify allowable combinations of values). An arbitrary \\\n",
        "domain Di consists of a set of allowable values {v1,..,vk} for variable Xi. Each constraint Cj consists of a pair (scope, rel) where scope is a tuple of variables that participate in the constraint \\\n",
        "andrel is a relation that defines the values that those variables cann take on. Relation can mean an  explicit set of all tuples of values that satisfy the constraint, or function that can compute \\\n",
        "whether or not a tuple is a member of the relation. CSPs deal with assignments of values to variables\n",
        "Solution to a CSP should be a consistent, complete assignment. A partial assignment would be one that leaves some variables unassigned. A partial solution is a partial assignment that is consistent. Constraint \\\n",
        "graphs contain nodes that correspond to variables of the problem, and edge connects any two variables that participate in a constraint.\n",
        "Variations on the CSP formalism: simplest kind of CSP (discrete, finite domains). Discrete domains can be infinite, such as the set of integers or strings. Implicit constraints are needed rather than \\\n",
        "explicit tuples of values, and some special solution algos exist for linear constraints on integer variables. No algo exists for solving general nonlinear constraints on integer variables--problem is undecidable \\\n",
        "and constraint satisfaction problems with continuous domains are common (ex: scheduling of experiments on Hubble Space Telescope requires precise timing of observations--start and finish of each observation \\\n",
        "and maneuver are continuous-valued variables that must obey a variety of astronomical, precedence, and power constraints).\n",
        "Best-known continuous domain CSP is linear programming problems, where constraints must be linear equalities or inequalities. The simplest type of constraint is unary, which restricts the value of a single \\\n",
        "variable. Binary constraint relates two variables and binary CSP is one with only unary and binary constraints--can be represented as a constraint graph.\n",
        "Cryptarithmetic puzzles are ex of global constraints, and a constraint hypergraph has ordinary nodes and hypernodes (n-ary constraints/constraints involving n variables)\n",
        "Dual graph transformation: new graph in which there is one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables\n",
        "Preference constraint: allowable but not optimal solutions\n",
        "Constrained optimization problem: CSPs with preferences can be solved w/optimization search methods (path-based or local)\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"Constraint propagation: using constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, etc. The key is local consistency \\\n",
        "such that each variable = node and binary constraint = edge, then the process of enforcing local consistency in eeach part of the graph causes inconsistent values to be eliminated throughout the graph.\n",
        "Node-consistency is when a variable whose values in its domain satisfy the variable’s unary constraints. The variable is arc-consistent if every value in its domain satisfies the variable’s binary constraints. \\\n",
        "Path consistency occurs when binary constraints are tightened by using implicit constraints inferred by looking at triples of variables. K-consistency is the stronger forms of propagation such that \\\n",
        "for any set of k - 1 variables and any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. CSP is strongly k-consistent if it is k-consistent and \\\n",
        "(k-1)-consistent...1-consistent.\n",
        "Resource constraint is atmost constraint. It detects inconsistencies by checking sum of the min values of the current domains. It has bounds propagation and is bounds-consistent such that for every \\\n",
        "variable X and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"Backtracking search for CSPs looks at commmutativity, the order of application of any given set of actions does not matter. Degree heuristic attempts to reduce branching factor on \\\n",
        "future choicesby selecting the variable that is involved in the largest number of constraints on other unassigned variables. Least-constraining-vluae heuristic picks the value that rules out the \\\n",
        "fewest choices for the neighboring variables in the constraint graph is preferred. Forward checking establishes arc consistency when variable X is assigned.\n",
        "For each unassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value that is inconsistent w/value chosen for X\n",
        "MAC (maintaining arc consistency) detects inconsistencies\n",
        "Intelligent backtracking is looking backtracking, while chronological backtracking is the most recent deciiosn point is revisited.\n",
        "Conflict set contains assignments that are in conflict with some vlue for SA\n",
        "Conflict-directed backjumping involves backjumping algorithm that uses conflict sets to skip around\n",
        "Set of variables + corresponding values are no-good\"\"\"\n",
        "chapter6_4 = \"\"\"Local searches for CSPs involve ini-conflicts heuristic, which selects the value that results in the minimum number of conflics with other variables. Tabu search keeps a small \\\n",
        "list of recently visited states and forbidding the algorithm to return to those states, and constraint weighting concentrates the search on the important constraints.\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"Independent subproblems are unrelated problems that yield a solution. Connected components are connected parts of a constraint path--independence can be derived from this information. \\\n",
        "Trees are constraint graph when any two variables are connected by only one path. Any tree-structured CSP can be solved in time linear in the number of variables.\n",
        "Directional arc consistency (DAC) means that if for every Xi, it’s arc-consistent with each Xj for j > i\n",
        "Topological sort checks arbitrary variable is root, and ordering of the variables such that each variable appears after its parent\n",
        "Tree decomposition is the transformation of original graph into a tree where each node in the tree consists of a set of variables. Every variable in the original problem appears in at least one of the tree nodes \\\n",
        "and if two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. Also, if a variable appears in two nodes in \\\n",
        "the tree, it must appear in every node along the path connecting those nodes. The min tree weight is the min width among all tree decompositions. CSPs with constraint graphs of bounded tree width are solvable \n",
        "in polynomial time. Value symmetryis the S=symmetry-breaking constraint to reduce search space.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"consistent/legal assignment\" : \"one that does not violate any constraints\",    \n",
        "\"Complete assignment\" : \"one in which every variable is assigned a value\",\n",
        "\"Precedence constraints\" : \" between individual tasks, we can say some tasks must occur before others, etc.\",\n",
        "\"disjunctive constraints\" : \"constraint that certain tasks may not overlap in time--either one comes first or the other does\",\n",
        "\"global constraint\" : \"constraint involving an arbitrary number of variables\", \n",
        "\"Constraint learning\": \"finding a minimum set of variables from the conflict set that causes the problem\"\n",
        "}\n"
      ],
      "execution_count": 29,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1612
        },
        "outputId": "2a979ca5-092a-412c-8c32-d7e7df4a5628"
      },
      "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": 30,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nThree components include X (set of variables), D (set of domains, one for each variable), C (set of constraints that specify allowable combinations of values). An arbitrary domain Di consists of a set of allowable values {v1,..,vk} for variable Xi. Each constraint Cj consists of a pair (scope, rel) where scope is a tuple of variables that participate in the constraint andrel is a relation that defines the values that those variables cann take on. Relation can mean an  explicit set of all tuples of values that satisfy the constraint, or function that can compute whether or not a tuple is a member of the relation. CSPs deal with assignments of values to variables\nSolution to a CSP should be a consistent, complete assignment. A partial assignment would be one that leaves some variables unassigned. A partial solution is a partial assignment that is consistent. Constraint graphs contain nodes that correspond to variables of the problem, and edge connects any two variables that participate in a constraint.\nVariations on the CSP formalism: simplest kind of CSP (discrete, finite domains). Discrete domains can be infinite, such as the set of integers or strings. Implicit constraints are needed rather than explicit tuples of values, and some special solution algos exist for linear constraints on integer variables. No algo exists for solving general nonlinear constraints on integer variables--problem is undecidable and constraint satisfaction problems with continuous domains are common (ex: scheduling of experiments on Hubble Space Telescope requires precise timing of observations--start and finish of each observation and maneuver are continuous-valued variables that must obey a variety of astronomical, precedence, and power constraints).\nBest-known continuous domain CSP is linear programming problems, where constraints must be linear equalities or inequalities. The simplest type of constraint is unary, which restricts the value of a single variable. Binary constraint relates two variables and binary CSP is one with only unary and binary constraints--can be represented as a constraint graph.\nCryptarithmetic puzzles are ex of global constraints, and a constraint hypergraph has ordinary nodes and hypernodes (n-ary constraints/constraints involving n variables)\nDual graph transformation: new graph in which there is one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables\nPreference constraint: allowable but not optimal solutions\nConstrained optimization problem: CSPs with preferences can be solved w/optimization search methods (path-based or local)\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nConstraint propagation: using constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, etc. The key is local consistency such that each variable = node and binary constraint = edge, then the process of enforcing local consistency in eeach part of the graph causes inconsistent values to be eliminated throughout the graph.\nNode-consistency is when a variable whose values in its domain satisfy the variable’s unary constraints. The variable is arc-consistent if every value in its domain satisfies the variable’s binary constraints. Path consistency occurs when binary constraints are tightened by using implicit constraints inferred by looking at triples of variables. K-consistency is the stronger forms of propagation such that for any set of k - 1 variables and any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. CSP is strongly k-consistent if it is k-consistent and (k-1)-consistent...1-consistent.\nResource constraint is atmost constraint. It detects inconsistencies by checking sum of the min values of the current domains. It has bounds propagation and is bounds-consistent such that for every variable X and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nBacktracking search for CSPs looks at commmutativity, the order of application of any given set of actions does not matter. Degree heuristic attempts to reduce branching factor on future choicesby selecting the variable that is involved in the largest number of constraints on other unassigned variables. Least-constraining-vluae heuristic picks the value that rules out the fewest choices for the neighboring variables in the constraint graph is preferred. Forward checking establishes arc consistency when variable X is assigned.\nFor each unassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value that is inconsistent w/value chosen for X\nMAC (maintaining arc consistency) detects inconsistencies\nIntelligent backtracking is looking backtracking, while chronological backtracking is the most recent deciiosn point is revisited.\nConflict set contains assignments that are in conflict with some vlue for SA\nConflict-directed backjumping involves backjumping algorithm that uses conflict sets to skip around\nSet of variables + corresponding values are no-good\n\n## AIMA Chapter 6.4 Local Search for CSPs\nLocal searches for CSPs involve ini-conflicts heuristic, which selects the value that results in the minimum number of conflics with other variables. Tabu search keeps a small list of recently visited states and forbidding the algorithm to return to those states, and constraint weighting concentrates the search on the important constraints.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\nIndependent subproblems are unrelated problems that yield a solution. Connected components are connected parts of a constraint path--independence can be derived from this information. Trees are constraint graph when any two variables are connected by only one path. Any tree-structured CSP can be solved in time linear in the number of variables.\nDirectional arc consistency (DAC) means that if for every Xi, it’s arc-consistent with each Xj for j > i\nTopological sort checks arbitrary variable is root, and ordering of the variables such that each variable appears after its parent\nTree decomposition is the transformation of original graph into a tree where each node in the tree consists of a set of variables. Every variable in the original problem appears in at least one of the tree nodes and if two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. Also, if a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. The min tree weight is the min width among all tree decompositions. CSPs with constraint graphs of bounded tree width are solvable \nin polynomial time. Value symmetryis the S=symmetry-breaking constraint to reduce search space.\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Consistent/legal assignment** - one that does not violate any constraints\n* **Complete assignment** - one in which every variable is assigned a value\n* **Precedence constraints** -  between individual tasks, we can say some tasks must occur before others, etc.\n* **Disjunctive constraints** - constraint that certain tasks may not overlap in time--either one comes first or the other does\n* **Global constraint** - constraint involving an arbitrary number of variables\n* **Constraint learning** - finding a minimum set of variables from the conflict set that causes the problem\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 = \"\"\"Knowledge base is a set of sentences in which each sentence is expressed in knowledge representation language and reps some assertion about the world. An axio mis a setence taken \\\n",
        "as being given without being derived from other sentences. Tell and Ask are operations to query and add what si known. These involve inference (derive new sentecne from old). Agent maintains a knowledge base \\\n",
        "that initially may contain background knowledge. Each time the agent program is called, it TELLS the knowledge base the percept. Then, it ASKS the knowledge base for the action. Then, the agent program TELLS \\\n",
        "the knoweldge base what action was chosen and return action to be executed (done by make-percept-sentence, make-action-query, make-action-sentence). Inference is hidden in ASK and TELL. We also need to specify \\\n",
        "a knowledge level for the agent. Analyses are disjoint from implementation level.\n",
        "Declarative approach is when the agent designer can TELL one by one until agent knows how to act. Procedural approach encodes desired behaviors directly in the program code.\"\"\"\n",
        "chapter7_2 = \"\"\"Wumpus World is cave with gold, pits, etc. Performance measure is reward for action. Environment is the grid of rooms. Actuators is the player moving square to square and actions it can make. \\\n",
        "The sensors can register stenches, breezes, bump, etc.\"\"\"\n",
        "chapter7_3 = \"\"\"Logic must define semantics of setneces. Semantics define truth of setences with respect to possible worlds (model/mathematical abstractions of environments). m satisfies a/m is a model of a if \\\n",
        "a is true in model m. M(a) is the set of all models of a.\n",
        "Logical reasoning is the logical entailment between sentences such that a sentence follows logically from another sentence (|=), aka a entails B when a |= B, or M(a) subset of M(B). Logical inference derives \\\n",
        "conclusions by applying entailment. Inference algorithm model checking checks all possible models to see that a is true in allm odels in which KB is true such that M(KB) subset of M(a). Sound or truth-preserving \\\n",
        "inference algorithm dervies only entailed sentences. Completeness is also desriable (derive any entailed sentence). \"\"\"\n",
        "chapter7_4 = \"\"\"Atomic sentences = single propositional symbol (can be true or false). Complex sentences are constructed from simpler sentences with parentheses and logical connectives (5 common are not, literal \\\n",
        "and, or, and implies. Implications are made of precedents/antecedents and conclusions/consequents. Same as rules or if-then statements. Literals are atomic sentences or negated atomic sentences.\n",
        "Truth values are set for every porposition symbol in the set of values. There are five following rules for complex sentences: not P is true iff P is false in m; P and Q is true iff P and Q are true in m; \\\n",
        "P or Q is true iff eiteher P or Q is true; P implies Q is ture unless P is true and Q is false in m; P implies Q and Q implies P are true iff P and Q both true or both false in m.\n",
        "Truth tables can also specify each truth value of a complex sentence.\"\"\"\n",
        "chapter7_5 = \"\"\"Propositional theorem proving applies rules of inference to sentences in our knowledge base to construct proof of desired sentence w/o consulting models. Concepts relating to entailment are \\\n",
        "logical equivalence (two true sentences in m represented by triple =); validity (sentence is true in all models), where valid setnences are called tautologies (necessariliy true), useful in deduction theorems; \n",
        "and satisfiability, where sentences are true if satisfied by some model. We can prove B from a by reductio ad absurdum or refutation/proof by contradiction.\n",
        "Some rules include Modus Ponens, meaning whenever sentences a=>B and a are given, sentence B can be inferred (a => B, a / B). Another rule is And-elimnation, which a ^ B / a.\n",
        "We can also prove by resolution, which finds a complete inference algorithm when coupled with a complete search algorithm. RC(S) is resolution closure to compute final value of variable clauses. Completenesss \\\n",
        "theorem for resolution in propositional logic is called ground resolution theorem, such that if a set of clauses is unsatisfiable, the resolution closure of those clauses contains the empty clause.\n",
        "Definite clauses are a disjunction of literalsof which one is positive. The Horn clause is a disjunction of literals of which at most one is positive. All definite clauses are Horn clauses, as are \\\n",
        "clauses with no positive literals (goal clauses). These are closed.\n",
        "Knowledge bases contain only definite clauses because 1. every definite clause can be written as an implication w/premise as a conjunction of positive literals and whose conclusion is a single positive literal. \\\n",
        "Horn form: premise is body and conclusion is head and sentence has a single positive literal called fact. 2. forward-chaining + backward-chaining algorithm done to infer with Horn clauses (logic programming). \\\n",
        "3. entailment with Horn in linear time in size of knowledge base. Forward-chaining is sound and complete. Forward chaining is also data-driven reason-derived. Backward chaining is a form of goal-directed reasoning \\\n",
        "good for questions in relation to relevant facts.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1255
        },
        "outputId": "9e81b318-350a-481e-9373-abe7acb66d9c"
      },
      "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": 32,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nKnowledge base is a set of sentences in which each sentence is expressed in knowledge representation language and reps some assertion about the world. An axio mis a setence taken as being given without being derived from other sentences. Tell and Ask are operations to query and add what si known. These involve inference (derive new sentecne from old). Agent maintains a knowledge base that initially may contain background knowledge. Each time the agent program is called, it TELLS the knowledge base the percept. Then, it ASKS the knowledge base for the action. Then, the agent program TELLS the knoweldge base what action was chosen and return action to be executed (done by make-percept-sentence, make-action-query, make-action-sentence). Inference is hidden in ASK and TELL. We also need to specify a knowledge level for the agent. Analyses are disjoint from implementation level.\nDeclarative approach is when the agent designer can TELL one by one until agent knows how to act. Procedural approach encodes desired behaviors directly in the program code.\n\n## AIMA Chapter 7.2 The Wumpus World\nWumpus World is cave with gold, pits, etc. Performance measure is reward for action. Environment is the grid of rooms. Actuators is the player moving square to square and actions it can make. The sensors can register stenches, breezes, bump, etc.\n\n## AIMA Chapter 7.3 Logic\nLogic must define semantics of setneces. Semantics define truth of setences with respect to possible worlds (model/mathematical abstractions of environments). m satisfies a/m is a model of a if a is true in model m. M(a) is the set of all models of a.\nLogical reasoning is the logical entailment between sentences such that a sentence follows logically from another sentence (|=), aka a entails B when a |= B, or M(a) subset of M(B). Logical inference derives conclusions by applying entailment. Inference algorithm model checking checks all possible models to see that a is true in allm odels in which KB is true such that M(KB) subset of M(a). Sound or truth-preserving inference algorithm dervies only entailed sentences. Completeness is also desriable (derive any entailed sentence). \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nAtomic sentences = single propositional symbol (can be true or false). Complex sentences are constructed from simpler sentences with parentheses and logical connectives (5 common are not, literal and, or, and implies. Implications are made of precedents/antecedents and conclusions/consequents. Same as rules or if-then statements. Literals are atomic sentences or negated atomic sentences.\nTruth values are set for every porposition symbol in the set of values. There are five following rules for complex sentences: not P is true iff P is false in m; P and Q is true iff P and Q are true in m; P or Q is true iff eiteher P or Q is true; P implies Q is ture unless P is true and Q is false in m; P implies Q and Q implies P are true iff P and Q both true or both false in m.\nTruth tables can also specify each truth value of a complex sentence.\n\n## AIMA 7.5 Propositional Theorem Proving\nPropositional theorem proving applies rules of inference to sentences in our knowledge base to construct proof of desired sentence w/o consulting models. Concepts relating to entailment are logical equivalence (two true sentences in m represented by triple =); validity (sentence is true in all models), where valid setnences are called tautologies (necessariliy true), useful in deduction theorems; \nand satisfiability, where sentences are true if satisfied by some model. We can prove B from a by reductio ad absurdum or refutation/proof by contradiction.\nSome rules include Modus Ponens, meaning whenever sentences a=>B and a are given, sentence B can be inferred (a => B, a / B). Another rule is And-elimnation, which a ^ B / a.\nWe can also prove by resolution, which finds a complete inference algorithm when coupled with a complete search algorithm. RC(S) is resolution closure to compute final value of variable clauses. Completenesss theorem for resolution in propositional logic is called ground resolution theorem, such that if a set of clauses is unsatisfiable, the resolution closure of those clauses contains the empty clause.\nDefinite clauses are a disjunction of literalsof which one is positive. The Horn clause is a disjunction of literals of which at most one is positive. All definite clauses are Horn clauses, as are clauses with no positive literals (goal clauses). These are closed.\nKnowledge bases contain only definite clauses because 1. every definite clause can be written as an implication w/premise as a conjunction of positive literals and whose conclusion is a single positive literal. Horn form: premise is body and conclusion is head and sentence has a single positive literal called fact. 2. forward-chaining + backward-chaining algorithm done to infer with Horn clauses (logic programming). 3. entailment with Horn in linear time in size of knowledge base. Forward-chaining is sound and complete. Forward chaining is also data-driven reason-derived. Backward chaining is a form of goal-directed reasoning good for questions in relation to relevant facts.\n\n## Module 7 Lecture Notes\n Your summary here \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": 10795
        },
        "id": "T3cm1WV542_a",
        "outputId": "d98a41e9-5a8e-4611-8625-a34446c5418d"
      },
      "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": 33,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nSchools of thought: human vs rational + thought vs behavior. 2 ways to measure intelligence: empirical science w/observations + hypotheses about human behavior and thought process, or a rationalist approach combining math + engineering w/statistics, control theory, economics.\nTuring test approach: acting humanly - TTT: natural language processing for successful communication, knowledge representation to store info, automated reasoning to draw conclusions, machine learning to adapt + learn + find patterns. TTT also requires interaction w/objects and people in the real world, requiring: computer vision + speech recognition, and robotics to manip objects + move around.\nThinking humanly - cognitive model approach: can learn about humans through introspection, psychological experiments, brain imaging. Precise theory of mind -- possible to express mind as a computer program. When program's in-out behavior matches corresponding human behavior, there is evidence that the program's mechanisms can also operate in humans. Cog. model more concerned w/comparing sequence + timing of reasoning steps to those of human subjects solving the same problems (models from AI + experimental techniques from psychology to construct precise + testable theories of the human mind). This is separated from schools of thought that algos perform well on tasks = good model of human performance, as separation leads to cohesion.\nThinking rationally: \"laws of thought\" approach, influenced by Aristotle and \"right thinking\". Syllogisms provide patterns for argument structures that yield \"correct\" conclusions, which are notations for statements about objects and relationships between objects. Logic requires knowledge the world that is certain - theory of probability fills in gap of uncertainty, allowing for construction of rational thought (does generate rational behavior, which requires rational action).\nActing rationally: rational agent approach (act to achieve the best outcome). Skills needed for Turing test also allow an agent to act rationally - knowledge representation and reasoning enable agents to reach good decisions aka learning for functionality. Two advantages over other approaches are that it's more general than “laws of thought” approach: correct inference is just one of many mechanisms for achieving rationality, and it's more amenable to scientific development: mathematically defined and general. Standard model: study and construction of agents that do the right thing. Issue of limited rationality arises: acting appropriately when there is not enough time to do all the computations. \nBeneficial machines address that the standard model assumes that we will supply a fully specified objective to the machine. Tradeoffs with unexpected circumstances? Can't just always have one goal in mind. Value alignment problem deals w/achieving agreement between our true preferences and objective we put into the machine--those put into machine must align with human's.\n\n## AIMA Chapter 27.1 The Limits of AI\nWeak AI is the idea that machines could act as if they were intelligent. Strong AI is the assertion that machines are actually consciously thinking (not simulating thinking/human-level AI or general AI). Turing’s argument from informality: human behavior is far too complex to be captured by formal sets of rules. Humans must be using some informal guidelines that could never be captured in a formal set of rules and thus could never be codified in computer programs (according to Turing). Good Old-Fashioned AI: AI pursued in computational terms (GOFAI). Qualification problem: difficulty of capturing every contingency of appropriate behavior in a set of necessary and sufficient logical rules. Embodied cognition approach: brain is part of the body--it is thus embedded in an environment and should not be considered separately. Need to study the system as a whole: brain’s functioning exploits regularities in its environment: robotics, vision, sensory experiences are central.\nThe argument from disability: machine can never do X. Turing’s examples: be kind, resourceful, friendly, enjoy ice cream, fall in love, etc., so they can’t be exactly human. The mathematical objection between Turing and Godel is that certain mathematical questions are in principle unanswerable by particular formal systems. Godel’s incompleteness theorem:\nG(F) is a sentence of F, but cannot be proved within F\nIf F is consistent, then G(F) is true\nLucas: theorem shows that machines are inferior to humans bc formal systems are limited by the incompleteness theorem and cannot establish the truth of their own Godel sentence, while humans don’t have this limitation but this statement has problems. Agent should not be ashamed that it cannot establish the truth while other agents can. Ex: “Lucas can’t consistently assert that this sentence is true.”, but if he asserts this sentence, he contradicts himself. There is already a true sentence that Lucas cannot assert while other people/machines can, but we don’t think less of Lucas.\nGodel’s incompleteness theorem and results apply to math and not to computers. No entity (human or machine) can prove things that are impossible to prove. Godel’s incompleteness theorem only applies to formal systems that are powerful enough to do arithmetic. This includes Turing machines, and Lucas assumes all machines are equivalents to Turing machines. Turing machines are infinite, whereas computers and brains are finite, and any computer can be described as a system in proposition logic, which is not subject to Godel’s incompleteness theorem. Humans can change their minds but so could machines after further deliberation with new info; upgrades in hardware; changes in its decision-making processes w/machine learning or software rewriting. We measure AI with Turing test, but no well-trained judge has been fooled yet. Point isn’t to fool judges, it’s to provide useful functionalities.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nCan Machines Really Think? The polite convention: assumption that systems are intelligent\nThe Chinese Room: John Searle rejecting the polite convention. No one in the room understands Chinese--they’re just following the rule book (which also does not understand Chinese, but spells out conventions), therefore the people don’t understand Chinese. \nProponent of biological naturalism--mental states are high-level features caused by low-level physical processes in the neurons, and it’s the properties of the neurons that matter. Neurons have “it” and transistors do not. Consciousness: awareness of the outside world, and of the self, and the subjective experience of living. Qualia: intrinsic nature of experiences. Can machines have qualia? Turing: interested in creating programs that behave intelligently, while aspects of consciousness (awareness) can be programmed and part of an intelligent machine\n\n\n## AIMA 2.1 Agents and Environments\nFour views of AI: thinking humanly, thinking rationally, acting humanly, acting rationally. An agent: anything that can perceive its environment and act on it. Sensors perceive the environment using these. Actuators allow the agent to act on its environment. Percept is agent’s perceptual inputs at any given instance. Vector of all inputs received from sensors. Agent functions map vector of inputs to an output action. This model of inputs to map of outputs can change over time depending on whether the environment is fully observable and depends on environment’s behavior--deterministic or stochastic (randomly determined)\nAgent program runs the physical architecture to produce the function. The agent = architecture + program. Easiest solution: lookup table of sorts for sequence P (sequence of percepts) to action a. This problem is exponential length of P and is too difficult to explicitly enumerate every possibility--solution: more sophisticated algorithms.\nAgent is generic and is anything that can be viewed as perceiving its actions through sensors; acting upon that environment using actuators. This can be humans, robots, software, thermostats, etc.\nRational agent perceives its environment and behaves rationally/does the right thing. Consequentialism: evaluate the behavior of an agent/person based on the consequences of the actions it takes. We want only desirable consequences. This definition does not require omniscience (like predicting something bad before it happens, like freak accidents).\nRational choice theory (Herbert Simon) states that agents can only make decisions based on the info available to them. They have their own preferences and opinions that create bias in behavior. There is no singular right choice with limited computational ability.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nPerformance measure is an object criterion for success of an agent’s behavior given the evidence provided by the percept sequence. Did the agent take the right action to maximize performance? Better to measure this by whether the performance you want from the agent is achieved, rather than how you think the agent should behave.\nRational agent (redefined): for each possible percept sequence P, a rational agent selects action a that maximizes the expected value of the performance measure. rationality != omniscience. In actuality, computational limitations make complete rationality unachievable.\n\n\n## AIMA 2.3 The Nature of Environments\nTask environment: problem specification for which a rational agent is the solution. PEAS: to specify a task environment include performance measure, environment, actuators, sensors. Rational agent designer goals when given a PEAS task environment include abstract mathematical description: construct agent function f that gets the maximum expected value of performance measure; concrete implementation in which we design agent program that implements f on a particular architecture.\nTask environments are fully observable or partially observable. They describe task environments (for ex, a chess board is fully observable, while a elf driving car’s environment is partially observable). They are deterministic vs non deterministic vs stochastic (probabilistic); chess vs someone liking chocolate vs wheel of fortune. They are also episodic vs sequential, where episodic means the agent needs to process self-contained episodes and then performs a single action and choice of action is not dependent on previous action. In sequential environments, agents plan multiple steps ahead to determine the next best step. They are static vs dynamic (crossword puzzle vs self-driving car). They are discrete vs continuous, where there is a discrete number of distinct states in discrete environments, and have a finite set of actions. Continuous environments are ones that can go through a continuous range of values smoothly over time. Thy are single agent vs multi agent, where ulti agent environments are deterministic but need to take other agents (players in games) into account.\nWhen is something considered an agent? The thing’s behavior can be described as having its own performance measure. Telephone pole is environment and another car is an agent. Hardest environment is continuous, partially observable, stochastic, multiagent. For example, a self-driving car would be an agent. Simple task environments are static, fully observable, deterministic, discrete.\n\n\n## AIMA 2.4 The Structure of Agents\nAn agent = architecture + program. There is a lookup table (map) that maps certain input to behavior output (table-driven-agent function). A key challege for AI is to find out how to design programs that produce rational behavior from a small program rather than table--should be able to make determinations. 4 agent programs embody the principles underlying all intelligent systems: simple reflex, model-based reflex, goal-based, and utility-based. \nSimple reflex agents selection actions based on the current percept and ignore the previous percept history (ex: vacuum). These behaviors occur in more complex environments often. They implement a condition-action rule, written as if-then statements. \nModel-based reflex agents handle partial observability by keeping track of the part of the world it can't see now. It maintains an internal state dependent on percept history and reflects some of the unobserved aspects of the current state. Updating state requires two kinds of knowledge: info about how the world changes over time (effects of agents's actions + how the world evolves independntly of the agent/transition model of the world), and info about how state of the world is reflected in percepts (using sensor models).\nGoal-based agents require goal information (describes desirable outcomes). Agent program combines with this model to choose actions to achieve that desirable goal. Search and planning are fields in AI that help determine action sequences to achieve agent goals.\nUtility-based agents make decisions and chooses between actions based on how happy it'd make the agent. Agent has a utility function that internalizes such performance measures for each environment, allowing the agent to maximize its utility on that state. Conflicting goals lead to tradeoffs and several uncertain goals exist means utility can help measure a greater likelihood of success (vs importance of goals). Learning agents can be divided into four components: the learning element (makes improvements), the performance element (responsible for selecting external actions), the critic (determines performanc element), the problem generator (which suggets actions that lead to new + informative experiences). Performance standard must determine a percept as a reward or penatly and provides feedback to the agent about its behavior.\nFactored representations split up states into variables and attributes, and each have a value (fixed). We can also have structured representations, which objects and their various/varying relationships are defined explicitly. These representations lie along an axis of increasing expressiveness, and more expressive representation is more detailed and concise (reasoning + learning are more complex). Another axis for representation is mapping of concepts to locations in memory--localist representation. When memory location is spread out for a representation of a concept = a distributed representation.\n\n## Module 1 Lecture Notes\n Your summary here \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\nStrings + tuples (which can be mixed type) are immutable (have to reassign as with Java). We use Is to check pointer in memory vs == for the same value. Lists are mutable and we can use Y = x[:] to get and assign a shallow copy. Python 3 strings: Unicode (vs 8-bit in the past). Slicing is inclusive, exclusive.\nFor lists, sorted(list) needs to be reassigned, while li.sort() sorts in place (no need to reassign)\nFor dicts, values can be reassigned, cannot do lookup by value\nFor functions: no declaration of arg or return types, and can return multiple values as a tuple.\nNo function overloading in Python (whereas Java can have multiple functions w/the same name), but operator overloading is possible when implementing a class.\nWe can provide default values for arguments--these are optional arguments when function is called. Non default arguments should precede default arguments. Keyword arguments are arguments that can be called out of order if specified when called. *args allows functions to accept a variable num of non-keyword arguments, **kwargs same but keyword arguments\nDynamic scope: takes the most value for the variable.\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\nFor problem-solving agents, unknown environments mean uninformed decisions--> all possibilities must be explored. In four-phase problem solving we require goal formulation (agent adopts a goal such that goal limits objective and the actions to be considered); problem formulation (agent formulates description of the states and actions needed to achieve described states and goals; abstract model of the relevant part of the world); search (agent simulates sequences to find the one that is the solution (leads to the goal state) and either finds that there is or isn’t a solution); execution  (agent executes the actions in the solution, one at a time).\nIn fully observable, deterministic, known environments, there is always a solution to the problem that is a fixed sequence of events (or no solution). An open-loop system is when percepts of an agent are separated from the environment. This happens when a solution is found--an agent can execute the solution without further regarding its environment. It is generally safer to use a closed-loop solution, which allows agent to monitor its environment in case the model is incorrect or the environment is indeterministic.\nSearch problem definition is made of state space (set of possible states the environment can be in); initial state; goal state (can be one or more); actions(s): set of executable actions in s (the state space) where finite set of actions are applicable in s; ation cost function (determines the cost of a particular action in the state in a numeric form); path (set of actions) where a solution is a path from initial state to the goal state, and an optimal solution has the lowest cost from the initial to goal state; state space can be represented as a graph, where vertices are states and edges are actions.\nA model is a formulation of a problem. Abstractions are models of a problem with the fine details removed where the level of abstraction should be appropriate so that the user is able to understand  the instructions without being too overly detailed.\n\n\n## AIMA Chapter 3.2 Example Problems\nStandardized problem illustrates/exercises various problem solving methods and can be given in explicit terms and suitable for researchers to compare solutions and optimality in the algorithm. \nA real-world problem finds solutions that people actually use, and often are idiosyncratic, non-standardized. Grid world problem is usually represented in a 2D rectangular array of cells where agent traverses from cell to cell.\nRoute-finding problems in real life are websites and in-car systems that often use these methods.\n\n\n## AIMA Chapter 3.3 Search Algorithms\nSearch algorithm takes a search problem as an input and returns a solution/indication of failure. Many of these algorithms utilize a search tree superimposed over the state-space graph that forms many paths from the initial state to try and a find a path that reaches the goal state. Node = state; edges = actions; root = initial state. Expanding a particular node creates a child/successor node (available actions for that particular state); every child node also has a parent node. Frontier of search tree = child nodes that are leaf nodes. \nBest-first search process occurs such that 1. we choose a node n, with some minimum value of an evaluation function f(n) and 2. for each iteration, we choose the node on the frontier with min f(n) value and expand from there. 3 kinds of queues to support this are the priority queue (ordered by min cost), FIFO: first in, first out (BFS), and LIFO: last in, first out (DFS).\nRepeated state means that redundant paths form cycles and can cause a complete infinite search tree, and redundant paths are not optimal. We can measure problem-solving performance by completeness (does the algorithm find a solution/report when no solution is available?); cost optimality (does it find the solution with the lowest path cost of all solutions?); time complexity (how long does it take to find the solution?); and space complexity (how much memory is needed to perform the search?).\nA complete search algorithm should also be systematic and should explore a finite state space. For implicit state space, complexity can be measured in terms of d, depth (# of actions in optimal solution), m, number of maximum actions in any path, b, branching factor (number of successors of a node that must be considered).\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nUninformed search strategies means the agent has no clue about how close the state is to the goal\nBreadth-first search can make a better algorithm by performing early goal test, which is checking for the solution as we go along; vs best-first search’s late goal test. Space and time is both O(b^d), where b = successors and d = depth.\nDijkstra’s algorithm/uniform-cost search is a best-first search where the evaluation function is the cost of the path from the root to the current node\nDepth-first search always expands the deepest node in the frontier first. It is not an optimal solution--may return a non-optimal solution, but has much smaller needs for memory. Memory is O(bm), where b is the branching factor and m is the maximum depth of the tree. A variant of depth-first search uses backtracking, which only expands one successor at a time, such that memory becomes O(m).\nDepth-limited search is depth-first search but we stop at a limit l, which we treat as frontier nodes with no successors. The time = O(b^l) and space = O(bl), but we may  not necessarily find a solution. This algorithm is not complete! The diameter of state-space graph: max number of actions to reach goal state.\nIterative deepening search has memory of O(bd) with a solution and O(bm) when there is not a solution. This is good for when all actions have the same cost. It essentially is a depth-limited search but reaches failure instead of cutoff if no solution is found\nTime is O(b^d) when there is a solution and O(b^m) when there is not. In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and the depth of the solution is not known.\nBidirectional search searches forward from the initial state and backwards from the goal state, hoping the two searches will meet\nOptimality of different algorithms: depth-first and depth-limited are not complete and not optimal, while others are.\n\n## Module 3 Lecture Notes\n Your summary here \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\nGreedy best-first expands first node with lowest h(n) value that seems to lead most quickly to solution. Space/time is O(|V|).\nFor A*, f(n) = complete path and admissible + cost-optimal, as A* expands all nodes that can be reached from the initial state on a path where every node on the path has (surely-expanded nodes). Efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution. A* expands all nodes that can be reached from the initial state on a path where every node on the path has f(n) < C* (surely expanded nodes), where C* is cost of the optimal solution path. A* w/a consistent heuristic is optimally efficient: extends paths from the initial state and uses the same heuristic information and expands all nodes that are surely expanded by A*.\nSatisficing solutions are less optimal solutions that explore less nodes and take less time. Inadmissible heuristic is more accurate but not optimal.\nSuboptimal search algorithms include bounded suboptimal search (solution guaranteed to be within constant factor W of optimal cost); bounded-cost search (solution whose cost is less than some constant C); unbounded-cost search (solution of any cost, as long as we can find it quickly) (ex: speedy search, a GBF that uses the estimated number of actions required to reach a goal as a heuristic, same as GBF when actions have equal cost. Otherwise, it finds a solution more quickly w/higher cost).\nMemory-bounded search is when memory is split between frontier and reached states. Duplicating states in the frontier requires a trivial amount of memory (bc size of frontier is smaller than reached).\nReference counts is the num of times a state has been reached and remove it from the reached table when there are no more ways to reach the state. Algorithms that conserve memory usage include beam search (limits the size of the frontier) and keeps only the k nodes with the best f-scores, discarding any other expanded nodes. This is incomplete and suboptimal, but k can be a good use of available memory and the algorithm executes fast bc it expands fewer nodes. Essentially a focused part of the concentric contours of uniform-cost or A* search, which will contain the k best candidates.\nIterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth-first: benefits of A* w/o requirement to keep all reached states in memory at cost of visiting redundant states.\nRecursive best-first search is recursive DFS with limit to keep track of best alternative path from any ancestor of the current node (keeps backed-up value)\nMA* (memory-bounded A*) and SMA* (simplified MA*) are A* but, respectively, expanding the best leaf until memory is full; dropping the worst leaf node (the one with the highest f-value)\nBidirectional heuristic search is f_F(n) = gF(n) + hF(n) for forward and f_B(n) = gB(n) + hB(n) for nodes in the backward direction\nFront-to-front search attempts to estimate the distance to the other frontier\n\n## AIMA Chapter 3.6 Heuristic Functions\nEffective branching factor b*: one way to characterize the quality of a heuristic. Another way to characterize the effect of A* pruning with the given heuristic h because it reduces the effective depth by a constant kh compared to the true depth, and H2 dominates H1 in that it’s always better. \nState-space graph is a supergraph of the original state space. Cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. It must obey the triangle inequality and be consistent. Admissible heuristics can be derived from the solution cost of a subproblem of a given problem\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Relaxed problem** - problem with fewer restrictions on actions\n* **Pattern databases** - store exact solution costs for every possible subproblem instance\n* **Disjoint pattern databases** - sum of two costs is still a lower bound on the cost of solving the entire problem\n* **Precomputation** - done once and can be amortized over billions of search requests (the precomputation is time consuming but is helpful later)\n* **Metalevel state space** - each state in space captures internal (computational) state of a program that is searching in an ordinary state space\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nWhat is search for? Assumptions about the world: a single agent, deterministic actions, fully observed state, discrete state space. Path to goal is the important thing (paths have various costs, depths), and heuristics give problem-specific guidance. Identification is assignments to variables, and the oal itself is important, not the path.\nAll paths are at the same depth (for some formulations), and CSPs are specialized for identification problems\nCSPs represent the constraints that solutions must satisfy in a uniform declarative language. It must find solutions by general purpose search algorithms with no changes from problem to problem. There are no hand-build transition functions and no hand-built heuristics. We specify the problem in a formal declarative language, and a general-purpose algorithm does everything else\nCSP consists of a finite set of variables; a nonempty domain of possible values for each variable where D1, D2, Dn where Di = {v1, ..., vk}; a finite set of constraints (C2, C2, ..., Cm) where each constraint Ci limits the values that variables can take. A state is defined as an assignment of values to some or all variables, and a consistent assignment does not violate the constraints\nAssignment is complete when every variable is assigned a value: solution to a CSP is a complete, consistent, assignment and can be found.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nMinimax search: derived as solution for nondeterministic planning problems; desirable outcome must be guaranteed no matter what the “other side” does and is for games with multiple score outcomes. Optimal strategy given a game tree determined by working out the minimax value of each state n the tree. The minimax value of a terminal state = utility. Minimax is the utility of being in that state (for MAX), assuming that both players play optimally from there to the end of the game. It is a recursive algorithm that proceeds all the way down to the leaves of tree and backs up the minimax values through the tree as the recursion unwinds. It performs a complete depth-first exploration of the game tree. If max depth of the tree is m and there are b legal moves at each point, then the time-complexity of the minimax algorithm is O(b^m). Space complexity is O(bm) for an algorithm that generates all actions, or O(m) for one that generates actions one at a time (not good for games like chess).\nOptimal decisions in multiplayer games involves using a vector to replace single value for each node, and a utility function can return a vector of utilities\nAlpha-beta pruning uses pruning to get rid of large parts of the tree  that make no difference to the outcome. The value of root and minimax decision are independent of the values of the arbitrary leaves x, y, so they can be pruned. Consider a node n somewhere in the tree, such that a player has a chance of moving to n 1. If the  player has a better choice either at the same level, or any point higher up in the tree, player will never have to move to n. Minimax is depth-first, so we have to consider the nodes along a single path in the tree\nAlpha-beta pruning gets its name from the two extra params in MAX-VALUE, where alpha is the value of the best choice we have found at any choice point allong the path for max (alpha = at least) and beta is the value of the best (loweset value) choice we have found so for at any choice point along the path for MIN (beta = at most). It is O(b^m) such that branching becomes sqrt(b) instead of b\nIterative deepening searches one ply deep, record running of moves, then continue to go deeper.\nTranspositions are different permutations of the same move sequence that end up in the same position, and the problem can be addressed w/a transposition table that caches the heuristic values of states\nType A: considers all possible moves to a certain depth in the search tree and uses h(n) to estimate the utility of states at that depth -- wide but shallow\nType B:: ignores moves that look bad and follows promising lines as far as possible -- deep but narrow \nChess is A, and Go is B (higher branching factor)\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nHeuristic AB tree cuts off search early and apply h(n). Nodes become terminal, eval + cutoff test to cut search by the search depth and property of the state.\nMaterial value helps determine value of positions for eval functions (weighted linear function). Cutting off search checks if max depth reached and can lead to errors due to approximate nature of eval function (should only be applied to quiescent positions). Quiescence search is restricted to consider only certain types of moves, such as capture moves\nHorizon effect allows for singular extensions--clearly better move than all other moves in a given positions, even when the search would normally be cut off at that point\nForward pruning prunes moves that appear to be poor moves, but might possibly be good ones to save computation time at risk of making errors.\nBeam search: consider only a beam of the n best moves rather than all possible moves. ProbCut prunes nodes that are probably outside of the window. Late move reduction assumes that move ordering is done well and moves that appear later in the list are less likely to be good--this redueces depth of searched moves, saving time. If reduced search comes back w/value above current alpha, we can re-run the search with the full depth\nSearch vs lookup policy maps from every possible state to the best move in that state. The computer can play perfectly by lookup in the table constructed by retrograde minimax search.\nMCTS looks at value of state estimated as the average utility over a number of simulations of complete games starting from the state. Simulation/playout/rollout chooses moves first for one player, then for other, repeating until terminal position reached. Playout policy biases the moves towards good ones. Do N simulations from current state of game and track which moves has the highest win percentage. For stochastic games, this converges to optimal play as N increases, a selection policy that focuses the computational resources on the important parts of the game tree is needed. Balances 2 factors: exploration of states that have had few playouts, and exploitation of states that have done well in past playouts to get more accurate estimate of their value. Steps are selection (choose move and repeat down the tree to leaf); expansion (grow search tree by generating new child of selected node, shows new node marked with 0/0); simulation (perform playout from newly generated child node, choosing moves for both players according to the playout policy, and moves are not recorded in the search tree); back-propagation (use result of simulation to update all the search tree nodes going up to the root). Repeat these for a set number of iterations, or until the allotted time has expired, and return the move with the highest number of playouts\nEffective selection policy is called “upper confidence bounds applied to trees”, or UCT. Policy ranks possible move based on an upper confidence bound formula called UCDB1\n\n## AIMA Chapter 5.5 Stochastic Games\nStochastic games invokes the unpredictability of real life y including a random element, such as the throwing of dice (backgammon is  a good example: combines luck and skill). Chance nodes are present in stochastic games in addition to max and min nodes. Positions dont have definite minimax values--we can only calculate the expected value of a position, which is the average over all possible outcomes of the chance nodes. Expectiminimax value: for games with chance nodes, this is a generalization of the minimax value for deterministic games. Terminal max and min work the same except that legal moves for max and min are dependent on the outcome of the dice roll in the previous chance node. For chance nodes: compute expected value = sum of the value over all outcomes, weighted by the probability of each chance action. Eval function for games of chance must return values that are a positive linear transformation of the probability of winning. The relation to probability is an important and general property of situations in which uncertainty is involved, and big oh of xpectiminimax = O(b^m*n^m), where n is the number of distinct rolls.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nDecision theory: deals with choosing among actions based on the desirability of their immediate outcomes; the environment is assumed to be episodic. The agent’s preferences are captured by a utility function, which assigns a single number to express the desirability of a state. Expected utility of an action given the evidence, EU(a) = average utility value of the outcomes weighted by the probability that the outcome occurs. MEU: maximum expected utility - a rational agent should choose the action that maximizes the agent’s expected utility, and action = argmax EU(a). This formalizes the general notion that an intelligent agent should “do the right thing”, but does not operationalize that advice\nDecision theory provides the beginnings of a basic mathematical framework general enough to define the AI problem\nMEU principle’s central justification is that if an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments). The performance measure gives a score for a history--a sequence of states. This is applied retrospectively after an agent completes a sequence of actions\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nConstraints on rational preferences are lottery (set of outcomes for each action when there is uncertainty about what is being offered); outcome of lottery (atomic state or another lottery). Primary issue for utility theory is to understand how preferences between complex lotteries are related to preferences between the underlying states in those lotteries. There are six constraints to address this issue: orderability (given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable--agent cannot avoid deciding); transitivity (given any three lotteries, if an agent prefers A to  B and prefers B to C, then the agent prefers A to C); continuity (if some lottery B is between A and C in preference, then some probability p exists for which the rational agent will be indifferent between getting B for sure and the lottery that yields A w/probability p and C w/probability 1 - p); substitutability (if agent is indifferent between lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them); monotonicity (two lotteries A and B have the same outcomes--if agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A); decomposability (compound lotteries can be reduced to simpler ones using the laws of probability)\nNo fun in gambling rule, and rational preferences lead to utility\nExistence of utility function checks if agent’s preferences obey the axioms of utility, then there is a function such that U(A) > U(B) iff A is preferred to B and U(A) = U(B) iff agent is indifferent between A and B. The expected utility of a lottery is the sum of the probability of each outcome times the utility of that outcome. Value function/ordinal utility function: an agent needs only a preference ranking on states and the numbers don’t matter\n\n\n## AIMA Chapter 16.3 Utility Functions\nUtility functions look at preference elicitation, which presents choices to human and using the observed preferences to pin down underlying utility function. Given a utility scale, it’s possible to assess the utility of any particular prize S by asking the agent to choose between S and a standard lottery. Probability p is adjusted until the agent is indifferent between S and the standard lottery. The value of a statistical life is the value that is assigned to a life. A micromort is a one in a million chance of death. QALY: quality-adjusted life year -- people accept a shorter life expectancy to avoid a disability. Utility of money: monotonic preference for money, meaning that agent prefers more money to less, all other things being equal.\nSome qualities of risk include: risk-averse, risk seeking, certainty equivalent (value an agent will accept in lieu of a lottery), instance premium (difference between EMV of a lottery and its certainty equivalent). An agent with a linear curve is risk-neutral. The expected utility and post-decision disappointment are determined by order statistic (distribution of any particular ranked element of a sample) and optimizer’s curse (tendency for estimated expected utility of the best choice to be too high).\nHuman judgment and irrationality are implemented by decision theory/normative theory, which describes how a rational agent should act. Descriptive theory describes how actual agents really do act. One explanation for the apparently irrational preferences is the certainty effect; people are strongly attracted to gains that are not certain. Framing effect is the wording of a decision problem having an impact on the agent’s choices. Evolutionary psychology\n\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Planning** - sequences of actions\n* **Move** - both players have taken an action--ply brings us one level deeper into a game\n* **Killer moves** - best moves--trying to find them first is called the killer move heuristic\n* **Ambiguity aversion** - people elect the known probability rather than the unknown unknowns\n* **Anchoring effect** -  given expensive option and a cheaper (not cheap) option so users will go for less expensive option\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nThree components include X (set of variables), D (set of domains, one for each variable), C (set of constraints that specify allowable combinations of values). An arbitrary domain Di consists of a set of allowable values {v1,..,vk} for variable Xi. Each constraint Cj consists of a pair (scope, rel) where scope is a tuple of variables that participate in the constraint andrel is a relation that defines the values that those variables cann take on. Relation can mean an  explicit set of all tuples of values that satisfy the constraint, or function that can compute whether or not a tuple is a member of the relation. CSPs deal with assignments of values to variables\nSolution to a CSP should be a consistent, complete assignment. A partial assignment would be one that leaves some variables unassigned. A partial solution is a partial assignment that is consistent. Constraint graphs contain nodes that correspond to variables of the problem, and edge connects any two variables that participate in a constraint.\nVariations on the CSP formalism: simplest kind of CSP (discrete, finite domains). Discrete domains can be infinite, such as the set of integers or strings. Implicit constraints are needed rather than explicit tuples of values, and some special solution algos exist for linear constraints on integer variables. No algo exists for solving general nonlinear constraints on integer variables--problem is undecidable and constraint satisfaction problems with continuous domains are common (ex: scheduling of experiments on Hubble Space Telescope requires precise timing of observations--start and finish of each observation and maneuver are continuous-valued variables that must obey a variety of astronomical, precedence, and power constraints).\nBest-known continuous domain CSP is linear programming problems, where constraints must be linear equalities or inequalities. The simplest type of constraint is unary, which restricts the value of a single variable. Binary constraint relates two variables and binary CSP is one with only unary and binary constraints--can be represented as a constraint graph.\nCryptarithmetic puzzles are ex of global constraints, and a constraint hypergraph has ordinary nodes and hypernodes (n-ary constraints/constraints involving n variables)\nDual graph transformation: new graph in which there is one variable for each constraint in the original graph, and one binary constraint for each pair of constraints in the original graph that share variables\nPreference constraint: allowable but not optimal solutions\nConstrained optimization problem: CSPs with preferences can be solved w/optimization search methods (path-based or local)\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nConstraint propagation: using constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, etc. The key is local consistency such that each variable = node and binary constraint = edge, then the process of enforcing local consistency in eeach part of the graph causes inconsistent values to be eliminated throughout the graph.\nNode-consistency is when a variable whose values in its domain satisfy the variable’s unary constraints. The variable is arc-consistent if every value in its domain satisfies the variable’s binary constraints. Path consistency occurs when binary constraints are tightened by using implicit constraints inferred by looking at triples of variables. K-consistency is the stronger forms of propagation such that for any set of k - 1 variables and any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. CSP is strongly k-consistent if it is k-consistent and (k-1)-consistent...1-consistent.\nResource constraint is atmost constraint. It detects inconsistencies by checking sum of the min values of the current domains. It has bounds propagation and is bounds-consistent such that for every variable X and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nBacktracking search for CSPs looks at commmutativity, the order of application of any given set of actions does not matter. Degree heuristic attempts to reduce branching factor on future choicesby selecting the variable that is involved in the largest number of constraints on other unassigned variables. Least-constraining-vluae heuristic picks the value that rules out the fewest choices for the neighboring variables in the constraint graph is preferred. Forward checking establishes arc consistency when variable X is assigned.\nFor each unassigned variable Y that is connected to X by a constraint, delete from Y’s domain any value that is inconsistent w/value chosen for X\nMAC (maintaining arc consistency) detects inconsistencies\nIntelligent backtracking is looking backtracking, while chronological backtracking is the most recent deciiosn point is revisited.\nConflict set contains assignments that are in conflict with some vlue for SA\nConflict-directed backjumping involves backjumping algorithm that uses conflict sets to skip around\nSet of variables + corresponding values are no-good\n\n## AIMA Chapter 6.4 Local Search for CSPs\nLocal searches for CSPs involve ini-conflicts heuristic, which selects the value that results in the minimum number of conflics with other variables. Tabu search keeps a small list of recently visited states and forbidding the algorithm to return to those states, and constraint weighting concentrates the search on the important constraints.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\nIndependent subproblems are unrelated problems that yield a solution. Connected components are connected parts of a constraint path--independence can be derived from this information. Trees are constraint graph when any two variables are connected by only one path. Any tree-structured CSP can be solved in time linear in the number of variables.\nDirectional arc consistency (DAC) means that if for every Xi, it’s arc-consistent with each Xj for j > i\nTopological sort checks arbitrary variable is root, and ordering of the variables such that each variable appears after its parent\nTree decomposition is the transformation of original graph into a tree where each node in the tree consists of a set of variables. Every variable in the original problem appears in at least one of the tree nodes and if two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. Also, if a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. The min tree weight is the min width among all tree decompositions. CSPs with constraint graphs of bounded tree width are solvable \nin polynomial time. Value symmetryis the S=symmetry-breaking constraint to reduce search space.\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Consistent/legal assignment** - one that does not violate any constraints\n* **Complete assignment** - one in which every variable is assigned a value\n* **Precedence constraints** -  between individual tasks, we can say some tasks must occur before others, etc.\n* **Disjunctive constraints** - constraint that certain tasks may not overlap in time--either one comes first or the other does\n* **Global constraint** - constraint involving an arbitrary number of variables\n* **Constraint learning** - finding a minimum set of variables from the conflict set that causes the problem\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nKnowledge base is a set of sentences in which each sentence is expressed in knowledge representation language and reps some assertion about the world. An axio mis a setence taken as being given without being derived from other sentences. Tell and Ask are operations to query and add what si known. These involve inference (derive new sentecne from old). Agent maintains a knowledge base that initially may contain background knowledge. Each time the agent program is called, it TELLS the knowledge base the percept. Then, it ASKS the knowledge base for the action. Then, the agent program TELLS the knoweldge base what action was chosen and return action to be executed (done by make-percept-sentence, make-action-query, make-action-sentence). Inference is hidden in ASK and TELL. We also need to specify a knowledge level for the agent. Analyses are disjoint from implementation level.\nDeclarative approach is when the agent designer can TELL one by one until agent knows how to act. Procedural approach encodes desired behaviors directly in the program code.\n\n## AIMA Chapter 7.2 The Wumpus World\nWumpus World is cave with gold, pits, etc. Performance measure is reward for action. Environment is the grid of rooms. Actuators is the player moving square to square and actions it can make. The sensors can register stenches, breezes, bump, etc.\n\n## AIMA Chapter 7.3 Logic\nLogic must define semantics of setneces. Semantics define truth of setences with respect to possible worlds (model/mathematical abstractions of environments). m satisfies a/m is a model of a if a is true in model m. M(a) is the set of all models of a.\nLogical reasoning is the logical entailment between sentences such that a sentence follows logically from another sentence (|=), aka a entails B when a |= B, or M(a) subset of M(B). Logical inference derives conclusions by applying entailment. Inference algorithm model checking checks all possible models to see that a is true in allm odels in which KB is true such that M(KB) subset of M(a). Sound or truth-preserving inference algorithm dervies only entailed sentences. Completeness is also desriable (derive any entailed sentence). \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nAtomic sentences = single propositional symbol (can be true or false). Complex sentences are constructed from simpler sentences with parentheses and logical connectives (5 common are not, literal and, or, and implies. Implications are made of precedents/antecedents and conclusions/consequents. Same as rules or if-then statements. Literals are atomic sentences or negated atomic sentences.\nTruth values are set for every porposition symbol in the set of values. There are five following rules for complex sentences: not P is true iff P is false in m; P and Q is true iff P and Q are true in m; P or Q is true iff eiteher P or Q is true; P implies Q is ture unless P is true and Q is false in m; P implies Q and Q implies P are true iff P and Q both true or both false in m.\nTruth tables can also specify each truth value of a complex sentence.\n\n## AIMA 7.5 Propositional Theorem Proving\nPropositional theorem proving applies rules of inference to sentences in our knowledge base to construct proof of desired sentence w/o consulting models. Concepts relating to entailment are logical equivalence (two true sentences in m represented by triple =); validity (sentence is true in all models), where valid setnences are called tautologies (necessariliy true), useful in deduction theorems; \nand satisfiability, where sentences are true if satisfied by some model. We can prove B from a by reductio ad absurdum or refutation/proof by contradiction.\nSome rules include Modus Ponens, meaning whenever sentences a=>B and a are given, sentence B can be inferred (a => B, a / B). Another rule is And-elimnation, which a ^ B / a.\nWe can also prove by resolution, which finds a complete inference algorithm when coupled with a complete search algorithm. RC(S) is resolution closure to compute final value of variable clauses. Completenesss theorem for resolution in propositional logic is called ground resolution theorem, such that if a set of clauses is unsatisfiable, the resolution closure of those clauses contains the empty clause.\nDefinite clauses are a disjunction of literalsof which one is positive. The Horn clause is a disjunction of literals of which at most one is positive. All definite clauses are Horn clauses, as are clauses with no positive literals (goal clauses). These are closed.\nKnowledge bases contain only definite clauses because 1. every definite clause can be written as an implication w/premise as a conjunction of positive literals and whose conclusion is a single positive literal. Horn form: premise is body and conclusion is head and sentence has a single positive literal called fact. 2. forward-chaining + backward-chaining algorithm done to infer with Horn clauses (logic programming). 3. entailment with Horn in linear time in size of knowledge base. Forward-chaining is sound and complete. Forward chaining is also data-driven reason-derived. Backward chaining is a form of goal-directed reasoning good for questions in relation to relevant facts.\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}