{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "chreb 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": "f650a572-1635-49cd-f941-f48244956531"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c633c7b2-e5ff-4812-8ee0-58daee730215"
      },
      "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": 23,
      "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": 24,
      "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 = \"\"\"AI long history: intelligence is in difference ways (human performance vs abstractformal definition of rationality [doing the right thing]). Also: intelligence of internal thought processes and reasoning vs intelligent behavior (external characterization) [human vs rational& thought vs behavior) Turing introduced tests (can a machine think?: imitation game: NLP&ML&KnowledgeRepresentation&AutomatedReasoning). Total turing test involves interactions w/ objects and people in real world (CV&ROBO). AI Research is mostly for underlying principles of intelligence (instead of passing turing test). Cog modeling approach: intospection, brain images, psychological experiments. Allen Newell/Herbert Simon developed general problem solver(wanted to have program solving problems, but also comparing sequence and timing of reasoning w/ other humans 1961) Aristotle introduces irrefutable reasoning processes (syllogisms provided argument structures; a ->b, b->c, so a-> c). Agents are something that acts and perceives its environment. a rational one does it to achieve the best outcome (or expected). There are inferences, but also reflexes in rational acting (like touching hot stove. solving the turing test can also make a rational agent [which is preferred over other approaches to AI cuz its more general than the laws of thought and is more mathematically defined and complete). doing the right thing is seen as the standard model paradigm. perfect rationality isnt always possible, however. limited rationality—acting appropriately when there is not enough time to do all the computations one might like. However, perfect rationality often remains a good\n",
        "starting point for theoretical analysis. FOr something like chess, w/ objective built in, the standard model is easy to apply, it gets harder tho for the real world (self driving cars). The problem of achieving agreement between our true preferences and the objective we put\n",
        "into the machine is called the value alignment problem. the machine must be aligned with those of the human. If we are developing an AI system in the lab or in a simulator—as has been the case for most of the field’s history—there is an easy fix for an incorrectly specified objective: reset the system, fix the objective, and try again. As the field progresses towards increasingly capable intelligent systems that are deployed in the real world, this approach is no longer viable. what happens if the machine is intelligent enough to reason and act beyond the confines of the chessboard? Its not unintelligent nor insane, its just a consequence of deifining winning as the sole objective for the machine. We ultimately want agents that are provably beneficial to humans\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 = \"\"\" 1980 John Searle described weak AI: machines could act as if they were intelligent and strong AI: machines that act are actually consciously thinking (not just simulating thinking). Shifted to “general AI”: solve arbitrarily wide variety of tasks, including novel ones, and do so as well as a human. Turing’s “argument from informality of behavior”  human behavior is too large to be captured by some set of rules (supported by Hubert/Stuart Dreyfus, Ken Sayre) cognition takes place within a body, which is embedded in an environment (embodied cognition) Turing and Godel proved that  some mathematical questions cannot be ansered. Lucas said machines are inferior to humans because of it (but others, such as penrose, say otherwise)\n",
        "\n",
        "Alan Turing suggested that instead of asking whether machines can think, we should ask whether machines can pass a behavioral test, which has come to be called the Turing test. (imitation game, where a guy talks with an interrogator for 5 minutes, and the program passes the test if it fools the person 30% of the time). He thought by 2000 there'd be a computer that passes the test (there isnt except for Eugene Goostman. ELIZA and other bots like MGONZ and NATACHATA have fooled people, CYBERLOVER got in trouble with police ). Maybe a turing test is just for human gullibility, as no well-trained judge has been fooled  \"\"\"\n",
        "chapter27_2 = \"\"\" people think that machines thinking intelligently are only acting it, not actually conscious. But some( like dijkstra) dont really care about the distinction.\n",
        "\n",
        "\n",
        "John Searle rejects the polite convention, w/ the  Chinese room argument (Searle, 1990) \n",
        "it is given that the human does not understand Chinese.\n",
        "\n",
        "Strong AI centeres around consciousness: awareness of the outside world, and of the self, and the subjective experience of living.  \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent is anything that can be viewed as perceiving its environment through sensors and\n",
        "acting upon that environment through actuators. \n",
        "\n",
        "Percept refers to the content an agent’s sensors are perceiving. An agent’s percept sequence is the complete history of everything the agent has ever perceived. In\n",
        "general, an agent’s choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived. agent's behavior is defined by the agent function (maps percept sequence to an action) implemented by an agent program (agent function is an abstract mathematical description; the agent program is an implementation, running within some physical system)\n",
        "\n",
        "vacuum cleaner world is easy to see.\n",
        "\n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\" A rational agent is one that does the right thing (what does that mean? consequentialism: we evaluate an agent’s behavior by its consequences). Has a good performance measure. \n",
        "\n",
        "Rational at any given point is based on four things: performance measure that defines success, agents prior knowledge of environment, actions the agent can perform, and the agent's percept sequence. \n",
        "\n",
        "\n",
        "Theres a difference between rationality and omniscience (where it knows the actual outcome of the actions and can act, but its impossible irl). Imagine a freak accident of a piano falling on someones head on the street. If they get hit, they werent irrational, but they died so it obviously isnt perfect. Rationality is expected performance, while perfection is like actual performance. Rationality doesnt require omniscience. \n",
        "\n",
        "Doing actions in order to modify future percepts (info gathering) is important\n",
        "\n",
        "If an agent relies on prior knowledge of the designer rather than learning processes and percepts, it lacks autonomy. \n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" We have a task environment, which is the problems which the rational agents are the solutions. remember PEAS (Performance, Environment, Actuators, Sensors)\n",
        "\n",
        "\n",
        "\n",
        "FULLY OBSERVABLE VS. PARTIALLY OBSERVABLE: If an agent’s sensors give it access\n",
        "to the complete state of the environment at each point in time, then we say that the task\n",
        "environment is fully observable (chess). Partially observable is basically when its not fully seen. Single agent is when its just one agent (like crossword), while multiagent is more than one (chess is competitive multiagent, while self driving is cooperative multi agent)\n",
        "\n",
        "Deterministic is when the state is determined by the current state and actions of the agent. If it isnt, its nondeterministic (not necessarily always gonna lead to the same results every time) Stochastic assigns actual probabilities. \n",
        "\n",
        "\n",
        "episodic task environment, the agent’s experience is divided into atomic episodes. In each episode the agent receives a percept and then performs a single action. the next episode does not depend on the actions taken in previous episodes. Sequential environments work off of a sequence, where previous actions can affect future ones (chess and taxi driving)\n",
        "\n",
        "\n",
        "Static enviroments are when the environment does change, but if it does its dynamic (self driving)\n",
        "\n",
        "\n",
        "Discrete: finite number of discrete states, as well as percepts and actions (still intractible). Self driving is continous. \n",
        " \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "\"rational agent\" : \"select an action that is expected to maximize with knowledge from percept sequence and built-in knowledge the agent has.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "fe64d1c7-8ee8-4513-c746-870a3d13a679"
      },
      "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": 26,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nAI long history: intelligence is in difference ways (human performance vs abstractformal definition of rationality [doing the right thing]). Also: intelligence of internal thought processes and reasoning vs intelligent behavior (external characterization) [human vs rational& thought vs behavior) Turing introduced tests (can a machine think?: imitation game: NLP&ML&KnowledgeRepresentation&AutomatedReasoning). Total turing test involves interactions w/ objects and people in real world (CV&ROBO). AI Research is mostly for underlying principles of intelligence (instead of passing turing test). Cog modeling approach: intospection, brain images, psychological experiments. Allen Newell/Herbert Simon developed general problem solver(wanted to have program solving problems, but also comparing sequence and timing of reasoning w/ other humans 1961) Aristotle introduces irrefutable reasoning processes (syllogisms provided argument structures; a ->b, b->c, so a-> c). Agents are something that acts and perceives its environment. a rational one does it to achieve the best outcome (or expected). There are inferences, but also reflexes in rational acting (like touching hot stove. solving the turing test can also make a rational agent [which is preferred over other approaches to AI cuz its more general than the laws of thought and is more mathematically defined and complete). doing the right thing is seen as the standard model paradigm. perfect rationality isnt always possible, however. limited rationality—acting appropriately when there is not enough time to do all the computations one might like. However, perfect rationality often remains a good\nstarting point for theoretical analysis. FOr something like chess, w/ objective built in, the standard model is easy to apply, it gets harder tho for the real world (self driving cars). The problem of achieving agreement between our true preferences and the objective we put\ninto the machine is called the value alignment problem. the machine must be aligned with those of the human. If we are developing an AI system in the lab or in a simulator—as has been the case for most of the field’s history—there is an easy fix for an incorrectly specified objective: reset the system, fix the objective, and try again. As the field progresses towards increasingly capable intelligent systems that are deployed in the real world, this approach is no longer viable. what happens if the machine is intelligent enough to reason and act beyond the confines of the chessboard? Its not unintelligent nor insane, its just a consequence of deifining winning as the sole objective for the machine. We ultimately want agents that are provably beneficial to humans\n\n\n## AIMA Chapter 27.1 The Limits of AI\n 1980 John Searle described weak AI: machines could act as if they were intelligent and strong AI: machines that act are actually consciously thinking (not just simulating thinking). Shifted to “general AI”: solve arbitrarily wide variety of tasks, including novel ones, and do so as well as a human. Turing’s “argument from informality of behavior”  human behavior is too large to be captured by some set of rules (supported by Hubert/Stuart Dreyfus, Ken Sayre) cognition takes place within a body, which is embedded in an environment (embodied cognition) Turing and Godel proved that  some mathematical questions cannot be ansered. Lucas said machines are inferior to humans because of it (but others, such as penrose, say otherwise)\n\nAlan Turing suggested that instead of asking whether machines can think, we should ask whether machines can pass a behavioral test, which has come to be called the Turing test. (imitation game, where a guy talks with an interrogator for 5 minutes, and the program passes the test if it fools the person 30% of the time). He thought by 2000 there'd be a computer that passes the test (there isnt except for Eugene Goostman. ELIZA and other bots like MGONZ and NATACHATA have fooled people, CYBERLOVER got in trouble with police ). Maybe a turing test is just for human gullibility, as no well-trained judge has been fooled  \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n people think that machines thinking intelligently are only acting it, not actually conscious. But some( like dijkstra) dont really care about the distinction.\n\n\nJohn Searle rejects the polite convention, w/ the  Chinese room argument (Searle, 1990) \nit is given that the human does not understand Chinese.\n\nStrong AI centeres around consciousness: awareness of the outside world, and of the self, and the subjective experience of living.  \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and\nacting upon that environment through actuators. \n\nPercept refers to the content an agent’s sensors are perceiving. An agent’s percept sequence is the complete history of everything the agent has ever perceived. In\ngeneral, an agent’s choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived. agent's behavior is defined by the agent function (maps percept sequence to an action) implemented by an agent program (agent function is an abstract mathematical description; the agent program is an implementation, running within some physical system)\n\nvacuum cleaner world is easy to see.\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n A rational agent is one that does the right thing (what does that mean? consequentialism: we evaluate an agent’s behavior by its consequences). Has a good performance measure. \n\nRational at any given point is based on four things: performance measure that defines success, agents prior knowledge of environment, actions the agent can perform, and the agent's percept sequence. \n\n\nTheres a difference between rationality and omniscience (where it knows the actual outcome of the actions and can act, but its impossible irl). Imagine a freak accident of a piano falling on someones head on the street. If they get hit, they werent irrational, but they died so it obviously isnt perfect. Rationality is expected performance, while perfection is like actual performance. Rationality doesnt require omniscience. \n\nDoing actions in order to modify future percepts (info gathering) is important\n\nIf an agent relies on prior knowledge of the designer rather than learning processes and percepts, it lacks autonomy. \n \n\n## AIMA 2.3 The Nature of Environments\n We have a task environment, which is the problems which the rational agents are the solutions. remember PEAS (Performance, Environment, Actuators, Sensors)\n\n\n\nFULLY OBSERVABLE VS. PARTIALLY OBSERVABLE: If an agent’s sensors give it access\nto the complete state of the environment at each point in time, then we say that the task\nenvironment is fully observable (chess). Partially observable is basically when its not fully seen. Single agent is when its just one agent (like crossword), while multiagent is more than one (chess is competitive multiagent, while self driving is cooperative multi agent)\n\nDeterministic is when the state is determined by the current state and actions of the agent. If it isnt, its nondeterministic (not necessarily always gonna lead to the same results every time) Stochastic assigns actual probabilities. \n\n\nepisodic task environment, the agent’s experience is divided into atomic episodes. In each episode the agent receives a percept and then performs a single action. the next episode does not depend on the actions taken in previous episodes. Sequential environments work off of a sequence, where previous actions can affect future ones (chess and taxi driving)\n\n\nStatic enviroments are when the environment does change, but if it does its dynamic (self driving)\n\n\nDiscrete: finite number of discrete states, as well as percepts and actions (still intractible). Self driving is continous. \n \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n* **Rational agent** - select an action that is expected to maximize with knowledge from percept sequence and built-in knowledge the agent has.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"Developed by Guido van Rossum in 1989. Originally Dutch, in USA since 1995. Benevolent Dictator for Life (now retired, monty python)inspired by ABC language DARPA proposal\n",
        "“Computer Programming for Everybody”: An easy and intuitive language just as powerful as major competitors.\n",
        "Open source, code thats in plain english. Suitability for everyday tasks, allowing for short\n",
        "development times. Fast development (whitespace delimited, garbage collector), portable, various builtin types (dict, sets), numpy, pandas, sklearn, pytorch, pep8 python style\n",
        "All data treated as objects (Deleted by garbage collection one unreachable). Strong typed (, interpreter doesn’t allow things incompatible with\n",
        "that type (eg. “foo” + 2). Dynamic typing x=2 and x=foo. Strings can concatenate using +, prefix with r means raw, no need for special characters r'\\n' Spring formatting with %, IMMUTABLE\n",
        "== checks if it points to objects of same value, while is checks if variable is same object. Lists, are mutable. y=x for list makes it same object, y = x[:] creates a shallow copy of any sequence (a new object of same value)\n",
        " \n",
        " \n",
        "Tuple:  A simple immutable ordered sequence of items that is immutable and can be of mixed typesImmutable: a tuple cannot be modified once created\n",
        "Strings: immutable and use unicode and 2-byte characters (python 2 uses 8-bit characters)\n",
        "List: Mutable ordered sequence of items of mixed types\n",
        "\n",
        "tu = (23, 'abc', 4.56, (2,3), 'def'), tu[-3] #negative lookup from right, from -1 = 4.56\n",
        "t = (23, 'abc', 4.56, (2,3), 'def')\n",
        ">>> t[1:4] #slicing ends before last index\n",
        "('abc', 4.56, (2,3))\n",
        ">>> t[1:-1] #using negative index\n",
        "('abc', 4.56, (2,3))\n",
        ">>> t[1:-1:2] # selection of every nth item.\n",
        "('abc', (2,3))\n",
        ">>> t[:2] # copy from beginning of sequence\n",
        "(23, 'abc')\n",
        ">>> t[2:] # copy to the very end of the sequence\n",
        "(4.56, (2,3), 'def')\n",
        "\n",
        ">>> li = [1, 11, 3, 4, 5]\n",
        ">>> li.append('a') # Note the method syntax\n",
        ">>> li\n",
        "[1, 11, 3, 4, 5, 'a']\n",
        ">>> li.insert(2, 'i')\n",
        ">>> li\n",
        "[1, 11, 'i', 3, 4, 5, 'a']\n",
        ">>> li = ['a', 'b', 'c', 'b']\n",
        ">>> li.index('b') # index of first occurrence\n",
        "1\n",
        ">>> li.count('b') # number of occurrences\n",
        "2\n",
        ">>> li.remove('b') # remove first occurrence\n",
        ">>> li\n",
        "['a', 'c', 'b']\n",
        "\n",
        ">>> li.sort(some_function) # sort in place using user-defined comparison\n",
        ">>> sorted(li) #return a *copy* sorted\n",
        "\n",
        "\n",
        "\n",
        "dictionaries must have immutable keys: constant average time add, lookup, update\n",
        ">>> d = {'user' : 'R2D2',\n",
        "'pswd': 1234}\n",
        ">>> d['user']\n",
        "'R2D2'\n",
        ">>> d['R2D2'] = ERROR\n",
        "\n",
        ".keys()  gives a list of keys, .values() gives a list of values, .items() gives a list of item tuples\n",
        "defaultdict initializes nonexistent dictionary values\n",
        "\n",
        "no function overloading (function specified by name alone)\n",
        "\n",
        "default values for arguments:\n",
        "  >>> def myfun(b, c=5, d=\"no\"):\n",
        "return b + c\n",
        ">>> myfun(5,3,\"bob\")\n",
        "10\n",
        ">>> myfun(5,5)\n",
        "10\n",
        ">>> myfun(5)\n",
        "10\n",
        "\n",
        "Non-default argument should always precede default arguments; otherwise, it reports SyntaxError\n",
        "\n",
        "Functions can be called with arguments out of order (must be specified in cell)\n",
        "\n",
        "*args: def print_everything(*args): lst = ['a', 'b', 'c’]\n",
        "print_everything(*lst)\n",
        "**kwargs is similar\n",
        "def print_keyword_args(**kwargs):my_dict = {'first_name': 'Wei',\n",
        "'last_name': 'Xu’}\n",
        "print_keyword_args(**my_dict)\n",
        "\n",
        "\n",
        "def fib(n, fibs={}):\n",
        "    if n in fibs:\n",
        "        print('n = %d exists' % n)\n",
        "        return fibs[n]\n",
        "    if n <= 1:\n",
        "        print(\"here\")\n",
        "        print(n)\n",
        "        fibs[n] = n # Changes fibs!!\n",
        "    else:\n",
        "        print(\"there\")\n",
        "        print(n)\n",
        "        fibs[n] = fib(n-1) + fib(n-2)\n",
        "    return fibs[n]\n",
        "    \n",
        "g = fib(3)\n",
        "print(g)\n",
        "\n",
        "there\n",
        "3\n",
        "there\n",
        "2\n",
        "here\n",
        "1\n",
        "here\n",
        "0\n",
        "n = 1 exists\n",
        "2\n",
        "\n",
        "\n",
        "functions are first class obects: dynamically crated, destroyrd, passed to a function, returned as a value, and has all other rights as other variables\n",
        "\n",
        "multiple inheritance is supported\n",
        "\n",
        "class A(object):\n",
        "def foo(self):\n",
        "print('Foo!')\n",
        "class B(object):\n",
        "def foo(self):\n",
        "print('Foo?')\n",
        "def bar(self):\n",
        "print('Bar!')\n",
        "class C(A, B):\n",
        "def foobar(self):\n",
        "super().foo() # Foo!\n",
        "super().bar() # Bar!\n",
        "\n",
        "magic methods: init, len, copy, cmp, add, neg. main method is __main__\n",
        "\n",
        "list = list(range(1, 101)) goes from 1 to 100\n",
        "range(5) goes from 0 to 4\n",
        "\n",
        "list comprehension: squares = [x*x for x in nums]\n",
        "\n",
        "li = [3, 10, 2, 20, 1, 30]\n",
        "[elem * 2 for elem in li if elem > 4]\n",
        "[20, 40, 60]\n",
        "\n",
        "d = { k: v for k,v in lst1 } #dict\n",
        "s = { x for x in lst2 } #set\n",
        "\n",
        "class Yes:\n",
        "    def __init__(self, data):\n",
        "        self.data = data\n",
        "        self.index = len(data)\n",
        "    def __next__(self):\n",
        "        if self.index == 0:\n",
        "            raise StopIteration\n",
        "        self.index = self.index - 1\n",
        "        return self.data[self.index]\n",
        "    def __iter__(self):\n",
        "        return self\n",
        "generators are iterators with __next()__ method\n",
        "\n",
        "Benefits: less code than standard iterator, maintains local state, values computed once at a time, avoids storing entire sequence in memory, good for aggregating and for inginite sequences (bad for individual value inspection)\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 27,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1912caa1-8618-4952-9cc6-ef794628c0f9"
      },
      "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": 28,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\nDeveloped by Guido van Rossum in 1989. Originally Dutch, in USA since 1995. Benevolent Dictator for Life (now retired, monty python)inspired by ABC language DARPA proposal\n“Computer Programming for Everybody”: An easy and intuitive language just as powerful as major competitors.\nOpen source, code thats in plain english. Suitability for everyday tasks, allowing for short\ndevelopment times. Fast development (whitespace delimited, garbage collector), portable, various builtin types (dict, sets), numpy, pandas, sklearn, pytorch, pep8 python style\nAll data treated as objects (Deleted by garbage collection one unreachable). Strong typed (, interpreter doesn’t allow things incompatible with\nthat type (eg. “foo” + 2). Dynamic typing x=2 and x=foo. Strings can concatenate using +, prefix with r means raw, no need for special characters r'\n' Spring formatting with %, IMMUTABLE\n== checks if it points to objects of same value, while is checks if variable is same object. Lists, are mutable. y=x for list makes it same object, y = x[:] creates a shallow copy of any sequence (a new object of same value)\n \n \nTuple:  A simple immutable ordered sequence of items that is immutable and can be of mixed typesImmutable: a tuple cannot be modified once created\nStrings: immutable and use unicode and 2-byte characters (python 2 uses 8-bit characters)\nList: Mutable ordered sequence of items of mixed types\n\ntu = (23, 'abc', 4.56, (2,3), 'def'), tu[-3] #negative lookup from right, from -1 = 4.56\nt = (23, 'abc', 4.56, (2,3), 'def')\n>>> t[1:4] #slicing ends before last index\n('abc', 4.56, (2,3))\n>>> t[1:-1] #using negative index\n('abc', 4.56, (2,3))\n>>> t[1:-1:2] # selection of every nth item.\n('abc', (2,3))\n>>> t[:2] # copy from beginning of sequence\n(23, 'abc')\n>>> t[2:] # copy to the very end of the sequence\n(4.56, (2,3), 'def')\n\n>>> li = [1, 11, 3, 4, 5]\n>>> li.append('a') # Note the method syntax\n>>> li\n[1, 11, 3, 4, 5, 'a']\n>>> li.insert(2, 'i')\n>>> li\n[1, 11, 'i', 3, 4, 5, 'a']\n>>> li = ['a', 'b', 'c', 'b']\n>>> li.index('b') # index of first occurrence\n1\n>>> li.count('b') # number of occurrences\n2\n>>> li.remove('b') # remove first occurrence\n>>> li\n['a', 'c', 'b']\n\n>>> li.sort(some_function) # sort in place using user-defined comparison\n>>> sorted(li) #return a *copy* sorted\n\n\n\ndictionaries must have immutable keys: constant average time add, lookup, update\n>>> d = {'user' : 'R2D2',\n'pswd': 1234}\n>>> d['user']\n'R2D2'\n>>> d['R2D2'] = ERROR\n\n.keys()  gives a list of keys, .values() gives a list of values, .items() gives a list of item tuples\ndefaultdict initializes nonexistent dictionary values\n\nno function overloading (function specified by name alone)\n\ndefault values for arguments:\n  >>> def myfun(b, c=5, d=\"no\"):\nreturn b + c\n>>> myfun(5,3,\"bob\")\n10\n>>> myfun(5,5)\n10\n>>> myfun(5)\n10\n\nNon-default argument should always precede default arguments; otherwise, it reports SyntaxError\n\nFunctions can be called with arguments out of order (must be specified in cell)\n\n*args: def print_everything(*args): lst = ['a', 'b', 'c’]\nprint_everything(*lst)\n**kwargs is similar\ndef print_keyword_args(**kwargs):my_dict = {'first_name': 'Wei',\n'last_name': 'Xu’}\nprint_keyword_args(**my_dict)\n\n\ndef fib(n, fibs={}):\n    if n in fibs:\n        print('n = %d exists' % n)\n        return fibs[n]\n    if n <= 1:\n        print(\"here\")\n        print(n)\n        fibs[n] = n # Changes fibs!!\n    else:\n        print(\"there\")\n        print(n)\n        fibs[n] = fib(n-1) + fib(n-2)\n    return fibs[n]\n    \ng = fib(3)\nprint(g)\n\nthere\n3\nthere\n2\nhere\n1\nhere\n0\nn = 1 exists\n2\n\n\nfunctions are first class obects: dynamically crated, destroyrd, passed to a function, returned as a value, and has all other rights as other variables\n\nmultiple inheritance is supported\n\nclass A(object):\ndef foo(self):\nprint('Foo!')\nclass B(object):\ndef foo(self):\nprint('Foo?')\ndef bar(self):\nprint('Bar!')\nclass C(A, B):\ndef foobar(self):\nsuper().foo() # Foo!\nsuper().bar() # Bar!\n\nmagic methods: init, len, copy, cmp, add, neg. main method is __main__\n\nlist = list(range(1, 101)) goes from 1 to 100\nrange(5) goes from 0 to 4\n\nlist comprehension: squares = [x*x for x in nums]\n\nli = [3, 10, 2, 20, 1, 30]\n[elem * 2 for elem in li if elem > 4]\n[20, 40, 60]\n\nd = { k: v for k,v in lst1 } #dict\ns = { x for x in lst2 } #set\n\nclass Yes:\n    def __init__(self, data):\n        self.data = data\n        self.index = len(data)\n    def __next__(self):\n        if self.index == 0:\n            raise StopIteration\n        self.index = self.index - 1\n        return self.data[self.index]\n    def __iter__(self):\n        return self\ngenerators are iterators with __next()__ method\n\nBenefits: less code than standard iterator, maintains local state, values computed once at a time, avoids storing entire sequence in memory, good for aggregating and for inginite sequences (bad for individual value inspection)\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" When solving a problem, we have to make a goal, as well as formulate the problem. We do a SEARCH. We simulate sequences of actions in the model, searching until it finds a sequence of actions that hits the goal (which yields a solution). A problem is defined with having a set of possible states, an initial state, some goal states, actions, a transition model, and an action cost function. A sequence of actions forms a path, and a solution is a path from the initial state to the goal, an optimal soltuion is one wth the lowest cost path among all solutions. \"\"\"\n",
        "chapter3_2 = \"\"\" Grid world problem is used as a standardized problem (intended to illustrate various methods of problem solving). Real world problems can be standardized ones i suppose, but they seem to have much more variables. Like traveling salesman, VSLI, etc. \"\"\"\n",
        "chapter3_3 = \"\"\" A search algorithm takes the search problem as an input and returns a solution or failure. We see a node and expand it (child/successor node), and we make a tree. We have best first search (graph) where we chose the node with the minimum value of the evaluation function. FIFO for BFS and LIFO (stack) for DFS. Graph search checks for redundant paths, while tree-search doesnt. Completeness is if it returns a solution when there is one and reports a failure if there isnt, cost optimality si when the solution is the lowest path cost. TIme complexity is how long it takes to find a solution, and space complexity is how much memory is needed to do the search. Complexity can be measured of depth d (number of actions in an optimal solution). maximum number of actions in any path m, and branching factor b (number of successors of a node that need to be considered) \"\"\"\n",
        "chapter3_4 = \"\"\" BFS expands root first, tehn all successors of root are expanded, and so on.  It is best first search where evaluation function F(n) is the depth of the node (use FIFO). WE use early goal test (checking if node is a solution as soon as it is generated vs late goal test that best-first-search uses, waiting until node is popped off the queue). time and space is b^d, it is complete but not necessarily optimal. Uniform cost search or dijkstras algorithm is where best-first search has an evaluation funtion where the cost of the path from the root to the current node. It is complete and cost optimal. DFS just keeps expanding. evaluation function is the negative of depth (implemented like tree-like search, where it doesnt keep a table of reached states). It is not cost optimal, and it isnt even complete. It is good for smaller memory tho. memory complexity of O(bm).\n",
        "\n",
        "Depth limited search uses depth first search where we use a depth limit l and treat nodes at depth l if they have no successors. Has time complexity O(b^l) and space O(bl), still incomplete! Iterative deepending helps by incrementing l until a solution is found or it fails.  O(bd) memory (O(b^d) time) if theres a solution, O(bm) (O(b^m) time) w/ finite state spaces with no solution). It is optimal for problems where all actions have same cost (like BFS) and is complete on finite acyclic stae spaces. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 29,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 795
        },
        "outputId": "da2573a3-245d-4c54-baea-cd821edc9486"
      },
      "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": 30,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n When solving a problem, we have to make a goal, as well as formulate the problem. We do a SEARCH. We simulate sequences of actions in the model, searching until it finds a sequence of actions that hits the goal (which yields a solution). A problem is defined with having a set of possible states, an initial state, some goal states, actions, a transition model, and an action cost function. A sequence of actions forms a path, and a solution is a path from the initial state to the goal, an optimal soltuion is one wth the lowest cost path among all solutions. \n\n## AIMA Chapter 3.2 Example Problems\n Grid world problem is used as a standardized problem (intended to illustrate various methods of problem solving). Real world problems can be standardized ones i suppose, but they seem to have much more variables. Like traveling salesman, VSLI, etc. \n\n## AIMA Chapter 3.3 Search Algorithms\n A search algorithm takes the search problem as an input and returns a solution or failure. We see a node and expand it (child/successor node), and we make a tree. We have best first search (graph) where we chose the node with the minimum value of the evaluation function. FIFO for BFS and LIFO (stack) for DFS. Graph search checks for redundant paths, while tree-search doesnt. Completeness is if it returns a solution when there is one and reports a failure if there isnt, cost optimality si when the solution is the lowest path cost. TIme complexity is how long it takes to find a solution, and space complexity is how much memory is needed to do the search. Complexity can be measured of depth d (number of actions in an optimal solution). maximum number of actions in any path m, and branching factor b (number of successors of a node that need to be considered) \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS expands root first, tehn all successors of root are expanded, and so on.  It is best first search where evaluation function F(n) is the depth of the node (use FIFO). WE use early goal test (checking if node is a solution as soon as it is generated vs late goal test that best-first-search uses, waiting until node is popped off the queue). time and space is b^d, it is complete but not necessarily optimal. Uniform cost search or dijkstras algorithm is where best-first search has an evaluation funtion where the cost of the path from the root to the current node. It is complete and cost optimal. DFS just keeps expanding. evaluation function is the negative of depth (implemented like tree-like search, where it doesnt keep a table of reached states). It is not cost optimal, and it isnt even complete. It is good for smaller memory tho. memory complexity of O(bm).\n\nDepth limited search uses depth first search where we use a depth limit l and treat nodes at depth l if they have no successors. Has time complexity O(b^l) and space O(bl), still incomplete! Iterative deepending helps by incrementing l until a solution is found or it fails.  O(bd) memory (O(b^d) time) if theres a solution, O(bm) (O(b^m) time) w/ finite state spaces with no solution). It is optimal for problems where all actions have same cost (like BFS) and is complete on finite acyclic stae spaces. \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" informed search strategy uses domain specific hints about the goal, which uses a heuristic function (estimated cost of the cheapest path from the state at node n to goal state) h(n). Greedy best first search uses best-first search which expands the node with the lowest h(n) value (remember in class, route finding in romania, the heuristic they used was straight line distance). Worst case time and space complexity is O(V), it can be reduced to O(bm) with good heuristic stuff. it is complete in finite statespace, but not infinite. \n",
        "\n",
        "A* ends up using f(n) = g(n) + h(n), where g(n) is the path cost from the initial node to node n and h(n) is the estimated cost of the shortest path from n to goal state. altogether, f(n) estimates the cost of the best path that from continues from n to a goal. A* is indeed complete. For a heuristic to be admissible, it should NEVER overestimate the cost to reach a goal (admissible is optimistic). There is also consistency, where the heuristic is consistent if for every node n and its sucessor n', h(n) less than or equal to c(n, a, n') + h(n'). Remember triangle inequality. g costs are monotonic.It does prune nodes that arent necessary for finding an optimal solution. Inadmissible heuristics can overestimate (we could miss optimal solutions, but it could be more accurate.).  A* expands a lot of nodes, we explore fewer if we accept solutions that are suboptimal. There is also weighted A* search f(n) = g(n) + W*h(n), if W=1, thats A*, W=0 is uniform cost search, W = infinity is greedy best first search. All other values are just a modified weighted A* \"\"\"\n",
        "chapter3_6 = \"\"\" quality of heuristic is with effective branching factor. If a heuristic h2 dominates h1, h2 >= h1 for any n. Basically, h2 will never expand more nodes than h1 when they are used with A* (except when breaking ties). Creating a heuristic is like creating a relaxed problem. The state space of the relaxed problem is a super graph of the original state space; the game is more free, which creates more edges. look back at the grid sliding example\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 557
        },
        "outputId": "fdc0035f-e0b9-4c7b-ed9d-3c4f99acc6ed"
      },
      "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": 32,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n informed search strategy uses domain specific hints about the goal, which uses a heuristic function (estimated cost of the cheapest path from the state at node n to goal state) h(n). Greedy best first search uses best-first search which expands the node with the lowest h(n) value (remember in class, route finding in romania, the heuristic they used was straight line distance). Worst case time and space complexity is O(V), it can be reduced to O(bm) with good heuristic stuff. it is complete in finite statespace, but not infinite. \n\nA* ends up using f(n) = g(n) + h(n), where g(n) is the path cost from the initial node to node n and h(n) is the estimated cost of the shortest path from n to goal state. altogether, f(n) estimates the cost of the best path that from continues from n to a goal. A* is indeed complete. For a heuristic to be admissible, it should NEVER overestimate the cost to reach a goal (admissible is optimistic). There is also consistency, where the heuristic is consistent if for every node n and its sucessor n', h(n) less than or equal to c(n, a, n') + h(n'). Remember triangle inequality. g costs are monotonic.It does prune nodes that arent necessary for finding an optimal solution. Inadmissible heuristics can overestimate (we could miss optimal solutions, but it could be more accurate.).  A* expands a lot of nodes, we explore fewer if we accept solutions that are suboptimal. There is also weighted A* search f(n) = g(n) + W*h(n), if W=1, thats A*, W=0 is uniform cost search, W = infinity is greedy best first search. All other values are just a modified weighted A* \n\n## AIMA Chapter 3.6 Heuristic Functions\n quality of heuristic is with effective branching factor. If a heuristic h2 dominates h1, h2 >= h1 for any n. Basically, h2 will never expand more nodes than h1 when they are used with A* (except when breaking ties). Creating a heuristic is like creating a relaxed problem. The state space of the relaxed problem is a super graph of the original state space; the game is more free, which creates more edges. look back at the grid sliding example\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Go and chess are perfect info (fully observable) zero sum games (one move thats good for player 1 is bad for player 2, there is no win win). There is an initial state, a bool for whose turn, actions, results, and is terminal (game over). A utility function defines the final numeric value to a player when the game ends. \n",
        "\n",
        "the initial state, ACTIONS function, and RESULT function define the state space graph—a graph where the vertices are states, the edges are moves and a state might be reached by multiple paths. We define the complete game tree as a search tree that follows every sequence of moves all the way to a terminal state. The game tree may be infinite if the state space itself is unbounded or if the rules of the game allow for infinitely repeating positions.\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\" in a 2 player game, theres max and min. Max wants to maximize his score, while min wants to minimize. With multiple outcome scores, we use minimax (example on slides). We assume both players play optimally and that max goes first. Max tries to maximize what min would logically play. It is best to actually see this example (go to slides). It has a time complexity of O(b^m) and space of O(bm) for all actiosn at once (O(m) for generating actions one at a time). given a maximum depth of tree of m and b legal moves.\n",
        "\n",
        "The number of game states is exponential with the depth of the three. WE can prune the parts of the tree to make it faster with alpha-beta pruning. Alpha (at least) is the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX. While beta (at most) is the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MIN. At best, this could be O(b^m/2) nodes to be looked at. \"\"\"\n",
        "chapter5_3 = \"\"\" We can speed things up by cutting off search early and applying a heuristic evaluation function (we end up replacing the utility with eval, which estimates the states utility). we also use the cutoff test, which must return true for terminal states (but can choose whenever it watns to end). \"\"\"\n",
        "chapter5_5 = \"\"\" stochastic games make it unpredictable. Each move has a probability assigned to it. Positions have an expected value of a position (average over all possible outcomes of the chance nodes). This leads us to expectiminimax, which is similar to minimax, except that its basically using the expectation. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Maximum expected utility is  is the arg max of the expected utility (sum over all probability times the utilitiy)\n",
        "In a sense, the MEU principle could be seen as a prescription for intelligent behavior. All an\n",
        "intelligent agent has to do is calculate the various quantities, maximize utility over its\n",
        "actions, and away it goes. But this does not mean that the AI problem is solved by the\n",
        "definition!\n",
        "The MEU principle formalizes the general notion that an intelligent agent should “do the\n",
        "right thing,” but does not operationalize that advice. Estimating the probability distribution\n",
        " over possible states of the world, which folds into , requires perception,\n",
        "learning, knowledge representation, and inference. Computing itself\n",
        "requires a causal model of the world. There may be many actions to consider, and\n",
        "computing the outcome utilities may itself require further searching or planning\n",
        "because an agent may not know how good a state is until it knows where it can get to from\n",
        "that state. An AI system acting on behalf of a human may not know the human’s true utility\n",
        "function, so there may be uncertainty about . In summary, decision theory is not a panacea\n",
        "that solves the AI problem—but it does provide the beginnings of a basic mathematical\n",
        "framework that is general enough to define the AI problem.\n",
        "The MEU principle has a clear relation to the idea of performance measures introduced in\n",
        "Chapter 2 . The basic idea is simple. Consider the environments that could lead to an agent\n",
        "having a given percept history, and consider the different agents that we could design. If an\n",
        "agent acts so as to maximize a utility function that correctly reflects the performance measure, then\n",
        "the agent will achieve the highest possible performance score (averaged over all the possible\n",
        "environments). This is the central justification for the MEU principle itself. While the claim\n",
        "may seem tautological, it does in fact embody a very important transition from the external\n",
        "performance measure to an internal utility function. The performance measure gives a score\n",
        "for a history—a sequence of states. Thus it is applied retrospectively after an agent\n",
        "completes a sequence of actions. The utility function applies to the very next state, so it can\n",
        "be used to guide actions step by step \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 33,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "48cfecb0-7ac3-42c0-dfcf-acb07d182539"
      },
      "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": 34,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Go and chess are perfect info (fully observable) zero sum games (one move thats good for player 1 is bad for player 2, there is no win win). There is an initial state, a bool for whose turn, actions, results, and is terminal (game over). A utility function defines the final numeric value to a player when the game ends. \n\nthe initial state, ACTIONS function, and RESULT function define the state space graph—a graph where the vertices are states, the edges are moves and a state might be reached by multiple paths. We define the complete game tree as a search tree that follows every sequence of moves all the way to a terminal state. The game tree may be infinite if the state space itself is unbounded or if the rules of the game allow for infinitely repeating positions.\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n in a 2 player game, theres max and min. Max wants to maximize his score, while min wants to minimize. With multiple outcome scores, we use minimax (example on slides). We assume both players play optimally and that max goes first. Max tries to maximize what min would logically play. It is best to actually see this example (go to slides). It has a time complexity of O(b^m) and space of O(bm) for all actiosn at once (O(m) for generating actions one at a time). given a maximum depth of tree of m and b legal moves.\n\nThe number of game states is exponential with the depth of the three. WE can prune the parts of the tree to make it faster with alpha-beta pruning. Alpha (at least) is the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX. While beta (at most) is the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MIN. At best, this could be O(b^m/2) nodes to be looked at. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n We can speed things up by cutting off search early and applying a heuristic evaluation function (we end up replacing the utility with eval, which estimates the states utility). we also use the cutoff test, which must return true for terminal states (but can choose whenever it watns to end). \n\n## AIMA Chapter 5.5 Stochastic Games\n stochastic games make it unpredictable. Each move has a probability assigned to it. Positions have an expected value of a position (average over all possible outcomes of the chance nodes). This leads us to expectiminimax, which is similar to minimax, except that its basically using the expectation. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Maximum expected utility is  is the arg max of the expected utility (sum over all probability times the utilitiy)\nIn a sense, the MEU principle could be seen as a prescription for intelligent behavior. All an\nintelligent agent has to do is calculate the various quantities, maximize utility over its\nactions, and away it goes. But this does not mean that the AI problem is solved by the\ndefinition!\nThe MEU principle formalizes the general notion that an intelligent agent should “do the\nright thing,” but does not operationalize that advice. Estimating the probability distribution\n over possible states of the world, which folds into , requires perception,\nlearning, knowledge representation, and inference. Computing itself\nrequires a causal model of the world. There may be many actions to consider, and\ncomputing the outcome utilities may itself require further searching or planning\nbecause an agent may not know how good a state is until it knows where it can get to from\nthat state. An AI system acting on behalf of a human may not know the human’s true utility\nfunction, so there may be uncertainty about . In summary, decision theory is not a panacea\nthat solves the AI problem—but it does provide the beginnings of a basic mathematical\nframework that is general enough to define the AI problem.\nThe MEU principle has a clear relation to the idea of performance measures introduced in\nChapter 2 . The basic idea is simple. Consider the environments that could lead to an agent\nhaving a given percept history, and consider the different agents that we could design. If an\nagent acts so as to maximize a utility function that correctly reflects the performance measure, then\nthe agent will achieve the highest possible performance score (averaged over all the possible\nenvironments). This is the central justification for the MEU principle itself. While the claim\nmay seem tautological, it does in fact embody a very important transition from the external\nperformance measure to an internal utility function. The performance measure gives a score\nfor a history—a sequence of states. Thus it is applied retrospectively after an agent\ncompletes a sequence of actions. The utility function applies to the very next state, so it can\nbe used to guide actions step by step \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" We use a factored representation for each stae (a set of variables each of which has a value where the problem is solved when each variable has a value that satisfies all constraints on the variable: a constraint satisfaction problem or CSP). WE have a set of variables, a set of domains (one for each variable) and a set of constraints. Each constraint is a pair of scope (tuple of variables that participate in the constraint) and the relation which defines what the variables can take on. An assignment that doesnt violate the constraints is consistent. a complete assignment is where every variable is assigned. both of these together is a solution (complete and consistent). Solving a CSP is NP-hard haha. Remember coloring states of australia. Precedence constraints might mean constraints that have a higher precedence over others. special solution algorithms exist for Linear constarints on integer variables  (each variable appears only in linear form). Constraint optimiozation problems are CSPs with  preferences which can be solved with optimization search methods (path or local) \"\"\"\n",
        "chapter6_2 = \"\"\" CSP can do a specific type of inference called constraint propagation, where it uses the constraints to reduce the number of legal values for a variable (which can reduce other values, like sudoku). A single variable is node-consistent if all values in the variables domain satisfy the variables unary constraints. Example: south australians hate green, so the variable starts with domain {red, gree, blue}. WE can eliminate green and give it {red, blue}. A graph is node-consistent if all nodes are node-consistent.A variable is arc-consistent if for every value in its domain satisfies the variables binary constraints. A variable A is arc consistent with B if for every value in the domain of A there is some value in the domain of B that satisfies the binary constraint on the arc (A, B). A popular one is AC-3. It maintains a queue of arcs to consider (intiially all arcs in CSP). it pops off an arbitrary arc (A, B) and makes A concsistent with B. If this makes the domain of A unchanged, then it moves on. However, if this does change the domain of A, then we add all arcs (C, A) to the queue, where C is a neighbor of A. We do this cuz the change in A's domain might enable further reductions in C's domain. If the domain of A reduces to nothing, AC-3 can return failure. Otherwise, we keep checking trying to remove values from the domains of variables until no arcs are left. WE are left with a CSP that is equal to the original CSP, but the arc consistent CSP will be faster to search because its variables have smaller domains. \n",
        "\n",
        "\n",
        "Arc consistency tightens down the domains (unary constraints) using the arcs (binary\n",
        "constraints). To make progress on problems like map coloring, we need a stronger notion of consistency. Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. There is also k-consistency where if, for any set of variables and for any consistent assignment to those\n",
        "variables, a consistent value can always be assigned to any th variable. 1-consistency says\n",
        "that, given the empty set, we can make any set of one variable consistent: this is what we\n",
        "called node consistency. 2-consistency is the same as arc consistency. For binary constraint graphs, 3-consistency is the same as path consistency. Strongly k consistent is where it is k, k-1, k-2... conssitent.\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" With constraint propagation, some variables can still have multiple values. we then have to search for a solution. using depth limited search leads to a tree with n! d^n leaves (bad) even though there are only d^n complete assignments. Commutativity, which is if the order of application of any given set of actions does not matter, is used to help shave down n! a backtracking search procedure for CSPs. It repeatedly chooses an unassigned variable, and then tries all values in the domain of that variable in turn, trying to\n",
        "extend each one into a solution via a recursive call. If the call succeeds, the solution is\n",
        "returned, failing returns to previous state. least-constraining value heuristic is effective to decide on the order in which to examine its values. It ends up prefering values that rules out the fewest choices for the neighbors.\n",
        "\n",
        "AC-3 can reduce the domains of variables before we search, inference is more powerful during the search. Forward checking is used (Variable A is assigned, forward checking establishes arc consistency for it, every unassaigned variable B that is connected to A by a constraint, delete from B's domain any value inconsistent with A)\n",
        "\n",
        "Forward checking can fail. Other helpful things can be MAC (maintaining arc consistency). After A is called, an inference calls AC-3, but it only contains arcs B,A, where B is an unassigned variable neighbor of A. (AC-3 is still normal)\n",
        "\n",
        "Chronological backtracing back ups to the preceding variable and tries a new value when a branch fails. backjumping backtracks to the most recent assignment in the conflict set ( a set of variables responsible for making a value of some variable impossible).  A backjumping algorithm that uses conflict sets defined in this way is called conflict-directed backjumping.\n",
        "\n",
        "Constraint learning is finding a minimum set of variables from the conflict set that causes the problem.\n",
        "\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" Local search algorithms solve CSPs well because  They use a complete-state formulation (each state assigns a value to every variable, and the search changes the value of one variable at a time.)\n",
        "\n",
        "select the value that results in the minimum number of conflicts with other variables—the min-conflicts heuristic.\n",
        "\n",
        " constraint weighting aims to concentrate the search on the important constraints. where each constraing is set to 1. At each step, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then incrementing the weight of each constraint that is violated by the current assignment. \n",
        "\n",
        "local search can be used in an online setting (when the problem changes)\n",
        "\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" The structure of such CSPs can also help. with coloring australia, tasmania isnt connected to the mainland, so it is an independent subproblem. They then talk about topological sort. which can be thought of as DFS but each node is in reverse order of finish time (i think) (good for solving a tree-structured CSP). Cutset conditioning can help reduce a constraint graph to a tree\n",
        "\n",
        "Tree-structured problems can be solved in linear time. Cutset conditioning can reduce a general CSP to a tree-structured one if a small cutset can be found. Tree decomposition transforms the CSP into a tree of subproblems and are efficient if the tree width of the constraint graph is small (the minimum width among all its tree decompositions)  combine cutset conditioning with tree decomposition for a good tradeoff. \"\"\"\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": 35,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ff2afefb-2614-4e25-d0db-2725faf308ee"
      },
      "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": 36,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n We use a factored representation for each stae (a set of variables each of which has a value where the problem is solved when each variable has a value that satisfies all constraints on the variable: a constraint satisfaction problem or CSP). WE have a set of variables, a set of domains (one for each variable) and a set of constraints. Each constraint is a pair of scope (tuple of variables that participate in the constraint) and the relation which defines what the variables can take on. An assignment that doesnt violate the constraints is consistent. a complete assignment is where every variable is assigned. both of these together is a solution (complete and consistent). Solving a CSP is NP-hard haha. Remember coloring states of australia. Precedence constraints might mean constraints that have a higher precedence over others. special solution algorithms exist for Linear constarints on integer variables  (each variable appears only in linear form). Constraint optimiozation problems are CSPs with  preferences which can be solved with optimization search methods (path or local) \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n CSP can do a specific type of inference called constraint propagation, where it uses the constraints to reduce the number of legal values for a variable (which can reduce other values, like sudoku). A single variable is node-consistent if all values in the variables domain satisfy the variables unary constraints. Example: south australians hate green, so the variable starts with domain {red, gree, blue}. WE can eliminate green and give it {red, blue}. A graph is node-consistent if all nodes are node-consistent.A variable is arc-consistent if for every value in its domain satisfies the variables binary constraints. A variable A is arc consistent with B if for every value in the domain of A there is some value in the domain of B that satisfies the binary constraint on the arc (A, B). A popular one is AC-3. It maintains a queue of arcs to consider (intiially all arcs in CSP). it pops off an arbitrary arc (A, B) and makes A concsistent with B. If this makes the domain of A unchanged, then it moves on. However, if this does change the domain of A, then we add all arcs (C, A) to the queue, where C is a neighbor of A. We do this cuz the change in A's domain might enable further reductions in C's domain. If the domain of A reduces to nothing, AC-3 can return failure. Otherwise, we keep checking trying to remove values from the domains of variables until no arcs are left. WE are left with a CSP that is equal to the original CSP, but the arc consistent CSP will be faster to search because its variables have smaller domains. \n\n\nArc consistency tightens down the domains (unary constraints) using the arcs (binary\nconstraints). To make progress on problems like map coloring, we need a stronger notion of consistency. Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. There is also k-consistency where if, for any set of variables and for any consistent assignment to those\nvariables, a consistent value can always be assigned to any th variable. 1-consistency says\nthat, given the empty set, we can make any set of one variable consistent: this is what we\ncalled node consistency. 2-consistency is the same as arc consistency. For binary constraint graphs, 3-consistency is the same as path consistency. Strongly k consistent is where it is k, k-1, k-2... conssitent.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n With constraint propagation, some variables can still have multiple values. we then have to search for a solution. using depth limited search leads to a tree with n! d^n leaves (bad) even though there are only d^n complete assignments. Commutativity, which is if the order of application of any given set of actions does not matter, is used to help shave down n! a backtracking search procedure for CSPs. It repeatedly chooses an unassigned variable, and then tries all values in the domain of that variable in turn, trying to\nextend each one into a solution via a recursive call. If the call succeeds, the solution is\nreturned, failing returns to previous state. least-constraining value heuristic is effective to decide on the order in which to examine its values. It ends up prefering values that rules out the fewest choices for the neighbors.\n\nAC-3 can reduce the domains of variables before we search, inference is more powerful during the search. Forward checking is used (Variable A is assigned, forward checking establishes arc consistency for it, every unassaigned variable B that is connected to A by a constraint, delete from B's domain any value inconsistent with A)\n\nForward checking can fail. Other helpful things can be MAC (maintaining arc consistency). After A is called, an inference calls AC-3, but it only contains arcs B,A, where B is an unassigned variable neighbor of A. (AC-3 is still normal)\n\nChronological backtracing back ups to the preceding variable and tries a new value when a branch fails. backjumping backtracks to the most recent assignment in the conflict set ( a set of variables responsible for making a value of some variable impossible).  A backjumping algorithm that uses conflict sets defined in this way is called conflict-directed backjumping.\n\nConstraint learning is finding a minimum set of variables from the conflict set that causes the problem.\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search algorithms solve CSPs well because  They use a complete-state formulation (each state assigns a value to every variable, and the search changes the value of one variable at a time.)\n\nselect the value that results in the minimum number of conflicts with other variables—the min-conflicts heuristic.\n\n constraint weighting aims to concentrate the search on the important constraints. where each constraing is set to 1. At each step, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then incrementing the weight of each constraint that is violated by the current assignment. \n\nlocal search can be used in an online setting (when the problem changes)\n\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n The structure of such CSPs can also help. with coloring australia, tasmania isnt connected to the mainland, so it is an independent subproblem. They then talk about topological sort. which can be thought of as DFS but each node is in reverse order of finish time (i think) (good for solving a tree-structured CSP). Cutset conditioning can help reduce a constraint graph to a tree\n\nTree-structured problems can be solved in linear time. Cutset conditioning can reduce a general CSP to a tree-structured one if a small cutset can be found. Tree decomposition transforms the CSP into a tree of subproblems and are efficient if the tree width of the constraint graph is small (the minimum width among all its tree decompositions)  combine cutset conditioning with tree decomposition for a good tradeoff. \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 = \"\"\" The central component of a knowledge-based agent is its knowledge base, or KB. A\n",
        "knowledge base is a set of sentences. A given sentence is an axiom Some new sentences can be inferred (deriving new sentences from old)\n",
        "Starting with an empty knowledge base, the agent designer can TELL sentences until the agent can operate in its environment (declarative), while procedural approach encodes behaviors as code \"\"\"\n",
        "chapter7_2 = \"\"\" wumpus world hehe!\"\"\"\n",
        "chapter7_3 = \"\"\" knowledge bases consist of sentences made up of a syntax. model is a \"possible word\". if a sentence a is true in model m, we say m satisfies a or m is a model of a. M(a) means all models of a. For entailment (sentence follows logically from another sentence). a |= b. a entails b (iff in every model where a is true, b is also true). An inference algorithm that derives only entailed sentences is called sound or truthpreserving. if an inference algorithm i can derive alpha from KB, we write KB ⊢_i alpha. There is also completeness, it is complete if it can derive any sentence that is entailed. \"\"\"\n",
        "chapter7_4 = \"\"\" propositional logic. ¬W is the negation of W (both are literals). A conjunction is used with a ^ (carrot) a disjunction uses V. (A ^ B) V C is a disjunction. (A^B) is a disjunct as well as C. All this stuff is from 160 man. just study it \"\"\"\n",
        "chapter7_5 = \"\"\" α ≡ β if and only if α ⊨ β and β ⊨ α. logical equivalence. A sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF. Horn clause, which is a disjunction of literals of which at most one is positive.  I have stopped caring :) \"\"\"\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": 37,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 665
        },
        "outputId": "b47084ea-9667-402e-f9bb-6a46fe212db7"
      },
      "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": 39,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n The central component of a knowledge-based agent is its knowledge base, or KB. A\nknowledge base is a set of sentences. A given sentence is an axiom Some new sentences can be inferred (deriving new sentences from old)\nStarting with an empty knowledge base, the agent designer can TELL sentences until the agent can operate in its environment (declarative), while procedural approach encodes behaviors as code \n\n## AIMA Chapter 7.2 The Wumpus World\n wumpus world hehe!\n\n## AIMA Chapter 7.3 Logic\n knowledge bases consist of sentences made up of a syntax. model is a \"possible word\". if a sentence a is true in model m, we say m satisfies a or m is a model of a. M(a) means all models of a. For entailment (sentence follows logically from another sentence). a |= b. a entails b (iff in every model where a is true, b is also true). An inference algorithm that derives only entailed sentences is called sound or truthpreserving. if an inference algorithm i can derive alpha from KB, we write KB ⊢_i alpha. There is also completeness, it is complete if it can derive any sentence that is entailed. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n propositional logic. ¬W is the negation of W (both are literals). A conjunction is used with a ^ (carrot) a disjunction uses V. (A ^ B) V C is a disjunction. (A^B) is a disjunct as well as C. All this stuff is from 160 man. just study it \n\n## AIMA 7.5 Propositional Theorem Proving\n α ≡ β if and only if α ⊨ β and β ⊨ α. logical equivalence. A sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF. Horn clause, which is a disjunction of literals of which at most one is positive.  I have stopped caring :) \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "a5058d48-a800-45e7-dc1c-65f46d5c4ebd"
      },
      "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": 40,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nAI long history: intelligence is in difference ways (human performance vs abstractformal definition of rationality [doing the right thing]). Also: intelligence of internal thought processes and reasoning vs intelligent behavior (external characterization) [human vs rational& thought vs behavior) Turing introduced tests (can a machine think?: imitation game: NLP&ML&KnowledgeRepresentation&AutomatedReasoning). Total turing test involves interactions w/ objects and people in real world (CV&ROBO). AI Research is mostly for underlying principles of intelligence (instead of passing turing test). Cog modeling approach: intospection, brain images, psychological experiments. Allen Newell/Herbert Simon developed general problem solver(wanted to have program solving problems, but also comparing sequence and timing of reasoning w/ other humans 1961) Aristotle introduces irrefutable reasoning processes (syllogisms provided argument structures; a ->b, b->c, so a-> c). Agents are something that acts and perceives its environment. a rational one does it to achieve the best outcome (or expected). There are inferences, but also reflexes in rational acting (like touching hot stove. solving the turing test can also make a rational agent [which is preferred over other approaches to AI cuz its more general than the laws of thought and is more mathematically defined and complete). doing the right thing is seen as the standard model paradigm. perfect rationality isnt always possible, however. limited rationality—acting appropriately when there is not enough time to do all the computations one might like. However, perfect rationality often remains a good\nstarting point for theoretical analysis. FOr something like chess, w/ objective built in, the standard model is easy to apply, it gets harder tho for the real world (self driving cars). The problem of achieving agreement between our true preferences and the objective we put\ninto the machine is called the value alignment problem. the machine must be aligned with those of the human. If we are developing an AI system in the lab or in a simulator—as has been the case for most of the field’s history—there is an easy fix for an incorrectly specified objective: reset the system, fix the objective, and try again. As the field progresses towards increasingly capable intelligent systems that are deployed in the real world, this approach is no longer viable. what happens if the machine is intelligent enough to reason and act beyond the confines of the chessboard? Its not unintelligent nor insane, its just a consequence of deifining winning as the sole objective for the machine. We ultimately want agents that are provably beneficial to humans\n\n\n## AIMA Chapter 27.1 The Limits of AI\n 1980 John Searle described weak AI: machines could act as if they were intelligent and strong AI: machines that act are actually consciously thinking (not just simulating thinking). Shifted to “general AI”: solve arbitrarily wide variety of tasks, including novel ones, and do so as well as a human. Turing’s “argument from informality of behavior”  human behavior is too large to be captured by some set of rules (supported by Hubert/Stuart Dreyfus, Ken Sayre) cognition takes place within a body, which is embedded in an environment (embodied cognition) Turing and Godel proved that  some mathematical questions cannot be ansered. Lucas said machines are inferior to humans because of it (but others, such as penrose, say otherwise)\n\nAlan Turing suggested that instead of asking whether machines can think, we should ask whether machines can pass a behavioral test, which has come to be called the Turing test. (imitation game, where a guy talks with an interrogator for 5 minutes, and the program passes the test if it fools the person 30% of the time). He thought by 2000 there'd be a computer that passes the test (there isnt except for Eugene Goostman. ELIZA and other bots like MGONZ and NATACHATA have fooled people, CYBERLOVER got in trouble with police ). Maybe a turing test is just for human gullibility, as no well-trained judge has been fooled  \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n people think that machines thinking intelligently are only acting it, not actually conscious. But some( like dijkstra) dont really care about the distinction.\n\n\nJohn Searle rejects the polite convention, w/ the  Chinese room argument (Searle, 1990) \nit is given that the human does not understand Chinese.\n\nStrong AI centeres around consciousness: awareness of the outside world, and of the self, and the subjective experience of living.  \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and\nacting upon that environment through actuators. \n\nPercept refers to the content an agent’s sensors are perceiving. An agent’s percept sequence is the complete history of everything the agent has ever perceived. In\ngeneral, an agent’s choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived. agent's behavior is defined by the agent function (maps percept sequence to an action) implemented by an agent program (agent function is an abstract mathematical description; the agent program is an implementation, running within some physical system)\n\nvacuum cleaner world is easy to see.\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n A rational agent is one that does the right thing (what does that mean? consequentialism: we evaluate an agent’s behavior by its consequences). Has a good performance measure. \n\nRational at any given point is based on four things: performance measure that defines success, agents prior knowledge of environment, actions the agent can perform, and the agent's percept sequence. \n\n\nTheres a difference between rationality and omniscience (where it knows the actual outcome of the actions and can act, but its impossible irl). Imagine a freak accident of a piano falling on someones head on the street. If they get hit, they werent irrational, but they died so it obviously isnt perfect. Rationality is expected performance, while perfection is like actual performance. Rationality doesnt require omniscience. \n\nDoing actions in order to modify future percepts (info gathering) is important\n\nIf an agent relies on prior knowledge of the designer rather than learning processes and percepts, it lacks autonomy. \n \n\n## AIMA 2.3 The Nature of Environments\n We have a task environment, which is the problems which the rational agents are the solutions. remember PEAS (Performance, Environment, Actuators, Sensors)\n\n\n\nFULLY OBSERVABLE VS. PARTIALLY OBSERVABLE: If an agent’s sensors give it access\nto the complete state of the environment at each point in time, then we say that the task\nenvironment is fully observable (chess). Partially observable is basically when its not fully seen. Single agent is when its just one agent (like crossword), while multiagent is more than one (chess is competitive multiagent, while self driving is cooperative multi agent)\n\nDeterministic is when the state is determined by the current state and actions of the agent. If it isnt, its nondeterministic (not necessarily always gonna lead to the same results every time) Stochastic assigns actual probabilities. \n\n\nepisodic task environment, the agent’s experience is divided into atomic episodes. In each episode the agent receives a percept and then performs a single action. the next episode does not depend on the actions taken in previous episodes. Sequential environments work off of a sequence, where previous actions can affect future ones (chess and taxi driving)\n\n\nStatic enviroments are when the environment does change, but if it does its dynamic (self driving)\n\n\nDiscrete: finite number of discrete states, as well as percepts and actions (still intractible). Self driving is continous. \n \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n* **Rational agent** - select an action that is expected to maximize with knowledge from percept sequence and built-in knowledge the agent has.\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\nDeveloped by Guido van Rossum in 1989. Originally Dutch, in USA since 1995. Benevolent Dictator for Life (now retired, monty python)inspired by ABC language DARPA proposal\n“Computer Programming for Everybody”: An easy and intuitive language just as powerful as major competitors.\nOpen source, code thats in plain english. Suitability for everyday tasks, allowing for short\ndevelopment times. Fast development (whitespace delimited, garbage collector), portable, various builtin types (dict, sets), numpy, pandas, sklearn, pytorch, pep8 python style\nAll data treated as objects (Deleted by garbage collection one unreachable). Strong typed (, interpreter doesn’t allow things incompatible with\nthat type (eg. “foo” + 2). Dynamic typing x=2 and x=foo. Strings can concatenate using +, prefix with r means raw, no need for special characters r'\n' Spring formatting with %, IMMUTABLE\n== checks if it points to objects of same value, while is checks if variable is same object. Lists, are mutable. y=x for list makes it same object, y = x[:] creates a shallow copy of any sequence (a new object of same value)\n \n \nTuple:  A simple immutable ordered sequence of items that is immutable and can be of mixed typesImmutable: a tuple cannot be modified once created\nStrings: immutable and use unicode and 2-byte characters (python 2 uses 8-bit characters)\nList: Mutable ordered sequence of items of mixed types\n\ntu = (23, 'abc', 4.56, (2,3), 'def'), tu[-3] #negative lookup from right, from -1 = 4.56\nt = (23, 'abc', 4.56, (2,3), 'def')\n>>> t[1:4] #slicing ends before last index\n('abc', 4.56, (2,3))\n>>> t[1:-1] #using negative index\n('abc', 4.56, (2,3))\n>>> t[1:-1:2] # selection of every nth item.\n('abc', (2,3))\n>>> t[:2] # copy from beginning of sequence\n(23, 'abc')\n>>> t[2:] # copy to the very end of the sequence\n(4.56, (2,3), 'def')\n\n>>> li = [1, 11, 3, 4, 5]\n>>> li.append('a') # Note the method syntax\n>>> li\n[1, 11, 3, 4, 5, 'a']\n>>> li.insert(2, 'i')\n>>> li\n[1, 11, 'i', 3, 4, 5, 'a']\n>>> li = ['a', 'b', 'c', 'b']\n>>> li.index('b') # index of first occurrence\n1\n>>> li.count('b') # number of occurrences\n2\n>>> li.remove('b') # remove first occurrence\n>>> li\n['a', 'c', 'b']\n\n>>> li.sort(some_function) # sort in place using user-defined comparison\n>>> sorted(li) #return a *copy* sorted\n\n\n\ndictionaries must have immutable keys: constant average time add, lookup, update\n>>> d = {'user' : 'R2D2',\n'pswd': 1234}\n>>> d['user']\n'R2D2'\n>>> d['R2D2'] = ERROR\n\n.keys()  gives a list of keys, .values() gives a list of values, .items() gives a list of item tuples\ndefaultdict initializes nonexistent dictionary values\n\nno function overloading (function specified by name alone)\n\ndefault values for arguments:\n  >>> def myfun(b, c=5, d=\"no\"):\nreturn b + c\n>>> myfun(5,3,\"bob\")\n10\n>>> myfun(5,5)\n10\n>>> myfun(5)\n10\n\nNon-default argument should always precede default arguments; otherwise, it reports SyntaxError\n\nFunctions can be called with arguments out of order (must be specified in cell)\n\n*args: def print_everything(*args): lst = ['a', 'b', 'c’]\nprint_everything(*lst)\n**kwargs is similar\ndef print_keyword_args(**kwargs):my_dict = {'first_name': 'Wei',\n'last_name': 'Xu’}\nprint_keyword_args(**my_dict)\n\n\ndef fib(n, fibs={}):\n    if n in fibs:\n        print('n = %d exists' % n)\n        return fibs[n]\n    if n <= 1:\n        print(\"here\")\n        print(n)\n        fibs[n] = n # Changes fibs!!\n    else:\n        print(\"there\")\n        print(n)\n        fibs[n] = fib(n-1) + fib(n-2)\n    return fibs[n]\n    \ng = fib(3)\nprint(g)\n\nthere\n3\nthere\n2\nhere\n1\nhere\n0\nn = 1 exists\n2\n\n\nfunctions are first class obects: dynamically crated, destroyrd, passed to a function, returned as a value, and has all other rights as other variables\n\nmultiple inheritance is supported\n\nclass A(object):\ndef foo(self):\nprint('Foo!')\nclass B(object):\ndef foo(self):\nprint('Foo?')\ndef bar(self):\nprint('Bar!')\nclass C(A, B):\ndef foobar(self):\nsuper().foo() # Foo!\nsuper().bar() # Bar!\n\nmagic methods: init, len, copy, cmp, add, neg. main method is __main__\n\nlist = list(range(1, 101)) goes from 1 to 100\nrange(5) goes from 0 to 4\n\nlist comprehension: squares = [x*x for x in nums]\n\nli = [3, 10, 2, 20, 1, 30]\n[elem * 2 for elem in li if elem > 4]\n[20, 40, 60]\n\nd = { k: v for k,v in lst1 } #dict\ns = { x for x in lst2 } #set\n\nclass Yes:\n    def __init__(self, data):\n        self.data = data\n        self.index = len(data)\n    def __next__(self):\n        if self.index == 0:\n            raise StopIteration\n        self.index = self.index - 1\n        return self.data[self.index]\n    def __iter__(self):\n        return self\ngenerators are iterators with __next()__ method\n\nBenefits: less code than standard iterator, maintains local state, values computed once at a time, avoids storing entire sequence in memory, good for aggregating and for inginite sequences (bad for individual value inspection)\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n When solving a problem, we have to make a goal, as well as formulate the problem. We do a SEARCH. We simulate sequences of actions in the model, searching until it finds a sequence of actions that hits the goal (which yields a solution). A problem is defined with having a set of possible states, an initial state, some goal states, actions, a transition model, and an action cost function. A sequence of actions forms a path, and a solution is a path from the initial state to the goal, an optimal soltuion is one wth the lowest cost path among all solutions. \n\n## AIMA Chapter 3.2 Example Problems\n Grid world problem is used as a standardized problem (intended to illustrate various methods of problem solving). Real world problems can be standardized ones i suppose, but they seem to have much more variables. Like traveling salesman, VSLI, etc. \n\n## AIMA Chapter 3.3 Search Algorithms\n A search algorithm takes the search problem as an input and returns a solution or failure. We see a node and expand it (child/successor node), and we make a tree. We have best first search (graph) where we chose the node with the minimum value of the evaluation function. FIFO for BFS and LIFO (stack) for DFS. Graph search checks for redundant paths, while tree-search doesnt. Completeness is if it returns a solution when there is one and reports a failure if there isnt, cost optimality si when the solution is the lowest path cost. TIme complexity is how long it takes to find a solution, and space complexity is how much memory is needed to do the search. Complexity can be measured of depth d (number of actions in an optimal solution). maximum number of actions in any path m, and branching factor b (number of successors of a node that need to be considered) \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS expands root first, tehn all successors of root are expanded, and so on.  It is best first search where evaluation function F(n) is the depth of the node (use FIFO). WE use early goal test (checking if node is a solution as soon as it is generated vs late goal test that best-first-search uses, waiting until node is popped off the queue). time and space is b^d, it is complete but not necessarily optimal. Uniform cost search or dijkstras algorithm is where best-first search has an evaluation funtion where the cost of the path from the root to the current node. It is complete and cost optimal. DFS just keeps expanding. evaluation function is the negative of depth (implemented like tree-like search, where it doesnt keep a table of reached states). It is not cost optimal, and it isnt even complete. It is good for smaller memory tho. memory complexity of O(bm).\n\nDepth limited search uses depth first search where we use a depth limit l and treat nodes at depth l if they have no successors. Has time complexity O(b^l) and space O(bl), still incomplete! Iterative deepending helps by incrementing l until a solution is found or it fails.  O(bd) memory (O(b^d) time) if theres a solution, O(bm) (O(b^m) time) w/ finite state spaces with no solution). It is optimal for problems where all actions have same cost (like BFS) and is complete on finite acyclic stae spaces. \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n informed search strategy uses domain specific hints about the goal, which uses a heuristic function (estimated cost of the cheapest path from the state at node n to goal state) h(n). Greedy best first search uses best-first search which expands the node with the lowest h(n) value (remember in class, route finding in romania, the heuristic they used was straight line distance). Worst case time and space complexity is O(V), it can be reduced to O(bm) with good heuristic stuff. it is complete in finite statespace, but not infinite. \n\nA* ends up using f(n) = g(n) + h(n), where g(n) is the path cost from the initial node to node n and h(n) is the estimated cost of the shortest path from n to goal state. altogether, f(n) estimates the cost of the best path that from continues from n to a goal. A* is indeed complete. For a heuristic to be admissible, it should NEVER overestimate the cost to reach a goal (admissible is optimistic). There is also consistency, where the heuristic is consistent if for every node n and its sucessor n', h(n) less than or equal to c(n, a, n') + h(n'). Remember triangle inequality. g costs are monotonic.It does prune nodes that arent necessary for finding an optimal solution. Inadmissible heuristics can overestimate (we could miss optimal solutions, but it could be more accurate.).  A* expands a lot of nodes, we explore fewer if we accept solutions that are suboptimal. There is also weighted A* search f(n) = g(n) + W*h(n), if W=1, thats A*, W=0 is uniform cost search, W = infinity is greedy best first search. All other values are just a modified weighted A* \n\n## AIMA Chapter 3.6 Heuristic Functions\n quality of heuristic is with effective branching factor. If a heuristic h2 dominates h1, h2 >= h1 for any n. Basically, h2 will never expand more nodes than h1 when they are used with A* (except when breaking ties). Creating a heuristic is like creating a relaxed problem. The state space of the relaxed problem is a super graph of the original state space; the game is more free, which creates more edges. look back at the grid sliding example\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Go and chess are perfect info (fully observable) zero sum games (one move thats good for player 1 is bad for player 2, there is no win win). There is an initial state, a bool for whose turn, actions, results, and is terminal (game over). A utility function defines the final numeric value to a player when the game ends. \n\nthe initial state, ACTIONS function, and RESULT function define the state space graph—a graph where the vertices are states, the edges are moves and a state might be reached by multiple paths. We define the complete game tree as a search tree that follows every sequence of moves all the way to a terminal state. The game tree may be infinite if the state space itself is unbounded or if the rules of the game allow for infinitely repeating positions.\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n in a 2 player game, theres max and min. Max wants to maximize his score, while min wants to minimize. With multiple outcome scores, we use minimax (example on slides). We assume both players play optimally and that max goes first. Max tries to maximize what min would logically play. It is best to actually see this example (go to slides). It has a time complexity of O(b^m) and space of O(bm) for all actiosn at once (O(m) for generating actions one at a time). given a maximum depth of tree of m and b legal moves.\n\nThe number of game states is exponential with the depth of the three. WE can prune the parts of the tree to make it faster with alpha-beta pruning. Alpha (at least) is the value of the best (i.e., highest-value) choice we have found so far at any choice point along the path for MAX. While beta (at most) is the value of the best (i.e., lowest-value) choice we have found so far at any choice point along the path for MIN. At best, this could be O(b^m/2) nodes to be looked at. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n We can speed things up by cutting off search early and applying a heuristic evaluation function (we end up replacing the utility with eval, which estimates the states utility). we also use the cutoff test, which must return true for terminal states (but can choose whenever it watns to end). \n\n## AIMA Chapter 5.5 Stochastic Games\n stochastic games make it unpredictable. Each move has a probability assigned to it. Positions have an expected value of a position (average over all possible outcomes of the chance nodes). This leads us to expectiminimax, which is similar to minimax, except that its basically using the expectation. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Maximum expected utility is  is the arg max of the expected utility (sum over all probability times the utilitiy)\nIn a sense, the MEU principle could be seen as a prescription for intelligent behavior. All an\nintelligent agent has to do is calculate the various quantities, maximize utility over its\nactions, and away it goes. But this does not mean that the AI problem is solved by the\ndefinition!\nThe MEU principle formalizes the general notion that an intelligent agent should “do the\nright thing,” but does not operationalize that advice. Estimating the probability distribution\n over possible states of the world, which folds into , requires perception,\nlearning, knowledge representation, and inference. Computing itself\nrequires a causal model of the world. There may be many actions to consider, and\ncomputing the outcome utilities may itself require further searching or planning\nbecause an agent may not know how good a state is until it knows where it can get to from\nthat state. An AI system acting on behalf of a human may not know the human’s true utility\nfunction, so there may be uncertainty about . In summary, decision theory is not a panacea\nthat solves the AI problem—but it does provide the beginnings of a basic mathematical\nframework that is general enough to define the AI problem.\nThe MEU principle has a clear relation to the idea of performance measures introduced in\nChapter 2 . The basic idea is simple. Consider the environments that could lead to an agent\nhaving a given percept history, and consider the different agents that we could design. If an\nagent acts so as to maximize a utility function that correctly reflects the performance measure, then\nthe agent will achieve the highest possible performance score (averaged over all the possible\nenvironments). This is the central justification for the MEU principle itself. While the claim\nmay seem tautological, it does in fact embody a very important transition from the external\nperformance measure to an internal utility function. The performance measure gives a score\nfor a history—a sequence of states. Thus it is applied retrospectively after an agent\ncompletes a sequence of actions. The utility function applies to the very next state, so it can\nbe used to guide actions step by step \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n We use a factored representation for each stae (a set of variables each of which has a value where the problem is solved when each variable has a value that satisfies all constraints on the variable: a constraint satisfaction problem or CSP). WE have a set of variables, a set of domains (one for each variable) and a set of constraints. Each constraint is a pair of scope (tuple of variables that participate in the constraint) and the relation which defines what the variables can take on. An assignment that doesnt violate the constraints is consistent. a complete assignment is where every variable is assigned. both of these together is a solution (complete and consistent). Solving a CSP is NP-hard haha. Remember coloring states of australia. Precedence constraints might mean constraints that have a higher precedence over others. special solution algorithms exist for Linear constarints on integer variables  (each variable appears only in linear form). Constraint optimiozation problems are CSPs with  preferences which can be solved with optimization search methods (path or local) \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n CSP can do a specific type of inference called constraint propagation, where it uses the constraints to reduce the number of legal values for a variable (which can reduce other values, like sudoku). A single variable is node-consistent if all values in the variables domain satisfy the variables unary constraints. Example: south australians hate green, so the variable starts with domain {red, gree, blue}. WE can eliminate green and give it {red, blue}. A graph is node-consistent if all nodes are node-consistent.A variable is arc-consistent if for every value in its domain satisfies the variables binary constraints. A variable A is arc consistent with B if for every value in the domain of A there is some value in the domain of B that satisfies the binary constraint on the arc (A, B). A popular one is AC-3. It maintains a queue of arcs to consider (intiially all arcs in CSP). it pops off an arbitrary arc (A, B) and makes A concsistent with B. If this makes the domain of A unchanged, then it moves on. However, if this does change the domain of A, then we add all arcs (C, A) to the queue, where C is a neighbor of A. We do this cuz the change in A's domain might enable further reductions in C's domain. If the domain of A reduces to nothing, AC-3 can return failure. Otherwise, we keep checking trying to remove values from the domains of variables until no arcs are left. WE are left with a CSP that is equal to the original CSP, but the arc consistent CSP will be faster to search because its variables have smaller domains. \n\n\nArc consistency tightens down the domains (unary constraints) using the arcs (binary\nconstraints). To make progress on problems like map coloring, we need a stronger notion of consistency. Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. There is also k-consistency where if, for any set of variables and for any consistent assignment to those\nvariables, a consistent value can always be assigned to any th variable. 1-consistency says\nthat, given the empty set, we can make any set of one variable consistent: this is what we\ncalled node consistency. 2-consistency is the same as arc consistency. For binary constraint graphs, 3-consistency is the same as path consistency. Strongly k consistent is where it is k, k-1, k-2... conssitent.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n With constraint propagation, some variables can still have multiple values. we then have to search for a solution. using depth limited search leads to a tree with n! d^n leaves (bad) even though there are only d^n complete assignments. Commutativity, which is if the order of application of any given set of actions does not matter, is used to help shave down n! a backtracking search procedure for CSPs. It repeatedly chooses an unassigned variable, and then tries all values in the domain of that variable in turn, trying to\nextend each one into a solution via a recursive call. If the call succeeds, the solution is\nreturned, failing returns to previous state. least-constraining value heuristic is effective to decide on the order in which to examine its values. It ends up prefering values that rules out the fewest choices for the neighbors.\n\nAC-3 can reduce the domains of variables before we search, inference is more powerful during the search. Forward checking is used (Variable A is assigned, forward checking establishes arc consistency for it, every unassaigned variable B that is connected to A by a constraint, delete from B's domain any value inconsistent with A)\n\nForward checking can fail. Other helpful things can be MAC (maintaining arc consistency). After A is called, an inference calls AC-3, but it only contains arcs B,A, where B is an unassigned variable neighbor of A. (AC-3 is still normal)\n\nChronological backtracing back ups to the preceding variable and tries a new value when a branch fails. backjumping backtracks to the most recent assignment in the conflict set ( a set of variables responsible for making a value of some variable impossible).  A backjumping algorithm that uses conflict sets defined in this way is called conflict-directed backjumping.\n\nConstraint learning is finding a minimum set of variables from the conflict set that causes the problem.\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search algorithms solve CSPs well because  They use a complete-state formulation (each state assigns a value to every variable, and the search changes the value of one variable at a time.)\n\nselect the value that results in the minimum number of conflicts with other variables—the min-conflicts heuristic.\n\n constraint weighting aims to concentrate the search on the important constraints. where each constraing is set to 1. At each step, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then incrementing the weight of each constraint that is violated by the current assignment. \n\nlocal search can be used in an online setting (when the problem changes)\n\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n The structure of such CSPs can also help. with coloring australia, tasmania isnt connected to the mainland, so it is an independent subproblem. They then talk about topological sort. which can be thought of as DFS but each node is in reverse order of finish time (i think) (good for solving a tree-structured CSP). Cutset conditioning can help reduce a constraint graph to a tree\n\nTree-structured problems can be solved in linear time. Cutset conditioning can reduce a general CSP to a tree-structured one if a small cutset can be found. Tree decomposition transforms the CSP into a tree of subproblems and are efficient if the tree width of the constraint graph is small (the minimum width among all its tree decompositions)  combine cutset conditioning with tree decomposition for a good tradeoff. \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 The central component of a knowledge-based agent is its knowledge base, or KB. A\nknowledge base is a set of sentences. A given sentence is an axiom Some new sentences can be inferred (deriving new sentences from old)\nStarting with an empty knowledge base, the agent designer can TELL sentences until the agent can operate in its environment (declarative), while procedural approach encodes behaviors as code \n\n## AIMA Chapter 7.2 The Wumpus World\n wumpus world hehe!\n\n## AIMA Chapter 7.3 Logic\n knowledge bases consist of sentences made up of a syntax. model is a \"possible word\". if a sentence a is true in model m, we say m satisfies a or m is a model of a. M(a) means all models of a. For entailment (sentence follows logically from another sentence). a |= b. a entails b (iff in every model where a is true, b is also true). An inference algorithm that derives only entailed sentences is called sound or truthpreserving. if an inference algorithm i can derive alpha from KB, we write KB ⊢_i alpha. There is also completeness, it is complete if it can derive any sentence that is entailed. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n propositional logic. ¬W is the negation of W (both are literals). A conjunction is used with a ^ (carrot) a disjunction uses V. (A ^ B) V C is a disjunction. (A^B) is a disjunct as well as C. All this stuff is from 160 man. just study it \n\n## AIMA 7.5 Propositional Theorem Proving\n α ≡ β if and only if α ⊨ β and β ⊨ α. logical equivalence. A sentence expressed as a conjunction of clauses is said to be in conjunctive normal form or CNF. Horn clause, which is a disjunction of literals of which at most one is positive.  I have stopped caring :) \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": {}
        }
      ]
    }
  ]
}