{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Ashok Freitas FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b4ea6738-27c9-41e0-9481-5b6ce23dc02a"
      },
      "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",
        "And more and more and more\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": 19,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 121 words long, so you could write an additional 379 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": "e60e817a-9095-4ca7-cde3-5bc94ee557f3"
      },
      "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": 20,
      "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": 21,
      "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 = \"\"\" Turing test - Can a machine think? Human interrogator questions it, and if it can't tell if it's a machine, it passes. \\n\n",
        "The computer would need the following: \\n\n",
        "natural language processing to communicate successfully in a human language \\n\n",
        "knowledge representation to store what it knows or hears \\n\n",
        "automated reasoning to answer questions and to draw new conclusions \\n\n",
        "machine learning to adapt to new circumstances and to detect and extrapolate patterns \\n\n",
        "Total Turing test - requires interaction with objects and people in the real world, a robot would need: \\n\n",
        "computer vision and speech recognition to perceive the world \\n\n",
        "robotics to manipulate objects and move about \\n\n",
        "The rational agent approach to AI is prevelent, because it is more general than \"laws of thought\" because correct inference is only a part of rationality. \\n\n",
        "Also it is better for scientific developement\\n\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 = \"\"\" Is this another section? \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agents choice of action at any given instant depends on built-in knowledge and \n",
        "the entire percept sequence observed to date. NOT on anything it hasn't percieved. \\n\n",
        "Examples of agents: calculator, auto-sink, autonomous vaccuum. etc.\\n\n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\" How to measure the \"right thing\" for a rational agent to do? \\n\n",
        "Performance measures: AI uses consequentialism: we evaluate an agent’s behavior by its consequences \\n\n",
        "As a general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave. \\n\n",
        "What is rational at any given time depends on four things: \\n\n",
        "1. The performance measure that defines the criteria of success\\n\n",
        "2. The agent's prior knowledge of the environment\\n\n",
        "3. The actionas that the agent can perform\\n\n",
        "4. The agent's percept sequence to date\\n\n",
        "Formal Definition of Rational Agent: For each possible percept sequence, a rational agent should select an action that is expected to\n",
        "maximize its performance measure, given the evidence provided by the percept sequence and\n",
        "whatever built-in knowledge the agent has.\\n\n",
        "OMNICIENCE vs Rationality. An omnicient agent knows the actual outcome of it's actions, rather than checking the state after making a move. Not really possible in reality. \\n\n",
        "Rationality maximizes EXPECTED performance, while perfection maximizes ACTUAL performance.\\n\n",
        "A rational agent should be AUTONOMOUS - it should learn what it can to compensate for partioal or incorrect prior knowledge. An example is a vaccuum that can learn where it is likely to become dirty again.\\n\n",
        "\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "See chart for PEAS examples.\\n\n",
        "Observatility: \\n\n",
        "Fully - if the agent's sensors give it access to complete state of the environment at each point in time (looking at a chess board). Note sensors only take in what is RELEVANT for it's decision.\\n\n",
        "Partially - if the agent cannot see the full picture, examples include inaccurate sensors, or just missing information.\\n\n",
        "Unobservable - if the agent has not sensors at all then the environment is unobservable.\\n\n",
        "SingleAgent vs MultiAgent: \\n\n",
        "SingleAgent - when there is one agent, for example a crossword puzzle.\\n\n",
        "MultiAgent - when there are multiple agents, like playing chess.\\n\n",
        "Distinctions: Does a taxi (an agent) view another vehicle as an object or another agent? The key distinction is whether ’s behavior is best described as maximizing a performance measure whose value depends on agent ’s behavior. \\n\n",
        "That distinction makes things like chess a COMPETETIVE multiagent environment. Whereas another vehicle wants to avoid collisions and so this can be viewed as a COOPERATIVE multiagent environment.\\n\n",
        "Deterministic vs Nondeterministic: If the next state of the environment is completely determined by the current state and the action executed by the agent. Otherwise it's nondeterministic. \\n\n",
        "If it is deterministic and fully observable then the agent doesn't need to worry about uncertainty. BUT if it is partially observable, it may APPEAR nondeterministic.\\n\n",
        "NOTE: some use stochastic as a synonym for nondeterministic, but they aren't the same thing. It is stochastic if it explicitly deals with probabilities, it's nondeterministic if there is no quantifier attached (there's a chance of rain)\\n\n",
        "Episodic vs Sequential:\\n\n",
        "Episodic - if an agent experience is atomic in nature. If for each episode it recieves information then acts. CRUCIALLY, the next episode doesn't depend on the last (like checking for defects)\\n\n",
        "Sequential - Chess is sequential, as the last episode affects the next by changing the board.\\n\n",
        "Static vs Dynamic :\\n\n",
        "Dynamic - if the board can change while the agent is choosing. Like self driving cars.\\n\n",
        "Static - if the board will wait for the move (chess, crossword, etc.)\\n\n",
        "Semidynamic - if the board doesn't change over time but the score does (time limit)\\n\n",
        "Discrete vs Continuous : The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent\\n\n",
        "KNOWN VS. UNKNOWN:\\n\n",
        "Known - outcomes for all actions are given (know the rules)\\n\n",
        "Unknown - if chance is involved or the environment is unkonwn\\n\n",
        "\n",
        "Hardest situation: partially observable, multiagent, nondeterministic, sequential, dynamic,continuous, and unknown\n",
        " \"\"\"\n",
        "chapter2_4 = \"\"\" NOTE: see figures.\\n\n",
        "SIMPLE-REFLEX AGENTS: \\n\n",
        "The simplest kind of agent. Only act on the current percept, ignoring percept history. Simple, small, but limited. \\n\n",
        "Condition-action rule: IF car-in-front-is-braking THEN initiate-braking.\\n\n",
        "Simple agents can be caught in infinite loops, but can break out if actions are RANDOMIZED.\\n\n",
        "MODEL-BASED REFLEX AGENTS:\\n\n",
        "Best way to handle partially-observalbility is for agent to keep track of the part of the world it can see now. Basically storing an internal state.\\n\n",
        "Transition model of the world - knowledge about how the world works.\\n\n",
        "Sensor model - knowledge about things changing in the world that it senses.\\n\n",
        "Model-based agent - an agent that uses the previous models.\\n\n",
        "GOAL-BASED AGENTS: \\n\n",
        "Agents which act in accordance to achieving a goal.\\n\n",
        "Search and planning are subfields of goal based AI.\\n\n",
        "May appear less efficient, but is very flexible, can just change the goal without changing behavior.\\n\n",
        "UTILITY-BASED AGENTS :\\n\n",
        "Agent which maximizes utility (hapiness).\\n\n",
        "Uses a utility function to measure this. Can specify trade-off in conflicting goals, allowing for multiple goals.\\n\n",
        "Maximizes EXPECTED UTILITY as it's not possible to be 100% \\n\n",
        "LEARNING AGENTS: \\n\n",
        "Learning element - responsible for making improvements\\n\n",
        "Performance element - responsible for selecting external actions\\n\n",
        "Critic - feeds info to learning element if it's not doing a good job, and determins how the performance element should be modified\\n\n",
        "Problem generator - responsisble for suggesting actions that will elad to new and informative experiences\\n\n",
        "STATES OF TRANSITION:\\n\n",
        "Atomic - states are indivisible, no internal structure.\\n\n",
        "Factored representation - split up each state into a fixed set of variables or attributes, each with a value.\n",
        "Structured rep - \n",
        "\\\\\n",
        "Formally defined, rational agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n",
        "\\\\\n",
        "PEAS (Performance - what performance do we want to shoot for, Environment - the environment our agent faces, Actuators - how the agent controls it's moves, Sensors - how the agent absorbs information)\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive through sensors and act in an environment via actuators\",\n",
        "\"rational agent\" : \"one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\",\n",
        "\"percept\" : \"the content an agent's sensors are perceiving\",\n",
        "\"percept sequence\" : \"complete history of percepts for the agent\",\n",
        "\"agent function\": \"describes the agent's behavior, it maps any given percept sequence to an action. Abstract mathematical description.\",\n",
        "\"agent program\": \"implements the agent function (not the same). It is concrete implementation, running within some physical system.\",\n",
        "\"consequentialism\": \"we evaluate an agent’s behavior by its consequences\",\n",
        "\"tas environments\": \"the 'problems' that the rational agents are the 'solutions' to \",\n",
        "\"PEAS\": \"see notes\",\n",
        "\"agent architecture\": \"a computing device with physical sensors and actuators (agent = architecture + program)\",\n",
        "\"etc\": \"definitions\",\n",
        "\"etc\": \"definitions\",\n",
        "\"etc\": \"definitions\",\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 22,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "d04a03e9-2b1e-4f78-daba-2414b9b8a140"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Turing test - Can a machine think? Human interrogator questions it, and if it can't tell if it's a machine, it passes. \n\nThe computer would need the following: \n\nnatural language processing to communicate successfully in a human language \n\nknowledge representation to store what it knows or hears \n\nautomated reasoning to answer questions and to draw new conclusions \n\nmachine learning to adapt to new circumstances and to detect and extrapolate patterns \n\nTotal Turing test - requires interaction with objects and people in the real world, a robot would need: \n\ncomputer vision and speech recognition to perceive the world \n\nrobotics to manipulate objects and move about \n\nThe rational agent approach to AI is prevelent, because it is more general than \"laws of thought\" because correct inference is only a part of rationality. \n\nAlso it is better for scientific developement\n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n Is this another section? \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n An agents choice of action at any given instant depends on built-in knowledge and \nthe entire percept sequence observed to date. NOT on anything it hasn't percieved. \n\nExamples of agents: calculator, auto-sink, autonomous vaccuum. etc.\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n How to measure the \"right thing\" for a rational agent to do? \n\nPerformance measures: AI uses consequentialism: we evaluate an agent’s behavior by its consequences \n\nAs a general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave. \n\nWhat is rational at any given time depends on four things: \n\n1. The performance measure that defines the criteria of success\n\n2. The agent's prior knowledge of the environment\n\n3. The actionas that the agent can perform\n\n4. The agent's percept sequence to date\n\nFormal Definition of Rational Agent: For each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has.\n\nOMNICIENCE vs Rationality. An omnicient agent knows the actual outcome of it's actions, rather than checking the state after making a move. Not really possible in reality. \n\nRationality maximizes EXPECTED performance, while perfection maximizes ACTUAL performance.\n\nA rational agent should be AUTONOMOUS - it should learn what it can to compensate for partioal or incorrect prior knowledge. An example is a vaccuum that can learn where it is likely to become dirty again.\n\n\n \n\n## AIMA 2.3 The Nature of Environments\n \nSee chart for PEAS examples.\n\nObservatility: \n\nFully - if the agent's sensors give it access to complete state of the environment at each point in time (looking at a chess board). Note sensors only take in what is RELEVANT for it's decision.\n\nPartially - if the agent cannot see the full picture, examples include inaccurate sensors, or just missing information.\n\nUnobservable - if the agent has not sensors at all then the environment is unobservable.\n\nSingleAgent vs MultiAgent: \n\nSingleAgent - when there is one agent, for example a crossword puzzle.\n\nMultiAgent - when there are multiple agents, like playing chess.\n\nDistinctions: Does a taxi (an agent) view another vehicle as an object or another agent? The key distinction is whether ’s behavior is best described as maximizing a performance measure whose value depends on agent ’s behavior. \n\nThat distinction makes things like chess a COMPETETIVE multiagent environment. Whereas another vehicle wants to avoid collisions and so this can be viewed as a COOPERATIVE multiagent environment.\n\nDeterministic vs Nondeterministic: If the next state of the environment is completely determined by the current state and the action executed by the agent. Otherwise it's nondeterministic. \n\nIf it is deterministic and fully observable then the agent doesn't need to worry about uncertainty. BUT if it is partially observable, it may APPEAR nondeterministic.\n\nNOTE: some use stochastic as a synonym for nondeterministic, but they aren't the same thing. It is stochastic if it explicitly deals with probabilities, it's nondeterministic if there is no quantifier attached (there's a chance of rain)\n\nEpisodic vs Sequential:\n\nEpisodic - if an agent experience is atomic in nature. If for each episode it recieves information then acts. CRUCIALLY, the next episode doesn't depend on the last (like checking for defects)\n\nSequential - Chess is sequential, as the last episode affects the next by changing the board.\n\nStatic vs Dynamic :\n\nDynamic - if the board can change while the agent is choosing. Like self driving cars.\n\nStatic - if the board will wait for the move (chess, crossword, etc.)\n\nSemidynamic - if the board doesn't change over time but the score does (time limit)\n\nDiscrete vs Continuous : The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent\n\nKNOWN VS. UNKNOWN:\n\nKnown - outcomes for all actions are given (know the rules)\n\nUnknown - if chance is involved or the environment is unkonwn\n\n\nHardest situation: partially observable, multiagent, nondeterministic, sequential, dynamic,continuous, and unknown\n \n\n## AIMA 2.4 The Structure of Agents\n NOTE: see figures.\n\nSIMPLE-REFLEX AGENTS: \n\nThe simplest kind of agent. Only act on the current percept, ignoring percept history. Simple, small, but limited. \n\nCondition-action rule: IF car-in-front-is-braking THEN initiate-braking.\n\nSimple agents can be caught in infinite loops, but can break out if actions are RANDOMIZED.\n\nMODEL-BASED REFLEX AGENTS:\n\nBest way to handle partially-observalbility is for agent to keep track of the part of the world it can see now. Basically storing an internal state.\n\nTransition model of the world - knowledge about how the world works.\n\nSensor model - knowledge about things changing in the world that it senses.\n\nModel-based agent - an agent that uses the previous models.\n\nGOAL-BASED AGENTS: \n\nAgents which act in accordance to achieving a goal.\n\nSearch and planning are subfields of goal based AI.\n\nMay appear less efficient, but is very flexible, can just change the goal without changing behavior.\n\nUTILITY-BASED AGENTS :\n\nAgent which maximizes utility (hapiness).\n\nUses a utility function to measure this. Can specify trade-off in conflicting goals, allowing for multiple goals.\n\nMaximizes EXPECTED UTILITY as it's not possible to be 100% \n\nLEARNING AGENTS: \n\nLearning element - responsible for making improvements\n\nPerformance element - responsible for selecting external actions\n\nCritic - feeds info to learning element if it's not doing a good job, and determins how the performance element should be modified\n\nProblem generator - responsisble for suggesting actions that will elad to new and informative experiences\n\nSTATES OF TRANSITION:\n\nAtomic - states are indivisible, no internal structure.\n\nFactored representation - split up each state into a fixed set of variables or attributes, each with a value.\nStructured rep - \n\\\nFormally defined, rational agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n\\\nPEAS (Performance - what performance do we want to shoot for, Environment - the environment our agent faces, Actuators - how the agent controls it's moves, Sensors - how the agent absorbs information)\n\n \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive through sensors and act in an environment via actuators\n* **Rational agent** - one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n* **Percept** - the content an agent's sensors are perceiving\n* **Percept sequence** - complete history of percepts for the agent\n* **Agent function** - describes the agent's behavior, it maps any given percept sequence to an action. Abstract mathematical description.\n* **Agent program** - implements the agent function (not the same). It is concrete implementation, running within some physical system.\n* **Consequentialism** - we evaluate an agent’s behavior by its consequences\n* **Tas environments** - the 'problems' that the rational agents are the 'solutions' to \n* **Peas** - see notes\n* **Agent architecture** - a computing device with physical sensors and actuators (agent = architecture + program)\n* **Etc** - definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "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": "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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "b504ed72-17bd-4805-fa7d-269cd8d8f031"
      },
      "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": 25,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \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",
        "If the correct action is not immediately obvious, an agent may need to PLAN AHEAD, this kind of agent is called a problem-solving agent. \\\\\n",
        "PS agents use ATOMIC representations, world states that are WHOLES, no internal structure visible to PS algorithm \\\\\n",
        "Agents which use factored or structured reps of states are called PLANNING AGENTS \\\\\n",
        "\\\\\n",
        "Process of planning: \\\\\n",
        "GOAL FORUMLATION: adopt a goal (reaching Bucharest)\\\\]\n",
        "PROBLEM FURMULATION: agent devises a description of hte states and actions to reach the goal. A model of the relevant part of the world. (actions of traveling from one city to another, only thing that changes is the current city)\\\\\n",
        "SEARCH: agent simulates actions, searching until it reaches the goal. A goal sequence is called a SOLUTION.\\\\\n",
        "EXECUTION: Agent now takes the actions to reach goal found in search.\\\\\n",
        "Note: in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions (drive to city, then city, then Bucharest)\\\\\n",
        "Once it's found a solution, agent can ignore percepts while executing, because solution is guaranteed to lead to goal. This is called OPEN-LOOP system.\\\\\n",
        "If there is a chance the model is wrong, or environment is nondeterministic (road closed), this is CLOSED-LOOP approach and keep sensons on.\\\\\n",
        "\\\\\n",
        "Search Problem Definition:\\\\\n",
        "A set of possible States the env can take, STATE SPACE\\\\\n",
        "INITIAL STATE where the agent starts\\\\\n",
        "GOAL STATES where the agent wants to go \\\\\n",
        "ACTIONS available, like move or sense. Is defined by current state, so an action is APPLICABLE based on current state (toBucharest is only applicable when cities are 1 away from it)\\\\\n",
        "TRANSITION MODEL describes what each action does. Returns the result from the action \\\\\n",
        "ACTION COST FUNCTION which calcs the cost of each action (dist, energy, etc)\\\\\n",
        "A sequence of actions forms a PATH, and a SOLUTION is a path which reaches the goal. OPTIMAL SOLUTION is a solution which is better than the rest by some measure.\n",
        "The state space can be represented by a GRAPH, so we can search it.\\\\\n",
        "Problem focumation, using ABSTRACTION to take our unnecessary details.\\\\\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "A grid world problem, or vacuum world are examples.\\\\\n",
        "\\\\\n",
        "For a circular robot moving on a flat surface, the space is essentially two-dimensional. When the robot has arms and legs that must also be controlled, \\\\\n",
        "the search space becomes many-dimensional—one dimension for each joint angle.\\\\\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" A search algorithm takes a search problem as input and returns a solution or false.\\\\\n",
        "Can do this by imposing a search tree on the graph, each node is a state sapce.\\\\\n",
        "EXPAND the node by considering available ACTIONS using the RESULT function and generate new nodes for each state.\\\\\n",
        "We explore nodes out of the FRONTIER (a queue). How to decide what to expand next?\\\\\n",
        "BEST FIRST SEARCH:\\\\\n",
        "Choose from the frontier the node n which has the min value of some evaluation function f(n) (see pseudocode 113)\\\\\n",
        "SEARCH DATA STRUCTURES: \\\\\n",
        "Each node can have information associated (node.state, node.parent, node.action, node.path-cost)\\\\\n",
        "Follow the parent from the goal node for the solution (or keep track as you traverse)\n",
        "QUEUES: \\\\\n",
        "Priority queue: assign some evaluation from a function f, sort before taking first out each time\\\\\n",
        "FIFO: first in first out (used in BFS) \\\\\n",
        "LIFO: last in first out (stack) (used in DFS) \\\\\n",
        "\\\\\n",
        "REDUNTANT PATHS: \\\\\n",
        "If you repeat nodes this implies a CYCLE, a REPEATED STATE. \\\\\n",
        "But note that there may be a faster way to get there, so store the faster way.\\\\\n",
        "When it is IMPOSSIBLE to repeat a state, it's space efficient to not store them.\\\\\n",
        "GRAPH SEARCH: if the algorithm checks for redundant paths\\\\\n",
        "TREE-LIKE SEARCH: if it does not check for cycles.\\\\\n",
        "BEST FIRST SEARCH is a graph search.\\\\\n",
        "MEASURING PROBLEM-SOLVING PERFORMANCE:\\\\\n",
        "COST OPTIMALITY: is the path it finds the lowest of all solutions?\\\\\n",
        "TIME COMPLEXITY: is the solution found in relatively good time?\\\\\n",
        "SPACE COMPLEXITY: how much memory does the algo need?\\\\\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" Uninformed search is given no idea how close to goal it is.\\\\\n",
        "BFS: If all actions have same cost, good use of BFS. We implement BFS as a call to Best-First-Search where f(n) is the depth of the node(number of steps to get there). Here we use a FIFO queue\\\\\n",
        "Once we reach the state, we can never find a better solution because it's BFS. (pc 122)\\\\\n",
        "ALWAYS finds a solution with min number of actions.\\\\\n",
        "\\\\\n",
        "DIJKSTRA'S ALGO or UNIFORM-COST SEARCH\\\\\n",
        "Can be implemented as a call to Best-First-Search with Path-Cost as the evaluation function.\\\\\n",
        "Figure 3.10 p 124\\\\\n",
        "Is complete and cost-optimal.\\\\\n",
        "\\\\\n",
        "DEPTH-FIRST SEARCH AND THE PROBLEM OF MEMORY:\\\\\n",
        "DFS always expands the deepst node in the frontier first.\\\\\n",
        "Call Best-First-Search where f is the negative of depth. Does not keep a table of reached states.\\\\\n",
        "For finite state space that are trees it is efficient and complete, but not for acyclic state spaces where it may expand the same state many times but will eventually explore the entire space.\\\\\n",
        "In a cyclic state space, it can get stuck in an infinite loop. And therefore INCOMPLETE.\\\\\n",
        "BUT it's got smaller need for memory, memory complexity of O(bm) where b is branching factor and m is the max depth of the tree.\\\\\n",
        "\\\\\n",
        "DEPTH-LIMITED AND ITERATIVE DEEPENING SEARCH:\\\\\n",
        "Limit the depth of DFS, But if we choose a bad depth, it is INCOMPLETE. (pc 128)\\\\\n",
        "Setting the limit can be done knowing the problem, in the Budapest problem, there are 20 cities, so depth of 19 is good.\\\\\n",
        "ITERATIVE DEEPEINING SEARCH:\\\\\n",
        "If we increase the depth with each call, we can make this complete.\\\\\n",
        "Time complexities 129.\\\\\n",
        "\\\\\n",
        "BIDIRECTIONAL SEARCH:\\\\\n",
        "Simultaneously searches forward from the initial state and backwards from the goal state(s)\\\\\n",
        "Keep track of two frontiers and two tables of reached states (pc 133)\\\\\n",
        "A useful table 134 COMPARING algos\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search, must use atomic rep of world states\", \n",
        "\"planning agent\" : \"agents which plan using factored or structured representations of states (not atomic)\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "fec7f20f-f22f-4c9c-de47-67179dd645cf"
      },
      "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": 27,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nIf the correct action is not immediately obvious, an agent may need to PLAN AHEAD, this kind of agent is called a problem-solving agent. \\\nPS agents use ATOMIC representations, world states that are WHOLES, no internal structure visible to PS algorithm \\\nAgents which use factored or structured reps of states are called PLANNING AGENTS \\\n\\\nProcess of planning: \\\nGOAL FORUMLATION: adopt a goal (reaching Bucharest)\\]\nPROBLEM FURMULATION: agent devises a description of hte states and actions to reach the goal. A model of the relevant part of the world. (actions of traveling from one city to another, only thing that changes is the current city)\\\nSEARCH: agent simulates actions, searching until it reaches the goal. A goal sequence is called a SOLUTION.\\\nEXECUTION: Agent now takes the actions to reach goal found in search.\\\nNote: in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions (drive to city, then city, then Bucharest)\\\nOnce it's found a solution, agent can ignore percepts while executing, because solution is guaranteed to lead to goal. This is called OPEN-LOOP system.\\\nIf there is a chance the model is wrong, or environment is nondeterministic (road closed), this is CLOSED-LOOP approach and keep sensons on.\\\n\\\nSearch Problem Definition:\\\nA set of possible States the env can take, STATE SPACE\\\nINITIAL STATE where the agent starts\\\nGOAL STATES where the agent wants to go \\\nACTIONS available, like move or sense. Is defined by current state, so an action is APPLICABLE based on current state (toBucharest is only applicable when cities are 1 away from it)\\\nTRANSITION MODEL describes what each action does. Returns the result from the action \\\nACTION COST FUNCTION which calcs the cost of each action (dist, energy, etc)\\\nA sequence of actions forms a PATH, and a SOLUTION is a path which reaches the goal. OPTIMAL SOLUTION is a solution which is better than the rest by some measure.\nThe state space can be represented by a GRAPH, so we can search it.\\\nProblem focumation, using ABSTRACTION to take our unnecessary details.\\\n\n\n## AIMA Chapter 3.2 Example Problems\n\nA grid world problem, or vacuum world are examples.\\\n\\\nFor a circular robot moving on a flat surface, the space is essentially two-dimensional. When the robot has arms and legs that must also be controlled, \\\nthe search space becomes many-dimensional—one dimension for each joint angle.\\\n \n\n## AIMA Chapter 3.3 Search Algorithms\n A search algorithm takes a search problem as input and returns a solution or false.\\Can do this by imposing a search tree on the graph, each node is a state sapce.\\EXPAND the node by considering available ACTIONS using the RESULT function and generate new nodes for each state.\\We explore nodes out of the FRONTIER (a queue). How to decide what to expand next?\\BEST FIRST SEARCH:\\Choose from the frontier the node n which has the min value of some evaluation function f(n) (see pseudocode 113)\\SEARCH DATA STRUCTURES: \\Each node can have information associated (node.state, node.parent, node.action, node.path-cost)\\Follow the parent from the goal node for the solution (or keep track as you traverse)\nQUEUES: \\\nPriority queue: assign some evaluation from a function f, sort before taking first out each time\\\nFIFO: first in first out (used in BFS) \\\nLIFO: last in first out (stack) (used in DFS) \\\n\\\nREDUNTANT PATHS: \\\nIf you repeat nodes this implies a CYCLE, a REPEATED STATE. \\\nBut note that there may be a faster way to get there, so store the faster way.\\\nWhen it is IMPOSSIBLE to repeat a state, it's space efficient to not store them.\\\nGRAPH SEARCH: if the algorithm checks for redundant paths\\\nTREE-LIKE SEARCH: if it does not check for cycles.\\\nBEST FIRST SEARCH is a graph search.\\\nMEASURING PROBLEM-SOLVING PERFORMANCE:\\\nCOST OPTIMALITY: is the path it finds the lowest of all solutions?\\\nTIME COMPLEXITY: is the solution found in relatively good time?\\\nSPACE COMPLEXITY: how much memory does the algo need?\\\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uninformed search is given no idea how close to goal it is.\\BFS: If all actions have same cost, good use of BFS. We implement BFS as a call to Best-First-Search where f(n) is the depth of the node(number of steps to get there). Here we use a FIFO queue\\Once we reach the state, we can never find a better solution because it's BFS. (pc 122)\\ALWAYS finds a solution with min number of actions.\\DIJKSTRA'S ALGO or UNIFORM-COST SEARCH\\Can be implemented as a call to Best-First-Search with Path-Cost as the evaluation function.\\Figure 3.10 p 124\\Is complete and cost-optimal.\\DEPTH-FIRST SEARCH AND THE PROBLEM OF MEMORY:\\DFS always expands the deepst node in the frontier first.\\Call Best-First-Search where f is the negative of depth. Does not keep a table of reached states.\\For finite state space that are trees it is efficient and complete, but not for acyclic state spaces where it may expand the same state many times but will eventually explore the entire space.\\In a cyclic state space, it can get stuck in an infinite loop. And therefore INCOMPLETE.\\BUT it's got smaller need for memory, memory complexity of O(bm) where b is branching factor and m is the max depth of the tree.\\DEPTH-LIMITED AND ITERATIVE DEEPENING SEARCH:\\Limit the depth of DFS, But if we choose a bad depth, it is INCOMPLETE. (pc 128)\\Setting the limit can be done knowing the problem, in the Budapest problem, there are 20 cities, so depth of 19 is good.\\ITERATIVE DEEPEINING SEARCH:\\If we increase the depth with each call, we can make this complete.\\Time complexities 129.\\BIDIRECTIONAL SEARCH:\\Simultaneously searches forward from the initial state and backwards from the goal state(s)\\Keep track of two frontiers and two tables of reached states (pc 133)\\A useful table 134 COMPARING algos\n\n \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search, must use atomic rep of world states\n* **Planning agent** - agents which plan using factored or structured representations of states (not atomic)\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 = \"\"\" Using heuristics to more effectively search.\\\\\n",
        "h(n) = estimated cost of the cheapest path from the state at node n to a goal state\\\\\n",
        "For example, using straight line distance from current state to goal to estimate how good the node is.\\\\\n",
        "\\\\\n",
        "GREEDY BEST-FIRST SEARCH:\\\\\n",
        "A form of best-first-search where you choose the lowest h(n) to expand next (of the avialalbe nodes). So the evaluation function is f(n) = h(n). Using a priority queue.\n",
        "Is COMPLETE in FINITE SPACES, but not in INFINITE SPACES. \\\\\n",
        "Worst case time and space complexity is O(|V|). With a good heuristic, we can reduce that, as far as O(bm)\\\\\n",
        "\\\\\n",
        "A* SEARCH:\\\\\n",
        "Best-First-Search type search where:\\\\\n",
        "f(n) = g(n) + h(n)\\\\\n",
        "That is, f(n) is the distance already traveled plus the distance to the goal.\\\\\n",
        "Or in general terms, cost already paid plus the heuristic cost to the goal.\\\\\n",
        "Can be written as: \\\\\n",
        "f(n) = estimated cost of the best path that continues from n to a goal\\\\\n",
        "This algo is COMPLETE.\\\\\n",
        "If the heuristic is good enough it is cost-optimal, but if not it CAN not be.\\\\\n",
        "The heuristic must be admissible and then A* is cost-optimal.\\\\\n",
        "Every consistent heuristic is admissible (BUT NOT VICE VERSA)\\\\\n",
        "It should be clear that as you extend a path, the costs are monotonic: the path cost always increases as you go along a path, because action costs are always positive. \\\\\n",
        "But note that a path might contribute several nodes in a row with the same score; this will happen whenever the decrease in is exactly equal to the action cost just taken (for \\\\\n",
        "example, in a grid problem, when is in the same row as the goal and you take a step towards the goal, is increased by 1 and is decreased by 1)\\\\\n",
        "\\\\\n",
        "A* is efficient because it prunes away search tree nodes that aren't necessary for an optimal solution. (never checks nodes farther away from the goal than current)\\\\\n",
        "A drawback is that the number of nodes expanded can be exponential in the length of the solution.\\\\\n",
        "\\\\\n",
        "SATISFICING SEARCH:\\\\\n",
        "If we let A* use an inadmissible heuristic (one that overestimates) it may miss the optimal solution, but can be more accurate and therefore expand fewer nodes.\\\\\n",
        "WEIGHTED A* SEARCH:\\\\\n",
        "f(n) = g(n) + W × h(n), W > 1.\\\\\n",
        "Here the heuristic is weighted more than the cost already taken.\\\\\n",
        "A good table 147\\\\\n",
        "Bounded searches 147\\\\\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "EFFECT OF HEURISTIC ACCURACY ON PERFORMANCE:\\\\\n",
        "EFFECTIVE BRANCHING FACTOR B*: the total nodes generated by A* for a particular problem is N and the solution depth is d, but b* is the branching factor that a uniform tree of depth d would have in order to contain N+1 nodes:\\\\\n",
        "N+1 = 1 + b* + (b*)^2 + ... + (b*)^d//\n",
        "For example, if A* finds a solution at depth 5 using 52 nodes, then b* = 1.92.\\\\\n",
        "A good heuristic would have a b* value close to 1.\\\\\n",
        "Korf and Reid 159.\\\\\n",
        "\\\\\n",
        "GENERATING HEURISTICS FROM RELAXED PROBLEMS:\\\\\n",
        "A problem with fewer restrictions on the actions is called a RELAXED PROBLEM.\\\\\n",
        "State space of a relaxed problem is a SUPERGRAPH because there are more options with fewer rules.\\\\\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\\\\\n",
        "ex of relaxed 162.\\\\\n",
        "we can have h(n) = max{h1(n), … , hk(n)}.\\\\\n",
        "Which can choose the best heuristic for the node in question.\\\\\n",
        "Since all hi are admissible then h(n) is also admissible, and h dominates all of it's component heuristics. BUT it takes longert to compute. \n",
        "DISJOINT PATTERN DATABASES 165\\\\\n",
        "\\\\\n",
        "GENERATING HEURISTICS WITH LANDMARKS:\\\\\n",
        "Can quicken finding solutions by precomputing some optimal path costs. It may be time consuming but only needs to be done once.\\\\\n",
        "Choose a few LANDMARK POINTS we compute C*(v,L) for vertices v. formula 166.\\\\\n",
        "If the path happens to go through the landmark, it is admissible but otherwise it overestimates the cost.\\\\\n",
        "DIFFERENTIAL HEURISTIC: think of it as a landmark beyond the goal, if the goal is on the path to the landmark, then we just subtract from the goal to n.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "\n",
        "MEMORY BOUNDED SEARCH:\\\\\n",
        "Saving nodes not in two places (fronteir and reached)\\\\\n",
        "So we can only store in 1 place.\\\\\n",
        "Or we could remove from reached when we know for usre it istn' part of the solution.\\\\\n",
        "BEAM SEARCH:\\\\\n",
        "Discard nodes from the fronteir which aren't good enough.\\\\\n",
        "Keep the k nodes with the best f-scores.\\\\\n",
        "\\\\\n",
        "ITERATIVE-DEEPENING A* SEARCH(IDA*):\\\\\n",
        "IDA* gives us the benefits of A* without the requirement to keep all reached states in memory, at a cost of visiting some states multiple times. \\\\\n",
        "Here the cutoff is not depth, but f-cost(g+h) at each iteration. \\\\\n",
        "RECURSIVE BEST-FIRST SEARCH (RBFS):\\\\\n",
        "attempts to mimic the operation of standard best-first search, but using only linear space\n",
        "It uses an f-limit variable to keep track of the f-value of the best ALTERNATIVE path avialbale from any ancestor of the current node.\\\\\n",
        "SO it doesn't DFS to the last node, it goes up to the next best chance of being a good path node. (pc 151)\\\\\n",
        "\\\\\n",
        "Use all memory: \n",
        "Two algorithms that do this are MA* (memory-bounded A*) and SMA* (simplified MA*)\\\\\n",
        "SMA* proceeds just like A*, expanding the best leaf until memory is full. At this point, it cannot add a new node to the search tree without dropping an old one. SMA* always drops the worst leaf node—the one with the highest f-value\\\\\n",
        "\\\\\n",
        "BIDIRECTIONAL HEURISTIC SEARCH: \\\\\n",
        "155 \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissible heuristic\" : \"is one that never overestimates the cost to reach a goal\",    \n",
        "\"consistency\" : \"for every node and every successor of generated by an action we have: h(n) ≤ c(n, a, n′) + h(n′)\",\n",
        "\"triangle inequality\" : \"which stipulates that a side of a triangle cannot be longer than the sum of the other two sides\",\n",
        "\"manhattan distance\" : \"city block distance, how many rows and columns out of place (rather than euclidean distance)\",\n",
        "\"dominates\" : \"h2 dominates h1 if A* using h2 will never expand more nodes than if it used h1\",\n",
        "\"metalevel state space\" : \"definition\",\n",
        "\"concept\" : \"definition\",\n",
        "\"concept\" : \"definition\",\n",
        "\"concept\" : \"definition\",\n",
        "\"concept\" : \"definition\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1a21c39a-187c-4640-c0ba-f1137ac4d3db"
      },
      "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\", module3_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": 29,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Using heuristics to more effectively search.\\h(n) = estimated cost of the cheapest path from the state at node n to a goal state\\For example, using straight line distance from current state to goal to estimate how good the node is.\\GREEDY BEST-FIRST SEARCH:\\A form of best-first-search where you choose the lowest h(n) to expand next (of the avialalbe nodes). So the evaluation function is f(n) = h(n). Using a priority queue.\nIs COMPLETE in FINITE SPACES, but not in INFINITE SPACES. \\\nWorst case time and space complexity is O(|V|). With a good heuristic, we can reduce that, as far as O(bm)\\\n\\\nA* SEARCH:\\\nBest-First-Search type search where:\\\nf(n) = g(n) + h(n)\\\nThat is, f(n) is the distance already traveled plus the distance to the goal.\\\nOr in general terms, cost already paid plus the heuristic cost to the goal.\\\nCan be written as: \\\nf(n) = estimated cost of the best path that continues from n to a goal\\\nThis algo is COMPLETE.\\\nIf the heuristic is good enough it is cost-optimal, but if not it CAN not be.\\\nThe heuristic must be admissible and then A* is cost-optimal.\\\nEvery consistent heuristic is admissible (BUT NOT VICE VERSA)\\\nIt should be clear that as you extend a path, the costs are monotonic: the path cost always increases as you go along a path, because action costs are always positive. \\\nBut note that a path might contribute several nodes in a row with the same score; this will happen whenever the decrease in is exactly equal to the action cost just taken (for \\\nexample, in a grid problem, when is in the same row as the goal and you take a step towards the goal, is increased by 1 and is decreased by 1)\\\n\\\nA* is efficient because it prunes away search tree nodes that aren't necessary for an optimal solution. (never checks nodes farther away from the goal than current)\\\nA drawback is that the number of nodes expanded can be exponential in the length of the solution.\\\n\\\nSATISFICING SEARCH:\\\nIf we let A* use an inadmissible heuristic (one that overestimates) it may miss the optimal solution, but can be more accurate and therefore expand fewer nodes.\\\nWEIGHTED A* SEARCH:\\\nf(n) = g(n) + W × h(n), W > 1.\\\nHere the heuristic is weighted more than the cost already taken.\\\nA good table 147\\\nBounded searches 147\\\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \nEFFECT OF HEURISTIC ACCURACY ON PERFORMANCE:\\\nEFFECTIVE BRANCHING FACTOR B*: the total nodes generated by A* for a particular problem is N and the solution depth is d, but b* is the branching factor that a uniform tree of depth d would have in order to contain N+1 nodes:\\\nN+1 = 1 + b* + (b*)^2 + ... + (b*)^d//\nFor example, if A* finds a solution at depth 5 using 52 nodes, then b* = 1.92.\\\nA good heuristic would have a b* value close to 1.\\\nKorf and Reid 159.\\\n\\\nGENERATING HEURISTICS FROM RELAXED PROBLEMS:\\\nA problem with fewer restrictions on the actions is called a RELAXED PROBLEM.\\\nState space of a relaxed problem is a SUPERGRAPH because there are more options with fewer rules.\\\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\\\nex of relaxed 162.\\\nwe can have h(n) = max{h1(n), … , hk(n)}.\\\nWhich can choose the best heuristic for the node in question.\\\nSince all hi are admissible then h(n) is also admissible, and h dominates all of it's component heuristics. BUT it takes longert to compute. \nDISJOINT PATTERN DATABASES 165\\\n\\\nGENERATING HEURISTICS WITH LANDMARKS:\\\nCan quicken finding solutions by precomputing some optimal path costs. It may be time consuming but only needs to be done once.\\\nChoose a few LANDMARK POINTS we compute C*(v,L) for vertices v. formula 166.\\\nIf the path happens to go through the landmark, it is admissible but otherwise it overestimates the cost.\\\nDIFFERENTIAL HEURISTIC: think of it as a landmark beyond the goal, if the goal is on the path to the landmark, then we just subtract from the goal to n.\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Admissible heuristic** - is one that never overestimates the cost to reach a goal\n* **Consistency** - for every node and every successor of generated by an action we have: h(n) ≤ c(n, a, n′) + h(n′)\n* **Triangle inequality** - which stipulates that a side of a triangle cannot be longer than the sum of the other two sides\n* **Manhattan distance** - city block distance, how many rows and columns out of place (rather than euclidean distance)\n* **Dominates** - h2 dominates h1 if A* using h2 will never expand more nodes than if it used h1\n* **Metalevel state space** - definition\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "Considering multi-agent environments, we could think of them as :\\\\\n",
        "An economy, thinking of it as aggregate.\\\\\n",
        "Consider adversarial agents as part of the environment, but we miss the idea that they are trying to defeat us.\\\\\n",
        "Third, model adversarial agents with techniques of adversarial game-tree search.\\\\\n",
        "\\\\\n",
        "TWO-PLAYER ZERO-SUM GAMES:\\\\\n",
        "Most studied within AI are deterministic, two-player, turn-based, perfect info, zero-sum games.\\\\\n",
        "This means it's fully observable, and what's good for one player is bad for another.\\\\\n",
        "Game tree for tic-tac-toe 184.\\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "Max must have a conditional plan (plan for mins move)\\\\\n",
        "Use MiniMax search for this.\\\\\n",
        "We do this assuming that min plays optimally, if they dont' then max will do at least as well as it would against an optimal player. NOT necessarily the best play/best score.\\\\\n",
        "\\\\\n",
        "MINIMAX SEARCH ALGO:\\\\\n",
        "Recursive algo that goes to the leaves and backs up the values to the root. (pc 188)\\\\\n",
        "Essentially a full DFS of the game tree.\\\\\n",
        "If depth of tree is m and there are b legal moves at each point, time complexity is O(b^m), space = O(bm)(if algo gen all actions at once) or O(m) if gen actions one at a time.\\\\\n",
        "\\\\\n",
        "OPTIMAL DECISIONS IN MULTIPLYAER GAMES:\\\\\n",
        "Get an array back with utility values for each player. The backed up value of node n is utility vector of best move for player moving at n.\\\\\n",
        "\\\\\n",
        "ALPHA-BETA PRUNING:\\\\\n",
        "minimax is exponential time complexity, no algo can eliminate the expo, but can prune some hopefully.\\\\\n",
        "Prune parts of tree which have no chance of being chosen. 191 diagram\\\\\n",
        "Alpha = value of best (highest value) choice we've found on the path for max, a = \"at least\"\\\\\n",
        "Beta = value of best (lowest value) choice on path for min. The most that min will allow max to get if we take that path. b = \"at most\"\\\\\n",
        "PS 194 (see note)\\\\\n",
        "\\\\\n",
        "MOVE DEPENDENT:\\\\\n",
        "How good pruning is depends on order we examine nodes, sometimes does nothing, best case done in O(b^(m/2)) instead of O(b^m)\\\\\n",
        "With random move ordering we get roughly O(b^(3m/4))\\\\\n",
        "We can give priorities to improve move ordering (chess first capture, then threats, then move...)\\\\\n",
        "Can also limit by PLY, first go one PLY deep, then use that to determine which to explore next, so on\\\\\n",
        "TRANSPOSITION TABLE, caches heuristic value of states.  it is possible to come back to same state, storing it makes everything faster 196.\\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "We can cut off at a certain point by treating nonterminal nodes as terminal nodes and using an evaluation function\\\\\n",
        "We use a cutoff test to evaluate the node when it is deemed as terminal, in other worst at the depth we want.\\\\\n",
        "The evaluation function returns an estimate of the expected utility of state s for player p.\\\\\n",
        "For nonterninal nodes the evaluation is somewhere between a loss and a win.\\\\\n",
        "For chess, this evaluation function could be the number of pieces each player has, with weights for the different pieces.\\\\\n",
        "\\\\\n",
        "CUTTING OFF SEARCH:\\\\\n",
        "if game.Is-Cutoff(state,depth) then return game.Eval(state,player),null \\\\\n",
        "\\\\\n",
        "FORWARD PRUNING:\\\\\n",
        "prunes moves that appear to be poor moves, but might possibly be good ones.\\\\\n",
        "So saves computation time but risks making a mistake.\\\\\n",
        "One approach is BEAM SEARCH on each ply, consider only a beam of the n best moves. Can still prune the best move.\\\\\n",
        "ProbCut prunes cuts that are probably outside the window. 205\\\\\n",
        "LATE MOVE REDUCTION: assumes that move ordering has been done well, so late moves are bad moves.\\\\\n",
        "\\\\\n",
        "SEARCH VS LOOKUP:\\\\\n",
        "Can use lookup for things like early game (don't want to search a billion options just to move a pawn). \\\\\n",
        "End game too, but must be manually programmed or learned and stored. This is where the computer has an edge.\\\\\n",
        "Can solve endgame by producing POLICY: mapping from every possible state to the best move in that state.\\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "Doesn't have heuristic search eval function.\\\\\n",
        "INstead, it averages the estimated utility of simulations of complete games from that state.\\\\\n",
        "How to choose how to play? Uses a playout policy which biases towards good moves.\\\\\n",
        "PURE monte carlo search, do N simulations from current state, track which possible moves from current state has highest win percent.\\\\\n",
        "Not always sufficient, need SELECTION POLICTY, which balances EXPLORATION of states that have had few playouts, and EPLOITATION of states that have done well in the past.\\\\\n",
        "SEE SELECTION, EXPANSION, SIMULATION, BACK-PROPAGATION 210\\\\\n",
        "One effective selection policy UCT, ranks possible move based on UCB1 (upper confidence bound formula see 211)\\\\\n",
        "Algo 213\\\\\n",
        "May want to use EARLY PLAYOUT TERMINATION where we stop playouts that take too many moves.\\\\\n",
        "Drawback: if a single move can change the course of the game, because it may not consider that move.\\\\\n",
        "\\\\\n",
        "STOCHASTIC GAMES:\\\\\n",
        "games with random element (luck and chance)\\\\\n",
        "Must include CHANCE NODES then, in addition to max and min nodes.\\\\\n",
        "So we can only calculate EXPECTED VALUE of a position: the average over all possible outcomes of the chance nodes.\\\\\n",
        "EXPECTIMINIMAX VALUE: 218 \\\\\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "DECISION-THEROETIC AGENT: agent that can make rational decisions based on what it believes and wants.\\\\\n",
        "Instead of goal agent (good = goal / bad =non-goal), DTA will evaluate on a continous range.\\\\\n",
        "MAXIMUM EXPECTED UTILITY(MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility \\\\\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "SIX CONSTRAINTS: known as the AXIOMS OF UTILITY THEORY\\\\\n",
        "ORDERABILITY: given any two lotteries, the agent must prefer one OR hold them equal (355)\\\\\n",
        "TRANSITIVITY: if A > B and B > C then A > C\\\\\n",
        "CONTINUITY: see 355\\\\\n",
        "SUBSTITUTABILITY: if agent finds two lotteries equal, subbing them in a more complex lottery the agent will find those equal too.\\\\\n",
        "MONOTONACITY: two lotteries with the same outcomes, A and B. If agent prefers A > B, then it chooses lottery with higher prob of getting A.\\\\\n",
        "DECOMPOSABILITY: Complex lottereis can be reduced using laws of probability (ex 356)\\\\\n",
        "\\\\\n",
        "From the axioms we can derive:\\\\\n",
        "EXISTENCE OF UTILITY FUNCTION: if agent prefers obey axioms and A > B then there is a utility function U where U(A) > U(B). Vice versa and same for equals.\\\\\n",
        "EXPECTED UTILITY OF A LOTTERY: Utility of a lottery is sum of prob of each outcome times utility of the outcome (expected value basically)\\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "Come back to?\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"define game\" : \"182 see chart\",   \n",
        "\"utility function\" : \"defines the final numeric value player p can expect when game ends\",\n",
        "\"UCT\" : \"upper confidence bounds applied to trees\",\n",
        "\"concept\" : \"definition\",\n",
        "\"concept\" : \"definition\",\n",
        "\"concept\" : \"definition\",\n",
        "\"concept\" : \"definition\", \n",
        "}\n",
        "\n"
      ],
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6224627a-0637-49e5-f618-ce8dcd4b5924"
      },
      "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": 31,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nConsidering multi-agent environments, we could think of them as :\\\nAn economy, thinking of it as aggregate.\\\nConsider adversarial agents as part of the environment, but we miss the idea that they are trying to defeat us.\\\nThird, model adversarial agents with techniques of adversarial game-tree search.\\\n\\\nTWO-PLAYER ZERO-SUM GAMES:\\\nMost studied within AI are deterministic, two-player, turn-based, perfect info, zero-sum games.\\\nThis means it's fully observable, and what's good for one player is bad for another.\\\nGame tree for tic-tac-toe 184.\\\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nMax must have a conditional plan (plan for mins move)\\\nUse MiniMax search for this.\\\nWe do this assuming that min plays optimally, if they dont' then max will do at least as well as it would against an optimal player. NOT necessarily the best play/best score.\\\n\\\nMINIMAX SEARCH ALGO:\\\nRecursive algo that goes to the leaves and backs up the values to the root. (pc 188)\\\nEssentially a full DFS of the game tree.\\\nIf depth of tree is m and there are b legal moves at each point, time complexity is O(b^m), space = O(bm)(if algo gen all actions at once) or O(m) if gen actions one at a time.\\\n\\\nOPTIMAL DECISIONS IN MULTIPLYAER GAMES:\\\nGet an array back with utility values for each player. The backed up value of node n is utility vector of best move for player moving at n.\\\n\\\nALPHA-BETA PRUNING:\\\nminimax is exponential time complexity, no algo can eliminate the expo, but can prune some hopefully.\\\nPrune parts of tree which have no chance of being chosen. 191 diagram\\\nAlpha = value of best (highest value) choice we've found on the path for max, a = \"at least\"\\\nBeta = value of best (lowest value) choice on path for min. The most that min will allow max to get if we take that path. b = \"at most\"\\\nPS 194 (see note)\\\n\\\nMOVE DEPENDENT:\\\nHow good pruning is depends on order we examine nodes, sometimes does nothing, best case done in O(b^(m/2)) instead of O(b^m)\\\nWith random move ordering we get roughly O(b^(3m/4))\\\nWe can give priorities to improve move ordering (chess first capture, then threats, then move...)\\\nCan also limit by PLY, first go one PLY deep, then use that to determine which to explore next, so on\\\nTRANSPOSITION TABLE, caches heuristic value of states.  it is possible to come back to same state, storing it makes everything faster 196.\\\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nWe can cut off at a certain point by treating nonterminal nodes as terminal nodes and using an evaluation function\\\nWe use a cutoff test to evaluate the node when it is deemed as terminal, in other worst at the depth we want.\\\nThe evaluation function returns an estimate of the expected utility of state s for player p.\\\nFor nonterninal nodes the evaluation is somewhere between a loss and a win.\\\nFor chess, this evaluation function could be the number of pieces each player has, with weights for the different pieces.\\\n\\\nCUTTING OFF SEARCH:\\\nif game.Is-Cutoff(state,depth) then return game.Eval(state,player),null \\\n\\\nFORWARD PRUNING:\\\nprunes moves that appear to be poor moves, but might possibly be good ones.\\\nSo saves computation time but risks making a mistake.\\\nOne approach is BEAM SEARCH on each ply, consider only a beam of the n best moves. Can still prune the best move.\\\nProbCut prunes cuts that are probably outside the window. 205\\\nLATE MOVE REDUCTION: assumes that move ordering has been done well, so late moves are bad moves.\\\n\\\nSEARCH VS LOOKUP:\\\nCan use lookup for things like early game (don't want to search a billion options just to move a pawn). \\\nEnd game too, but must be manually programmed or learned and stored. This is where the computer has an edge.\\\nCan solve endgame by producing POLICY: mapping from every possible state to the best move in that state.\\\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nDoesn't have heuristic search eval function.\\\nINstead, it averages the estimated utility of simulations of complete games from that state.\\\nHow to choose how to play? Uses a playout policy which biases towards good moves.\\\nPURE monte carlo search, do N simulations from current state, track which possible moves from current state has highest win percent.\\\nNot always sufficient, need SELECTION POLICTY, which balances EXPLORATION of states that have had few playouts, and EPLOITATION of states that have done well in the past.\\\nSEE SELECTION, EXPANSION, SIMULATION, BACK-PROPAGATION 210\\\nOne effective selection policy UCT, ranks possible move based on UCB1 (upper confidence bound formula see 211)\\\nAlgo 213\\\nMay want to use EARLY PLAYOUT TERMINATION where we stop playouts that take too many moves.\\\nDrawback: if a single move can change the course of the game, because it may not consider that move.\\\n\\\nSTOCHASTIC GAMES:\\\ngames with random element (luck and chance)\\\nMust include CHANCE NODES then, in addition to max and min nodes.\\\nSo we can only calculate EXPECTED VALUE of a position: the average over all possible outcomes of the chance nodes.\\\nEXPECTIMINIMAX VALUE: 218 \\\n\n\n\n\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nDECISION-THEROETIC AGENT: agent that can make rational decisions based on what it believes and wants.\\\nInstead of goal agent (good = goal / bad =non-goal), DTA will evaluate on a continous range.\\\nMAXIMUM EXPECTED UTILITY(MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility \\\n\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nSIX CONSTRAINTS: known as the AXIOMS OF UTILITY THEORY\\\nORDERABILITY: given any two lotteries, the agent must prefer one OR hold them equal (355)\\\nTRANSITIVITY: if A > B and B > C then A > C\\\nCONTINUITY: see 355\\\nSUBSTITUTABILITY: if agent finds two lotteries equal, subbing them in a more complex lottery the agent will find those equal too.\\\nMONOTONACITY: two lotteries with the same outcomes, A and B. If agent prefers A > B, then it chooses lottery with higher prob of getting A.\\\nDECOMPOSABILITY: Complex lottereis can be reduced using laws of probability (ex 356)\\\n\\\nFrom the axioms we can derive:\\\nEXISTENCE OF UTILITY FUNCTION: if agent prefers obey axioms and A > B then there is a utility function U where U(A) > U(B). Vice versa and same for equals.\\\nEXPECTED UTILITY OF A LOTTERY: Utility of a lottery is sum of prob of each outcome times utility of the outcome (expected value basically)\\\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nCome back to?\n\n \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Define game** - 182 see chart\n* **Utility function** - defines the final numeric value player p can expect when game ends\n* **Uct** - upper confidence bounds applied to trees\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",
        "CSP consists of three componnets, X, D, C:\\\\\n",
        "X is set of variables {X1,...,Xn}\\\\\n",
        "D is a set of domains, {D1,...,Dn}, one for each variable\\\\\n",
        "C is a set of contraints that specify allowable combinations of values\\\\\n",
        "A domain Di consists of allowable values {v1,...,Vk} for variable Xi\\\\\n",
        "Ex, a boolean variable would have domain {true, false}\\\\\n",
        "CSPs deal with asssignments of values to variables, {Xi = vi, Xj = vj,...}\\\\\n",
        "If it doesn't violate a constraint it is CONSISTENT.\\\\\n",
        "a COMPLETE ASSIGNMENT is when every var is assigned avalue.\\\\\n",
        "a SOLUTION to a CSP is a consisten, complete assignment.\\\\\n",
        "a PARTIAL ASSIGNMENT leaves some variables unassigned, and a PARTIAL SOLUTION isa partial assignemtn that is consisten.\\\\\n",
        "EX, MAP COLORING 233\\\\\n",
        "WHy formulate as CSP, 225.\\\\\n",
        "PRECEDENCE CONSTRAINGS:\\\\\n",
        "When a task must occur before another task, and a task takes a duration d1, we say:\\\\\n",
        "T1 + d1 <= T2\\\\\n",
        "DISJUNCTIVE CONSTRAINT: saying that the time's of these tasks cannot overlap:\\\\\n",
        "(AxleF + 10 ≤ AxleB) or (AxleB + 10 ≤ AxleF)\n",
        "If problem is Discrete, and Finite, then we can use tuples of variables.\\\\\n",
        "If not, we must use constraints.\\\\\n",
        "CONTINUOUS DOMAINS problems are studied in the real world (allocating time for hubble telescope)\\\\\n",
        "//\n",
        "CONSTRAINTS:\\\\\n",
        "UNARY CONSTRAING: restricts value of single variable\\\\\n",
        "BINARY CONSTRAINT: SA != NSW\\\\\n",
        "a BINARY CSP is one with only unary and binary constraints (constraint graph)\\\\\n",
        "HIGHER ORDER CONSTRAINTS:\\\\\n",
        "⟨(X,Y ,Z),X < Y < Z or X > Y > Z⟩\\\\\n",
        "GLOBAL CONSTRAINT: involving arbitrary number of vars(ex. Alldiff, where all vars must be diff values 230)\\\\\n",
        "PREFERENCE VS ABSOLUTE CONSTRAINTS: absolute must happen, preferences don't\\\\\n",
        "Can encode this with costs for variable assignments\\\\\n",
        "Maximizing preferences in this way is a CONSTRAINT OPTIMAZATION PROBLEM(COP)\\\\\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "CONSTRAINT PROPAGATION: using constraints to limit the legal values for a var, which trickles to other vars\\\\\n",
        "Can either do this within search, or before you start searching\\\\\n",
        "\\\\\n",
        "NODE CONSISTENCY:\\\\\n",
        "A variable is node-consistent if all values in it's domain satisfy it's UNARY constraints (legal values)\\\\\n",
        "Note: easy to change n-ary constraints to unary\\\\\n",
        "Can do this before starting solving process.\\\\\n",
        "\\\\\n",
        "ARC CONSISTENCY:\\\\\n",
        "a var is arc-consistent if EVERY value in it's domain satisfies the variable's BINARY constraint\\\\\n",
        "Think sudoku, a cell is arc-consistent if no other cell in grid, row, or column has same value\\\\\n",
        "\\\\\n",
        "AC-3:\\\\\n",
        "maintains a queue of arcs to considedr, starts with all arcs\\\\\n",
        "Checks if the arc is consistent, if it is, we move one\\\\\n",
        "if it isn't, we add back to the queue all arcs going to the outgoing arc we examined (pc 236)\\\\\n",
        "\\\\\n",
        "PATH CONSISTENCY:\\\\\n",
        "tightens binary constraints by using implicit constraints that are inferred by looking at triples of variables.\\\\\n",
        "adding a third restraint into the binary constraints\\\\\n",
        "\\\\\n",
        "K-CONSISTENCY:\\\\\n",
        "  A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consisten value can always be assigned to any kth variable.\\\\\n",
        "  1-consistency is node consistency, 2 consistency is arc consistency, and 3 consistency is path consistency.\\\\\n",
        "  Any algorithm for establishing n-consistency is exponential in time and space!\\\\\n",
        "\\\\\n",
        "GLOBAL CONSTRAINTS\\\\\n",
        "RESOURCE CONSTRAINT: or AtMost constraint. Used in scheduling problems.\\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "pc 244\\\\\n",
        "VARIABLE AND VALUE ORDERING:\\\\\n",
        "How to choose what variable to set next?\\\\\n",
        "MINIMUM REMAINING VALUES heuristic: choose variable with fewest \"legal\" moves (smallest domain). This is fail first\\\\\n",
        "DEGREE HEURISTIC: choosing the variable that is involved in the most constraints on other unassigned variables.\\\\\n",
        "Now the variable is chosen, which value to try first?\n",
        "LEAST CONSTRAINING VALUE: prefers value that rules out fewest choices of neighbors in the constraint graph. Keep as many options open as possible. This is fail-last\\\\\n",
        "\\\\\n",
        "INTERLEAVING SEARCH AND INFERENCE:\\\\\n",
        "Inference is powerful during search (as AC-3 is before search)\\\\\n",
        "Every time we inference, we can run AC-3 again and make real progress.\\\\\n",
        "FORWARD CHECKING: when we assign X, if there is an arc X->Y, take out value of X from domain of all Y (diag 248)\\\\\n",
        "FC doesn't catch all inconsistencies because it doesn't look forward enough. Could put you down a path which makes the puzzle impossible.\\\\\n",
        "\\\\\n",
        "INTELLIGENT BACKTRACKING: LOOKING BACKWARD:\\\\\n",
        "CHONOLOGICAL BACKTRACKING: when a search branch fails, it goes up to the previous level and tries another value (most recent)\\\\\n",
        "Can be inefficient as it goes up to levels that may not affect other regions (recoloring Tazmania)\\\\\n",
        "Say we fail in SA, we want to backtrack to a variable when changed could solve our SA problem. SO we keep track of a set of assignments that are in conflict with some value of SA.\\\\\n",
        "for instance,{Q = red,NSW = green,V = blue} (called teh CONFLICT SET)\\\\\n",
        "Then we backjump to most recent assignment in the set.\\\\\n",
        "DOn't need to backjump because forward checking will prune paths that require it\\\\\n",
        "251 conf(Xi) ← conf(Xi) ∪ conf(Xj) − {Xi}.\\\\\n",
        "\\\\\n",
        "CONSTRAINT LEARNING:\\\\\n",
        "idea of finding min set of vars from conflict set that causes the problem.\\\\\n",
        "Call that set a NO-GOOD\\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "Local search algorithms are good at solving many CSPs.\\\\\n",
        "pc 254\\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "Independent solutions can be found by finding connected components of the contraint graph.(tasmania vs mainland)\\\\\n",
        "dividing a Boolean CSP with 100 variables into four subproblems reduces the worst-case solution time from the lifetime of the universe down to less than a second\n",
        "but completely independent problems are rare. \\\\\n",
        "But other structures are found, like trees (if two variables are connected by only one path), and any tree-structured CSP is linear time complexity.\\\\\n",
        "DIRECTIONAL ARC CONSISTENCY(DAC): X1,X2,...,Xn if Xi is arc consistent with each Xj j>i\\\\\n",
        "use topo sort to do this (257)\\\\\n",
        "Can reduce time to O(nd^2) where d is possible domain values for two variables\n",
        "graph and pc 258\\\\\n",
        "\\\\\n",
        "CUTSET CONDITIONING:\\\\\n",
        "If we don't have a tree, we can sometimes prune nodes to make one (259)\\\\\n",
        "1: choose subset S of CSP such that removing S leave you with a tree, S is called a CYCLE CUTSET\\\\\n",
        "2: FOR each assignment to variables in S that satisfies constraints on S:\\\\\n",
        "  a. remove from domain of remaining vars those vars set in S\\\\\n",
        "  b. if remaining CSP has solution, return together with assignment of S\\\\\n",
        "If cycle cutset is size c, total runtime is O(d^c * (n - c)d^2).\\\\\n",
        "We need to try all variations of solutions for S, so that is d^c combinations, then solve a tree of size (n-c)\\\\\n",
        "NOTE: finding smallest cycle cutset is NP-Hard, but approx algos are known. called CUTSET CONDITIONING\\\\\n",
        "\\\\\n",
        "TREE DECOMPOSITION:\\\\\n",
        "sECOND WAY TO REDUCE CONSTRAINT GRAPH\\\\\n",
        "Transform the original graph into a tree where each node is a set of variables(graph 261)\\\\\n",
        "Once we have the tree-structured graph, we can get solution in O(nd^2) time, where n is number of tree nodes and d is size of largest domain (a domain here is a set of tuples).\\\\\n",
        "\\\\\n",
        "VALUE SYMETRY:\\\\\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0a36edd4-7b52-4670-b5f7-19fcc5f79626"
      },
      "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": 33,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSP consists of three componnets, X, D, C:\\\nX is set of variables {X1,...,Xn}\\\nD is a set of domains, {D1,...,Dn}, one for each variable\\\nC is a set of contraints that specify allowable combinations of values\\\nA domain Di consists of allowable values {v1,...,Vk} for variable Xi\\\nEx, a boolean variable would have domain {true, false}\\\nCSPs deal with asssignments of values to variables, {Xi = vi, Xj = vj,...}\\\nIf it doesn't violate a constraint it is CONSISTENT.\\\na COMPLETE ASSIGNMENT is when every var is assigned avalue.\\\na SOLUTION to a CSP is a consisten, complete assignment.\\\na PARTIAL ASSIGNMENT leaves some variables unassigned, and a PARTIAL SOLUTION isa partial assignemtn that is consisten.\\\nEX, MAP COLORING 233\\\nWHy formulate as CSP, 225.\\\nPRECEDENCE CONSTRAINGS:\\\nWhen a task must occur before another task, and a task takes a duration d1, we say:\\\nT1 + d1 <= T2\\\nDISJUNCTIVE CONSTRAINT: saying that the time's of these tasks cannot overlap:\\\n(AxleF + 10 ≤ AxleB) or (AxleB + 10 ≤ AxleF)\nIf problem is Discrete, and Finite, then we can use tuples of variables.\\\nIf not, we must use constraints.\\\nCONTINUOUS DOMAINS problems are studied in the real world (allocating time for hubble telescope)\\\n//\nCONSTRAINTS:\\\nUNARY CONSTRAING: restricts value of single variable\\\nBINARY CONSTRAINT: SA != NSW\\\na BINARY CSP is one with only unary and binary constraints (constraint graph)\\\nHIGHER ORDER CONSTRAINTS:\\\n⟨(X,Y ,Z),X < Y < Z or X > Y > Z⟩\\\nGLOBAL CONSTRAINT: involving arbitrary number of vars(ex. Alldiff, where all vars must be diff values 230)\\\nPREFERENCE VS ABSOLUTE CONSTRAINTS: absolute must happen, preferences don't\\\nCan encode this with costs for variable assignments\\\nMaximizing preferences in this way is a CONSTRAINT OPTIMAZATION PROBLEM(COP)\\\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nCONSTRAINT PROPAGATION: using constraints to limit the legal values for a var, which trickles to other vars\\\nCan either do this within search, or before you start searching\\\n\\\nNODE CONSISTENCY:\\\nA variable is node-consistent if all values in it's domain satisfy it's UNARY constraints (legal values)\\\nNote: easy to change n-ary constraints to unary\\\nCan do this before starting solving process.\\\n\\\nARC CONSISTENCY:\\\na var is arc-consistent if EVERY value in it's domain satisfies the variable's BINARY constraint\\\nThink sudoku, a cell is arc-consistent if no other cell in grid, row, or column has same value\\\n\\\nAC-3:\\\nmaintains a queue of arcs to considedr, starts with all arcs\\\nChecks if the arc is consistent, if it is, we move one\\\nif it isn't, we add back to the queue all arcs going to the outgoing arc we examined (pc 236)\\\n\\\nPATH CONSISTENCY:\\\ntightens binary constraints by using implicit constraints that are inferred by looking at triples of variables.\\\nadding a third restraint into the binary constraints\\\n\\\nK-CONSISTENCY:\\\n  A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consisten value can always be assigned to any kth variable.\\\n  1-consistency is node consistency, 2 consistency is arc consistency, and 3 consistency is path consistency.\\\n  Any algorithm for establishing n-consistency is exponential in time and space!\\\n\\\nGLOBAL CONSTRAINTS\\\nRESOURCE CONSTRAINT: or AtMost constraint. Used in scheduling problems.\\\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \npc 244\\\nVARIABLE AND VALUE ORDERING:\\\nHow to choose what variable to set next?\\\nMINIMUM REMAINING VALUES heuristic: choose variable with fewest \"legal\" moves (smallest domain). This is fail first\\\nDEGREE HEURISTIC: choosing the variable that is involved in the most constraints on other unassigned variables.\\\nNow the variable is chosen, which value to try first?\nLEAST CONSTRAINING VALUE: prefers value that rules out fewest choices of neighbors in the constraint graph. Keep as many options open as possible. This is fail-last\\\n\\\nINTERLEAVING SEARCH AND INFERENCE:\\\nInference is powerful during search (as AC-3 is before search)\\\nEvery time we inference, we can run AC-3 again and make real progress.\\\nFORWARD CHECKING: when we assign X, if there is an arc X->Y, take out value of X from domain of all Y (diag 248)\\\nFC doesn't catch all inconsistencies because it doesn't look forward enough. Could put you down a path which makes the puzzle impossible.\\\n\\\nINTELLIGENT BACKTRACKING: LOOKING BACKWARD:\\\nCHONOLOGICAL BACKTRACKING: when a search branch fails, it goes up to the previous level and tries another value (most recent)\\\nCan be inefficient as it goes up to levels that may not affect other regions (recoloring Tazmania)\\\nSay we fail in SA, we want to backtrack to a variable when changed could solve our SA problem. SO we keep track of a set of assignments that are in conflict with some value of SA.\\\nfor instance,{Q = red,NSW = green,V = blue} (called teh CONFLICT SET)\\\nThen we backjump to most recent assignment in the set.\\\nDOn't need to backjump because forward checking will prune paths that require it\\\n251 conf(Xi) ← conf(Xi) ∪ conf(Xj) − {Xi}.\\\n\\\nCONSTRAINT LEARNING:\\\nidea of finding min set of vars from conflict set that causes the problem.\\\nCall that set a NO-GOOD\\\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nLocal search algorithms are good at solving many CSPs.\\\npc 254\\\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n \nIndependent solutions can be found by finding connected components of the contraint graph.(tasmania vs mainland)\\\ndividing a Boolean CSP with 100 variables into four subproblems reduces the worst-case solution time from the lifetime of the universe down to less than a second\nbut completely independent problems are rare. \\\nBut other structures are found, like trees (if two variables are connected by only one path), and any tree-structured CSP is linear time complexity.\\\nDIRECTIONAL ARC CONSISTENCY(DAC): X1,X2,...,Xn if Xi is arc consistent with each Xj j>i\\\nuse topo sort to do this (257)\\\nCan reduce time to O(nd^2) where d is possible domain values for two variables\ngraph and pc 258\\\n\\\nCUTSET CONDITIONING:\\\nIf we don't have a tree, we can sometimes prune nodes to make one (259)\\\n1: choose subset S of CSP such that removing S leave you with a tree, S is called a CYCLE CUTSET\\\n2: FOR each assignment to variables in S that satisfies constraints on S:\\\n  a. remove from domain of remaining vars those vars set in S\\\n  b. if remaining CSP has solution, return together with assignment of S\\\nIf cycle cutset is size c, total runtime is O(d^c * (n - c)d^2).\\\nWe need to try all variations of solutions for S, so that is d^c combinations, then solve a tree of size (n-c)\\\nNOTE: finding smallest cycle cutset is NP-Hard, but approx algos are known. called CUTSET CONDITIONING\\\n\\\nTREE DECOMPOSITION:\\\nsECOND WAY TO REDUCE CONSTRAINT GRAPH\\\nTransform the original graph into a tree where each node is a set of variables(graph 261)\\\nOnce we have the tree-structured graph, we can get solution in O(nd^2) time, where n is number of tree nodes and d is size of largest domain (a domain here is a set of tuples).\\\n\\\nVALUE SYMETRY:\\\n\n \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "Knowledge base = KB = set of sentences which hold information about the world.\\\\\n",
        "If it is given to the agent it is called an axiom\\\\\n",
        "Can start with BACKGROUND KNOWLEDGE\\\\\n",
        "When an agent program is called:\n",
        "  1. TELLS the KB what it percieves\n",
        "  2. ASKS the KB what action it should perform\n",
        "  3. Agent program TELLS the KB what action it chose, and returns the action to be executed\n",
        "DECLARATIVE approach to system building is starting with empty KB and TELL sentences until agent can operate in the system\\\\\n",
        "PROCEDURAL approach encodes desired behaviors as program code\\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "def 278\\\\\n",
        "pretty straight forward\n",
        "\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "ENTAILMENT between sentences: when a sentence follows logically from another sentence or KB\\\\\n",
        "α ⊨ β\\\\\n",
        "α ⊨ β if and only if M(α) ⊆ M(β) \\\\\n",
        "where M is the model(world) we are working with\\\\\n",
        "if α ⊨ β then a is a STRONGER assertion than B, it rules out MORE possible worlds\\\\\n",
        "ex. x = 0 entails xy = 0 as it doesn't matter the value of y xy will always equal 0\\\\\n",
        "Good model 287.\\\\\n",
        "In every model where KB is true, a1 is also true, so KB ⊨ α1\\\\\n",
        "In some models in which KB is true, a2 is false, so KB does not entail a2 (and the agent cannot conclude whatever a2 puts forth)\\\\\n",
        "if an inference algorithm can derive from , we write:\\\\\n",
        "KB ⊢i α \\\\\n",
        "which is pronounced “ is derived from by ” or “ derives from .”\\\\\n",
        "Inference algo that derives only entailed sentences is SOUND or TRUTH-PRESERVING.\\\\\n",
        "It is COMPLETE if it can derive any sentence that is entailed from the KB\\\\\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "Use symbols for wompus world: P, Q, R, W1,3, FacingEast...\\\\\n",
        "Prop symbols with fixed meaning are true and false.\\\\\n",
        "COMPLEX SENTENCES are constructed from simple sentences, with parentheses and logical connectives\\\\\n",
        "see sheet294\\\\\n",
        "TT 296\\\\\n",
        "\\\\\n",
        "A SIMPLE KB:\\\\\n",
        "Px,y is true if there is a pit in [x,y] etc.\\\\\n",
        "Some sentences are true in all wompus worlds (or all similar worlds as they state teh rules):\n",
        "R2 : B1,1 ⇔ (P1,2 ∨ P2,1) \\\\\n",
        "R3 : B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1) \\\\\n",
        "We know that \\\\\n",
        "R1 : NOT B1,1\\\\\n",
        "so there is no pit in 1,2 or 2,1\n",
        "R4 : NOT P1,2\\\\\n",
        "R5 : NOT P2,1\\\\\n",
        "\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "LOGICAL EQUIVALENCE: two sentences are LE if they are true in the same set of models.\\\\\n",
        "α ≡ β if and only if α ⊨ β and β ⊨ α\\\\\n",
        "301 implications\\\\\n",
        "a sentence is VALID if it is true in ALL models\\\\\n",
        "For any sentences and , if and only if the sentence is valid.\\\\\n",
        "SATISFYABILITY:\\\\\n",
        "A SETNENCE IS SATISFIABLE IF IT IS TRUE OR SATISFIED BY some MODELS\\\\\n",
        "The SAT problem was the first NP-Complete\\\\\n",
        "\\\\\n",
        "INFERENCE AND PROOFS:\\\\\n",
        "MODUS PONENS:\\\\\n",
        "α ⇒ β, α\n",
        "_____\n",
        "β\n",
        "\\\\\n",
        "a implies b an a is given, then we can infer b\\\\\n",
        "AND ELIMINATION:\\\\\n",
        "α ∧ β\n",
        "___\n",
        "α\n",
        "If a and b, then definitely a, or definitely b. Ex WumpusAhead AND WumpusAlive, then WUMPUS alive can be inferred.\\\\\n",
        "α ⇔ β            ||        (α ⇒ β) ∧ (β ⇒ α)\n",
        "___\n",
        "(α ⇒ β) ∧ (β ⇒ α)         ||          α ⇔ β\n",
        "\n",
        "305 show how wecan get to NO pit in 2,1 and 1,2\\\\\n",
        "\n",
        "MONOTONACITY:\\\\\n",
        "if KB ⊨ α then KB ∧ β ⊨ α \n",
        "Anding B to KB doesn't change that a is inferred. because we are increasing the KB.\\\\\n",
        "This does work logically, as we couldn't infer a if there is some information out there (b) that could invalidate it, so once it's inferred it's inferred.\\\\\n",
        "\\\\\n",
        "RESOLUTION RULE:\n",
        "P1 OR P2 or P3, NOT P2\n",
        "___\n",
        "P1 OR P3\\\\\n",
        "You can resolve only 1 pair of complementary literals at a time.\\\\\n",
        "\\\\\n",
        "CONJUNCTIVE NORMAL FORM\\\\\n",
        "Resolution rule applies only to clauses, so we need to reduce complex sentences to clauses\\\\\n",
        "Theorem Proving 2 310\\\\\n",
        "\\\\\n",
        "A RESOLUTION ALGO:\\\\\n",
        "That is, to show that , we show that (KB ∧ ¬α) is unsatisfiable\\\\\n",
        "The algo (pc 312):\\\\\n",
        "  1. converts to CNF\n",
        "  2. Resolves complementary literals until\\\\\n",
        "    a. there are no new clauses (can't resolve anymore) in which case KB does not ientail a\n",
        "    b. two clauses resolve to give us the EMPTY clause, in which case KB entails a\n",
        "\n",
        "DEFINITE CLAUSE:\\\\\n",
        "Disjunction of literals with EXACTLY ONE positive:\\\\\n",
        "(¬L1,1 ∨ ¬Breeze ∨ B1,1)\\\\\n",
        "HORN CLAUSE:\\\\\n",
        "Has AT MOST ONE positive\\\\\n",
        "GOAL CLAUSES:\\\\\n",
        "NO POSITIVE literals.\\\\\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "2ad082b1-0932-4ee1-c3ff-226bdc237618"
      },
      "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": 35,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nKnowledge base = KB = set of sentences which hold information about the world.\\\nIf it is given to the agent it is called an axiom\\\nCan start with BACKGROUND KNOWLEDGE\\\nWhen an agent program is called:\n  1. TELLS the KB what it percieves\n  2. ASKS the KB what action it should perform\n  3. Agent program TELLS the KB what action it chose, and returns the action to be executed\nDECLARATIVE approach to system building is starting with empty KB and TELL sentences until agent can operate in the system\\\nPROCEDURAL approach encodes desired behaviors as program code\\\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \ndef 278\\\npretty straight forward\n\n\n\n## AIMA Chapter 7.3 Logic\n \nENTAILMENT between sentences: when a sentence follows logically from another sentence or KB\\\nα ⊨ β\\\nα ⊨ β if and only if M(α) ⊆ M(β) \\\nwhere M is the model(world) we are working with\\\nif α ⊨ β then a is a STRONGER assertion than B, it rules out MORE possible worlds\\\nex. x = 0 entails xy = 0 as it doesn't matter the value of y xy will always equal 0\\\nGood model 287.\\\nIn every model where KB is true, a1 is also true, so KB ⊨ α1\\\nIn some models in which KB is true, a2 is false, so KB does not entail a2 (and the agent cannot conclude whatever a2 puts forth)\\\nif an inference algorithm can derive from , we write:\\\nKB ⊢i α \\\nwhich is pronounced “ is derived from by ” or “ derives from .”\\\nInference algo that derives only entailed sentences is SOUND or TRUTH-PRESERVING.\\\nIt is COMPLETE if it can derive any sentence that is entailed from the KB\\\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nUse symbols for wompus world: P, Q, R, W1,3, FacingEast...\\\nProp symbols with fixed meaning are true and false.\\\nCOMPLEX SENTENCES are constructed from simple sentences, with parentheses and logical connectives\\\nsee sheet294\\\nTT 296\\\n\\\nA SIMPLE KB:\\\nPx,y is true if there is a pit in [x,y] etc.\\\nSome sentences are true in all wompus worlds (or all similar worlds as they state teh rules):\nR2 : B1,1 ⇔ (P1,2 ∨ P2,1) \\\nR3 : B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1) \\\nWe know that \\\nR1 : NOT B1,1\\\nso there is no pit in 1,2 or 2,1\nR4 : NOT P1,2\\\nR5 : NOT P2,1\\\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \nLOGICAL EQUIVALENCE: two sentences are LE if they are true in the same set of models.\\\nα ≡ β if and only if α ⊨ β and β ⊨ α\\\n301 implications\\\na sentence is VALID if it is true in ALL models\\\nFor any sentences and , if and only if the sentence is valid.\\\nSATISFYABILITY:\\\nA SETNENCE IS SATISFIABLE IF IT IS TRUE OR SATISFIED BY some MODELS\\\nThe SAT problem was the first NP-Complete\\\n\\\nINFERENCE AND PROOFS:\\\nMODUS PONENS:\\\nα ⇒ β, α\n_____\nβ\n\\\na implies b an a is given, then we can infer b\\\nAND ELIMINATION:\\\nα ∧ β\n___\nα\nIf a and b, then definitely a, or definitely b. Ex WumpusAhead AND WumpusAlive, then WUMPUS alive can be inferred.\\\nα ⇔ β            ||        (α ⇒ β) ∧ (β ⇒ α)\n___\n(α ⇒ β) ∧ (β ⇒ α)         ||          α ⇔ β\n\n305 show how wecan get to NO pit in 2,1 and 1,2\\\n\nMONOTONACITY:\\\nif KB ⊨ α then KB ∧ β ⊨ α \nAnding B to KB doesn't change that a is inferred. because we are increasing the KB.\\\nThis does work logically, as we couldn't infer a if there is some information out there (b) that could invalidate it, so once it's inferred it's inferred.\\\n\\\nRESOLUTION RULE:\nP1 OR P2 or P3, NOT P2\n___\nP1 OR P3\\\nYou can resolve only 1 pair of complementary literals at a time.\\\n\\\nCONJUNCTIVE NORMAL FORM\\\nResolution rule applies only to clauses, so we need to reduce complex sentences to clauses\\\nTheorem Proving 2 310\\\n\\\nA RESOLUTION ALGO:\\\nThat is, to show that , we show that (KB ∧ ¬α) is unsatisfiable\\\nThe algo (pc 312):\\\n  1. converts to CNF\n  2. Resolves complementary literals until\\\n    a. there are no new clauses (can't resolve anymore) in which case KB does not ientail a\n    b. two clauses resolve to give us the EMPTY clause, in which case KB entails a\n\nDEFINITE CLAUSE:\\\nDisjunction of literals with EXACTLY ONE positive:\\\n(¬L1,1 ∨ ¬Breeze ∨ B1,1)\\\nHORN CLAUSE:\\\nHas AT MOST ONE positive\\\nGOAL CLAUSES:\\\nNO POSITIVE literals.\\\n\n\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "T3cm1WV542_a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0592b875-d105-4525-d383-6e97b4ecd0d2"
      },
      "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": 36,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Turing test - Can a machine think? Human interrogator questions it, and if it can't tell if it's a machine, it passes. \n\nThe computer would need the following: \n\nnatural language processing to communicate successfully in a human language \n\nknowledge representation to store what it knows or hears \n\nautomated reasoning to answer questions and to draw new conclusions \n\nmachine learning to adapt to new circumstances and to detect and extrapolate patterns \n\nTotal Turing test - requires interaction with objects and people in the real world, a robot would need: \n\ncomputer vision and speech recognition to perceive the world \n\nrobotics to manipulate objects and move about \n\nThe rational agent approach to AI is prevelent, because it is more general than \"laws of thought\" because correct inference is only a part of rationality. \n\nAlso it is better for scientific developement\n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n Is this another section? \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n An agents choice of action at any given instant depends on built-in knowledge and \nthe entire percept sequence observed to date. NOT on anything it hasn't percieved. \n\nExamples of agents: calculator, auto-sink, autonomous vaccuum. etc.\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n How to measure the \"right thing\" for a rational agent to do? \n\nPerformance measures: AI uses consequentialism: we evaluate an agent’s behavior by its consequences \n\nAs a general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave. \n\nWhat is rational at any given time depends on four things: \n\n1. The performance measure that defines the criteria of success\n\n2. The agent's prior knowledge of the environment\n\n3. The actionas that the agent can perform\n\n4. The agent's percept sequence to date\n\nFormal Definition of Rational Agent: For each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has.\n\nOMNICIENCE vs Rationality. An omnicient agent knows the actual outcome of it's actions, rather than checking the state after making a move. Not really possible in reality. \n\nRationality maximizes EXPECTED performance, while perfection maximizes ACTUAL performance.\n\nA rational agent should be AUTONOMOUS - it should learn what it can to compensate for partioal or incorrect prior knowledge. An example is a vaccuum that can learn where it is likely to become dirty again.\n\n\n \n\n## AIMA 2.3 The Nature of Environments\n \nSee chart for PEAS examples.\n\nObservatility: \n\nFully - if the agent's sensors give it access to complete state of the environment at each point in time (looking at a chess board). Note sensors only take in what is RELEVANT for it's decision.\n\nPartially - if the agent cannot see the full picture, examples include inaccurate sensors, or just missing information.\n\nUnobservable - if the agent has not sensors at all then the environment is unobservable.\n\nSingleAgent vs MultiAgent: \n\nSingleAgent - when there is one agent, for example a crossword puzzle.\n\nMultiAgent - when there are multiple agents, like playing chess.\n\nDistinctions: Does a taxi (an agent) view another vehicle as an object or another agent? The key distinction is whether ’s behavior is best described as maximizing a performance measure whose value depends on agent ’s behavior. \n\nThat distinction makes things like chess a COMPETETIVE multiagent environment. Whereas another vehicle wants to avoid collisions and so this can be viewed as a COOPERATIVE multiagent environment.\n\nDeterministic vs Nondeterministic: If the next state of the environment is completely determined by the current state and the action executed by the agent. Otherwise it's nondeterministic. \n\nIf it is deterministic and fully observable then the agent doesn't need to worry about uncertainty. BUT if it is partially observable, it may APPEAR nondeterministic.\n\nNOTE: some use stochastic as a synonym for nondeterministic, but they aren't the same thing. It is stochastic if it explicitly deals with probabilities, it's nondeterministic if there is no quantifier attached (there's a chance of rain)\n\nEpisodic vs Sequential:\n\nEpisodic - if an agent experience is atomic in nature. If for each episode it recieves information then acts. CRUCIALLY, the next episode doesn't depend on the last (like checking for defects)\n\nSequential - Chess is sequential, as the last episode affects the next by changing the board.\n\nStatic vs Dynamic :\n\nDynamic - if the board can change while the agent is choosing. Like self driving cars.\n\nStatic - if the board will wait for the move (chess, crossword, etc.)\n\nSemidynamic - if the board doesn't change over time but the score does (time limit)\n\nDiscrete vs Continuous : The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent\n\nKNOWN VS. UNKNOWN:\n\nKnown - outcomes for all actions are given (know the rules)\n\nUnknown - if chance is involved or the environment is unkonwn\n\n\nHardest situation: partially observable, multiagent, nondeterministic, sequential, dynamic,continuous, and unknown\n \n\n## AIMA 2.4 The Structure of Agents\n NOTE: see figures.\n\nSIMPLE-REFLEX AGENTS: \n\nThe simplest kind of agent. Only act on the current percept, ignoring percept history. Simple, small, but limited. \n\nCondition-action rule: IF car-in-front-is-braking THEN initiate-braking.\n\nSimple agents can be caught in infinite loops, but can break out if actions are RANDOMIZED.\n\nMODEL-BASED REFLEX AGENTS:\n\nBest way to handle partially-observalbility is for agent to keep track of the part of the world it can see now. Basically storing an internal state.\n\nTransition model of the world - knowledge about how the world works.\n\nSensor model - knowledge about things changing in the world that it senses.\n\nModel-based agent - an agent that uses the previous models.\n\nGOAL-BASED AGENTS: \n\nAgents which act in accordance to achieving a goal.\n\nSearch and planning are subfields of goal based AI.\n\nMay appear less efficient, but is very flexible, can just change the goal without changing behavior.\n\nUTILITY-BASED AGENTS :\n\nAgent which maximizes utility (hapiness).\n\nUses a utility function to measure this. Can specify trade-off in conflicting goals, allowing for multiple goals.\n\nMaximizes EXPECTED UTILITY as it's not possible to be 100% \n\nLEARNING AGENTS: \n\nLearning element - responsible for making improvements\n\nPerformance element - responsible for selecting external actions\n\nCritic - feeds info to learning element if it's not doing a good job, and determins how the performance element should be modified\n\nProblem generator - responsisble for suggesting actions that will elad to new and informative experiences\n\nSTATES OF TRANSITION:\n\nAtomic - states are indivisible, no internal structure.\n\nFactored representation - split up each state into a fixed set of variables or attributes, each with a value.\nStructured rep - \n\\\nFormally defined, rational agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n\\\nPEAS (Performance - what performance do we want to shoot for, Environment - the environment our agent faces, Actuators - how the agent controls it's moves, Sensors - how the agent absorbs information)\n\n \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive through sensors and act in an environment via actuators\n* **Rational agent** - one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n* **Percept** - the content an agent's sensors are perceiving\n* **Percept sequence** - complete history of percepts for the agent\n* **Agent function** - describes the agent's behavior, it maps any given percept sequence to an action. Abstract mathematical description.\n* **Agent program** - implements the agent function (not the same). It is concrete implementation, running within some physical system.\n* **Consequentialism** - we evaluate an agent’s behavior by its consequences\n* **Tas environments** - the 'problems' that the rational agents are the 'solutions' to \n* **Peas** - see notes\n* **Agent architecture** - a computing device with physical sensors and actuators (agent = architecture + program)\n* **Etc** - definitions\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \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 \nIf the correct action is not immediately obvious, an agent may need to PLAN AHEAD, this kind of agent is called a problem-solving agent. \\\nPS agents use ATOMIC representations, world states that are WHOLES, no internal structure visible to PS algorithm \\\nAgents which use factored or structured reps of states are called PLANNING AGENTS \\\n\\\nProcess of planning: \\\nGOAL FORUMLATION: adopt a goal (reaching Bucharest)\\]\nPROBLEM FURMULATION: agent devises a description of hte states and actions to reach the goal. A model of the relevant part of the world. (actions of traveling from one city to another, only thing that changes is the current city)\\\nSEARCH: agent simulates actions, searching until it reaches the goal. A goal sequence is called a SOLUTION.\\\nEXECUTION: Agent now takes the actions to reach goal found in search.\\\nNote: in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions (drive to city, then city, then Bucharest)\\\nOnce it's found a solution, agent can ignore percepts while executing, because solution is guaranteed to lead to goal. This is called OPEN-LOOP system.\\\nIf there is a chance the model is wrong, or environment is nondeterministic (road closed), this is CLOSED-LOOP approach and keep sensons on.\\\n\\\nSearch Problem Definition:\\\nA set of possible States the env can take, STATE SPACE\\\nINITIAL STATE where the agent starts\\\nGOAL STATES where the agent wants to go \\\nACTIONS available, like move or sense. Is defined by current state, so an action is APPLICABLE based on current state (toBucharest is only applicable when cities are 1 away from it)\\\nTRANSITION MODEL describes what each action does. Returns the result from the action \\\nACTION COST FUNCTION which calcs the cost of each action (dist, energy, etc)\\\nA sequence of actions forms a PATH, and a SOLUTION is a path which reaches the goal. OPTIMAL SOLUTION is a solution which is better than the rest by some measure.\nThe state space can be represented by a GRAPH, so we can search it.\\\nProblem focumation, using ABSTRACTION to take our unnecessary details.\\\n\n\n## AIMA Chapter 3.2 Example Problems\n\nA grid world problem, or vacuum world are examples.\\\n\\\nFor a circular robot moving on a flat surface, the space is essentially two-dimensional. When the robot has arms and legs that must also be controlled, \\\nthe search space becomes many-dimensional—one dimension for each joint angle.\\\n \n\n## AIMA Chapter 3.3 Search Algorithms\n A search algorithm takes a search problem as input and returns a solution or false.\\Can do this by imposing a search tree on the graph, each node is a state sapce.\\EXPAND the node by considering available ACTIONS using the RESULT function and generate new nodes for each state.\\We explore nodes out of the FRONTIER (a queue). How to decide what to expand next?\\BEST FIRST SEARCH:\\Choose from the frontier the node n which has the min value of some evaluation function f(n) (see pseudocode 113)\\SEARCH DATA STRUCTURES: \\Each node can have information associated (node.state, node.parent, node.action, node.path-cost)\\Follow the parent from the goal node for the solution (or keep track as you traverse)\nQUEUES: \\\nPriority queue: assign some evaluation from a function f, sort before taking first out each time\\\nFIFO: first in first out (used in BFS) \\\nLIFO: last in first out (stack) (used in DFS) \\\n\\\nREDUNTANT PATHS: \\\nIf you repeat nodes this implies a CYCLE, a REPEATED STATE. \\\nBut note that there may be a faster way to get there, so store the faster way.\\\nWhen it is IMPOSSIBLE to repeat a state, it's space efficient to not store them.\\\nGRAPH SEARCH: if the algorithm checks for redundant paths\\\nTREE-LIKE SEARCH: if it does not check for cycles.\\\nBEST FIRST SEARCH is a graph search.\\\nMEASURING PROBLEM-SOLVING PERFORMANCE:\\\nCOST OPTIMALITY: is the path it finds the lowest of all solutions?\\\nTIME COMPLEXITY: is the solution found in relatively good time?\\\nSPACE COMPLEXITY: how much memory does the algo need?\\\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uninformed search is given no idea how close to goal it is.\\BFS: If all actions have same cost, good use of BFS. We implement BFS as a call to Best-First-Search where f(n) is the depth of the node(number of steps to get there). Here we use a FIFO queue\\Once we reach the state, we can never find a better solution because it's BFS. (pc 122)\\ALWAYS finds a solution with min number of actions.\\DIJKSTRA'S ALGO or UNIFORM-COST SEARCH\\Can be implemented as a call to Best-First-Search with Path-Cost as the evaluation function.\\Figure 3.10 p 124\\Is complete and cost-optimal.\\DEPTH-FIRST SEARCH AND THE PROBLEM OF MEMORY:\\DFS always expands the deepst node in the frontier first.\\Call Best-First-Search where f is the negative of depth. Does not keep a table of reached states.\\For finite state space that are trees it is efficient and complete, but not for acyclic state spaces where it may expand the same state many times but will eventually explore the entire space.\\In a cyclic state space, it can get stuck in an infinite loop. And therefore INCOMPLETE.\\BUT it's got smaller need for memory, memory complexity of O(bm) where b is branching factor and m is the max depth of the tree.\\DEPTH-LIMITED AND ITERATIVE DEEPENING SEARCH:\\Limit the depth of DFS, But if we choose a bad depth, it is INCOMPLETE. (pc 128)\\Setting the limit can be done knowing the problem, in the Budapest problem, there are 20 cities, so depth of 19 is good.\\ITERATIVE DEEPEINING SEARCH:\\If we increase the depth with each call, we can make this complete.\\Time complexities 129.\\BIDIRECTIONAL SEARCH:\\Simultaneously searches forward from the initial state and backwards from the goal state(s)\\Keep track of two frontiers and two tables of reached states (pc 133)\\A useful table 134 COMPARING algos\n\n \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search, must use atomic rep of world states\n* **Planning agent** - agents which plan using factored or structured representations of states (not atomic)\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Using heuristics to more effectively search.\\h(n) = estimated cost of the cheapest path from the state at node n to a goal state\\For example, using straight line distance from current state to goal to estimate how good the node is.\\GREEDY BEST-FIRST SEARCH:\\A form of best-first-search where you choose the lowest h(n) to expand next (of the avialalbe nodes). So the evaluation function is f(n) = h(n). Using a priority queue.\nIs COMPLETE in FINITE SPACES, but not in INFINITE SPACES. \\\nWorst case time and space complexity is O(|V|). With a good heuristic, we can reduce that, as far as O(bm)\\\n\\\nA* SEARCH:\\\nBest-First-Search type search where:\\\nf(n) = g(n) + h(n)\\\nThat is, f(n) is the distance already traveled plus the distance to the goal.\\\nOr in general terms, cost already paid plus the heuristic cost to the goal.\\\nCan be written as: \\\nf(n) = estimated cost of the best path that continues from n to a goal\\\nThis algo is COMPLETE.\\\nIf the heuristic is good enough it is cost-optimal, but if not it CAN not be.\\\nThe heuristic must be admissible and then A* is cost-optimal.\\\nEvery consistent heuristic is admissible (BUT NOT VICE VERSA)\\\nIt should be clear that as you extend a path, the costs are monotonic: the path cost always increases as you go along a path, because action costs are always positive. \\\nBut note that a path might contribute several nodes in a row with the same score; this will happen whenever the decrease in is exactly equal to the action cost just taken (for \\\nexample, in a grid problem, when is in the same row as the goal and you take a step towards the goal, is increased by 1 and is decreased by 1)\\\n\\\nA* is efficient because it prunes away search tree nodes that aren't necessary for an optimal solution. (never checks nodes farther away from the goal than current)\\\nA drawback is that the number of nodes expanded can be exponential in the length of the solution.\\\n\\\nSATISFICING SEARCH:\\\nIf we let A* use an inadmissible heuristic (one that overestimates) it may miss the optimal solution, but can be more accurate and therefore expand fewer nodes.\\\nWEIGHTED A* SEARCH:\\\nf(n) = g(n) + W × h(n), W > 1.\\\nHere the heuristic is weighted more than the cost already taken.\\\nA good table 147\\\nBounded searches 147\\\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \nEFFECT OF HEURISTIC ACCURACY ON PERFORMANCE:\\\nEFFECTIVE BRANCHING FACTOR B*: the total nodes generated by A* for a particular problem is N and the solution depth is d, but b* is the branching factor that a uniform tree of depth d would have in order to contain N+1 nodes:\\\nN+1 = 1 + b* + (b*)^2 + ... + (b*)^d//\nFor example, if A* finds a solution at depth 5 using 52 nodes, then b* = 1.92.\\\nA good heuristic would have a b* value close to 1.\\\nKorf and Reid 159.\\\n\\\nGENERATING HEURISTICS FROM RELAXED PROBLEMS:\\\nA problem with fewer restrictions on the actions is called a RELAXED PROBLEM.\\\nState space of a relaxed problem is a SUPERGRAPH because there are more options with fewer rules.\\\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\\\nex of relaxed 162.\\\nwe can have h(n) = max{h1(n), … , hk(n)}.\\\nWhich can choose the best heuristic for the node in question.\\\nSince all hi are admissible then h(n) is also admissible, and h dominates all of it's component heuristics. BUT it takes longert to compute. \nDISJOINT PATTERN DATABASES 165\\\n\\\nGENERATING HEURISTICS WITH LANDMARKS:\\\nCan quicken finding solutions by precomputing some optimal path costs. It may be time consuming but only needs to be done once.\\\nChoose a few LANDMARK POINTS we compute C*(v,L) for vertices v. formula 166.\\\nIf the path happens to go through the landmark, it is admissible but otherwise it overestimates the cost.\\\nDIFFERENTIAL HEURISTIC: think of it as a landmark beyond the goal, if the goal is on the path to the landmark, then we just subtract from the goal to n.\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Admissible heuristic** - is one that never overestimates the cost to reach a goal\n* **Consistency** - for every node and every successor of generated by an action we have: h(n) ≤ c(n, a, n′) + h(n′)\n* **Triangle inequality** - which stipulates that a side of a triangle cannot be longer than the sum of the other two sides\n* **Manhattan distance** - city block distance, how many rows and columns out of place (rather than euclidean distance)\n* **Dominates** - h2 dominates h1 if A* using h2 will never expand more nodes than if it used h1\n* **Metalevel state space** - definition\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nConsidering multi-agent environments, we could think of them as :\\\nAn economy, thinking of it as aggregate.\\\nConsider adversarial agents as part of the environment, but we miss the idea that they are trying to defeat us.\\\nThird, model adversarial agents with techniques of adversarial game-tree search.\\\n\\\nTWO-PLAYER ZERO-SUM GAMES:\\\nMost studied within AI are deterministic, two-player, turn-based, perfect info, zero-sum games.\\\nThis means it's fully observable, and what's good for one player is bad for another.\\\nGame tree for tic-tac-toe 184.\\\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nMax must have a conditional plan (plan for mins move)\\\nUse MiniMax search for this.\\\nWe do this assuming that min plays optimally, if they dont' then max will do at least as well as it would against an optimal player. NOT necessarily the best play/best score.\\\n\\\nMINIMAX SEARCH ALGO:\\\nRecursive algo that goes to the leaves and backs up the values to the root. (pc 188)\\\nEssentially a full DFS of the game tree.\\\nIf depth of tree is m and there are b legal moves at each point, time complexity is O(b^m), space = O(bm)(if algo gen all actions at once) or O(m) if gen actions one at a time.\\\n\\\nOPTIMAL DECISIONS IN MULTIPLYAER GAMES:\\\nGet an array back with utility values for each player. The backed up value of node n is utility vector of best move for player moving at n.\\\n\\\nALPHA-BETA PRUNING:\\\nminimax is exponential time complexity, no algo can eliminate the expo, but can prune some hopefully.\\\nPrune parts of tree which have no chance of being chosen. 191 diagram\\\nAlpha = value of best (highest value) choice we've found on the path for max, a = \"at least\"\\\nBeta = value of best (lowest value) choice on path for min. The most that min will allow max to get if we take that path. b = \"at most\"\\\nPS 194 (see note)\\\n\\\nMOVE DEPENDENT:\\\nHow good pruning is depends on order we examine nodes, sometimes does nothing, best case done in O(b^(m/2)) instead of O(b^m)\\\nWith random move ordering we get roughly O(b^(3m/4))\\\nWe can give priorities to improve move ordering (chess first capture, then threats, then move...)\\\nCan also limit by PLY, first go one PLY deep, then use that to determine which to explore next, so on\\\nTRANSPOSITION TABLE, caches heuristic value of states.  it is possible to come back to same state, storing it makes everything faster 196.\\\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nWe can cut off at a certain point by treating nonterminal nodes as terminal nodes and using an evaluation function\\\nWe use a cutoff test to evaluate the node when it is deemed as terminal, in other worst at the depth we want.\\\nThe evaluation function returns an estimate of the expected utility of state s for player p.\\\nFor nonterninal nodes the evaluation is somewhere between a loss and a win.\\\nFor chess, this evaluation function could be the number of pieces each player has, with weights for the different pieces.\\\n\\\nCUTTING OFF SEARCH:\\\nif game.Is-Cutoff(state,depth) then return game.Eval(state,player),null \\\n\\\nFORWARD PRUNING:\\\nprunes moves that appear to be poor moves, but might possibly be good ones.\\\nSo saves computation time but risks making a mistake.\\\nOne approach is BEAM SEARCH on each ply, consider only a beam of the n best moves. Can still prune the best move.\\\nProbCut prunes cuts that are probably outside the window. 205\\\nLATE MOVE REDUCTION: assumes that move ordering has been done well, so late moves are bad moves.\\\n\\\nSEARCH VS LOOKUP:\\\nCan use lookup for things like early game (don't want to search a billion options just to move a pawn). \\\nEnd game too, but must be manually programmed or learned and stored. This is where the computer has an edge.\\\nCan solve endgame by producing POLICY: mapping from every possible state to the best move in that state.\\\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nDoesn't have heuristic search eval function.\\\nINstead, it averages the estimated utility of simulations of complete games from that state.\\\nHow to choose how to play? Uses a playout policy which biases towards good moves.\\\nPURE monte carlo search, do N simulations from current state, track which possible moves from current state has highest win percent.\\\nNot always sufficient, need SELECTION POLICTY, which balances EXPLORATION of states that have had few playouts, and EPLOITATION of states that have done well in the past.\\\nSEE SELECTION, EXPANSION, SIMULATION, BACK-PROPAGATION 210\\\nOne effective selection policy UCT, ranks possible move based on UCB1 (upper confidence bound formula see 211)\\\nAlgo 213\\\nMay want to use EARLY PLAYOUT TERMINATION where we stop playouts that take too many moves.\\\nDrawback: if a single move can change the course of the game, because it may not consider that move.\\\n\\\nSTOCHASTIC GAMES:\\\ngames with random element (luck and chance)\\\nMust include CHANCE NODES then, in addition to max and min nodes.\\\nSo we can only calculate EXPECTED VALUE of a position: the average over all possible outcomes of the chance nodes.\\\nEXPECTIMINIMAX VALUE: 218 \\\n\n\n\n\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nDECISION-THEROETIC AGENT: agent that can make rational decisions based on what it believes and wants.\\\nInstead of goal agent (good = goal / bad =non-goal), DTA will evaluate on a continous range.\\\nMAXIMUM EXPECTED UTILITY(MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility \\\n\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nSIX CONSTRAINTS: known as the AXIOMS OF UTILITY THEORY\\\nORDERABILITY: given any two lotteries, the agent must prefer one OR hold them equal (355)\\\nTRANSITIVITY: if A > B and B > C then A > C\\\nCONTINUITY: see 355\\\nSUBSTITUTABILITY: if agent finds two lotteries equal, subbing them in a more complex lottery the agent will find those equal too.\\\nMONOTONACITY: two lotteries with the same outcomes, A and B. If agent prefers A > B, then it chooses lottery with higher prob of getting A.\\\nDECOMPOSABILITY: Complex lottereis can be reduced using laws of probability (ex 356)\\\n\\\nFrom the axioms we can derive:\\\nEXISTENCE OF UTILITY FUNCTION: if agent prefers obey axioms and A > B then there is a utility function U where U(A) > U(B). Vice versa and same for equals.\\\nEXPECTED UTILITY OF A LOTTERY: Utility of a lottery is sum of prob of each outcome times utility of the outcome (expected value basically)\\\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n \nCome back to?\n\n \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Define game** - 182 see chart\n* **Utility function** - defines the final numeric value player p can expect when game ends\n* **Uct** - upper confidence bounds applied to trees\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSP consists of three componnets, X, D, C:\\\nX is set of variables {X1,...,Xn}\\\nD is a set of domains, {D1,...,Dn}, one for each variable\\\nC is a set of contraints that specify allowable combinations of values\\\nA domain Di consists of allowable values {v1,...,Vk} for variable Xi\\\nEx, a boolean variable would have domain {true, false}\\\nCSPs deal with asssignments of values to variables, {Xi = vi, Xj = vj,...}\\\nIf it doesn't violate a constraint it is CONSISTENT.\\\na COMPLETE ASSIGNMENT is when every var is assigned avalue.\\\na SOLUTION to a CSP is a consisten, complete assignment.\\\na PARTIAL ASSIGNMENT leaves some variables unassigned, and a PARTIAL SOLUTION isa partial assignemtn that is consisten.\\\nEX, MAP COLORING 233\\\nWHy formulate as CSP, 225.\\\nPRECEDENCE CONSTRAINGS:\\\nWhen a task must occur before another task, and a task takes a duration d1, we say:\\\nT1 + d1 <= T2\\\nDISJUNCTIVE CONSTRAINT: saying that the time's of these tasks cannot overlap:\\\n(AxleF + 10 ≤ AxleB) or (AxleB + 10 ≤ AxleF)\nIf problem is Discrete, and Finite, then we can use tuples of variables.\\\nIf not, we must use constraints.\\\nCONTINUOUS DOMAINS problems are studied in the real world (allocating time for hubble telescope)\\\n//\nCONSTRAINTS:\\\nUNARY CONSTRAING: restricts value of single variable\\\nBINARY CONSTRAINT: SA != NSW\\\na BINARY CSP is one with only unary and binary constraints (constraint graph)\\\nHIGHER ORDER CONSTRAINTS:\\\n⟨(X,Y ,Z),X < Y < Z or X > Y > Z⟩\\\nGLOBAL CONSTRAINT: involving arbitrary number of vars(ex. Alldiff, where all vars must be diff values 230)\\\nPREFERENCE VS ABSOLUTE CONSTRAINTS: absolute must happen, preferences don't\\\nCan encode this with costs for variable assignments\\\nMaximizing preferences in this way is a CONSTRAINT OPTIMAZATION PROBLEM(COP)\\\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nCONSTRAINT PROPAGATION: using constraints to limit the legal values for a var, which trickles to other vars\\\nCan either do this within search, or before you start searching\\\n\\\nNODE CONSISTENCY:\\\nA variable is node-consistent if all values in it's domain satisfy it's UNARY constraints (legal values)\\\nNote: easy to change n-ary constraints to unary\\\nCan do this before starting solving process.\\\n\\\nARC CONSISTENCY:\\\na var is arc-consistent if EVERY value in it's domain satisfies the variable's BINARY constraint\\\nThink sudoku, a cell is arc-consistent if no other cell in grid, row, or column has same value\\\n\\\nAC-3:\\\nmaintains a queue of arcs to considedr, starts with all arcs\\\nChecks if the arc is consistent, if it is, we move one\\\nif it isn't, we add back to the queue all arcs going to the outgoing arc we examined (pc 236)\\\n\\\nPATH CONSISTENCY:\\\ntightens binary constraints by using implicit constraints that are inferred by looking at triples of variables.\\\nadding a third restraint into the binary constraints\\\n\\\nK-CONSISTENCY:\\\n  A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consisten value can always be assigned to any kth variable.\\\n  1-consistency is node consistency, 2 consistency is arc consistency, and 3 consistency is path consistency.\\\n  Any algorithm for establishing n-consistency is exponential in time and space!\\\n\\\nGLOBAL CONSTRAINTS\\\nRESOURCE CONSTRAINT: or AtMost constraint. Used in scheduling problems.\\\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \npc 244\\\nVARIABLE AND VALUE ORDERING:\\\nHow to choose what variable to set next?\\\nMINIMUM REMAINING VALUES heuristic: choose variable with fewest \"legal\" moves (smallest domain). This is fail first\\\nDEGREE HEURISTIC: choosing the variable that is involved in the most constraints on other unassigned variables.\\\nNow the variable is chosen, which value to try first?\nLEAST CONSTRAINING VALUE: prefers value that rules out fewest choices of neighbors in the constraint graph. Keep as many options open as possible. This is fail-last\\\n\\\nINTERLEAVING SEARCH AND INFERENCE:\\\nInference is powerful during search (as AC-3 is before search)\\\nEvery time we inference, we can run AC-3 again and make real progress.\\\nFORWARD CHECKING: when we assign X, if there is an arc X->Y, take out value of X from domain of all Y (diag 248)\\\nFC doesn't catch all inconsistencies because it doesn't look forward enough. Could put you down a path which makes the puzzle impossible.\\\n\\\nINTELLIGENT BACKTRACKING: LOOKING BACKWARD:\\\nCHONOLOGICAL BACKTRACKING: when a search branch fails, it goes up to the previous level and tries another value (most recent)\\\nCan be inefficient as it goes up to levels that may not affect other regions (recoloring Tazmania)\\\nSay we fail in SA, we want to backtrack to a variable when changed could solve our SA problem. SO we keep track of a set of assignments that are in conflict with some value of SA.\\\nfor instance,{Q = red,NSW = green,V = blue} (called teh CONFLICT SET)\\\nThen we backjump to most recent assignment in the set.\\\nDOn't need to backjump because forward checking will prune paths that require it\\\n251 conf(Xi) ← conf(Xi) ∪ conf(Xj) − {Xi}.\\\n\\\nCONSTRAINT LEARNING:\\\nidea of finding min set of vars from conflict set that causes the problem.\\\nCall that set a NO-GOOD\\\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nLocal search algorithms are good at solving many CSPs.\\\npc 254\\\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n \nIndependent solutions can be found by finding connected components of the contraint graph.(tasmania vs mainland)\\\ndividing a Boolean CSP with 100 variables into four subproblems reduces the worst-case solution time from the lifetime of the universe down to less than a second\nbut completely independent problems are rare. \\\nBut other structures are found, like trees (if two variables are connected by only one path), and any tree-structured CSP is linear time complexity.\\\nDIRECTIONAL ARC CONSISTENCY(DAC): X1,X2,...,Xn if Xi is arc consistent with each Xj j>i\\\nuse topo sort to do this (257)\\\nCan reduce time to O(nd^2) where d is possible domain values for two variables\ngraph and pc 258\\\n\\\nCUTSET CONDITIONING:\\\nIf we don't have a tree, we can sometimes prune nodes to make one (259)\\\n1: choose subset S of CSP such that removing S leave you with a tree, S is called a CYCLE CUTSET\\\n2: FOR each assignment to variables in S that satisfies constraints on S:\\\n  a. remove from domain of remaining vars those vars set in S\\\n  b. if remaining CSP has solution, return together with assignment of S\\\nIf cycle cutset is size c, total runtime is O(d^c * (n - c)d^2).\\\nWe need to try all variations of solutions for S, so that is d^c combinations, then solve a tree of size (n-c)\\\nNOTE: finding smallest cycle cutset is NP-Hard, but approx algos are known. called CUTSET CONDITIONING\\\n\\\nTREE DECOMPOSITION:\\\nsECOND WAY TO REDUCE CONSTRAINT GRAPH\\\nTransform the original graph into a tree where each node is a set of variables(graph 261)\\\nOnce we have the tree-structured graph, we can get solution in O(nd^2) time, where n is number of tree nodes and d is size of largest domain (a domain here is a set of tuples).\\\n\\\nVALUE SYMETRY:\\\n\n \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nKnowledge base = KB = set of sentences which hold information about the world.\\\nIf it is given to the agent it is called an axiom\\\nCan start with BACKGROUND KNOWLEDGE\\\nWhen an agent program is called:\n  1. TELLS the KB what it percieves\n  2. ASKS the KB what action it should perform\n  3. Agent program TELLS the KB what action it chose, and returns the action to be executed\nDECLARATIVE approach to system building is starting with empty KB and TELL sentences until agent can operate in the system\\\nPROCEDURAL approach encodes desired behaviors as program code\\\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \ndef 278\\\npretty straight forward\n\n\n\n## AIMA Chapter 7.3 Logic\n \nENTAILMENT between sentences: when a sentence follows logically from another sentence or KB\\\nα ⊨ β\\\nα ⊨ β if and only if M(α) ⊆ M(β) \\\nwhere M is the model(world) we are working with\\\nif α ⊨ β then a is a STRONGER assertion than B, it rules out MORE possible worlds\\\nex. x = 0 entails xy = 0 as it doesn't matter the value of y xy will always equal 0\\\nGood model 287.\\\nIn every model where KB is true, a1 is also true, so KB ⊨ α1\\\nIn some models in which KB is true, a2 is false, so KB does not entail a2 (and the agent cannot conclude whatever a2 puts forth)\\\nif an inference algorithm can derive from , we write:\\\nKB ⊢i α \\\nwhich is pronounced “ is derived from by ” or “ derives from .”\\\nInference algo that derives only entailed sentences is SOUND or TRUTH-PRESERVING.\\\nIt is COMPLETE if it can derive any sentence that is entailed from the KB\\\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nUse symbols for wompus world: P, Q, R, W1,3, FacingEast...\\\nProp symbols with fixed meaning are true and false.\\\nCOMPLEX SENTENCES are constructed from simple sentences, with parentheses and logical connectives\\\nsee sheet294\\\nTT 296\\\n\\\nA SIMPLE KB:\\\nPx,y is true if there is a pit in [x,y] etc.\\\nSome sentences are true in all wompus worlds (or all similar worlds as they state teh rules):\nR2 : B1,1 ⇔ (P1,2 ∨ P2,1) \\\nR3 : B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1) \\\nWe know that \\\nR1 : NOT B1,1\\\nso there is no pit in 1,2 or 2,1\nR4 : NOT P1,2\\\nR5 : NOT P2,1\\\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \nLOGICAL EQUIVALENCE: two sentences are LE if they are true in the same set of models.\\\nα ≡ β if and only if α ⊨ β and β ⊨ α\\\n301 implications\\\na sentence is VALID if it is true in ALL models\\\nFor any sentences and , if and only if the sentence is valid.\\\nSATISFYABILITY:\\\nA SETNENCE IS SATISFIABLE IF IT IS TRUE OR SATISFIED BY some MODELS\\\nThe SAT problem was the first NP-Complete\\\n\\\nINFERENCE AND PROOFS:\\\nMODUS PONENS:\\\nα ⇒ β, α\n_____\nβ\n\\\na implies b an a is given, then we can infer b\\\nAND ELIMINATION:\\\nα ∧ β\n___\nα\nIf a and b, then definitely a, or definitely b. Ex WumpusAhead AND WumpusAlive, then WUMPUS alive can be inferred.\\\nα ⇔ β            ||        (α ⇒ β) ∧ (β ⇒ α)\n___\n(α ⇒ β) ∧ (β ⇒ α)         ||          α ⇔ β\n\n305 show how wecan get to NO pit in 2,1 and 1,2\\\n\nMONOTONACITY:\\\nif KB ⊨ α then KB ∧ β ⊨ α \nAnding B to KB doesn't change that a is inferred. because we are increasing the KB.\\\nThis does work logically, as we couldn't infer a if there is some information out there (b) that could invalidate it, so once it's inferred it's inferred.\\\n\\\nRESOLUTION RULE:\nP1 OR P2 or P3, NOT P2\n___\nP1 OR P3\\\nYou can resolve only 1 pair of complementary literals at a time.\\\n\\\nCONJUNCTIVE NORMAL FORM\\\nResolution rule applies only to clauses, so we need to reduce complex sentences to clauses\\\nTheorem Proving 2 310\\\n\\\nA RESOLUTION ALGO:\\\nThat is, to show that , we show that (KB ∧ ¬α) is unsatisfiable\\\nThe algo (pc 312):\\\n  1. converts to CNF\n  2. Resolves complementary literals until\\\n    a. there are no new clauses (can't resolve anymore) in which case KB does not ientail a\n    b. two clauses resolve to give us the EMPTY clause, in which case KB entails a\n\nDEFINITE CLAUSE:\\\nDisjunction of literals with EXACTLY ONE positive:\\\n(¬L1,1 ∨ ¬Breeze ∨ B1,1)\\\nHORN CLAUSE:\\\nHas AT MOST ONE positive\\\nGOAL CLAUSES:\\\nNO POSITIVE literals.\\\n\n\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}