{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm notes_db.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5222d03d-ca9e-4284-d165-500b28869d23"
      },
      "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": 103,
      "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": "d46d8f70-4d67-4b49-c07b-4eb30117b005"
      },
      "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": 104,
      "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": 105,
      "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 = \"\"\" Historically, there are several different approaches to defining \\\n",
        "(and therefore recreating) intelligence. We can categorize these differing views along \\\n",
        "two \"dimensions\": 1) human (i.e. fidelity to human performance) vs rational (doing the \\\n",
        "\"right thing\") and 2) thought (thought processes and reasoning) vs behavior (external \\\n",
        "characterization). This yields four possible combinations each describing an approach \\\n",
        "to artificial intelligence. Acting Humanly: proponents include Alan turing, as is \\\n",
        "encapsulated in the Turing test. A human interrogator poses written questions and the \\\n",
        "computer generates written responses; if the interrogator cannot tell whether the \\\n",
        "response was written by a person or computer then the computer passes the test. \\\n",
        "Thinking Humanly: proponents include Allen Newell and Herbert Simon who developed \\\n",
        "the \"general problem solver\" and were concerned with comparing the sequence and \\\n",
        "timing of its reasoning against those of humans solving the same problem. Cognitive \\\n",
        "Science can be seen as a product of this approach. Thinking Rationally: defining \\\n",
        "\"right thinking\" has led to the development of logic. Probability fills in the gaps \\\n",
        "where knowledge or events are uncertain. Acting Rationally: this is the approach that \\\n",
        "has prevailed for most of the field’s history and can be thought of as the \"Standard Model\": \\\n",
        "focusing on the study and construction of agents that \"do the right thing\". This approach \\\n",
        "has the advantages that 1) it is more general than the thinking rationally approach and \\\n",
        "2) it is more amenable to scientific development than imitating human behavior or thought. \\\n",
        "Furthermore, the skills required in the other approaches (e.g. Turing test and making \\\n",
        "inferences) will be useful in making an agent act rationally.\"\"\" \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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "An agent is anything that can perceive an environment (via sensors) and act on that \\\n",
        "environment (via actuators). Environment could be the entire universe (i.e. everything) \\\n",
        "but typically just a part of the universe that is relevant to the agent; the part that \\\n",
        "affects what the agent perceives and is affected by the agent’s actions. \\\n",
        "E.g.: humans - sensors = eyes, ears, etc., actuators = hands, legs, vocal tract, etc.; \\\n",
        "robot - sensors = camera, infrared range finder, etc., actuators = motors, cervos, etc.; \\\n",
        "software agent - sensory inputs = file contents, network packets, user input, etc., \\\n",
        "actions = writing files, sending network packets, displaying information, generating \\\n",
        "sounds, etc. thermostat - sensors = temperature and humidity sensors, actuators = fan, \\\n",
        "valve, and compressor controls. Percept refers to the input an agent receives \\\n",
        "from it’s sensors; typically we represent a precept as a vector of all the inputs/signals \\\n",
        "of each sensor. Percept Sequence refers to the entire history of an agent’s percepts to date. \\\n",
        "An agent’s behavior is a consequence of its Percept Sequence and any built-in knowledge. \\\n",
        "Mathematically, we can describe this as a function which maps a series of percepts to a \\\n",
        "series of actions. This abstract mathematical description is called the agent function. \\\n",
        "An agent program is an implementation of the agent function running on a physical \\\n",
        "architecture (agent = architecture + program). Important Note: the concept of an agent \\\n",
        "is a helpful framework for analyzing systems, but not an absolute lens in which to \\\n",
        "characterize the world into agents and non-agents; we consider something an agent when \\\n",
        "it is helpful - typically if the entity contains significant computational resources \\\n",
        "and the task environment requires nontrivial decision making; Additionally, something \\\n",
        "is an agent vs part of the environment when it’s behavior can be described in terms of \\\n",
        "a performance measure (see below). \n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "But what does it mean to do the “right thing”? Typically for AI we use the notion of \\\n",
        "consequentialism, that is, an agent’s behavior is evaluated based on its consequences. \\\n",
        "We use a Performance Measure to evaluate the behavior of our agent. This is an objective \\\n",
        "criterion for success of an agent’s behavior given the evidence provided by the percept \\\n",
        "sequence. But our definition should not require omniscience. How can an agent know what \\\n",
        "the correct course of action is if this depends on the consequences which are not \\\n",
        "perfectly known until it has finished its action? So we introduce the notion of \\\n",
        "expected performance (to distinguish from actual performance, which would require \\\n",
        "knowledge of the future) which we determine by calculating the expected value of \\\n",
        "the performance measure. Now we define a rational agent as follows: for every possible \\\n",
        "percept sequence, a rational agent selects an action that maximizes the expected \\\n",
        "value of its performance measure, given its Percept Sequence and any built-in knowledge. \n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" Agents are ‘solutions’ to ‘problems’; we refer to these ‘problems’ \\\n",
        "as Task Environments. We define a Task Environment we need to specify: a Performance \\\n",
        "measure, an Environment, Actuators, and Sensors (PEAS). E.g. Taxi - performance \\\n",
        "measure = safe, fast, maximize profits, etc., environment = roads, traffic, pedestrians, \\\n",
        "etc., actuators = steering, accelerator, brake, etc., sensors = cameras, radar, \\\n",
        "speedometer, etc. After defining the task environment, we can construct the agent \\\n",
        "function. Then we can write an agent program to implement the agent function. \\\n",
        "Properties of Task Environments:\n",
        "<ol>\n",
        "<li> **fully observable** (agent can detect all aspects of the environment that are relevant \\\n",
        "to the choice of action - e.g. chess) VS **partially observable** (access to some of \\\n",
        "information about the environment, but not the entire global picture - e.g. self-driving cars) \\\n",
        "(**unobservable**) </li>\n",
        "<li> **deterministic** (the expected result of a given action is guaranteed to happen) \\\n",
        "VS **nondeterministic** (the outcome of an action is uncertain - e.g. dice, cards - use \\\n",
        "term stochastic if we explicitly quantify the probabilities of possible outcomes \\\n",
        "and nondeterminsitic if not quantified) </li>\n",
        "<li> **episodic** (agent’s experience is divided into atomic episodes which do not depend \\\n",
        "on the actions taken in previous episodes - e.g. spotting defective parts in assembly \\\n",
        "line) VS **sequential** (each decision affects all future decisions - e.g. chess, taxi)</li>\n",
        "<li> **static** (environment remains unchanged while the agent is deliberating - e.g. \\\n",
        "crossword) VS **dynamic** (environment is changing eve while agent is deciding which \\\n",
        "action to take - e.g. driving)  VS **semi-dynamic** ( environment itself does not change \\\n",
        "with passage of time, but agent’s performance score does - e.g. chess w/ clock)</li>\n",
        "<li> **discrete** (e.g. chess) VS **continuous** (e.g. driving) (with regard to the \\\n",
        "states, time, percepts, and actions)</li> \n",
        "<li> **single agent** (e.g. crossword) VS **multiagent** (e.g. chess, pacman - competitive or cooperative)</li>\n",
        "<li> **known** (the outcomes for all actions are given) VS **unknown** () (refers to agent’s \\\n",
        "state of knowledge about the environment, rather than environment itself. Known vs \\\n",
        "observable - solitaire is known but partially observable, video game might be fully \\\n",
        "observable but unknown if button controls are not known)</li>\n",
        "</ol> \n",
        "Hardest case: partially observable, nondeterministic, sequential, dynamic, continuous, multiagent, and unknown\n",
        " \"\"\"\n",
        "chapter2_4 = \"\"\" \n",
        "Simple reflex agent\n",
        "Model based agent\n",
        "Goal based agent\n",
        "Utility based agent\n",
        "Learning agents\n",
        "\n",
        "Atomic representation\n",
        "Factored representation\n",
        "Structured representation\n",
        "\n",
        "Localist representation\n",
        "Distributed representation\n",
        "\n",
        " \"\"\"\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": 106,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "658fb693-ddde-4f30-ff39-4fabdeaf32e0"
      },
      "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": 107,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Historically, there are several different approaches to defining (and therefore recreating) intelligence. We can categorize these differing views along two \"dimensions\": 1) human (i.e. fidelity to human performance) vs rational (doing the \"right thing\") and 2) thought (thought processes and reasoning) vs behavior (external characterization). This yields four possible combinations each describing an approach to artificial intelligence. Acting Humanly: proponents include Alan turing, as is encapsulated in the Turing test. A human interrogator poses written questions and the computer generates written responses; if the interrogator cannot tell whether the response was written by a person or computer then the computer passes the test. Thinking Humanly: proponents include Allen Newell and Herbert Simon who developed the \"general problem solver\" and were concerned with comparing the sequence and timing of its reasoning against those of humans solving the same problem. Cognitive Science can be seen as a product of this approach. Thinking Rationally: defining \"right thinking\" has led to the development of logic. Probability fills in the gaps where knowledge or events are uncertain. Acting Rationally: this is the approach that has prevailed for most of the field’s history and can be thought of as the \"Standard Model\": focusing on the study and construction of agents that \"do the right thing\". This approach has the advantages that 1) it is more general than the thinking rationally approach and 2) it is more amenable to scientific development than imitating human behavior or thought. Furthermore, the skills required in the other approaches (e.g. Turing test and making inferences) will be useful in making an agent act rationally.\n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n \nAn agent is anything that can perceive an environment (via sensors) and act on that environment (via actuators). Environment could be the entire universe (i.e. everything) but typically just a part of the universe that is relevant to the agent; the part that affects what the agent perceives and is affected by the agent’s actions. E.g.: humans - sensors = eyes, ears, etc., actuators = hands, legs, vocal tract, etc.; robot - sensors = camera, infrared range finder, etc., actuators = motors, cervos, etc.; software agent - sensory inputs = file contents, network packets, user input, etc., actions = writing files, sending network packets, displaying information, generating sounds, etc. thermostat - sensors = temperature and humidity sensors, actuators = fan, valve, and compressor controls. Percept refers to the input an agent receives from it’s sensors; typically we represent a precept as a vector of all the inputs/signals of each sensor. Percept Sequence refers to the entire history of an agent’s percepts to date. An agent’s behavior is a consequence of its Percept Sequence and any built-in knowledge. Mathematically, we can describe this as a function which maps a series of percepts to a series of actions. This abstract mathematical description is called the agent function. An agent program is an implementation of the agent function running on a physical architecture (agent = architecture + program). Important Note: the concept of an agent is a helpful framework for analyzing systems, but not an absolute lens in which to characterize the world into agents and non-agents; we consider something an agent when it is helpful - typically if the entity contains significant computational resources and the task environment requires nontrivial decision making; Additionally, something is an agent vs part of the environment when it’s behavior can be described in terms of a performance measure (see below). \n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nBut what does it mean to do the “right thing”? Typically for AI we use the notion of consequentialism, that is, an agent’s behavior is evaluated based on its consequences. We use a Performance Measure to evaluate the behavior of our agent. This is an objective criterion for success of an agent’s behavior given the evidence provided by the percept sequence. But our definition should not require omniscience. How can an agent know what the correct course of action is if this depends on the consequences which are not perfectly known until it has finished its action? So we introduce the notion of expected performance (to distinguish from actual performance, which would require knowledge of the future) which we determine by calculating the expected value of the performance measure. Now we define a rational agent as follows: for every possible percept sequence, a rational agent selects an action that maximizes the expected value of its performance measure, given its Percept Sequence and any built-in knowledge. \n \n\n## AIMA 2.3 The Nature of Environments\n Agents are ‘solutions’ to ‘problems’; we refer to these ‘problems’ as Task Environments. We define a Task Environment we need to specify: a Performance measure, an Environment, Actuators, and Sensors (PEAS). E.g. Taxi - performance measure = safe, fast, maximize profits, etc., environment = roads, traffic, pedestrians, etc., actuators = steering, accelerator, brake, etc., sensors = cameras, radar, speedometer, etc. After defining the task environment, we can construct the agent function. Then we can write an agent program to implement the agent function. Properties of Task Environments:\n<ol>\n<li> **fully observable** (agent can detect all aspects of the environment that are relevant to the choice of action - e.g. chess) VS **partially observable** (access to some of information about the environment, but not the entire global picture - e.g. self-driving cars) (**unobservable**) </li>\n<li> **deterministic** (the expected result of a given action is guaranteed to happen) VS **nondeterministic** (the outcome of an action is uncertain - e.g. dice, cards - use term stochastic if we explicitly quantify the probabilities of possible outcomes and nondeterminsitic if not quantified) </li>\n<li> **episodic** (agent’s experience is divided into atomic episodes which do not depend on the actions taken in previous episodes - e.g. spotting defective parts in assembly line) VS **sequential** (each decision affects all future decisions - e.g. chess, taxi)</li>\n<li> **static** (environment remains unchanged while the agent is deliberating - e.g. crossword) VS **dynamic** (environment is changing eve while agent is deciding which action to take - e.g. driving)  VS **semi-dynamic** ( environment itself does not change with passage of time, but agent’s performance score does - e.g. chess w/ clock)</li>\n<li> **discrete** (e.g. chess) VS **continuous** (e.g. driving) (with regard to the states, time, percepts, and actions)</li> \n<li> **single agent** (e.g. crossword) VS **multiagent** (e.g. chess, pacman - competitive or cooperative)</li>\n<li> **known** (the outcomes for all actions are given) VS **unknown** () (refers to agent’s state of knowledge about the environment, rather than environment itself. Known vs observable - solitaire is known but partially observable, video game might be fully observable but unknown if button controls are not known)</li>\n</ol> \nHardest case: partially observable, nondeterministic, sequential, dynamic, continuous, multiagent, and unknown\n \n\n## AIMA 2.4 The Structure of Agents\n \nSimple reflex agent\nModel based agent\nGoal based agent\nUtility based agent\nLearning agents\n\nAtomic representation\nFactored representation\nStructured representation\n\nLocalist representation\nDistributed representation\n\n \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 = \"\"\" \n",
        "all data is treated as objects. Python has strong typing (every object has a fixed type), \\\n",
        "but it is also dynamic typing (type is automatically determined and can change if reassigne \\\n",
        "to differnt type). Immutable: strings, tuples, Mutable: Lists.\\n \n",
        "List comprehensions:\\n\n",
        "li = [3, 6, 2, 7]\\n\n",
        "[elem * 2 for elem in li]\\n\n",
        "result is [6, 12, 4, 14]\\n\n",
        "Dictionary keys must be immutable.\\n \n",
        "[:] operator returns copy of a list\\n\n",
        "no function overloading in python, but operator overloading is possible.\\n\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"cannot be modified once created\",\n",
        "}"
      ],
      "execution_count": 108,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 387
        },
        "outputId": "8d9d43da-b5f6-4a84-c0d6-75010ee0d180"
      },
      "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": 109,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nall data is treated as objects. Python has strong typing (every object has a fixed type), but it is also dynamic typing (type is automatically determined and can change if reassigne to differnt type). Immutable: strings, tuples, Mutable: Lists.\n \nList comprehensions:\n\nli = [3, 6, 2, 7]\n\n[elem * 2 for elem in li]\n\nresult is [6, 12, 4, 14]\n\nDictionary keys must be immutable.\n \n[:] operator returns copy of a list\n\nno function overloading in python, but operator overloading is possible.\n\n \n\n## Module 2 Definitions\n* **Mutability** - cannot be modified once created\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 = \"\"\" Problem-Solving Agents solve Search Problems by planning ahead and \\\n",
        "formulating the best possible sequence of actions (i.e. Searching). The Task Environments \\\n",
        "we are considering here are fully observable, deterministic, and known. The solution to a \\\n",
        "problem in such an environment is a fixed sequence of actions, and can therefore be found \\\n",
        "via a Search, which is a computational process that considers a sequence of actions that \\\n",
        "form a path from the initial state to a goal state. We formally define a Search Problem \\\n",
        "by specifying: \n",
        "\\n1) States - the set of all possible states $S$\n",
        "\\n2) Initial State - state in which the agent starts $s_i \\in S$\n",
        "\\n3) Goal State(s)/Goal Test  - a state in which the agent has accomplished the \\\n",
        "objective. Can define a goal test $Goal$ which indicates if the goal has been reached \\\n",
        "- $s$ is a goal state if $Goal(s) == true$\n",
        "\\n4) Actions - the set of available actions $A$. We define a function $Actions$ such \\\n",
        "that $Actions(s) =$ the set of actions that is applicable in $s$ (i.e can be execute in $s$)\n",
        "\\n5) Transition Model - describes what each action does (from the given state). This is \\\n",
        "represented as a function $Results$: $Results(s, a) = s_r =$ the state that results \\\n",
        "from doing action $a$ in state $s$. This new state $s_r$ is called a successor of $s$\n",
        "\\n6) Action Cost - the numeric cost of applying an action (from one \\\n",
        "state to another). We denote an action cost function: $c(x,a,y) =$ the cost of taking action $a$ from \\\n",
        "state $x$ to state $y$. The cost must be positive and should reflect the performance \\\n",
        "measure, as we will use this to determine the optimal solution. The overall Path Cost \\\n",
        "will be the sum of action costs along a path.\n",
        "\n",
        "\\nNote that our formulation is a model which is an abstraction of the real world problem. \\\n",
        "For example we don’t include the weather, or traffic etc. We can think of this abstraction \\\n",
        "in terms of equivalence classes. Our abstract State = a set (equivalence class) of real-world \\\n",
        "states. Similarly our abstract actions = a set (equivalence class) of combinations of real \\\n",
        "world actions.  \n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" \n",
        "Grid world - vacuum world\\n\n",
        "8-puzzle\\n\n",
        "Route-finding puzzle\\n\n",
        "Touring problems - traveling salesperson\\n\n",
        "VLSI layout\\n\n",
        "robot navigation\\n\n",
        "Automatic assembly sequencing\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" A Search Algorithm takes a search problem as an input and returns either \\\n",
        "a solution or an indication of failure. Can visualize search as a tree: \\\n",
        "each node represents a state, each edge represents an action. Root node is \\\n",
        "the initial state, and every child is a successor of its parent, connected by the \\\n",
        "respective action. Can expand a node by using the Actions function to consider all \\\n",
        "actions available from that state, and using the Transition Model to determine the \\\n",
        "resulting state. A state for which a node has been generated (whether expanded or not) \\\n",
        "is said to have been reached. Three distinct regions of the graph: nodes that have \\\n",
        "been reached and visited/expanded, nodes that have been reached but not expanded (the frontier), \\\n",
        "and nodes that have not been reached; the frontier separates the other two. \\\n",
        "The crux of the search: deciding which node to expand next - depends \\\n",
        "on how the queue is implemented.\n",
        "\n",
        "A search tree will contain redundant paths which include multiple different paths \\\n",
        "from one node to another, as well as cycles. A tree search doesn't not check for redundant paths \\\n",
        "(i.e. treats different paths to the same node as distinct), but a graph \\\n",
        "search does, by checking to see if a node \\\n",
        "has been visited before adding it to the search queue- this requires additional memory.\n",
        "\n",
        "Parameters of a state space are depth (d) - the number of actions in an optimal \\\n",
        "solution; maximum depth (m) - the maximum number of actions in any path; and the \\\n",
        "branching factor (b) - the number of successors considered for each node.\n",
        "\n",
        "```\n",
        "General-Tree-Search-Algo(problem) -> solution or failure\n",
        "  initialize frontier as some type of queue\n",
        "  add initial state to frontier\n",
        "  while the frontier is not empty:\n",
        "    pop node from frontier\n",
        "    if node is goal state:\n",
        "      then return node\n",
        "    expand node- i.e. for each successor, \n",
        "      add to the frontier\n",
        "  return failure\n",
        "\\n\n",
        "General-Graph-Search-Algo(problem) -> solution or failure\n",
        "  initialize frontier as some type of queue\n",
        "  add initial state to frontier\n",
        "  initialize explored as empty set\n",
        "  while the frontier is not empty:\n",
        "    pop node from frontier\n",
        "    if node is goal state:\n",
        "      then return node\n",
        "    add node to explored set\n",
        "    expand node- i.e. for each successor, \n",
        "      if not in frontier and not in explored\n",
        "        add to the frontier\n",
        "  return failure\n",
        "```\n",
        "\n",
        "Criteria for evaluating search algorithm performance:\n",
        "1)Completeness - a search algorithm is complete if it is guaranteed to find a \\\n",
        "solution if one exists, and to correctly report a failure if not\n",
        "2)(Cost) Optimality - a solution is optimal if it is guaranteed to find the/an optimal solution\n",
        "3)Time Complexity\n",
        "4)Space Complexity\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "An uninformed search only has access to the problem definition. Algorithms build \\\n",
        "a search tree and attempt to find a solution by exploring the tree. They differ in \\\n",
        "their decision of which node to expand next:\\n\n",
        "\n",
        "<ul>\n",
        "<li>Best First Search - selects the node with the minimum cost according to some evaluation \\\n",
        "function f(n) - priority queue with f(n)</li>\n",
        "<li>Bread-First Search - selects the node that was added to the queue first - FIFO queue</li>\n",
        "<li>Uniform-Cost Search (aka Dijkstra’s) - selects the node with the lowest path cost \\\n",
        "g(n) - priority queue with g(n) - uniform because it spreads out in eaves of uniform \\\n",
        "path cost (wheras breadth first spreads out in waves of uniform depth)</li> \n",
        "<li>Depth-First Search - selects the node that was most recently added - LIFO queue \\\n",
        "(variant with backtracking - only one successor is generated at a time rather than \\\n",
        "all at the same time, and succeros are generated by modifying the current state rather \\\n",
        "than copying and changing a new state - reduces memory use)</li>\n",
        "<li>Depth Limited - Depth first search, but limit depth to $l$</li>\n",
        "<li>Iterative Deepening - keep performing depth limited and increasing $l$ each time; \\\n",
        "combines benefits of depth first and breadth first search.</li>\n",
        "<li>Bidirectional Search - simultaneously search fro initial state forward, and goal \\\n",
        "state backwards, untl two searches meet.</li> \n",
        "</ul>\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "Reflex agent: picks a single action based on a percept at a given time\\n\n",
        "problem solving agent: plans ahead - undertakes a serach whic sonideres a sequnence of actions \\\n",
        "that forms a path from the start to the goal state. this sequence is called a solution\\n\n",
        "Tree search treats different paths to the same node as distinct, in contrast to graph search. \\\n",
        "Graph search checks to see if a node has been visited before adding it to the search quque. \\\n",
        "Uninformed search strategies (aka Blind Search) use only information avaialbel in the probelm definition. \\\n",
        "strategy = order of tree expansion i.e. which node on the frontier shoue we expand next: implemented \\\n",
        "by using different queue structures for the fronrier/n\n",
        "LIFO - Depth first search -/n\n",
        "FIFO - Breadthfirst search/n\n",
        "Priority - Best first search/n\n",
        "\n",
        "Depth Limited search:DFS with a depth limit $l$/n\n",
        "if $l =d$ (by luck) then optimal/n\n",
        "if $l < d$ incomplete/n\n",
        "if $l >d$ not optimal/n\n",
        "\n",
        "Iterative Deepening Search: user depth liite search as subroutine and keep increasing $l$\\\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        "\"state space\" : \"the set of all states reachable form the intial state by any sequenc of actions\"   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 110,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6d7be00b-d65b-4e87-f351-ee8ef3a60df0"
      },
      "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": 111,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem-Solving Agents solve Search Problems by planning ahead and formulating the best possible sequence of actions (i.e. Searching). The Task Environments we are considering here are fully observable, deterministic, and known. The solution to a problem in such an environment is a fixed sequence of actions, and can therefore be found via a Search, which is a computational process that considers a sequence of actions that form a path from the initial state to a goal state. We formally define a Search Problem by specifying: \n\n1) States - the set of all possible states $S$\n\n2) Initial State - state in which the agent starts $s_i \\in S$\n\n3) Goal State(s)/Goal Test  - a state in which the agent has accomplished the objective. Can define a goal test $Goal$ which indicates if the goal has been reached - $s$ is a goal state if $Goal(s) == true$\n\n4) Actions - the set of available actions $A$. We define a function $Actions$ such that $Actions(s) =$ the set of actions that is applicable in $s$ (i.e can be execute in $s$)\n\n5) Transition Model - describes what each action does (from the given state). This is represented as a function $Results$: $Results(s, a) = s_r =$ the state that results from doing action $a$ in state $s$. This new state $s_r$ is called a successor of $s$\n\n6) Action Cost - the numeric cost of applying an action (from one state to another). We denote an action cost function: $c(x,a,y) =$ the cost of taking action $a$ from state $x$ to state $y$. The cost must be positive and should reflect the performance measure, as we will use this to determine the optimal solution. The overall Path Cost will be the sum of action costs along a path.\n\n\nNote that our formulation is a model which is an abstraction of the real world problem. For example we don’t include the weather, or traffic etc. We can think of this abstraction in terms of equivalence classes. Our abstract State = a set (equivalence class) of real-world states. Similarly our abstract actions = a set (equivalence class) of combinations of real world actions.  \n\n\n## AIMA Chapter 3.2 Example Problems\n \nGrid world - vacuum world\n\n8-puzzle\n\nRoute-finding puzzle\n\nTouring problems - traveling salesperson\n\nVLSI layout\n\nrobot navigation\n\nAutomatic assembly sequencing\n \n\n## AIMA Chapter 3.3 Search Algorithms\n A Search Algorithm takes a search problem as an input and returns either a solution or an indication of failure. Can visualize search as a tree: each node represents a state, each edge represents an action. Root node is the initial state, and every child is a successor of its parent, connected by the respective action. Can expand a node by using the Actions function to consider all actions available from that state, and using the Transition Model to determine the resulting state. A state for which a node has been generated (whether expanded or not) is said to have been reached. Three distinct regions of the graph: nodes that have been reached and visited/expanded, nodes that have been reached but not expanded (the frontier), and nodes that have not been reached; the frontier separates the other two. The crux of the search: deciding which node to expand next - depends on how the queue is implemented.\n\nA search tree will contain redundant paths which include multiple different paths from one node to another, as well as cycles. A tree search doesn't not check for redundant paths (i.e. treats different paths to the same node as distinct), but a graph search does, by checking to see if a node has been visited before adding it to the search queue- this requires additional memory.\n\nParameters of a state space are depth (d) - the number of actions in an optimal solution; maximum depth (m) - the maximum number of actions in any path; and the branching factor (b) - the number of successors considered for each node.\n\n```\nGeneral-Tree-Search-Algo(problem) -> solution or failure\n  initialize frontier as some type of queue\n  add initial state to frontier\n  while the frontier is not empty:\n    pop node from frontier\n    if node is goal state:\n      then return node\n    expand node- i.e. for each successor, \n      add to the frontier\n  return failure\n\n\nGeneral-Graph-Search-Algo(problem) -> solution or failure\n  initialize frontier as some type of queue\n  add initial state to frontier\n  initialize explored as empty set\n  while the frontier is not empty:\n    pop node from frontier\n    if node is goal state:\n      then return node\n    add node to explored set\n    expand node- i.e. for each successor, \n      if not in frontier and not in explored\n        add to the frontier\n  return failure\n```\n\nCriteria for evaluating search algorithm performance:\n1)Completeness - a search algorithm is complete if it is guaranteed to find a solution if one exists, and to correctly report a failure if not\n2)(Cost) Optimality - a solution is optimal if it is guaranteed to find the/an optimal solution\n3)Time Complexity\n4)Space Complexity\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nAn uninformed search only has access to the problem definition. Algorithms build a search tree and attempt to find a solution by exploring the tree. They differ in their decision of which node to expand next:\n\n\n<ul>\n<li>Best First Search - selects the node with the minimum cost according to some evaluation function f(n) - priority queue with f(n)</li>\n<li>Bread-First Search - selects the node that was added to the queue first - FIFO queue</li>\n<li>Uniform-Cost Search (aka Dijkstra’s) - selects the node with the lowest path cost g(n) - priority queue with g(n) - uniform because it spreads out in eaves of uniform path cost (wheras breadth first spreads out in waves of uniform depth)</li> \n<li>Depth-First Search - selects the node that was most recently added - LIFO queue (variant with backtracking - only one successor is generated at a time rather than all at the same time, and succeros are generated by modifying the current state rather than copying and changing a new state - reduces memory use)</li>\n<li>Depth Limited - Depth first search, but limit depth to $l$</li>\n<li>Iterative Deepening - keep performing depth limited and increasing $l$ each time; combines benefits of depth first and breadth first search.</li>\n<li>Bidirectional Search - simultaneously search fro initial state forward, and goal state backwards, untl two searches meet.</li> \n</ul>\n\n \n\n## Module 3 Lecture Notes\n \nReflex agent: picks a single action based on a percept at a given time\n\nproblem solving agent: plans ahead - undertakes a serach whic sonideres a sequnence of actions that forms a path from the start to the goal state. this sequence is called a solution\n\nTree search treats different paths to the same node as distinct, in contrast to graph search. Graph search checks to see if a node has been visited before adding it to the search quque. Uninformed search strategies (aka Blind Search) use only information avaialbel in the probelm definition. strategy = order of tree expansion i.e. which node on the frontier shoue we expand next: implemented by using different queue structures for the fronrier/n\nLIFO - Depth first search -/n\nFIFO - Breadthfirst search/n\nPriority - Best first search/n\n\nDepth Limited search:DFS with a depth limit $l$/n\nif $l =d$ (by luck) then optimal/n\nif $l < d$ incomplete/n\nif $l >d$ not optimal/n\n\nIterative Deepening Search: user depth liite search as subroutine and keep increasing $l$\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - the set of all states reachable form the intial state by any sequenc of actions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "An informed search has access to the problem definition and a heuristic function \\\n",
        "$h(n)$ which estimates the (remaining) path cost from the state at node $n$ to a \\\n",
        "goal state. (they may also have access to additional information such as pattern databases).\\n\n",
        "\n",
        "$g(n)=$ the path cost from the initial state to node $n$ \\n\n",
        "$h(n)=$ the estimated path cost from node $n$ to a goal state\\n\n",
        "\n",
        "<ul>\n",
        "<li>**Greedy Best First Search** - selects the node with the minimum h(n) - priority queue with f(n)= h(n)</li>\n",
        "<li>**A* Search** - selects the node with the minimum g(n)+ h(n) - priority queue with f(n)= g(n) + h(n)</li>\n",
        "</ul>\n",
        "\n",
        "A* search is complete and is optimal if the heuristic is **admissible**. A heuristic is \\\n",
        "admissible if it never overestimates the cost to reach a goal (it is optimistic) \\\n",
        "that is $0 \\leq h(n) \\leq h*(n)$ where $h*(n)$ is the true cost to a nearest goal. \\\n",
        "A stronger property is **consistency**; a heuristic is consistent if, for every node \\\n",
        "$n$ and every successor $n’$ of $n$ the following holds $h(n) \\leq c(n,a,n’) + h(n’)$ \\\n",
        "(this is a form of the triangle inequality). A consistent heuristic is admissible, \\\n",
        "but not necessarily vice versa.\\n\n",
        "\n",
        "It's useful to visualize searches as exploring the state space in contours. A* search \\\n",
        "fans out from the start node in concentric bands of increasing $f(n)$ cost. Uniform \\\n",
        "cost search fans out in contours of $g(n)$ cost and will spread out equally in all \\\n",
        "directions (circular) whereas A* will spread out in bands that will stretch increasing \\\n",
        "towards the goal. The A* search lines will monotonically increase iff A* is consistent.  \\\n",
        "If C* is the true cost of the optimal solution, then A* expands all nodes where \\\n",
        "$f(n)< C*$ (these are surely expanded nodes), may expand some nodes where $f(n) = C*$, \\\n",
        "and will NOT expand any nodes where $f(n) > C*$. This means that A* is optimally efficiency; \\\n",
        "any algorithm that starts for the initial state and uses the same heuristic must \\\n",
        "expand all nodes that are “surely expanded” by A*. \n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "The quality of a heuristic has a significant impact on the performance of the algorithm. \\\n",
        "One way we characterize this is using the effective branching factor b*. b* is the \\\n",
        "branching factor of a a uniform tree with N nodes and depth d, where N is the number \\\n",
        "of nodes generated by the A* search and d is the solution depth. The lower the effective \\\n",
        "branching factor the better. We say a heuristic $h_2$ dominates another heuristic $h_1$ \\\n",
        "if for any node $n$, $h_2(n) \\geq h_1(n)$. Domination translates directly into efficiency. \\\n",
        "Recall that every node with $f(n) < C*$ is surely expanded; when h is consistent, this is \\\n",
        "the same as saying every node with $h(n) < C* - g(n)$ is surely expanded. If a node is \\\n",
        "surely expanded by $h2$ it will also be surely expanded by $h_1$,  since $h_1 \\leq h_2$, \\\n",
        "but $h_1$ may even expand more nodes. Therefore $h_2$ will always expand fewer nodes than \\\n",
        "$h_1$. Therefore it is generally better to use a heuristic with higher values, as long as \\\n",
        "it's still consistent and it doesn’t take too long to compute.\\n   \n",
        "\n",
        "Another suggested way to characterize this impact is that heuristic reduces the \\\n",
        "effective depth of an A* search by a constant $k_h$, so that the total search is $O(b^{d-k_h})$\\n\n",
        "\n",
        "We can typically construct good heuristics from relaxed problems. Relaxed problems \\\n",
        "are problems similar to the one we are considering, with fewer restrictions on the \\\n",
        "actions. By removing restrictions we strictly increase edges to our state-space graph \\\n",
        "(we will never remove edges) and our relaxed state-space graph is a supergraph of our \\\n",
        "original problem. This means that any optimal solution in this new relaxed problem \\\n",
        "will be at least as good as a solution in our original problem. Therefore, the cost \\\n",
        "of an optimal solution to the relaxed problem is an admissible heuristic for the \\\n",
        "original problem. Additionally, because its an exact cost, it must obey the triangle \\\n",
        "inequality and is therefore consistent.\\n \n",
        "\n",
        "Other ways of generating heuristics are:\\n\n",
        "<ul>\n",
        "<li>From subproblems, using pattern databases to store the exact solutions fore every possible subproblem.</li>\n",
        "<li>Using landmarks - we precompute and store the optimal paths between a handful of landmark points.</li>\n",
        "</ul>\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "A* is efficient because it prunes the search tree, avoiding nodes that are not necessary \\\n",
        "for finding an optimal solution. A* is good, complete, cost optimal, and optimally efficient \\\n",
        "(given a consistent heuristic), but the number of nodes expanded can still be exponential in \\\n",
        "the length of the solution. If we accept satisficing solutions (suboptimal but still ‘good enough’), \\\n",
        "we can explore fewer nodes and reduce the time and space complexity. An inadmissible heuristic, \\\n",
        "while risking missing the optimal solution, could potentially be more accurate, therefore \\\n",
        "reducing the number of nodes examined. This leads to the weighted A* search; we give the \\\n",
        "heuristic function more weight, thus focusing the search contour more towards the goal, \\\n",
        "and exploring fewer states $f(n) = g(n) + Wh(n)$. We may miss the optimal path if it’s \\\n",
        "outside the weighted search contour, but the search will be much faster. This can actually \\\n",
        "be seen as a generalization of A* (W=1), Uniform cost search (W=0) and greedy best-first (W=infinity).\\n \n",
        "\n",
        "Main issue with A* is the use of memory. Memory is split between the frontier \\\n",
        "and the reached states. A state in the frontier is stored in both; as a node in \\\n",
        "the frontier (so we can decide if we should expand it) and as an entry in the table \\\n",
        "of reached states (so we know if it has been visited). Some potential solutions:\\n\n",
        "<ul>\n",
        "<li>keep a state only in one of the two places (less space, but more time)</li>\n",
        "<li>eliminate reached altogether</li>\n",
        "<li>remove states from reached when they are no longer needed e.g. keep a reference \\\n",
        "count of the number of times a state has been reached and remove it when there are no \\\n",
        "more ways to reach it</li>   \n",
        "</ul>\n",
        "Other memory conserving algorithms:\n",
        "<ul>\n",
        "<li>Beam search - limits the size of the frontier. e.g. keep only k nodes with the \\\n",
        "best f(n). OR keep every node with f(n) within some delta of the best f(n). </li>\n",
        "<li>Iterative deepening A* - the cutoff for each iteration is the smallest f(n) \\\n",
        "that exceeded the cutoff on the previous iteration. This way we don’t have to keep \\\n",
        "all reached states in memory, though we may visit some states multiple times</li>\n",
        "<li> Recursive best first search (RBFS) - recursively explores a path keeping track \\\n",
        "of the best alternative f(n) available from any ancestor of the current node. If the \\\n",
        "current node exceeds this f(n), the recursion unwids back to an alternative back and \\\n",
        "replaces f(n) for each node with a backed-up value (best f(n) of its children). </li>\n",
        "<li>Memory bounded A* (MA*)</li>\n",
        "<li>Simplified MA* (SMA*) </li>\n",
        "</ul>\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 112,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "c9b7de15-24de-4b11-c94f-60125d901d22"
      },
      "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": 113,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nAn informed search has access to the problem definition and a heuristic function $h(n)$ which estimates the (remaining) path cost from the state at node $n$ to a goal state. (they may also have access to additional information such as pattern databases).\n\n\n$g(n)=$ the path cost from the initial state to node $n$ \n\n$h(n)=$ the estimated path cost from node $n$ to a goal state\n\n\n<ul>\n<li>**Greedy Best First Search** - selects the node with the minimum h(n) - priority queue with f(n)= h(n)</li>\n<li>**A* Search** - selects the node with the minimum g(n)+ h(n) - priority queue with f(n)= g(n) + h(n)</li>\n</ul>\n\nA* search is complete and is optimal if the heuristic is **admissible**. A heuristic is admissible if it never overestimates the cost to reach a goal (it is optimistic) that is $0 \\leq h(n) \\leq h*(n)$ where $h*(n)$ is the true cost to a nearest goal. A stronger property is **consistency**; a heuristic is consistent if, for every node $n$ and every successor $n’$ of $n$ the following holds $h(n) \\leq c(n,a,n’) + h(n’)$ (this is a form of the triangle inequality). A consistent heuristic is admissible, but not necessarily vice versa.\n\n\nIt's useful to visualize searches as exploring the state space in contours. A* search fans out from the start node in concentric bands of increasing $f(n)$ cost. Uniform cost search fans out in contours of $g(n)$ cost and will spread out equally in all directions (circular) whereas A* will spread out in bands that will stretch increasing towards the goal. The A* search lines will monotonically increase iff A* is consistent.  If C* is the true cost of the optimal solution, then A* expands all nodes where $f(n)< C*$ (these are surely expanded nodes), may expand some nodes where $f(n) = C*$, and will NOT expand any nodes where $f(n) > C*$. This means that A* is optimally efficiency; any algorithm that starts for the initial state and uses the same heuristic must expand all nodes that are “surely expanded” by A*. \n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \nThe quality of a heuristic has a significant impact on the performance of the algorithm. One way we characterize this is using the effective branching factor b*. b* is the branching factor of a a uniform tree with N nodes and depth d, where N is the number of nodes generated by the A* search and d is the solution depth. The lower the effective branching factor the better. We say a heuristic $h_2$ dominates another heuristic $h_1$ if for any node $n$, $h_2(n) \\geq h_1(n)$. Domination translates directly into efficiency. Recall that every node with $f(n) < C*$ is surely expanded; when h is consistent, this is the same as saying every node with $h(n) < C* - g(n)$ is surely expanded. If a node is surely expanded by $h2$ it will also be surely expanded by $h_1$,  since $h_1 \\leq h_2$, but $h_1$ may even expand more nodes. Therefore $h_2$ will always expand fewer nodes than $h_1$. Therefore it is generally better to use a heuristic with higher values, as long as it's still consistent and it doesn’t take too long to compute.\n   \n\nAnother suggested way to characterize this impact is that heuristic reduces the effective depth of an A* search by a constant $k_h$, so that the total search is $O(b^{d-k_h})$\n\n\nWe can typically construct good heuristics from relaxed problems. Relaxed problems are problems similar to the one we are considering, with fewer restrictions on the actions. By removing restrictions we strictly increase edges to our state-space graph (we will never remove edges) and our relaxed state-space graph is a supergraph of our original problem. This means that any optimal solution in this new relaxed problem will be at least as good as a solution in our original problem. Therefore, the cost of an optimal solution to the relaxed problem is an admissible heuristic for the original problem. Additionally, because its an exact cost, it must obey the triangle inequality and is therefore consistent.\n \n\nOther ways of generating heuristics are:\n\n<ul>\n<li>From subproblems, using pattern databases to store the exact solutions fore every possible subproblem.</li>\n<li>Using landmarks - we precompute and store the optimal paths between a handful of landmark points.</li>\n</ul>\n\n \n\n## Module 4 Lecture Notes\n \nA* is efficient because it prunes the search tree, avoiding nodes that are not necessary for finding an optimal solution. A* is good, complete, cost optimal, and optimally efficient (given a consistent heuristic), but the number of nodes expanded can still be exponential in the length of the solution. If we accept satisficing solutions (suboptimal but still ‘good enough’), we can explore fewer nodes and reduce the time and space complexity. An inadmissible heuristic, while risking missing the optimal solution, could potentially be more accurate, therefore reducing the number of nodes examined. This leads to the weighted A* search; we give the heuristic function more weight, thus focusing the search contour more towards the goal, and exploring fewer states $f(n) = g(n) + Wh(n)$. We may miss the optimal path if it’s outside the weighted search contour, but the search will be much faster. This can actually be seen as a generalization of A* (W=1), Uniform cost search (W=0) and greedy best-first (W=infinity).\n \n\nMain issue with A* is the use of memory. Memory is split between the frontier and the reached states. A state in the frontier is stored in both; as a node in the frontier (so we can decide if we should expand it) and as an entry in the table of reached states (so we know if it has been visited). Some potential solutions:\n\n<ul>\n<li>keep a state only in one of the two places (less space, but more time)</li>\n<li>eliminate reached altogether</li>\n<li>remove states from reached when they are no longer needed e.g. keep a reference count of the number of times a state has been reached and remove it when there are no more ways to reach it</li>   \n</ul>\nOther memory conserving algorithms:\n<ul>\n<li>Beam search - limits the size of the frontier. e.g. keep only k nodes with the best f(n). OR keep every node with f(n) within some delta of the best f(n). </li>\n<li>Iterative deepening A* - the cutoff for each iteration is the smallest f(n) that exceeded the cutoff on the previous iteration. This way we don’t have to keep all reached states in memory, though we may visit some states multiple times</li>\n<li> Recursive best first search (RBFS) - recursively explores a path keeping track of the best alternative f(n) available from any ancestor of the current node. If the current node exceeds this f(n), the recursion unwids back to an alternative back and replaces f(n) for each node with a backed-up value (best f(n) of its children). </li>\n<li>Memory bounded A* (MA*)</li>\n<li>Simplified MA* (SMA*) </li>\n</ul>\n\n\n\n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "Three approaches to multi-agent envoronments\\n\n",
        "<ol>\n",
        "<li>Consider them in aggregate as an economy, without predicting the action of each individual agent</li>\n",
        "<li>Consider agents as part of the environment (their behaviro would represent a nondeterministic \\\n",
        "aspect of the environment). But this ignores that adversarial agents are working actively against us </li>\n",
        "<li>Explicitly model agents  - in this module we do so with adversarial agent in a game tree</li>\n",
        "</ol>\n",
        "Games we typically study are \n",
        "<ol>\n",
        "<li>deterministic</li>\n",
        "<li>two player; with players taking turns</li>\n",
        "<li>zero sum; what's good for one player is bad for the other</li>\n",
        "<li>perfect information; i.e. fully observable</li>\n",
        "</ol>\n",
        "A game can be formally ydefined with the following elements:\\n\n",
        "$S_0$: the **initial state**, specifies how the game is set up at the start\\n\n",
        "To-Move($s$): the player whose turn it is to move in state $s$\\n\n",
        "Action($s$): the set of legal moves in state $s$\\n\n",
        "Result($s$,$a$): the **transition model** that defines which state results from the action $a$ in the current state $s$\\n\n",
        "Is-Terminal($s$): the **terminal test** which indicates when the game is over (i.e. has reached a **terminal state**)\\n\n",
        "Utility($s$,$p$): the **utility function** which defines the numerical value of a terminal state, $s$, to player $p$\\n\n",
        "\n",
        "Similarly to search problems, we can generate a game tree with states as nodes \\\n",
        "moves as edges, and the root as the initial state. However in our game each successive \\\n",
        "layer of the game tree (a **ply**) reprsents a different palyers turn. \n",
        "\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "<h3>Minimax</h3>\n",
        "we define two players: MAX and MIN\\n\n",
        "The score is kept from MAX's viewpoint, so MAX tries to maximize the score and MIN tries to minimize it. \\\n",
        "They take turns playing, and we typiically ssume MAX moves first. When represented as a \\\n",
        "Tree, each successive ply (i.e. level) represents the other player's turn. They keep alternating, \\\n",
        "until a terminal state is reached. At this point we can call the Utility function to determine the \\\n",
        "value of the terminal node.\\n\n",
        "The **minimax search algorithm** computes the  **minimax value** at each node recusively \\\n",
        "by working from the terminal states back up to the root. The minimax value at the terminal nodes \\\n",
        "is given by the Utility function. Then as we work our way up the tree, each MIN node chooses the \\\n",
        "minimal value of it's children, and each MAX node chooses the maximal value of its children (called the **backed up** values) \\\n",
        "until we get back up to the root. **a key assumption is that both players play optimally**.  This algorithm \\\n",
        "has a time complexity of $O(b^m)$ and a space complexity of $O(bm)$ (if all actions are generated at once) or \\\n",
        "$O(m)$ (if actions are generated one at a time).\\n\n",
        "\n",
        "<h3>Alpha-Beta Pruning</h3>\n",
        "We introduce two variables that allow us to ignore certain portions of the game subtree \\\n",
        "that will not be fruitful. This process is called **pruning**. \\n\n",
        "$\\\\alpha$ = the value of MAX's best choice so far (i.e. at any node along the path from the \\\n",
        "current node to the root): MAX will get **at least** $\\\\alpha$\\n\n",
        "$\\\\beta$ = the value of MIN's best choice so far (i.e. at any node along the path from the \\\n",
        "current node to the root): MIN can limit MAX to **at most** $\\\\beta$\\n\n",
        "\n",
        "When evaluating a MAX node: if a value $\\\\geq \\\\beta$ we can stop evaluating (MIN will never select this MAX node)\n",
        "\n",
        "When evaluating a MIN node: if a value $\\\\leq \\\\alpha$ we can stop evaluating (MAX will never select this MIN node)\\n\n",
        "\n",
        "For multiplayer games, we replace the single value of each node with a vector of values \\\n",
        "representing the utility of the state for each player. Then the utility of an internal node \\\n",
        "is typicially the utility vector of the successor sate with the highest value for the player \\\n",
        "choosing at that time. \n",
        "\n",
        "The effectivenes of alpha-beta pruning depends on the order in which states are examined; it would \\\n",
        "be better to examine the best possible successors first. If done perfectly, alpha beta could \\\n",
        "examine only $O(b^{m/2})$ (rather than $O(b^{m})$ for plain minimax). Can try and determine order \\\n",
        "of good moves (e.g. chess - captures > threats > forward moves > backward moves). Can also use \\\n",
        "iterative deepening and use previous exploration to determine best moves.\n",
        "\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "To make the search more time-effective, we can modify it in two ways:\\n\n",
        "1) replace the Utility function with a heuristic **evaluation function** \\\n",
        "(treat nonterminal nodes as terminal)\\n\n",
        "2) replace the terminal test with a **cutoff test** which returns true for terminal \\\n",
        "states and when search should stop; depth and state properties\\n\n",
        "<h3>Evaluation Funcitons</h3>\n",
        "the *heuristic* evaluation function, $Eval(s,p)$, returns an estimate of the expected utility \\\n",
        "of the state $s$ to player $p$.\n",
        "<ul>\n",
        "<li>Terminal States - $Eval(s,p)=Utility(s,p) $ </li>\n",
        "<li>Non-terminal States - $Utility(loss,p) \\\\leq Eval(s,p) \\\\leq Utility(win,p) $ </li>\n",
        "</ul>\n",
        "Criteria for good evaluation function\n",
        "<ul>\n",
        "<li>quick computation</li>\n",
        "<li>strongly correlated with actual chances of winning</li>\n",
        "</ul>\n",
        "Most evaluation functions calculate features of a state\\\n",
        "and use these features to defined categories of states. In theory, an \\\n",
        "**expected value** for each category could be computed based on the proportion of states with \\\n",
        "a given outcome. However in practice, this is not feasible and instead a numerical contribution \\\n",
        "(an approximate **material value**) is estimated for each feature and combined into a total value; \\\n",
        " called a **weighted linear function** and can be writtend as:\n",
        "$Eval(s) = w_1f_1(s)+w_2f_2(s)+...+w_nf_n(s)= \\\\sum_{i=1}^{n}w_if_i(s) $\n",
        "Where $f_i$ is a feature (e.g. number of which bishops) and $w_i$ is a weight indicating how \\\n",
        "important that feature is. Weights should be normalized so that the sum is always between 0 and 1. \\\n",
        "Adding the features in this way assumes that the contribution of each feature is indepedent of each other \\\n",
        "which may not be true, in ehich case non-linear combinations might be used instead. Features and weights \\\n",
        "typically come from human experience, or from machine learning. \n",
        "<h3>Cutoff</h3>\n",
        "Instead of checking for a terminal state, we check for cutoff conditions. \\\n",
        "however if we we just limit the depth of the search, we may missjudge the true value of a state, therefore \\\n",
        "the evaluation function should only be applied to states that are **quiescent** meaning there is no pending \\\n",
        "move that could drastically affect the evaluation. The **horizon effect** occurs when the program simply \\\n",
        "delays an inevitable move by pushing it beyond the horizon. A fix is **singular extension** \\\n",
        "allowing \"clearly better moves\" to extend search depth.\n",
        "<h3>Forward Pruning</h3>\n",
        "saves computation tume by attempting to prune poor moves. \\\n",
        "beam search - consider only $n$ best moves; ProbCut - using past experience to estimate if nodes will probably be outside the \\\n",
        "alpha-beta window; late move reduction - assuming that moves are ordered (best to worst) reduce the depth \\\n",
        "of search for later moves\n",
        "<h3>Search vs Lookup</h3>\n",
        "Sometimes it makes sense to just create lookup tabels. e.g. chess opening and closings \\\n",
        "have fewer possible positions and have well documented plays and we can rely on human expertise \\\n",
        "rather than wasting computing time.\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "Similar to minimax game tree but now we have chance nodes, in addition to MIN and MAX nodes. \\\n",
        "each child represents a possible outcome and has an associated probablility. So we calculate \\\n",
        "an **expected** value for this node as the wieghted average of possible outcomes. This then \\\n",
        "leads to an overall **expectiminimax value**. The presence of chances nodes changes the impact \\\n",
        "that the evaluation funciton has on the final outcome; we have to be more careful about what \\\n",
        "values mean. the evaluation function should return values that are a positive linear transformation \\\n",
        "of the probablility of winning (the the expected utility). \n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "Evaluation fucntion f assignes real-number scores to board withough references to path \\\n",
        "(i.e. don't care how we got there). Terminal nodes represent ways the game could end, and are \\\n",
        "labeled with the desirability of that ending.\\n\n",
        "The minimax rule: don't play hope chess (i.e. assume MIN always replies with best move for MIN), \\\n",
        "backed-up value - recursive process. it is the optimal value of children:\\n\n",
        "for MAX - the maximun of children\\n\n",
        "for MIN - the minimum of children\\n\n",
        "\n",
        "Minimax Procedure:\\n\n",
        "<ol>\n",
        "<li>start with current position (as MAX)</li>\n",
        "<li>expand the game a fixed number of plies</li>\n",
        "<li>apply the evaluation functio at leaf nodes</li>\n",
        "<li>calculate the back up value from the bottom up</li>\n",
        "<li>pick the move assigned to MAX at the root</li>\n",
        "<li>wait for MIN to respond</li>\n",
        "</ol>\n",
        "we can't expand the entire game tree because the stat-space is typically too large. \\n\n",
        "\n",
        "Expecitmax\\n\n",
        "games iwht uncertain outcomes (e.g. dice, cards). consider uncertian outcomes controlled by chance \\\n",
        "rather than an adversary. Game tree is similar to minimax, with the addition of chance nodes. \\n\n",
        "chance nodes - calculate the expected utilites (wighted average)\\n\n",
        "MAX/MIN nodes - same as before\\n\n",
        "overall we compute the average score under optimal play. It is much harder to prune here.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 114,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "103815a2-4b0b-4daf-e635-3a5a8f54b90f"
      },
      "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": 115,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nThree approaches to multi-agent envoronments\n\n<ol>\n<li>Consider them in aggregate as an economy, without predicting the action of each individual agent</li>\n<li>Consider agents as part of the environment (their behaviro would represent a nondeterministic aspect of the environment). But this ignores that adversarial agents are working actively against us </li>\n<li>Explicitly model agents  - in this module we do so with adversarial agent in a game tree</li>\n</ol>\nGames we typically study are \n<ol>\n<li>deterministic</li>\n<li>two player; with players taking turns</li>\n<li>zero sum; what's good for one player is bad for the other</li>\n<li>perfect information; i.e. fully observable</li>\n</ol>\nA game can be formally ydefined with the following elements:\n\n$S_0$: the **initial state**, specifies how the game is set up at the start\n\nTo-Move($s$): the player whose turn it is to move in state $s$\n\nAction($s$): the set of legal moves in state $s$\n\nResult($s$,$a$): the **transition model** that defines which state results from the action $a$ in the current state $s$\n\nIs-Terminal($s$): the **terminal test** which indicates when the game is over (i.e. has reached a **terminal state**)\n\nUtility($s$,$p$): the **utility function** which defines the numerical value of a terminal state, $s$, to player $p$\n\n\nSimilarly to search problems, we can generate a game tree with states as nodes moves as edges, and the root as the initial state. However in our game each successive layer of the game tree (a **ply**) reprsents a different palyers turn. \n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n<h3>Minimax</h3>\nwe define two players: MAX and MIN\n\nThe score is kept from MAX's viewpoint, so MAX tries to maximize the score and MIN tries to minimize it. They take turns playing, and we typiically ssume MAX moves first. When represented as a Tree, each successive ply (i.e. level) represents the other player's turn. They keep alternating, until a terminal state is reached. At this point we can call the Utility function to determine the value of the terminal node.\n\nThe **minimax search algorithm** computes the  **minimax value** at each node recusively by working from the terminal states back up to the root. The minimax value at the terminal nodes is given by the Utility function. Then as we work our way up the tree, each MIN node chooses the minimal value of it's children, and each MAX node chooses the maximal value of its children (called the **backed up** values) until we get back up to the root. **a key assumption is that both players play optimally**.  This algorithm has a time complexity of $O(b^m)$ and a space complexity of $O(bm)$ (if all actions are generated at once) or $O(m)$ (if actions are generated one at a time).\n\n\n<h3>Alpha-Beta Pruning</h3>\nWe introduce two variables that allow us to ignore certain portions of the game subtree that will not be fruitful. This process is called **pruning**. \n\n$\\alpha$ = the value of MAX's best choice so far (i.e. at any node along the path from the current node to the root): MAX will get **at least** $\\alpha$\n\n$\\beta$ = the value of MIN's best choice so far (i.e. at any node along the path from the current node to the root): MIN can limit MAX to **at most** $\\beta$\n\n\nWhen evaluating a MAX node: if a value $\\geq \\beta$ we can stop evaluating (MIN will never select this MAX node)\n\nWhen evaluating a MIN node: if a value $\\leq \\alpha$ we can stop evaluating (MAX will never select this MIN node)\n\n\nFor multiplayer games, we replace the single value of each node with a vector of values representing the utility of the state for each player. Then the utility of an internal node is typicially the utility vector of the successor sate with the highest value for the player choosing at that time. \n\nThe effectivenes of alpha-beta pruning depends on the order in which states are examined; it would be better to examine the best possible successors first. If done perfectly, alpha beta could examine only $O(b^{m/2})$ (rather than $O(b^{m})$ for plain minimax). Can try and determine order of good moves (e.g. chess - captures > threats > forward moves > backward moves). Can also use iterative deepening and use previous exploration to determine best moves.\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nTo make the search more time-effective, we can modify it in two ways:\n\n1) replace the Utility function with a heuristic **evaluation function** (treat nonterminal nodes as terminal)\n\n2) replace the terminal test with a **cutoff test** which returns true for terminal states and when search should stop; depth and state properties\n\n<h3>Evaluation Funcitons</h3>\nthe *heuristic* evaluation function, $Eval(s,p)$, returns an estimate of the expected utility of the state $s$ to player $p$.\n<ul>\n<li>Terminal States - $Eval(s,p)=Utility(s,p) $ </li>\n<li>Non-terminal States - $Utility(loss,p) \\leq Eval(s,p) \\leq Utility(win,p) $ </li>\n</ul>\nCriteria for good evaluation function\n<ul>\n<li>quick computation</li>\n<li>strongly correlated with actual chances of winning</li>\n</ul>\nMost evaluation functions calculate features of a stateand use these features to defined categories of states. In theory, an **expected value** for each category could be computed based on the proportion of states with a given outcome. However in practice, this is not feasible and instead a numerical contribution (an approximate **material value**) is estimated for each feature and combined into a total value;  called a **weighted linear function** and can be writtend as:\n$Eval(s) = w_1f_1(s)+w_2f_2(s)+...+w_nf_n(s)= \\sum_{i=1}^{n}w_if_i(s) $\nWhere $f_i$ is a feature (e.g. number of which bishops) and $w_i$ is a weight indicating how important that feature is. Weights should be normalized so that the sum is always between 0 and 1. Adding the features in this way assumes that the contribution of each feature is indepedent of each other which may not be true, in ehich case non-linear combinations might be used instead. Features and weights typically come from human experience, or from machine learning. \n<h3>Cutoff</h3>\nInstead of checking for a terminal state, we check for cutoff conditions. however if we we just limit the depth of the search, we may missjudge the true value of a state, therefore the evaluation function should only be applied to states that are **quiescent** meaning there is no pending move that could drastically affect the evaluation. The **horizon effect** occurs when the program simply delays an inevitable move by pushing it beyond the horizon. A fix is **singular extension** allowing \"clearly better moves\" to extend search depth.\n<h3>Forward Pruning</h3>\nsaves computation tume by attempting to prune poor moves. beam search - consider only $n$ best moves; ProbCut - using past experience to estimate if nodes will probably be outside the alpha-beta window; late move reduction - assuming that moves are ordered (best to worst) reduce the depth of search for later moves\n<h3>Search vs Lookup</h3>\nSometimes it makes sense to just create lookup tabels. e.g. chess opening and closings have fewer possible positions and have well documented plays and we can rely on human expertise rather than wasting computing time.\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \nSimilar to minimax game tree but now we have chance nodes, in addition to MIN and MAX nodes. each child represents a possible outcome and has an associated probablility. So we calculate an **expected** value for this node as the wieghted average of possible outcomes. This then leads to an overall **expectiminimax value**. The presence of chances nodes changes the impact that the evaluation funciton has on the final outcome; we have to be more careful about what values mean. the evaluation function should return values that are a positive linear transformation of the probablility of winning (the the expected utility). \n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n \nEvaluation fucntion f assignes real-number scores to board withough references to path (i.e. don't care how we got there). Terminal nodes represent ways the game could end, and are labeled with the desirability of that ending.\n\nThe minimax rule: don't play hope chess (i.e. assume MIN always replies with best move for MIN), backed-up value - recursive process. it is the optimal value of children:\n\nfor MAX - the maximun of children\n\nfor MIN - the minimum of children\n\n\nMinimax Procedure:\n\n<ol>\n<li>start with current position (as MAX)</li>\n<li>expand the game a fixed number of plies</li>\n<li>apply the evaluation functio at leaf nodes</li>\n<li>calculate the back up value from the bottom up</li>\n<li>pick the move assigned to MAX at the root</li>\n<li>wait for MIN to respond</li>\n</ol>\nwe can't expand the entire game tree because the stat-space is typically too large. \n\n\nExpecitmax\n\ngames iwht uncertain outcomes (e.g. dice, cards). consider uncertian outcomes controlled by chance rather than an adversary. Game tree is similar to minimax, with the addition of chance nodes. \n\nchance nodes - calculate the expected utilites (wighted average)\n\nMAX/MIN nodes - same as before\n\noverall we compute the average score under optimal play. It is much harder to prune here.\n \n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NoT2HcA0jTux"
      },
      "source": [
        ""
      ],
      "execution_count": 115,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FP0izLrnjUAY"
      },
      "source": [
        ""
      ],
      "execution_count": 115,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "CSP consists of three components:\n",
        "<ul>\n",
        "<li> $X$ a set of variables</li>\n",
        "<li> $D$ a set of domains, one for each variable</li>\n",
        "<li> $C$ a set of constraints that specify allowable combinations of values</li>\n",
        "</ul>\n",
        "CSPs deal with assignment of values to each variable. A **consistent** or legal assignment \\\n",
        "does not violate any of the constraints. A **complete** assignment is one in which every \\\n",
        "variable is assigned a value. A **solution** is a consistent, complete assignment. A \\\n",
        "**partial assignment** leaves some variables unassigned. A **partial solution** is a \\\n",
        "conistent partial assignment.\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "CSP algorithm generates successors by choosing a new variable assignemnt OR by \\\n",
        "constraint propagation, a specific type of inference which uses the constraints \\\n",
        "to reduce the number of legal values for a variable, which in turn can reduce the \\\n",
        "legal values for other variables. If we treat each variable as a node in a graph, \\\n",
        "and constraints as edges, then enforcing local consistency causes values to be \\\n",
        "eliminated.\n",
        "<ul>\n",
        "<li> node consistency - all values in a variables domain satisfy unary constraints</li>\n",
        "<li> arc consistency - all values in a variables domain satisfy binary constraints</li>\n",
        "<li> path consistency - uses implocty constraints inferred by looking at variable triples</li>\n",
        "<li> k-consistency - for any set of $k-1$ variables, and for any consistent assignment to those variables \\\n",
        "a conistent value can always be assigned to any $kth$ variable</li>\n",
        "</ul>\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "Backtracking search is a form of depth-first search, commonly used for solving CSPs. \\\n",
        "CSPs are commutative, therefore we need only consider one variable assignment at a time. \\\n",
        "so a backtracking search repeatedly makes an assignment for an unassigned variable, and continues \\\n",
        "untill either a solution is found, or it fails. If it fails, then we \"backtrack\" and try another \\\n",
        "path.\n",
        "\n",
        "we can interleave this searching algorithm with inferencing. Each time we make an assignment \\\n",
        "we go as far as we can with inferencing. Forward checking is a simple form of inference \\\n",
        "which establishes arc-consistency everytime a variable is assigned.\n",
        "\n",
        "MAC (maintaining arc consistency) is an algorithm that detects inconsistencies by doing \\\n",
        "the following: when a variable $X_i$ is assigned, inference calls AC-3, but starts only with arcs \\\n",
        "(X_i,X_j), for $X_j$s that are unassigned. AC-3 does constraint propogation per usual and if any \\\n",
        "domain is reduced to the empty set, it returns a failure and we backtrack. Forward checking does not \\\n",
        "recursively propogate constraints like MAC.\n",
        "\n",
        "This standard backtracking is \"chronological\" but it would be better to backtrack to \\\n",
        "a variable that may fix the problem; we can do this by keeping track of a conflict set \\\n",
        "and backjumping to the most recent assignment in the conflict set.\n",
        "\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "Min-Conflict \\n\n",
        "1) start with a complete assigment (it will have constraint violations)\\n\n",
        "2) randomly choose a conflicted variable; select a new value that results in \\\n",
        "the minimum number of comflicts with other variables\\n\n",
        "3) keep doing this until we've eliminated all conflicts\n",
        "\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "Complexity of CSPs is strongly related to the structure of its constrain graph. \\\n",
        "we could break down CSPs into independent problems based on their connected compoenents \\\n",
        "then solve thes individually. It is rare though to have many independent subproblems. \\\n",
        "Another more easily solvable structure is a tree; any tree-structured CSP can be solved in linear time \\\n",
        "w.r.t. the number of variables.\\n\n",
        "\n",
        "Cutset conditioning is a way to reduce a contraint graph to a tree. We assign values to \\\n",
        "some variables so that the remaining variables for a tree. Requires finding such a set of \\\n",
        "of variables called a cycle cutset. \\n\n",
        "\n",
        "Tree decomposition is a second eay to reduce a constraint graph to a tree. we transform \\\n",
        "the original grpah into a tree where each node consists of a set of variables./n\n",
        "\n",
        "Decomposition has time $O(d^c (n-c)d^2)$ (where $c$ is cycle-cutset size). Tree decomposition \\\n",
        "has time $O(nd^{w+1})$ (where $w$ is the tree width). whenever you have a cycle-cutset size $c$ \\\n",
        "you also have a tree width size $w < c+1$, so tree decomposition is usually better time complexity. \\\n",
        "but cutset has linear memory while tree decomposition time complexity is exponential is $w$.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "CSP components:\\n\n",
        "finite set of variables\\n\n",
        "non-empty domain of possible values ofr each variable\\n\n",
        "finite set of constraints which limit the values that variables can have\\n\n",
        "Solutions to CSPs can be found by a completely general purpose algorithm, just need to \\\n",
        "formally specify the problem.\\n\n",
        "maximizing objective function - beyond the scope of the class\\n\n",
        "Benefits of csp: 1) clean specification of many problems 2) csp knows which variable \\\n",
        "violates a contraint and therefore where to focus the search 3) csp automatically prunes \\\n",
        "branches that violate constraints.\\n\n",
        "AC3 - a more efficient version of arc-consistency.\\n\n",
        "heuristic 1) most constrained variable - choose the variable with the fewest legal values \\\n",
        "(aka minimum remaining value MRV heuristic)\\n\n",
        "heuristic 2) most constrining variable - tie breaker among constrained variables, choose the \\\n",
        "variable with the most constraints on the remaining variables\\n\n",
        "heuristic 3) least constraining value - given the variable, choose the least constraining value: \\\n",
        "i.e. the one that rules out the fewese values in the remaining variables\\n\n",
        "heuristic 4) forward checking - keep track of remaining legal values for unassigned variables. \\\n",
        "terminate the search when any assigned variable has no remaining legal values.\\n\n",
        "\n",
        "Constrait propagation goes beyond forward cheking and repeatedly enforces constraints locally. \\\n",
        "Arc-consistency, the simplest form of propagation makes each arc consistent. AC-3 is improved \\\n",
        "algorithm\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"consistent\": \"assignment does not violate constraints\",\n",
        "\"complete\" : \"all variables are assigned\",\n",
        "\"solution\": \"complete and consistent assignment\",\n",
        "\"unary constraint\" : \"restricts a single variable\",\n",
        "\"binary constraint\": \"constraint between two variables\",\n",
        "\"global constraint\": \"constraint between an arbitrary number of variables\"    \n",
        "}\n"
      ],
      "execution_count": 116,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0be14592-cab3-4019-d0d9-91fefdb6638b"
      },
      "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": 117,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nCSP consists of three components:\n<ul>\n<li> $X$ a set of variables</li>\n<li> $D$ a set of domains, one for each variable</li>\n<li> $C$ a set of constraints that specify allowable combinations of values</li>\n</ul>\nCSPs deal with assignment of values to each variable. A **consistent** or legal assignment does not violate any of the constraints. A **complete** assignment is one in which every variable is assigned a value. A **solution** is a consistent, complete assignment. A **partial assignment** leaves some variables unassigned. A **partial solution** is a conistent partial assignment.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nCSP algorithm generates successors by choosing a new variable assignemnt OR by constraint propagation, a specific type of inference which uses the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for other variables. If we treat each variable as a node in a graph, and constraints as edges, then enforcing local consistency causes values to be eliminated.\n<ul>\n<li> node consistency - all values in a variables domain satisfy unary constraints</li>\n<li> arc consistency - all values in a variables domain satisfy binary constraints</li>\n<li> path consistency - uses implocty constraints inferred by looking at variable triples</li>\n<li> k-consistency - for any set of $k-1$ variables, and for any consistent assignment to those variables a conistent value can always be assigned to any $kth$ variable</li>\n</ul>\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nBacktracking search is a form of depth-first search, commonly used for solving CSPs. CSPs are commutative, therefore we need only consider one variable assignment at a time. so a backtracking search repeatedly makes an assignment for an unassigned variable, and continues untill either a solution is found, or it fails. If it fails, then we \"backtrack\" and try another path.\n\nwe can interleave this searching algorithm with inferencing. Each time we make an assignment we go as far as we can with inferencing. Forward checking is a simple form of inference which establishes arc-consistency everytime a variable is assigned.\n\nMAC (maintaining arc consistency) is an algorithm that detects inconsistencies by doing the following: when a variable $X_i$ is assigned, inference calls AC-3, but starts only with arcs (X_i,X_j), for $X_j$s that are unassigned. AC-3 does constraint propogation per usual and if any domain is reduced to the empty set, it returns a failure and we backtrack. Forward checking does not recursively propogate constraints like MAC.\n\nThis standard backtracking is \"chronological\" but it would be better to backtrack to a variable that may fix the problem; we can do this by keeping track of a conflict set and backjumping to the most recent assignment in the conflict set.\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nMin-Conflict \n\n1) start with a complete assigment (it will have constraint violations)\n\n2) randomly choose a conflicted variable; select a new value that results in the minimum number of comflicts with other variables\n\n3) keep doing this until we've eliminated all conflicts\n\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nComplexity of CSPs is strongly related to the structure of its constrain graph. we could break down CSPs into independent problems based on their connected compoenents then solve thes individually. It is rare though to have many independent subproblems. Another more easily solvable structure is a tree; any tree-structured CSP can be solved in linear time w.r.t. the number of variables.\n\n\nCutset conditioning is a way to reduce a contraint graph to a tree. We assign values to some variables so that the remaining variables for a tree. Requires finding such a set of of variables called a cycle cutset. \n\n\nTree decomposition is a second eay to reduce a constraint graph to a tree. we transform the original grpah into a tree where each node consists of a set of variables./n\n\nDecomposition has time $O(d^c (n-c)d^2)$ (where $c$ is cycle-cutset size). Tree decomposition has time $O(nd^{w+1})$ (where $w$ is the tree width). whenever you have a cycle-cutset size $c$ you also have a tree width size $w < c+1$, so tree decomposition is usually better time complexity. but cutset has linear memory while tree decomposition time complexity is exponential is $w$.\n \n\n## Module 6 Lecture Notes\n \nCSP components:\n\nfinite set of variables\n\nnon-empty domain of possible values ofr each variable\n\nfinite set of constraints which limit the values that variables can have\n\nSolutions to CSPs can be found by a completely general purpose algorithm, just need to formally specify the problem.\n\nmaximizing objective function - beyond the scope of the class\n\nBenefits of csp: 1) clean specification of many problems 2) csp knows which variable violates a contraint and therefore where to focus the search 3) csp automatically prunes branches that violate constraints.\n\nAC3 - a more efficient version of arc-consistency.\n\nheuristic 1) most constrained variable - choose the variable with the fewest legal values (aka minimum remaining value MRV heuristic)\n\nheuristic 2) most constrining variable - tie breaker among constrained variables, choose the variable with the most constraints on the remaining variables\n\nheuristic 3) least constraining value - given the variable, choose the least constraining value: i.e. the one that rules out the fewese values in the remaining variables\n\nheuristic 4) forward checking - keep track of remaining legal values for unassigned variables. terminate the search when any assigned variable has no remaining legal values.\n\n\nConstrait propagation goes beyond forward cheking and repeatedly enforces constraints locally. Arc-consistency, the simplest form of propagation makes each arc consistent. AC-3 is improved algorithm\n \n\n## Module 6 Definitions\n* **Consistent** - assignment does not violate constraints\n* **Complete** - all variables are assigned\n* **Solution** - complete and consistent assignment\n* **Unary constraint** - restricts a single variable\n* **Binary constraint** - constraint between two variables\n* **Global constraint** - constraint between an arbitrary number of variables\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "Our goal here is to give agents a way to represent general knowledge and a mechanism \\\n",
        "for combining and recombining information to achieve a variety of tasks.\\n\n",
        "\n",
        "The central component of a knowledge-based agent is a **Knowledge Base (KB)**, which is \\\n",
        "a set of sentences (used here as a technical term), each of which is written in a \\\n",
        "knowledge representation language and represents some assertion about the world. \\\n",
        "There are two kinds of sentences:\\n\n",
        "**Axioms** - are given\\n \n",
        "**Derived Sentences** - are new sentences derived from other sentences in a process called inference\\n\n",
        "The operation to add a new sentence to the KB is TELL, and to Query what is known is ASK.\\n \n",
        "\n",
        "A KB can initially contain some background knowledge, then as the agent program runs, \\\n",
        "it will add information to the KB based on what it perceives and inferences that it makes.\\n\n",
        "\n",
        "The agent program continuously does the following three steps:\\n\n",
        "<ol>\n",
        "<li>TELLs the KB what it perceives (percepts)</li>\n",
        "<li>ASKs what action it should perform, which involves reasoning and inference</li>\n",
        "<li>TELLs the KB what action was chosen</li>\n",
        "</ol>\n",
        "This process allows for a declarative approach wherein the agent can be given knowledge and told what it goal is then know how to operate. In contrast with a procedural approach which ecodes desired behaviors directly in the program code.\n",
        "\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "A grid world  for demonstrating KB agent behavior.\\n\n",
        "The Task Environment:\n",
        "<ul>\n",
        "<li> Performance: +1000 for success (leave cave with gold); -1000 for dying \\\n",
        "(pit, wumpus); -1 for each action; -10 for using arrow.</li>\n",
        "<li> Environment: 4x4 grid; agent starts in [1,1],  1 Wumpus, 1 gold, each other \\\n",
        "square can be pit with 0.2 probability.</li>\n",
        "<li> Actuators: move forward, left, or right; bumps into walls (no movement); \\\n",
        "Grab if in square with gold; shoot - shoots arrow, only once </li>\n",
        "<li>Sensors: perceive stench (from wumpus); perceive breeze (from pit); \\\n",
        "perceive glitter (from gold); perceive bump (from wall); perceive scream (dying wumpus); \\\n",
        "percept given as vector</li>\n",
        "</ul>\n",
        "Wumpus world is deterministic, discrete, static, single agent (wumpus doesn’t move), \\\n",
        "sequential, partially observable. Main challenge is ignorance of configuration. \n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "Sentences of knowledge are expressed in a representation language. The **syntax** of a \\\n",
        "language specifies what is a well-formed sentence. Logic defines the **semantics** \\\n",
        "(meaning) of a sentence, i.e. the truth of the sentence with respect to a possible \\\n",
        "world, which we represent abstractly as a **model**.\\n \n",
        "\n",
        "$m$ is a model of $\\\\alpha$ (i.e. $m$ satisfies $\\\\alpha$) if a sentence $\\\\alpha$ is true \\\n",
        "in a model $m$\\n\n",
        "\n",
        "$M(\\\\alpha)=$ the set of all models of $\\\\alpha$ \\n\n",
        "**Entailment**: $\\\\alpha$ entails $\\\\beta$ iff in every model in which $\\\\alpha$ is true \\\n",
        "$\\\\beta$ is also true \\n \n",
        "$\\\\alpha \\\\vDash \\\\beta$ iff $M(\\\\alpha) \\subseteq M(\\\\beta)$  (note that $\\\\alpha$ \\\n",
        "is a stronger assertion, it rules out more possible worlds than $\\\\beta$)\\n\n",
        "\n",
        "Considering a KB as a set of sentences, the KB is true in all models where these sentences \\\n",
        "are true, and false in all models where any of these sentences is false. Thus a KB must \\\n",
        "entail each of its constituent sentences. Conversely, if we can prove that the KB entails \\\n",
        "a sentence $\\\\alpha_1$ (i.e. that in every model where KB is true, $\\\\alpha_1$ is also true) \\\n",
        "then we can conclude that $\\\\alpha_1$ is true and derives (i.e. follows from) from KB - this process is \\\n",
        "known as **logical inference**, and we denote it as follows:\\n\n",
        "$KB \\\\vdash \\\\alpha_1$\\n\n",
        "**Soundness**: only sentences that are entailed can be inferred (aka truth-preserving)\\n\n",
        "**Completeness**: all sentences that are enatailed can be inferred\\n\n",
        "Usefull analogy is a needle in a haystack, if all consequences of s sentence or set of sentences \\\n",
        "is the haystack, then all logical consequences are needles. Something is entailed if it is a needle \\\n",
        "something is inferred if it is found\\n\n",
        "\n",
        "If $KB$ is true in the real world, then any sentence derivce from $KB$ by sound inference is also \\\n",
        "true in the real world.\\n\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "<h3>Syntax </h3>\n",
        "Allowable sentences:\\n\n",
        "**Atomic sentences** - consist of a single **proposition symbol** which stands for a \\\n",
        "proposition that can be true or false. Typically an uppercase letter with other letters \\\n",
        "or subscripts (e.g. $P$, $W_{1,3}$, $FacingEast$)\\n\n",
        "**Complex sentences** - constructed from simpler sentences using parenthesis and logical connectives\\n\n",
        "**Logical connectives** (five main ones):\n",
        "<ul>\n",
        "<li>$\\\\neg$ (not) negation</li>\n",
        "<li>$\\\\wedge$ (and) conjuntion</li>\n",
        "<li>$\\\\vee$ (or) disjuntion</li>\n",
        "<li>$\\\\Rightarrow$ (implies, if-then) implication/conditional; $A\\\\Rightarrow B$, $A$ is the \\\n",
        "premise/antecedent, $B$ is the conclusion/consequent</li>\n",
        "<li>$\\\\Leftrightarrow$ (if and only if, iff) biconditional </li>\n",
        "</ul>\n",
        "<h3>Semantics</h3>\n",
        "A model consists of a truth value for every proposition symbol. Then for any sentence, \\\n",
        "the truth value is computed recursively starting with the atomic sentences.\\n\n",
        "\n",
        "For atomic sentences:\n",
        "<ul>\n",
        "<li>(trivially) $True$ is true in every model, and $False$ is false in every model</li>\n",
        "<li>the truth value of every proposition symbol is specified directly by the model</li>\n",
        "</ul>\n",
        "For complex sentences\n",
        "<ul>\n",
        "<li>$\\\\neg P$ is true iff $P$ is false</li>\n",
        "<li>$P\\\\wedge Q$ is true iff both $P$ and $Q$ are true</li>\n",
        "<li>$P\\\\vee Q$ is true iff either $P$ or $Q$ is true</li>\n",
        "<li>$P\\\\Rightarrow Q$ is true unless $P$ is true and $Q$ is false</li>\n",
        "<li>$P\\\\Leftrightarrow Q$ is true iff $P$ and $Q$ are both true or both false</li>\n",
        "</ul>\n",
        "\n",
        "To decide if $KB \\\\vdash \\\\alpha$, a simple inference procedure might generate every possible model by creating all \\\n",
        "possible permutations of truth statments to the relavent proposition symbols and \\\n",
        "then iterate over each one to check that $\\\\alpha$ is true in every model in which $KB$ \\\n",
        "is true. This approach is sound and complete, but has a time complexity of $O(2^n)$.\n",
        "\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "**Logical equivalence**: two sentences $\\\\alpha$ and $\\\\beta$ are equivalent iff each \\\n",
        "of them entails the other (i.e. if they are true in the same set of models)\\n\n",
        "$\\\\alpha \\\\equiv \\\\beta$ iff $\\\\alpha \\\\vDash \\\\beta$ and $\\\\beta \\\\vDash \\\\alpha$\\n\n",
        "**Validity**: a sentence is valid if it is true in *all* models; such a sentence is also known as a **tautology**\\n\n",
        "**Satisfiability**: a sentence is satisfiable if it is true in (i.e. satisfied by) *some* model \\n\n",
        "Standard Logical Equivalences:\\n\n",
        "$(\\\\alpha \\\\wedge \\\\beta) \\\\equiv (\\\\beta \\\\wedge \\\\alpha)$ Commutativity of $\\\\wedge$\\n\n",
        "$(\\\\alpha \\\\vee \\\\beta) \\\\equiv (\\\\beta \\\\vee \\\\alpha)$ Commutativity of $\\\\vee$\\n\n",
        "$((\\\\alpha \\\\wedge \\\\beta) \\\\wedge \\\\gamma) \\\\equiv (\\\\alpha \\\\wedge (\\\\beta \\\\wedge \\\\gamma))$ Associativity of $\\\\wedge$\\n\n",
        "$((\\\\alpha \\\\vee \\\\beta) \\\\vee \\\\gamma) \\\\equiv (\\\\alpha \\\\vee (\\\\beta \\\\vee \\\\gamma))$ Associativity of $\\\\vee$\\n\n",
        "$\\\\neg (\\\\neg \\\\alpha) \\\\equiv \\\\alpha$ Double-negation elimination\\n\n",
        "$(\\\\alpha\\\\Rightarrow\\\\beta) \\\\equiv (\\\\neg\\\\beta \\\\Rightarrow\\\\neg\\\\alpha)$ Contraposition\\n\n",
        "$(\\\\alpha\\\\Rightarrow\\\\beta) \\\\equiv (\\\\neg\\\\alpha \\\\vee \\\\beta)$ Implication elimination\\n\n",
        "$(\\\\alpha\\\\Leftrightarrow\\\\beta) \\\\equiv ((\\\\alpha\\\\Rightarrow\\\\beta) \\\\wedge (\\\\beta \\\\Rightarrow\\\\alpha))$ Biconditional elimination\\n\n",
        "$\\\\neg(\\\\alpha \\\\wedge \\\\beta) \\\\equiv (\\\\neg\\\\alpha \\\\vee \\\\neg\\\\beta)$ De Morgan\\n\n",
        "$\\\\neg(\\\\alpha \\\\vee \\\\beta) \\\\equiv (\\\\neg\\\\alpha \\\\wedge \\\\neg\\\\beta)$ De Morgan\\n\n",
        "$((\\\\alpha \\\\wedge \\\\beta) \\\\vee \\\\gamma) \\\\equiv ((\\\\alpha \\\\wedge \\\\beta) \\\\vee (\\\\alpha \\\\wedge \\\\gamma)))$ Distributivity of $\\\\wedge$ over $\\\\vee$\\n\n",
        "$((\\\\alpha \\\\vee \\\\beta) \\\\wedge \\\\gamma) \\\\equiv ((\\\\alpha \\\\vee \\\\beta) \\\\wedge (\\\\alpha \\\\vee \\\\gamma)))$ Distributivity of $\\\\vee$ over $\\\\wedge$\\n\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\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": 118,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "05488027-a6ed-41bb-cd2b-238bb059a55d"
      },
      "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": 119,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nOur goal here is to give agents a way to represent general knowledge and a mechanism for combining and recombining information to achieve a variety of tasks.\n\n\nThe central component of a knowledge-based agent is a **Knowledge Base (KB)**, which is a set of sentences (used here as a technical term), each of which is written in a knowledge representation language and represents some assertion about the world. There are two kinds of sentences:\n\n**Axioms** - are given\n \n**Derived Sentences** - are new sentences derived from other sentences in a process called inference\n\nThe operation to add a new sentence to the KB is TELL, and to Query what is known is ASK.\n \n\nA KB can initially contain some background knowledge, then as the agent program runs, it will add information to the KB based on what it perceives and inferences that it makes.\n\n\nThe agent program continuously does the following three steps:\n\n<ol>\n<li>TELLs the KB what it perceives (percepts)</li>\n<li>ASKs what action it should perform, which involves reasoning and inference</li>\n<li>TELLs the KB what action was chosen</li>\n</ol>\nThis process allows for a declarative approach wherein the agent can be given knowledge and told what it goal is then know how to operate. In contrast with a procedural approach which ecodes desired behaviors directly in the program code.\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \nA grid world  for demonstrating KB agent behavior.\n\nThe Task Environment:\n<ul>\n<li> Performance: +1000 for success (leave cave with gold); -1000 for dying (pit, wumpus); -1 for each action; -10 for using arrow.</li>\n<li> Environment: 4x4 grid; agent starts in [1,1],  1 Wumpus, 1 gold, each other square can be pit with 0.2 probability.</li>\n<li> Actuators: move forward, left, or right; bumps into walls (no movement); Grab if in square with gold; shoot - shoots arrow, only once </li>\n<li>Sensors: perceive stench (from wumpus); perceive breeze (from pit); perceive glitter (from gold); perceive bump (from wall); perceive scream (dying wumpus); percept given as vector</li>\n</ul>\nWumpus world is deterministic, discrete, static, single agent (wumpus doesn’t move), sequential, partially observable. Main challenge is ignorance of configuration. \n \n\n## AIMA Chapter 7.3 Logic\n\nSentences of knowledge are expressed in a representation language. The **syntax** of a language specifies what is a well-formed sentence. Logic defines the **semantics** (meaning) of a sentence, i.e. the truth of the sentence with respect to a possible world, which we represent abstractly as a **model**.\n \n\n$m$ is a model of $\\alpha$ (i.e. $m$ satisfies $\\alpha$) if a sentence $\\alpha$ is true in a model $m$\n\n\n$M(\\alpha)=$ the set of all models of $\\alpha$ \n\n**Entailment**: $\\alpha$ entails $\\beta$ iff in every model in which $\\alpha$ is true $\\beta$ is also true \n \n$\\alpha \\vDash \\beta$ iff $M(\\alpha) \\subseteq M(\\beta)$  (note that $\\alpha$ is a stronger assertion, it rules out more possible worlds than $\\beta$)\n\n\nConsidering a KB as a set of sentences, the KB is true in all models where these sentences are true, and false in all models where any of these sentences is false. Thus a KB must entail each of its constituent sentences. Conversely, if we can prove that the KB entails a sentence $\\alpha_1$ (i.e. that in every model where KB is true, $\\alpha_1$ is also true) then we can conclude that $\\alpha_1$ is true and derives (i.e. follows from) from KB - this process is known as **logical inference**, and we denote it as follows:\n\n$KB \\vdash \\alpha_1$\n\n**Soundness**: only sentences that are entailed can be inferred (aka truth-preserving)\n\n**Completeness**: all sentences that are enatailed can be inferred\n\nUsefull analogy is a needle in a haystack, if all consequences of s sentence or set of sentences is the haystack, then all logical consequences are needles. Something is entailed if it is a needle something is inferred if it is found\n\n\nIf $KB$ is true in the real world, then any sentence derivce from $KB$ by sound inference is also true in the real world.\n\n\n\n\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n<h3>Syntax </h3>\nAllowable sentences:\n\n**Atomic sentences** - consist of a single **proposition symbol** which stands for a proposition that can be true or false. Typically an uppercase letter with other letters or subscripts (e.g. $P$, $W_{1,3}$, $FacingEast$)\n\n**Complex sentences** - constructed from simpler sentences using parenthesis and logical connectives\n\n**Logical connectives** (five main ones):\n<ul>\n<li>$\\neg$ (not) negation</li>\n<li>$\\wedge$ (and) conjuntion</li>\n<li>$\\vee$ (or) disjuntion</li>\n<li>$\\Rightarrow$ (implies, if-then) implication/conditional; $A\\Rightarrow B$, $A$ is the premise/antecedent, $B$ is the conclusion/consequent</li>\n<li>$\\Leftrightarrow$ (if and only if, iff) biconditional </li>\n</ul>\n<h3>Semantics</h3>\nA model consists of a truth value for every proposition symbol. Then for any sentence, the truth value is computed recursively starting with the atomic sentences.\n\n\nFor atomic sentences:\n<ul>\n<li>(trivially) $True$ is true in every model, and $False$ is false in every model</li>\n<li>the truth value of every proposition symbol is specified directly by the model</li>\n</ul>\nFor complex sentences\n<ul>\n<li>$\\neg P$ is true iff $P$ is false</li>\n<li>$P\\wedge Q$ is true iff both $P$ and $Q$ are true</li>\n<li>$P\\vee Q$ is true iff either $P$ or $Q$ is true</li>\n<li>$P\\Rightarrow Q$ is true unless $P$ is true and $Q$ is false</li>\n<li>$P\\Leftrightarrow Q$ is true iff $P$ and $Q$ are both true or both false</li>\n</ul>\n\nTo decide if $KB \\vdash \\alpha$, a simple inference procedure might generate every possible model by creating all possible permutations of truth statments to the relavent proposition symbols and then iterate over each one to check that $\\alpha$ is true in every model in which $KB$ is true. This approach is sound and complete, but has a time complexity of $O(2^n)$.\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \n**Logical equivalence**: two sentences $\\alpha$ and $\\beta$ are equivalent iff each of them entails the other (i.e. if they are true in the same set of models)\n\n$\\alpha \\equiv \\beta$ iff $\\alpha \\vDash \\beta$ and $\\beta \\vDash \\alpha$\n\n**Validity**: a sentence is valid if it is true in *all* models; such a sentence is also known as a **tautology**\n\n**Satisfiability**: a sentence is satisfiable if it is true in (i.e. satisfied by) *some* model \n\nStandard Logical Equivalences:\n\n$(\\alpha \\wedge \\beta) \\equiv (\\beta \\wedge \\alpha)$ Commutativity of $\\wedge$\n\n$(\\alpha \\vee \\beta) \\equiv (\\beta \\vee \\alpha)$ Commutativity of $\\vee$\n\n$((\\alpha \\wedge \\beta) \\wedge \\gamma) \\equiv (\\alpha \\wedge (\\beta \\wedge \\gamma))$ Associativity of $\\wedge$\n\n$((\\alpha \\vee \\beta) \\vee \\gamma) \\equiv (\\alpha \\vee (\\beta \\vee \\gamma))$ Associativity of $\\vee$\n\n$\\neg (\\neg \\alpha) \\equiv \\alpha$ Double-negation elimination\n\n$(\\alpha\\Rightarrow\\beta) \\equiv (\\neg\\beta \\Rightarrow\\neg\\alpha)$ Contraposition\n\n$(\\alpha\\Rightarrow\\beta) \\equiv (\\neg\\alpha \\vee \\beta)$ Implication elimination\n\n$(\\alpha\\Leftrightarrow\\beta) \\equiv ((\\alpha\\Rightarrow\\beta) \\wedge (\\beta \\Rightarrow\\alpha))$ Biconditional elimination\n\n$\\neg(\\alpha \\wedge \\beta) \\equiv (\\neg\\alpha \\vee \\neg\\beta)$ De Morgan\n\n$\\neg(\\alpha \\vee \\beta) \\equiv (\\neg\\alpha \\wedge \\neg\\beta)$ De Morgan\n\n$((\\alpha \\wedge \\beta) \\vee \\gamma) \\equiv ((\\alpha \\wedge \\beta) \\vee (\\alpha \\wedge \\gamma)))$ Distributivity of $\\wedge$ over $\\vee$\n\n$((\\alpha \\vee \\beta) \\wedge \\gamma) \\equiv ((\\alpha \\vee \\beta) \\wedge (\\alpha \\vee \\gamma)))$ Distributivity of $\\vee$ over $\\wedge$\n\n\n\n\n\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": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "b01b7631-3934-41ca-d849-19e8d93fd8e4"
      },
      "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": 120,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Historically, there are several different approaches to defining (and therefore recreating) intelligence. We can categorize these differing views along two \"dimensions\": 1) human (i.e. fidelity to human performance) vs rational (doing the \"right thing\") and 2) thought (thought processes and reasoning) vs behavior (external characterization). This yields four possible combinations each describing an approach to artificial intelligence. Acting Humanly: proponents include Alan turing, as is encapsulated in the Turing test. A human interrogator poses written questions and the computer generates written responses; if the interrogator cannot tell whether the response was written by a person or computer then the computer passes the test. Thinking Humanly: proponents include Allen Newell and Herbert Simon who developed the \"general problem solver\" and were concerned with comparing the sequence and timing of its reasoning against those of humans solving the same problem. Cognitive Science can be seen as a product of this approach. Thinking Rationally: defining \"right thinking\" has led to the development of logic. Probability fills in the gaps where knowledge or events are uncertain. Acting Rationally: this is the approach that has prevailed for most of the field’s history and can be thought of as the \"Standard Model\": focusing on the study and construction of agents that \"do the right thing\". This approach has the advantages that 1) it is more general than the thinking rationally approach and 2) it is more amenable to scientific development than imitating human behavior or thought. Furthermore, the skills required in the other approaches (e.g. Turing test and making inferences) will be useful in making an agent act rationally.\n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n \nAn agent is anything that can perceive an environment (via sensors) and act on that environment (via actuators). Environment could be the entire universe (i.e. everything) but typically just a part of the universe that is relevant to the agent; the part that affects what the agent perceives and is affected by the agent’s actions. E.g.: humans - sensors = eyes, ears, etc., actuators = hands, legs, vocal tract, etc.; robot - sensors = camera, infrared range finder, etc., actuators = motors, cervos, etc.; software agent - sensory inputs = file contents, network packets, user input, etc., actions = writing files, sending network packets, displaying information, generating sounds, etc. thermostat - sensors = temperature and humidity sensors, actuators = fan, valve, and compressor controls. Percept refers to the input an agent receives from it’s sensors; typically we represent a precept as a vector of all the inputs/signals of each sensor. Percept Sequence refers to the entire history of an agent’s percepts to date. An agent’s behavior is a consequence of its Percept Sequence and any built-in knowledge. Mathematically, we can describe this as a function which maps a series of percepts to a series of actions. This abstract mathematical description is called the agent function. An agent program is an implementation of the agent function running on a physical architecture (agent = architecture + program). Important Note: the concept of an agent is a helpful framework for analyzing systems, but not an absolute lens in which to characterize the world into agents and non-agents; we consider something an agent when it is helpful - typically if the entity contains significant computational resources and the task environment requires nontrivial decision making; Additionally, something is an agent vs part of the environment when it’s behavior can be described in terms of a performance measure (see below). \n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nBut what does it mean to do the “right thing”? Typically for AI we use the notion of consequentialism, that is, an agent’s behavior is evaluated based on its consequences. We use a Performance Measure to evaluate the behavior of our agent. This is an objective criterion for success of an agent’s behavior given the evidence provided by the percept sequence. But our definition should not require omniscience. How can an agent know what the correct course of action is if this depends on the consequences which are not perfectly known until it has finished its action? So we introduce the notion of expected performance (to distinguish from actual performance, which would require knowledge of the future) which we determine by calculating the expected value of the performance measure. Now we define a rational agent as follows: for every possible percept sequence, a rational agent selects an action that maximizes the expected value of its performance measure, given its Percept Sequence and any built-in knowledge. \n \n\n## AIMA 2.3 The Nature of Environments\n Agents are ‘solutions’ to ‘problems’; we refer to these ‘problems’ as Task Environments. We define a Task Environment we need to specify: a Performance measure, an Environment, Actuators, and Sensors (PEAS). E.g. Taxi - performance measure = safe, fast, maximize profits, etc., environment = roads, traffic, pedestrians, etc., actuators = steering, accelerator, brake, etc., sensors = cameras, radar, speedometer, etc. After defining the task environment, we can construct the agent function. Then we can write an agent program to implement the agent function. Properties of Task Environments:\n<ol>\n<li> **fully observable** (agent can detect all aspects of the environment that are relevant to the choice of action - e.g. chess) VS **partially observable** (access to some of information about the environment, but not the entire global picture - e.g. self-driving cars) (**unobservable**) </li>\n<li> **deterministic** (the expected result of a given action is guaranteed to happen) VS **nondeterministic** (the outcome of an action is uncertain - e.g. dice, cards - use term stochastic if we explicitly quantify the probabilities of possible outcomes and nondeterminsitic if not quantified) </li>\n<li> **episodic** (agent’s experience is divided into atomic episodes which do not depend on the actions taken in previous episodes - e.g. spotting defective parts in assembly line) VS **sequential** (each decision affects all future decisions - e.g. chess, taxi)</li>\n<li> **static** (environment remains unchanged while the agent is deliberating - e.g. crossword) VS **dynamic** (environment is changing eve while agent is deciding which action to take - e.g. driving)  VS **semi-dynamic** ( environment itself does not change with passage of time, but agent’s performance score does - e.g. chess w/ clock)</li>\n<li> **discrete** (e.g. chess) VS **continuous** (e.g. driving) (with regard to the states, time, percepts, and actions)</li> \n<li> **single agent** (e.g. crossword) VS **multiagent** (e.g. chess, pacman - competitive or cooperative)</li>\n<li> **known** (the outcomes for all actions are given) VS **unknown** () (refers to agent’s state of knowledge about the environment, rather than environment itself. Known vs observable - solitaire is known but partially observable, video game might be fully observable but unknown if button controls are not known)</li>\n</ol> \nHardest case: partially observable, nondeterministic, sequential, dynamic, continuous, multiagent, and unknown\n \n\n## AIMA 2.4 The Structure of Agents\n \nSimple reflex agent\nModel based agent\nGoal based agent\nUtility based agent\nLearning agents\n\nAtomic representation\nFactored representation\nStructured representation\n\nLocalist representation\nDistributed representation\n\n \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\n \nall data is treated as objects. Python has strong typing (every object has a fixed type), but it is also dynamic typing (type is automatically determined and can change if reassigne to differnt type). Immutable: strings, tuples, Mutable: Lists.\n \nList comprehensions:\n\nli = [3, 6, 2, 7]\n\n[elem * 2 for elem in li]\n\nresult is [6, 12, 4, 14]\n\nDictionary keys must be immutable.\n \n[:] operator returns copy of a list\n\nno function overloading in python, but operator overloading is possible.\n\n \n\n## Module 2 Definitions\n* **Mutability** - cannot be modified once created\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem-Solving Agents solve Search Problems by planning ahead and formulating the best possible sequence of actions (i.e. Searching). The Task Environments we are considering here are fully observable, deterministic, and known. The solution to a problem in such an environment is a fixed sequence of actions, and can therefore be found via a Search, which is a computational process that considers a sequence of actions that form a path from the initial state to a goal state. We formally define a Search Problem by specifying: \n\n1) States - the set of all possible states $S$\n\n2) Initial State - state in which the agent starts $s_i \\in S$\n\n3) Goal State(s)/Goal Test  - a state in which the agent has accomplished the objective. Can define a goal test $Goal$ which indicates if the goal has been reached - $s$ is a goal state if $Goal(s) == true$\n\n4) Actions - the set of available actions $A$. We define a function $Actions$ such that $Actions(s) =$ the set of actions that is applicable in $s$ (i.e can be execute in $s$)\n\n5) Transition Model - describes what each action does (from the given state). This is represented as a function $Results$: $Results(s, a) = s_r =$ the state that results from doing action $a$ in state $s$. This new state $s_r$ is called a successor of $s$\n\n6) Action Cost - the numeric cost of applying an action (from one state to another). We denote an action cost function: $c(x,a,y) =$ the cost of taking action $a$ from state $x$ to state $y$. The cost must be positive and should reflect the performance measure, as we will use this to determine the optimal solution. The overall Path Cost will be the sum of action costs along a path.\n\n\nNote that our formulation is a model which is an abstraction of the real world problem. For example we don’t include the weather, or traffic etc. We can think of this abstraction in terms of equivalence classes. Our abstract State = a set (equivalence class) of real-world states. Similarly our abstract actions = a set (equivalence class) of combinations of real world actions.  \n\n\n## AIMA Chapter 3.2 Example Problems\n \nGrid world - vacuum world\n\n8-puzzle\n\nRoute-finding puzzle\n\nTouring problems - traveling salesperson\n\nVLSI layout\n\nrobot navigation\n\nAutomatic assembly sequencing\n \n\n## AIMA Chapter 3.3 Search Algorithms\n A Search Algorithm takes a search problem as an input and returns either a solution or an indication of failure. Can visualize search as a tree: each node represents a state, each edge represents an action. Root node is the initial state, and every child is a successor of its parent, connected by the respective action. Can expand a node by using the Actions function to consider all actions available from that state, and using the Transition Model to determine the resulting state. A state for which a node has been generated (whether expanded or not) is said to have been reached. Three distinct regions of the graph: nodes that have been reached and visited/expanded, nodes that have been reached but not expanded (the frontier), and nodes that have not been reached; the frontier separates the other two. The crux of the search: deciding which node to expand next - depends on how the queue is implemented.\n\nA search tree will contain redundant paths which include multiple different paths from one node to another, as well as cycles. A tree search doesn't not check for redundant paths (i.e. treats different paths to the same node as distinct), but a graph search does, by checking to see if a node has been visited before adding it to the search queue- this requires additional memory.\n\nParameters of a state space are depth (d) - the number of actions in an optimal solution; maximum depth (m) - the maximum number of actions in any path; and the branching factor (b) - the number of successors considered for each node.\n\n```\nGeneral-Tree-Search-Algo(problem) -> solution or failure\n  initialize frontier as some type of queue\n  add initial state to frontier\n  while the frontier is not empty:\n    pop node from frontier\n    if node is goal state:\n      then return node\n    expand node- i.e. for each successor, \n      add to the frontier\n  return failure\n\n\nGeneral-Graph-Search-Algo(problem) -> solution or failure\n  initialize frontier as some type of queue\n  add initial state to frontier\n  initialize explored as empty set\n  while the frontier is not empty:\n    pop node from frontier\n    if node is goal state:\n      then return node\n    add node to explored set\n    expand node- i.e. for each successor, \n      if not in frontier and not in explored\n        add to the frontier\n  return failure\n```\n\nCriteria for evaluating search algorithm performance:\n1)Completeness - a search algorithm is complete if it is guaranteed to find a solution if one exists, and to correctly report a failure if not\n2)(Cost) Optimality - a solution is optimal if it is guaranteed to find the/an optimal solution\n3)Time Complexity\n4)Space Complexity\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nAn uninformed search only has access to the problem definition. Algorithms build a search tree and attempt to find a solution by exploring the tree. They differ in their decision of which node to expand next:\n\n\n<ul>\n<li>Best First Search - selects the node with the minimum cost according to some evaluation function f(n) - priority queue with f(n)</li>\n<li>Bread-First Search - selects the node that was added to the queue first - FIFO queue</li>\n<li>Uniform-Cost Search (aka Dijkstra’s) - selects the node with the lowest path cost g(n) - priority queue with g(n) - uniform because it spreads out in eaves of uniform path cost (wheras breadth first spreads out in waves of uniform depth)</li> \n<li>Depth-First Search - selects the node that was most recently added - LIFO queue (variant with backtracking - only one successor is generated at a time rather than all at the same time, and succeros are generated by modifying the current state rather than copying and changing a new state - reduces memory use)</li>\n<li>Depth Limited - Depth first search, but limit depth to $l$</li>\n<li>Iterative Deepening - keep performing depth limited and increasing $l$ each time; combines benefits of depth first and breadth first search.</li>\n<li>Bidirectional Search - simultaneously search fro initial state forward, and goal state backwards, untl two searches meet.</li> \n</ul>\n\n \n\n## Module 3 Lecture Notes\n \nReflex agent: picks a single action based on a percept at a given time\n\nproblem solving agent: plans ahead - undertakes a serach whic sonideres a sequnence of actions that forms a path from the start to the goal state. this sequence is called a solution\n\nTree search treats different paths to the same node as distinct, in contrast to graph search. Graph search checks to see if a node has been visited before adding it to the search quque. Uninformed search strategies (aka Blind Search) use only information avaialbel in the probelm definition. strategy = order of tree expansion i.e. which node on the frontier shoue we expand next: implemented by using different queue structures for the fronrier/n\nLIFO - Depth first search -/n\nFIFO - Breadthfirst search/n\nPriority - Best first search/n\n\nDepth Limited search:DFS with a depth limit $l$/n\nif $l =d$ (by luck) then optimal/n\nif $l < d$ incomplete/n\nif $l >d$ not optimal/n\n\nIterative Deepening Search: user depth liite search as subroutine and keep increasing $l$\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - the set of all states reachable form the intial state by any sequenc of actions\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nAn informed search has access to the problem definition and a heuristic function $h(n)$ which estimates the (remaining) path cost from the state at node $n$ to a goal state. (they may also have access to additional information such as pattern databases).\n\n\n$g(n)=$ the path cost from the initial state to node $n$ \n\n$h(n)=$ the estimated path cost from node $n$ to a goal state\n\n\n<ul>\n<li>**Greedy Best First Search** - selects the node with the minimum h(n) - priority queue with f(n)= h(n)</li>\n<li>**A* Search** - selects the node with the minimum g(n)+ h(n) - priority queue with f(n)= g(n) + h(n)</li>\n</ul>\n\nA* search is complete and is optimal if the heuristic is **admissible**. A heuristic is admissible if it never overestimates the cost to reach a goal (it is optimistic) that is $0 \\leq h(n) \\leq h*(n)$ where $h*(n)$ is the true cost to a nearest goal. A stronger property is **consistency**; a heuristic is consistent if, for every node $n$ and every successor $n’$ of $n$ the following holds $h(n) \\leq c(n,a,n’) + h(n’)$ (this is a form of the triangle inequality). A consistent heuristic is admissible, but not necessarily vice versa.\n\n\nIt's useful to visualize searches as exploring the state space in contours. A* search fans out from the start node in concentric bands of increasing $f(n)$ cost. Uniform cost search fans out in contours of $g(n)$ cost and will spread out equally in all directions (circular) whereas A* will spread out in bands that will stretch increasing towards the goal. The A* search lines will monotonically increase iff A* is consistent.  If C* is the true cost of the optimal solution, then A* expands all nodes where $f(n)< C*$ (these are surely expanded nodes), may expand some nodes where $f(n) = C*$, and will NOT expand any nodes where $f(n) > C*$. This means that A* is optimally efficiency; any algorithm that starts for the initial state and uses the same heuristic must expand all nodes that are “surely expanded” by A*. \n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \nThe quality of a heuristic has a significant impact on the performance of the algorithm. One way we characterize this is using the effective branching factor b*. b* is the branching factor of a a uniform tree with N nodes and depth d, where N is the number of nodes generated by the A* search and d is the solution depth. The lower the effective branching factor the better. We say a heuristic $h_2$ dominates another heuristic $h_1$ if for any node $n$, $h_2(n) \\geq h_1(n)$. Domination translates directly into efficiency. Recall that every node with $f(n) < C*$ is surely expanded; when h is consistent, this is the same as saying every node with $h(n) < C* - g(n)$ is surely expanded. If a node is surely expanded by $h2$ it will also be surely expanded by $h_1$,  since $h_1 \\leq h_2$, but $h_1$ may even expand more nodes. Therefore $h_2$ will always expand fewer nodes than $h_1$. Therefore it is generally better to use a heuristic with higher values, as long as it's still consistent and it doesn’t take too long to compute.\n   \n\nAnother suggested way to characterize this impact is that heuristic reduces the effective depth of an A* search by a constant $k_h$, so that the total search is $O(b^{d-k_h})$\n\n\nWe can typically construct good heuristics from relaxed problems. Relaxed problems are problems similar to the one we are considering, with fewer restrictions on the actions. By removing restrictions we strictly increase edges to our state-space graph (we will never remove edges) and our relaxed state-space graph is a supergraph of our original problem. This means that any optimal solution in this new relaxed problem will be at least as good as a solution in our original problem. Therefore, the cost of an optimal solution to the relaxed problem is an admissible heuristic for the original problem. Additionally, because its an exact cost, it must obey the triangle inequality and is therefore consistent.\n \n\nOther ways of generating heuristics are:\n\n<ul>\n<li>From subproblems, using pattern databases to store the exact solutions fore every possible subproblem.</li>\n<li>Using landmarks - we precompute and store the optimal paths between a handful of landmark points.</li>\n</ul>\n\n \n\n## Module 4 Lecture Notes\n \nA* is efficient because it prunes the search tree, avoiding nodes that are not necessary for finding an optimal solution. A* is good, complete, cost optimal, and optimally efficient (given a consistent heuristic), but the number of nodes expanded can still be exponential in the length of the solution. If we accept satisficing solutions (suboptimal but still ‘good enough’), we can explore fewer nodes and reduce the time and space complexity. An inadmissible heuristic, while risking missing the optimal solution, could potentially be more accurate, therefore reducing the number of nodes examined. This leads to the weighted A* search; we give the heuristic function more weight, thus focusing the search contour more towards the goal, and exploring fewer states $f(n) = g(n) + Wh(n)$. We may miss the optimal path if it’s outside the weighted search contour, but the search will be much faster. This can actually be seen as a generalization of A* (W=1), Uniform cost search (W=0) and greedy best-first (W=infinity).\n \n\nMain issue with A* is the use of memory. Memory is split between the frontier and the reached states. A state in the frontier is stored in both; as a node in the frontier (so we can decide if we should expand it) and as an entry in the table of reached states (so we know if it has been visited). Some potential solutions:\n\n<ul>\n<li>keep a state only in one of the two places (less space, but more time)</li>\n<li>eliminate reached altogether</li>\n<li>remove states from reached when they are no longer needed e.g. keep a reference count of the number of times a state has been reached and remove it when there are no more ways to reach it</li>   \n</ul>\nOther memory conserving algorithms:\n<ul>\n<li>Beam search - limits the size of the frontier. e.g. keep only k nodes with the best f(n). OR keep every node with f(n) within some delta of the best f(n). </li>\n<li>Iterative deepening A* - the cutoff for each iteration is the smallest f(n) that exceeded the cutoff on the previous iteration. This way we don’t have to keep all reached states in memory, though we may visit some states multiple times</li>\n<li> Recursive best first search (RBFS) - recursively explores a path keeping track of the best alternative f(n) available from any ancestor of the current node. If the current node exceeds this f(n), the recursion unwids back to an alternative back and replaces f(n) for each node with a backed-up value (best f(n) of its children). </li>\n<li>Memory bounded A* (MA*)</li>\n<li>Simplified MA* (SMA*) </li>\n</ul>\n\n\n\n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nThree approaches to multi-agent envoronments\n\n<ol>\n<li>Consider them in aggregate as an economy, without predicting the action of each individual agent</li>\n<li>Consider agents as part of the environment (their behaviro would represent a nondeterministic aspect of the environment). But this ignores that adversarial agents are working actively against us </li>\n<li>Explicitly model agents  - in this module we do so with adversarial agent in a game tree</li>\n</ol>\nGames we typically study are \n<ol>\n<li>deterministic</li>\n<li>two player; with players taking turns</li>\n<li>zero sum; what's good for one player is bad for the other</li>\n<li>perfect information; i.e. fully observable</li>\n</ol>\nA game can be formally ydefined with the following elements:\n\n$S_0$: the **initial state**, specifies how the game is set up at the start\n\nTo-Move($s$): the player whose turn it is to move in state $s$\n\nAction($s$): the set of legal moves in state $s$\n\nResult($s$,$a$): the **transition model** that defines which state results from the action $a$ in the current state $s$\n\nIs-Terminal($s$): the **terminal test** which indicates when the game is over (i.e. has reached a **terminal state**)\n\nUtility($s$,$p$): the **utility function** which defines the numerical value of a terminal state, $s$, to player $p$\n\n\nSimilarly to search problems, we can generate a game tree with states as nodes moves as edges, and the root as the initial state. However in our game each successive layer of the game tree (a **ply**) reprsents a different palyers turn. \n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n<h3>Minimax</h3>\nwe define two players: MAX and MIN\n\nThe score is kept from MAX's viewpoint, so MAX tries to maximize the score and MIN tries to minimize it. They take turns playing, and we typiically ssume MAX moves first. When represented as a Tree, each successive ply (i.e. level) represents the other player's turn. They keep alternating, until a terminal state is reached. At this point we can call the Utility function to determine the value of the terminal node.\n\nThe **minimax search algorithm** computes the  **minimax value** at each node recusively by working from the terminal states back up to the root. The minimax value at the terminal nodes is given by the Utility function. Then as we work our way up the tree, each MIN node chooses the minimal value of it's children, and each MAX node chooses the maximal value of its children (called the **backed up** values) until we get back up to the root. **a key assumption is that both players play optimally**.  This algorithm has a time complexity of $O(b^m)$ and a space complexity of $O(bm)$ (if all actions are generated at once) or $O(m)$ (if actions are generated one at a time).\n\n\n<h3>Alpha-Beta Pruning</h3>\nWe introduce two variables that allow us to ignore certain portions of the game subtree that will not be fruitful. This process is called **pruning**. \n\n$\\alpha$ = the value of MAX's best choice so far (i.e. at any node along the path from the current node to the root): MAX will get **at least** $\\alpha$\n\n$\\beta$ = the value of MIN's best choice so far (i.e. at any node along the path from the current node to the root): MIN can limit MAX to **at most** $\\beta$\n\n\nWhen evaluating a MAX node: if a value $\\geq \\beta$ we can stop evaluating (MIN will never select this MAX node)\n\nWhen evaluating a MIN node: if a value $\\leq \\alpha$ we can stop evaluating (MAX will never select this MIN node)\n\n\nFor multiplayer games, we replace the single value of each node with a vector of values representing the utility of the state for each player. Then the utility of an internal node is typicially the utility vector of the successor sate with the highest value for the player choosing at that time. \n\nThe effectivenes of alpha-beta pruning depends on the order in which states are examined; it would be better to examine the best possible successors first. If done perfectly, alpha beta could examine only $O(b^{m/2})$ (rather than $O(b^{m})$ for plain minimax). Can try and determine order of good moves (e.g. chess - captures > threats > forward moves > backward moves). Can also use iterative deepening and use previous exploration to determine best moves.\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nTo make the search more time-effective, we can modify it in two ways:\n\n1) replace the Utility function with a heuristic **evaluation function** (treat nonterminal nodes as terminal)\n\n2) replace the terminal test with a **cutoff test** which returns true for terminal states and when search should stop; depth and state properties\n\n<h3>Evaluation Funcitons</h3>\nthe *heuristic* evaluation function, $Eval(s,p)$, returns an estimate of the expected utility of the state $s$ to player $p$.\n<ul>\n<li>Terminal States - $Eval(s,p)=Utility(s,p) $ </li>\n<li>Non-terminal States - $Utility(loss,p) \\leq Eval(s,p) \\leq Utility(win,p) $ </li>\n</ul>\nCriteria for good evaluation function\n<ul>\n<li>quick computation</li>\n<li>strongly correlated with actual chances of winning</li>\n</ul>\nMost evaluation functions calculate features of a stateand use these features to defined categories of states. In theory, an **expected value** for each category could be computed based on the proportion of states with a given outcome. However in practice, this is not feasible and instead a numerical contribution (an approximate **material value**) is estimated for each feature and combined into a total value;  called a **weighted linear function** and can be writtend as:\n$Eval(s) = w_1f_1(s)+w_2f_2(s)+...+w_nf_n(s)= \\sum_{i=1}^{n}w_if_i(s) $\nWhere $f_i$ is a feature (e.g. number of which bishops) and $w_i$ is a weight indicating how important that feature is. Weights should be normalized so that the sum is always between 0 and 1. Adding the features in this way assumes that the contribution of each feature is indepedent of each other which may not be true, in ehich case non-linear combinations might be used instead. Features and weights typically come from human experience, or from machine learning. \n<h3>Cutoff</h3>\nInstead of checking for a terminal state, we check for cutoff conditions. however if we we just limit the depth of the search, we may missjudge the true value of a state, therefore the evaluation function should only be applied to states that are **quiescent** meaning there is no pending move that could drastically affect the evaluation. The **horizon effect** occurs when the program simply delays an inevitable move by pushing it beyond the horizon. A fix is **singular extension** allowing \"clearly better moves\" to extend search depth.\n<h3>Forward Pruning</h3>\nsaves computation tume by attempting to prune poor moves. beam search - consider only $n$ best moves; ProbCut - using past experience to estimate if nodes will probably be outside the alpha-beta window; late move reduction - assuming that moves are ordered (best to worst) reduce the depth of search for later moves\n<h3>Search vs Lookup</h3>\nSometimes it makes sense to just create lookup tabels. e.g. chess opening and closings have fewer possible positions and have well documented plays and we can rely on human expertise rather than wasting computing time.\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \nSimilar to minimax game tree but now we have chance nodes, in addition to MIN and MAX nodes. each child represents a possible outcome and has an associated probablility. So we calculate an **expected** value for this node as the wieghted average of possible outcomes. This then leads to an overall **expectiminimax value**. The presence of chances nodes changes the impact that the evaluation funciton has on the final outcome; we have to be more careful about what values mean. the evaluation function should return values that are a positive linear transformation of the probablility of winning (the the expected utility). \n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n \nEvaluation fucntion f assignes real-number scores to board withough references to path (i.e. don't care how we got there). Terminal nodes represent ways the game could end, and are labeled with the desirability of that ending.\n\nThe minimax rule: don't play hope chess (i.e. assume MIN always replies with best move for MIN), backed-up value - recursive process. it is the optimal value of children:\n\nfor MAX - the maximun of children\n\nfor MIN - the minimum of children\n\n\nMinimax Procedure:\n\n<ol>\n<li>start with current position (as MAX)</li>\n<li>expand the game a fixed number of plies</li>\n<li>apply the evaluation functio at leaf nodes</li>\n<li>calculate the back up value from the bottom up</li>\n<li>pick the move assigned to MAX at the root</li>\n<li>wait for MIN to respond</li>\n</ol>\nwe can't expand the entire game tree because the stat-space is typically too large. \n\n\nExpecitmax\n\ngames iwht uncertain outcomes (e.g. dice, cards). consider uncertian outcomes controlled by chance rather than an adversary. Game tree is similar to minimax, with the addition of chance nodes. \n\nchance nodes - calculate the expected utilites (wighted average)\n\nMAX/MIN nodes - same as before\n\noverall we compute the average score under optimal play. It is much harder to prune here.\n \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nCSP consists of three components:\n<ul>\n<li> $X$ a set of variables</li>\n<li> $D$ a set of domains, one for each variable</li>\n<li> $C$ a set of constraints that specify allowable combinations of values</li>\n</ul>\nCSPs deal with assignment of values to each variable. A **consistent** or legal assignment does not violate any of the constraints. A **complete** assignment is one in which every variable is assigned a value. A **solution** is a consistent, complete assignment. A **partial assignment** leaves some variables unassigned. A **partial solution** is a conistent partial assignment.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nCSP algorithm generates successors by choosing a new variable assignemnt OR by constraint propagation, a specific type of inference which uses the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for other variables. If we treat each variable as a node in a graph, and constraints as edges, then enforcing local consistency causes values to be eliminated.\n<ul>\n<li> node consistency - all values in a variables domain satisfy unary constraints</li>\n<li> arc consistency - all values in a variables domain satisfy binary constraints</li>\n<li> path consistency - uses implocty constraints inferred by looking at variable triples</li>\n<li> k-consistency - for any set of $k-1$ variables, and for any consistent assignment to those variables a conistent value can always be assigned to any $kth$ variable</li>\n</ul>\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nBacktracking search is a form of depth-first search, commonly used for solving CSPs. CSPs are commutative, therefore we need only consider one variable assignment at a time. so a backtracking search repeatedly makes an assignment for an unassigned variable, and continues untill either a solution is found, or it fails. If it fails, then we \"backtrack\" and try another path.\n\nwe can interleave this searching algorithm with inferencing. Each time we make an assignment we go as far as we can with inferencing. Forward checking is a simple form of inference which establishes arc-consistency everytime a variable is assigned.\n\nMAC (maintaining arc consistency) is an algorithm that detects inconsistencies by doing the following: when a variable $X_i$ is assigned, inference calls AC-3, but starts only with arcs (X_i,X_j), for $X_j$s that are unassigned. AC-3 does constraint propogation per usual and if any domain is reduced to the empty set, it returns a failure and we backtrack. Forward checking does not recursively propogate constraints like MAC.\n\nThis standard backtracking is \"chronological\" but it would be better to backtrack to a variable that may fix the problem; we can do this by keeping track of a conflict set and backjumping to the most recent assignment in the conflict set.\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nMin-Conflict \n\n1) start with a complete assigment (it will have constraint violations)\n\n2) randomly choose a conflicted variable; select a new value that results in the minimum number of comflicts with other variables\n\n3) keep doing this until we've eliminated all conflicts\n\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nComplexity of CSPs is strongly related to the structure of its constrain graph. we could break down CSPs into independent problems based on their connected compoenents then solve thes individually. It is rare though to have many independent subproblems. Another more easily solvable structure is a tree; any tree-structured CSP can be solved in linear time w.r.t. the number of variables.\n\n\nCutset conditioning is a way to reduce a contraint graph to a tree. We assign values to some variables so that the remaining variables for a tree. Requires finding such a set of of variables called a cycle cutset. \n\n\nTree decomposition is a second eay to reduce a constraint graph to a tree. we transform the original grpah into a tree where each node consists of a set of variables./n\n\nDecomposition has time $O(d^c (n-c)d^2)$ (where $c$ is cycle-cutset size). Tree decomposition has time $O(nd^{w+1})$ (where $w$ is the tree width). whenever you have a cycle-cutset size $c$ you also have a tree width size $w < c+1$, so tree decomposition is usually better time complexity. but cutset has linear memory while tree decomposition time complexity is exponential is $w$.\n \n\n## Module 6 Lecture Notes\n \nCSP components:\n\nfinite set of variables\n\nnon-empty domain of possible values ofr each variable\n\nfinite set of constraints which limit the values that variables can have\n\nSolutions to CSPs can be found by a completely general purpose algorithm, just need to formally specify the problem.\n\nmaximizing objective function - beyond the scope of the class\n\nBenefits of csp: 1) clean specification of many problems 2) csp knows which variable violates a contraint and therefore where to focus the search 3) csp automatically prunes branches that violate constraints.\n\nAC3 - a more efficient version of arc-consistency.\n\nheuristic 1) most constrained variable - choose the variable with the fewest legal values (aka minimum remaining value MRV heuristic)\n\nheuristic 2) most constrining variable - tie breaker among constrained variables, choose the variable with the most constraints on the remaining variables\n\nheuristic 3) least constraining value - given the variable, choose the least constraining value: i.e. the one that rules out the fewese values in the remaining variables\n\nheuristic 4) forward checking - keep track of remaining legal values for unassigned variables. terminate the search when any assigned variable has no remaining legal values.\n\n\nConstrait propagation goes beyond forward cheking and repeatedly enforces constraints locally. Arc-consistency, the simplest form of propagation makes each arc consistent. AC-3 is improved algorithm\n \n\n## Module 6 Definitions\n* **Consistent** - assignment does not violate constraints\n* **Complete** - all variables are assigned\n* **Solution** - complete and consistent assignment\n* **Unary constraint** - restricts a single variable\n* **Binary constraint** - constraint between two variables\n* **Global constraint** - constraint between an arbitrary number of variables\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nOur goal here is to give agents a way to represent general knowledge and a mechanism for combining and recombining information to achieve a variety of tasks.\n\n\nThe central component of a knowledge-based agent is a **Knowledge Base (KB)**, which is a set of sentences (used here as a technical term), each of which is written in a knowledge representation language and represents some assertion about the world. There are two kinds of sentences:\n\n**Axioms** - are given\n \n**Derived Sentences** - are new sentences derived from other sentences in a process called inference\n\nThe operation to add a new sentence to the KB is TELL, and to Query what is known is ASK.\n \n\nA KB can initially contain some background knowledge, then as the agent program runs, it will add information to the KB based on what it perceives and inferences that it makes.\n\n\nThe agent program continuously does the following three steps:\n\n<ol>\n<li>TELLs the KB what it perceives (percepts)</li>\n<li>ASKs what action it should perform, which involves reasoning and inference</li>\n<li>TELLs the KB what action was chosen</li>\n</ol>\nThis process allows for a declarative approach wherein the agent can be given knowledge and told what it goal is then know how to operate. In contrast with a procedural approach which ecodes desired behaviors directly in the program code.\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \nA grid world  for demonstrating KB agent behavior.\n\nThe Task Environment:\n<ul>\n<li> Performance: +1000 for success (leave cave with gold); -1000 for dying (pit, wumpus); -1 for each action; -10 for using arrow.</li>\n<li> Environment: 4x4 grid; agent starts in [1,1],  1 Wumpus, 1 gold, each other square can be pit with 0.2 probability.</li>\n<li> Actuators: move forward, left, or right; bumps into walls (no movement); Grab if in square with gold; shoot - shoots arrow, only once </li>\n<li>Sensors: perceive stench (from wumpus); perceive breeze (from pit); perceive glitter (from gold); perceive bump (from wall); perceive scream (dying wumpus); percept given as vector</li>\n</ul>\nWumpus world is deterministic, discrete, static, single agent (wumpus doesn’t move), sequential, partially observable. Main challenge is ignorance of configuration. \n \n\n## AIMA Chapter 7.3 Logic\n\nSentences of knowledge are expressed in a representation language. The **syntax** of a language specifies what is a well-formed sentence. Logic defines the **semantics** (meaning) of a sentence, i.e. the truth of the sentence with respect to a possible world, which we represent abstractly as a **model**.\n \n\n$m$ is a model of $\\alpha$ (i.e. $m$ satisfies $\\alpha$) if a sentence $\\alpha$ is true in a model $m$\n\n\n$M(\\alpha)=$ the set of all models of $\\alpha$ \n\n**Entailment**: $\\alpha$ entails $\\beta$ iff in every model in which $\\alpha$ is true $\\beta$ is also true \n \n$\\alpha \\vDash \\beta$ iff $M(\\alpha) \\subseteq M(\\beta)$  (note that $\\alpha$ is a stronger assertion, it rules out more possible worlds than $\\beta$)\n\n\nConsidering a KB as a set of sentences, the KB is true in all models where these sentences are true, and false in all models where any of these sentences is false. Thus a KB must entail each of its constituent sentences. Conversely, if we can prove that the KB entails a sentence $\\alpha_1$ (i.e. that in every model where KB is true, $\\alpha_1$ is also true) then we can conclude that $\\alpha_1$ is true and derives (i.e. follows from) from KB - this process is known as **logical inference**, and we denote it as follows:\n\n$KB \\vdash \\alpha_1$\n\n**Soundness**: only sentences that are entailed can be inferred (aka truth-preserving)\n\n**Completeness**: all sentences that are enatailed can be inferred\n\nUsefull analogy is a needle in a haystack, if all consequences of s sentence or set of sentences is the haystack, then all logical consequences are needles. Something is entailed if it is a needle something is inferred if it is found\n\n\nIf $KB$ is true in the real world, then any sentence derivce from $KB$ by sound inference is also true in the real world.\n\n\n\n\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n<h3>Syntax </h3>\nAllowable sentences:\n\n**Atomic sentences** - consist of a single **proposition symbol** which stands for a proposition that can be true or false. Typically an uppercase letter with other letters or subscripts (e.g. $P$, $W_{1,3}$, $FacingEast$)\n\n**Complex sentences** - constructed from simpler sentences using parenthesis and logical connectives\n\n**Logical connectives** (five main ones):\n<ul>\n<li>$\\neg$ (not) negation</li>\n<li>$\\wedge$ (and) conjuntion</li>\n<li>$\\vee$ (or) disjuntion</li>\n<li>$\\Rightarrow$ (implies, if-then) implication/conditional; $A\\Rightarrow B$, $A$ is the premise/antecedent, $B$ is the conclusion/consequent</li>\n<li>$\\Leftrightarrow$ (if and only if, iff) biconditional </li>\n</ul>\n<h3>Semantics</h3>\nA model consists of a truth value for every proposition symbol. Then for any sentence, the truth value is computed recursively starting with the atomic sentences.\n\n\nFor atomic sentences:\n<ul>\n<li>(trivially) $True$ is true in every model, and $False$ is false in every model</li>\n<li>the truth value of every proposition symbol is specified directly by the model</li>\n</ul>\nFor complex sentences\n<ul>\n<li>$\\neg P$ is true iff $P$ is false</li>\n<li>$P\\wedge Q$ is true iff both $P$ and $Q$ are true</li>\n<li>$P\\vee Q$ is true iff either $P$ or $Q$ is true</li>\n<li>$P\\Rightarrow Q$ is true unless $P$ is true and $Q$ is false</li>\n<li>$P\\Leftrightarrow Q$ is true iff $P$ and $Q$ are both true or both false</li>\n</ul>\n\nTo decide if $KB \\vdash \\alpha$, a simple inference procedure might generate every possible model by creating all possible permutations of truth statments to the relavent proposition symbols and then iterate over each one to check that $\\alpha$ is true in every model in which $KB$ is true. This approach is sound and complete, but has a time complexity of $O(2^n)$.\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \n**Logical equivalence**: two sentences $\\alpha$ and $\\beta$ are equivalent iff each of them entails the other (i.e. if they are true in the same set of models)\n\n$\\alpha \\equiv \\beta$ iff $\\alpha \\vDash \\beta$ and $\\beta \\vDash \\alpha$\n\n**Validity**: a sentence is valid if it is true in *all* models; such a sentence is also known as a **tautology**\n\n**Satisfiability**: a sentence is satisfiable if it is true in (i.e. satisfied by) *some* model \n\nStandard Logical Equivalences:\n\n$(\\alpha \\wedge \\beta) \\equiv (\\beta \\wedge \\alpha)$ Commutativity of $\\wedge$\n\n$(\\alpha \\vee \\beta) \\equiv (\\beta \\vee \\alpha)$ Commutativity of $\\vee$\n\n$((\\alpha \\wedge \\beta) \\wedge \\gamma) \\equiv (\\alpha \\wedge (\\beta \\wedge \\gamma))$ Associativity of $\\wedge$\n\n$((\\alpha \\vee \\beta) \\vee \\gamma) \\equiv (\\alpha \\vee (\\beta \\vee \\gamma))$ Associativity of $\\vee$\n\n$\\neg (\\neg \\alpha) \\equiv \\alpha$ Double-negation elimination\n\n$(\\alpha\\Rightarrow\\beta) \\equiv (\\neg\\beta \\Rightarrow\\neg\\alpha)$ Contraposition\n\n$(\\alpha\\Rightarrow\\beta) \\equiv (\\neg\\alpha \\vee \\beta)$ Implication elimination\n\n$(\\alpha\\Leftrightarrow\\beta) \\equiv ((\\alpha\\Rightarrow\\beta) \\wedge (\\beta \\Rightarrow\\alpha))$ Biconditional elimination\n\n$\\neg(\\alpha \\wedge \\beta) \\equiv (\\neg\\alpha \\vee \\neg\\beta)$ De Morgan\n\n$\\neg(\\alpha \\vee \\beta) \\equiv (\\neg\\alpha \\wedge \\neg\\beta)$ De Morgan\n\n$((\\alpha \\wedge \\beta) \\vee \\gamma) \\equiv ((\\alpha \\wedge \\beta) \\vee (\\alpha \\wedge \\gamma)))$ Distributivity of $\\wedge$ over $\\vee$\n\n$((\\alpha \\vee \\beta) \\wedge \\gamma) \\equiv ((\\alpha \\vee \\beta) \\wedge (\\alpha \\vee \\gamma)))$ Distributivity of $\\vee$ over $\\wedge$\n\n\n\n\n\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": {}
        }
      ]
    }
  ]
}