{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Kachik_Ashkaryan_CIS521_Midterm_Notes",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5bbdee8b-0e3b-4c27-fd61-c4eab2316b61"
      },
      "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": 4,
      "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": "44f3686c-e7ff-4cb1-f796-ad78b8c8d1c1"
      },
      "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": 5,
      "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": 6,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "Rationality, doing the right thing. Intelligence, internal through process\n",
        "and reasoning (others focus on intelligent behavior). Human v rational (humans\n",
        "sometimes act irrational), thought vs behavior. Turing test, ask computer\n",
        "questions, cannot tell if resonse if from person or computer. Need NLP, knowledge \n",
        "representation, automated reasoning, and machine learning to learn patterns. Total\n",
        "Turing test, includes physical aspect, need computer vision and robotics. Others\n",
        "wish to incorporate logic into their work (using premises (knowledge of the \n",
        "world that is certain)). If uncertain, use probability.\"Laws of Thought\", corect \n",
        "inferences. The rational-agent approach to AI is more general than \"laws of thought\"\n",
        "since correct inference is one of several parts and easier to build machine models\n",
        "of it. The standard model of AI, focused on making agents that do the right thing.\n",
        "In the long run, will need to update standard model since it requires the machine to have a \n",
        "fully specified objective.\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" \n",
        "Strong AI is now human level AI, solve new problems as well as humans. Qualification\n",
        "problem, difficult to capture every contingency of appropriate behavior in a set of \n",
        "necessary and suffiecient logical rules. Good old fashion AI (GOFAI), simple logical \n",
        "agent design. Embodied cognition, robotics, vision, and sensors are central to \n",
        "AI. Lucas claims machiens are inferior to humans, incompleteness theorem they \n",
        "cannot establish the truth of their own Gödel sentence. Three inconsistencies, \n",
        "machine does not need to establish a truth from a sentence (I cannot always \n",
        "tell if this sentence is true), no machine can prove something a human can't,\n",
        "machines can change their minds.\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" \n",
        "Does thinking require a brain, polite convention that everyone thinks. Chinese \n",
        "room, give guy characters and rules, he intelligently translates it, computers\n",
        "generate no understanding. COnciousness, qualia, awareness of outside world. \n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "In general, an agent’s choice of action at any given instant can depend on its \n",
        "built-in knowledge and on the entire percept sequence observed to date, but \n",
        "not on anything it hasn’t perceived. Agent’s behavior is described by the agent \n",
        "function that maps any given percept sequence to an action. Agent program is what\n",
        "actually makes the action happen in the physical system.\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "Check agents actions to scenario, if the reaction sequence is favorable, then \n",
        "it performed well. We call this a performance measure. As a general rule, it is\n",
        "better to design performance measures according to what one actually wants to \n",
        "be achieved in the environment, rather than according to how one thinks the\n",
        "agent should behave. Rational depends on 4 things: performance measure that \n",
        "defines the criterion of success, agent’s prior knowledge of the environment,\n",
        "the actions that the agent can perform, and the agent’s percept sequence to date.\n",
        "Rational maximizes expected performance, while perfection maximizes actual \n",
        "performance. Sometimes random initially because they have nothing to go off of.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "Need to define PEAS for task environment. Example: agent, tutor. Perf: Student \n",
        "test score, Env: set of student, actuators, exercises, speech, Sensors, ears.\n",
        "FULLY OBSERVABLE, sensors give access to complete state of envirnoment at each\n",
        "point in time. Fully observable environments are convenient because the agent \n",
        "need not maintain any internal state to keep track of the world. An environment\n",
        "might be PARTIALLY observable because of noisy and inaccurate sensors or\n",
        "because parts of the state are simply missing from the sensor data. If no data, \n",
        "unobservable. Singel vs multiagent, call the other an agent if it is also trying\n",
        "to maximize its behavior, competitive vs cooperative. If the next state of the \n",
        "environment is completely determined by the current state and the action \n",
        "executed by the agent(s), then we say the environment is deterministic; \n",
        "otherwise, it is nondeterministic. Taxi driving is clearly nondeterministic \n",
        "in this sense, because one can never predict the behavior of traffic\n",
        "exactly; moreover, one’s tires may blow out unexpectedly and one’s \n",
        "engine may seize up without warning. Schoastic is non-deterministic with \n",
        "probabilities, non-deterministic does not have numbers. Episodic, action does not\n",
        "depend on last episode. Sequential (chess), current action influences future \n",
        "decisions. If envornoment can change, it's dynamic, else it is static. Semidynamic\n",
        "if score changes with time (chess and clocks). Discrete (states) vs continuous, \n",
        "driving a car. Known vs unknown, the rules or laws of the envirnoment (card \n",
        "game with cars flipped over). The hardest case is partially observable, \n",
        "multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" \n",
        "Agent=architecture+program. Table approach for lookup actions on environment\n",
        "would mean a huge table. Simple reflex agents select actions on the basis of the\n",
        "current percept, ignoring the rest of the percept history (break when car in\n",
        "front breaks), condition-action rule (if x then y). Will work only if the\n",
        "correct decision can be made on the basis of just the current percept—that \n",
        "is, only if the environment is fully observable. Sometimes randomized simple\n",
        " reflex agent might outperform a deterministic simple reflex agent, but not \n",
        " rational, just useful trick. \n",
        " Maintain some sort of internal state that depends on the percept history and \n",
        " thereby reflects at least some of the unobserved aspects of the current state.\n",
        "Updating internal state depends on transition model of the world, and sensor\n",
        " model for percieving the change, create model-based agent.\n",
        " Goal based agent, need goal info, to combine with model.\n",
        " Utility-based agent, use utility function with goal for each state. Rationally, \n",
        " maximize the expected utility of the action outcomes. \n",
        " A learning agent can be divided into four conceptual components, the most \n",
        " important distinction is between the learning element, which is responsible \n",
        " for making improvements, and the performance element, which is responsible\n",
        "for selecting external actions. The learning element uses feedback from the \n",
        "critic on how the agent is doing and determines how the performance element \n",
        "should be modified to do better in the future. The problem generator is\n",
        "responsible for suggesting actions that will lead to new and informative \n",
        "experiences. Atomic representation each state of the world is indivisible—it \n",
        "has no internal structure. Factored representation splits up each state into a \n",
        "fixed set of variables or attributes, each of which can have a value.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "Agent percieves envornoment through sensors and acts on environemt through \n",
        "actuators, percept is agents percentpual inputs at given instance. Easy solution\n",
        "for agent program, giant table, but exponential in length of P (every possible \n",
        "sequence of input). Example, robot, stock market software agent, thermostat,\n",
        "etc. Consequentialism, evaluate actions by consequences. Use performance measure\n",
        "as criterion. Give performance based on what you want to be achieved, not how\n",
        "you want it to behave. Maximize expected value instead of actual value that \n",
        "requires omniscience. Agent function, abstract mathematical description; agent\n",
        "program, concrete implementation that implements function.\n",
        "Fully vs Partially observable: chess table vs self driving car\n",
        "Deterministic, nondeterministic, stochastic: we know what happens when we choose\n",
        "an action and the env is completely knowable, else outcome is uncertain, else \n",
        "we know probabilities for outcomes. \n",
        "Episodic v Sequential : independent not affect future\n",
        "Static v dynamic: if the env changes like car\n",
        "Discrete v Continuous: finite set of actions, state rep is continuous range\n",
        "Single v Multi Agent, game like cross word vs pacman\n",
        "If something else in the environment is trying to optimize something, then it\n",
        "is an agent. Hardest is continuous, partially obs, stochastic, multiagent (self\n",
        "driving car). Easy, fully observable, static, deterministic, discrete like chess.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"introspection\" : \"thinking about your own thoughts\",\n",
        "\"psychological experiments\" : \"observing person in action\",\n",
        "\"brain imaging\" : \"observing ht brain\",\n",
        "\"Cognitive Science\": \"brings together computer models from AI and experimental techniques from psychology\",\n",
        "\"agent\":\"someone that acts, operate autonomously, percieve their environment, adapt to change, make goals\",\n",
        "\"rational agent\":\"For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure\",\n",
        "\"limited rationality\":\"acting appropriately when there is not enough time to do all the computations one might like\",\n",
        "\"value alignment problem\":\"the values or objectives put into the machine must be aligned with those of the human.\",\n",
        "\"agent\" : \"anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators\",\n",
        "\"percept sequence\" : \" the complete history of everything the agent has ever perceived\",\n",
        "\"consequentialism\":\" we evaluate an agent’s behavior by its consequences\",\n",
        "\"information gathering\":\"Doing actions in order to modify future percepts\",\n",
        "\"task environments\" : \"problems which rational agents are the solutions\",\n",
        "\"PEAS\" : \"Performance, Environment, Actuators, Sensors\",\n",
        "\n",
        "}\n"
      ],
      "execution_count": 7,
      "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": "e35d716b-1646-4b22-810e-4c4bb0dcdb9b"
      },
      "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": 8,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nRationality, doing the right thing. Intelligence, internal through process\nand reasoning (others focus on intelligent behavior). Human v rational (humans\nsometimes act irrational), thought vs behavior. Turing test, ask computer\nquestions, cannot tell if resonse if from person or computer. Need NLP, knowledge \nrepresentation, automated reasoning, and machine learning to learn patterns. Total\nTuring test, includes physical aspect, need computer vision and robotics. Others\nwish to incorporate logic into their work (using premises (knowledge of the \nworld that is certain)). If uncertain, use probability.\"Laws of Thought\", corect \ninferences. The rational-agent approach to AI is more general than \"laws of thought\"\nsince correct inference is one of several parts and easier to build machine models\nof it. The standard model of AI, focused on making agents that do the right thing.\nIn the long run, will need to update standard model since it requires the machine to have a \nfully specified objective.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n \nStrong AI is now human level AI, solve new problems as well as humans. Qualification\nproblem, difficult to capture every contingency of appropriate behavior in a set of \nnecessary and suffiecient logical rules. Good old fashion AI (GOFAI), simple logical \nagent design. Embodied cognition, robotics, vision, and sensors are central to \nAI. Lucas claims machiens are inferior to humans, incompleteness theorem they \ncannot establish the truth of their own Gödel sentence. Three inconsistencies, \nmachine does not need to establish a truth from a sentence (I cannot always \ntell if this sentence is true), no machine can prove something a human can't,\nmachines can change their minds.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \nDoes thinking require a brain, polite convention that everyone thinks. Chinese \nroom, give guy characters and rules, he intelligently translates it, computers\ngenerate no understanding. COnciousness, qualia, awareness of outside world. \n \n\n## AIMA 2.1 Agents and Environments\n \nIn general, an agent’s choice of action at any given instant can depend on its \nbuilt-in knowledge and on the entire percept sequence observed to date, but \nnot on anything it hasn’t perceived. Agent’s behavior is described by the agent \nfunction that maps any given percept sequence to an action. Agent program is what\nactually makes the action happen in the physical system.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nCheck agents actions to scenario, if the reaction sequence is favorable, then \nit performed well. We call this a performance measure. As a general rule, it is\nbetter to design performance measures according to what one actually wants to \nbe achieved in the environment, rather than according to how one thinks the\nagent should behave. Rational depends on 4 things: performance measure that \ndefines the criterion of success, agent’s prior knowledge of the environment,\nthe actions that the agent can perform, and the agent’s percept sequence to date.\nRational maximizes expected performance, while perfection maximizes actual \nperformance. Sometimes random initially because they have nothing to go off of.\n\n\n## AIMA 2.3 The Nature of Environments\n \nNeed to define PEAS for task environment. Example: agent, tutor. Perf: Student \ntest score, Env: set of student, actuators, exercises, speech, Sensors, ears.\nFULLY OBSERVABLE, sensors give access to complete state of envirnoment at each\npoint in time. Fully observable environments are convenient because the agent \nneed not maintain any internal state to keep track of the world. An environment\nmight be PARTIALLY observable because of noisy and inaccurate sensors or\nbecause parts of the state are simply missing from the sensor data. If no data, \nunobservable. Singel vs multiagent, call the other an agent if it is also trying\nto maximize its behavior, competitive vs cooperative. If the next state of the \nenvironment is completely determined by the current state and the action \nexecuted by the agent(s), then we say the environment is deterministic; \notherwise, it is nondeterministic. Taxi driving is clearly nondeterministic \nin this sense, because one can never predict the behavior of traffic\nexactly; moreover, one’s tires may blow out unexpectedly and one’s \nengine may seize up without warning. Schoastic is non-deterministic with \nprobabilities, non-deterministic does not have numbers. Episodic, action does not\ndepend on last episode. Sequential (chess), current action influences future \ndecisions. If envornoment can change, it's dynamic, else it is static. Semidynamic\nif score changes with time (chess and clocks). Discrete (states) vs continuous, \ndriving a car. Known vs unknown, the rules or laws of the envirnoment (card \ngame with cars flipped over). The hardest case is partially observable, \nmultiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n \nAgent=architecture+program. Table approach for lookup actions on environment\nwould mean a huge table. Simple reflex agents select actions on the basis of the\ncurrent percept, ignoring the rest of the percept history (break when car in\nfront breaks), condition-action rule (if x then y). Will work only if the\ncorrect decision can be made on the basis of just the current percept—that \nis, only if the environment is fully observable. Sometimes randomized simple\n reflex agent might outperform a deterministic simple reflex agent, but not \n rational, just useful trick. \n Maintain some sort of internal state that depends on the percept history and \n thereby reflects at least some of the unobserved aspects of the current state.\nUpdating internal state depends on transition model of the world, and sensor\n model for percieving the change, create model-based agent.\n Goal based agent, need goal info, to combine with model.\n Utility-based agent, use utility function with goal for each state. Rationally, \n maximize the expected utility of the action outcomes. \n A learning agent can be divided into four conceptual components, the most \n important distinction is between the learning element, which is responsible \n for making improvements, and the performance element, which is responsible\nfor selecting external actions. The learning element uses feedback from the \ncritic on how the agent is doing and determines how the performance element \nshould be modified to do better in the future. The problem generator is\nresponsible for suggesting actions that will lead to new and informative \nexperiences. Atomic representation each state of the world is indivisible—it \nhas no internal structure. Factored representation splits up each state into a \nfixed set of variables or attributes, each of which can have a value.\n\n\n\n## Module 1 Lecture Notes\n \nAgent percieves envornoment through sensors and acts on environemt through \nactuators, percept is agents percentpual inputs at given instance. Easy solution\nfor agent program, giant table, but exponential in length of P (every possible \nsequence of input). Example, robot, stock market software agent, thermostat,\netc. Consequentialism, evaluate actions by consequences. Use performance measure\nas criterion. Give performance based on what you want to be achieved, not how\nyou want it to behave. Maximize expected value instead of actual value that \nrequires omniscience. Agent function, abstract mathematical description; agent\nprogram, concrete implementation that implements function.\nFully vs Partially observable: chess table vs self driving car\nDeterministic, nondeterministic, stochastic: we know what happens when we choose\nan action and the env is completely knowable, else outcome is uncertain, else \nwe know probabilities for outcomes. \nEpisodic v Sequential : independent not affect future\nStatic v dynamic: if the env changes like car\nDiscrete v Continuous: finite set of actions, state rep is continuous range\nSingle v Multi Agent, game like cross word vs pacman\nIf something else in the environment is trying to optimize something, then it\nis an agent. Hardest is continuous, partially obs, stochastic, multiagent (self\ndriving car). Easy, fully observable, static, deterministic, discrete like chess.\n\n\n## Module 1 Definitions\n* **Introspection** - thinking about your own thoughts\n* **Psychological experiments** - observing person in action\n* **Brain imaging** - observing ht brain\n* **Cognitive science** - brings together computer models from AI and experimental techniques from psychology\n* **Agent** - anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators\n* **Rational agent** - For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure\n* **Limited rationality** - acting appropriately when there is not enough time to do all the computations one might like\n* **Value alignment problem** - the values or objectives put into the machine must be aligned with those of the human.\n* **Percept sequence** -  the complete history of everything the agent has ever perceived\n* **Consequentialism** -  we evaluate an agent’s behavior by its consequences\n* **Information gathering** - Doing actions in order to modify future percepts\n* **Task environments** - problems which rational agents are the solutions\n* **Peas** - Performance, Environment, Actuators, Sensors\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" \n",
        "All data are objects (even functions). Garbage collection once unreachable. Every object has a fixed type,\n",
        "cant add \"foo\"+2 (strongly typed). Dynamically typed varibales, can change type of var\n",
        "by calling type(var) type errors caught at runtime. Concatenate string literals with +,\n",
        "immutable (when modified, makes new string). == checks whether same value,\n",
        "'is' checks for same object. Lists are mutable, use y=x[:] to get shallow copy\n",
        "of different object with same value.\n",
        "Tuple is immutable, string is immutable, list is mutable. Using t[1:-1:2] as\n",
        "slicing that creates a copy of subsequence.\n",
        "For list, use append, insert, index (get first occurance), count, remove, \n",
        "reverse, list.sort(using function), sort(list) to get copy.\n",
        "For strings, split(), join, capitalize, upper, strip.\n",
        "Dictionary, use hash table, thus key must be immutable. Get KeyError if key\n",
        "doesn't exist. Use .keys(), .values(), .items()\n",
        "Default dictionaries from Collections: defaultdict automatically initializes\n",
        "noexistent dic vals to empty string. For Counter, gives num of occurances.\n",
        "Function, return multiple by using tuple. Python doesn't allow function overloading,\n",
        "but operator overloading is possible with special methods. Give default values\n",
        "for arguments, make them optional. Non-defautl before default, or else syntax error.\n",
        "Keyword arguments can be out of order, c=43. Use *args for number of non-keyword\n",
        "args, use as tuple, unpack list using *list for args*. For keyword args, use \n",
        "**kwargs with first_name=\"John\" or **my_dict to unpack dictionary. Uses dynamic \n",
        "scope, function can use variable defined outside it and get different value on \n",
        "updates. Functions are first class, can be passed into other function, return\n",
        "function, assign function to variable.\n",
        "class Student(Man):#for subclass man, extends\n",
        "    univ=\"Upenn\"#class_attribute\n",
        "    def __init__(self,etc.) called when object is instantiated\n",
        "      Main.__init__(self, etc.)\n",
        "      self.student_name=name\n",
        "      super().foo()\n",
        "To redefine a method from subclass, use same name. Magic method, __str__,\n",
        "for printing, also len, copy, cmp, add, neg, __name__ (for main method). Duck typing,\n",
        "establishes suitability of object if it has a method. List comprehension, put in \n",
        "brackets to replace loop [expression for name in list if filter]. Generators are \n",
        "iterator objects, yeild is the next. Returns yield, starts where it left off.\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 450
        },
        "outputId": "f0ce20e1-46b1-46f4-eb23-70cb65bbd186"
      },
      "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": 10,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \nAll data are objects (even functions). Garbage collection once unreachable. Every object has a fixed type,\ncant add \"foo\"+2 (strongly typed). Dynamically typed varibales, can change type of var\nby calling type(var) type errors caught at runtime. Concatenate string literals with +,\nimmutable (when modified, makes new string). == checks whether same value,\n'is' checks for same object. Lists are mutable, use y=x[:] to get shallow copy\nof different object with same value.\nTuple is immutable, string is immutable, list is mutable. Using t[1:-1:2] as\nslicing that creates a copy of subsequence.\nFor list, use append, insert, index (get first occurance), count, remove, \nreverse, list.sort(using function), sort(list) to get copy.\nFor strings, split(), join, capitalize, upper, strip.\nDictionary, use hash table, thus key must be immutable. Get KeyError if key\ndoesn't exist. Use .keys(), .values(), .items()\nDefault dictionaries from Collections: defaultdict automatically initializes\nnoexistent dic vals to empty string. For Counter, gives num of occurances.\nFunction, return multiple by using tuple. Python doesn't allow function overloading,\nbut operator overloading is possible with special methods. Give default values\nfor arguments, make them optional. Non-defautl before default, or else syntax error.\nKeyword arguments can be out of order, c=43. Use *args for number of non-keyword\nargs, use as tuple, unpack list using *list for args*. For keyword args, use \n**kwargs with first_name=\"John\" or **my_dict to unpack dictionary. Uses dynamic \nscope, function can use variable defined outside it and get different value on \nupdates. Functions are first class, can be passed into other function, return\nfunction, assign function to variable.\nclass Student(Man):#for subclass man, extends\n    univ=\"Upenn\"#class_attribute\n    def __init__(self,etc.) called when object is instantiated\n      Main.__init__(self, etc.)\n      self.student_name=name\n      super().foo()\nTo redefine a method from subclass, use same name. Magic method, __str__,\nfor printing, also len, copy, cmp, add, neg, __name__ (for main method). Duck typing,\nestablishes suitability of object if it has a method. List comprehension, put in \nbrackets to replace loop [expression for name in list if filter]. Generators are \niterator objects, yeild is the next. Returns yield, starts where it left off.\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" \n",
        "Search, for sequence of actions that reach goal, called solution. For deterministic\n",
        "observable problem, the solution is always a fixed sequence of actions. A search problem can be defined formally as\n",
        "a set of possible states that the environment can be in, call this the state space.\n",
        "With initial and goal state. Each action at state is applicable to state. Transition\n",
        "model describes what each action does, along with action cost function.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Touring problems describe a set of locations that must be \n",
        "visited, rather than a single goal destination. The traveling salesperson \n",
        "problem (TSP) is a touring problem in which every city on a map must be \n",
        "visited. The aim is to find a tour with cost < C.\"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\" The state space describes the (possibly infinite) set of states\n",
        "in the world, and the actions that allow transitions from one state to another.\n",
        "The search tree describes paths between these states, reaching towards the \n",
        "goal. The search tree may have multiple paths to (and thus multiple nodes for)\n",
        "any given state, but each node in the tree has a unique path back to the root\n",
        "(as in all trees).\n",
        "BEST FIRST SEARCH - Like BFS where we expand node with least cost. If search\n",
        "for cycles say graph search, else tree-like. \n",
        "Measure performance in 4 ways, Completeness, find solution if there\n",
        "is one. Cost Optimal, Time complexity, space complexity.\n",
        "For an implicit state space, complexity can be measured in terms of the depth\n",
        "or number of actions in an optimal solution; the maximum number of actions in\n",
        "any path; and the branching factor or number of successors of a node that\n",
        "need to be considered. O(b^d) time and space complexity. \n",
        "\"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\" Uniform cost search-Disjkatra's O(b^(d+1)). DFS (B*maxDepth) to O(maxDepth) by\n",
        "backtracking search, only save up to current.\n",
        "terative deepening combines many of the benefits of depth-first and breadth-first \n",
        "search. Like depth-first search, its memory requirements are modest:\n",
        "when there is a solution, or on finite state spaces with no solution. Like\n",
        "breadth-first search, iterative deepening is optimal for problems where all \n",
        "actions have the same cost, and is complete on finite acyclic state spaces, \n",
        "or on any finite state space when we check nodes for cycles all the way up the path.\n",
        "The time complexity is when there is a solution, or when there is none. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Search, planning ahead to find best sequence, agents\n",
        "are called problem solving agents. Reflex agents, uses only current percept\n",
        "(about to hit a wall). If fully observable, fixed sequence of actions. If not, \n",
        "then branching strategy depending on what it percieves. Path cost must be additive.\n",
        "Make tree structure from problem, while frontier isn't empty, use strategy to remove\n",
        "and process. Repeating states turn linear to exponential problem. Tree search to \n",
        "graph search, check to see if node visited before adding to queue. Uninformed\n",
        "search, all non-goal nodes look equally good, else can be ranked using heuristic.\n",
        "b:branching-factor, d:depth-of-shallowest goal node, m:max_length_of_any_path.\n",
        "Using DFS, last-in-first-out queue (recurse), not complete, if infinite will go \n",
        "down forever, O(b^m) time O(bm) space since each node keeps its siblings. DFS\n",
        "for space and if path is long, BFS for infinite. Combine best aspect of both, \n",
        "DFS with depth limit, time is O(b^l), space O(bl), complete and optimal. When found at \n",
        "depth d, gives O(b^d) and O(bd).\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        "\"open loop\":\"close eyes and go along solutions since it's gauranteed to lead to goal\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 802
        },
        "outputId": "9653798a-647c-467c-828f-bbee374a4593"
      },
      "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": 12,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nSearch, for sequence of actions that reach goal, called solution. For deterministic\nobservable problem, the solution is always a fixed sequence of actions. A search problem can be defined formally as\na set of possible states that the environment can be in, call this the state space.\nWith initial and goal state. Each action at state is applicable to state. Transition\nmodel describes what each action does, along with action cost function.\n\n\n## AIMA Chapter 3.2 Example Problems\n Touring problems describe a set of locations that must be \nvisited, rather than a single goal destination. The traveling salesperson \nproblem (TSP) is a touring problem in which every city on a map must be \nvisited. The aim is to find a tour with cost < C.\n\n## AIMA Chapter 3.3 Search Algorithms\n The state space describes the (possibly infinite) set of states\nin the world, and the actions that allow transitions from one state to another.\nThe search tree describes paths between these states, reaching towards the \ngoal. The search tree may have multiple paths to (and thus multiple nodes for)\nany given state, but each node in the tree has a unique path back to the root\n(as in all trees).\nBEST FIRST SEARCH - Like BFS where we expand node with least cost. If search\nfor cycles say graph search, else tree-like. \nMeasure performance in 4 ways, Completeness, find solution if there\nis one. Cost Optimal, Time complexity, space complexity.\nFor an implicit state space, complexity can be measured in terms of the depth\nor number of actions in an optimal solution; the maximum number of actions in\nany path; and the branching factor or number of successors of a node that\nneed to be considered. O(b^d) time and space complexity. \n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uniform cost search-Disjkatra's O(b^(d+1)). DFS (B*maxDepth) to O(maxDepth) by\nbacktracking search, only save up to current.\nterative deepening combines many of the benefits of depth-first and breadth-first \nsearch. Like depth-first search, its memory requirements are modest:\nwhen there is a solution, or on finite state spaces with no solution. Like\nbreadth-first search, iterative deepening is optimal for problems where all \nactions have the same cost, and is complete on finite acyclic state spaces, \nor on any finite state space when we check nodes for cycles all the way up the path.\nThe time complexity is when there is a solution, or when there is none. \n\n## Module 3 Lecture Notes\n Search, planning ahead to find best sequence, agents\nare called problem solving agents. Reflex agents, uses only current percept\n(about to hit a wall). If fully observable, fixed sequence of actions. If not, \nthen branching strategy depending on what it percieves. Path cost must be additive.\nMake tree structure from problem, while frontier isn't empty, use strategy to remove\nand process. Repeating states turn linear to exponential problem. Tree search to \ngraph search, check to see if node visited before adding to queue. Uninformed\nsearch, all non-goal nodes look equally good, else can be ranked using heuristic.\nb:branching-factor, d:depth-of-shallowest goal node, m:max_length_of_any_path.\nUsing DFS, last-in-first-out queue (recurse), not complete, if infinite will go \ndown forever, O(b^m) time O(bm) space since each node keeps its siblings. DFS\nfor space and if path is long, BFS for infinite. Combine best aspect of both, \nDFS with depth limit, time is O(b^l), space O(bl), complete and optimal. When found at \ndepth d, gives O(b^d) and O(bd).\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open loop** - close eyes and go along solutions since it's gauranteed to lead to goal\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "Informed Strategy, uses hints about domain, in form of heuristic function\n",
        "estimates cost frmo state n to goal (h(n)). Greedy best first search, \n",
        "expand node that has lowest heuristic (closest to goal). This is why the \n",
        "algorithm is called “greedy”—on each iteration it tries to get as close to a \n",
        "goal as it can, but greediness can lead to worse results than being careful.\n",
        "With good heuristic, greedy best-first-search O(bm) time. A*, uses f(n) = g(n) + h(n),\n",
        "where g(n) is the cost from initial to n, so f(n) is total estimated cost. The \n",
        "algorithm expands, says \"there may be a lower cost path somewhere else\" to \n",
        "avoid ending with a non-optimal path. Optimal if heuristic is admissible (never \n",
        "overestimates the cost to reach goal, optimistic). Proof by contradiction, take \n",
        "node not in optimal, call it n, say f(n) > C*, since it was not expanded and \n",
        "C* expands the lowest f(n) at a time. Then, f(n) = g(n) + h(n), then =g(n)*+h(n)\n",
        "since assumed n is optimal, then f(n) <= g*(n) + h*(n) = C* as admissible, gives\n",
        "contradiction. Also needs consistency, for node n and successor n', action a,\n",
        "h(n)<=c(n,a,n')+h(n'), triangle inequality. Every consistent heuristic is admissible,\n",
        "but not vice versa. With consistent, no cycles since it would cost more, don't \n",
        "revisit nodes. Cost-optimal is found as long as that path has admissible heuristic.\n",
        "If heuristic never overestimates by more than optimal-second_best, then cost-optimal.\n",
        "TopologicalMap has contours of increasing f(n) costs that don't cross since \n",
        "monotonically increasing. All nodes,n, expanded if f(n)<=C*, until goal is found.\n",
        "Prunes wihtout considering extra branches. Larger heuristic is faster, weight W*h(n)\n",
        "path costs between C*<and<WxC*. Memory split between fronteir and reached states,\n",
        "Can only check frontier for redundant paths, instead of reached since don't U-turn.\n",
        "Beam search limits the size of the frontier. The easiest approach is to keep \n",
        "only the nodes with the best -scores, discarding any other expanded nodes. Also, \n",
        "use iterative A* search. Recursive_best_fs, keep track of best f so far, and \n",
        "only expand if better than that (with back-up value).\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "Effective branching factor b*, total nodes by A* is N, depth d, N+1=1+b*+..(b*)^d.\n",
        "The closer b* to 1, the better. If heuristic dominates other, then it will never \n",
        "expand more nodes. For relaxed problem (less restrictions on actions), use og\n",
        "heuristic. Instead of storing perfect heuristic, which would take O(V^2) space and O(E^3)\n",
        "time, use landmark points, to get h(n) minimum cost to get between landmarks.\n",
        "Differential heuristic, subtract part between precomputed nodes.\n",
        "\n",
        "MISSING INFO ON MORE\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "Uniform-Cost-Search, use priorityQueue with g(n) as the key, sum of costs traversing.\n",
        "WIth BFS, check if goal is when added to frontier. For Uniform, check when expanded, \n",
        "since uniform not sure if lowest until comes out of priQ. Relax constraints, \n",
        "now it is an admissible heuristic. Heuristic 2 dominates heuristic 1 if for every node in \n",
        "search graph, has higher estimate, but still admissible. If we huse h(n)=0, then\n",
        "this admissible but same as uniform-cost-search. Optimal nodes always get\n",
        "expanded first with A*, since their f(n) is always less. Use came_from data \n",
        "structure to keep track of path.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 658
        },
        "cellView": "form",
        "outputId": "de2ef3e2-7444-4913-a512-a980f7ef659f"
      },
      "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": 14,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nInformed Strategy, uses hints about domain, in form of heuristic function\nestimates cost frmo state n to goal (h(n)). Greedy best first search, \nexpand node that has lowest heuristic (closest to goal). This is why the \nalgorithm is called “greedy”—on each iteration it tries to get as close to a \ngoal as it can, but greediness can lead to worse results than being careful.\nWith good heuristic, greedy best-first-search O(bm) time. A*, uses f(n) = g(n) + h(n),\nwhere g(n) is the cost from initial to n, so f(n) is total estimated cost. The \nalgorithm expands, says \"there may be a lower cost path somewhere else\" to \navoid ending with a non-optimal path. Optimal if heuristic is admissible (never \noverestimates the cost to reach goal, optimistic). Proof by contradiction, take \nnode not in optimal, call it n, say f(n) > C*, since it was not expanded and \nC* expands the lowest f(n) at a time. Then, f(n) = g(n) + h(n), then =g(n)*+h(n)\nsince assumed n is optimal, then f(n) <= g*(n) + h*(n) = C* as admissible, gives\ncontradiction. Also needs consistency, for node n and successor n', action a,\nh(n)<=c(n,a,n')+h(n'), triangle inequality. Every consistent heuristic is admissible,\nbut not vice versa. With consistent, no cycles since it would cost more, don't \nrevisit nodes. Cost-optimal is found as long as that path has admissible heuristic.\nIf heuristic never overestimates by more than optimal-second_best, then cost-optimal.\nTopologicalMap has contours of increasing f(n) costs that don't cross since \nmonotonically increasing. All nodes,n, expanded if f(n)<=C*, until goal is found.\nPrunes wihtout considering extra branches. Larger heuristic is faster, weight W*h(n)\npath costs between C*<and<WxC*. Memory split between fronteir and reached states,\nCan only check frontier for redundant paths, instead of reached since don't U-turn.\nBeam search limits the size of the frontier. The easiest approach is to keep \nonly the nodes with the best -scores, discarding any other expanded nodes. Also, \nuse iterative A* search. Recursive_best_fs, keep track of best f so far, and \nonly expand if better than that (with back-up value).\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nEffective branching factor b*, total nodes by A* is N, depth d, N+1=1+b*+..(b*)^d.\nThe closer b* to 1, the better. If heuristic dominates other, then it will never \nexpand more nodes. For relaxed problem (less restrictions on actions), use og\nheuristic. Instead of storing perfect heuristic, which would take O(V^2) space and O(E^3)\ntime, use landmark points, to get h(n) minimum cost to get between landmarks.\nDifferential heuristic, subtract part between precomputed nodes.\n\nMISSING INFO ON MORE\n\n\n## Module 4 Lecture Notes\n \nUniform-Cost-Search, use priorityQueue with g(n) as the key, sum of costs traversing.\nWIth BFS, check if goal is when added to frontier. For Uniform, check when expanded, \nsince uniform not sure if lowest until comes out of priQ. Relax constraints, \nnow it is an admissible heuristic. Heuristic 2 dominates heuristic 1 if for every node in \nsearch graph, has higher estimate, but still admissible. If we huse h(n)=0, then\nthis admissible but same as uniform-cost-search. Optimal nodes always get\nexpanded first with A*, since their f(n) is always less. Use came_from data \nstructure to keep track of path.\n\n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Competitive environments, in which two or more agents have \n",
        "conflicting goals, giving rise to adversarial search problems. Three stances, \n",
        "economy, nondeterministic environment, adversarial game-search-tree. To know\n",
        "who is winning, take heuristic, or avergae all possible continuations. Deterministic,\n",
        "two-player, perfect info (fully observable), zero-sum games (what's good for one\n",
        "is bad for the other). \n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\" Initial state, who's turn, actions, transition model, \n",
        "is-terminal-state, utility-function for terminal states. Gives state space graph, \n",
        "Minimax is utility if terminal state, or max action for MAX, same for MIN. \n",
        "Recursive solution down tree, minimax similar to dfs order, same time and space\n",
        "as dfs. Save space by pruning (alpha-beta). Where beta is the lowest for min\n",
        "and alpha equals that in min. If next min node has a min lower than alpha, skip, \n",
        "vice vera with MAX. Alpha is value of best choice for MAX along the path \n",
        "\"at least\", beta is \"at most\" or the lowest value for MIN. This way examine\n",
        "O(b^m/2) nods if can only examine best first, thus can solve tree twice as deep\n",
        "in same time. Type A strategy considers all possible moves to a certain depth \n",
        "in the search tree, and then uses a heuristic evaluation function to estimate \n",
        "the utility of states at that depth. It explores a wide but shallow portion of \n",
        "the tree. A Type B strategy ignores moves that look bad, and follows promising \n",
        "lines “as far as possible.” It explores a deep but narrow portion of the tree. \"\"\"\n",
        "\n",
        "chapter5_3 = \"\"\" \n",
        "Use heurictic evaluation function to treat nonterminal nodes as terminal, must\n",
        "be between loss and a win. Use expected value of probability win at certain\n",
        "point, or material value of each piece (weighted function for number of pieces).\n",
        "Keep track of depth, and use isCutOff(state,depth). Forward prune moves that seem\n",
        "poor, consider beam search of n best moves at each state.\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "Stochastic games bring us a little closer to the unpredictability of real\n",
        " life by including a random element, such as the throwing of dice. Use \n",
        " expected value of position (expectiminimax value). Use alpha beta by giving range\n",
        " of utility on each node.\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "Decision theory is episodic, immediate, rational agent maximizes expected\n",
        "utility. The performance measure gives a score for a history—a sequence of \n",
        "states. Thus it is applied retrospectively after an agent completes a \n",
        "sequence of actions. The utility function applies to the very next state, \n",
        "so it can be used to guide actions step by step.\n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "For prference, orderability (ranking), transitivity , if A and B then C, \n",
        "continuity (bet so so over good if probability is high enough), substitutability, \n",
        "if A and B are about same, MONOTONICITY: Suppose two lotteries have the same two possible outcomes,A and\n",
        "B. If an agent prefers to , then the agent must prefer the lottery that has a higher probability for A.\n",
        "DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability. \n",
        "Axioms of utility theory.\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "That is, agents with curves of this shape are risk-averse: they prefer a \n",
        "sure thing with a payoff that is less than the expected monetary value of a\n",
        "gamble. On the other hand, in the “desperate” region at large negative wealth,\n",
        "the behavior is risk-seeking. The value an agent will accept in lieu of a \n",
        "lottery is called the certainty equivalent of the lottery. \n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "Evaluation function f that gives numebr for states, that come from terminated\n",
        "states, f>0 better than MAX else for MIN (for chess use material value,\n",
        "for tictactoe use number of ways to win at each state). Don't play hope chess,\n",
        "assuming MIN always chooses their best move. Choose max of all minvalues \n",
        "of successors (for MAX and same with MIN). Alpha, mac's current lower bound on \n",
        "Max's outcome. Beta, upper bound on MIN's outcome. Max wouldn't allow a move worse\n",
        "than alpha. For MAX, if alpha less than v, max won't select it. MAX will never \n",
        "choose a MIN child with beta less than its alpha. You give your beta to parent\n",
        "as alpha if more. Alpha, best option already eplored along path to root for \n",
        "MAX, and beta with MIN. Give power to a dice roll, stochastic game tree, don't\n",
        "know result of action, with unpredictable action by opponent, or nondeterministic\n",
        "action, not guaranteed action. Values are average case outcomes. Compute average\n",
        "scores under optimal, max nodes like minimax, change nodes are like min nodes.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "cf4186d4-9fa5-40c4-c139-1cfb70fad68d"
      },
      "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": 16,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Competitive environments, in which two or more agents have \nconflicting goals, giving rise to adversarial search problems. Three stances, \neconomy, nondeterministic environment, adversarial game-search-tree. To know\nwho is winning, take heuristic, or avergae all possible continuations. Deterministic,\ntwo-player, perfect info (fully observable), zero-sum games (what's good for one\nis bad for the other). \n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Initial state, who's turn, actions, transition model, \nis-terminal-state, utility-function for terminal states. Gives state space graph, \nMinimax is utility if terminal state, or max action for MAX, same for MIN. \nRecursive solution down tree, minimax similar to dfs order, same time and space\nas dfs. Save space by pruning (alpha-beta). Where beta is the lowest for min\nand alpha equals that in min. If next min node has a min lower than alpha, skip, \nvice vera with MAX. Alpha is value of best choice for MAX along the path \n\"at least\", beta is \"at most\" or the lowest value for MIN. This way examine\nO(b^m/2) nods if can only examine best first, thus can solve tree twice as deep\nin same time. Type A strategy considers all possible moves to a certain depth \nin the search tree, and then uses a heuristic evaluation function to estimate \nthe utility of states at that depth. It explores a wide but shallow portion of \nthe tree. A Type B strategy ignores moves that look bad, and follows promising \nlines “as far as possible.” It explores a deep but narrow portion of the tree. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nUse heurictic evaluation function to treat nonterminal nodes as terminal, must\nbe between loss and a win. Use expected value of probability win at certain\npoint, or material value of each piece (weighted function for number of pieces).\nKeep track of depth, and use isCutOff(state,depth). Forward prune moves that seem\npoor, consider beam search of n best moves at each state.\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nStochastic games bring us a little closer to the unpredictability of real\n life by including a random element, such as the throwing of dice. Use \n expected value of position (expectiminimax value). Use alpha beta by giving range\n of utility on each node.\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nDecision theory is episodic, immediate, rational agent maximizes expected\nutility. The performance measure gives a score for a history—a sequence of \nstates. Thus it is applied retrospectively after an agent completes a \nsequence of actions. The utility function applies to the very next state, \nso it can be used to guide actions step by step.\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nFor prference, orderability (ranking), transitivity , if A and B then C, \ncontinuity (bet so so over good if probability is high enough), substitutability, \nif A and B are about same, MONOTONICITY: Suppose two lotteries have the same two possible outcomes,A and\nB. If an agent prefers to , then the agent must prefer the lottery that has a higher probability for A.\nDECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability. \nAxioms of utility theory.\n \n\n## AIMA Chapter 16.3 Utility Functions\n \nThat is, agents with curves of this shape are risk-averse: they prefer a \nsure thing with a payoff that is less than the expected monetary value of a\ngamble. On the other hand, in the “desperate” region at large negative wealth,\nthe behavior is risk-seeking. The value an agent will accept in lieu of a \nlottery is called the certainty equivalent of the lottery. \n \n\n## Module 5 Lecture Notes\n \nEvaluation function f that gives numebr for states, that come from terminated\nstates, f>0 better than MAX else for MIN (for chess use material value,\nfor tictactoe use number of ways to win at each state). Don't play hope chess,\nassuming MIN always chooses their best move. Choose max of all minvalues \nof successors (for MAX and same with MIN). Alpha, mac's current lower bound on \nMax's outcome. Beta, upper bound on MIN's outcome. Max wouldn't allow a move worse\nthan alpha. For MAX, if alpha less than v, max won't select it. MAX will never \nchoose a MIN child with beta less than its alpha. You give your beta to parent\nas alpha if more. Alpha, best option already eplored along path to root for \nMAX, and beta with MIN. Give power to a dice roll, stochastic game tree, don't\nknow result of action, with unpredictable action by opponent, or nondeterministic\naction, not guaranteed action. Values are average case outcomes. Compute average\nscores under optimal, max nodes like minimax, change nodes are like min nodes.\n\n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "Eliminate large portions of search space by using constraints. CSPs deal with \n",
        "assignments of values to variables, that does not violate any constraints is \n",
        "called a consistent or legal assignment. A complete assignment is one \n",
        "in which every variable is assigned a value, and a solution to a CSP is a \n",
        "consistent, complete assignment. \n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "Contraint propogation, use contraints to reduce the number of legal values for \n",
        "variable. Node consistent if all vaues in vairbales domain satisfy unary constraints.\n",
        "Arc-consistent, if every value in domain satisfies binary constriants. AC-3, maintians queue\n",
        "of arcs, initally all arcs in CSP, each binary constraint becomes two arcs in each direction,\n",
        "pop off queue and make Xi arc-consistent to Xj, done in O(cd^3) time since each \n",
        "arc is done in O(d^2) time, d-domain, c-arcs. CSP is k=consistent if for any set\n",
        "of k-1 vars and any assignment, consistent value can always be assigned to kth variable. \n",
        "2-consistency is arc consistency, 1 is node-consistency.\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "Backtracking solution, choose one, try it, if not go back and try next solution.\n",
        "Minimum-remaining-values hauristic, choose variable with least legal values to \n",
        "try out all first. Next, degree heuristic, choose variable involved in largest \n",
        "number of constrains. The least-constraining-value heuristic is effective for \n",
        "this. It prefers the value that rules out the fewest choices for the neighboring\n",
        "variables in the constraint graph. Forward check, assign variable then delete \n",
        "other vairables inconsistent values.\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "Select the value that results in the minimum number of conflicts with other \n",
        "variables—the min-conflicts heuristic. Tabu search: keeping a small list of \n",
        "recently visited states and forbidding the algorithm to return to those states.\n",
        "Local search, use complete state formulation where ech state assigns a value to \n",
        "every variable and search changes value one var at a time.\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "Delete parts that are not in connected component. Tree decomposition, tranform\n",
        "graph into tree so no cycle interference, solvable in O(nd^2) time with \n",
        "TREE-CSP-Solver.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "Identification, assignment to variables. Represent constrinas using declarative\n",
        "language. Genreal purpose search with no changes between problems. Has set of \n",
        "variables X1,X2,... domain of possible labels for each variable {v1,v2,...},\n",
        "finite set of constraints, consistent solution if no violations. Cut off partial\n",
        "solution as soon as possible if we know it won't work. O(d^n) possible assignments\n",
        "for discrete varibales. Then continuous like start/end time for hubble space.\n",
        "Unary SA!=green, binary SA!=WA. May have preferences too. As a search problem,\n",
        "use depth first search with depth n, for n variables as each takes on one val.\n",
        "It has n!d^n leaves, since n*d at each level, and n get's smaller, and we multiply\n",
        "between levels. But is commutative, order of actions not affect outcome, WA red then\n",
        "SA green or other way around, thus tree search not graph search (no cycles). Now \n",
        "b^d leaves, address one variable at a time-call this backtracking search (DFS),\n",
        "backtrack when no legal values left to assign. Improve backtracking, use heuristics\n",
        "to choose which variable to start with. Pick varibale with fewest legal values, MRV\n",
        "fast-fail-method. If tie, choose var with most constraints on remaining variables.\n",
        "Choose least constraining variable (rules out fewest values in remaining). Forward\n",
        "checking, keep track of remaining legal vals for unassigned variables, terminate\n",
        "if variable has no remaining legal vals. Propogates info from assigned vars to \n",
        "vars without assignment. Inferences is constraint propogation, eliminate possible \n",
        "values for varible if value would violate local consistency. Local consistency, \n",
        "node consistency, satisfy unary constraints, and arc consistency, where for Xi\n",
        "every value in domain of i there is a value in domaain of Xj that satisfies constraint.\n",
        "Represent pair in constraint graph with pair of directed arcs. Check for every value\n",
        "in the tail, there is a value in the head that doesn't violate, else remove that\n",
        "value, after each search step do inference, takes O(d^2) since walk through every \n",
        "head and tail value d times, d=size_of_domain. Waltz/Mackworth_Constraint_Prop_Algo,\n",
        "assigne every node set of all possible vlaues, while set of values change, for each\n",
        "node and neighbor, remove any vlaue from i which is not arc consistent. In AC-3,\n",
        "at each iteration only examine Xi where at least one neighbor has lost a value.\n",
        "If Xi loses value because of arc inconsistencies with Yj, don't need to check Xj \n",
        "on next iteration, since removing value can only make it more consistent, thus\n",
        "next iteration only need to check inverse relationship. Worst case, all nodes\n",
        "connected to every other node, O(n^2), or O(d^2) if d values and each arc is \n",
        "only inserted d times, together worst case is O(n^2d^3).\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constraint graph\" : \"CSP with edge as restrictions\",    \n",
        "}\n"
      ],
      "execution_count": 17,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "38433db7-7c0a-43ab-aa71-c723ca307d26"
      },
      "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": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nEliminate large portions of search space by using constraints. CSPs deal with \nassignments of values to variables, that does not violate any constraints is \ncalled a consistent or legal assignment. A complete assignment is one \nin which every variable is assigned a value, and a solution to a CSP is a \nconsistent, complete assignment. \n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nContraint propogation, use contraints to reduce the number of legal values for \nvariable. Node consistent if all vaues in vairbales domain satisfy unary constraints.\nArc-consistent, if every value in domain satisfies binary constriants. AC-3, maintians queue\nof arcs, initally all arcs in CSP, each binary constraint becomes two arcs in each direction,\npop off queue and make Xi arc-consistent to Xj, done in O(cd^3) time since each \narc is done in O(d^2) time, d-domain, c-arcs. CSP is k=consistent if for any set\nof k-1 vars and any assignment, consistent value can always be assigned to kth variable. \n2-consistency is arc consistency, 1 is node-consistency.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nBacktracking solution, choose one, try it, if not go back and try next solution.\nMinimum-remaining-values hauristic, choose variable with least legal values to \ntry out all first. Next, degree heuristic, choose variable involved in largest \nnumber of constrains. The least-constraining-value heuristic is effective for \nthis. It prefers the value that rules out the fewest choices for the neighboring\nvariables in the constraint graph. Forward check, assign variable then delete \nother vairables inconsistent values.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nSelect the value that results in the minimum number of conflicts with other \nvariables—the min-conflicts heuristic. Tabu search: keeping a small list of \nrecently visited states and forbidding the algorithm to return to those states.\nLocal search, use complete state formulation where ech state assigns a value to \nevery variable and search changes value one var at a time.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nDelete parts that are not in connected component. Tree decomposition, tranform\ngraph into tree so no cycle interference, solvable in O(nd^2) time with \nTREE-CSP-Solver.\n \n\n## Module 6 Lecture Notes\n \nIdentification, assignment to variables. Represent constrinas using declarative\nlanguage. Genreal purpose search with no changes between problems. Has set of \nvariables X1,X2,... domain of possible labels for each variable {v1,v2,...},\nfinite set of constraints, consistent solution if no violations. Cut off partial\nsolution as soon as possible if we know it won't work. O(d^n) possible assignments\nfor discrete varibales. Then continuous like start/end time for hubble space.\nUnary SA!=green, binary SA!=WA. May have preferences too. As a search problem,\nuse depth first search with depth n, for n variables as each takes on one val.\nIt has n!d^n leaves, since n*d at each level, and n get's smaller, and we multiply\nbetween levels. But is commutative, order of actions not affect outcome, WA red then\nSA green or other way around, thus tree search not graph search (no cycles). Now \nb^d leaves, address one variable at a time-call this backtracking search (DFS),\nbacktrack when no legal values left to assign. Improve backtracking, use heuristics\nto choose which variable to start with. Pick varibale with fewest legal values, MRV\nfast-fail-method. If tie, choose var with most constraints on remaining variables.\nChoose least constraining variable (rules out fewest values in remaining). Forward\nchecking, keep track of remaining legal vals for unassigned variables, terminate\nif variable has no remaining legal vals. Propogates info from assigned vars to \nvars without assignment. Inferences is constraint propogation, eliminate possible \nvalues for varible if value would violate local consistency. Local consistency, \nnode consistency, satisfy unary constraints, and arc consistency, where for Xi\nevery value in domain of i there is a value in domaain of Xj that satisfies constraint.\nRepresent pair in constraint graph with pair of directed arcs. Check for every value\nin the tail, there is a value in the head that doesn't violate, else remove that\nvalue, after each search step do inference, takes O(d^2) since walk through every \nhead and tail value d times, d=size_of_domain. Waltz/Mackworth_Constraint_Prop_Algo,\nassigne every node set of all possible vlaues, while set of values change, for each\nnode and neighbor, remove any vlaue from i which is not arc consistent. In AC-3,\nat each iteration only examine Xi where at least one neighbor has lost a value.\nIf Xi loses value because of arc inconsistencies with Yj, don't need to check Xj \non next iteration, since removing value can only make it more consistent, thus\nnext iteration only need to check inverse relationship. Worst case, all nodes\nconnected to every other node, O(n^2), or O(d^2) if d values and each arc is \nonly inserted d times, together worst case is O(n^2d^3).\n \n\n## Module 6 Definitions\n* **Constraint graph** - CSP with edge as restrictions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Knowledge-based agents use a process of reasoning over an \n",
        "internal representation of knowledge to decide what actions to take. A knowledge \n",
        "base is a set of sentences. Each sentence is expressed in a language called a \n",
        "knowledge representation language and represents some assertion about the world.\n",
        "When the sentence is taken as being given without being derived from other \n",
        "sentences, we call it an axiom, inference derive new sentence from old. Combine \n",
        "declarative and procedural approach. \n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "Wumpus world, monster, holes, gold, one arrow, climb from square (1,1). Smells\n",
        "stench if next to, see glitter, bump wall, hear scream if kills.\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "Take knowledge base, and keep models that are entailed by predicates, or called\n",
        "model checking. Entailment is the model existing, inference is finding it (called\n",
        "alpha), is a sound procedure. \n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "Literal is either posor noeg atomic sentance ^(and) is conjunction, v(or) is \n",
        "disjunction, =>(implies), <=>(biconditional). Order (not,and,or,implies,bicond).\n",
        "P<=>Q true iff PandQ are both true or both false, P=>Q true unless P is true and\n",
        "Q is false.\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "Modus Ponens, inference rule to derive proof, if alpha=>beta and alpha is given,\n",
        "beta is inferred, And-Elimination, given and statement, can infer either literal.\n",
        "Form is (clause, given)/(output), so (a=>b, a)/(b). Finding a proof can be more \n",
        "efficient because the proof can ignore irrelevant propositions, no matter how\n",
        "many of them there are. Resolution, yields inference algorithm. Combine to get\n",
        "resolvenets. Complementary literatls example of unit resolution, remove one\n",
        "clause from or clause. Combine clauses that are given, and negations cancel out.\n",
        "Conjutive normal form, eliminare <=> but using a=>b^b=>a, eliminate a=>b with\n",
        "!avb(or). DeMorgan, !(a^b)=(!av!b) and !(avb)=(!a^!b). Algorithm, add to resolvents,\n",
        "then closed since contain resolvent of additional clauses.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "Logic based adgent, knowledge based agent, reason over internal representation\n",
        "of knowledge, make informed decision called reasoning. State representation is\n",
        "atomic, and limited (take me to state that's cold as target instead of specific\n",
        "state). Knowledge set of sentences in knowledge representation language with \n",
        "assertions. Axioms, given, derived, new sentences using inferences. Knowledge \n",
        "based agent can either tell something to the KB (infer) and query KB to take\n",
        "some action. Wumpa example, R2D2 can only percieve sensors, doesn't know\n",
        "where it's coming from. Logic, serve as a general class of representations for \n",
        "knowledge based agents, propositional logic. Logic defines semantics of sentence\n",
        "or its meaning. Possible world, or model. Model m satisfies sentence a M(a) or\n",
        "model of a. No pit in (2,2), M is instance where that is true. Entailment, relation\n",
        "that holds between two sentences (logically follows). Propositional logic, W1,3\n",
        "can denote a statement that is true or false. Combine sentences in knowledge base,\n",
        "KB entails certain fact. B entails a iff every model in B is true, then a is true,\n",
        "no pit in 1,2 does not mean no pit in 2,2. Sound, entail only what's derivable,\n",
        "complete, derive all valid entailments. Logically equivalent when a and b are true\n",
        "in same set of models, or a<=>b. Inference rule, a=>b,a/b (given numerator as \n",
        "given sentence, denominator is inferred). Monotonicity, if a is inferred, then\n",
        "KB^a. Apply search to proof, apply rule resolution for complete inference algorithm.\n",
        "Combine clauses, unit resolution, cancel out. Thus, we need to convert every clause\n",
        "to conjust of literals. Conjuctuve Normal Form, bucondition, implication, demorgan,\n",
        "and distribute ands and ors. To show that we can add a to KB, we can say that adding\n",
        "negation is unsatisfiable. Convert (KB^!a)to CNF, apply resolution rule, resolve every\n",
        "pair that contains comlpementary literals, continue until no new clauses, thus not entail\n",
        "a, or get empty clause, so KB does entail a, from our contradiction. Definite clause and\n",
        "Horn clause are close (apply two get one back). Definite clause (rewrite as implication,\n",
        "positive is on right side, negatives are and clauses on left without negative). Horn can use forward and \n",
        "backward chaining algorithm that run in linear. Forward-chaining, pop clause off\n",
        "KB queue, if query we want return true, else for each clause in KB where poppped is in\n",
        "premise for the number of literals in cause c's premise. Backward training, starts with\n",
        "query, try to use KB to arrive to it. \n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"definite clause\":\"which is a disjunction of literals of which exactly one is positive\",\n",
        "\"Horn clause\":\"which is a disjunction of literals of which at most one is positive.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 19,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 971
        },
        "outputId": "2dd14fee-4559-4f63-ff4d-0d80f8e909ce"
      },
      "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": 20,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge-based agents use a process of reasoning over an \ninternal representation of knowledge to decide what actions to take. A knowledge \nbase is a set of sentences. Each sentence is expressed in a language called a \nknowledge representation language and represents some assertion about the world.\nWhen the sentence is taken as being given without being derived from other \nsentences, we call it an axiom, inference derive new sentence from old. Combine \ndeclarative and procedural approach. \n\n\n## AIMA Chapter 7.2 The Wumpus World\n \nWumpus world, monster, holes, gold, one arrow, climb from square (1,1). Smells\nstench if next to, see glitter, bump wall, hear scream if kills.\n\n\n## AIMA Chapter 7.3 Logic\n\nTake knowledge base, and keep models that are entailed by predicates, or called\nmodel checking. Entailment is the model existing, inference is finding it (called\nalpha), is a sound procedure. \n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nLiteral is either posor noeg atomic sentance ^(and) is conjunction, v(or) is \ndisjunction, =>(implies), <=>(biconditional). Order (not,and,or,implies,bicond).\nP<=>Q true iff PandQ are both true or both false, P=>Q true unless P is true and\nQ is false.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nModus Ponens, inference rule to derive proof, if alpha=>beta and alpha is given,\nbeta is inferred, And-Elimination, given and statement, can infer either literal.\nForm is (clause, given)/(output), so (a=>b, a)/(b). Finding a proof can be more \nefficient because the proof can ignore irrelevant propositions, no matter how\nmany of them there are. Resolution, yields inference algorithm. Combine to get\nresolvenets. Complementary literatls example of unit resolution, remove one\nclause from or clause. Combine clauses that are given, and negations cancel out.\nConjutive normal form, eliminare <=> but using a=>b^b=>a, eliminate a=>b with\n!avb(or). DeMorgan, !(a^b)=(!av!b) and !(avb)=(!a^!b). Algorithm, add to resolvents,\nthen closed since contain resolvent of additional clauses.\n\n\n## Module 7 Lecture Notes\n\nLogic based adgent, knowledge based agent, reason over internal representation\nof knowledge, make informed decision called reasoning. State representation is\natomic, and limited (take me to state that's cold as target instead of specific\nstate). Knowledge set of sentences in knowledge representation language with \nassertions. Axioms, given, derived, new sentences using inferences. Knowledge \nbased agent can either tell something to the KB (infer) and query KB to take\nsome action. Wumpa example, R2D2 can only percieve sensors, doesn't know\nwhere it's coming from. Logic, serve as a general class of representations for \nknowledge based agents, propositional logic. Logic defines semantics of sentence\nor its meaning. Possible world, or model. Model m satisfies sentence a M(a) or\nmodel of a. No pit in (2,2), M is instance where that is true. Entailment, relation\nthat holds between two sentences (logically follows). Propositional logic, W1,3\ncan denote a statement that is true or false. Combine sentences in knowledge base,\nKB entails certain fact. B entails a iff every model in B is true, then a is true,\nno pit in 1,2 does not mean no pit in 2,2. Sound, entail only what's derivable,\ncomplete, derive all valid entailments. Logically equivalent when a and b are true\nin same set of models, or a<=>b. Inference rule, a=>b,a/b (given numerator as \ngiven sentence, denominator is inferred). Monotonicity, if a is inferred, then\nKB^a. Apply search to proof, apply rule resolution for complete inference algorithm.\nCombine clauses, unit resolution, cancel out. Thus, we need to convert every clause\nto conjust of literals. Conjuctuve Normal Form, bucondition, implication, demorgan,\nand distribute ands and ors. To show that we can add a to KB, we can say that adding\nnegation is unsatisfiable. Convert (KB^!a)to CNF, apply resolution rule, resolve every\npair that contains comlpementary literals, continue until no new clauses, thus not entail\na, or get empty clause, so KB does entail a, from our contradiction. Definite clause and\nHorn clause are close (apply two get one back). Definite clause (rewrite as implication,\npositive is on right side, negatives are and clauses on left without negative). Horn can use forward and \nbackward chaining algorithm that run in linear. Forward-chaining, pop clause off\nKB queue, if query we want return true, else for each clause in KB where poppped is in\npremise for the number of literals in cause c's premise. Backward training, starts with\nquery, try to use KB to arrive to it. \n\n\n## Module 7 Definitions\n* **Definite clause** - which is a disjunction of literals of which exactly one is positive\n* **Horn clause** - which is a disjunction of literals of which at most one is positive.\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": "2e30a7d8-87fe-470e-be44-13665ea17931"
      },
      "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": 21,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nRationality, doing the right thing. Intelligence, internal through process\nand reasoning (others focus on intelligent behavior). Human v rational (humans\nsometimes act irrational), thought vs behavior. Turing test, ask computer\nquestions, cannot tell if resonse if from person or computer. Need NLP, knowledge \nrepresentation, automated reasoning, and machine learning to learn patterns. Total\nTuring test, includes physical aspect, need computer vision and robotics. Others\nwish to incorporate logic into their work (using premises (knowledge of the \nworld that is certain)). If uncertain, use probability.\"Laws of Thought\", corect \ninferences. The rational-agent approach to AI is more general than \"laws of thought\"\nsince correct inference is one of several parts and easier to build machine models\nof it. The standard model of AI, focused on making agents that do the right thing.\nIn the long run, will need to update standard model since it requires the machine to have a \nfully specified objective.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n \nStrong AI is now human level AI, solve new problems as well as humans. Qualification\nproblem, difficult to capture every contingency of appropriate behavior in a set of \nnecessary and suffiecient logical rules. Good old fashion AI (GOFAI), simple logical \nagent design. Embodied cognition, robotics, vision, and sensors are central to \nAI. Lucas claims machiens are inferior to humans, incompleteness theorem they \ncannot establish the truth of their own Gödel sentence. Three inconsistencies, \nmachine does not need to establish a truth from a sentence (I cannot always \ntell if this sentence is true), no machine can prove something a human can't,\nmachines can change their minds.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \nDoes thinking require a brain, polite convention that everyone thinks. Chinese \nroom, give guy characters and rules, he intelligently translates it, computers\ngenerate no understanding. COnciousness, qualia, awareness of outside world. \n \n\n## AIMA 2.1 Agents and Environments\n \nIn general, an agent’s choice of action at any given instant can depend on its \nbuilt-in knowledge and on the entire percept sequence observed to date, but \nnot on anything it hasn’t perceived. Agent’s behavior is described by the agent \nfunction that maps any given percept sequence to an action. Agent program is what\nactually makes the action happen in the physical system.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nCheck agents actions to scenario, if the reaction sequence is favorable, then \nit performed well. We call this a performance measure. As a general rule, it is\nbetter to design performance measures according to what one actually wants to \nbe achieved in the environment, rather than according to how one thinks the\nagent should behave. Rational depends on 4 things: performance measure that \ndefines the criterion of success, agent’s prior knowledge of the environment,\nthe actions that the agent can perform, and the agent’s percept sequence to date.\nRational maximizes expected performance, while perfection maximizes actual \nperformance. Sometimes random initially because they have nothing to go off of.\n\n\n## AIMA 2.3 The Nature of Environments\n \nNeed to define PEAS for task environment. Example: agent, tutor. Perf: Student \ntest score, Env: set of student, actuators, exercises, speech, Sensors, ears.\nFULLY OBSERVABLE, sensors give access to complete state of envirnoment at each\npoint in time. Fully observable environments are convenient because the agent \nneed not maintain any internal state to keep track of the world. An environment\nmight be PARTIALLY observable because of noisy and inaccurate sensors or\nbecause parts of the state are simply missing from the sensor data. If no data, \nunobservable. Singel vs multiagent, call the other an agent if it is also trying\nto maximize its behavior, competitive vs cooperative. If the next state of the \nenvironment is completely determined by the current state and the action \nexecuted by the agent(s), then we say the environment is deterministic; \notherwise, it is nondeterministic. Taxi driving is clearly nondeterministic \nin this sense, because one can never predict the behavior of traffic\nexactly; moreover, one’s tires may blow out unexpectedly and one’s \nengine may seize up without warning. Schoastic is non-deterministic with \nprobabilities, non-deterministic does not have numbers. Episodic, action does not\ndepend on last episode. Sequential (chess), current action influences future \ndecisions. If envornoment can change, it's dynamic, else it is static. Semidynamic\nif score changes with time (chess and clocks). Discrete (states) vs continuous, \ndriving a car. Known vs unknown, the rules or laws of the envirnoment (card \ngame with cars flipped over). The hardest case is partially observable, \nmultiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n\n\n## AIMA 2.4 The Structure of Agents\n \nAgent=architecture+program. Table approach for lookup actions on environment\nwould mean a huge table. Simple reflex agents select actions on the basis of the\ncurrent percept, ignoring the rest of the percept history (break when car in\nfront breaks), condition-action rule (if x then y). Will work only if the\ncorrect decision can be made on the basis of just the current percept—that \nis, only if the environment is fully observable. Sometimes randomized simple\n reflex agent might outperform a deterministic simple reflex agent, but not \n rational, just useful trick. \n Maintain some sort of internal state that depends on the percept history and \n thereby reflects at least some of the unobserved aspects of the current state.\nUpdating internal state depends on transition model of the world, and sensor\n model for percieving the change, create model-based agent.\n Goal based agent, need goal info, to combine with model.\n Utility-based agent, use utility function with goal for each state. Rationally, \n maximize the expected utility of the action outcomes. \n A learning agent can be divided into four conceptual components, the most \n important distinction is between the learning element, which is responsible \n for making improvements, and the performance element, which is responsible\nfor selecting external actions. The learning element uses feedback from the \ncritic on how the agent is doing and determines how the performance element \nshould be modified to do better in the future. The problem generator is\nresponsible for suggesting actions that will lead to new and informative \nexperiences. Atomic representation each state of the world is indivisible—it \nhas no internal structure. Factored representation splits up each state into a \nfixed set of variables or attributes, each of which can have a value.\n\n\n\n## Module 1 Lecture Notes\n \nAgent percieves envornoment through sensors and acts on environemt through \nactuators, percept is agents percentpual inputs at given instance. Easy solution\nfor agent program, giant table, but exponential in length of P (every possible \nsequence of input). Example, robot, stock market software agent, thermostat,\netc. Consequentialism, evaluate actions by consequences. Use performance measure\nas criterion. Give performance based on what you want to be achieved, not how\nyou want it to behave. Maximize expected value instead of actual value that \nrequires omniscience. Agent function, abstract mathematical description; agent\nprogram, concrete implementation that implements function.\nFully vs Partially observable: chess table vs self driving car\nDeterministic, nondeterministic, stochastic: we know what happens when we choose\nan action and the env is completely knowable, else outcome is uncertain, else \nwe know probabilities for outcomes. \nEpisodic v Sequential : independent not affect future\nStatic v dynamic: if the env changes like car\nDiscrete v Continuous: finite set of actions, state rep is continuous range\nSingle v Multi Agent, game like cross word vs pacman\nIf something else in the environment is trying to optimize something, then it\nis an agent. Hardest is continuous, partially obs, stochastic, multiagent (self\ndriving car). Easy, fully observable, static, deterministic, discrete like chess.\n\n\n## Module 1 Definitions\n* **Introspection** - thinking about your own thoughts\n* **Psychological experiments** - observing person in action\n* **Brain imaging** - observing ht brain\n* **Cognitive science** - brings together computer models from AI and experimental techniques from psychology\n* **Agent** - anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators\n* **Rational agent** - For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure\n* **Limited rationality** - acting appropriately when there is not enough time to do all the computations one might like\n* **Value alignment problem** - the values or objectives put into the machine must be aligned with those of the human.\n* **Percept sequence** -  the complete history of everything the agent has ever perceived\n* **Consequentialism** -  we evaluate an agent’s behavior by its consequences\n* **Information gathering** - Doing actions in order to modify future percepts\n* **Task environments** - problems which rational agents are the solutions\n* **Peas** - Performance, Environment, Actuators, Sensors\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \nAll data are objects (even functions). Garbage collection once unreachable. Every object has a fixed type,\ncant add \"foo\"+2 (strongly typed). Dynamically typed varibales, can change type of var\nby calling type(var) type errors caught at runtime. Concatenate string literals with +,\nimmutable (when modified, makes new string). == checks whether same value,\n'is' checks for same object. Lists are mutable, use y=x[:] to get shallow copy\nof different object with same value.\nTuple is immutable, string is immutable, list is mutable. Using t[1:-1:2] as\nslicing that creates a copy of subsequence.\nFor list, use append, insert, index (get first occurance), count, remove, \nreverse, list.sort(using function), sort(list) to get copy.\nFor strings, split(), join, capitalize, upper, strip.\nDictionary, use hash table, thus key must be immutable. Get KeyError if key\ndoesn't exist. Use .keys(), .values(), .items()\nDefault dictionaries from Collections: defaultdict automatically initializes\nnoexistent dic vals to empty string. For Counter, gives num of occurances.\nFunction, return multiple by using tuple. Python doesn't allow function overloading,\nbut operator overloading is possible with special methods. Give default values\nfor arguments, make them optional. Non-defautl before default, or else syntax error.\nKeyword arguments can be out of order, c=43. Use *args for number of non-keyword\nargs, use as tuple, unpack list using *list for args*. For keyword args, use \n**kwargs with first_name=\"John\" or **my_dict to unpack dictionary. Uses dynamic \nscope, function can use variable defined outside it and get different value on \nupdates. Functions are first class, can be passed into other function, return\nfunction, assign function to variable.\nclass Student(Man):#for subclass man, extends\n    univ=\"Upenn\"#class_attribute\n    def __init__(self,etc.) called when object is instantiated\n      Main.__init__(self, etc.)\n      self.student_name=name\n      super().foo()\nTo redefine a method from subclass, use same name. Magic method, __str__,\nfor printing, also len, copy, cmp, add, neg, __name__ (for main method). Duck typing,\nestablishes suitability of object if it has a method. List comprehension, put in \nbrackets to replace loop [expression for name in list if filter]. Generators are \niterator objects, yeild is the next. Returns yield, starts where it left off.\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nSearch, for sequence of actions that reach goal, called solution. For deterministic\nobservable problem, the solution is always a fixed sequence of actions. A search problem can be defined formally as\na set of possible states that the environment can be in, call this the state space.\nWith initial and goal state. Each action at state is applicable to state. Transition\nmodel describes what each action does, along with action cost function.\n\n\n## AIMA Chapter 3.2 Example Problems\n Touring problems describe a set of locations that must be \nvisited, rather than a single goal destination. The traveling salesperson \nproblem (TSP) is a touring problem in which every city on a map must be \nvisited. The aim is to find a tour with cost < C.\n\n## AIMA Chapter 3.3 Search Algorithms\n The state space describes the (possibly infinite) set of states\nin the world, and the actions that allow transitions from one state to another.\nThe search tree describes paths between these states, reaching towards the \ngoal. The search tree may have multiple paths to (and thus multiple nodes for)\nany given state, but each node in the tree has a unique path back to the root\n(as in all trees).\nBEST FIRST SEARCH - Like BFS where we expand node with least cost. If search\nfor cycles say graph search, else tree-like. \nMeasure performance in 4 ways, Completeness, find solution if there\nis one. Cost Optimal, Time complexity, space complexity.\nFor an implicit state space, complexity can be measured in terms of the depth\nor number of actions in an optimal solution; the maximum number of actions in\nany path; and the branching factor or number of successors of a node that\nneed to be considered. O(b^d) time and space complexity. \n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uniform cost search-Disjkatra's O(b^(d+1)). DFS (B*maxDepth) to O(maxDepth) by\nbacktracking search, only save up to current.\nterative deepening combines many of the benefits of depth-first and breadth-first \nsearch. Like depth-first search, its memory requirements are modest:\nwhen there is a solution, or on finite state spaces with no solution. Like\nbreadth-first search, iterative deepening is optimal for problems where all \nactions have the same cost, and is complete on finite acyclic state spaces, \nor on any finite state space when we check nodes for cycles all the way up the path.\nThe time complexity is when there is a solution, or when there is none. \n\n## Module 3 Lecture Notes\n Search, planning ahead to find best sequence, agents\nare called problem solving agents. Reflex agents, uses only current percept\n(about to hit a wall). If fully observable, fixed sequence of actions. If not, \nthen branching strategy depending on what it percieves. Path cost must be additive.\nMake tree structure from problem, while frontier isn't empty, use strategy to remove\nand process. Repeating states turn linear to exponential problem. Tree search to \ngraph search, check to see if node visited before adding to queue. Uninformed\nsearch, all non-goal nodes look equally good, else can be ranked using heuristic.\nb:branching-factor, d:depth-of-shallowest goal node, m:max_length_of_any_path.\nUsing DFS, last-in-first-out queue (recurse), not complete, if infinite will go \ndown forever, O(b^m) time O(bm) space since each node keeps its siblings. DFS\nfor space and if path is long, BFS for infinite. Combine best aspect of both, \nDFS with depth limit, time is O(b^l), space O(bl), complete and optimal. When found at \ndepth d, gives O(b^d) and O(bd).\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open loop** - close eyes and go along solutions since it's gauranteed to lead to goal\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nInformed Strategy, uses hints about domain, in form of heuristic function\nestimates cost frmo state n to goal (h(n)). Greedy best first search, \nexpand node that has lowest heuristic (closest to goal). This is why the \nalgorithm is called “greedy”—on each iteration it tries to get as close to a \ngoal as it can, but greediness can lead to worse results than being careful.\nWith good heuristic, greedy best-first-search O(bm) time. A*, uses f(n) = g(n) + h(n),\nwhere g(n) is the cost from initial to n, so f(n) is total estimated cost. The \nalgorithm expands, says \"there may be a lower cost path somewhere else\" to \navoid ending with a non-optimal path. Optimal if heuristic is admissible (never \noverestimates the cost to reach goal, optimistic). Proof by contradiction, take \nnode not in optimal, call it n, say f(n) > C*, since it was not expanded and \nC* expands the lowest f(n) at a time. Then, f(n) = g(n) + h(n), then =g(n)*+h(n)\nsince assumed n is optimal, then f(n) <= g*(n) + h*(n) = C* as admissible, gives\ncontradiction. Also needs consistency, for node n and successor n', action a,\nh(n)<=c(n,a,n')+h(n'), triangle inequality. Every consistent heuristic is admissible,\nbut not vice versa. With consistent, no cycles since it would cost more, don't \nrevisit nodes. Cost-optimal is found as long as that path has admissible heuristic.\nIf heuristic never overestimates by more than optimal-second_best, then cost-optimal.\nTopologicalMap has contours of increasing f(n) costs that don't cross since \nmonotonically increasing. All nodes,n, expanded if f(n)<=C*, until goal is found.\nPrunes wihtout considering extra branches. Larger heuristic is faster, weight W*h(n)\npath costs between C*<and<WxC*. Memory split between fronteir and reached states,\nCan only check frontier for redundant paths, instead of reached since don't U-turn.\nBeam search limits the size of the frontier. The easiest approach is to keep \nonly the nodes with the best -scores, discarding any other expanded nodes. Also, \nuse iterative A* search. Recursive_best_fs, keep track of best f so far, and \nonly expand if better than that (with back-up value).\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nEffective branching factor b*, total nodes by A* is N, depth d, N+1=1+b*+..(b*)^d.\nThe closer b* to 1, the better. If heuristic dominates other, then it will never \nexpand more nodes. For relaxed problem (less restrictions on actions), use og\nheuristic. Instead of storing perfect heuristic, which would take O(V^2) space and O(E^3)\ntime, use landmark points, to get h(n) minimum cost to get between landmarks.\nDifferential heuristic, subtract part between precomputed nodes.\n\nMISSING INFO ON MORE\n\n\n## Module 4 Lecture Notes\n \nUniform-Cost-Search, use priorityQueue with g(n) as the key, sum of costs traversing.\nWIth BFS, check if goal is when added to frontier. For Uniform, check when expanded, \nsince uniform not sure if lowest until comes out of priQ. Relax constraints, \nnow it is an admissible heuristic. Heuristic 2 dominates heuristic 1 if for every node in \nsearch graph, has higher estimate, but still admissible. If we huse h(n)=0, then\nthis admissible but same as uniform-cost-search. Optimal nodes always get\nexpanded first with A*, since their f(n) is always less. Use came_from data \nstructure to keep track of path.\n\n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Competitive environments, in which two or more agents have \nconflicting goals, giving rise to adversarial search problems. Three stances, \neconomy, nondeterministic environment, adversarial game-search-tree. To know\nwho is winning, take heuristic, or avergae all possible continuations. Deterministic,\ntwo-player, perfect info (fully observable), zero-sum games (what's good for one\nis bad for the other). \n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Initial state, who's turn, actions, transition model, \nis-terminal-state, utility-function for terminal states. Gives state space graph, \nMinimax is utility if terminal state, or max action for MAX, same for MIN. \nRecursive solution down tree, minimax similar to dfs order, same time and space\nas dfs. Save space by pruning (alpha-beta). Where beta is the lowest for min\nand alpha equals that in min. If next min node has a min lower than alpha, skip, \nvice vera with MAX. Alpha is value of best choice for MAX along the path \n\"at least\", beta is \"at most\" or the lowest value for MIN. This way examine\nO(b^m/2) nods if can only examine best first, thus can solve tree twice as deep\nin same time. Type A strategy considers all possible moves to a certain depth \nin the search tree, and then uses a heuristic evaluation function to estimate \nthe utility of states at that depth. It explores a wide but shallow portion of \nthe tree. A Type B strategy ignores moves that look bad, and follows promising \nlines “as far as possible.” It explores a deep but narrow portion of the tree. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nUse heurictic evaluation function to treat nonterminal nodes as terminal, must\nbe between loss and a win. Use expected value of probability win at certain\npoint, or material value of each piece (weighted function for number of pieces).\nKeep track of depth, and use isCutOff(state,depth). Forward prune moves that seem\npoor, consider beam search of n best moves at each state.\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nStochastic games bring us a little closer to the unpredictability of real\n life by including a random element, such as the throwing of dice. Use \n expected value of position (expectiminimax value). Use alpha beta by giving range\n of utility on each node.\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nDecision theory is episodic, immediate, rational agent maximizes expected\nutility. The performance measure gives a score for a history—a sequence of \nstates. Thus it is applied retrospectively after an agent completes a \nsequence of actions. The utility function applies to the very next state, \nso it can be used to guide actions step by step.\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nFor prference, orderability (ranking), transitivity , if A and B then C, \ncontinuity (bet so so over good if probability is high enough), substitutability, \nif A and B are about same, MONOTONICITY: Suppose two lotteries have the same two possible outcomes,A and\nB. If an agent prefers to , then the agent must prefer the lottery that has a higher probability for A.\nDECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability. \nAxioms of utility theory.\n \n\n## AIMA Chapter 16.3 Utility Functions\n \nThat is, agents with curves of this shape are risk-averse: they prefer a \nsure thing with a payoff that is less than the expected monetary value of a\ngamble. On the other hand, in the “desperate” region at large negative wealth,\nthe behavior is risk-seeking. The value an agent will accept in lieu of a \nlottery is called the certainty equivalent of the lottery. \n \n\n## Module 5 Lecture Notes\n \nEvaluation function f that gives numebr for states, that come from terminated\nstates, f>0 better than MAX else for MIN (for chess use material value,\nfor tictactoe use number of ways to win at each state). Don't play hope chess,\nassuming MIN always chooses their best move. Choose max of all minvalues \nof successors (for MAX and same with MIN). Alpha, mac's current lower bound on \nMax's outcome. Beta, upper bound on MIN's outcome. Max wouldn't allow a move worse\nthan alpha. For MAX, if alpha less than v, max won't select it. MAX will never \nchoose a MIN child with beta less than its alpha. You give your beta to parent\nas alpha if more. Alpha, best option already eplored along path to root for \nMAX, and beta with MIN. Give power to a dice roll, stochastic game tree, don't\nknow result of action, with unpredictable action by opponent, or nondeterministic\naction, not guaranteed action. Values are average case outcomes. Compute average\nscores under optimal, max nodes like minimax, change nodes are like min nodes.\n\n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nEliminate large portions of search space by using constraints. CSPs deal with \nassignments of values to variables, that does not violate any constraints is \ncalled a consistent or legal assignment. A complete assignment is one \nin which every variable is assigned a value, and a solution to a CSP is a \nconsistent, complete assignment. \n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nContraint propogation, use contraints to reduce the number of legal values for \nvariable. Node consistent if all vaues in vairbales domain satisfy unary constraints.\nArc-consistent, if every value in domain satisfies binary constriants. AC-3, maintians queue\nof arcs, initally all arcs in CSP, each binary constraint becomes two arcs in each direction,\npop off queue and make Xi arc-consistent to Xj, done in O(cd^3) time since each \narc is done in O(d^2) time, d-domain, c-arcs. CSP is k=consistent if for any set\nof k-1 vars and any assignment, consistent value can always be assigned to kth variable. \n2-consistency is arc consistency, 1 is node-consistency.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nBacktracking solution, choose one, try it, if not go back and try next solution.\nMinimum-remaining-values hauristic, choose variable with least legal values to \ntry out all first. Next, degree heuristic, choose variable involved in largest \nnumber of constrains. The least-constraining-value heuristic is effective for \nthis. It prefers the value that rules out the fewest choices for the neighboring\nvariables in the constraint graph. Forward check, assign variable then delete \nother vairables inconsistent values.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nSelect the value that results in the minimum number of conflicts with other \nvariables—the min-conflicts heuristic. Tabu search: keeping a small list of \nrecently visited states and forbidding the algorithm to return to those states.\nLocal search, use complete state formulation where ech state assigns a value to \nevery variable and search changes value one var at a time.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nDelete parts that are not in connected component. Tree decomposition, tranform\ngraph into tree so no cycle interference, solvable in O(nd^2) time with \nTREE-CSP-Solver.\n \n\n## Module 6 Lecture Notes\n \nIdentification, assignment to variables. Represent constrinas using declarative\nlanguage. Genreal purpose search with no changes between problems. Has set of \nvariables X1,X2,... domain of possible labels for each variable {v1,v2,...},\nfinite set of constraints, consistent solution if no violations. Cut off partial\nsolution as soon as possible if we know it won't work. O(d^n) possible assignments\nfor discrete varibales. Then continuous like start/end time for hubble space.\nUnary SA!=green, binary SA!=WA. May have preferences too. As a search problem,\nuse depth first search with depth n, for n variables as each takes on one val.\nIt has n!d^n leaves, since n*d at each level, and n get's smaller, and we multiply\nbetween levels. But is commutative, order of actions not affect outcome, WA red then\nSA green or other way around, thus tree search not graph search (no cycles). Now \nb^d leaves, address one variable at a time-call this backtracking search (DFS),\nbacktrack when no legal values left to assign. Improve backtracking, use heuristics\nto choose which variable to start with. Pick varibale with fewest legal values, MRV\nfast-fail-method. If tie, choose var with most constraints on remaining variables.\nChoose least constraining variable (rules out fewest values in remaining). Forward\nchecking, keep track of remaining legal vals for unassigned variables, terminate\nif variable has no remaining legal vals. Propogates info from assigned vars to \nvars without assignment. Inferences is constraint propogation, eliminate possible \nvalues for varible if value would violate local consistency. Local consistency, \nnode consistency, satisfy unary constraints, and arc consistency, where for Xi\nevery value in domain of i there is a value in domaain of Xj that satisfies constraint.\nRepresent pair in constraint graph with pair of directed arcs. Check for every value\nin the tail, there is a value in the head that doesn't violate, else remove that\nvalue, after each search step do inference, takes O(d^2) since walk through every \nhead and tail value d times, d=size_of_domain. Waltz/Mackworth_Constraint_Prop_Algo,\nassigne every node set of all possible vlaues, while set of values change, for each\nnode and neighbor, remove any vlaue from i which is not arc consistent. In AC-3,\nat each iteration only examine Xi where at least one neighbor has lost a value.\nIf Xi loses value because of arc inconsistencies with Yj, don't need to check Xj \non next iteration, since removing value can only make it more consistent, thus\nnext iteration only need to check inverse relationship. Worst case, all nodes\nconnected to every other node, O(n^2), or O(d^2) if d values and each arc is \nonly inserted d times, together worst case is O(n^2d^3).\n \n\n## Module 6 Definitions\n* **Constraint graph** - CSP with edge as restrictions\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge-based agents use a process of reasoning over an \ninternal representation of knowledge to decide what actions to take. A knowledge \nbase is a set of sentences. Each sentence is expressed in a language called a \nknowledge representation language and represents some assertion about the world.\nWhen the sentence is taken as being given without being derived from other \nsentences, we call it an axiom, inference derive new sentence from old. Combine \ndeclarative and procedural approach. \n\n\n## AIMA Chapter 7.2 The Wumpus World\n \nWumpus world, monster, holes, gold, one arrow, climb from square (1,1). Smells\nstench if next to, see glitter, bump wall, hear scream if kills.\n\n\n## AIMA Chapter 7.3 Logic\n\nTake knowledge base, and keep models that are entailed by predicates, or called\nmodel checking. Entailment is the model existing, inference is finding it (called\nalpha), is a sound procedure. \n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\nLiteral is either posor noeg atomic sentance ^(and) is conjunction, v(or) is \ndisjunction, =>(implies), <=>(biconditional). Order (not,and,or,implies,bicond).\nP<=>Q true iff PandQ are both true or both false, P=>Q true unless P is true and\nQ is false.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nModus Ponens, inference rule to derive proof, if alpha=>beta and alpha is given,\nbeta is inferred, And-Elimination, given and statement, can infer either literal.\nForm is (clause, given)/(output), so (a=>b, a)/(b). Finding a proof can be more \nefficient because the proof can ignore irrelevant propositions, no matter how\nmany of them there are. Resolution, yields inference algorithm. Combine to get\nresolvenets. Complementary literatls example of unit resolution, remove one\nclause from or clause. Combine clauses that are given, and negations cancel out.\nConjutive normal form, eliminare <=> but using a=>b^b=>a, eliminate a=>b with\n!avb(or). DeMorgan, !(a^b)=(!av!b) and !(avb)=(!a^!b). Algorithm, add to resolvents,\nthen closed since contain resolvent of additional clauses.\n\n\n## Module 7 Lecture Notes\n\nLogic based adgent, knowledge based agent, reason over internal representation\nof knowledge, make informed decision called reasoning. State representation is\natomic, and limited (take me to state that's cold as target instead of specific\nstate). Knowledge set of sentences in knowledge representation language with \nassertions. Axioms, given, derived, new sentences using inferences. Knowledge \nbased agent can either tell something to the KB (infer) and query KB to take\nsome action. Wumpa example, R2D2 can only percieve sensors, doesn't know\nwhere it's coming from. Logic, serve as a general class of representations for \nknowledge based agents, propositional logic. Logic defines semantics of sentence\nor its meaning. Possible world, or model. Model m satisfies sentence a M(a) or\nmodel of a. No pit in (2,2), M is instance where that is true. Entailment, relation\nthat holds between two sentences (logically follows). Propositional logic, W1,3\ncan denote a statement that is true or false. Combine sentences in knowledge base,\nKB entails certain fact. B entails a iff every model in B is true, then a is true,\nno pit in 1,2 does not mean no pit in 2,2. Sound, entail only what's derivable,\ncomplete, derive all valid entailments. Logically equivalent when a and b are true\nin same set of models, or a<=>b. Inference rule, a=>b,a/b (given numerator as \ngiven sentence, denominator is inferred). Monotonicity, if a is inferred, then\nKB^a. Apply search to proof, apply rule resolution for complete inference algorithm.\nCombine clauses, unit resolution, cancel out. Thus, we need to convert every clause\nto conjust of literals. Conjuctuve Normal Form, bucondition, implication, demorgan,\nand distribute ands and ors. To show that we can add a to KB, we can say that adding\nnegation is unsatisfiable. Convert (KB^!a)to CNF, apply resolution rule, resolve every\npair that contains comlpementary literals, continue until no new clauses, thus not entail\na, or get empty clause, so KB does entail a, from our contradiction. Definite clause and\nHorn clause are close (apply two get one back). Definite clause (rewrite as implication,\npositive is on right side, negatives are and clauses on left without negative). Horn can use forward and \nbackward chaining algorithm that run in linear. Forward-chaining, pop clause off\nKB queue, if query we want return true, else for each clause in KB where poppped is in\npremise for the number of literals in cause c's premise. Backward training, starts with\nquery, try to use KB to arrive to it. \n\n\n## Module 7 Definitions\n* **Definite clause** - which is a disjunction of literals of which exactly one is positive\n* **Horn clause** - which is a disjunction of literals of which at most one is positive.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}