{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Daniel_Schwartz_midterm_notes.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "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": "775a141a-9c17-42e3-9829-569285952fda"
      },
      "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": null,
      "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": "783a4d41-1c79-4406-b9d6-f7935c59cc4d"
      },
      "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": null,
      "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": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "There are two main schools of thought on desired AI behaviour: human vs rational. \\\n",
        "The turing test is designed to determine if a computer could pass as a human to some interrogator. \\\n",
        "To pass a turing test, a computer would need natural language processing, knowledge representation, \\\n",
        "automated reasoning, and machine learning.  A total turing test would require interations with objects \\\n",
        "in the real world and the computer would need computer vision and robotics.  These skills needed for \\\n",
        "a turing test allow an agent to act rationally.  The rational-agent approach to AI is more general than \\\n",
        "other approaches and it is more easily defined mathematically.  AI focuses on the study of agents that \\\n",
        "'do the right thing' given a defined objective and this is often referred to as the standard model. \\\n",
        "Perfect rationality is not always feasible due to computational demands so sometimes limited rationality \\\n",
        "is employed.  The standard model is a time tested approach, but it requires a fully specified objective \\\n",
        "which is not always easy to define.  A machine pursuing a fixed objective might behave in unanticipated \\\n",
        "ways which don't align with the human objective.\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "John Searle introduced the idea of weak AI - machines that act as if there were intelligent \\\n",
        "and strong AI (general AI) - machines that actually think consciously.  A turing test requires a program to \\\n",
        "converse with an interrogater for 5 minutes (through typed messages).  The interrogator then guesses whether \\\n",
        "it was conversing with a human or computer.  If the interrogator is fooled 30% of the time, then the computer \\\n",
        "passes the test.  Many chatbots (ELIZA, MGONZ, CYBERLOVER) have fooled people, but it is still unclear if any program has passed the turing \\\n",
        "test.  A chatbot claiming to be a Ukrainian boy (Eugene Goostman) fooled 33% of untrained interrogators.  The \\\n",
        "backstory of the chatbot helped to explain errors.  Standards for what AI passes is somewhat of a moving goalpost.\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "In the Chinese room argument by Searle, a human only fluent in English is given a rulebook of \\\n",
        "English instructions.  He is passed indecipherable Chinese symbols, looks them up in the rulebook, and \\\n",
        "writes back with symbols from his instructions.  What he passes back is intelligent Chinese responses, \\\n",
        "but he has no understanding of Chinese.  This argument states that computers may generate intelligent \\\n",
        "responses, but they have no understanding of the true meaning.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "There are many existing examples of agents. A human is an agent with eyes/ears/etc \\\n",
        "for sensors and hands/legs/etc for actuators. A software agent might take file contents/input devices \\\n",
        "as sensory input and act by writing to files or output devices. An agent's environment could be as broad \\\n",
        "as the entire universe.  An agent will choose an action based on its knowledge and percept sequence, but \\\n",
        "not based on anything that it has not yet percieved.  A simple example of an agent is a robotic vacuum cleaner \\\n",
        "agent in a world consisting of squares that are clean or dirty.  The agent can percieve its current location \\\n",
        "and whether or not that square is clean or dirty.  The actions available are move, clean the dirt, or do nothing. \\\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "The notion of consequentialism means that we evalutate an agent's behaviour given the \\\n",
        "consequences that follow from some actions.  The agent should perform actions that lead to a desirable \\\n",
        "outcome.  Desirability can be defined using a performance measure.  A rational agent will seek to maximize \\\n",
        "its peformance measure.  A poorly chosen performance measure can lead to undesirable results.  The performance \\\n",
        "measure should be chosen based on the end goal and not on how you think the agent should behave.  The current \\\n",
        "rational choice for an agent will depend on its performance measure, prior knowledge, actions, and current percept \\\n",
        "sequence.  Rationality does not require omniscience (knowing the actual outcome of its actions) but instead \\\n",
        "it maximizes expected performance and depends only its percept sequence and knowledge to date.  Agents must \\\n",
        "explore and gather information to learn new things.  It is rare but possible that an environment is completely \\\n",
        "known and in this case an agent can simply act correctly. A rational agent should be autonomous, meaning that \\\n",
        "it can learn as a means of compensating for missing/incorrect knowledge.  \n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "Task environments can be virual or physical. \\\n",
        "In a fully observable environment, an agent can see the full state of the environment at any given time. \\\n",
        "Otherwise, the envirnoment is partially observable which could be due to missing or limited sensor data. \\\n",
        "Environments can be single-agent or they can contain more agents in a multi-agent environment.  Multi-agent \\\n",
        "environments can be either competative or cooperative.  In a deterministic environment, the result of an \\\n",
        "action is always known, but if there is uncertaintiy, it is non-deterministic.  In a stochastic environment, \\\n",
        "it can be modeled using probabilities. In an episodic environment, each percept and resulting action is an \\\n",
        "episode in itself whereas in a sequential environemnt, the previous percepts and actions are taken into account. \\\n",
        "If an environment is constantly chaning then it is dynamic, otherwise a turn based environment would be static. \\\n",
        "A discrete environment has a finite number of states otherwise actions and states transition smoothly over time \\\n",
        "in a continuous environment.  In a known environment, whether or not the agent is aware, all outcomes for a given \\\n",
        "action are given.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "An important distinction: the agent program takes the current percept as input whereas the function may depend \\\n",
        "on the entire percept history.  Suppose we have a table-driven agent program, the table size would grow exponentially \\\n",
        "and would easily become intractible given the space requirement and the time needed to create such a table. \\\n",
        "The biggest challeng in AI is writing an agent program that produces rational behaviour from a smallish table. \\\n",
        "Simple reflex agents are simple, but they only really work if the environment is fully observable. \\\n",
        "A goal-based agent will choose actions inorder to achieve some goal.  This often involves searching and planning. \\\n",
        "A utility-based agent will choose an action in order to maximize its expected utility (average utility given some probailities). \\\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive through sensors and act in an environment through actuators\",\n",
        "\"rational agent\" : \"agent that seeks to achieve best expected outcome (maximize performance measure) given percept sequence and knowledge\",\n",
        "\"percept\" : \"the content percieved through sensors\",\n",
        "\"percept sequence\" : \"the history of all percepts percieved by an agent\",\n",
        "\"agent function\" : \"mathematical map from a particular percept sequence to an action\",\n",
        "\"agent program\" : \"the acutal concrete implementation of an agent function\",\n",
        "\"agent architecture\" : \"the physical computing device with actuators/sensors that runs the agent program\",\n",
        "\"performance measure\" : \"evaluation of any sequence of states for an enviroment\",\n",
        "\"task environment\" : \"combination of PEAS (performance, environment, actuators, sensors)\",\n",
        "\"simple reflex agent\" : \"selection action only based on current percept (no history)\",\n",
        "\"transition model\" : \"keeps track of how the world changes over time\", \n",
        "\"sensor model\" : \"how the world's state is percived by the agent\",\n",
        "\"model-based agent\" : \"uses both a transition model and sensor model to track the world's state (internal state)\",\n",
        "\"utility function\" : \"an internal function for the external performance measure\"\n",
        "\n",
        "}\n"
      ],
      "execution_count": null,
      "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": "fce7bb79-dcb5-4814-b564-d057dc6f6961"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nThere are two main schools of thought on desired AI behaviour: human vs rational. The turing test is designed to determine if a computer could pass as a human to some interrogator. To pass a turing test, a computer would need natural language processing, knowledge representation, automated reasoning, and machine learning.  A total turing test would require interations with objects in the real world and the computer would need computer vision and robotics.  These skills needed for a turing test allow an agent to act rationally.  The rational-agent approach to AI is more general than other approaches and it is more easily defined mathematically.  AI focuses on the study of agents that 'do the right thing' given a defined objective and this is often referred to as the standard model. Perfect rationality is not always feasible due to computational demands so sometimes limited rationality is employed.  The standard model is a time tested approach, but it requires a fully specified objective which is not always easy to define.  A machine pursuing a fixed objective might behave in unanticipated ways which don't align with the human objective.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\nJohn Searle introduced the idea of weak AI - machines that act as if there were intelligent and strong AI (general AI) - machines that actually think consciously.  A turing test requires a program to converse with an interrogater for 5 minutes (through typed messages).  The interrogator then guesses whether it was conversing with a human or computer.  If the interrogator is fooled 30% of the time, then the computer passes the test.  Many chatbots (ELIZA, MGONZ, CYBERLOVER) have fooled people, but it is still unclear if any program has passed the turing test.  A chatbot claiming to be a Ukrainian boy (Eugene Goostman) fooled 33% of untrained interrogators.  The backstory of the chatbot helped to explain errors.  Standards for what AI passes is somewhat of a moving goalpost.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nIn the Chinese room argument by Searle, a human only fluent in English is given a rulebook of English instructions.  He is passed indecipherable Chinese symbols, looks them up in the rulebook, and writes back with symbols from his instructions.  What he passes back is intelligent Chinese responses, but he has no understanding of Chinese.  This argument states that computers may generate intelligent responses, but they have no understanding of the true meaning.\n\n\n## AIMA 2.1 Agents and Environments\n\nThere are many existing examples of agents. A human is an agent with eyes/ears/etc for sensors and hands/legs/etc for actuators. A software agent might take file contents/input devices as sensory input and act by writing to files or output devices. An agent's environment could be as broad as the entire universe.  An agent will choose an action based on its knowledge and percept sequence, but not based on anything that it has not yet percieved.  A simple example of an agent is a robotic vacuum cleaner agent in a world consisting of squares that are clean or dirty.  The agent can percieve its current location and whether or not that square is clean or dirty.  The actions available are move, clean the dirt, or do nothing. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nThe notion of consequentialism means that we evalutate an agent's behaviour given the consequences that follow from some actions.  The agent should perform actions that lead to a desirable outcome.  Desirability can be defined using a performance measure.  A rational agent will seek to maximize its peformance measure.  A poorly chosen performance measure can lead to undesirable results.  The performance measure should be chosen based on the end goal and not on how you think the agent should behave.  The current rational choice for an agent will depend on its performance measure, prior knowledge, actions, and current percept sequence.  Rationality does not require omniscience (knowing the actual outcome of its actions) but instead it maximizes expected performance and depends only its percept sequence and knowledge to date.  Agents must explore and gather information to learn new things.  It is rare but possible that an environment is completely known and in this case an agent can simply act correctly. A rational agent should be autonomous, meaning that it can learn as a means of compensating for missing/incorrect knowledge.  \n\n\n## AIMA 2.3 The Nature of Environments\n\nTask environments can be virual or physical. In a fully observable environment, an agent can see the full state of the environment at any given time. Otherwise, the envirnoment is partially observable which could be due to missing or limited sensor data. Environments can be single-agent or they can contain more agents in a multi-agent environment.  Multi-agent environments can be either competative or cooperative.  In a deterministic environment, the result of an action is always known, but if there is uncertaintiy, it is non-deterministic.  In a stochastic environment, it can be modeled using probabilities. In an episodic environment, each percept and resulting action is an episode in itself whereas in a sequential environemnt, the previous percepts and actions are taken into account. If an environment is constantly chaning then it is dynamic, otherwise a turn based environment would be static. A discrete environment has a finite number of states otherwise actions and states transition smoothly over time in a continuous environment.  In a known environment, whether or not the agent is aware, all outcomes for a given action are given.\n\n\n## AIMA 2.4 The Structure of Agents\n\nAn important distinction: the agent program takes the current percept as input whereas the function may depend on the entire percept history.  Suppose we have a table-driven agent program, the table size would grow exponentially and would easily become intractible given the space requirement and the time needed to create such a table. The biggest challeng in AI is writing an agent program that produces rational behaviour from a smallish table. Simple reflex agents are simple, but they only really work if the environment is fully observable. A goal-based agent will choose actions inorder to achieve some goal.  This often involves searching and planning. A utility-based agent will choose an action in order to maximize its expected utility (average utility given some probailities). \n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive through sensors and act in an environment through actuators\n* **Rational agent** - agent that seeks to achieve best expected outcome (maximize performance measure) given percept sequence and knowledge\n* **Percept** - the content percieved through sensors\n* **Percept sequence** - the history of all percepts percieved by an agent\n* **Agent function** - mathematical map from a particular percept sequence to an action\n* **Agent program** - the acutal concrete implementation of an agent function\n* **Agent architecture** - the physical computing device with actuators/sensors that runs the agent program\n* **Performance measure** - evaluation of any sequence of states for an enviroment\n* **Task environment** - combination of PEAS (performance, environment, actuators, sensors)\n* **Simple reflex agent** - selection action only based on current percept (no history)\n* **Transition model** - keeps track of how the world changes over time\n* **Sensor model** - how the world's state is percived by the agent\n* **Model-based agent** - uses both a transition model and sensor model to track the world's state (internal state)\n* **Utility function** - an internal function for the external performance measure\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 = \"\"\"The list slice operator [:] returns a new list (shallow copy). Lists can be concatenated \\\n",
        "using the + operator but dictonaries cannot.  Dictionary keys cannot be mutable. Strings and tuples are not \\\n",
        "mutable. The elements in tuples can be lists or other mutables.  Tuples and lists can contain mixed types. \\\n",
        "String formatting using '%' is allowed. 'is' operator is used to check if two objects are the same instance. \\\n",
        "*args can be used in a function to take a variable number of arguments and *kwargs can be used to take a dict \\\n",
        "as a variable number of keyword arguments.  Python is dynamically scoped so variables take most current value. \\\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "\"magic methods\" : \"user-defined classes can behave like built in and can implement operator overloading\",\n",
        "\"duck typing\" : \"establish suitability of an object depending on the methods available (duck defense)\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 294
        },
        "outputId": "751ce7d7-597d-46d2-fd40-01b97cd27889"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\nThe list slice operator [:] returns a new list (shallow copy). Lists can be concatenated using the + operator but dictonaries cannot.  Dictionary keys cannot be mutable. Strings and tuples are not mutable. The elements in tuples can be lists or other mutables.  Tuples and lists can contain mixed types. String formatting using '%' is allowed. 'is' operator is used to check if two objects are the same instance. *args can be used in a function to take a variable number of arguments and *kwargs can be used to take a dict as a variable number of keyword arguments.  Python is dynamically scoped so variables take most current value. \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n* **Magic methods** - user-defined classes can behave like built in and can implement operator overloading\n* **Duck typing** - establish suitability of an object depending on the methods available (duck defense)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "A problem solving agent can follow a four-phase problem solving process: goal formulation - \\\n",
        "finding some goal, problem formulation - a description of the states/actions needed to reach the goal, \\\n",
        "search - simulates a sequence of actions until one is found that reaches the goal, execute - the agent \\\n",
        "performs the actions found in the solution.  This requires that an environment be fully observable, \\\n",
        "deterministic, and known. A search problem consists of: a state space, an initial state, goal state/s, \\\n",
        "actions, a transition model, and an action cost function.  A solution consists of a path made up of actions \\\n",
        "and an optimal solution is the lowest cost path.  The state space can be modeled as a graph with states as \\\n",
        "nodes and action as edges.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "Some example standard search problems: vaccum world, sokoban puzzle (push boxes on grid to designated \\\n",
        "locations), sliding-tile puzzle (8-puzzle).  Some example real world search problems: route-finding problems, \\\n",
        "touring problems/traveling salesperson problem (visit each city and minimize cost), VLSI layout (circuit layout), \\\n",
        "robot navigation, automatic assembly sequencing.\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "The state space defines all possible states while the search tree describes paths between states. \\\n",
        "Best-first-search uses a priority queue and adds nodes to the frontier if they have not been reached \\\n",
        "or a lower cost path is found.  A cycle is a redundant path and can lead to an infinite search tree. \\\n",
        "A algorithm's performance can be measured based on: completeness, cost optimality, time complexity, and \\\n",
        "space complexity.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "Breadth-first-search could be implemented as best-first-search with an evaluation function such that it is\\\n",
        "simply the depth of the node.  Breadth-first-search can early goal test when the node is added to the frontier \\\n",
        "whereas best-first-search has to late goal test when a node is popped from the frontier.  Breadth-first-search \\\n",
        "is cost optimal if each action has the same cost.  Both space and time complexity for breadth-first-search are\n",
        "$O(b^d)$.  Uniform-cost-search performs goal test when a node is popped from the frontier.  Uniform-cost-search \\\n",
        "is complete and cost-optimal, but the space/time complexity is based on $C*$ which is the cost of the \\\n",
        "optimal solution and $e$ the cost of each action as $O(b^{1+{C*/e}})$ which in the worst case is far greater than $b^d$. \\ \n",
        "DFS could be implemented using best-first where the eval function is the negated depth.  DFS is not cost optimal \\\n",
        "as it will just return the first solution found.  It is also incomplete because on an infinite state space it can \\\n",
        "continually go down an infinite path.  DFS is memory efficient though and has a space complexity of $O(bm)$ where \\\n",
        "$m$ is the max depth of the tree.  For this reason, DFS and its variants are widely used in AI. Depth-limited search \\\n",
        "has a time complexity of $O(b^l)$ and space of $O(bl)$ but it is still not complete if we chose some $l<d$. \\\n",
        "Iterative deepening is complete and optimal for same cost problems like BFS.  However, it runs in $O(b^d)$ with \\\n",
        "a space complexity of $O(bd)$ by not storing all nodes in memory.  IDDFS is a good choice for problems with a large \\\n",
        "search state space. Bidirectiional search is complete and optimal with space/time complexity of $O(b^{d/2})$.\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",
        "\"state space\" : \"all possible states for an environment\",\n",
        "\"transition model\" : \"determines what an action does\",\n",
        "\"action cost function\" : \"a numeric cost for taking some action which reflects the performance measure\",\n",
        "\"grid world\" : \"2D world made of cells, agents move between cells (vaccum world)\", \n",
        "\"search tree\" : \"graph of state space with various paths from an initial state (root)\",\n",
        "\"best-first-search\" : \"expand the node from the frontier with minimum value for some evaluation function\",\n",
        "\"graph search\" : \"checks for redundant paths as opposed to tree search which does not\",\n",
        "\"completeness\" : \"will the algorithm always find a solution if it exists\",\n",
        "\"cost optimality\" : \"will it find the solution with the lowest path cost\", \n",
        "\"time complexity\" : \"how long will it take to find a solution\",\n",
        "\"space complexity\" : \"how much space is needed to perform the search\", \n",
        "\"depth\" : \"$d$ the number of actions performed to reach an optimal solution\",\n",
        "\"branching factor\" : \"$b$ the number of children for a given node that need to be considered\",\n",
        "\"breadth-first-search\" : \"implemented using FIFO queue and is complete even on infinite search spaces\",\n",
        "\"uniform-cost-search\" : \"AI variant of Dijkstra's algorithm that finds min cost path given different costs\",\n",
        "\"depth-first-search\" : \"expands the deepest node in the frontier first using LIFO stack\",\n",
        "\"backtracking search\" : \"uses less memory than DFS by only generating only one child at a time $O(m)$\",\n",
        "\"depth-limited search\" : \"Run DFS with some limit $l$ to prevent following an infinite path\",\n",
        "\"iterative deepening search\" : \"Runs a series of depth-limited searches increasing the limit on each iteration\",\n",
        "\"bidirectional search\" : \"searches both forward from the start and backward from the goal, hoping they will meet\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "90cfd632-860d-47df-c01e-15770f5fecb5"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nA problem solving agent can follow a four-phase problem solving process: goal formulation - finding some goal, problem formulation - a description of the states/actions needed to reach the goal, search - simulates a sequence of actions until one is found that reaches the goal, execute - the agent performs the actions found in the solution.  This requires that an environment be fully observable, deterministic, and known. A search problem consists of: a state space, an initial state, goal state/s, actions, a transition model, and an action cost function.  A solution consists of a path made up of actions and an optimal solution is the lowest cost path.  The state space can be modeled as a graph with states as nodes and action as edges.\n\n\n## AIMA Chapter 3.2 Example Problems\n\nSome example standard search problems: vaccum world, sokoban puzzle (push boxes on grid to designated locations), sliding-tile puzzle (8-puzzle).  Some example real world search problems: route-finding problems, touring problems/traveling salesperson problem (visit each city and minimize cost), VLSI layout (circuit layout), robot navigation, automatic assembly sequencing.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nThe state space defines all possible states while the search tree describes paths between states. Best-first-search uses a priority queue and adds nodes to the frontier if they have not been reached or a lower cost path is found.  A cycle is a redundant path and can lead to an infinite search tree. A algorithm's performance can be measured based on: completeness, cost optimality, time complexity, and space complexity.\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBreadth-first-search could be implemented as best-first-search with an evaluation function such that it issimply the depth of the node.  Breadth-first-search can early goal test when the node is added to the frontier whereas best-first-search has to late goal test when a node is popped from the frontier.  Breadth-first-search is cost optimal if each action has the same cost.  Both space and time complexity for breadth-first-search are\n$O(b^d)$.  Uniform-cost-search performs goal test when a node is popped from the frontier.  Uniform-cost-search is complete and cost-optimal, but the space/time complexity is based on $C*$ which is the cost of the optimal solution and $e$ the cost of each action as $O(b^{1+{C*/e}})$ which in the worst case is far greater than $b^d$. \\ \nDFS could be implemented using best-first where the eval function is the negated depth.  DFS is not cost optimal as it will just return the first solution found.  It is also incomplete because on an infinite state space it can continually go down an infinite path.  DFS is memory efficient though and has a space complexity of $O(bm)$ where $m$ is the max depth of the tree.  For this reason, DFS and its variants are widely used in AI. Depth-limited search has a time complexity of $O(b^l)$ and space of $O(bl)$ but it is still not complete if we chose some $l<d$. Iterative deepening is complete and optimal for same cost problems like BFS.  However, it runs in $O(b^d)$ with a space complexity of $O(bd)$ by not storing all nodes in memory.  IDDFS is a good choice for problems with a large search state space. Bidirectiional search is complete and optimal with space/time complexity of $O(b^{d/2})$.\n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - all possible states for an environment\n* **Transition model** - determines what an action does\n* **Action cost function** - a numeric cost for taking some action which reflects the performance measure\n* **Grid world** - 2D world made of cells, agents move between cells (vaccum world)\n* **Search tree** - graph of state space with various paths from an initial state (root)\n* **Best-first-search** - expand the node from the frontier with minimum value for some evaluation function\n* **Graph search** - checks for redundant paths as opposed to tree search which does not\n* **Completeness** - will the algorithm always find a solution if it exists\n* **Cost optimality** - will it find the solution with the lowest path cost\n* **Time complexity** - how long will it take to find a solution\n* **Space complexity** - how much space is needed to perform the search\n* **Depth** - $d$ the number of actions performed to reach an optimal solution\n* **Branching factor** - $b$ the number of children for a given node that need to be considered\n* **Breadth-first-search** - implemented using FIFO queue and is complete even on infinite search spaces\n* **Uniform-cost-search** - AI variant of Dijkstra's algorithm that finds min cost path given different costs\n* **Depth-first-search** - expands the deepest node in the frontier first using LIFO stack\n* **Backtracking search** - uses less memory than DFS by only generating only one child at a time $O(m)$\n* **Depth-limited search** - Run DFS with some limit $l$ to prevent following an infinite path\n* **Iterative deepening search** - Runs a series of depth-limited searches increasing the limit on each iteration\n* **Bidirectional search** - searches both forward from the start and backward from the goal, hoping they will meet\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "In finite spaces, greed best-first is complete however this is not the case for infinite spaces. \\\n",
        "A good heuristic can reduce the time/space complexity of greedy to almost $O(bm)$.  A* search \\\n",
        "relies on admissibility in order to produce a cost optimal solution. If a heuristic is consistent \\\n",
        "then it is also admissable (not vice versa) and the first time we reach a state it will be the optimal \\\n",
        "path to that state.  This means states will only be added once to the frontier and never will be updated. \\\n",
        "If a heuristic is inadmissable, then A* may or may not return an optimal solution.  A* will expand all \\\n",
        "nodes with $f(n)$ less than the optimal cost $C*$, no nodes greater than $C*$, and may expand nodes with \\\n",
        "cost equal to $C*$ before reaching the goal.  With a consistent heuristic A* is also optimally efficient. \\\n",
        "Weighted A* is more similar to greedy best-first and could be called 'somewhat greedy'.  Memory usage is \\\n",
        "one main drawback of A* search.  There are algorithms which address this issue.  IDA* and RBFS both use \\\n",
        "less memory but they actually use too little memory which is a problem.  To fix this MA* and SMA* are used \\\n",
        "to take advantage to the available amount of memory.  Bidirectional search is sometimes more efficient, but \\\n",
        "it also might not be.  With a good heuristic, A* is generally just as good.  With an average heuristic, \\\n",
        "bidirectional search may perform better.\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "The quality of a heuristic can be characterized by its effective branching factor.  This \\\n",
        "is usually consistent among all not trivial problem instances.  Another way to characterize a heuristic \\\n",
        "is with its effective depth which compares total search cost to the uninformed search cost. Given two \\\n",
        "heuristics if $h_2(n) \\geq h_1(n)$ then $h_2$ dominates $h_1$ which means that $h_2$ will not expand more \\\n",
        "nodes than $h_1$.  If it is consitent and not computationally expensive, then it is better to use a heuristic \\\n",
        "function with higher values. Relaxed problems can produce better solutions due to shortcuts from added edges. \\\n",
        "The cost of an optimal solution in the relaxed problem can be used as an admissable heuristic in the original \n",
        "problem.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"heuristic function\" : \"an estimate cost of the cheapest path from some state to the goal\", \n",
        "\"informed search\" : \"find solutions more efficiently using domain-specific info\",\n",
        "\"greedy best-first search\" : \"expand the node with the lowest heuristic cost (seemingly closest to goal) $f(n) = h(n)$\",\n",
        "\"A* search\" : \"most common informed search, combines heuristic cost with path cost from starting state $f(n) = g(n) + h(n)$\",\n",
        "\"admissible heuristic\" : \"optimistic, never overestimates the cost of reaching the goal\",\n",
        "\"consistency\" : \"if every node $n$ and succesor $n'$, $h(n) \\leq c(n, a, n') + h(n')$ then $h(n)$ consistent\",\n",
        "\"contours\" : \"shows increasing concentric bands of $f(n)$ costs\",\n",
        "\"monotonic\" : \"path cost always increases monotonically along a path\",\n",
        "\"optimally efficient\" : \"one algorithm could get lucky and choose the optimal solution first\",\n",
        "\"weighted A* search\" : \"the heuristic value is weighted such that $f(n) = g(n) + W * h(n)$ for some $W > 1$\",\n",
        "\"Beam search\" : \"conserves memory usage by limiting the size of the frontier but it is incomplete and sub optimal\",\n",
        "\"Iterative-deepening A*\" : \"similar to IDDFS and reduces memory need by A* by not storing all states in memory\",\n",
        "\"Recursive Best-First\" : \"mimics the standard best-first search, but with linear space and slightly more efficient than IDA*\",\n",
        "\"Memory-bounded A*\" : \"(also simplified SMA*) determines the available memory and runs A* until memory full, then drops worst node\",\n",
        "\"relaxed problem\" : \"a superset of the orignal state space with fewer restrictions on the actions\",\n",
        "\"pattern databases\" : \"the idea of storing the exact cost of a solution to every possible subproblem\",\n",
        "\"precomputation\" : \"time-consuming but precomputing optimal path costs can save massive time on many queries\",\n",
        "\"landmark points\" : \"we can precompute the optimal path from a smaller set of landmark points\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 880
        },
        "cellView": "form",
        "outputId": "ed5a55ff-1138-44e1-eb34-1c7e0c920733"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nIn finite spaces, greed best-first is complete however this is not the case for infinite spaces. A good heuristic can reduce the time/space complexity of greedy to almost $O(bm)$.  A* search relies on admissibility in order to produce a cost optimal solution. If a heuristic is consistent then it is also admissable (not vice versa) and the first time we reach a state it will be the optimal path to that state.  This means states will only be added once to the frontier and never will be updated. If a heuristic is inadmissable, then A* may or may not return an optimal solution.  A* will expand all nodes with $f(n)$ less than the optimal cost $C*$, no nodes greater than $C*$, and may expand nodes with cost equal to $C*$ before reaching the goal.  With a consistent heuristic A* is also optimally efficient. Weighted A* is more similar to greedy best-first and could be called 'somewhat greedy'.  Memory usage is one main drawback of A* search.  There are algorithms which address this issue.  IDA* and RBFS both use less memory but they actually use too little memory which is a problem.  To fix this MA* and SMA* are used to take advantage to the available amount of memory.  Bidirectional search is sometimes more efficient, but it also might not be.  With a good heuristic, A* is generally just as good.  With an average heuristic, bidirectional search may perform better.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nThe quality of a heuristic can be characterized by its effective branching factor.  This is usually consistent among all not trivial problem instances.  Another way to characterize a heuristic is with its effective depth which compares total search cost to the uninformed search cost. Given two heuristics if $h_2(n) \\geq h_1(n)$ then $h_2$ dominates $h_1$ which means that $h_2$ will not expand more nodes than $h_1$.  If it is consitent and not computationally expensive, then it is better to use a heuristic function with higher values. Relaxed problems can produce better solutions due to shortcuts from added edges. The cost of an optimal solution in the relaxed problem can be used as an admissable heuristic in the original \nproblem.\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Heuristic function** - an estimate cost of the cheapest path from some state to the goal\n* **Informed search** - find solutions more efficiently using domain-specific info\n* **Greedy best-first search** - expand the node with the lowest heuristic cost (seemingly closest to goal) $f(n) = h(n)$\n* **A* search** - most common informed search, combines heuristic cost with path cost from starting state $f(n) = g(n) + h(n)$\n* **Admissible heuristic** - optimistic, never overestimates the cost of reaching the goal\n* **Consistency** - if every node $n$ and succesor $n'$, $h(n) \\leq c(n, a, n') + h(n')$ then $h(n)$ consistent\n* **Contours** - shows increasing concentric bands of $f(n)$ costs\n* **Monotonic** - path cost always increases monotonically along a path\n* **Optimally efficient** - one algorithm could get lucky and choose the optimal solution first\n* **Weighted a* search** - the heuristic value is weighted such that $f(n) = g(n) + W * h(n)$ for some $W > 1$\n* **Beam search** - conserves memory usage by limiting the size of the frontier but it is incomplete and sub optimal\n* **Iterative-deepening a*** - similar to IDDFS and reduces memory need by A* by not storing all states in memory\n* **Recursive best-first** - mimics the standard best-first search, but with linear space and slightly more efficient than IDA*\n* **Memory-bounded a*** - (also simplified SMA*) determines the available memory and runs A* until memory full, then drops worst node\n* **Relaxed problem** - a superset of the orignal state space with fewer restrictions on the actions\n* **Pattern databases** - the idea of storing the exact cost of a solution to every possible subproblem\n* **Precomputation** - time-consuming but precomputing optimal path costs can save massive time on many queries\n* **Landmark points** - we can precompute the optimal path from a smaller set of landmark points\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 = \"\"\"In adversarial search, we assume our opponent is actively trying to defeat us.  \\\n",
        "Perfect information, zero-sum games are often studied because they are deterministic, two-player, \\\n",
        "turn-taking games that are fully observable.\"\"\"\n",
        "chapter5_2 = \"\"\"The max player is trying to find a sequence of actions that \\\n",
        "lead to a win, but the min player is trying to prevent that.  Max assumes that min is playing optimally \\\n",
        "and vice versa. The time complexity for minimax is $O(b^m)$ and the space complexity is $O(bm)$ unless \\\n",
        "the algorithm generates values one at a time as $O(m)$.  In the best case alpha-beta will only examine $O(b^{m/2})$ \\\n",
        "nodes.  In games with too many states to explore, either a Type A or Type B strategy is employed.  In Type A \\\n",
        "all moves are considered up to a certain depth of the tree where a heuristic is then applied.  In Type B \\\n",
        "only promising moves are follow as far a is possible, and then bad looking moves are ignored.\n",
        "```\n",
        "function ALPHA-BETA-SEARCH(game,state) returns action\n",
        "  player = game.TO-MOVE(state)\n",
        "  value, move = MAX-Value(game,state,-inf,+inf)\n",
        "  return move\n",
        "\n",
        "function MAX-VALUE(game,state,alpha,beta) returns (utility, move)\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state,player),null\n",
        "  v = -inf\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2,a2 = MIN-VALUE(game,game.RESULT(state,a),alpha,beta)\n",
        "    if v2 > v then\n",
        "      v,move = v2,a\n",
        "      alpha = max(alpha,v)\n",
        "    if v >= beta then return v,move\n",
        "  return v,move\n",
        "\n",
        "function MIN-VALUE(game,state,alpha,beta) returns (utility, move)\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state,player),null\n",
        "  v = +inf\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2,a2 = MAX-VALUE(game,game.RESULT(state,a),alpha,beta)\n",
        "    if v2 < v then\n",
        "      v,move = v2,a\n",
        "      beta = min(beta,v)\n",
        "    if v <= alpha then return v,move\n",
        "  return v,move\n",
        "```\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"In a heuristic Alpha-Beta search, the search is cutoff as some depth and it is \\\n",
        "then evaluated for the utility of the states at that depth using some heuristic.  The heuristic \\\n",
        "that is applied is an estimate of the expected utility of a given state for the player that lies \\\n",
        "somewhere between a loss and a win.  Commonly these evaluation functions make some calculation based \\\n",
        "on the features of a state (probability that some feature leads to a win) to find the expected value. \\\n",
        "This kind of evalutation function is referred to as a weighted linear function.\"\"\"\n",
        "chapter5_5 = \"\"\"In the expectiminimax algorithm, chance nodes are added between min/max nodes that branch \\\n",
        "based on probabilities.  Expectiminimax has to consider all possible $n$ dice-rolls so it takes $O(b^mn^m)$. \\\n",
        "For this reason, expecitminimax trees are usually cutoff early and cannot run very deep.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"pruning\" : \"ignores large unnecessary portions of the search tree to improve efficiency\",\n",
        "\"evaluation function\" : \"based on the state of the game, an estimate of who is winning\",\n",
        "\"zero-sum game\" : \"there are no win-win outcomes and what is good for one player is bad for their opponent\",\n",
        "\"utility function\" : \"associates some numerical value to a player when a terminal state is reached\",\n",
        "\"game tree\" : \"a search tree containing all sequences of moves until a terminal state is reached\",\n",
        "\"minimax search\" : \"adversarial search algorithm for two players: min and max\",\n",
        "\"ply\" : \"some times move means both players take action, so ply refers to a single move by a single player\",\n",
        "\"minimax value\" : \"the ultility value for max of the current state\",\n",
        "\"alpha-beta pruning\" : \"prunes minimax tree given $alpha$: best choice so far for max, and $beta$: best choice so far for min\",\n",
        "\"killer moves\" : \"heuristic to try the best moves first in a move-ordering scheme\",\n",
        "\"transpositions\" : \"permutations of a move sequence that result in the same position\",\n",
        "\"cutoff test\" : \"cutoff the search at a certain depth or if a terminal state is reached\",\n",
        "\"quiescence search\" : \"only evaluates positions where no future move that will drastically change the utility\",\n",
        "\"horizon effect\" : \"unavoidable move that causes serioius damage but could be delayed\",\n",
        "\"singular extensions\" : \"allow clearly better move in a position even if the search would be cutoff, avoids horizon effect\",\n",
        "\"forward pruning\" : \"prune moves that appear to be bad, even though they might be good\",\n",
        "\"late move reduction\" : \"if move ordering is well done, then later moves are less likely to be good\",\n",
        "\"Monte Carlo tree search\" : \"instead of using heuristic, estimates average utilty given a number of simulations\",\n",
        "\"Stochastic games\" : \"introduce some element of unpredictability\",\n",
        "\"chance nodes\" : \"nodes inbetween min/max nodes that branch to new states based on some probability\",\n",
        "\"expectiminimax value\" : \"compute the expected value for a chance node as the sum of all outcomes weighted by their probability\",\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6c00ecc5-0994-406a-9f83-c72add0e3972"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nIn adversarial search, we assume our opponent is actively trying to defeat us.  Perfect information, zero-sum games are often studied because they are deterministic, two-player, turn-taking games that are fully observable.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nThe max player is trying to find a sequence of actions that lead to a win, but the min player is trying to prevent that.  Max assumes that min is playing optimally and vice versa. The time complexity for minimax is $O(b^m)$ and the space complexity is $O(bm)$ unless the algorithm generates values one at a time as $O(m)$.  In the best case alpha-beta will only examine $O(b^{m/2})$ nodes.  In games with too many states to explore, either a Type A or Type B strategy is employed.  In Type A all moves are considered up to a certain depth of the tree where a heuristic is then applied.  In Type B only promising moves are follow as far a is possible, and then bad looking moves are ignored.\n```\nfunction ALPHA-BETA-SEARCH(game,state) returns action\n  player = game.TO-MOVE(state)\n  value, move = MAX-Value(game,state,-inf,+inf)\n  return move\n\nfunction MAX-VALUE(game,state,alpha,beta) returns (utility, move)\n  if game.IS-TERMINAL(state) then return game.UTILITY(state,player),null\n  v = -inf\n  for each a in game.ACTIONS(state) do\n    v2,a2 = MIN-VALUE(game,game.RESULT(state,a),alpha,beta)\n    if v2 > v then\n      v,move = v2,a\n      alpha = max(alpha,v)\n    if v >= beta then return v,move\n  return v,move\n\nfunction MIN-VALUE(game,state,alpha,beta) returns (utility, move)\n  if game.IS-TERMINAL(state) then return game.UTILITY(state,player),null\n  v = +inf\n  for each a in game.ACTIONS(state) do\n    v2,a2 = MAX-VALUE(game,game.RESULT(state,a),alpha,beta)\n    if v2 < v then\n      v,move = v2,a\n      beta = min(beta,v)\n    if v <= alpha then return v,move\n  return v,move\n```\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nIn a heuristic Alpha-Beta search, the search is cutoff as some depth and it is then evaluated for the utility of the states at that depth using some heuristic.  The heuristic that is applied is an estimate of the expected utility of a given state for the player that lies somewhere between a loss and a win.  Commonly these evaluation functions make some calculation based on the features of a state (probability that some feature leads to a win) to find the expected value. This kind of evalutation function is referred to as a weighted linear function.\n\n## AIMA Chapter 5.5 Stochastic Games\nIn the expectiminimax algorithm, chance nodes are added between min/max nodes that branch based on probabilities.  Expectiminimax has to consider all possible $n$ dice-rolls so it takes $O(b^mn^m)$. For this reason, expecitminimax trees are usually cutoff early and cannot run very deep.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Pruning** - ignores large unnecessary portions of the search tree to improve efficiency\n* **Evaluation function** - based on the state of the game, an estimate of who is winning\n* **Zero-sum game** - there are no win-win outcomes and what is good for one player is bad for their opponent\n* **Utility function** - associates some numerical value to a player when a terminal state is reached\n* **Game tree** - a search tree containing all sequences of moves until a terminal state is reached\n* **Minimax search** - adversarial search algorithm for two players: min and max\n* **Ply** - some times move means both players take action, so ply refers to a single move by a single player\n* **Minimax value** - the ultility value for max of the current state\n* **Alpha-beta pruning** - prunes minimax tree given $alpha$: best choice so far for max, and $beta$: best choice so far for min\n* **Killer moves** - heuristic to try the best moves first in a move-ordering scheme\n* **Transpositions** - permutations of a move sequence that result in the same position\n* **Cutoff test** - cutoff the search at a certain depth or if a terminal state is reached\n* **Quiescence search** - only evaluates positions where no future move that will drastically change the utility\n* **Horizon effect** - unavoidable move that causes serioius damage but could be delayed\n* **Singular extensions** - allow clearly better move in a position even if the search would be cutoff, avoids horizon effect\n* **Forward pruning** - prune moves that appear to be bad, even though they might be good\n* **Late move reduction** - if move ordering is well done, then later moves are less likely to be good\n* **Monte carlo tree search** - instead of using heuristic, estimates average utilty given a number of simulations\n* **Stochastic games** - introduce some element of unpredictability\n* **Chance nodes** - nodes inbetween min/max nodes that branch to new states based on some probability\n* **Expectiminimax value** - compute the expected value for a chance node as the sum of all outcomes weighted by their probability\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 = \"\"\"A constraint satisfaction problem consists of a set of variables $X$, a set of domains for each \\\n",
        "variable $D$, and a set of constraints $C$ that specify allowed combinations of variables.  A solution to \\\n",
        "a CSP problem is a complete assignment that is consistent.  CSP problems are NP-complete, but there are some \\\n",
        "subclasses which are efficiently solvable.  Map coloring is an example of a CSP problem.  Job scheduling is \\\n",
        "another example of a CSP problem.  In a binary CSP, only unary or binary constraints are used and they can \\\n",
        "be represented using a constraint graph.  Global constraints can be represented using a hypergraph or a dual \\\n",
        "graph transformation with multiple graphs containing binary constraints.\"\"\"\n",
        "chapter6_2 = \"\"\"AC-3 is the most popular algorithm to enforce arc-consistency:\n",
        "```\n",
        "function AC-3(csp) returns false if inconsistent and true otherwise\n",
        "  queue = all arcs in csp\n",
        "\n",
        "  while queue is not empty do\n",
        "    (X_i, X_j) = POP(queue)\n",
        "    if REVISE(csp, X_i, X_j) then\n",
        "      if size of D_i = 0 then return false\n",
        "      for each X_k in X_i.NEIGHBORS-{X_j} do\n",
        "        add (X_k, X_i) to queue\n",
        "  return true\n",
        "\n",
        "function REVISE(csp, X_i, X_j) returns true iff the domain of X_i is revised\n",
        "  revised = false\n",
        "  for each x in D_i do\n",
        "    if no value y in D_j allows (x,y) to satisfy constraint beetween X_i and X_j then\n",
        "      delete x from D_i\n",
        "      revised = true\n",
        "  return revised\n",
        "```\n",
        "Given domain size $d$ and $c$ constraints, AC-3 has a run time of $O(cd^3)$.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"It is possible that variables with multiple possible values still exist and executing \\\n",
        "the constraint propagation process.  This requires that we then search for a solution.  CSPs are commutative \\\n",
        "meaning the order of application does not matter.  A backtracking search is done to find a solution. \\\n",
        "Backtracking search will only keep a single state representation that it modifies rather than creating new ones. \\\n",
        "We can improve backtracking search with domain-independent heuristics.  It is a powerful techinque to \\\n",
        "interleave both strategies of inference and search.\"\"\"\n",
        "chapter6_4 = \"\"\"Local search is another strategy that can be employed in solving CSPs.  In a local search \\\n",
        "each state will assign a value to each variable and the search will change a single variable at a time. \\\n",
        "An assignment may violate constraints, so we pick a conflicting varaible at random and try to pick a new \\\n",
        "value that is closer to a solution.  This is usually picked using the min-conflicts heuristic.\"\"\"\n",
        "chapter6_5 = \"\"\"Finding connected components in the constraint graph will create independent subproblems \\\n",
        "for each CC where the solutions for each independent CSP do not have any relation to the other.  If a \\\n",
        "constraint graph is a tree, then any two variables are only connected by one path.  This allows for a linear \\\n",
        "time solution.  To solve a tree CSP, pick variables in topological sorted order and enforce directional arc \\\n",
        "consistency.  Non-tree CSPs can also benefit from this.  Given a subset of variables that forms a tree in a \\\n",
        "cycle cutset, this technique can be applied first.  Another way is through tree decomposition where the orignal \\\n",
        "graph is transformed into a tree with sets of variables as nodes.  This requires that: each variable is in at least \\\n",
        "one node, two variables connected by a constraint must appear in the same node with that constraint in at \\\n",
        "least one node, and a variable that appears in two nodes must appear in each node along the connecting path. \\\n",
        "The tree width in a decomposition is equal to one less than the size of its largest node.  Although CSPs with \\\n",
        "bounded tree width are solvable in poly time, finding a decoposition with minimal tree width is NP-hard.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"assignments\" : \"a value given to a variable that does not violate the constraints\",\n",
        "\"consistent\" : \"a legal assignment\",\n",
        "\"complete assignment\" : \"each variable is given a value\",\n",
        "\"linear constraints\" : \"problems where each variable appears in linear form can be solve using special algorithms\",\n",
        "\"nonlinear constraints\" : \"No algorithm exists that can solve nonlinear constraints of integer variables\",\n",
        "\"continuous domains\" : \"variables have continuous domains, common in real world like scheduling precise times\",\n",
        "\"linear programming\" : \"continuous domain CSP given contraints as linear equalities/inequalities\",\n",
        "\"unary constraint\" : \"some restriction on a single variable\",\n",
        "\"binary constraint\" : \"a restriction that relates two variables\",\n",
        "\"global constraint\" : \"a constraint that relates some arbitrary number of variables\",\n",
        "\"preference constraints\" : \"non-absolute constraints where some solutions are preferred leading to an optimal solution\",\n",
        "\"constraint propogation\" : \"reduce the legal values for a variable through constraints, which may reduce another variable, etc\",\n",
        "\"local consistency\" : \"each variable is a node in a graph with edges as constraints, enforcing local consistency removes inconsistent values\",\n",
        "\"node-consistent\" : \"all values in the domain of a node satisfy unary constraints\",\n",
        "\"arc-consistent\" : \"all values in the domain satisfy binary constraints\",\n",
        "\"path consistency\" : \"uses implicit inferred constraints to tighten binary constraints\",\n",
        "\"k-consistency\" : \"given $k$ variables, if $k-1$ variables have a consistent assignment, then the $k$th variable also must\",\n",
        "\"bounds propagation\" : \"a way to manage domains with an upper and lower bound\",\n",
        "\"backtracking search\" : \"A form of DFS used in CSPs that commonly interleaves with inference\",\n",
        "\"minimum-remaining-values\" : \"Heuristic that first picks the most contrained variable that is most likely to fail - powerful guide\",\n",
        "\"degree heuristic\" : \"First pick the variable that is most used in contraints on other unassigned variables - tiebreaker\",\n",
        "\"least-constraining-values\" : \"First pick the value that rules out the fewest choices - stay flexible\",\n",
        "\"forward checking\" : \"When a variable is assigned, perform inference by establishing arc consistency for it\",\n",
        "\"Maintaining Arc Consistency\" : \"Call AC-3 after an assignment on variables in arcs from unassigned neighbors and if AC-3 fails, we backtrack\",\n",
        "\"backjumping\" : \"go back to the most recent assignment in the conflicting set\",\n",
        "\"constraint learning\" : \"find a min set from the conflict set that creates the problem\", \n",
        "\"tabu search\" : \"maintain list of visited states that the algo cannot return to\",\n",
        "\"constraint weighting\" : \"technique to concentrate the search on the most important contraints through weights\",\n",
        "\"directional arc consistency\" : \"if for some ordering every $X_i$ is arc consistent with $X_j$ for all $j > i$\",\n",
        "\"symmetry-breaking constraint\" : \"Every consistent solution can be permuted to symetric solutions, we can enfore some ordering to prevent this\"\n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "92fb3d5b-95a2-4c1c-8dd0-5cf1d8edd61e"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nA constraint satisfaction problem consists of a set of variables $X$, a set of domains for each variable $D$, and a set of constraints $C$ that specify allowed combinations of variables.  A solution to a CSP problem is a complete assignment that is consistent.  CSP problems are NP-complete, but there are some subclasses which are efficiently solvable.  Map coloring is an example of a CSP problem.  Job scheduling is another example of a CSP problem.  In a binary CSP, only unary or binary constraints are used and they can be represented using a constraint graph.  Global constraints can be represented using a hypergraph or a dual graph transformation with multiple graphs containing binary constraints.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nAC-3 is the most popular algorithm to enforce arc-consistency:\n```\nfunction AC-3(csp) returns false if inconsistent and true otherwise\n  queue = all arcs in csp\n\n  while queue is not empty do\n    (X_i, X_j) = POP(queue)\n    if REVISE(csp, X_i, X_j) then\n      if size of D_i = 0 then return false\n      for each X_k in X_i.NEIGHBORS-{X_j} do\n        add (X_k, X_i) to queue\n  return true\n\nfunction REVISE(csp, X_i, X_j) returns true iff the domain of X_i is revised\n  revised = false\n  for each x in D_i do\n    if no value y in D_j allows (x,y) to satisfy constraint beetween X_i and X_j then\n      delete x from D_i\n      revised = true\n  return revised\n```\nGiven domain size $d$ and $c$ constraints, AC-3 has a run time of $O(cd^3)$.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nIt is possible that variables with multiple possible values still exist and executing the constraint propagation process.  This requires that we then search for a solution.  CSPs are commutative meaning the order of application does not matter.  A backtracking search is done to find a solution. Backtracking search will only keep a single state representation that it modifies rather than creating new ones. We can improve backtracking search with domain-independent heuristics.  It is a powerful techinque to interleave both strategies of inference and search.\n\n## AIMA Chapter 6.4 Local Search for CSPs\nLocal search is another strategy that can be employed in solving CSPs.  In a local search each state will assign a value to each variable and the search will change a single variable at a time. An assignment may violate constraints, so we pick a conflicting varaible at random and try to pick a new value that is closer to a solution.  This is usually picked using the min-conflicts heuristic.\n\n## AIMA Chapter 6.5 The Structure of Problems\nFinding connected components in the constraint graph will create independent subproblems for each CC where the solutions for each independent CSP do not have any relation to the other.  If a constraint graph is a tree, then any two variables are only connected by one path.  This allows for a linear time solution.  To solve a tree CSP, pick variables in topological sorted order and enforce directional arc consistency.  Non-tree CSPs can also benefit from this.  Given a subset of variables that forms a tree in a cycle cutset, this technique can be applied first.  Another way is through tree decomposition where the orignal graph is transformed into a tree with sets of variables as nodes.  This requires that: each variable is in at least one node, two variables connected by a constraint must appear in the same node with that constraint in at least one node, and a variable that appears in two nodes must appear in each node along the connecting path. The tree width in a decomposition is equal to one less than the size of its largest node.  Although CSPs with bounded tree width are solvable in poly time, finding a decoposition with minimal tree width is NP-hard.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Assignments** - a value given to a variable that does not violate the constraints\n* **Consistent** - a legal assignment\n* **Complete assignment** - each variable is given a value\n* **Linear constraints** - problems where each variable appears in linear form can be solve using special algorithms\n* **Nonlinear constraints** - No algorithm exists that can solve nonlinear constraints of integer variables\n* **Continuous domains** - variables have continuous domains, common in real world like scheduling precise times\n* **Linear programming** - continuous domain CSP given contraints as linear equalities/inequalities\n* **Unary constraint** - some restriction on a single variable\n* **Binary constraint** - a restriction that relates two variables\n* **Global constraint** - a constraint that relates some arbitrary number of variables\n* **Preference constraints** - non-absolute constraints where some solutions are preferred leading to an optimal solution\n* **Constraint propogation** - reduce the legal values for a variable through constraints, which may reduce another variable, etc\n* **Local consistency** - each variable is a node in a graph with edges as constraints, enforcing local consistency removes inconsistent values\n* **Node-consistent** - all values in the domain of a node satisfy unary constraints\n* **Arc-consistent** - all values in the domain satisfy binary constraints\n* **Path consistency** - uses implicit inferred constraints to tighten binary constraints\n* **K-consistency** - given $k$ variables, if $k-1$ variables have a consistent assignment, then the $k$th variable also must\n* **Bounds propagation** - a way to manage domains with an upper and lower bound\n* **Backtracking search** - A form of DFS used in CSPs that commonly interleaves with inference\n* **Minimum-remaining-values** - Heuristic that first picks the most contrained variable that is most likely to fail - powerful guide\n* **Degree heuristic** - First pick the variable that is most used in contraints on other unassigned variables - tiebreaker\n* **Least-constraining-values** - First pick the value that rules out the fewest choices - stay flexible\n* **Forward checking** - When a variable is assigned, perform inference by establishing arc consistency for it\n* **Maintaining arc consistency** - Call AC-3 after an assignment on variables in arcs from unassigned neighbors and if AC-3 fails, we backtrack\n* **Backjumping** - go back to the most recent assignment in the conflicting set\n* **Constraint learning** - find a min set from the conflict set that creates the problem\n* **Tabu search** - maintain list of visited states that the algo cannot return to\n* **Constraint weighting** - technique to concentrate the search on the most important contraints through weights\n* **Directional arc consistency** - if for some ordering every $X_i$ is arc consistent with $X_j$ for all $j > i$\n* **Symmetry-breaking constraint** - Every consistent solution can be permuted to symetric solutions, we can enfore some ordering to prevent this\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 = \"\"\"A knowledge-based agent must tell the knowledge base what it perceives \\\n",
        "and it must ask the knowledge base what action to be perform.  Then it tells the knowledge base \\\n",
        "which action was chosen and peforms the action.  In a declarative system, the agent starts with an \\\n",
        "empty knowledge base and is told knowledge in sentences until it can operate.  In a procedural system \\\n",
        "desired behaviour is encoded directly into the agent's code.  Agents can also be given a mechanism to learn.\"\"\"\n",
        "chapter7_2 = \"\"\"Wumpus world.\"\"\"\n",
        "chapter7_3 = \"\"\"An inference algorithm $i$ can derive entailment.  Inference algorithms that only derive \\\n",
        "entailed sentences are referred to as sound or truth perserving.  An inference algorithm that can derive \\\n",
        "any entailment is complete.\"\"\"\n",
        "chapter7_4 = \"\"\"Using logical connectives, complex sentences can be formed from simple sentences. \\\n",
        "Propositional logic can be used to construct a knowledge base.  Using model checking on this knowledge \\\n",
        "base, inferences can be made using a truth table enumeration.\"\"\"\n",
        "chapter7_5 = \"\"\"Beyond model checking, entailment can also be done through theorem proving.  Some common \\\n",
        "logical equivalence rules: implication $(P \\Rightarrow Q) \\equiv (-P \\land Q)$, \\\n",
        "demorgan $-(P \\land Q) \\equiv (-P \\lor -Q)$ (same vice versa), \\\n",
        "distribution $(P \\land (Q \\lor R)) \\equiv ((P \\land Q) \\lor (P \\land R))$ (same vice versa). \\\n",
        "Searching for a proof is often more efficient than enumeratin models, because this way we ignore \\\n",
        "any irrelevant propositions.  Logical systems are monotonic in that entailments will only increase as \\\n",
        "new information is added.  A resolution algorithm works using the principle of proof by contradiction.\\\n",
        "In order to prove that $KB \\models a$, we show that $(KB \\land -a)$ converted to CNF is in fact a contradition. \\\n",
        "Then each pair of clauses that contains complementary literals is resolved until either two clauses resolve to the \\\n",
        "empty clause (meaning $KB \\models a$) or no new clauses can be can be added (meaning there is no entailment). \\\n",
        "We can discard clauses with two complementary literals to prevent pointless steps.  Definite clauses are \\\n",
        "interesting because they can be written as implications with a premise of positive literal.  Horn clauses \\\n",
        "allow for the use of forward-chaining and backward-chaining algorithms and deciding entailment with them can\n",
        "be done in linear time based on the size of KB. Backward-chaining works back from the query and it is a form of goal-directed reasoning. \n",
        "```\n",
        "function Forward-Chaining(KB, q) returns bool\n",
        "  inputs: KB, set of definite clauses\n",
        "          a, the query proposition symbol\n",
        "  count = table - count[c] init num symbols in c's premise\n",
        "  inferred = table - inferred[s] init false for all symbols s\n",
        "  queue = queue of symbols, init known true in KB\n",
        "\n",
        "  while queue is not empty do\n",
        "    p = POP(queue)\n",
        "    if p = q then return true\n",
        "    if inferred[p] = false theen\n",
        "      inferred[p] = true\n",
        "      for each clause c in KB where p is in c.PREMISE do\n",
        "        --count[c]\n",
        "        if count[c] = 0 then add c.CONCLUSION to queue\n",
        "  return false\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"agents that reason over an internal knowledge representation to decide on an action\",    \n",
        "\"knowledge base\" : \"a set of sentences expressed in a knowledge representation language that contains some assertion\",\n",
        "\"axiom\" : \"an assertion that is given and not derived from other sentences\",\n",
        "\"inference\" : \"generate new sentences from existing knowledge\",\n",
        "\"model\" : \"$M(a)$ is the set of all models of $a$ (models where $a$ is true)\",\n",
        "\"entailment\" : \"one sentence follows logically from another $a \\models b$ iff $M(a) \\subseteq M(b)$\",\n",
        "\"model checking\" : \"enumerate all models where $KB$ is true showing that $a$ is true and thus $M(KB) \\subseteq M(a)$\",\n",
        "\"proposition symbol\" : \"a symbol for a given proposition that can either be true or false\",\n",
        "\"conjunction\" : \"logical 'and': $P \\land Q$ with each part as a conjunct\",\n",
        "\"disjunction\" : \"logical 'or': $P \\lor Q$ with each part as a disjunct\",\n",
        "\"implication\" : \"$P \\implies Q$ with premise P and conclusion Q\",\n",
        "\"biconditional\" : \"$P \\iff Q$, if and only if\",\n",
        "\"theorem proving\" : \"construct a proof of a desired sentence by applying inference rules directly to knowledge base\",\n",
        "\"logical equivalence\" : \"sentences are logically equivalent if true for the same set of models $P\\equiv Q$\",\n",
        "\"satisfiability\" : \"if a sentence is true in some model then it is satisfiable\",\n",
        "\"Modus Ponens\" : \"inference rule - $(P \\Rightarrow Q, P) | Q$ meaning, if the top sentences are true, then so is Q\",\n",
        "\"And-Elimination\" : \"inference rule - $(P \\land Q)| P$\",\n",
        "\"resolution\" : \"a single inference rule that can create a complete inference algorithm paired with a search\",\n",
        "\"unit resolution\" : \"$(l_1 \\lor ... \\lor l_k, m) | (l_1 \\lor ... \\lor l_{i-1} \\lor l_{i+1} \\lor ... \\lor l_k)$\",\n",
        "\"full resolution\" : \"a generalization that takes two clauses and produces a single clause without the complements\",\n",
        "\"conjunctive normal form\" : \"a sentence written as a conjunction of clauses (disjunctions)\",\n",
        "\"resolution closure\" : \"the set of all clauses derivable from applying the resolution rule to each clause and the resulting derivates\",\n",
        "\"ground resolution theorem\" : \"An unsatisfiable set of clauses with have a resolution closure containing the empty clause\",\n",
        "\"definite clause\" : \"a restriction on form such that it is a disjunction of literals and exactly one is positive\",\n",
        "\"horn clause\" : \"a disjunction of literals where at most one is positive\",\n",
        "\"goal clause\" : \"a disjunction of literals where none are positive\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "05ba30fb-7421-43d9-fb48-17f40da068d7"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nA knowledge-based agent must tell the knowledge base what it perceives and it must ask the knowledge base what action to be perform.  Then it tells the knowledge base which action was chosen and peforms the action.  In a declarative system, the agent starts with an empty knowledge base and is told knowledge in sentences until it can operate.  In a procedural system desired behaviour is encoded directly into the agent's code.  Agents can also be given a mechanism to learn.\n\n## AIMA Chapter 7.2 The Wumpus World\nWumpus world.\n\n## AIMA Chapter 7.3 Logic\nAn inference algorithm $i$ can derive entailment.  Inference algorithms that only derive entailed sentences are referred to as sound or truth perserving.  An inference algorithm that can derive any entailment is complete.\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nUsing logical connectives, complex sentences can be formed from simple sentences. Propositional logic can be used to construct a knowledge base.  Using model checking on this knowledge base, inferences can be made using a truth table enumeration.\n\n## AIMA 7.5 Propositional Theorem Proving\nBeyond model checking, entailment can also be done through theorem proving.  Some common logical equivalence rules: implication $(P \\Rightarrow Q) \\equiv (-P \\land Q)$, demorgan $-(P \\land Q) \\equiv (-P \\lor -Q)$ (same vice versa), distribution $(P \\land (Q \\lor R)) \\equiv ((P \\land Q) \\lor (P \\land R))$ (same vice versa). Searching for a proof is often more efficient than enumeratin models, because this way we ignore any irrelevant propositions.  Logical systems are monotonic in that entailments will only increase as new information is added.  A resolution algorithm works using the principle of proof by contradiction.In order to prove that $KB \\models a$, we show that $(KB \\land -a)$ converted to CNF is in fact a contradition. Then each pair of clauses that contains complementary literals is resolved until either two clauses resolve to the empty clause (meaning $KB \\models a$) or no new clauses can be can be added (meaning there is no entailment). We can discard clauses with two complementary literals to prevent pointless steps.  Definite clauses are interesting because they can be written as implications with a premise of positive literal.  Horn clauses allow for the use of forward-chaining and backward-chaining algorithms and deciding entailment with them can\nbe done in linear time based on the size of KB. Backward-chaining works back from the query and it is a form of goal-directed reasoning. \n```\nfunction Forward-Chaining(KB, q) returns bool\n  inputs: KB, set of definite clauses\n          a, the query proposition symbol\n  count = table - count[c] init num symbols in c's premise\n  inferred = table - inferred[s] init false for all symbols s\n  queue = queue of symbols, init known true in KB\n\n  while queue is not empty do\n    p = POP(queue)\n    if p = q then return true\n    if inferred[p] = false theen\n      inferred[p] = true\n      for each clause c in KB where p is in c.PREMISE do\n        --count[c]\n        if count[c] = 0 then add c.CONCLUSION to queue\n  return false\n```\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** - agents that reason over an internal knowledge representation to decide on an action\n* **Knowledge base** - a set of sentences expressed in a knowledge representation language that contains some assertion\n* **Axiom** - an assertion that is given and not derived from other sentences\n* **Inference** - generate new sentences from existing knowledge\n* **Model** - $M(a)$ is the set of all models of $a$ (models where $a$ is true)\n* **Entailment** - one sentence follows logically from another $a \\models b$ iff $M(a) \\subseteq M(b)$\n* **Model checking** - enumerate all models where $KB$ is true showing that $a$ is true and thus $M(KB) \\subseteq M(a)$\n* **Proposition symbol** - a symbol for a given proposition that can either be true or false\n* **Conjunction** - logical 'and': $P \\land Q$ with each part as a conjunct\n* **Disjunction** - logical 'or': $P \\lor Q$ with each part as a disjunct\n* **Implication** - $P \\implies Q$ with premise P and conclusion Q\n* **Biconditional** - $P \\iff Q$, if and only if\n* **Theorem proving** - construct a proof of a desired sentence by applying inference rules directly to knowledge base\n* **Logical equivalence** - sentences are logically equivalent if true for the same set of models $P\\equiv Q$\n* **Satisfiability** - if a sentence is true in some model then it is satisfiable\n* **Modus ponens** - inference rule - $(P \\Rightarrow Q, P) | Q$ meaning, if the top sentences are true, then so is Q\n* **And-elimination** - inference rule - $(P \\land Q)| P$\n* **Resolution** - a single inference rule that can create a complete inference algorithm paired with a search\n* **Unit resolution** - $(l_1 \\lor ... \\lor l_k, m) | (l_1 \\lor ... \\lor l_{i-1} \\lor l_{i+1} \\lor ... \\lor l_k)$\n* **Full resolution** - a generalization that takes two clauses and produces a single clause without the complements\n* **Conjunctive normal form** - a sentence written as a conjunction of clauses (disjunctions)\n* **Resolution closure** - the set of all clauses derivable from applying the resolution rule to each clause and the resulting derivates\n* **Ground resolution theorem** - An unsatisfiable set of clauses with have a resolution closure containing the empty clause\n* **Definite clause** - a restriction on form such that it is a disjunction of literals and exactly one is positive\n* **Horn clause** - a disjunction of literals where at most one is positive\n* **Goal clause** - a disjunction of literals where none are positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "87e1c278-06f2-453a-f62f-00510093bc4c"
      },
      "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": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nThere are two main schools of thought on desired AI behaviour: human vs rational. The turing test is designed to determine if a computer could pass as a human to some interrogator. To pass a turing test, a computer would need natural language processing, knowledge representation, automated reasoning, and machine learning.  A total turing test would require interations with objects in the real world and the computer would need computer vision and robotics.  These skills needed for a turing test allow an agent to act rationally.  The rational-agent approach to AI is more general than other approaches and it is more easily defined mathematically.  AI focuses on the study of agents that 'do the right thing' given a defined objective and this is often referred to as the standard model. Perfect rationality is not always feasible due to computational demands so sometimes limited rationality is employed.  The standard model is a time tested approach, but it requires a fully specified objective which is not always easy to define.  A machine pursuing a fixed objective might behave in unanticipated ways which don't align with the human objective.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\nJohn Searle introduced the idea of weak AI - machines that act as if there were intelligent and strong AI (general AI) - machines that actually think consciously.  A turing test requires a program to converse with an interrogater for 5 minutes (through typed messages).  The interrogator then guesses whether it was conversing with a human or computer.  If the interrogator is fooled 30% of the time, then the computer passes the test.  Many chatbots (ELIZA, MGONZ, CYBERLOVER) have fooled people, but it is still unclear if any program has passed the turing test.  A chatbot claiming to be a Ukrainian boy (Eugene Goostman) fooled 33% of untrained interrogators.  The backstory of the chatbot helped to explain errors.  Standards for what AI passes is somewhat of a moving goalpost.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nIn the Chinese room argument by Searle, a human only fluent in English is given a rulebook of English instructions.  He is passed indecipherable Chinese symbols, looks them up in the rulebook, and writes back with symbols from his instructions.  What he passes back is intelligent Chinese responses, but he has no understanding of Chinese.  This argument states that computers may generate intelligent responses, but they have no understanding of the true meaning.\n\n\n## AIMA 2.1 Agents and Environments\n\nThere are many existing examples of agents. A human is an agent with eyes/ears/etc for sensors and hands/legs/etc for actuators. A software agent might take file contents/input devices as sensory input and act by writing to files or output devices. An agent's environment could be as broad as the entire universe.  An agent will choose an action based on its knowledge and percept sequence, but not based on anything that it has not yet percieved.  A simple example of an agent is a robotic vacuum cleaner agent in a world consisting of squares that are clean or dirty.  The agent can percieve its current location and whether or not that square is clean or dirty.  The actions available are move, clean the dirt, or do nothing. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nThe notion of consequentialism means that we evalutate an agent's behaviour given the consequences that follow from some actions.  The agent should perform actions that lead to a desirable outcome.  Desirability can be defined using a performance measure.  A rational agent will seek to maximize its peformance measure.  A poorly chosen performance measure can lead to undesirable results.  The performance measure should be chosen based on the end goal and not on how you think the agent should behave.  The current rational choice for an agent will depend on its performance measure, prior knowledge, actions, and current percept sequence.  Rationality does not require omniscience (knowing the actual outcome of its actions) but instead it maximizes expected performance and depends only its percept sequence and knowledge to date.  Agents must explore and gather information to learn new things.  It is rare but possible that an environment is completely known and in this case an agent can simply act correctly. A rational agent should be autonomous, meaning that it can learn as a means of compensating for missing/incorrect knowledge.  \n\n\n## AIMA 2.3 The Nature of Environments\n\nTask environments can be virual or physical. In a fully observable environment, an agent can see the full state of the environment at any given time. Otherwise, the envirnoment is partially observable which could be due to missing or limited sensor data. Environments can be single-agent or they can contain more agents in a multi-agent environment.  Multi-agent environments can be either competative or cooperative.  In a deterministic environment, the result of an action is always known, but if there is uncertaintiy, it is non-deterministic.  In a stochastic environment, it can be modeled using probabilities. In an episodic environment, each percept and resulting action is an episode in itself whereas in a sequential environemnt, the previous percepts and actions are taken into account. If an environment is constantly chaning then it is dynamic, otherwise a turn based environment would be static. A discrete environment has a finite number of states otherwise actions and states transition smoothly over time in a continuous environment.  In a known environment, whether or not the agent is aware, all outcomes for a given action are given.\n\n\n## AIMA 2.4 The Structure of Agents\n\nAn important distinction: the agent program takes the current percept as input whereas the function may depend on the entire percept history.  Suppose we have a table-driven agent program, the table size would grow exponentially and would easily become intractible given the space requirement and the time needed to create such a table. The biggest challeng in AI is writing an agent program that produces rational behaviour from a smallish table. Simple reflex agents are simple, but they only really work if the environment is fully observable. A goal-based agent will choose actions inorder to achieve some goal.  This often involves searching and planning. A utility-based agent will choose an action in order to maximize its expected utility (average utility given some probailities). \n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive through sensors and act in an environment through actuators\n* **Rational agent** - agent that seeks to achieve best expected outcome (maximize performance measure) given percept sequence and knowledge\n* **Percept** - the content percieved through sensors\n* **Percept sequence** - the history of all percepts percieved by an agent\n* **Agent function** - mathematical map from a particular percept sequence to an action\n* **Agent program** - the acutal concrete implementation of an agent function\n* **Agent architecture** - the physical computing device with actuators/sensors that runs the agent program\n* **Performance measure** - evaluation of any sequence of states for an enviroment\n* **Task environment** - combination of PEAS (performance, environment, actuators, sensors)\n* **Simple reflex agent** - selection action only based on current percept (no history)\n* **Transition model** - keeps track of how the world changes over time\n* **Sensor model** - how the world's state is percived by the agent\n* **Model-based agent** - uses both a transition model and sensor model to track the world's state (internal state)\n* **Utility function** - an internal function for the external performance measure\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\nThe list slice operator [:] returns a new list (shallow copy). Lists can be concatenated using the + operator but dictonaries cannot.  Dictionary keys cannot be mutable. Strings and tuples are not mutable. The elements in tuples can be lists or other mutables.  Tuples and lists can contain mixed types. String formatting using '%' is allowed. 'is' operator is used to check if two objects are the same instance. *args can be used in a function to take a variable number of arguments and *kwargs can be used to take a dict as a variable number of keyword arguments.  Python is dynamically scoped so variables take most current value. \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n* **Magic methods** - user-defined classes can behave like built in and can implement operator overloading\n* **Duck typing** - establish suitability of an object depending on the methods available (duck defense)\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nA problem solving agent can follow a four-phase problem solving process: goal formulation - finding some goal, problem formulation - a description of the states/actions needed to reach the goal, search - simulates a sequence of actions until one is found that reaches the goal, execute - the agent performs the actions found in the solution.  This requires that an environment be fully observable, deterministic, and known. A search problem consists of: a state space, an initial state, goal state/s, actions, a transition model, and an action cost function.  A solution consists of a path made up of actions and an optimal solution is the lowest cost path.  The state space can be modeled as a graph with states as nodes and action as edges.\n\n\n## AIMA Chapter 3.2 Example Problems\n\nSome example standard search problems: vaccum world, sokoban puzzle (push boxes on grid to designated locations), sliding-tile puzzle (8-puzzle).  Some example real world search problems: route-finding problems, touring problems/traveling salesperson problem (visit each city and minimize cost), VLSI layout (circuit layout), robot navigation, automatic assembly sequencing.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nThe state space defines all possible states while the search tree describes paths between states. Best-first-search uses a priority queue and adds nodes to the frontier if they have not been reached or a lower cost path is found.  A cycle is a redundant path and can lead to an infinite search tree. A algorithm's performance can be measured based on: completeness, cost optimality, time complexity, and space complexity.\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBreadth-first-search could be implemented as best-first-search with an evaluation function such that it issimply the depth of the node.  Breadth-first-search can early goal test when the node is added to the frontier whereas best-first-search has to late goal test when a node is popped from the frontier.  Breadth-first-search is cost optimal if each action has the same cost.  Both space and time complexity for breadth-first-search are\n$O(b^d)$.  Uniform-cost-search performs goal test when a node is popped from the frontier.  Uniform-cost-search is complete and cost-optimal, but the space/time complexity is based on $C*$ which is the cost of the optimal solution and $e$ the cost of each action as $O(b^{1+{C*/e}})$ which in the worst case is far greater than $b^d$. \\ \nDFS could be implemented using best-first where the eval function is the negated depth.  DFS is not cost optimal as it will just return the first solution found.  It is also incomplete because on an infinite state space it can continually go down an infinite path.  DFS is memory efficient though and has a space complexity of $O(bm)$ where $m$ is the max depth of the tree.  For this reason, DFS and its variants are widely used in AI. Depth-limited search has a time complexity of $O(b^l)$ and space of $O(bl)$ but it is still not complete if we chose some $l<d$. Iterative deepening is complete and optimal for same cost problems like BFS.  However, it runs in $O(b^d)$ with a space complexity of $O(bd)$ by not storing all nodes in memory.  IDDFS is a good choice for problems with a large search state space. Bidirectiional search is complete and optimal with space/time complexity of $O(b^{d/2})$.\n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - all possible states for an environment\n* **Transition model** - determines what an action does\n* **Action cost function** - a numeric cost for taking some action which reflects the performance measure\n* **Grid world** - 2D world made of cells, agents move between cells (vaccum world)\n* **Search tree** - graph of state space with various paths from an initial state (root)\n* **Best-first-search** - expand the node from the frontier with minimum value for some evaluation function\n* **Graph search** - checks for redundant paths as opposed to tree search which does not\n* **Completeness** - will the algorithm always find a solution if it exists\n* **Cost optimality** - will it find the solution with the lowest path cost\n* **Time complexity** - how long will it take to find a solution\n* **Space complexity** - how much space is needed to perform the search\n* **Depth** - $d$ the number of actions performed to reach an optimal solution\n* **Branching factor** - $b$ the number of children for a given node that need to be considered\n* **Breadth-first-search** - implemented using FIFO queue and is complete even on infinite search spaces\n* **Uniform-cost-search** - AI variant of Dijkstra's algorithm that finds min cost path given different costs\n* **Depth-first-search** - expands the deepest node in the frontier first using LIFO stack\n* **Backtracking search** - uses less memory than DFS by only generating only one child at a time $O(m)$\n* **Depth-limited search** - Run DFS with some limit $l$ to prevent following an infinite path\n* **Iterative deepening search** - Runs a series of depth-limited searches increasing the limit on each iteration\n* **Bidirectional search** - searches both forward from the start and backward from the goal, hoping they will meet\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nIn finite spaces, greed best-first is complete however this is not the case for infinite spaces. A good heuristic can reduce the time/space complexity of greedy to almost $O(bm)$.  A* search relies on admissibility in order to produce a cost optimal solution. If a heuristic is consistent then it is also admissable (not vice versa) and the first time we reach a state it will be the optimal path to that state.  This means states will only be added once to the frontier and never will be updated. If a heuristic is inadmissable, then A* may or may not return an optimal solution.  A* will expand all nodes with $f(n)$ less than the optimal cost $C*$, no nodes greater than $C*$, and may expand nodes with cost equal to $C*$ before reaching the goal.  With a consistent heuristic A* is also optimally efficient. Weighted A* is more similar to greedy best-first and could be called 'somewhat greedy'.  Memory usage is one main drawback of A* search.  There are algorithms which address this issue.  IDA* and RBFS both use less memory but they actually use too little memory which is a problem.  To fix this MA* and SMA* are used to take advantage to the available amount of memory.  Bidirectional search is sometimes more efficient, but it also might not be.  With a good heuristic, A* is generally just as good.  With an average heuristic, bidirectional search may perform better.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nThe quality of a heuristic can be characterized by its effective branching factor.  This is usually consistent among all not trivial problem instances.  Another way to characterize a heuristic is with its effective depth which compares total search cost to the uninformed search cost. Given two heuristics if $h_2(n) \\geq h_1(n)$ then $h_2$ dominates $h_1$ which means that $h_2$ will not expand more nodes than $h_1$.  If it is consitent and not computationally expensive, then it is better to use a heuristic function with higher values. Relaxed problems can produce better solutions due to shortcuts from added edges. The cost of an optimal solution in the relaxed problem can be used as an admissable heuristic in the original \nproblem.\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Heuristic function** - an estimate cost of the cheapest path from some state to the goal\n* **Informed search** - find solutions more efficiently using domain-specific info\n* **Greedy best-first search** - expand the node with the lowest heuristic cost (seemingly closest to goal) $f(n) = h(n)$\n* **A* search** - most common informed search, combines heuristic cost with path cost from starting state $f(n) = g(n) + h(n)$\n* **Admissible heuristic** - optimistic, never overestimates the cost of reaching the goal\n* **Consistency** - if every node $n$ and succesor $n'$, $h(n) \\leq c(n, a, n') + h(n')$ then $h(n)$ consistent\n* **Contours** - shows increasing concentric bands of $f(n)$ costs\n* **Monotonic** - path cost always increases monotonically along a path\n* **Optimally efficient** - one algorithm could get lucky and choose the optimal solution first\n* **Weighted a* search** - the heuristic value is weighted such that $f(n) = g(n) + W * h(n)$ for some $W > 1$\n* **Beam search** - conserves memory usage by limiting the size of the frontier but it is incomplete and sub optimal\n* **Iterative-deepening a*** - similar to IDDFS and reduces memory need by A* by not storing all states in memory\n* **Recursive best-first** - mimics the standard best-first search, but with linear space and slightly more efficient than IDA*\n* **Memory-bounded a*** - (also simplified SMA*) determines the available memory and runs A* until memory full, then drops worst node\n* **Relaxed problem** - a superset of the orignal state space with fewer restrictions on the actions\n* **Pattern databases** - the idea of storing the exact cost of a solution to every possible subproblem\n* **Precomputation** - time-consuming but precomputing optimal path costs can save massive time on many queries\n* **Landmark points** - we can precompute the optimal path from a smaller set of landmark points\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nIn adversarial search, we assume our opponent is actively trying to defeat us.  Perfect information, zero-sum games are often studied because they are deterministic, two-player, turn-taking games that are fully observable.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nThe max player is trying to find a sequence of actions that lead to a win, but the min player is trying to prevent that.  Max assumes that min is playing optimally and vice versa. The time complexity for minimax is $O(b^m)$ and the space complexity is $O(bm)$ unless the algorithm generates values one at a time as $O(m)$.  In the best case alpha-beta will only examine $O(b^{m/2})$ nodes.  In games with too many states to explore, either a Type A or Type B strategy is employed.  In Type A all moves are considered up to a certain depth of the tree where a heuristic is then applied.  In Type B only promising moves are follow as far a is possible, and then bad looking moves are ignored.\n```\nfunction ALPHA-BETA-SEARCH(game,state) returns action\n  player = game.TO-MOVE(state)\n  value, move = MAX-Value(game,state,-inf,+inf)\n  return move\n\nfunction MAX-VALUE(game,state,alpha,beta) returns (utility, move)\n  if game.IS-TERMINAL(state) then return game.UTILITY(state,player),null\n  v = -inf\n  for each a in game.ACTIONS(state) do\n    v2,a2 = MIN-VALUE(game,game.RESULT(state,a),alpha,beta)\n    if v2 > v then\n      v,move = v2,a\n      alpha = max(alpha,v)\n    if v >= beta then return v,move\n  return v,move\n\nfunction MIN-VALUE(game,state,alpha,beta) returns (utility, move)\n  if game.IS-TERMINAL(state) then return game.UTILITY(state,player),null\n  v = +inf\n  for each a in game.ACTIONS(state) do\n    v2,a2 = MAX-VALUE(game,game.RESULT(state,a),alpha,beta)\n    if v2 < v then\n      v,move = v2,a\n      beta = min(beta,v)\n    if v <= alpha then return v,move\n  return v,move\n```\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nIn a heuristic Alpha-Beta search, the search is cutoff as some depth and it is then evaluated for the utility of the states at that depth using some heuristic.  The heuristic that is applied is an estimate of the expected utility of a given state for the player that lies somewhere between a loss and a win.  Commonly these evaluation functions make some calculation based on the features of a state (probability that some feature leads to a win) to find the expected value. This kind of evalutation function is referred to as a weighted linear function.\n\n## AIMA Chapter 5.5 Stochastic Games\nIn the expectiminimax algorithm, chance nodes are added between min/max nodes that branch based on probabilities.  Expectiminimax has to consider all possible $n$ dice-rolls so it takes $O(b^mn^m)$. For this reason, expecitminimax trees are usually cutoff early and cannot run very deep.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Pruning** - ignores large unnecessary portions of the search tree to improve efficiency\n* **Evaluation function** - based on the state of the game, an estimate of who is winning\n* **Zero-sum game** - there are no win-win outcomes and what is good for one player is bad for their opponent\n* **Utility function** - associates some numerical value to a player when a terminal state is reached\n* **Game tree** - a search tree containing all sequences of moves until a terminal state is reached\n* **Minimax search** - adversarial search algorithm for two players: min and max\n* **Ply** - some times move means both players take action, so ply refers to a single move by a single player\n* **Minimax value** - the ultility value for max of the current state\n* **Alpha-beta pruning** - prunes minimax tree given $alpha$: best choice so far for max, and $beta$: best choice so far for min\n* **Killer moves** - heuristic to try the best moves first in a move-ordering scheme\n* **Transpositions** - permutations of a move sequence that result in the same position\n* **Cutoff test** - cutoff the search at a certain depth or if a terminal state is reached\n* **Quiescence search** - only evaluates positions where no future move that will drastically change the utility\n* **Horizon effect** - unavoidable move that causes serioius damage but could be delayed\n* **Singular extensions** - allow clearly better move in a position even if the search would be cutoff, avoids horizon effect\n* **Forward pruning** - prune moves that appear to be bad, even though they might be good\n* **Late move reduction** - if move ordering is well done, then later moves are less likely to be good\n* **Monte carlo tree search** - instead of using heuristic, estimates average utilty given a number of simulations\n* **Stochastic games** - introduce some element of unpredictability\n* **Chance nodes** - nodes inbetween min/max nodes that branch to new states based on some probability\n* **Expectiminimax value** - compute the expected value for a chance node as the sum of all outcomes weighted by their probability\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nA constraint satisfaction problem consists of a set of variables $X$, a set of domains for each variable $D$, and a set of constraints $C$ that specify allowed combinations of variables.  A solution to a CSP problem is a complete assignment that is consistent.  CSP problems are NP-complete, but there are some subclasses which are efficiently solvable.  Map coloring is an example of a CSP problem.  Job scheduling is another example of a CSP problem.  In a binary CSP, only unary or binary constraints are used and they can be represented using a constraint graph.  Global constraints can be represented using a hypergraph or a dual graph transformation with multiple graphs containing binary constraints.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nAC-3 is the most popular algorithm to enforce arc-consistency:\n```\nfunction AC-3(csp) returns false if inconsistent and true otherwise\n  queue = all arcs in csp\n\n  while queue is not empty do\n    (X_i, X_j) = POP(queue)\n    if REVISE(csp, X_i, X_j) then\n      if size of D_i = 0 then return false\n      for each X_k in X_i.NEIGHBORS-{X_j} do\n        add (X_k, X_i) to queue\n  return true\n\nfunction REVISE(csp, X_i, X_j) returns true iff the domain of X_i is revised\n  revised = false\n  for each x in D_i do\n    if no value y in D_j allows (x,y) to satisfy constraint beetween X_i and X_j then\n      delete x from D_i\n      revised = true\n  return revised\n```\nGiven domain size $d$ and $c$ constraints, AC-3 has a run time of $O(cd^3)$.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nIt is possible that variables with multiple possible values still exist and executing the constraint propagation process.  This requires that we then search for a solution.  CSPs are commutative meaning the order of application does not matter.  A backtracking search is done to find a solution. Backtracking search will only keep a single state representation that it modifies rather than creating new ones. We can improve backtracking search with domain-independent heuristics.  It is a powerful techinque to interleave both strategies of inference and search.\n\n## AIMA Chapter 6.4 Local Search for CSPs\nLocal search is another strategy that can be employed in solving CSPs.  In a local search each state will assign a value to each variable and the search will change a single variable at a time. An assignment may violate constraints, so we pick a conflicting varaible at random and try to pick a new value that is closer to a solution.  This is usually picked using the min-conflicts heuristic.\n\n## AIMA Chapter 6.5 The Structure of Problems\nFinding connected components in the constraint graph will create independent subproblems for each CC where the solutions for each independent CSP do not have any relation to the other.  If a constraint graph is a tree, then any two variables are only connected by one path.  This allows for a linear time solution.  To solve a tree CSP, pick variables in topological sorted order and enforce directional arc consistency.  Non-tree CSPs can also benefit from this.  Given a subset of variables that forms a tree in a cycle cutset, this technique can be applied first.  Another way is through tree decomposition where the orignal graph is transformed into a tree with sets of variables as nodes.  This requires that: each variable is in at least one node, two variables connected by a constraint must appear in the same node with that constraint in at least one node, and a variable that appears in two nodes must appear in each node along the connecting path. The tree width in a decomposition is equal to one less than the size of its largest node.  Although CSPs with bounded tree width are solvable in poly time, finding a decoposition with minimal tree width is NP-hard.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Assignments** - a value given to a variable that does not violate the constraints\n* **Consistent** - a legal assignment\n* **Complete assignment** - each variable is given a value\n* **Linear constraints** - problems where each variable appears in linear form can be solve using special algorithms\n* **Nonlinear constraints** - No algorithm exists that can solve nonlinear constraints of integer variables\n* **Continuous domains** - variables have continuous domains, common in real world like scheduling precise times\n* **Linear programming** - continuous domain CSP given contraints as linear equalities/inequalities\n* **Unary constraint** - some restriction on a single variable\n* **Binary constraint** - a restriction that relates two variables\n* **Global constraint** - a constraint that relates some arbitrary number of variables\n* **Preference constraints** - non-absolute constraints where some solutions are preferred leading to an optimal solution\n* **Constraint propogation** - reduce the legal values for a variable through constraints, which may reduce another variable, etc\n* **Local consistency** - each variable is a node in a graph with edges as constraints, enforcing local consistency removes inconsistent values\n* **Node-consistent** - all values in the domain of a node satisfy unary constraints\n* **Arc-consistent** - all values in the domain satisfy binary constraints\n* **Path consistency** - uses implicit inferred constraints to tighten binary constraints\n* **K-consistency** - given $k$ variables, if $k-1$ variables have a consistent assignment, then the $k$th variable also must\n* **Bounds propagation** - a way to manage domains with an upper and lower bound\n* **Backtracking search** - A form of DFS used in CSPs that commonly interleaves with inference\n* **Minimum-remaining-values** - Heuristic that first picks the most contrained variable that is most likely to fail - powerful guide\n* **Degree heuristic** - First pick the variable that is most used in contraints on other unassigned variables - tiebreaker\n* **Least-constraining-values** - First pick the value that rules out the fewest choices - stay flexible\n* **Forward checking** - When a variable is assigned, perform inference by establishing arc consistency for it\n* **Maintaining arc consistency** - Call AC-3 after an assignment on variables in arcs from unassigned neighbors and if AC-3 fails, we backtrack\n* **Backjumping** - go back to the most recent assignment in the conflicting set\n* **Constraint learning** - find a min set from the conflict set that creates the problem\n* **Tabu search** - maintain list of visited states that the algo cannot return to\n* **Constraint weighting** - technique to concentrate the search on the most important contraints through weights\n* **Directional arc consistency** - if for some ordering every $X_i$ is arc consistent with $X_j$ for all $j > i$\n* **Symmetry-breaking constraint** - Every consistent solution can be permuted to symetric solutions, we can enfore some ordering to prevent this\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nA knowledge-based agent must tell the knowledge base what it perceives and it must ask the knowledge base what action to be perform.  Then it tells the knowledge base which action was chosen and peforms the action.  In a declarative system, the agent starts with an empty knowledge base and is told knowledge in sentences until it can operate.  In a procedural system desired behaviour is encoded directly into the agent's code.  Agents can also be given a mechanism to learn.\n\n## AIMA Chapter 7.2 The Wumpus World\nWumpus world.\n\n## AIMA Chapter 7.3 Logic\nAn inference algorithm $i$ can derive entailment.  Inference algorithms that only derive entailed sentences are referred to as sound or truth perserving.  An inference algorithm that can derive any entailment is complete.\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nUsing logical connectives, complex sentences can be formed from simple sentences. Propositional logic can be used to construct a knowledge base.  Using model checking on this knowledge base, inferences can be made using a truth table enumeration.\n\n## AIMA 7.5 Propositional Theorem Proving\nBeyond model checking, entailment can also be done through theorem proving.  Some common logical equivalence rules: implication $(P \\Rightarrow Q) \\equiv (-P \\land Q)$, demorgan $-(P \\land Q) \\equiv (-P \\lor -Q)$ (same vice versa), distribution $(P \\land (Q \\lor R)) \\equiv ((P \\land Q) \\lor (P \\land R))$ (same vice versa). Searching for a proof is often more efficient than enumeratin models, because this way we ignore any irrelevant propositions.  Logical systems are monotonic in that entailments will only increase as new information is added.  A resolution algorithm works using the principle of proof by contradiction.In order to prove that $KB \\models a$, we show that $(KB \\land -a)$ converted to CNF is in fact a contradition. Then each pair of clauses that contains complementary literals is resolved until either two clauses resolve to the empty clause (meaning $KB \\models a$) or no new clauses can be can be added (meaning there is no entailment). We can discard clauses with two complementary literals to prevent pointless steps.  Definite clauses are interesting because they can be written as implications with a premise of positive literal.  Horn clauses allow for the use of forward-chaining and backward-chaining algorithms and deciding entailment with them can\nbe done in linear time based on the size of KB. Backward-chaining works back from the query and it is a form of goal-directed reasoning. \n```\nfunction Forward-Chaining(KB, q) returns bool\n  inputs: KB, set of definite clauses\n          a, the query proposition symbol\n  count = table - count[c] init num symbols in c's premise\n  inferred = table - inferred[s] init false for all symbols s\n  queue = queue of symbols, init known true in KB\n\n  while queue is not empty do\n    p = POP(queue)\n    if p = q then return true\n    if inferred[p] = false theen\n      inferred[p] = true\n      for each clause c in KB where p is in c.PREMISE do\n        --count[c]\n        if count[c] = 0 then add c.CONCLUSION to queue\n  return false\n```\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** - agents that reason over an internal knowledge representation to decide on an action\n* **Knowledge base** - a set of sentences expressed in a knowledge representation language that contains some assertion\n* **Axiom** - an assertion that is given and not derived from other sentences\n* **Inference** - generate new sentences from existing knowledge\n* **Model** - $M(a)$ is the set of all models of $a$ (models where $a$ is true)\n* **Entailment** - one sentence follows logically from another $a \\models b$ iff $M(a) \\subseteq M(b)$\n* **Model checking** - enumerate all models where $KB$ is true showing that $a$ is true and thus $M(KB) \\subseteq M(a)$\n* **Proposition symbol** - a symbol for a given proposition that can either be true or false\n* **Conjunction** - logical 'and': $P \\land Q$ with each part as a conjunct\n* **Disjunction** - logical 'or': $P \\lor Q$ with each part as a disjunct\n* **Implication** - $P \\implies Q$ with premise P and conclusion Q\n* **Biconditional** - $P \\iff Q$, if and only if\n* **Theorem proving** - construct a proof of a desired sentence by applying inference rules directly to knowledge base\n* **Logical equivalence** - sentences are logically equivalent if true for the same set of models $P\\equiv Q$\n* **Satisfiability** - if a sentence is true in some model then it is satisfiable\n* **Modus ponens** - inference rule - $(P \\Rightarrow Q, P) | Q$ meaning, if the top sentences are true, then so is Q\n* **And-elimination** - inference rule - $(P \\land Q)| P$\n* **Resolution** - a single inference rule that can create a complete inference algorithm paired with a search\n* **Unit resolution** - $(l_1 \\lor ... \\lor l_k, m) | (l_1 \\lor ... \\lor l_{i-1} \\lor l_{i+1} \\lor ... \\lor l_k)$\n* **Full resolution** - a generalization that takes two clauses and produces a single clause without the complements\n* **Conjunctive normal form** - a sentence written as a conjunction of clauses (disjunctions)\n* **Resolution closure** - the set of all clauses derivable from applying the resolution rule to each clause and the resulting derivates\n* **Ground resolution theorem** - An unsatisfiable set of clauses with have a resolution closure containing the empty clause\n* **Definite clause** - a restriction on form such that it is a disjunction of literals and exactly one is positive\n* **Horn clause** - a disjunction of literals where at most one is positive\n* **Goal clause** - a disjunction of literals where none are positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}