{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "157e20a8-e398-4304-9c6d-abd4bf0f2878"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3aaa2307-ec5d-48eb-f8e6-f1329f614f9b"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Intelligence is either human performance or 'rationality': doing the right thing.\n",
        "Intelligence can be categorized as thought process or behavior. Turing test: human interrogator\n",
        "asks written questions and tries tofigure out if the responses came from a computer. We want\n",
        "machines to pursue our objectives, not their own.\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" John Searle distinguished between weak and strong AI. Hubert Dreyfus thought\n",
        "that human  behavior was toocomplex to be embodies by a logical agent and that cognition takes\n",
        "place inside a body. We need to study the system as a whole. Godel's incompleteness\n",
        "theorem saysthat a formal axiomatic framework can't prove itself comletely.\"\"\"\n",
        "chapter27_2 = \"\"\" Is a machine that acts intelligently actually thinking or only be\n",
        "a simulation of thinking? Semantic distinction, so doesn't matter so much. John Searle\n",
        "proposed the Chinese Room experiment about a human who doesn't speak Chinese and yet is\n",
        "able to repond in fluent Chinese to questions by following a guidebook and matching.\n",
        "This would pass the Turing test without any understanding being involved. He believed\n",
        "in biological naturalism which says that it is neurons that matter for thinking\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent's choice of action can depend on its built in knowledge\n",
        "and its percept sequence up to the present. Agents should have significant\n",
        "computational resources and task environment requires nontrivial decision making.\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\" Humans need todesign performance metric. Some agent designs\n",
        "have an explicit representation of the performancemeasure, others don't. They\n",
        "might notknow why they are doing the right thing. Should design a performance\n",
        "measure according to what we want done, not how we think it should behave.\n",
        "Rationality depends on a performance measure, priorknowledge, actions available,\n",
        "and percept sequence. Rationality maximized expected performance, perfection/\n",
        "omniscience maximizes actual performance.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" Task environments are the problems to which rational agents are\n",
        "the solutions. Need to  specify PEAS (Performance, Environment, Actuators, Sensors).\n",
        "for each agent. Fully observable/partially observable environment is whether the\n",
        "agent's sensors giveit access to the complete state of the environment.\n",
        "Single/multiagent problems is whether ornot there is another agent (being\n",
        "maximizing its own performance metric). Deterministic vs nondeterministic is\n",
        "whether the next state of the environment is completely determined by the current\n",
        "state and the action from an agent. (Stochastic if it explicitly deals in\n",
        "probabilities, nondeterministic if not quantified.) Episodic/sequential is\n",
        "if the agent's experience is divided into atomic episodes, where next episode\n",
        "doesn't depend on previous one. Static/dynamic is if an environment can change\n",
        "while an agent is deliberating. (Semidynamic is if environment doesn't change\n",
        "but performance score does.) Discrete/continuous state, time, percepts and actions.\n",
        "Known/unknown describes the  agent's knowledge about the laws ofphysics of\n",
        "the environment and the consequences of actions.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"Agent = architecture + program. Agent program takes current\n",
        "percept asinput and agent function could depend on entire percepthistory. Would\n",
        "need to have agent remember percepts. Can't implement table with all possible percept\n",
        "sequences, because there are too many. Simple reflex agents don't perform well\n",
        "in partially observable environments. Model-based reflex agents have an internal\n",
        "state which depends on the percept history. Has a transition model and sensor\n",
        "model. Goals only have a binary distinction of reaching it or not, whereas\n",
        "utility can compare different states by assigning them scores. A learning agent\n",
        "has a learning element (takes feedback from critic) and performace element\n",
        "which is modified by learning element. Also has critic and problem generator.\n",
        "Problem generator suggests actions that will lead to new and informative\n",
        "experiences (exploration). Distributed representation is more robust to noise\n",
        "than localist representation.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"Rene Descartes: Cogito ergo sum. Mechanical Turk-\n",
        "'robot' that plays chess, but really a person. Descartes thought that automoton\n",
        "couldn't use language. Eliza-early NLP program imitating Rogerian psychotherapy.\n",
        "Daniel Dennet-brain in a vat-don't need biological brain to think.\"\"\"\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",
        "\"AI disciplines\": \"NLP, Knowledge representation, Automated reasoning, ML, Total Turing  test, CV,  Robotics\",\n",
        "\"Total Turing test\": \"Turing test+perceiving and acting in the world\",\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"rational agent\": \"agent that acts to achieve the best (expected) outcome\",\n",
        "\"value alignment problem\": \"values in machine must be aligned with human values\",\n",
        "\"weak AI\": \"act as if it is intelligent\",\n",
        "\"strong AI\": \"machine that can solve a wide variety of tasks like a human, even novel ones\",\n",
        "\"good old-fashioned AI (GOFAI)\": \"simple logical  agent design (can't capture complex behavior in all scenarios)\",\n",
        "\"qualia\": \"intrinsic nature of experience\",\n",
        "\"percept\" : \"content an agent's sensors are perceiving\",\n",
        "\"agent function\": \"map from any given percept sequence to an action\",\n",
        "\"agent program\": \"implementation of an agent function on a physical system\",\n",
        "\"consequentialism\": \"evaluate an agent's behavior by its consequences\",\n",
        "\"performance measure\": \"evaluate any given sequence of environment states\",\n",
        "\"omniscience\": \"agent knows the actual outcome of its actions and can act accordingly\",\n",
        "\"information gathering\": \"doing actions in order to modify future percepts\",\n",
        "\"exploration\": \"creating a map of an initially unknown environment\",\n",
        "\"autonomous\": \"learn what it can do to compensate for partial orincorrect prior knowledge\",\n",
        "\"agent architecture\": \"computing device with sensors and actuators\",\n",
        "\"simple reflex agent\": \"select actions only based on current percept\",\n",
        "\"condition-action rule\": \"if/then statement about which action to take\",\n",
        "\"model-based reflex agents\": \"keeps track of the part of the world it can't see now\",\n",
        "\"transition model\": \"knowledge about how the world works\",\n",
        "\"sensor model\": \"how the world affects the sensors\",\n",
        "\"goal-based agent\": \"takes actions because it has a goal\",\n",
        "\"utility function\": \"internalization of performace measure\",\n",
        "\"utility-based agent\": \"agent with a utility function rather than just a goal\",\n",
        "\"atomic representation\": \"each state is indivisible with no internal structure\",\n",
        "\"factored representation\": \"splits up each state into fixed set of variables or attributes (each with value)\",\n",
        "\"structured representation\": \"world has thigs related to each other, not just variables with values\",\n",
        "\"localist representation\": \"one-to-one mapping between concepts and memory locations\",\n",
        "\"distributed representation\": \"representation of concept is spread over memory locations, each location stores several concepts\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "26a9457b-5e99-4273-edcb-92a5106116c7"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Intelligence is either human performance or 'rationality': doing the right thing.\nIntelligence can be categorized as thought process or behavior. Turing test: human interrogator\nasks written questions and tries tofigure out if the responses came from a computer. We want\nmachines to pursue our objectives, not their own.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n John Searle distinguished between weak and strong AI. Hubert Dreyfus thought\nthat human  behavior was toocomplex to be embodies by a logical agent and that cognition takes\nplace inside a body. We need to study the system as a whole. Godel's incompleteness\ntheorem saysthat a formal axiomatic framework can't prove itself comletely.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Is a machine that acts intelligently actually thinking or only be\na simulation of thinking? Semantic distinction, so doesn't matter so much. John Searle\nproposed the Chinese Room experiment about a human who doesn't speak Chinese and yet is\nable to repond in fluent Chinese to questions by following a guidebook and matching.\nThis would pass the Turing test without any understanding being involved. He believed\nin biological naturalism which says that it is neurons that matter for thinking\n\n## AIMA 2.1 Agents and Environments\n An agent's choice of action can depend on its built in knowledge\nand its percept sequence up to the present. Agents should have significant\ncomputational resources and task environment requires nontrivial decision making.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Humans need todesign performance metric. Some agent designs\nhave an explicit representation of the performancemeasure, others don't. They\nmight notknow why they are doing the right thing. Should design a performance\nmeasure according to what we want done, not how we think it should behave.\nRationality depends on a performance measure, priorknowledge, actions available,\nand percept sequence. Rationality maximized expected performance, perfection/\nomniscience maximizes actual performance.\n\n\n## AIMA 2.3 The Nature of Environments\n Task environments are the problems to which rational agents are\nthe solutions. Need to  specify PEAS (Performance, Environment, Actuators, Sensors).\nfor each agent. Fully observable/partially observable environment is whether the\nagent's sensors giveit access to the complete state of the environment.\nSingle/multiagent problems is whether ornot there is another agent (being\nmaximizing its own performance metric). Deterministic vs nondeterministic is\nwhether the next state of the environment is completely determined by the current\nstate and the action from an agent. (Stochastic if it explicitly deals in\nprobabilities, nondeterministic if not quantified.) Episodic/sequential is\nif the agent's experience is divided into atomic episodes, where next episode\ndoesn't depend on previous one. Static/dynamic is if an environment can change\nwhile an agent is deliberating. (Semidynamic is if environment doesn't change\nbut performance score does.) Discrete/continuous state, time, percepts and actions.\nKnown/unknown describes the  agent's knowledge about the laws ofphysics of\nthe environment and the consequences of actions.\n\n\n## AIMA 2.4 The Structure of Agents\nAgent = architecture + program. Agent program takes current\npercept asinput and agent function could depend on entire percepthistory. Would\nneed to have agent remember percepts. Can't implement table with all possible percept\nsequences, because there are too many. Simple reflex agents don't perform well\nin partially observable environments. Model-based reflex agents have an internal\nstate which depends on the percept history. Has a transition model and sensor\nmodel. Goals only have a binary distinction of reaching it or not, whereas\nutility can compare different states by assigning them scores. A learning agent\nhas a learning element (takes feedback from critic) and performace element\nwhich is modified by learning element. Also has critic and problem generator.\nProblem generator suggests actions that will lead to new and informative\nexperiences (exploration). Distributed representation is more robust to noise\nthan localist representation.\n\n\n## Module 1 Lecture Notes\nRene Descartes: Cogito ergo sum. Mechanical Turk-\n'robot' that plays chess, but really a person. Descartes thought that automoton\ncouldn't use language. Eliza-early NLP program imitating Rogerian psychotherapy.\nDaniel Dennet-brain in a vat-don't need biological brain to think.\n\n## Module 1 Definitions\n* **Ai disciplines** - NLP, Knowledge representation, Automated reasoning, ML, Total Turing  test, CV,  Robotics\n* **Total turing test** - Turing test+perceiving and acting in the world\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - agent that acts to achieve the best (expected) outcome\n* **Value alignment problem** - values in machine must be aligned with human values\n* **Weak ai** - act as if it is intelligent\n* **Strong ai** - machine that can solve a wide variety of tasks like a human, even novel ones\n* **Good old-fashioned ai (gofai)** - simple logical  agent design (can't capture complex behavior in all scenarios)\n* **Qualia** - intrinsic nature of experience\n* **Percept** - content an agent's sensors are perceiving\n* **Agent function** - map from any given percept sequence to an action\n* **Agent program** - implementation of an agent function on a physical system\n* **Consequentialism** - evaluate an agent's behavior by its consequences\n* **Performance measure** - evaluate any given sequence of environment states\n* **Omniscience** - agent knows the actual outcome of its actions and can act accordingly\n* **Information gathering** - doing actions in order to modify future percepts\n* **Exploration** - creating a map of an initially unknown environment\n* **Autonomous** - learn what it can do to compensate for partial orincorrect prior knowledge\n* **Agent architecture** - computing device with sensors and actuators\n* **Simple reflex agent** - select actions only based on current percept\n* **Condition-action rule** - if/then statement about which action to take\n* **Model-based reflex agents** - keeps track of the part of the world it can't see now\n* **Transition model** - knowledge about how the world works\n* **Sensor model** - how the world affects the sensors\n* **Goal-based agent** - takes actions because it has a goal\n* **Utility function** - internalization of performace measure\n* **Utility-based agent** - agent with a utility function rather than just a goal\n* **Atomic representation** - each state is indivisible with no internal structure\n* **Factored representation** - splits up each state into fixed set of variables or attributes (each with value)\n* **Structured representation** - world has thigs related to each other, not just variables with values\n* **Localist representation** - one-to-one mapping between concepts and memory locations\n* **Distributed representation** - representation of concept is spread over memory locations, each location stores several concepts\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 = \"\"\"Memoization is used ofr dynamic programming and recursion.\n",
        "Remember previous calls so don't have to recurse every time. Functions are treated\n",
        "as objects-can be passed into functions as arguments. Magic methods-double\n",
        "underscore before and after function name so can use overloaded operators. E.g.\n",
        "init,  str, len, cmp, add, neg, copy. For executing code, insert (if name == main:)\n",
        "(both double underscored). Iterators can be used in loop because they\n",
        "have iter magic method. Need to have a next magic method, but no function whether\n",
        "it has next-catches StopIteration exception (memory efficient). Generators are\n",
        "like iterators but don't need to initialize iterator. Use yield instead of return.\n",
        "Will pause code to return value and continue running code when called again.\n",
        "Lists, dicts, sets are mutable. Tuples and strings are immutable. Labels are\n",
        "always changeable, even if thing it points to is immutable.\\n\n",
        "\n",
        "\\t print([(first, second) for first in range(3) for second in range(3)])\n",
        "\n",
        "\\t [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 360
        },
        "outputId": "5508c91f-6743-47c9-8ee6-03e86970ae47"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\nMemoization is used ofr dynamic programming and recursion.\nRemember previous calls so don't have to recurse every time. Functions are treated\nas objects-can be passed into functions as arguments. Magic methods-double\nunderscore before and after function name so can use overloaded operators. E.g.\ninit,  str, len, cmp, add, neg, copy. For executing code, insert (if name == main:)\n(both double underscored). Iterators can be used in loop because they\nhave iter magic method. Need to have a next magic method, but no function whether\nit has next-catches StopIteration exception (memory efficient). Generators are\nlike iterators but don't need to initialize iterator. Use yield instead of return.\nWill pause code to return value and continue running code when called again.\nLists, dicts, sets are mutable. Tuples and strings are immutable. Labels are\nalways changeable, even if thing it points to is immutable.\n\n\n\t print([(first, second) for first in range(3) for second in range(3)])\n\n\t [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]\n\n\n## Module 2 Definitions\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 use atomic representations. If they\n",
        "use factored or structured, called planning agents. Agent does Goal formulation,\n",
        "(what is its goal- limit objectives and actions), Problem formulation\n",
        "(description of states and actions necessary to reach goal), Search\n",
        "(simulation of action sequences until it finds goal), Execution. In a\n",
        "fully observable deterministic known environment, solution to any problem\n",
        "is a fixed sequence of actions. Agent can ignore percepts if model and\n",
        "solution are correct. Search problem has state space, initial state,\n",
        "set of goal states, set of actions given a state, transition model,\n",
        "action cost function (relevent to performance measure). Can represent\n",
        "state space by graph (vertices=states, directed edges=actions).\n",
        "Intelligent abstraction removes as much detail as possible while retaining\n",
        "validity and making sure that abstract actions can be carried out.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"N/A\"\"\"\n",
        "chapter3_3 = \"\"\" Can form a search tree over state-space graph and use it\n",
        "to search for goal states. Each node in the tree has a unique path back to the\n",
        "initial state. Frontier is states/nodes that have been reached but not yet\n",
        "expanded (divides interior from exterior). Best first search: choose node\n",
        "on frontier with minimum evaluation function f(n). If it is a goal, return\n",
        "it and if not, expand it. Each child node is added to frontier (if already\n",
        "on frontier, replace if new path has smaller cost). Each node contains\n",
        "State, Parent, Action (applied to get there), Path cost g(n). Use queue\n",
        "to store frontier nodes (have priority queue-best first search, FIFO-BFS,\n",
        "LIFO queue/stack-DFS).Reached states can be stores in a lookup table like\n",
        "hash table (key is state, value is node for state). If no cap on cycles or\n",
        "redundant paths, number of possible sequences explodes. Could remember\n",
        "all previously reached states and keep only best path or could not worry\n",
        "about redundant paths. Best first search is a graph search. Could also check\n",
        "for cycles but not redundant paths (follow chain of parents to see if\n",
        "node at end of path has appeared earlier). Size of state-space graph =\n",
        "|V| + |E| (number of state nodes + number of state/action pairs).\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" BFS: root node us expanded than all of its successors are\n",
        "expanded, then all of their successors, etc. Complete even on infinite\n",
        "state-spaces. Could be implemented as best first search with f(n)=depth of node.\n",
        "Use FIFO queue and add new nodes to back of queue. Reached can be set of states.\n",
        "Can do early goal test. Complete, and optimal when all actions have the same cost.\n",
        "Time and space complexity both are O(b^d). Dijkstra's algorithm/uniform-cost search\n",
        "works when actions have different costs. Uses best first search where f(n) is\n",
        "the cost of the path from root to current node. Time and space complexity of\n",
        "O(b^(1+floor(C*/e))) where C* is the cost of the optimal solution and e>0 is\n",
        "a lower bound on the cost of each action (can be much larger than b^d unless\n",
        "action costs are equal, where it is then O(b^(d+1))). Complete and optimal.\n",
        "DFS expands the deepest node in the frontier. Could be implemented by best first\n",
        "search with f(n) the negative of the depth. Could also be implemented as a tree\n",
        "search (not graph search). Not optimal, and only complete for finite acyclic\n",
        "state-spaces. Time of O(number of states) and memory of O(bm). Backtracking\n",
        "search is a variant of DFS that uses less memory. Only one successor is generated\n",
        "at a time and each node remembers which node to expand next. Successors are\n",
        "generated by modifying current state instead of allocating new memory. Space is\n",
        "O(m) and can check for cycles in O(1) instead of O(m). Depth limited search\n",
        "is DFS with a limit l which 'have no successors'. Time is O(b^l) and space is\n",
        "O(bl). Might be incomplete if l is to shallow. Iterative deepening search\n",
        "if depth limited search while increasing l with every call. Memory of O(bd) if\n",
        "there is a solution and O(bm) if there isn't. Complete and optimal on finite spaces.\n",
        "Need to check for cycles to be complete. Time is O(b^d) if there is a solution\n",
        "and O(b^m) if there isn't. Bidirectional search starts searching from initial\n",
        "state and backward from goal state and try to meet. Have solution when the \n",
        "two frontiers collide. If evaluation is path cost, first solution found is\n",
        "optimal, otherwise need to check all solutions. Complete and optimal. Time\n",
        "and space O(b^(d/2)).\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"N/A\"\"\"\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",
        "\"informed agent\": \"can estimate how far it is from goal\",\n",
        "\"uninformed agent\": \"can't estimate how far from goal\",\n",
        "\"solution\": \"sequence of actions that reaches the goal\",\n",
        "\"open-loop\": \"doesn't take  percepts into account\",\n",
        "\"closed-loop\": \"takes percepts into account\",\n",
        "\"state space\": \"set of possible states environment can be in\",\n",
        "\"action cost funtion\": \"c(s, a, s') gives numeric cost when taking an action (additive)\",\n",
        "\"path\": \"sequence of actions\",\n",
        "\"optimal solution\": \"solution with lowest path cost\",\n",
        "\"standardized problem\": \"illustrates or exercises problem solving methods\",\n",
        "\"real-world problem\": \"problem whose solutions people actually use, idiosyncratic\",\n",
        "\"egocentric actions\": \"defined with respect to the agent (forward/backward as opposed to which cell to move to)\",\n",
        "\"search algorithm\": \"takes a search problem as input and returns solution or indication of failure\",\n",
        "\"search tree\": \"search over graph of state space with initial state as root node\",\n",
        "\"frontier\": \"separates two regions of state space graph: interior-states have been expanded; exterior, have not been reached\",\n",
        "\"graph search\": \"checks for redundant paths\",\n",
        "\"tree-like search\": \"doesn't check for redundant paths\",\n",
        "\"completeness\": \"algorithm guaranteed to find solution when there is one and correctly report failure if there isn't\",\n",
        "\"cost optimality\": \"finds solution with lowest path cost\",\n",
        "\"time complexity\": \"how long until search finds a solution\",\n",
        "\"space complexity\": \"how much memory is needed to perform search\",\n",
        "\"d\": \"depth of number of actions in an optimal solution\",\n",
        "\"m\": \"maximum number of actions in any path\",\n",
        "\"b\": \"branching factor-number of successors of a node to be considered\",\n",
        "\"early goal test\": \"test if a state is a goal state as soon as it is generated\",\n",
        "\"late goal test\": \"test if a state is a goal state when it is popped off the queue\",\n",
        "\"abstract state\": \"equivalence class between real world states\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "2426ecec-0bf1-4e39-d6eb-67cfc97e497c"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem-solving agents use atomic representations. If they\nuse factored or structured, called planning agents. Agent does Goal formulation,\n(what is its goal- limit objectives and actions), Problem formulation\n(description of states and actions necessary to reach goal), Search\n(simulation of action sequences until it finds goal), Execution. In a\nfully observable deterministic known environment, solution to any problem\nis a fixed sequence of actions. Agent can ignore percepts if model and\nsolution are correct. Search problem has state space, initial state,\nset of goal states, set of actions given a state, transition model,\naction cost function (relevent to performance measure). Can represent\nstate space by graph (vertices=states, directed edges=actions).\nIntelligent abstraction removes as much detail as possible while retaining\nvalidity and making sure that abstract actions can be carried out.\n\n\n## AIMA Chapter 3.2 Example Problems\nN/A\n\n## AIMA Chapter 3.3 Search Algorithms\n Can form a search tree over state-space graph and use it\nto search for goal states. Each node in the tree has a unique path back to the\ninitial state. Frontier is states/nodes that have been reached but not yet\nexpanded (divides interior from exterior). Best first search: choose node\non frontier with minimum evaluation function f(n). If it is a goal, return\nit and if not, expand it. Each child node is added to frontier (if already\non frontier, replace if new path has smaller cost). Each node contains\nState, Parent, Action (applied to get there), Path cost g(n). Use queue\nto store frontier nodes (have priority queue-best first search, FIFO-BFS,\nLIFO queue/stack-DFS).Reached states can be stores in a lookup table like\nhash table (key is state, value is node for state). If no cap on cycles or\nredundant paths, number of possible sequences explodes. Could remember\nall previously reached states and keep only best path or could not worry\nabout redundant paths. Best first search is a graph search. Could also check\nfor cycles but not redundant paths (follow chain of parents to see if\nnode at end of path has appeared earlier). Size of state-space graph =\n|V| + |E| (number of state nodes + number of state/action pairs).\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS: root node us expanded than all of its successors are\nexpanded, then all of their successors, etc. Complete even on infinite\nstate-spaces. Could be implemented as best first search with f(n)=depth of node.\nUse FIFO queue and add new nodes to back of queue. Reached can be set of states.\nCan do early goal test. Complete, and optimal when all actions have the same cost.\nTime and space complexity both are O(b^d). Dijkstra's algorithm/uniform-cost search\nworks when actions have different costs. Uses best first search where f(n) is\nthe cost of the path from root to current node. Time and space complexity of\nO(b^(1+floor(C*/e))) where C* is the cost of the optimal solution and e>0 is\na lower bound on the cost of each action (can be much larger than b^d unless\naction costs are equal, where it is then O(b^(d+1))). Complete and optimal.\nDFS expands the deepest node in the frontier. Could be implemented by best first\nsearch with f(n) the negative of the depth. Could also be implemented as a tree\nsearch (not graph search). Not optimal, and only complete for finite acyclic\nstate-spaces. Time of O(number of states) and memory of O(bm). Backtracking\nsearch is a variant of DFS that uses less memory. Only one successor is generated\nat a time and each node remembers which node to expand next. Successors are\ngenerated by modifying current state instead of allocating new memory. Space is\nO(m) and can check for cycles in O(1) instead of O(m). Depth limited search\nis DFS with a limit l which 'have no successors'. Time is O(b^l) and space is\nO(bl). Might be incomplete if l is to shallow. Iterative deepening search\nif depth limited search while increasing l with every call. Memory of O(bd) if\nthere is a solution and O(bm) if there isn't. Complete and optimal on finite spaces.\nNeed to check for cycles to be complete. Time is O(b^d) if there is a solution\nand O(b^m) if there isn't. Bidirectional search starts searching from initial\nstate and backward from goal state and try to meet. Have solution when the \ntwo frontiers collide. If evaluation is path cost, first solution found is\noptimal, otherwise need to check all solutions. Complete and optimal. Time\nand space O(b^(d/2)).\n\n\n## Module 3 Lecture Notes\nN/A\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Informed agent** - can estimate how far it is from goal\n* **Uninformed agent** - can't estimate how far from goal\n* **Solution** - sequence of actions that reaches the goal\n* **Open-loop** - doesn't take  percepts into account\n* **Closed-loop** - takes percepts into account\n* **State space** - set of possible states environment can be in\n* **Action cost funtion** - c(s, a, s') gives numeric cost when taking an action (additive)\n* **Path** - sequence of actions\n* **Optimal solution** - solution with lowest path cost\n* **Standardized problem** - illustrates or exercises problem solving methods\n* **Real-world problem** - problem whose solutions people actually use, idiosyncratic\n* **Egocentric actions** - defined with respect to the agent (forward/backward as opposed to which cell to move to)\n* **Search algorithm** - takes a search problem as input and returns solution or indication of failure\n* **Search tree** - search over graph of state space with initial state as root node\n* **Frontier** - separates two regions of state space graph: interior-states have been expanded; exterior, have not been reached\n* **Graph search** - checks for redundant paths\n* **Tree-like search** - doesn't check for redundant paths\n* **Completeness** - algorithm guaranteed to find solution when there is one and correctly report failure if there isn't\n* **Cost optimality** - finds solution with lowest path cost\n* **Time complexity** - how long until search finds a solution\n* **Space complexity** - how much memory is needed to perform search\n* **D** - depth of number of actions in an optimal solution\n* **M** - maximum number of actions in any path\n* **B** - branching factor-number of successors of a node to be considered\n* **Early goal test** - test if a state is a goal state as soon as it is generated\n* **Late goal test** - test if a state is a goal state when it is popped off the queue\n* **Abstract state** - equivalence class between real world states\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"Greedy best-first search expands node with lowest h(n) value.\n",
        "Best-first search with f(n)=h(n). Can find solution without ever expanding node\n",
        "that isn't on solution  path. Complete in finite spaces, but not optimal. Time\n",
        "and space is O(|V|). With good heuristic, can sometimes be O(bm). A* uses\n",
        "f(n)=g(n)+h(n)=path cost so far + estimated future cost. Complete, and optimal\n",
        "if heuristic is admissible. Consistency is stronger than admissibility. With\n",
        "consistent heuristic, first time we reach a state it will be on optimal path.\n",
        "With inadmissible heuristic, can be optimal if there is a cost optimal path where\n",
        "h(n) is admissible for all n or if h(n) never overestimates costs by more than\n",
        "C2-C* (different in costs of best two solutions). Can draw contours of regions\n",
        "where all nodeshave f(n)=g(n)+h(n) <= constant. A* fans out adding nodes in\n",
        "bands of increasing f(n). With uniform cost, have circular contours of\n",
        "g(n) <= constant. With A*, contours stretch toward goal state and narrow \n",
        "around the optimal path. f=g+h will monotonically increase iff the heuristic\n",
        "is consistent. A* is optimally efficient because any other algorithm that expands\n",
        "from the initial state using the same heuristic must expand all nodes expanded\n",
        "by A*. Could try using inadmissible heuristic for A* if it is more accurate:\n",
        "doesn't necessarily give optimal solution but expands fewer nodes. Weighted A*\n",
        "is where weweight heuristic more heavily: f(n) = g(n) + W*h(n) for W>1. Will\n",
        "find solution that is between C* and (W)(C*) but usually closer to C*. Other\n",
        "algorithms: A*: W=1, Uniform cost: W=0, Greedy best-first: W=inf,\n",
        "Weighted A*: 1<W<inf. Speedy search is version of greedy best-first that uses\n",
        "heuristic h(n)=estimated number of actions to reach goal (unbounded cost search\n",
        "algorithm). If all actions have same cost, same as greedy best-first. Otherwise,\n",
        "fast but might have a high cost. Beam search limits the size of the frontier by only\n",
        "storing the k nodes with the best f scores. Incomplete and suboptimal, but saves\n",
        "space and is fast. Could also do iterative deepening A* with cutoff of f as the\n",
        "smallest f of any node that exceeded the cutoff on the previous iteration.\n",
        "Recursive best first search is DFS with f_limit keeping track of best f value of\n",
        "alternative path from any ancestor of current node. If current node exceeds it,\n",
        "rewind to it. Replace f value of each node by backed-up value. Optimal if\n",
        "heuristic function is admissible. Space is linear in depth of deepest optimal solution.\n",
        "Time is difficult to ascertain. MA* (memory bounded A*) and SMA* (simplified MA*).\n",
        "Expands until memoryis full. Drop worst leaf node (highest f) and back up its value\n",
        "to its parent. Expands newest best leaf and deletes oldest worst leaf. Complete\n",
        "if possible to store in memory, and optimal if reachable. Otherwise, returns best\n",
        "reachable solution. Bidirectional heuristic search can't be optimally efficient.\n",
        "Not necessarily better than A*.\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" If A* generates N nodes and solution depth is d, b* (effective\n",
        "branching factor) is the branching factor that a uniform tree of depth d would\n",
        "have in order to contain N+1 nodes. N+1=1+b*+(b*)^2 +...+(b*)^d. Well designed\n",
        "heuristic has b* close to 1. If h2(n)>=h1(n) for two admissible heuristics, h2\n",
        "dominates h1. A* will never expand more nodes using h2 than using h1. Can generate\n",
        "heuristic functions by relaxing constraints on the original problem. State space\n",
        "graph is a supergraph of the original problem (same nodes with more edges). If\n",
        "there are multiple admissible heuristics, can also use h(n)=max[h1(n),...,hk(n)].\n",
        "h(n) is admissible and consistent if all hi(n) are and dominate them all.\n",
        "Choosing at random can be inconsistent, but is faster. Could also get heuristic\n",
        "from solution cost of subproblem. Could also choose landmark points from the\n",
        "vertices and compute cost between landmarks to and from all other vertices.\n",
        "Then create an efficient but inadmissible heuristic as minimum over all\n",
        "landmarks of cost from current node to landmark then to goal. Admissible\n",
        "heuristic would be max_{L \\in Landmarks} | C*(n, L) - C* (goal, L)|\n",
        "(differential heuristic). Could pick landmarks at random or try to space them out.\n",
        "If you have data, pick ones that are common. Metalevel state space is the space\n",
        "of states representing the internal state of a program that is searching\n",
        "in the object-level state space. Could also train a model to estimate heuristics\n",
        "using features in the state space. Not necessarily admissible or consistent.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"N/A\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"heuristic function\" : \"h(n) = estimated cost of cheapest path from node n to a goal state\",  \n",
        "\"admissible heuristic\": \"heuristic that never overestimates cost from n to goal (optimistic)\",\n",
        "\"consistent heuristic\": \"if for every node n and successor n' generated by a, h(n) <= c(n,a,n') + h(n')\",\n",
        "\"surely expanded nodes\": \"nodes in A* that can be reached from initial state on path where every node has f(n) < C*\",\n",
        "\"pruning\": \"eliminating possibilities from consideration without examining them\",\n",
        "\"satisficing solution\": \"solutions that are suboptimal but 'good enough'\",\n",
        "\"detour index\": \"multiplier applied to straight line distance to account for curvature of roads\",\n",
        "\"bounded suboptimal search\": \"looks for a solution guaranteed to be within constant factor W of optimal cost\",\n",
        "\"bounded cost search\": \"looks for a solution whose cost is less than constant C\",\n",
        "\"unbounded cost search\": \"accept solution at any cost, as long as we find it quickly\",\n",
        "\"reference count\": \"how many ways a state has been reached already\",\n",
        "\"backed-up value\": \"best f value of a node's children\",\n",
        "\"relaxed problem\": \"problem with some constraints removed (used to generate heuristic\",\n",
        "\"pattern database\": \"store exact solutions costs for every possible subproblem\",\n",
        "\"disjoint pattern databases\": \"sum of costs of subproblems (if no overlap in solution actions)\",\n",
        "\"precomputation\": \"doing some optimal path costs beforehand so don't need to calculate in real time\",\n",
        "\"shortcuts\": \"artificial edges in graph that define an optimal multiaction path\",\n",
        "\"differential heuristic\": \"heuristic function composed of difference of two others\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "06c8e704-0224-4733-90e7-b84981fa9e44"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nGreedy best-first search expands node with lowest h(n) value.\nBest-first search with f(n)=h(n). Can find solution without ever expanding node\nthat isn't on solution  path. Complete in finite spaces, but not optimal. Time\nand space is O(|V|). With good heuristic, can sometimes be O(bm). A* uses\nf(n)=g(n)+h(n)=path cost so far + estimated future cost. Complete, and optimal\nif heuristic is admissible. Consistency is stronger than admissibility. With\nconsistent heuristic, first time we reach a state it will be on optimal path.\nWith inadmissible heuristic, can be optimal if there is a cost optimal path where\nh(n) is admissible for all n or if h(n) never overestimates costs by more than\nC2-C* (different in costs of best two solutions). Can draw contours of regions\nwhere all nodeshave f(n)=g(n)+h(n) <= constant. A* fans out adding nodes in\nbands of increasing f(n). With uniform cost, have circular contours of\ng(n) <= constant. With A*, contours stretch toward goal state and narrow \naround the optimal path. f=g+h will monotonically increase iff the heuristic\nis consistent. A* is optimally efficient because any other algorithm that expands\nfrom the initial state using the same heuristic must expand all nodes expanded\nby A*. Could try using inadmissible heuristic for A* if it is more accurate:\ndoesn't necessarily give optimal solution but expands fewer nodes. Weighted A*\nis where weweight heuristic more heavily: f(n) = g(n) + W*h(n) for W>1. Will\nfind solution that is between C* and (W)(C*) but usually closer to C*. Other\nalgorithms: A*: W=1, Uniform cost: W=0, Greedy best-first: W=inf,\nWeighted A*: 1<W<inf. Speedy search is version of greedy best-first that uses\nheuristic h(n)=estimated number of actions to reach goal (unbounded cost search\nalgorithm). If all actions have same cost, same as greedy best-first. Otherwise,\nfast but might have a high cost. Beam search limits the size of the frontier by only\nstoring the k nodes with the best f scores. Incomplete and suboptimal, but saves\nspace and is fast. Could also do iterative deepening A* with cutoff of f as the\nsmallest f of any node that exceeded the cutoff on the previous iteration.\nRecursive best first search is DFS with f_limit keeping track of best f value of\nalternative path from any ancestor of current node. If current node exceeds it,\nrewind to it. Replace f value of each node by backed-up value. Optimal if\nheuristic function is admissible. Space is linear in depth of deepest optimal solution.\nTime is difficult to ascertain. MA* (memory bounded A*) and SMA* (simplified MA*).\nExpands until memoryis full. Drop worst leaf node (highest f) and back up its value\nto its parent. Expands newest best leaf and deletes oldest worst leaf. Complete\nif possible to store in memory, and optimal if reachable. Otherwise, returns best\nreachable solution. Bidirectional heuristic search can't be optimally efficient.\nNot necessarily better than A*.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n If A* generates N nodes and solution depth is d, b* (effective\nbranching factor) is the branching factor that a uniform tree of depth d would\nhave in order to contain N+1 nodes. N+1=1+b*+(b*)^2 +...+(b*)^d. Well designed\nheuristic has b* close to 1. If h2(n)>=h1(n) for two admissible heuristics, h2\ndominates h1. A* will never expand more nodes using h2 than using h1. Can generate\nheuristic functions by relaxing constraints on the original problem. State space\ngraph is a supergraph of the original problem (same nodes with more edges). If\nthere are multiple admissible heuristics, can also use h(n)=max[h1(n),...,hk(n)].\nh(n) is admissible and consistent if all hi(n) are and dominate them all.\nChoosing at random can be inconsistent, but is faster. Could also get heuristic\nfrom solution cost of subproblem. Could also choose landmark points from the\nvertices and compute cost between landmarks to and from all other vertices.\nThen create an efficient but inadmissible heuristic as minimum over all\nlandmarks of cost from current node to landmark then to goal. Admissible\nheuristic would be max_{L \\in Landmarks} | C*(n, L) - C* (goal, L)|\n(differential heuristic). Could pick landmarks at random or try to space them out.\nIf you have data, pick ones that are common. Metalevel state space is the space\nof states representing the internal state of a program that is searching\nin the object-level state space. Could also train a model to estimate heuristics\nusing features in the state space. Not necessarily admissible or consistent.\n\n\n## Module 4 Lecture Notes\nN/A\n\n## Module 4 Definitions\n* **Heuristic function** - h(n) = estimated cost of cheapest path from node n to a goal state\n* **Admissible heuristic** - heuristic that never overestimates cost from n to goal (optimistic)\n* **Consistent heuristic** - if for every node n and successor n' generated by a, h(n) <= c(n,a,n') + h(n')\n* **Surely expanded nodes** - nodes in A* that can be reached from initial state on path where every node has f(n) < C*\n* **Pruning** - eliminating possibilities from consideration without examining them\n* **Satisficing solution** - solutions that are suboptimal but 'good enough'\n* **Detour index** - multiplier applied to straight line distance to account for curvature of roads\n* **Bounded suboptimal search** - looks for a solution guaranteed to be within constant factor W of optimal cost\n* **Bounded cost search** - looks for a solution whose cost is less than constant C\n* **Unbounded cost search** - accept solution at any cost, as long as we find it quickly\n* **Reference count** - how many ways a state has been reached already\n* **Backed-up value** - best f value of a node's children\n* **Relaxed problem** - problem with some constraints removed (used to generate heuristic\n* **Pattern database** - store exact solutions costs for every possible subproblem\n* **Disjoint pattern databases** - sum of costs of subproblems (if no overlap in solution actions)\n* **Precomputation** - doing some optimal path costs beforehand so don't need to calculate in real time\n* **Shortcuts** - artificial edges in graph that define an optimal multiaction path\n* **Differential heuristic** - heuristic function composed of difference of two others\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 = \"\"\" Could consider group of agents as s collective (economy), as part\n",
        "of the environment which makes it nondeterministic, or adversarially. Want to study\n",
        "perfect information (fully observable) zero-sum games. Define a game by initial state,\n",
        "which player is To Move, set of actions, transition model, a terminal test, and a\n",
        "utility function. Game trees are often too big to actualize and could be infinite.\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" For games with a binary outcome, can use AND-OR search. For games\n",
        "with multiple outcome score, need minimax. Minimax value of terminal state is its\n",
        "value. Otherwise, equals the maximum value of its children (if MAX's turn) or\n",
        "minimum value of its children (if MIN's turn). If opponent doesn't play optimally,\n",
        "there could be better moves than minimax decision, but doesn't guarantee best\n",
        "outcome. Using minimax against suboptimal player will do at least as well as\n",
        "against optimal player. Time for minimax search is O(b^m) and space is O(bm) (if\n",
        "generates all actions at once) or O(m) (if generates actions one at a time). For\n",
        "minimax with multiple players, each node has a vector of values (one for each\n",
        "player). Backed up value of node is utility vector of successor state with\n",
        "highest value for player choosing at node. Alpha-beta search updates values as\n",
        "it goes along and prunes remaining branches at node as soon as value of current\n",
        "node is known to be worse than the current alpha or beta value for MAX or MIN\n",
        "respectively. Depends on order of states encountered. If done perfectly, time\n",
        "of O(b^(m/2)). With random ordering, roughly O(b^(3m/4)). Could try iterative\n",
        "deepening.\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" Heuristic minimax cuts off search before reaching terminal nodes\n",
        "using evaluation and cutoff functions. For terminal states, EVAL(s, p)=UTILITY(s, p)\n",
        "and in general UTILITY(loss, p) <= EVAL(s, p) <= UTILITY(win, p) for state s\n",
        "and player p. Could define equivalence classes for states that have the same\n",
        "features, which should have same evaluation. Can evaluate features separately\n",
        "and combine them. Forward pruning prunes moves that seem poor but might be good.\n",
        "Beam search is forward pruning (could eliminate best move, but much faster).\n",
        "ProbCut is forward pruning that uses prior experience to cut nodes that are\n",
        "probably outside the current (alpha, beta) window. Retrograde minimax search starts\n",
        "with winning positions and moves in reverse to all scenarios that must result\n",
        "in those wins. Then generate lookup table.\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic games must include chance nodes as well as MIN and MAX.\n",
        "Expectiminimax generalized minimax for games with chance nodes. For chance nodes,\n",
        "compute extected value of children. Evaluation function myst return values that\n",
        "are apositive linear transformation of probability of winning (or expected utility).\n",
        "Time of O(b^m n^m) where n is number of chance nodes. Can use alpha-beta pruning\n",
        "by trying to bound upper and lower values of chance nodes.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" If an agents acts to maximize utility function that correctly\n",
        "reflects performace measure, it will receive highest possible performace\n",
        "score (averaged over all possible environments).\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"A>B means agent prefers A to B. A~B means agent is indifferent.\n",
        "Could have lottery of possible outcomes S1,...,Sn with probabilities p1...pn\n",
        "to give L=[p1, S1;...pn, Sn]. Each outcome S1 can be atomic state or another\n",
        "lottery. Axioms of utility theory are orderability, transitivity, continuity,\n",
        "substitutability, monotonicity, and decomposability. If agent violates them,\n",
        "it is irrational. If agents preferences obey axioms of utility, exists function\n",
        "Usuch that U(A)>U(B) iff A is preferred to B and U(A)=U(B) iff indifferent.\n",
        "Can calculate expected value of lottery. Agent's behavior doesn't change\n",
        "if change utility function to U'(S)=aU(s)+b for a>0. For deterministic\n",
        "environments, only preference matters, not actual values.\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"Need scale for utilities. Often normalize to between 0 and 1.\n",
        "Can assess utility by asking agent to choose between S and lottery of\n",
        "[p, u_best; (1-p), u_worst]. Resulting p is utility when indifferent. Utility\n",
        "of money is usually logarithmic-concave for positive wealth. Looks kind of\n",
        "logistic/tanh for full range (S shaped). U(L) < U(S_EMV(L)) because of concavity\n",
        "where EMV is expected monetary value. People are risk averse for positive wealth\n",
        "but become risk seeking at large negative wealth. For small  changes relative to\n",
        "current wealth, changes are approximately linear. Estimates of utility function\n",
        "are often overly optimistic. Can use Bayes' rule to avoid optimizer's curse.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "\\tADVERSARIAL_SEARCH/MINIMAX(game, state) returns value:\\n\n",
        "\\t\\t if state is terminal, return state's utility\\n\n",
        "\\t\\t initialize v=-inf (for MAX) or v=inf (for min)\\n\n",
        "\\t\\t for each successor of state:\\n\n",
        "    \\t\\t\\t v = max(v, min_value(successor)) (for MAX) or v = min(v, max_value(successor)) (for MIN)\\n\n",
        "\\t\\t return v\\n\\n\\n\n",
        "\\t ALPHA_BETA_SEARCH(game, state) returns an action:\\n\n",
        "\\t\\t player <- game.TO_MOVE(state)\\n\n",
        "\\t\\t value, move <- MAX_VALUE(game, state, -inf, inf)\\n\n",
        "\\t\\t return move\\n\\n\n",
        "\\t MAX_VALUE(game, state, alpha, beta) returns (utility, move):\\n\n",
        "\\t\\t if game.IS_TERMINAL(state) then return (game.UTILITY(state, player), null)\\n\n",
        "\\t\\t v <- -inf\\n\n",
        "\\t\\t for each a in game.ACTIONS(state) do:\\n\n",
        "\\t\\t\\t (v2, a2) <- MIN_VALUE(ganme, game.RESULT(state,a), alpha, beta)\\n\n",
        "\\t\\t\\t if v2 > v:\\n\n",
        "\\t\\t\\t\\t v, move <- v2, a\\n\n",
        "\\t\\t\\t\\t alpha <- MAX(alpha, v)\\n\n",
        "\\t\\t\\t if v >= beta then return (v, move)\\n\n",
        "\\t\\t return (v, move)\\n\\n\n",
        "\\t MIN_VALUE(game, state, alpha, beta) returns (utility, move):\\n\n",
        "\\t\\t if game.IS_TERMINAL(state) then return (game.UTILITY(state, player), null)\\n\n",
        "\\t\\t v <- +inf\\n\n",
        "\\t\\t for each a in game.ACTIONS(state) do:\\n\n",
        "\\t\\t\\t (v2, a2) <- MAX_VALUE(ganme, game.RESULT(state,a), alpha, beta)\\n\n",
        "\\t\\t\\t if v2 < v:\\n\n",
        "\\t\\t\\t\\t v, move <- v2, a\\n\n",
        "\\t\\t\\t\\t beta <- MIN(beta, v)\\n\n",
        "\\t\\t\\t if v <= alpha then return (v, move)\\n\n",
        "\\t\\t return (v, move)\\n\\n\n",
        "\n",
        "\n",
        "alpha=current lower bound on MAX's score-can't get below that. beta=current\n",
        "upper bound on MIN's score-can't get higher than that. MAX will never allow move\n",
        "lower than alpha and MIN will never allow move higher than beta. Expectimax returns\n",
        "state with MAX's choice if choice node and expected value of children if chance\n",
        "node. Heuristic is consistent if it obeys triangle inequality.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"competitive environments\" : \"two or more agents have conflicting goals\",\n",
        "\"evaluation function\": \"heuristic to estimate who is winning from current state\",\n",
        "\"game tree\": \"search tree that follows every sequence of moves to a terminal state\",\n",
        "\"ply\": \"one move by one player, one level deeper in the search tree\",\n",
        "\"minimax value\": \"utility for MAX of being in that state assuming both players play optimally\",\n",
        "\"minimax decision\": \"decision made by player after running minimax-optimal choice for that player\",\n",
        "\"minimax search\": \"DFS using minimax on each node to assign each state a value\",\n",
        "\"m\": \"maximum depth of game tree\",\n",
        "\"b\": \"number of legal moves at each point\",\n",
        "\"alpha\": \"value of best choice found so far at any choice point along path for MAX (at least)\",\n",
        "\"beta\": \"value of best choice found so far at any choice point along path for MIN (at most)\",\n",
        "\"killer moves\": \"best moves, want to find them first with killer move heuristic\",\n",
        "\"transpositions\": \"different permutations of move sequences that end in same position\",\n",
        "\"transposition table\": \"catches heuristic values of states if encountered before\",\n",
        "\"Type A strategy\": \"consider all possible moves to certain depth then use heuristic to estimate utility-wide but shallow\",\n",
        "\"Type B strategy\": \"ignore moves that look bad and follow promising lines as far as possible, deep but narrow\",\n",
        "\"evaluation function\": \"heuristic to treat nonterminal nodes as terminal-replace UTILITY with EVAL\",\n",
        "\"cutoff test\": \"replaces terminal test for when to stop looking-must return true for terminal states\",\n",
        "\"quiescent\": \"states that don't have a pending move that wildly swings evaluation\",\n",
        "\"horizon effect\": \"opponent's damaging move is unavoidable but can be delayed past search depth\",\n",
        "\"singular extensions\": \"moves that are clearly better even when search would be cut off\",\n",
        "\"late move reduction\": \"assumes move ordering has been done well, searches deeper for earlier moves\",\n",
        "\"table lookup\": \"use lookup for common scenarios instead of searching\",\n",
        "\"policy\": \"mapping from every possible state to best move\",\n",
        "\"maximum expected utility\": \"rational agent should choose action that maximizes expected utility\",\n",
        "\"orderability\": \"given two lotteries, rational agent should prefer one or be indifferent\",\n",
        "\"transitivity\": \"A>B and B>C implies A>C\",\n",
        "\"continuity\": \"If A>B>C, there is some probability p so agent is indifferent between B and [p, A; 1-p, C]\",\n",
        "\"substitutability\": \"if indifferent between lotteries A and B, [p, A; 1-p, C]~[p, B; 1-p, C] (also truw with >)\",\n",
        "\"monotonicity\": \"A>B implies that agent prefers lottery with higher probability of A\",\n",
        "\"decomposability\": \"compound lotteries can be reduced to simpler ones using laws of probability\",\n",
        "\"value function/ordinal utility function\": \"ranking of states, used for deterministic environments\",\n",
        "\"preference elicitation\": \"trying to find a human's utility function by presenting choices\",\n",
        "\"micromort\": \"1 in a million chance of dying, used for value people place on own lives\",\n",
        "\"QALY\": \"quality-adjusted life year, used for medical decisions\",\n",
        "\"monotonic preference\": \"more is better (like money)\",\n",
        "\"certainty equivalent\": \"value an agent will accept instead of lottery\",\n",
        "\"insurance premium\": \"difference between EMV of lottery and certainty equivalent\",\n",
        "\"risk-neutral\": \"linear curve for utility of asset\",\n",
        "\"unbiased\": \"E(U_hat(a) - EU(a)) = 0\",\n",
        "\"order statistic\": \"distribution of any particular ranked element of sample\",\n",
        "\"optimizer's curse\": \"tendency of estimated expected utility of best choice to be too high\",\n",
        "\"normative theory\": \"describes how rational agent should act\",\n",
        "\"descriptive theory\": \"describes how agents actually act\",\n",
        "\"certainty effect\": \"people are attracted togains that are certain\",\n",
        "\"framing effect\": \"people choose differently when options are presented as gains or losses\",\n",
        "\"anchoring effect\": \"presenting options just to skew perception of other options\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6a5a8318-856c-4749-d8ee-b3662ea3a6af"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Could consider group of agents as s collective (economy), as part\nof the environment which makes it nondeterministic, or adversarially. Want to study\nperfect information (fully observable) zero-sum games. Define a game by initial state,\nwhich player is To Move, set of actions, transition model, a terminal test, and a\nutility function. Game trees are often too big to actualize and could be infinite.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n For games with a binary outcome, can use AND-OR search. For games\nwith multiple outcome score, need minimax. Minimax value of terminal state is its\nvalue. Otherwise, equals the maximum value of its children (if MAX's turn) or\nminimum value of its children (if MIN's turn). If opponent doesn't play optimally,\nthere could be better moves than minimax decision, but doesn't guarantee best\noutcome. Using minimax against suboptimal player will do at least as well as\nagainst optimal player. Time for minimax search is O(b^m) and space is O(bm) (if\ngenerates all actions at once) or O(m) (if generates actions one at a time). For\nminimax with multiple players, each node has a vector of values (one for each\nplayer). Backed up value of node is utility vector of successor state with\nhighest value for player choosing at node. Alpha-beta search updates values as\nit goes along and prunes remaining branches at node as soon as value of current\nnode is known to be worse than the current alpha or beta value for MAX or MIN\nrespectively. Depends on order of states encountered. If done perfectly, time\nof O(b^(m/2)). With random ordering, roughly O(b^(3m/4)). Could try iterative\ndeepening.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic minimax cuts off search before reaching terminal nodes\nusing evaluation and cutoff functions. For terminal states, EVAL(s, p)=UTILITY(s, p)\nand in general UTILITY(loss, p) <= EVAL(s, p) <= UTILITY(win, p) for state s\nand player p. Could define equivalence classes for states that have the same\nfeatures, which should have same evaluation. Can evaluate features separately\nand combine them. Forward pruning prunes moves that seem poor but might be good.\nBeam search is forward pruning (could eliminate best move, but much faster).\nProbCut is forward pruning that uses prior experience to cut nodes that are\nprobably outside the current (alpha, beta) window. Retrograde minimax search starts\nwith winning positions and moves in reverse to all scenarios that must result\nin those wins. Then generate lookup table.\n\n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games must include chance nodes as well as MIN and MAX.\nExpectiminimax generalized minimax for games with chance nodes. For chance nodes,\ncompute extected value of children. Evaluation function myst return values that\nare apositive linear transformation of probability of winning (or expected utility).\nTime of O(b^m n^m) where n is number of chance nodes. Can use alpha-beta pruning\nby trying to bound upper and lower values of chance nodes.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n If an agents acts to maximize utility function that correctly\nreflects performace measure, it will receive highest possible performace\nscore (averaged over all possible environments).\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nA>B means agent prefers A to B. A~B means agent is indifferent.\nCould have lottery of possible outcomes S1,...,Sn with probabilities p1...pn\nto give L=[p1, S1;...pn, Sn]. Each outcome S1 can be atomic state or another\nlottery. Axioms of utility theory are orderability, transitivity, continuity,\nsubstitutability, monotonicity, and decomposability. If agent violates them,\nit is irrational. If agents preferences obey axioms of utility, exists function\nUsuch that U(A)>U(B) iff A is preferred to B and U(A)=U(B) iff indifferent.\nCan calculate expected value of lottery. Agent's behavior doesn't change\nif change utility function to U'(S)=aU(s)+b for a>0. For deterministic\nenvironments, only preference matters, not actual values.\n\n\n## AIMA Chapter 16.3 Utility Functions\nNeed scale for utilities. Often normalize to between 0 and 1.\nCan assess utility by asking agent to choose between S and lottery of\n[p, u_best; (1-p), u_worst]. Resulting p is utility when indifferent. Utility\nof money is usually logarithmic-concave for positive wealth. Looks kind of\nlogistic/tanh for full range (S shaped). U(L) < U(S_EMV(L)) because of concavity\nwhere EMV is expected monetary value. People are risk averse for positive wealth\nbut become risk seeking at large negative wealth. For small  changes relative to\ncurrent wealth, changes are approximately linear. Estimates of utility function\nare often overly optimistic. Can use Bayes' rule to avoid optimizer's curse.\n\n\n## Module 5 Lecture Notes\n\n\tADVERSARIAL_SEARCH/MINIMAX(game, state) returns value:\n\n\t\t if state is terminal, return state's utility\n\n\t\t initialize v=-inf (for MAX) or v=inf (for min)\n\n\t\t for each successor of state:\n\n    \t\t\t v = max(v, min_value(successor)) (for MAX) or v = min(v, max_value(successor)) (for MIN)\n\n\t\t return v\n\n\n\n\t ALPHA_BETA_SEARCH(game, state) returns an action:\n\n\t\t player <- game.TO_MOVE(state)\n\n\t\t value, move <- MAX_VALUE(game, state, -inf, inf)\n\n\t\t return move\n\n\n\t MAX_VALUE(game, state, alpha, beta) returns (utility, move):\n\n\t\t if game.IS_TERMINAL(state) then return (game.UTILITY(state, player), null)\n\n\t\t v <- -inf\n\n\t\t for each a in game.ACTIONS(state) do:\n\n\t\t\t (v2, a2) <- MIN_VALUE(ganme, game.RESULT(state,a), alpha, beta)\n\n\t\t\t if v2 > v:\n\n\t\t\t\t v, move <- v2, a\n\n\t\t\t\t alpha <- MAX(alpha, v)\n\n\t\t\t if v >= beta then return (v, move)\n\n\t\t return (v, move)\n\n\n\t MIN_VALUE(game, state, alpha, beta) returns (utility, move):\n\n\t\t if game.IS_TERMINAL(state) then return (game.UTILITY(state, player), null)\n\n\t\t v <- +inf\n\n\t\t for each a in game.ACTIONS(state) do:\n\n\t\t\t (v2, a2) <- MAX_VALUE(ganme, game.RESULT(state,a), alpha, beta)\n\n\t\t\t if v2 < v:\n\n\t\t\t\t v, move <- v2, a\n\n\t\t\t\t beta <- MIN(beta, v)\n\n\t\t\t if v <= alpha then return (v, move)\n\n\t\t return (v, move)\n\n\n\n\nalpha=current lower bound on MAX's score-can't get below that. beta=current\nupper bound on MIN's score-can't get higher than that. MAX will never allow move\nlower than alpha and MIN will never allow move higher than beta. Expectimax returns\nstate with MAX's choice if choice node and expected value of children if chance\nnode. Heuristic is consistent if it obeys triangle inequality.\n\n\n## Module 5 Definitions\n* **Competitive environments** - two or more agents have conflicting goals\n* **Evaluation function** - heuristic to treat nonterminal nodes as terminal-replace UTILITY with EVAL\n* **Game tree** - search tree that follows every sequence of moves to a terminal state\n* **Ply** - one move by one player, one level deeper in the search tree\n* **Minimax value** - utility for MAX of being in that state assuming both players play optimally\n* **Minimax decision** - decision made by player after running minimax-optimal choice for that player\n* **Minimax search** - DFS using minimax on each node to assign each state a value\n* **M** - maximum depth of game tree\n* **B** - number of legal moves at each point\n* **Alpha** - value of best choice found so far at any choice point along path for MAX (at least)\n* **Beta** - value of best choice found so far at any choice point along path for MIN (at most)\n* **Killer moves** - best moves, want to find them first with killer move heuristic\n* **Transpositions** - different permutations of move sequences that end in same position\n* **Transposition table** - catches heuristic values of states if encountered before\n* **Type a strategy** - consider all possible moves to certain depth then use heuristic to estimate utility-wide but shallow\n* **Type b strategy** - ignore moves that look bad and follow promising lines as far as possible, deep but narrow\n* **Cutoff test** - replaces terminal test for when to stop looking-must return true for terminal states\n* **Quiescent** - states that don't have a pending move that wildly swings evaluation\n* **Horizon effect** - opponent's damaging move is unavoidable but can be delayed past search depth\n* **Singular extensions** - moves that are clearly better even when search would be cut off\n* **Late move reduction** - assumes move ordering has been done well, searches deeper for earlier moves\n* **Table lookup** - use lookup for common scenarios instead of searching\n* **Policy** - mapping from every possible state to best move\n* **Maximum expected utility** - rational agent should choose action that maximizes expected utility\n* **Orderability** - given two lotteries, rational agent should prefer one or be indifferent\n* **Transitivity** - A>B and B>C implies A>C\n* **Continuity** - If A>B>C, there is some probability p so agent is indifferent between B and [p, A; 1-p, C]\n* **Substitutability** - if indifferent between lotteries A and B, [p, A; 1-p, C]~[p, B; 1-p, C] (also truw with >)\n* **Monotonicity** - A>B implies that agent prefers lottery with higher probability of A\n* **Decomposability** - compound lotteries can be reduced to simpler ones using laws of probability\n* **Value function/ordinal utility function** - ranking of states, used for deterministic environments\n* **Preference elicitation** - trying to find a human's utility function by presenting choices\n* **Micromort** - 1 in a million chance of dying, used for value people place on own lives\n* **Qaly** - quality-adjusted life year, used for medical decisions\n* **Monotonic preference** - more is better (like money)\n* **Certainty equivalent** - value an agent will accept instead of lottery\n* **Insurance premium** - difference between EMV of lottery and certainty equivalent\n* **Risk-neutral** - linear curve for utility of asset\n* **Unbiased** - E(U_hat(a) - EU(a)) = 0\n* **Order statistic** - distribution of any particular ranked element of sample\n* **Optimizer's curse** - tendency of estimated expected utility of best choice to be too high\n* **Normative theory** - describes how rational agent should act\n* **Descriptive theory** - describes how agents actually act\n* **Certainty effect** - people are attracted togains that are certain\n* **Framing effect** - people choose differently when options are presented as gains or losses\n* **Anchoring effect** - presenting options just to skew perception of other options\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"In CSPs, don't  treat states as atomic/black boxes but can see\n",
        "inside. CSP has X (set of variables), D (set of domains for each variable), and\n",
        "C (set of constraints that specify allowable combinations of values). Each constraint\n",
        "is a tuple that contains a pair of points and a relation that defines the values\n",
        "they can take on (explicit set or function). Solving CSP is NP-complete, but there\n",
        "are subclasses that can be solves efficiently. Don't need to search until solution\n",
        "is found-can reject some assignments as soon as they violate constraint, reducing\n",
        "search space. Simplest CSPs have discrete finite domains. Solutions exist for\n",
        "linear constraint problems on integer variables. Could transform any CSP into one\n",
        "with only binary constraints by using auxiliary variables. Could also use dual graph:\n",
        "graph where there is one variable for each constraint and binary constraints for\n",
        "constraints that share variables. Easier, however, to use global constraints.\n",
        "Could model preference constraints as costs on individual variable assignments.\n",
        "Then can solve CSPs with optimization to make it a constrained optimization\n",
        "problem.\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"Constraint propogation can be done with search or as preprocessing.\n",
        "AC-3 enforces arc consistency. Maintain queue of arcs (initially all), with binary\n",
        "constraints as two arcs, one in each direction. Pop off arc (Xi, Xj) and make Xi\n",
        "arc-consistent with Xj. If you change domain of Xi, add all (Xk, Xi) arcs to\n",
        "queue where Xk are all neighbors in constraint graph. If domain is empty, failure.\n",
        "Checking single arc is time of O(d^2) and AC-3 is time of O(c d^3). {Xi, Xj} is\n",
        "path consistent with Xm if for every assignment {Xi=a, Xj=b} consistent with their\n",
        "constraints, there is an assignment to Xm that satisfies constraints on {Xi, Xm}\n",
        "and {Xm, Xj}. For strongly n-consistent, can start by choosing consistent value\n",
        "for X1, then for X2, etc. Time of O(n^2 d). Establishing n-consistentcy is\n",
        "time and space exponential in n.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"Constraint satisfaction doesn't always solve CSP (some variables\n",
        "have multiple possible values remaining). Then need to do search. Depth-limited\n",
        "search takes time and space of O(n! d^n) even though there are only d^n assignments.\n",
        "With commutativity, number of leaves is d^n. Backtracking chooses an unassigned\n",
        "variable, tries a possible value, and the propogates it. If solution is found,\n",
        "report, if not, try next value and continue. If no value works, failure. Forward\n",
        "checking is whenever a variable X is assigned, establish arc-consistency for it.\n",
        "Maintaining Arc Consistency (MAC) assigns a value to Xi the calls AC-3 but starts\n",
        "with a queue of arcs (Xj, Xi) for Xj neighbors of Xi. Like recursively calling\n",
        "forward checking. Backjumping backtracks to most recent assignment in conflict set.\n",
        "With forward checking, when X=x gets rid of a value in Y, add X=x to Y's conflict\n",
        "set. Simple backjumping is unneeded when using forward checking or any stronger\n",
        "consistency checking like MAC. Conflict-directed backjumping is backjumping\n",
        "that uses conflict sets defined  by set of previous variables that caused\n",
        "conflict together with any subsequent variables. Can keep track of no-good assignments\n",
        "and know never use that combination if ever encountered again.\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"Local search changes variable values one at a time by improving values\n",
        "of a variable each step. Can start with complete assignment that isn't consistent and switch\n",
        "conflicted variables using min-conflict heuristic to a better assignment. Works well\n",
        "for problems whose solutions are densely distributed througout state space. Plateau\n",
        "search allows movement from state to another state with same number of conflicts.\n",
        "For constranit weighting, each constraint is given weight, initially 1. At each step,\n",
        "choose variable value pair resulting in lowest weight of violated constraints. Then\n",
        "increment each weight whose constraint is violated. Local search can also be used\n",
        "online when problem changes.\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"Independent subproblems can be found by looking at connected components\n",
        "of constraint graph. Total work is O(d^c n / c) where c is number of variables in\n",
        "each subproblem (n/c subproblems). Without decomposition, is O(d^n). Any tree\n",
        "structures constraint graph can be solved in linear (in n) time. To solve tree\n",
        "structured CSP, pick any variable to be root and do topological sort. Can make\n",
        "graph consistent in O(n) steps so time is O(n d^2). Can then just choose any\n",
        "remaining value for all variables. Cutset conditioning assigns values to variables\n",
        "to remaining variables form tree. Need to try each value. Form cycle cutset and for\n",
        "each possible assignment to variables in S that satisfy their constraints, remove\n",
        "values from remaining variables that are inconsistent and if solution exists,\n",
        "return it. If cycle cutset has size c, time is O(d^c (n-c) d^2). Could also use\n",
        "tree decomposition which is tree where each node has a set of variables. Every\n",
        "variable in original problem appears in at least one tree node, if two variables\n",
        "are connected by a constraint in problem, must appear together with constraint\n",
        "in at least one node, if variable appears in two nodes, must appear in every\n",
        "node along path connecting those nodes. Then can apply tree-CSP-solver to\n",
        "get solution in O(n d^2) time. Domain is tuples of values, not individual values.\n",
        "Each graph has several tree decompositions, so try to make subproblems as small\n",
        "as possible. If graph has tree width w, time of O(n d^(w+1)) given tree decomposition.\n",
        "If have cycle-cutset size c, there is a tree width of size w<c+1. Tree\n",
        "decomposition has faster time but cycle-cutset is linear memory and tree\n",
        "decomposition's memory is exponential in w.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"In CSPs, only use problem definition, not heuristic\n",
        "functions (could use them, but usually want general algorithms). Waltz algorithm\n",
        "for checking direction of lines in 2D objects is CSP. For planar constraint graphs,\n",
        "number of arcs is O(n).\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constraint satisfaction problem\" : \"problem where solution is an assignment of values to variables that satisfy constraints\",\n",
        "\"consistent/legal assignment\": \"assignment that does not violate any constraints\",\n",
        "\"complete assignment\": \"assignment where every variable is assigned a value\",\n",
        "\"partial assignment\": \"assignment where some variables are unassigned\",\n",
        "\"partial solution\": \"partial assignment that is consistent\",\n",
        "\"constraint graph\": \"nodes are variables, edge connects variables that have a constraint\",\n",
        "\"precedence constraint\": \"constraint on which variable must come first chronologically\",\n",
        "\"disjunctive constraint\": \"constraint of the form x or y must be true\",\n",
        "\"linear programming\": \"constraints must be linear equalities or inequalities-solved in polynomial time\",\n",
        "\"unary constraint\": \"restricts value of single variable\",\n",
        "\"binary constraint\": \"relates two variables\",\n",
        "\"global constraint\": \"constraint involving arbitrary number of variables\",\n",
        "\"cryptarithmetic puzzle\": \"eachletter represents different digit\",\n",
        "\"constraint hypergraph\": \"contains nodes and hypernodes (which represent n-ary constraints involving n variables)\",\n",
        "\"preference constraints\": \"say which solutions are prefferred\",\n",
        "\"constraint propogation\": \"using constraints to reduce number of legal values for a variable\",\n",
        "\"local consistency\": \"treat each variable as node and binary constraint as edge to eliminate inconsistent assignments\",\n",
        "\"node consistent\": \"if all values in variable's domain satisfy unary constraints\",\n",
        "\"arc consistent\": \"every value of variable satisfies binary constraints\",\n",
        "\"n\": \"number of variables in CSP\",\n",
        "\"c\": \"number of binary constraints\",\n",
        "\"d\": \"maximum domain size\",\n",
        "\"path consistency\": \"implicit constraints inferred by looking at triplets of variables\",\n",
        "\"k-consistency\": \"for any set of k-1 variables and consistent assignment of their values, exists a consistent assignment for kth variable\",\n",
        "\"strongly k-consistent\": \"k-consistent, (k-1)-consistent...1-consistent\",\n",
        "\"resource constraint\": \"at-most constraint on variables\",\n",
        "\"bounds propogation\": \"for constraints between variables, could reduce bounds of domains for each one\",\n",
        "\"bounds-consistent\": \"for every variable X and both lower-bound and upper-bound of X, exists value of Y that satisfies X-Y constraint\",\n",
        "\"commutativity\": \"order of application of any given set of actions doesn't matter\",\n",
        "\"minimum remaining values\": \"heuristic for choosing unassigned variable-choose most constrained\",\n",
        "\"degree heuristic\": \"heuristic for choosing unassigned variable-choose variable that imposes the most constraints\",\n",
        "\"least constraining value\": \"heuristic for choosing value-pick value that rules out the fewest choices for neighbors\",\n",
        "\"chronological backtracking\": \"when an assignment fails, backtrack to most recent assigned variable\",\n",
        "\"conflict set\": \"set of assignments that are in conflict with some variable assignment\",\n",
        "\"constraint learning\": \"finding a minimum set of variables from the conflict set that causes the problem\",\n",
        "\"no-good\": \"set found by constraint learning along with their values\",\n",
        "\"min-conflicts heuristic\": \"select value that results in the minimum number of conflicts\",\n",
        "\"tabu search\": \"keep list of recently visited states and don't go back to them\",\n",
        "\"independent subproblems\": \"solution to those problems can be combined in any way for global solution\",\n",
        "\"directional arc consistency\": \"DAC under ordering of X1,...Xn iff every Xi is arc consistent with Xj for j>i\",\n",
        "\"topological sort\": \"ordering of variables so each variable is after parent\",\n",
        "\"cycle cutset\": \"subset S of CSP's variables such that constraint graph becomes tree after S is removed\",\n",
        "\"cutset conditioning\": \"finding cutset and solving CSP after trying its values on graph\",\n",
        "\"tree width\": \"one less than the size of the largest node in tree decomposition graph\",\n",
        "\"value symmetry\": \"can permute values of solution to get d! solutions\",\n",
        "\"symmetry-breaking constraint\": \"impose arbitrary ordering to reduce value symmetry to one solution\"\n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "99d47789-5736-47e6-9e47-418f533840a6"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nIn CSPs, don't  treat states as atomic/black boxes but can see\ninside. CSP has X (set of variables), D (set of domains for each variable), and\nC (set of constraints that specify allowable combinations of values). Each constraint\nis a tuple that contains a pair of points and a relation that defines the values\nthey can take on (explicit set or function). Solving CSP is NP-complete, but there\nare subclasses that can be solves efficiently. Don't need to search until solution\nis found-can reject some assignments as soon as they violate constraint, reducing\nsearch space. Simplest CSPs have discrete finite domains. Solutions exist for\nlinear constraint problems on integer variables. Could transform any CSP into one\nwith only binary constraints by using auxiliary variables. Could also use dual graph:\ngraph where there is one variable for each constraint and binary constraints for\nconstraints that share variables. Easier, however, to use global constraints.\nCould model preference constraints as costs on individual variable assignments.\nThen can solve CSPs with optimization to make it a constrained optimization\nproblem.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nConstraint propogation can be done with search or as preprocessing.\nAC-3 enforces arc consistency. Maintain queue of arcs (initially all), with binary\nconstraints as two arcs, one in each direction. Pop off arc (Xi, Xj) and make Xi\narc-consistent with Xj. If you change domain of Xi, add all (Xk, Xi) arcs to\nqueue where Xk are all neighbors in constraint graph. If domain is empty, failure.\nChecking single arc is time of O(d^2) and AC-3 is time of O(c d^3). {Xi, Xj} is\npath consistent with Xm if for every assignment {Xi=a, Xj=b} consistent with their\nconstraints, there is an assignment to Xm that satisfies constraints on {Xi, Xm}\nand {Xm, Xj}. For strongly n-consistent, can start by choosing consistent value\nfor X1, then for X2, etc. Time of O(n^2 d). Establishing n-consistentcy is\ntime and space exponential in n.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nConstraint satisfaction doesn't always solve CSP (some variables\nhave multiple possible values remaining). Then need to do search. Depth-limited\nsearch takes time and space of O(n! d^n) even though there are only d^n assignments.\nWith commutativity, number of leaves is d^n. Backtracking chooses an unassigned\nvariable, tries a possible value, and the propogates it. If solution is found,\nreport, if not, try next value and continue. If no value works, failure. Forward\nchecking is whenever a variable X is assigned, establish arc-consistency for it.\nMaintaining Arc Consistency (MAC) assigns a value to Xi the calls AC-3 but starts\nwith a queue of arcs (Xj, Xi) for Xj neighbors of Xi. Like recursively calling\nforward checking. Backjumping backtracks to most recent assignment in conflict set.\nWith forward checking, when X=x gets rid of a value in Y, add X=x to Y's conflict\nset. Simple backjumping is unneeded when using forward checking or any stronger\nconsistency checking like MAC. Conflict-directed backjumping is backjumping\nthat uses conflict sets defined  by set of previous variables that caused\nconflict together with any subsequent variables. Can keep track of no-good assignments\nand know never use that combination if ever encountered again.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\nLocal search changes variable values one at a time by improving values\nof a variable each step. Can start with complete assignment that isn't consistent and switch\nconflicted variables using min-conflict heuristic to a better assignment. Works well\nfor problems whose solutions are densely distributed througout state space. Plateau\nsearch allows movement from state to another state with same number of conflicts.\nFor constranit weighting, each constraint is given weight, initially 1. At each step,\nchoose variable value pair resulting in lowest weight of violated constraints. Then\nincrement each weight whose constraint is violated. Local search can also be used\nonline when problem changes.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\nIndependent subproblems can be found by looking at connected components\nof constraint graph. Total work is O(d^c n / c) where c is number of variables in\neach subproblem (n/c subproblems). Without decomposition, is O(d^n). Any tree\nstructures constraint graph can be solved in linear (in n) time. To solve tree\nstructured CSP, pick any variable to be root and do topological sort. Can make\ngraph consistent in O(n) steps so time is O(n d^2). Can then just choose any\nremaining value for all variables. Cutset conditioning assigns values to variables\nto remaining variables form tree. Need to try each value. Form cycle cutset and for\neach possible assignment to variables in S that satisfy their constraints, remove\nvalues from remaining variables that are inconsistent and if solution exists,\nreturn it. If cycle cutset has size c, time is O(d^c (n-c) d^2). Could also use\ntree decomposition which is tree where each node has a set of variables. Every\nvariable in original problem appears in at least one tree node, if two variables\nare connected by a constraint in problem, must appear together with constraint\nin at least one node, if variable appears in two nodes, must appear in every\nnode along path connecting those nodes. Then can apply tree-CSP-solver to\nget solution in O(n d^2) time. Domain is tuples of values, not individual values.\nEach graph has several tree decompositions, so try to make subproblems as small\nas possible. If graph has tree width w, time of O(n d^(w+1)) given tree decomposition.\nIf have cycle-cutset size c, there is a tree width of size w<c+1. Tree\ndecomposition has faster time but cycle-cutset is linear memory and tree\ndecomposition's memory is exponential in w.\n\n\n## Module 6 Lecture Notes\nIn CSPs, only use problem definition, not heuristic\nfunctions (could use them, but usually want general algorithms). Waltz algorithm\nfor checking direction of lines in 2D objects is CSP. For planar constraint graphs,\nnumber of arcs is O(n).\n\n## Module 6 Definitions\n* **Constraint satisfaction problem** - problem where solution is an assignment of values to variables that satisfy constraints\n* **Consistent/legal assignment** - assignment that does not violate any constraints\n* **Complete assignment** - assignment where every variable is assigned a value\n* **Partial assignment** - assignment where some variables are unassigned\n* **Partial solution** - partial assignment that is consistent\n* **Constraint graph** - nodes are variables, edge connects variables that have a constraint\n* **Precedence constraint** - constraint on which variable must come first chronologically\n* **Disjunctive constraint** - constraint of the form x or y must be true\n* **Linear programming** - constraints must be linear equalities or inequalities-solved in polynomial time\n* **Unary constraint** - restricts value of single variable\n* **Binary constraint** - relates two variables\n* **Global constraint** - constraint involving arbitrary number of variables\n* **Cryptarithmetic puzzle** - eachletter represents different digit\n* **Constraint hypergraph** - contains nodes and hypernodes (which represent n-ary constraints involving n variables)\n* **Preference constraints** - say which solutions are prefferred\n* **Constraint propogation** - using constraints to reduce number of legal values for a variable\n* **Local consistency** - treat each variable as node and binary constraint as edge to eliminate inconsistent assignments\n* **Node consistent** - if all values in variable's domain satisfy unary constraints\n* **Arc consistent** - every value of variable satisfies binary constraints\n* **N** - number of variables in CSP\n* **C** - number of binary constraints\n* **D** - maximum domain size\n* **Path consistency** - implicit constraints inferred by looking at triplets of variables\n* **K-consistency** - for any set of k-1 variables and consistent assignment of their values, exists a consistent assignment for kth variable\n* **Strongly k-consistent** - k-consistent, (k-1)-consistent...1-consistent\n* **Resource constraint** - at-most constraint on variables\n* **Bounds propogation** - for constraints between variables, could reduce bounds of domains for each one\n* **Bounds-consistent** - for every variable X and both lower-bound and upper-bound of X, exists value of Y that satisfies X-Y constraint\n* **Commutativity** - order of application of any given set of actions doesn't matter\n* **Minimum remaining values** - heuristic for choosing unassigned variable-choose most constrained\n* **Degree heuristic** - heuristic for choosing unassigned variable-choose variable that imposes the most constraints\n* **Least constraining value** - heuristic for choosing value-pick value that rules out the fewest choices for neighbors\n* **Chronological backtracking** - when an assignment fails, backtrack to most recent assigned variable\n* **Conflict set** - set of assignments that are in conflict with some variable assignment\n* **Constraint learning** - finding a minimum set of variables from the conflict set that causes the problem\n* **No-good** - set found by constraint learning along with their values\n* **Min-conflicts heuristic** - select value that results in the minimum number of conflicts\n* **Tabu search** - keep list of recently visited states and don't go back to them\n* **Independent subproblems** - solution to those problems can be combined in any way for global solution\n* **Directional arc consistency** - DAC under ordering of X1,...Xn iff every Xi is arc consistent with Xj for j>i\n* **Topological sort** - ordering of variables so each variable is after parent\n* **Cycle cutset** - subset S of CSP's variables such that constraint graph becomes tree after S is removed\n* **Cutset conditioning** - finding cutset and solving CSP after trying its values on graph\n* **Tree width** - one less than the size of the largest node in tree decomposition graph\n* **Value symmetry** - can permute values of solution to get d! solutions\n* **Symmetry-breaking constraint** - impose arbitrary ordering to reduce value symmetry to one solution\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 = \"\"\"Have TELL and ASK functions for knowledge base. When asked a question,\n",
        "answer should follow from what has previously been told to knowledge base. Shouldn't\n",
        "make things up. Agent program TELLs knowledge base what it perceives, ASKS knowledge\n",
        "base what action to do, then TELLs the knowledge base chosen action and returns\n",
        "action.\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"Task environment has Performance Measure, Environment, Actuators,\n",
        "and Sensors (PEAS). If available information is correct and conclusion is drawn\n",
        "from that information, conclusion is correct.\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"Every sentence must be either true or false in each possible\n",
        "world, no in between. If a sentence alpha is true in model m, m satisfies\n",
        "alpha or m is a model of alpha. M(alpha) is set of all models of alpha.\n",
        "alpha |= beta iff in every model in which alpha is true, beta is also true.\n",
        "(a |= b iff M(a) subseteq M(b)). Knowledge base is set of sdentences that asserts\n",
        "all individual sentences. False if it contradicts what agent knows. Logical\n",
        "inferrence is using entailment to derive conclusions. Model checking\n",
        "enumerates all possible models to check that sentence alpha is true in all\n",
        "models in which knowledge base KB is true (M(KB) subseteq M(alpha)). If an\n",
        "inferrence algorithm i can derive alpha from the knowledge base KB, KB |-i alpha.\n",
        "Model checking is a sound procedure, but only works if space of models is finite.\n",
        "\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"Model sets truth value for every propositional symbol. Truth\n",
        "value of every propositional symbol (except True and False) must be specified\n",
        "in model. Can use truth tables for complex sentences given  truth values of\n",
        "components. Checking all models might take a long time. If KB and alpha have n\n",
        "symbols, there are 2^n models, so time is O(2^n). Space is O(n) because it is\n",
        "depth first. Every known inference algorithm has worst case exponential in size\n",
        "ofinput (co-NP-complete).\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"a and b are logically equivalent iff a|=b and b|=a. a is valid\n",
        "iff -a is unsatisfiable, a is satisfiable iff -a is not valid. a|=b iff sentence\n",
        "(a ^ -b) is unsatisfiable. Can use proof by contradiction fo prove b from a by\n",
        "checking unsatisfiability of (a ^ -b). Not all inference rules work in both directions\n",
        "but some do. To apply search to problems of inference, need initial state (knowledge\n",
        "base), actions (inference rules), result (add sentence in bottom half of inference\n",
        "rule), and goal (state that contains sentence we are trying to prove). Alternative\n",
        "to enumerating models. Can also use resolution. Unit resolution takes a clause and\n",
        "a literal to produce new clause. Can apply resolution rule when li and mj are\n",
        "complementary literals. Takes two clauses and produces new clause containing\n",
        "all literals except complementary literals. Can only resolve one pair of complementary\n",
        "literals at a time. Resulting clause should only contain one copy of each literal\n",
        "e.g. (AvB)^(Av-B) obtains (AvA) which is A. Every sentence of propositional\n",
        "logic is equivalent to conjunction of clauses (conjunctive normal form).\n",
        "Replace (a <=> b) with (a => b)^(b => a). Replace (a => b) with (-a v b). Move\n",
        "(-) inward by DeMorgan's laws. Distribute v over ^ wherever possible. Results\n",
        "in (Clause_1 ^...^ Clause_n) where each clause is (Literal_1 v...v Literal_m).\n",
        "Can then show that KB|=a by showing (KB^-a) is unsatisfiable (prove a contradiction).\n",
        "Convert (KB^-a) into CNF, then apply resolution rule to resulting clauses. Either\n",
        "there are no new clauses that can be added (KB does not entail a) of two clauses\n",
        "resolve to yield the empty clause (KB entails a). Resolution closure RC(S) is set of\n",
        "all clauses derivable by repeated application of resolution rule to clauses in S\n",
        "or their derivatives. PL-Resolution is complete. If you resolve two horn clauses,\n",
        "get back a horn clause. Definite clause can be written as implication whose premise\n",
        "is conjunction of positive literals and whose conclusion is a single positive literal.\n",
        "Inference with horn clauses can be done with forward-chaining or backward-chaining.\n",
        "Entailment with horn clauses if linear in size of KB. PL-FC-Entails determines\n",
        "if a proposition symbol q (query) is entailed by KB of definite clauses. If all\n",
        "premises of implication are knwon, conclusion is added to set of known facts.\n",
        "Continues until finding q or no further inferences. Linear time. Sound and complete.\n",
        "In backward chaining, algorithm finds implications whose conclusion is q. If premises\n",
        "can be proven (by backward chaining) q is true.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"Could have knowledge base in form of knowledge\n",
        "representation language e.g. planet(x), sun(y), or far_from(x, y)=>cold(x)\\n\n",
        "\\t PL_RESOLUTION(KB, a) returns true or false:\\n\n",
        "\\t\\t clauses <- set of clauses in the CNF representation of KB ^-a\\n\n",
        "\\t\\t new <- {}\\n\n",
        "\\t\\t while true do:\\n\n",
        "\\t\\t\\t for each pair of clauses Ci Cj in clauses do:\\n\n",
        "\\t\\t\\t\\t resolvents <- PL_RESOLVE(Ci,Cj)\\n\n",
        "\\t\\t\\t\\t if resolvents contains empty clause, return true\\n\n",
        "\\t\\t\\t\\t new <- new U resolvents\\n\n",
        "\\t\\t\\t if new subseteq clauses then return false\\n\n",
        "\\t\\t\\t clauses <- clauses U new\\n\\n\n",
        "\n",
        "\\t PL_FC_ENTAILS(KB, q) returns true or false:\\n\n",
        "\\t\\t count <- table where count[c] is initially number of symbols in clause c's premise\\n\n",
        "\\t\\t inferred <- table where inferred[c] is initially false for all symbols\\n\n",
        "\\t\\t queue <- queue of symbols, initially symbols known to be true in KB\\n\n",
        "\\t\\t while queue is not empty do:\\n\n",
        "\\t\\t\\t p <- POP(queue)\\n\n",
        "\\t\\t\\t if p==q then return true\\n\n",
        "\\t\\t\\t if inferred[p] == false:\\n\n",
        "\\t\\t\\t\\t inferred[p] <- true\\n\n",
        "\\t\\t\\t\\t for each clause c in KB where p is in c.PREMISE do:\\n\n",
        "\\t\\t\\t\\t\\t decrement count[c]\\n\n",
        "\\t\\t\\t\\t\\t if count[c] == 0 then add c.CONCLUSION to queue\\n\n",
        "\\t\\t return false\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agent\" : \"use process of reasoning over internal representation to decideon actions\",\n",
        "\"knowledge base\": \"set of sentences\",\n",
        "\"knowledge representation language\": \"each sentence represents some assertion about the world\",\n",
        "\"axiom\": \"sentence taken as given\",\n",
        "\"inference\": \"deriving new sentences from  old ones\",\n",
        "\"declarative approach\": \"TELL agent sentences one by one until agent knows how to operate\",\n",
        "\"procedural approach\": \"encodes desired behavior directly as code\",\n",
        "\"syntax\": \"specifies all the sentences that are well formed\",\n",
        "\"semantics\": \"meaning of sentences\",\n",
        "\"possible world\": \"potentially real environments that agent might or might not be in\",\n",
        "\"model\": \"mathematical abstraction, each of which has a fixed truth value\",\n",
        "\"entailment\": \"sentences follow logically from another sentence- alpha |= beta\",\n",
        "\"sound/truth-preserving\": \"inference algoruthm that derives only entailed sentences\",\n",
        "\"complete\": \"if an inferrrence algorithm can derive any sentence that is entailed\",\n",
        "\"grounding\": \"connection between logical reasoning processes and real environment\",\n",
        "\"atomic sentences\": \"consist of a single propositional symbol\",\n",
        "\"propositional symbol\": \"stands for a proposition that can either be true or false\",\n",
        "\"complex sentences\": \"constructed from simpler sentences using parentheses and logical connectives\",\n",
        "\"positive literal\": \"atomic sentence\",\n",
        "\"negative literal\": \"negated atomic sentence\",\n",
        "\"negation\": \"-P: -P is true iff P is false in m\",\n",
        "\"conjunction\": \"and (^): P^Q is true iff both P and Q are true in m\",\n",
        "\"disjunction\": \"or (v): PvQ is true iff P or Q is true in m\",\n",
        "\"implication\": \"premise/antecedent => conclusion/consequent: P=>Q is true unless P is true and Q is false in m\",\n",
        "\"biconditional\": \"iff (<=>): P<=>Q is true iff P and Q are both true or both false in m\",\n",
        "\"theorem proving\": \"applying rules of inference to sentences in knowledge base\",\n",
        "\"logical equivalence\": \"alpha and beta are logically equivalent if they are true in the same set of models\",\n",
        "\"contraposition\": \"(a => b) == (-b => -a)\",\n",
        "\"implication elimination\": \"(a => b) == (-a v b)\",\n",
        "\"biconditional elimination\": \"(a <=> b) == ((a => b) ^ (b => a))\",\n",
        "\"DeMorgan1\": \"-(a ^ b) == (-a v -b)\",\n",
        "\"DeMorgan2\": \"-(a v b) == (-a ^ -b)\",\n",
        "\"distributivity of ^ over v\": \"((a ^ (b v c)) == ((a ^ b) v (a ^ c))\",\n",
        "\"distributivity of v over ^\": \"(a v (b ^ c)) == ((a v b) ^ (a v c))\",\n",
        "\"validity\": \"sentence is valid if true in all models (tautology) e.g. (P v -P)\",\n",
        "\"deduction theorem\": \"for any sentences a and b, (a|=b) iff the sentence (a=>b) is valid\",\n",
        "\"satisfiability\": \"if a sentence is true in (satisfied by) some model\",\n",
        "\"modus ponens\": \"{(a => b), a}/b : whenever any sentence a=>b and a are given, b canbe inferred\",\n",
        "\"and elimination\": \"(a^b)/b : from a conjunction, any of the conjuncts can be inferred\",\n",
        "\"monotonicity\": \"set of entailed sentences can only increase as information is added to KB\",\n",
        "\"unit resolution inference rule\": \"{(l1 v ... v lk) m}/{l1 v ... v li-1 v li+1 v... lk} where li is -m\",\n",
        "\"complementary literals\": \"one is the negation of the other\",\n",
        "\"clause\": \"disjunction of literals\",\n",
        "\"unit clause\": \"single literal (disjunction of one literal)\",\n",
        "\"resolution rule\": \"{(l1 v...v lk) (m1 v...v mn)}/{l1 v...v li-1 v li+1 v...v lk v m1 v...v mj-1 v...v mn}\",\n",
        "\"factoring\": \"removal of multiple copies of literals\",\n",
        "\"ground resolution theorem\": \"if set of clauses S is unsatisfiable, RC(S) contains the empty clause\",\n",
        "\"definite clause\": \"disjunction of literals of which exactly one is positive (not negated)\",\n",
        "\"horn clause\": \"disjunction of literals of which at most one is positive (not negated)\",\n",
        "\"goal clause\": \"disjunction of literals, none of which are positive (not negated)\",\n",
        "\"k-CNF sentence\": \"CNF sentence where each clause has at most k literals\",\n",
        "\"body/head\": \"for horn clause, premise=body and conclusion=head\",\n",
        "\"fact\": \"sentence containing single positive literal\",\n",
        "\"data-driven reasoning\": \"reasoning in which focus of attention starts with known data\",\n",
        "\"goal directed reasoning\": \"look for goal by only dealing with relevant facts (like backward chaining)\"\n",
        "}"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "33df802c-8736-4b11-e51c-08cbce944493"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nHave TELL and ASK functions for knowledge base. When asked a question,\nanswer should follow from what has previously been told to knowledge base. Shouldn't\nmake things up. Agent program TELLs knowledge base what it perceives, ASKS knowledge\nbase what action to do, then TELLs the knowledge base chosen action and returns\naction.\n\n\n## AIMA Chapter 7.2 The Wumpus World\nTask environment has Performance Measure, Environment, Actuators,\nand Sensors (PEAS). If available information is correct and conclusion is drawn\nfrom that information, conclusion is correct.\n\n\n## AIMA Chapter 7.3 Logic\nEvery sentence must be either true or false in each possible\nworld, no in between. If a sentence alpha is true in model m, m satisfies\nalpha or m is a model of alpha. M(alpha) is set of all models of alpha.\nalpha |= beta iff in every model in which alpha is true, beta is also true.\n(a |= b iff M(a) subseteq M(b)). Knowledge base is set of sdentences that asserts\nall individual sentences. False if it contradicts what agent knows. Logical\ninferrence is using entailment to derive conclusions. Model checking\nenumerates all possible models to check that sentence alpha is true in all\nmodels in which knowledge base KB is true (M(KB) subseteq M(alpha)). If an\ninferrence algorithm i can derive alpha from the knowledge base KB, KB |-i alpha.\nModel checking is a sound procedure, but only works if space of models is finite.\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nModel sets truth value for every propositional symbol. Truth\nvalue of every propositional symbol (except True and False) must be specified\nin model. Can use truth tables for complex sentences given  truth values of\ncomponents. Checking all models might take a long time. If KB and alpha have n\nsymbols, there are 2^n models, so time is O(2^n). Space is O(n) because it is\ndepth first. Every known inference algorithm has worst case exponential in size\nofinput (co-NP-complete).\n\n\n## AIMA 7.5 Propositional Theorem Proving\na and b are logically equivalent iff a|=b and b|=a. a is valid\niff -a is unsatisfiable, a is satisfiable iff -a is not valid. a|=b iff sentence\n(a ^ -b) is unsatisfiable. Can use proof by contradiction fo prove b from a by\nchecking unsatisfiability of (a ^ -b). Not all inference rules work in both directions\nbut some do. To apply search to problems of inference, need initial state (knowledge\nbase), actions (inference rules), result (add sentence in bottom half of inference\nrule), and goal (state that contains sentence we are trying to prove). Alternative\nto enumerating models. Can also use resolution. Unit resolution takes a clause and\na literal to produce new clause. Can apply resolution rule when li and mj are\ncomplementary literals. Takes two clauses and produces new clause containing\nall literals except complementary literals. Can only resolve one pair of complementary\nliterals at a time. Resulting clause should only contain one copy of each literal\ne.g. (AvB)^(Av-B) obtains (AvA) which is A. Every sentence of propositional\nlogic is equivalent to conjunction of clauses (conjunctive normal form).\nReplace (a <=> b) with (a => b)^(b => a). Replace (a => b) with (-a v b). Move\n(-) inward by DeMorgan's laws. Distribute v over ^ wherever possible. Results\nin (Clause_1 ^...^ Clause_n) where each clause is (Literal_1 v...v Literal_m).\nCan then show that KB|=a by showing (KB^-a) is unsatisfiable (prove a contradiction).\nConvert (KB^-a) into CNF, then apply resolution rule to resulting clauses. Either\nthere are no new clauses that can be added (KB does not entail a) of two clauses\nresolve to yield the empty clause (KB entails a). Resolution closure RC(S) is set of\nall clauses derivable by repeated application of resolution rule to clauses in S\nor their derivatives. PL-Resolution is complete. If you resolve two horn clauses,\nget back a horn clause. Definite clause can be written as implication whose premise\nis conjunction of positive literals and whose conclusion is a single positive literal.\nInference with horn clauses can be done with forward-chaining or backward-chaining.\nEntailment with horn clauses if linear in size of KB. PL-FC-Entails determines\nif a proposition symbol q (query) is entailed by KB of definite clauses. If all\npremises of implication are knwon, conclusion is added to set of known facts.\nContinues until finding q or no further inferences. Linear time. Sound and complete.\nIn backward chaining, algorithm finds implications whose conclusion is q. If premises\ncan be proven (by backward chaining) q is true.\n\n\n## Module 7 Lecture Notes\nCould have knowledge base in form of knowledge\nrepresentation language e.g. planet(x), sun(y), or far_from(x, y)=>cold(x)\n\n\t PL_RESOLUTION(KB, a) returns true or false:\n\n\t\t clauses <- set of clauses in the CNF representation of KB ^-a\n\n\t\t new <- {}\n\n\t\t while true do:\n\n\t\t\t for each pair of clauses Ci Cj in clauses do:\n\n\t\t\t\t resolvents <- PL_RESOLVE(Ci,Cj)\n\n\t\t\t\t if resolvents contains empty clause, return true\n\n\t\t\t\t new <- new U resolvents\n\n\t\t\t if new subseteq clauses then return false\n\n\t\t\t clauses <- clauses U new\n\n\n\n\t PL_FC_ENTAILS(KB, q) returns true or false:\n\n\t\t count <- table where count[c] is initially number of symbols in clause c's premise\n\n\t\t inferred <- table where inferred[c] is initially false for all symbols\n\n\t\t queue <- queue of symbols, initially symbols known to be true in KB\n\n\t\t while queue is not empty do:\n\n\t\t\t p <- POP(queue)\n\n\t\t\t if p==q then return true\n\n\t\t\t if inferred[p] == false:\n\n\t\t\t\t inferred[p] <- true\n\n\t\t\t\t for each clause c in KB where p is in c.PREMISE do:\n\n\t\t\t\t\t decrement count[c]\n\n\t\t\t\t\t if count[c] == 0 then add c.CONCLUSION to queue\n\n\t\t return false\n\n\n## Module 7 Definitions\n* **Knowledge-based agent** - use process of reasoning over internal representation to decideon actions\n* **Knowledge base** - set of sentences\n* **Knowledge representation language** - each sentence represents some assertion about the world\n* **Axiom** - sentence taken as given\n* **Inference** - deriving new sentences from  old ones\n* **Declarative approach** - TELL agent sentences one by one until agent knows how to operate\n* **Procedural approach** - encodes desired behavior directly as code\n* **Syntax** - specifies all the sentences that are well formed\n* **Semantics** - meaning of sentences\n* **Possible world** - potentially real environments that agent might or might not be in\n* **Model** - mathematical abstraction, each of which has a fixed truth value\n* **Entailment** - sentences follow logically from another sentence- alpha |= beta\n* **Sound/truth-preserving** - inference algoruthm that derives only entailed sentences\n* **Complete** - if an inferrrence algorithm can derive any sentence that is entailed\n* **Grounding** - connection between logical reasoning processes and real environment\n* **Atomic sentences** - consist of a single propositional symbol\n* **Propositional symbol** - stands for a proposition that can either be true or false\n* **Complex sentences** - constructed from simpler sentences using parentheses and logical connectives\n* **Positive literal** - atomic sentence\n* **Negative literal** - negated atomic sentence\n* **Negation** - -P: -P is true iff P is false in m\n* **Conjunction** - and (^): P^Q is true iff both P and Q are true in m\n* **Disjunction** - or (v): PvQ is true iff P or Q is true in m\n* **Implication** - premise/antecedent => conclusion/consequent: P=>Q is true unless P is true and Q is false in m\n* **Biconditional** - iff (<=>): P<=>Q is true iff P and Q are both true or both false in m\n* **Theorem proving** - applying rules of inference to sentences in knowledge base\n* **Logical equivalence** - alpha and beta are logically equivalent if they are true in the same set of models\n* **Contraposition** - (a => b) == (-b => -a)\n* **Implication elimination** - (a => b) == (-a v b)\n* **Biconditional elimination** - (a <=> b) == ((a => b) ^ (b => a))\n* **Demorgan1** - -(a ^ b) == (-a v -b)\n* **Demorgan2** - -(a v b) == (-a ^ -b)\n* **Distributivity of ^ over v** - ((a ^ (b v c)) == ((a ^ b) v (a ^ c))\n* **Distributivity of v over ^** - (a v (b ^ c)) == ((a v b) ^ (a v c))\n* **Validity** - sentence is valid if true in all models (tautology) e.g. (P v -P)\n* **Deduction theorem** - for any sentences a and b, (a|=b) iff the sentence (a=>b) is valid\n* **Satisfiability** - if a sentence is true in (satisfied by) some model\n* **Modus ponens** - {(a => b), a}/b : whenever any sentence a=>b and a are given, b canbe inferred\n* **And elimination** - (a^b)/b : from a conjunction, any of the conjuncts can be inferred\n* **Monotonicity** - set of entailed sentences can only increase as information is added to KB\n* **Unit resolution inference rule** - {(l1 v ... v lk) m}/{l1 v ... v li-1 v li+1 v... lk} where li is -m\n* **Complementary literals** - one is the negation of the other\n* **Clause** - disjunction of literals\n* **Unit clause** - single literal (disjunction of one literal)\n* **Resolution rule** - {(l1 v...v lk) (m1 v...v mn)}/{l1 v...v li-1 v li+1 v...v lk v m1 v...v mj-1 v...v mn}\n* **Factoring** - removal of multiple copies of literals\n* **Ground resolution theorem** - if set of clauses S is unsatisfiable, RC(S) contains the empty clause\n* **Definite clause** - disjunction of literals of which exactly one is positive (not negated)\n* **Horn clause** - disjunction of literals of which at most one is positive (not negated)\n* **Goal clause** - disjunction of literals, none of which are positive (not negated)\n* **K-cnf sentence** - CNF sentence where each clause has at most k literals\n* **Body/head** - for horn clause, premise=body and conclusion=head\n* **Fact** - sentence containing single positive literal\n* **Data-driven reasoning** - reasoning in which focus of attention starts with known data\n* **Goal directed reasoning** - look for goal by only dealing with relevant facts (like backward chaining)\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": "05b36342-d9e5-4bdf-937d-62371a4f42dd"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Intelligence is either human performance or 'rationality': doing the right thing.\nIntelligence can be categorized as thought process or behavior. Turing test: human interrogator\nasks written questions and tries tofigure out if the responses came from a computer. We want\nmachines to pursue our objectives, not their own.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n John Searle distinguished between weak and strong AI. Hubert Dreyfus thought\nthat human  behavior was toocomplex to be embodies by a logical agent and that cognition takes\nplace inside a body. We need to study the system as a whole. Godel's incompleteness\ntheorem saysthat a formal axiomatic framework can't prove itself comletely.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Is a machine that acts intelligently actually thinking or only be\na simulation of thinking? Semantic distinction, so doesn't matter so much. John Searle\nproposed the Chinese Room experiment about a human who doesn't speak Chinese and yet is\nable to repond in fluent Chinese to questions by following a guidebook and matching.\nThis would pass the Turing test without any understanding being involved. He believed\nin biological naturalism which says that it is neurons that matter for thinking\n\n## AIMA 2.1 Agents and Environments\n An agent's choice of action can depend on its built in knowledge\nand its percept sequence up to the present. Agents should have significant\ncomputational resources and task environment requires nontrivial decision making.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Humans need todesign performance metric. Some agent designs\nhave an explicit representation of the performancemeasure, others don't. They\nmight notknow why they are doing the right thing. Should design a performance\nmeasure according to what we want done, not how we think it should behave.\nRationality depends on a performance measure, priorknowledge, actions available,\nand percept sequence. Rationality maximized expected performance, perfection/\nomniscience maximizes actual performance.\n\n\n## AIMA 2.3 The Nature of Environments\n Task environments are the problems to which rational agents are\nthe solutions. Need to  specify PEAS (Performance, Environment, Actuators, Sensors).\nfor each agent. Fully observable/partially observable environment is whether the\nagent's sensors giveit access to the complete state of the environment.\nSingle/multiagent problems is whether ornot there is another agent (being\nmaximizing its own performance metric). Deterministic vs nondeterministic is\nwhether the next state of the environment is completely determined by the current\nstate and the action from an agent. (Stochastic if it explicitly deals in\nprobabilities, nondeterministic if not quantified.) Episodic/sequential is\nif the agent's experience is divided into atomic episodes, where next episode\ndoesn't depend on previous one. Static/dynamic is if an environment can change\nwhile an agent is deliberating. (Semidynamic is if environment doesn't change\nbut performance score does.) Discrete/continuous state, time, percepts and actions.\nKnown/unknown describes the  agent's knowledge about the laws ofphysics of\nthe environment and the consequences of actions.\n\n\n## AIMA 2.4 The Structure of Agents\nAgent = architecture + program. Agent program takes current\npercept asinput and agent function could depend on entire percepthistory. Would\nneed to have agent remember percepts. Can't implement table with all possible percept\nsequences, because there are too many. Simple reflex agents don't perform well\nin partially observable environments. Model-based reflex agents have an internal\nstate which depends on the percept history. Has a transition model and sensor\nmodel. Goals only have a binary distinction of reaching it or not, whereas\nutility can compare different states by assigning them scores. A learning agent\nhas a learning element (takes feedback from critic) and performace element\nwhich is modified by learning element. Also has critic and problem generator.\nProblem generator suggests actions that will lead to new and informative\nexperiences (exploration). Distributed representation is more robust to noise\nthan localist representation.\n\n\n## Module 1 Lecture Notes\nRene Descartes: Cogito ergo sum. Mechanical Turk-\n'robot' that plays chess, but really a person. Descartes thought that automoton\ncouldn't use language. Eliza-early NLP program imitating Rogerian psychotherapy.\nDaniel Dennet-brain in a vat-don't need biological brain to think.\n\n## Module 1 Definitions\n* **Ai disciplines** - NLP, Knowledge representation, Automated reasoning, ML, Total Turing  test, CV,  Robotics\n* **Total turing test** - Turing test+perceiving and acting in the world\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - agent that acts to achieve the best (expected) outcome\n* **Value alignment problem** - values in machine must be aligned with human values\n* **Weak ai** - act as if it is intelligent\n* **Strong ai** - machine that can solve a wide variety of tasks like a human, even novel ones\n* **Good old-fashioned ai (gofai)** - simple logical  agent design (can't capture complex behavior in all scenarios)\n* **Qualia** - intrinsic nature of experience\n* **Percept** - content an agent's sensors are perceiving\n* **Agent function** - map from any given percept sequence to an action\n* **Agent program** - implementation of an agent function on a physical system\n* **Consequentialism** - evaluate an agent's behavior by its consequences\n* **Performance measure** - evaluate any given sequence of environment states\n* **Omniscience** - agent knows the actual outcome of its actions and can act accordingly\n* **Information gathering** - doing actions in order to modify future percepts\n* **Exploration** - creating a map of an initially unknown environment\n* **Autonomous** - learn what it can do to compensate for partial orincorrect prior knowledge\n* **Agent architecture** - computing device with sensors and actuators\n* **Simple reflex agent** - select actions only based on current percept\n* **Condition-action rule** - if/then statement about which action to take\n* **Model-based reflex agents** - keeps track of the part of the world it can't see now\n* **Transition model** - knowledge about how the world works\n* **Sensor model** - how the world affects the sensors\n* **Goal-based agent** - takes actions because it has a goal\n* **Utility function** - internalization of performace measure\n* **Utility-based agent** - agent with a utility function rather than just a goal\n* **Atomic representation** - each state is indivisible with no internal structure\n* **Factored representation** - splits up each state into fixed set of variables or attributes (each with value)\n* **Structured representation** - world has thigs related to each other, not just variables with values\n* **Localist representation** - one-to-one mapping between concepts and memory locations\n* **Distributed representation** - representation of concept is spread over memory locations, each location stores several concepts\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\nMemoization is used ofr dynamic programming and recursion.\nRemember previous calls so don't have to recurse every time. Functions are treated\nas objects-can be passed into functions as arguments. Magic methods-double\nunderscore before and after function name so can use overloaded operators. E.g.\ninit,  str, len, cmp, add, neg, copy. For executing code, insert (if name == main:)\n(both double underscored). Iterators can be used in loop because they\nhave iter magic method. Need to have a next magic method, but no function whether\nit has next-catches StopIteration exception (memory efficient). Generators are\nlike iterators but don't need to initialize iterator. Use yield instead of return.\nWill pause code to return value and continue running code when called again.\nLists, dicts, sets are mutable. Tuples and strings are immutable. Labels are\nalways changeable, even if thing it points to is immutable.\n\n\n\t print([(first, second) for first in range(3) for second in range(3)])\n\n\t [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]\n\n\n## Module 2 Definitions\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem-solving agents use atomic representations. If they\nuse factored or structured, called planning agents. Agent does Goal formulation,\n(what is its goal- limit objectives and actions), Problem formulation\n(description of states and actions necessary to reach goal), Search\n(simulation of action sequences until it finds goal), Execution. In a\nfully observable deterministic known environment, solution to any problem\nis a fixed sequence of actions. Agent can ignore percepts if model and\nsolution are correct. Search problem has state space, initial state,\nset of goal states, set of actions given a state, transition model,\naction cost function (relevent to performance measure). Can represent\nstate space by graph (vertices=states, directed edges=actions).\nIntelligent abstraction removes as much detail as possible while retaining\nvalidity and making sure that abstract actions can be carried out.\n\n\n## AIMA Chapter 3.2 Example Problems\nN/A\n\n## AIMA Chapter 3.3 Search Algorithms\n Can form a search tree over state-space graph and use it\nto search for goal states. Each node in the tree has a unique path back to the\ninitial state. Frontier is states/nodes that have been reached but not yet\nexpanded (divides interior from exterior). Best first search: choose node\non frontier with minimum evaluation function f(n). If it is a goal, return\nit and if not, expand it. Each child node is added to frontier (if already\non frontier, replace if new path has smaller cost). Each node contains\nState, Parent, Action (applied to get there), Path cost g(n). Use queue\nto store frontier nodes (have priority queue-best first search, FIFO-BFS,\nLIFO queue/stack-DFS).Reached states can be stores in a lookup table like\nhash table (key is state, value is node for state). If no cap on cycles or\nredundant paths, number of possible sequences explodes. Could remember\nall previously reached states and keep only best path or could not worry\nabout redundant paths. Best first search is a graph search. Could also check\nfor cycles but not redundant paths (follow chain of parents to see if\nnode at end of path has appeared earlier). Size of state-space graph =\n|V| + |E| (number of state nodes + number of state/action pairs).\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS: root node us expanded than all of its successors are\nexpanded, then all of their successors, etc. Complete even on infinite\nstate-spaces. Could be implemented as best first search with f(n)=depth of node.\nUse FIFO queue and add new nodes to back of queue. Reached can be set of states.\nCan do early goal test. Complete, and optimal when all actions have the same cost.\nTime and space complexity both are O(b^d). Dijkstra's algorithm/uniform-cost search\nworks when actions have different costs. Uses best first search where f(n) is\nthe cost of the path from root to current node. Time and space complexity of\nO(b^(1+floor(C*/e))) where C* is the cost of the optimal solution and e>0 is\na lower bound on the cost of each action (can be much larger than b^d unless\naction costs are equal, where it is then O(b^(d+1))). Complete and optimal.\nDFS expands the deepest node in the frontier. Could be implemented by best first\nsearch with f(n) the negative of the depth. Could also be implemented as a tree\nsearch (not graph search). Not optimal, and only complete for finite acyclic\nstate-spaces. Time of O(number of states) and memory of O(bm). Backtracking\nsearch is a variant of DFS that uses less memory. Only one successor is generated\nat a time and each node remembers which node to expand next. Successors are\ngenerated by modifying current state instead of allocating new memory. Space is\nO(m) and can check for cycles in O(1) instead of O(m). Depth limited search\nis DFS with a limit l which 'have no successors'. Time is O(b^l) and space is\nO(bl). Might be incomplete if l is to shallow. Iterative deepening search\nif depth limited search while increasing l with every call. Memory of O(bd) if\nthere is a solution and O(bm) if there isn't. Complete and optimal on finite spaces.\nNeed to check for cycles to be complete. Time is O(b^d) if there is a solution\nand O(b^m) if there isn't. Bidirectional search starts searching from initial\nstate and backward from goal state and try to meet. Have solution when the \ntwo frontiers collide. If evaluation is path cost, first solution found is\noptimal, otherwise need to check all solutions. Complete and optimal. Time\nand space O(b^(d/2)).\n\n\n## Module 3 Lecture Notes\nN/A\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Informed agent** - can estimate how far it is from goal\n* **Uninformed agent** - can't estimate how far from goal\n* **Solution** - sequence of actions that reaches the goal\n* **Open-loop** - doesn't take  percepts into account\n* **Closed-loop** - takes percepts into account\n* **State space** - set of possible states environment can be in\n* **Action cost funtion** - c(s, a, s') gives numeric cost when taking an action (additive)\n* **Path** - sequence of actions\n* **Optimal solution** - solution with lowest path cost\n* **Standardized problem** - illustrates or exercises problem solving methods\n* **Real-world problem** - problem whose solutions people actually use, idiosyncratic\n* **Egocentric actions** - defined with respect to the agent (forward/backward as opposed to which cell to move to)\n* **Search algorithm** - takes a search problem as input and returns solution or indication of failure\n* **Search tree** - search over graph of state space with initial state as root node\n* **Frontier** - separates two regions of state space graph: interior-states have been expanded; exterior, have not been reached\n* **Graph search** - checks for redundant paths\n* **Tree-like search** - doesn't check for redundant paths\n* **Completeness** - algorithm guaranteed to find solution when there is one and correctly report failure if there isn't\n* **Cost optimality** - finds solution with lowest path cost\n* **Time complexity** - how long until search finds a solution\n* **Space complexity** - how much memory is needed to perform search\n* **D** - depth of number of actions in an optimal solution\n* **M** - maximum number of actions in any path\n* **B** - branching factor-number of successors of a node to be considered\n* **Early goal test** - test if a state is a goal state as soon as it is generated\n* **Late goal test** - test if a state is a goal state when it is popped off the queue\n* **Abstract state** - equivalence class between real world states\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nGreedy best-first search expands node with lowest h(n) value.\nBest-first search with f(n)=h(n). Can find solution without ever expanding node\nthat isn't on solution  path. Complete in finite spaces, but not optimal. Time\nand space is O(|V|). With good heuristic, can sometimes be O(bm). A* uses\nf(n)=g(n)+h(n)=path cost so far + estimated future cost. Complete, and optimal\nif heuristic is admissible. Consistency is stronger than admissibility. With\nconsistent heuristic, first time we reach a state it will be on optimal path.\nWith inadmissible heuristic, can be optimal if there is a cost optimal path where\nh(n) is admissible for all n or if h(n) never overestimates costs by more than\nC2-C* (different in costs of best two solutions). Can draw contours of regions\nwhere all nodeshave f(n)=g(n)+h(n) <= constant. A* fans out adding nodes in\nbands of increasing f(n). With uniform cost, have circular contours of\ng(n) <= constant. With A*, contours stretch toward goal state and narrow \naround the optimal path. f=g+h will monotonically increase iff the heuristic\nis consistent. A* is optimally efficient because any other algorithm that expands\nfrom the initial state using the same heuristic must expand all nodes expanded\nby A*. Could try using inadmissible heuristic for A* if it is more accurate:\ndoesn't necessarily give optimal solution but expands fewer nodes. Weighted A*\nis where weweight heuristic more heavily: f(n) = g(n) + W*h(n) for W>1. Will\nfind solution that is between C* and (W)(C*) but usually closer to C*. Other\nalgorithms: A*: W=1, Uniform cost: W=0, Greedy best-first: W=inf,\nWeighted A*: 1<W<inf. Speedy search is version of greedy best-first that uses\nheuristic h(n)=estimated number of actions to reach goal (unbounded cost search\nalgorithm). If all actions have same cost, same as greedy best-first. Otherwise,\nfast but might have a high cost. Beam search limits the size of the frontier by only\nstoring the k nodes with the best f scores. Incomplete and suboptimal, but saves\nspace and is fast. Could also do iterative deepening A* with cutoff of f as the\nsmallest f of any node that exceeded the cutoff on the previous iteration.\nRecursive best first search is DFS with f_limit keeping track of best f value of\nalternative path from any ancestor of current node. If current node exceeds it,\nrewind to it. Replace f value of each node by backed-up value. Optimal if\nheuristic function is admissible. Space is linear in depth of deepest optimal solution.\nTime is difficult to ascertain. MA* (memory bounded A*) and SMA* (simplified MA*).\nExpands until memoryis full. Drop worst leaf node (highest f) and back up its value\nto its parent. Expands newest best leaf and deletes oldest worst leaf. Complete\nif possible to store in memory, and optimal if reachable. Otherwise, returns best\nreachable solution. Bidirectional heuristic search can't be optimally efficient.\nNot necessarily better than A*.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n If A* generates N nodes and solution depth is d, b* (effective\nbranching factor) is the branching factor that a uniform tree of depth d would\nhave in order to contain N+1 nodes. N+1=1+b*+(b*)^2 +...+(b*)^d. Well designed\nheuristic has b* close to 1. If h2(n)>=h1(n) for two admissible heuristics, h2\ndominates h1. A* will never expand more nodes using h2 than using h1. Can generate\nheuristic functions by relaxing constraints on the original problem. State space\ngraph is a supergraph of the original problem (same nodes with more edges). If\nthere are multiple admissible heuristics, can also use h(n)=max[h1(n),...,hk(n)].\nh(n) is admissible and consistent if all hi(n) are and dominate them all.\nChoosing at random can be inconsistent, but is faster. Could also get heuristic\nfrom solution cost of subproblem. Could also choose landmark points from the\nvertices and compute cost between landmarks to and from all other vertices.\nThen create an efficient but inadmissible heuristic as minimum over all\nlandmarks of cost from current node to landmark then to goal. Admissible\nheuristic would be max_{L \\in Landmarks} | C*(n, L) - C* (goal, L)|\n(differential heuristic). Could pick landmarks at random or try to space them out.\nIf you have data, pick ones that are common. Metalevel state space is the space\nof states representing the internal state of a program that is searching\nin the object-level state space. Could also train a model to estimate heuristics\nusing features in the state space. Not necessarily admissible or consistent.\n\n\n## Module 4 Lecture Notes\nN/A\n\n## Module 4 Definitions\n* **Heuristic function** - h(n) = estimated cost of cheapest path from node n to a goal state\n* **Admissible heuristic** - heuristic that never overestimates cost from n to goal (optimistic)\n* **Consistent heuristic** - if for every node n and successor n' generated by a, h(n) <= c(n,a,n') + h(n')\n* **Surely expanded nodes** - nodes in A* that can be reached from initial state on path where every node has f(n) < C*\n* **Pruning** - eliminating possibilities from consideration without examining them\n* **Satisficing solution** - solutions that are suboptimal but 'good enough'\n* **Detour index** - multiplier applied to straight line distance to account for curvature of roads\n* **Bounded suboptimal search** - looks for a solution guaranteed to be within constant factor W of optimal cost\n* **Bounded cost search** - looks for a solution whose cost is less than constant C\n* **Unbounded cost search** - accept solution at any cost, as long as we find it quickly\n* **Reference count** - how many ways a state has been reached already\n* **Backed-up value** - best f value of a node's children\n* **Relaxed problem** - problem with some constraints removed (used to generate heuristic\n* **Pattern database** - store exact solutions costs for every possible subproblem\n* **Disjoint pattern databases** - sum of costs of subproblems (if no overlap in solution actions)\n* **Precomputation** - doing some optimal path costs beforehand so don't need to calculate in real time\n* **Shortcuts** - artificial edges in graph that define an optimal multiaction path\n* **Differential heuristic** - heuristic function composed of difference of two others\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Could consider group of agents as s collective (economy), as part\nof the environment which makes it nondeterministic, or adversarially. Want to study\nperfect information (fully observable) zero-sum games. Define a game by initial state,\nwhich player is To Move, set of actions, transition model, a terminal test, and a\nutility function. Game trees are often too big to actualize and could be infinite.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n For games with a binary outcome, can use AND-OR search. For games\nwith multiple outcome score, need minimax. Minimax value of terminal state is its\nvalue. Otherwise, equals the maximum value of its children (if MAX's turn) or\nminimum value of its children (if MIN's turn). If opponent doesn't play optimally,\nthere could be better moves than minimax decision, but doesn't guarantee best\noutcome. Using minimax against suboptimal player will do at least as well as\nagainst optimal player. Time for minimax search is O(b^m) and space is O(bm) (if\ngenerates all actions at once) or O(m) (if generates actions one at a time). For\nminimax with multiple players, each node has a vector of values (one for each\nplayer). Backed up value of node is utility vector of successor state with\nhighest value for player choosing at node. Alpha-beta search updates values as\nit goes along and prunes remaining branches at node as soon as value of current\nnode is known to be worse than the current alpha or beta value for MAX or MIN\nrespectively. Depends on order of states encountered. If done perfectly, time\nof O(b^(m/2)). With random ordering, roughly O(b^(3m/4)). Could try iterative\ndeepening.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Heuristic minimax cuts off search before reaching terminal nodes\nusing evaluation and cutoff functions. For terminal states, EVAL(s, p)=UTILITY(s, p)\nand in general UTILITY(loss, p) <= EVAL(s, p) <= UTILITY(win, p) for state s\nand player p. Could define equivalence classes for states that have the same\nfeatures, which should have same evaluation. Can evaluate features separately\nand combine them. Forward pruning prunes moves that seem poor but might be good.\nBeam search is forward pruning (could eliminate best move, but much faster).\nProbCut is forward pruning that uses prior experience to cut nodes that are\nprobably outside the current (alpha, beta) window. Retrograde minimax search starts\nwith winning positions and moves in reverse to all scenarios that must result\nin those wins. Then generate lookup table.\n\n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games must include chance nodes as well as MIN and MAX.\nExpectiminimax generalized minimax for games with chance nodes. For chance nodes,\ncompute extected value of children. Evaluation function myst return values that\nare apositive linear transformation of probability of winning (or expected utility).\nTime of O(b^m n^m) where n is number of chance nodes. Can use alpha-beta pruning\nby trying to bound upper and lower values of chance nodes.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n If an agents acts to maximize utility function that correctly\nreflects performace measure, it will receive highest possible performace\nscore (averaged over all possible environments).\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nA>B means agent prefers A to B. A~B means agent is indifferent.\nCould have lottery of possible outcomes S1,...,Sn with probabilities p1...pn\nto give L=[p1, S1;...pn, Sn]. Each outcome S1 can be atomic state or another\nlottery. Axioms of utility theory are orderability, transitivity, continuity,\nsubstitutability, monotonicity, and decomposability. If agent violates them,\nit is irrational. If agents preferences obey axioms of utility, exists function\nUsuch that U(A)>U(B) iff A is preferred to B and U(A)=U(B) iff indifferent.\nCan calculate expected value of lottery. Agent's behavior doesn't change\nif change utility function to U'(S)=aU(s)+b for a>0. For deterministic\nenvironments, only preference matters, not actual values.\n\n\n## AIMA Chapter 16.3 Utility Functions\nNeed scale for utilities. Often normalize to between 0 and 1.\nCan assess utility by asking agent to choose between S and lottery of\n[p, u_best; (1-p), u_worst]. Resulting p is utility when indifferent. Utility\nof money is usually logarithmic-concave for positive wealth. Looks kind of\nlogistic/tanh for full range (S shaped). U(L) < U(S_EMV(L)) because of concavity\nwhere EMV is expected monetary value. People are risk averse for positive wealth\nbut become risk seeking at large negative wealth. For small  changes relative to\ncurrent wealth, changes are approximately linear. Estimates of utility function\nare often overly optimistic. Can use Bayes' rule to avoid optimizer's curse.\n\n\n## Module 5 Lecture Notes\n\n\tADVERSARIAL_SEARCH/MINIMAX(game, state) returns value:\n\n\t\t if state is terminal, return state's utility\n\n\t\t initialize v=-inf (for MAX) or v=inf (for min)\n\n\t\t for each successor of state:\n\n    \t\t\t v = max(v, min_value(successor)) (for MAX) or v = min(v, max_value(successor)) (for MIN)\n\n\t\t return v\n\n\n\n\t ALPHA_BETA_SEARCH(game, state) returns an action:\n\n\t\t player <- game.TO_MOVE(state)\n\n\t\t value, move <- MAX_VALUE(game, state, -inf, inf)\n\n\t\t return move\n\n\n\t MAX_VALUE(game, state, alpha, beta) returns (utility, move):\n\n\t\t if game.IS_TERMINAL(state) then return (game.UTILITY(state, player), null)\n\n\t\t v <- -inf\n\n\t\t for each a in game.ACTIONS(state) do:\n\n\t\t\t (v2, a2) <- MIN_VALUE(ganme, game.RESULT(state,a), alpha, beta)\n\n\t\t\t if v2 > v:\n\n\t\t\t\t v, move <- v2, a\n\n\t\t\t\t alpha <- MAX(alpha, v)\n\n\t\t\t if v >= beta then return (v, move)\n\n\t\t return (v, move)\n\n\n\t MIN_VALUE(game, state, alpha, beta) returns (utility, move):\n\n\t\t if game.IS_TERMINAL(state) then return (game.UTILITY(state, player), null)\n\n\t\t v <- +inf\n\n\t\t for each a in game.ACTIONS(state) do:\n\n\t\t\t (v2, a2) <- MAX_VALUE(ganme, game.RESULT(state,a), alpha, beta)\n\n\t\t\t if v2 < v:\n\n\t\t\t\t v, move <- v2, a\n\n\t\t\t\t beta <- MIN(beta, v)\n\n\t\t\t if v <= alpha then return (v, move)\n\n\t\t return (v, move)\n\n\n\n\nalpha=current lower bound on MAX's score-can't get below that. beta=current\nupper bound on MIN's score-can't get higher than that. MAX will never allow move\nlower than alpha and MIN will never allow move higher than beta. Expectimax returns\nstate with MAX's choice if choice node and expected value of children if chance\nnode. Heuristic is consistent if it obeys triangle inequality.\n\n\n## Module 5 Definitions\n* **Competitive environments** - two or more agents have conflicting goals\n* **Evaluation function** - heuristic to treat nonterminal nodes as terminal-replace UTILITY with EVAL\n* **Game tree** - search tree that follows every sequence of moves to a terminal state\n* **Ply** - one move by one player, one level deeper in the search tree\n* **Minimax value** - utility for MAX of being in that state assuming both players play optimally\n* **Minimax decision** - decision made by player after running minimax-optimal choice for that player\n* **Minimax search** - DFS using minimax on each node to assign each state a value\n* **M** - maximum depth of game tree\n* **B** - number of legal moves at each point\n* **Alpha** - value of best choice found so far at any choice point along path for MAX (at least)\n* **Beta** - value of best choice found so far at any choice point along path for MIN (at most)\n* **Killer moves** - best moves, want to find them first with killer move heuristic\n* **Transpositions** - different permutations of move sequences that end in same position\n* **Transposition table** - catches heuristic values of states if encountered before\n* **Type a strategy** - consider all possible moves to certain depth then use heuristic to estimate utility-wide but shallow\n* **Type b strategy** - ignore moves that look bad and follow promising lines as far as possible, deep but narrow\n* **Cutoff test** - replaces terminal test for when to stop looking-must return true for terminal states\n* **Quiescent** - states that don't have a pending move that wildly swings evaluation\n* **Horizon effect** - opponent's damaging move is unavoidable but can be delayed past search depth\n* **Singular extensions** - moves that are clearly better even when search would be cut off\n* **Late move reduction** - assumes move ordering has been done well, searches deeper for earlier moves\n* **Table lookup** - use lookup for common scenarios instead of searching\n* **Policy** - mapping from every possible state to best move\n* **Maximum expected utility** - rational agent should choose action that maximizes expected utility\n* **Orderability** - given two lotteries, rational agent should prefer one or be indifferent\n* **Transitivity** - A>B and B>C implies A>C\n* **Continuity** - If A>B>C, there is some probability p so agent is indifferent between B and [p, A; 1-p, C]\n* **Substitutability** - if indifferent between lotteries A and B, [p, A; 1-p, C]~[p, B; 1-p, C] (also truw with >)\n* **Monotonicity** - A>B implies that agent prefers lottery with higher probability of A\n* **Decomposability** - compound lotteries can be reduced to simpler ones using laws of probability\n* **Value function/ordinal utility function** - ranking of states, used for deterministic environments\n* **Preference elicitation** - trying to find a human's utility function by presenting choices\n* **Micromort** - 1 in a million chance of dying, used for value people place on own lives\n* **Qaly** - quality-adjusted life year, used for medical decisions\n* **Monotonic preference** - more is better (like money)\n* **Certainty equivalent** - value an agent will accept instead of lottery\n* **Insurance premium** - difference between EMV of lottery and certainty equivalent\n* **Risk-neutral** - linear curve for utility of asset\n* **Unbiased** - E(U_hat(a) - EU(a)) = 0\n* **Order statistic** - distribution of any particular ranked element of sample\n* **Optimizer's curse** - tendency of estimated expected utility of best choice to be too high\n* **Normative theory** - describes how rational agent should act\n* **Descriptive theory** - describes how agents actually act\n* **Certainty effect** - people are attracted togains that are certain\n* **Framing effect** - people choose differently when options are presented as gains or losses\n* **Anchoring effect** - presenting options just to skew perception of other options\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nIn CSPs, don't  treat states as atomic/black boxes but can see\ninside. CSP has X (set of variables), D (set of domains for each variable), and\nC (set of constraints that specify allowable combinations of values). Each constraint\nis a tuple that contains a pair of points and a relation that defines the values\nthey can take on (explicit set or function). Solving CSP is NP-complete, but there\nare subclasses that can be solves efficiently. Don't need to search until solution\nis found-can reject some assignments as soon as they violate constraint, reducing\nsearch space. Simplest CSPs have discrete finite domains. Solutions exist for\nlinear constraint problems on integer variables. Could transform any CSP into one\nwith only binary constraints by using auxiliary variables. Could also use dual graph:\ngraph where there is one variable for each constraint and binary constraints for\nconstraints that share variables. Easier, however, to use global constraints.\nCould model preference constraints as costs on individual variable assignments.\nThen can solve CSPs with optimization to make it a constrained optimization\nproblem.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nConstraint propogation can be done with search or as preprocessing.\nAC-3 enforces arc consistency. Maintain queue of arcs (initially all), with binary\nconstraints as two arcs, one in each direction. Pop off arc (Xi, Xj) and make Xi\narc-consistent with Xj. If you change domain of Xi, add all (Xk, Xi) arcs to\nqueue where Xk are all neighbors in constraint graph. If domain is empty, failure.\nChecking single arc is time of O(d^2) and AC-3 is time of O(c d^3). {Xi, Xj} is\npath consistent with Xm if for every assignment {Xi=a, Xj=b} consistent with their\nconstraints, there is an assignment to Xm that satisfies constraints on {Xi, Xm}\nand {Xm, Xj}. For strongly n-consistent, can start by choosing consistent value\nfor X1, then for X2, etc. Time of O(n^2 d). Establishing n-consistentcy is\ntime and space exponential in n.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nConstraint satisfaction doesn't always solve CSP (some variables\nhave multiple possible values remaining). Then need to do search. Depth-limited\nsearch takes time and space of O(n! d^n) even though there are only d^n assignments.\nWith commutativity, number of leaves is d^n. Backtracking chooses an unassigned\nvariable, tries a possible value, and the propogates it. If solution is found,\nreport, if not, try next value and continue. If no value works, failure. Forward\nchecking is whenever a variable X is assigned, establish arc-consistency for it.\nMaintaining Arc Consistency (MAC) assigns a value to Xi the calls AC-3 but starts\nwith a queue of arcs (Xj, Xi) for Xj neighbors of Xi. Like recursively calling\nforward checking. Backjumping backtracks to most recent assignment in conflict set.\nWith forward checking, when X=x gets rid of a value in Y, add X=x to Y's conflict\nset. Simple backjumping is unneeded when using forward checking or any stronger\nconsistency checking like MAC. Conflict-directed backjumping is backjumping\nthat uses conflict sets defined  by set of previous variables that caused\nconflict together with any subsequent variables. Can keep track of no-good assignments\nand know never use that combination if ever encountered again.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\nLocal search changes variable values one at a time by improving values\nof a variable each step. Can start with complete assignment that isn't consistent and switch\nconflicted variables using min-conflict heuristic to a better assignment. Works well\nfor problems whose solutions are densely distributed througout state space. Plateau\nsearch allows movement from state to another state with same number of conflicts.\nFor constranit weighting, each constraint is given weight, initially 1. At each step,\nchoose variable value pair resulting in lowest weight of violated constraints. Then\nincrement each weight whose constraint is violated. Local search can also be used\nonline when problem changes.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\nIndependent subproblems can be found by looking at connected components\nof constraint graph. Total work is O(d^c n / c) where c is number of variables in\neach subproblem (n/c subproblems). Without decomposition, is O(d^n). Any tree\nstructures constraint graph can be solved in linear (in n) time. To solve tree\nstructured CSP, pick any variable to be root and do topological sort. Can make\ngraph consistent in O(n) steps so time is O(n d^2). Can then just choose any\nremaining value for all variables. Cutset conditioning assigns values to variables\nto remaining variables form tree. Need to try each value. Form cycle cutset and for\neach possible assignment to variables in S that satisfy their constraints, remove\nvalues from remaining variables that are inconsistent and if solution exists,\nreturn it. If cycle cutset has size c, time is O(d^c (n-c) d^2). Could also use\ntree decomposition which is tree where each node has a set of variables. Every\nvariable in original problem appears in at least one tree node, if two variables\nare connected by a constraint in problem, must appear together with constraint\nin at least one node, if variable appears in two nodes, must appear in every\nnode along path connecting those nodes. Then can apply tree-CSP-solver to\nget solution in O(n d^2) time. Domain is tuples of values, not individual values.\nEach graph has several tree decompositions, so try to make subproblems as small\nas possible. If graph has tree width w, time of O(n d^(w+1)) given tree decomposition.\nIf have cycle-cutset size c, there is a tree width of size w<c+1. Tree\ndecomposition has faster time but cycle-cutset is linear memory and tree\ndecomposition's memory is exponential in w.\n\n\n## Module 6 Lecture Notes\nIn CSPs, only use problem definition, not heuristic\nfunctions (could use them, but usually want general algorithms). Waltz algorithm\nfor checking direction of lines in 2D objects is CSP. For planar constraint graphs,\nnumber of arcs is O(n).\n\n## Module 6 Definitions\n* **Constraint satisfaction problem** - problem where solution is an assignment of values to variables that satisfy constraints\n* **Consistent/legal assignment** - assignment that does not violate any constraints\n* **Complete assignment** - assignment where every variable is assigned a value\n* **Partial assignment** - assignment where some variables are unassigned\n* **Partial solution** - partial assignment that is consistent\n* **Constraint graph** - nodes are variables, edge connects variables that have a constraint\n* **Precedence constraint** - constraint on which variable must come first chronologically\n* **Disjunctive constraint** - constraint of the form x or y must be true\n* **Linear programming** - constraints must be linear equalities or inequalities-solved in polynomial time\n* **Unary constraint** - restricts value of single variable\n* **Binary constraint** - relates two variables\n* **Global constraint** - constraint involving arbitrary number of variables\n* **Cryptarithmetic puzzle** - eachletter represents different digit\n* **Constraint hypergraph** - contains nodes and hypernodes (which represent n-ary constraints involving n variables)\n* **Preference constraints** - say which solutions are prefferred\n* **Constraint propogation** - using constraints to reduce number of legal values for a variable\n* **Local consistency** - treat each variable as node and binary constraint as edge to eliminate inconsistent assignments\n* **Node consistent** - if all values in variable's domain satisfy unary constraints\n* **Arc consistent** - every value of variable satisfies binary constraints\n* **N** - number of variables in CSP\n* **C** - number of binary constraints\n* **D** - maximum domain size\n* **Path consistency** - implicit constraints inferred by looking at triplets of variables\n* **K-consistency** - for any set of k-1 variables and consistent assignment of their values, exists a consistent assignment for kth variable\n* **Strongly k-consistent** - k-consistent, (k-1)-consistent...1-consistent\n* **Resource constraint** - at-most constraint on variables\n* **Bounds propogation** - for constraints between variables, could reduce bounds of domains for each one\n* **Bounds-consistent** - for every variable X and both lower-bound and upper-bound of X, exists value of Y that satisfies X-Y constraint\n* **Commutativity** - order of application of any given set of actions doesn't matter\n* **Minimum remaining values** - heuristic for choosing unassigned variable-choose most constrained\n* **Degree heuristic** - heuristic for choosing unassigned variable-choose variable that imposes the most constraints\n* **Least constraining value** - heuristic for choosing value-pick value that rules out the fewest choices for neighbors\n* **Chronological backtracking** - when an assignment fails, backtrack to most recent assigned variable\n* **Conflict set** - set of assignments that are in conflict with some variable assignment\n* **Constraint learning** - finding a minimum set of variables from the conflict set that causes the problem\n* **No-good** - set found by constraint learning along with their values\n* **Min-conflicts heuristic** - select value that results in the minimum number of conflicts\n* **Tabu search** - keep list of recently visited states and don't go back to them\n* **Independent subproblems** - solution to those problems can be combined in any way for global solution\n* **Directional arc consistency** - DAC under ordering of X1,...Xn iff every Xi is arc consistent with Xj for j>i\n* **Topological sort** - ordering of variables so each variable is after parent\n* **Cycle cutset** - subset S of CSP's variables such that constraint graph becomes tree after S is removed\n* **Cutset conditioning** - finding cutset and solving CSP after trying its values on graph\n* **Tree width** - one less than the size of the largest node in tree decomposition graph\n* **Value symmetry** - can permute values of solution to get d! solutions\n* **Symmetry-breaking constraint** - impose arbitrary ordering to reduce value symmetry to one solution\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nHave TELL and ASK functions for knowledge base. When asked a question,\nanswer should follow from what has previously been told to knowledge base. Shouldn't\nmake things up. Agent program TELLs knowledge base what it perceives, ASKS knowledge\nbase what action to do, then TELLs the knowledge base chosen action and returns\naction.\n\n\n## AIMA Chapter 7.2 The Wumpus World\nTask environment has Performance Measure, Environment, Actuators,\nand Sensors (PEAS). If available information is correct and conclusion is drawn\nfrom that information, conclusion is correct.\n\n\n## AIMA Chapter 7.3 Logic\nEvery sentence must be either true or false in each possible\nworld, no in between. If a sentence alpha is true in model m, m satisfies\nalpha or m is a model of alpha. M(alpha) is set of all models of alpha.\nalpha |= beta iff in every model in which alpha is true, beta is also true.\n(a |= b iff M(a) subseteq M(b)). Knowledge base is set of sdentences that asserts\nall individual sentences. False if it contradicts what agent knows. Logical\ninferrence is using entailment to derive conclusions. Model checking\nenumerates all possible models to check that sentence alpha is true in all\nmodels in which knowledge base KB is true (M(KB) subseteq M(alpha)). If an\ninferrence algorithm i can derive alpha from the knowledge base KB, KB |-i alpha.\nModel checking is a sound procedure, but only works if space of models is finite.\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nModel sets truth value for every propositional symbol. Truth\nvalue of every propositional symbol (except True and False) must be specified\nin model. Can use truth tables for complex sentences given  truth values of\ncomponents. Checking all models might take a long time. If KB and alpha have n\nsymbols, there are 2^n models, so time is O(2^n). Space is O(n) because it is\ndepth first. Every known inference algorithm has worst case exponential in size\nofinput (co-NP-complete).\n\n\n## AIMA 7.5 Propositional Theorem Proving\na and b are logically equivalent iff a|=b and b|=a. a is valid\niff -a is unsatisfiable, a is satisfiable iff -a is not valid. a|=b iff sentence\n(a ^ -b) is unsatisfiable. Can use proof by contradiction fo prove b from a by\nchecking unsatisfiability of (a ^ -b). Not all inference rules work in both directions\nbut some do. To apply search to problems of inference, need initial state (knowledge\nbase), actions (inference rules), result (add sentence in bottom half of inference\nrule), and goal (state that contains sentence we are trying to prove). Alternative\nto enumerating models. Can also use resolution. Unit resolution takes a clause and\na literal to produce new clause. Can apply resolution rule when li and mj are\ncomplementary literals. Takes two clauses and produces new clause containing\nall literals except complementary literals. Can only resolve one pair of complementary\nliterals at a time. Resulting clause should only contain one copy of each literal\ne.g. (AvB)^(Av-B) obtains (AvA) which is A. Every sentence of propositional\nlogic is equivalent to conjunction of clauses (conjunctive normal form).\nReplace (a <=> b) with (a => b)^(b => a). Replace (a => b) with (-a v b). Move\n(-) inward by DeMorgan's laws. Distribute v over ^ wherever possible. Results\nin (Clause_1 ^...^ Clause_n) where each clause is (Literal_1 v...v Literal_m).\nCan then show that KB|=a by showing (KB^-a) is unsatisfiable (prove a contradiction).\nConvert (KB^-a) into CNF, then apply resolution rule to resulting clauses. Either\nthere are no new clauses that can be added (KB does not entail a) of two clauses\nresolve to yield the empty clause (KB entails a). Resolution closure RC(S) is set of\nall clauses derivable by repeated application of resolution rule to clauses in S\nor their derivatives. PL-Resolution is complete. If you resolve two horn clauses,\nget back a horn clause. Definite clause can be written as implication whose premise\nis conjunction of positive literals and whose conclusion is a single positive literal.\nInference with horn clauses can be done with forward-chaining or backward-chaining.\nEntailment with horn clauses if linear in size of KB. PL-FC-Entails determines\nif a proposition symbol q (query) is entailed by KB of definite clauses. If all\npremises of implication are knwon, conclusion is added to set of known facts.\nContinues until finding q or no further inferences. Linear time. Sound and complete.\nIn backward chaining, algorithm finds implications whose conclusion is q. If premises\ncan be proven (by backward chaining) q is true.\n\n\n## Module 7 Lecture Notes\nCould have knowledge base in form of knowledge\nrepresentation language e.g. planet(x), sun(y), or far_from(x, y)=>cold(x)\n\n\t PL_RESOLUTION(KB, a) returns true or false:\n\n\t\t clauses <- set of clauses in the CNF representation of KB ^-a\n\n\t\t new <- {}\n\n\t\t while true do:\n\n\t\t\t for each pair of clauses Ci Cj in clauses do:\n\n\t\t\t\t resolvents <- PL_RESOLVE(Ci,Cj)\n\n\t\t\t\t if resolvents contains empty clause, return true\n\n\t\t\t\t new <- new U resolvents\n\n\t\t\t if new subseteq clauses then return false\n\n\t\t\t clauses <- clauses U new\n\n\n\n\t PL_FC_ENTAILS(KB, q) returns true or false:\n\n\t\t count <- table where count[c] is initially number of symbols in clause c's premise\n\n\t\t inferred <- table where inferred[c] is initially false for all symbols\n\n\t\t queue <- queue of symbols, initially symbols known to be true in KB\n\n\t\t while queue is not empty do:\n\n\t\t\t p <- POP(queue)\n\n\t\t\t if p==q then return true\n\n\t\t\t if inferred[p] == false:\n\n\t\t\t\t inferred[p] <- true\n\n\t\t\t\t for each clause c in KB where p is in c.PREMISE do:\n\n\t\t\t\t\t decrement count[c]\n\n\t\t\t\t\t if count[c] == 0 then add c.CONCLUSION to queue\n\n\t\t return false\n\n\n## Module 7 Definitions\n* **Knowledge-based agent** - use process of reasoning over internal representation to decideon actions\n* **Knowledge base** - set of sentences\n* **Knowledge representation language** - each sentence represents some assertion about the world\n* **Axiom** - sentence taken as given\n* **Inference** - deriving new sentences from  old ones\n* **Declarative approach** - TELL agent sentences one by one until agent knows how to operate\n* **Procedural approach** - encodes desired behavior directly as code\n* **Syntax** - specifies all the sentences that are well formed\n* **Semantics** - meaning of sentences\n* **Possible world** - potentially real environments that agent might or might not be in\n* **Model** - mathematical abstraction, each of which has a fixed truth value\n* **Entailment** - sentences follow logically from another sentence- alpha |= beta\n* **Sound/truth-preserving** - inference algoruthm that derives only entailed sentences\n* **Complete** - if an inferrrence algorithm can derive any sentence that is entailed\n* **Grounding** - connection between logical reasoning processes and real environment\n* **Atomic sentences** - consist of a single propositional symbol\n* **Propositional symbol** - stands for a proposition that can either be true or false\n* **Complex sentences** - constructed from simpler sentences using parentheses and logical connectives\n* **Positive literal** - atomic sentence\n* **Negative literal** - negated atomic sentence\n* **Negation** - -P: -P is true iff P is false in m\n* **Conjunction** - and (^): P^Q is true iff both P and Q are true in m\n* **Disjunction** - or (v): PvQ is true iff P or Q is true in m\n* **Implication** - premise/antecedent => conclusion/consequent: P=>Q is true unless P is true and Q is false in m\n* **Biconditional** - iff (<=>): P<=>Q is true iff P and Q are both true or both false in m\n* **Theorem proving** - applying rules of inference to sentences in knowledge base\n* **Logical equivalence** - alpha and beta are logically equivalent if they are true in the same set of models\n* **Contraposition** - (a => b) == (-b => -a)\n* **Implication elimination** - (a => b) == (-a v b)\n* **Biconditional elimination** - (a <=> b) == ((a => b) ^ (b => a))\n* **Demorgan1** - -(a ^ b) == (-a v -b)\n* **Demorgan2** - -(a v b) == (-a ^ -b)\n* **Distributivity of ^ over v** - ((a ^ (b v c)) == ((a ^ b) v (a ^ c))\n* **Distributivity of v over ^** - (a v (b ^ c)) == ((a v b) ^ (a v c))\n* **Validity** - sentence is valid if true in all models (tautology) e.g. (P v -P)\n* **Deduction theorem** - for any sentences a and b, (a|=b) iff the sentence (a=>b) is valid\n* **Satisfiability** - if a sentence is true in (satisfied by) some model\n* **Modus ponens** - {(a => b), a}/b : whenever any sentence a=>b and a are given, b canbe inferred\n* **And elimination** - (a^b)/b : from a conjunction, any of the conjuncts can be inferred\n* **Monotonicity** - set of entailed sentences can only increase as information is added to KB\n* **Unit resolution inference rule** - {(l1 v ... v lk) m}/{l1 v ... v li-1 v li+1 v... lk} where li is -m\n* **Complementary literals** - one is the negation of the other\n* **Clause** - disjunction of literals\n* **Unit clause** - single literal (disjunction of one literal)\n* **Resolution rule** - {(l1 v...v lk) (m1 v...v mn)}/{l1 v...v li-1 v li+1 v...v lk v m1 v...v mj-1 v...v mn}\n* **Factoring** - removal of multiple copies of literals\n* **Ground resolution theorem** - if set of clauses S is unsatisfiable, RC(S) contains the empty clause\n* **Definite clause** - disjunction of literals of which exactly one is positive (not negated)\n* **Horn clause** - disjunction of literals of which at most one is positive (not negated)\n* **Goal clause** - disjunction of literals, none of which are positive (not negated)\n* **K-cnf sentence** - CNF sentence where each clause has at most k literals\n* **Body/head** - for horn clause, premise=body and conclusion=head\n* **Fact** - sentence containing single positive literal\n* **Data-driven reasoning** - reasoning in which focus of attention starts with known data\n* **Goal directed reasoning** - look for goal by only dealing with relevant facts (like backward chaining)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}