{
  "nbformat": 4,
  "nbformat_minor": 2,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3.9.7 64-bit ('cis_189-oOrRbfqb-py3.9': poetry)"
    },
    "language_info": {
      "name": "python",
      "version": "3.9.7",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "interpreter": {
      "hash": "413d84b4c869fc43b6a72d3d9a2afbfffc35117e969c89be084f8554a7f21990"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "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.  "
      ],
      "metadata": {
        "id": "brNDGX-kvzds"
      }
    },
    {
      "cell_type": "markdown",
      "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."
      ],
      "metadata": {
        "id": "aPtM8g7R0Pds"
      }
    },
    {
      "cell_type": "markdown",
      "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"
      ],
      "metadata": {
        "id": "cw5IpDLCZa4W"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "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)))"
      ],
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7c5cdea4-fab7-49d0-daab-45049c3068af"
      }
    },
    {
      "cell_type": "markdown",
      "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. "
      ],
      "metadata": {
        "id": "s3Uk9gQTevcj"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "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))"
      ],
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ],
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0fba2813-5f70-45b4-a740-0e496effad3c"
      }
    },
    {
      "cell_type": "markdown",
      "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. "
      ],
      "metadata": {
        "id": "5yG3-YncJfTB"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "outputs": [],
      "metadata": {
        "id": "2RECnJArJew4"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Module 1 - Intro to AI"
      ],
      "metadata": {
        "id": "GZZXyrV-xuAp"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"There are many ways to define artificial intelligence; some defining it in terms of similiarity to human behavior, others to\n",
        "an ability to act rationally. Alan Turing theorized the artificial intelligence as acting human definition with the Turing Test which asked whether \n",
        "a machine can think. He did not believe that physicial simulation of a person is necessary to show intelligence. On the other side, Aristotle defined \n",
        "irrefutable reasoning processes as based in laws of thought called logic. Computer agents are expected to operate alone, understand their environment, \n",
        "and adapt to change among other things. Incorporating rationality requires that they achieve the best outcome or best expected outcome given the circumstances.\n",
        "This is called the rational-agent approach which is generally seen as the standard AI model.\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"John Searle theorized the difference between weak AI wherein a machine acted as if it were intelligent and strong AI \n",
        "wherein the machine is actually consciously thinking. Turing argued for the informality of behavior in which human behavior is too complicated \n",
        "to be represented by a formal set of rules and therefore can never be represented by a computer program.  \"\"\"\n",
        "chapter27_2 = \"\"\"In response to the question of whether machines can really think, John Searle proposed the Chinese Room argument which says \n",
        "that a human in a room copying down Chinese symbols and passing them to the outside world. The outside world sees a system that is taking \n",
        "Chinese sentence input and producing fluent responses in Chinese. However, we know that the person inside the room is only transcribing–it does\n",
        "not really have any understanding of what it is transcribing. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent in an environment can be represented by a human whose eyes, ears, and other organs are sensors, and hands, \n",
        "legs, are actuators. The environment it acts in can be anything but is usually just the part that directly affects the agent, its\n",
        "actions, and its perceptions. \"\"\"\n",
        "chapter2_2 = \"\"\" One of the challenges of AI is determining whether its purpose is a desirable one. We define this as the problem of \n",
        "defining a performance measure. The concept of rationality depends on four things: the performance measure, the agent's understanding of its \n",
        "environment, the actions the agent can perform, and the agent's percept sequence so far. Note that our understanding of rationality does not\n",
        "require the agent to be omniscient. A rational agent should be learning from what it is taking in. It should also be autonomous in that it \n",
        "leanrs from its previously incorrect or partial knowledge.\"\"\"\n",
        "chapter2_3 = \"\"\"In order to define a task environment, we first want to think about what performance measure we want. In other words what \n",
        "are the desirable qualities we want for our agent. Then we want to think about the environment that will have the most influence on our\n",
        "agent. Then we think about the different actions (actuators) and sensors that are relevenat to our problem. There are various different \n",
        "properties of task environments including fully observable (sensors allow an agent to see complete state of environment all the time), \n",
        "partially observable (part of the state is missing from sensor data), single-agent vs. multiagent (in order to determine whether an object \n",
        "is an agent, we ask ourself if its job is to maximize performance measure which depends on the main agent's actions -- an example of this is chess and \n",
        "taxi driving), episodic vs. sequential (the current decision does not affect furture decisions vs. it does), static vs. dynamic (an ever changing \n",
        "environment), discrete vs. continuous (refers to time in the environment), known vs. unknown (how the agent knows the outcomes of the environment).\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"Simple reflex agents are nice because they are simple but have limited intelligence. Only a little bit of unobservability can \n",
        "ruin the agent. Sometimes randomization can help use fix these problems but generally it is better to use more complex agents. In order to handle\n",
        "partial observability, the agent should keep track of an internal state which allows it to understand some of the currently unobserved parts of the\n",
        "current state. A model-based agent uses the transition model and sensor model to keep track of the state. Utility-based agents take in an additional\n",
        "utility function which analyzes its preferences among all the states. A learning agent is divided into four parts: the learning element which \n",
        "improves function, the performance elemnt which selects actions, and the critic which gives feedback on how the agent is doing. The problem generator\n",
        "is responsible for giving actions that will allow for exploration. \"\"\"\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 must use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment; includes program and architecture\",\n",
        "\"rational agent\" : \"selecting an action that is expected to maximize performance measure based on its analysis capabilities\",\n",
        "\"simple reflect agent\" : \"these types of agents select actions based only on current precept, ignoring everything else\",\n",
        "\"precept\" : \"the things that an agent's sensors are analyzing\",\n",
        "\"rationality\" : \"doing the right thing\",\n",
        "\"turing test\": \"a computer passes if an interrogator cannot tell the difference between human responses and computer responses\",\n",
        "\"syllogisms\" : \"argument formats that always resulted in correct conclusions if given correct premises\", \n",
        "\"consciousness\" : \"an understanding of the outside world, oneself, and the idea that one is living; important to strong AI\", \n",
        "\"consequentialism\" : \"evaluating whether an action is right by analyzing the consequences of that action\", \n",
        "\"omniscience\" : \"this type of agent actually knows the consequences of its actions but is impossible in reality\", \n",
        "\"information gathering\" : \"strategically selecting actions in order to modify future percepts\", \n",
        "\"task environments\" : \"the problems or situations to which agents are the solutions\", \n",
        "\"PEAS\" : \"performance, environment, actuators, sensors; help you to define a task environment\", \n",
        "\"unobservable\" : \"the environment if we have an agent with no sensors\", \n",
        "\"deterministic\" : \"when the next state in the environment is completely determined by the current state and any actions taken\", \n",
        "\"nondeterministic\" : \"when the next state cannot be predicted based on current information\", \n",
        "\"transition model\" : \"keeps track of how the environment changes over time\", \n",
        "\"sensor model\" : \"how the state of the world is reflect in an agent's current analysis\"\n",
        "}\n",
        "\n"
      ],
      "outputs": [],
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      }
    },
    {
      "cell_type": "markdown",
      "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"
      ],
      "metadata": {
        "id": "elCCgY64spuq"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "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))"
      ],
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ],
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              "There are many ways to define artificial intelligence; some defining it in terms of similiarity to human behavior, others to\n",
              "an ability to act rationally. Alan Turing theorized the artificial intelligence as acting human definition with the Turing Test which asked whether \n",
              "a machine can think. He did not believe that physicial simulation of a person is necessary to show intelligence. On the other side, Aristotle defined \n",
              "irrefutable reasoning processes as based in laws of thought called logic. Computer agents are expected to operate alone, understand their environment, \n",
              "and adapt to change among other things. Incorporating rationality requires that they achieve the best outcome or best expected outcome given the circumstances.\n",
              "This is called the rational-agent approach which is generally seen as the standard AI model.\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              "John Searle theorized the difference between weak AI wherein a machine acted as if it were intelligent and strong AI \n",
              "wherein the machine is actually consciously thinking. Turing argued for the informality of behavior in which human behavior is too complicated \n",
              "to be represented by a formal set of rules and therefore can never be represented by a computer program.  \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              "In response to the question of whether machines can really think, John Searle proposed the Chinese Room argument which says \n",
              "that a human in a room copying down Chinese symbols and passing them to the outside world. The outside world sees a system that is taking \n",
              "Chinese sentence input and producing fluent responses in Chinese. However, we know that the person inside the room is only transcribing–it does\n",
              "not really have any understanding of what it is transcribing. \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " An agent in an environment can be represented by a human whose eyes, ears, and other organs are sensors, and hands, \n",
              "legs, are actuators. The environment it acts in can be anything but is usually just the part that directly affects the agent, its\n",
              "actions, and its perceptions. \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " One of the challenges of AI is determining whether its purpose is a desirable one. We define this as the problem of \n",
              "defining a performance measure. The concept of rationality depends on four things: the performance measure, the agent's understanding of its \n",
              "environment, the actions the agent can perform, and the agent's percept sequence so far. Note that our understanding of rationality does not\n",
              "require the agent to be omniscient. A rational agent should be learning from what it is taking in. It should also be autonomous in that it \n",
              "leanrs from its previously incorrect or partial knowledge.\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              "In order to define a task environment, we first want to think about what performance measure we want. In other words what \n",
              "are the desirable qualities we want for our agent. Then we want to think about the environment that will have the most influence on our\n",
              "agent. Then we think about the different actions (actuators) and sensors that are relevenat to our problem. There are various different \n",
              "properties of task environments including fully observable (sensors allow an agent to see complete state of environment all the time), \n",
              "partially observable (part of the state is missing from sensor data), single-agent vs. multiagent (in order to determine whether an object \n",
              "is an agent, we ask ourself if its job is to maximize performance measure which depends on the main agent's actions -- an example of this is chess and \n",
              "taxi driving), episodic vs. sequential (the current decision does not affect furture decisions vs. it does), static vs. dynamic (an ever changing \n",
              "environment), discrete vs. continuous (refers to time in the environment), known vs. unknown (how the agent knows the outcomes of the environment).\n",
              "\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              "Simple reflex agents are nice because they are simple but have limited intelligence. Only a little bit of unobservability can \n",
              "ruin the agent. Sometimes randomization can help use fix these problems but generally it is better to use more complex agents. In order to handle\n",
              "partial observability, the agent should keep track of an internal state which allows it to understand some of the currently unobserved parts of the\n",
              "current state. A model-based agent uses the transition model and sensor model to keep track of the state. Utility-based agents take in an additional\n",
              "utility function which analyzes its preferences among all the states. A learning agent is divided into four parts: the learning element which \n",
              "improves function, the performance elemnt which selects actions, and the critic which gives feedback on how the agent is doing. The problem generator\n",
              "is responsible for giving actions that will allow for exploration. \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment; includes program and architecture\n",
              "* **Rational agent** - selecting an action that is expected to maximize performance measure based on its analysis capabilities\n",
              "* **Simple reflect agent** - these types of agents select actions based only on current precept, ignoring everything else\n",
              "* **Precept** - the things that an agent's sensors are analyzing\n",
              "* **Rationality** - doing the right thing\n",
              "* **Turing test** - a computer passes if an interrogator cannot tell the difference between human responses and computer responses\n",
              "* **Syllogisms** - argument formats that always resulted in correct conclusions if given correct premises\n",
              "* **Consciousness** - an understanding of the outside world, oneself, and the idea that one is living; important to strong AI\n",
              "* **Consequentialism** - evaluating whether an action is right by analyzing the consequences of that action\n",
              "* **Omniscience** - this type of agent actually knows the consequences of its actions but is impossible in reality\n",
              "* **Information gathering** - strategically selecting actions in order to modify future percepts\n",
              "* **Task environments** - the problems or situations to which agents are the solutions\n",
              "* **Peas** - performance, environment, actuators, sensors; help you to define a task environment\n",
              "* **Unobservable** - the environment if we have an agent with no sensors\n",
              "* **Deterministic** - when the next state in the environment is completely determined by the current state and any actions taken\n",
              "* **Nondeterministic** - when the next state cannot be predicted based on current information\n",
              "* **Transition model** - keeps track of how the environment changes over time\n",
              "* **Sensor model** - how the state of the world is reflect in an agent's current analysis\n"
            ]
          },
          "metadata": {}
        }
      ],
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 725
        },
        "cellView": "form",
        "outputId": "0caad8dd-ad20-4626-cb91-923d00b0fbab"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Module 2 - Python"
      ],
      "metadata": {
        "id": "9xRbdqDox2zD"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"Strongly typed means that every object has a fixed type.\n",
        "In other words, you would not be allowed to combine two objects with different types like\n",
        "\"hello\" + 3. Dynamically typed means that the type is established at the same time that the\n",
        "variable is defined. So when you write x = \"hello\", the type of x is automatically defined\n",
        "as string.\n",
        "\n",
        "```is``` checks whether variables point to the same object while == checks whether variables point to \n",
        "objects of the same value\n",
        "\n",
        "Strings are immutable which means we cannot reassign values. Lists on the other hand are mutable. \n",
        "We can get a shallow copy of any sequence by doing $y = x[:]$. Tuples are immutable and can be of mixed\n",
        "type. Strings cannot have mixed types but lists can. Accessing items in a string/tuple/list is just $x[1]$.\n",
        "You can also use negative index to get from the right. We can also use slicing to get sequences using the following\n",
        "format: object[start][end][$n$th element]. Sorted(list) will return a copy while list.sort() will sort in place. \n",
        "\n",
        "Dictionaries are unordered and work by hashing so keys have to be immutable. In otherwords, we cannot use lists as \n",
        "keys. If we query a for a key that does not exist, we will get an error. dict.keys() returns a list of the current keys\n",
        "and dict.values() returns a list of the current values. dict.items() returns a list of the item tuples. Default dictionaries \n",
        "automatically initialize nonexistence dictionary values. We also have a class called Counter which creates a a default dictionary\n",
        "to count number of time values appear. \n",
        "\n",
        "Python does not allow function overloading and it is identified by its name only. Functions are first-class objects which means \n",
        "they can be passed as arguments, returned, and assigned as variables/stored in data structures. We instantiate an object using \n",
        "the ``` def __init__(attributes)``` method\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "outputs": [],
      "metadata": {
        "id": "DpBvu7EMx7sy"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "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))"
      ],
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ],
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "Strongly typed means that every object has a fixed type.\n",
              "In other words, you would not be allowed to combine two objects with different types like\n",
              "\"hello\" + 3. Dynamically typed means that the type is established at the same time that the\n",
              "variable is defined. So when you write x = \"hello\", the type of x is automatically defined\n",
              "as string.\n",
              "\n",
              "```is``` checks whether variables point to the same object while == checks whether variables point to \n",
              "objects of the same value\n",
              "\n",
              "Strings are immutable which means we cannot reassign values. Lists on the other hand are mutable. \n",
              "We can get a shallow copy of any sequence by doing $y = x[:]$. Tuples are immutable and can be of mixed\n",
              "type. Strings cannot have mixed types but lists can. Accessing items in a string/tuple/list is just $x[1]$.\n",
              "You can also use negative index to get from the right. We can also use slicing to get sequences using the following\n",
              "format: object[start][end][$n$th element]. Sorted(list) will return a copy while list.sort() will sort in place. \n",
              "\n",
              "Dictionaries are unordered and work by hashing so keys have to be immutable. In otherwords, we cannot use lists as \n",
              "keys. If we query a for a key that does not exist, we will get an error. dict.keys() returns a list of the current keys\n",
              "and dict.values() returns a list of the current values. dict.items() returns a list of the item tuples. Default dictionaries \n",
              "automatically initialize nonexistence dictionary values. We also have a class called Counter which creates a a default dictionary\n",
              "to count number of time values appear. \n",
              "\n",
              "Python does not allow function overloading and it is identified by its name only. Functions are first-class objects which means \n",
              "they can be passed as arguments, returned, and assigned as variables/stored in data structures. We instantiate an object using \n",
              "the ``` def __init__(attributes)``` method\n",
              "\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n"
            ]
          },
          "metadata": {}
        }
      ],
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "237a5fc3-0d0f-4240-8ebf-655b10675954"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Module 3 - Search Problems"
      ],
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"An agent has a four step problem solving process as follows: first they goal formulate, allowing them to \n",
        "know which actions to consider. Then they problem formulate which consists of coming up with a descriptions of the states and\n",
        "different actions that might be involved in reaching the goal. Then the agent has to search in which it\n",
        "performs a sequence of actions until it finds the goal. The final step is the agent executing the solution it has found through \n",
        "the search step. Note that in a fully observable, deterministic, known environment that solution is fixed. If not, the solution\n",
        "would be a branching solution with different plans depending on stimuli. We can define a search problem as containing the following:\n",
        "a set of states called the state space, the initial state that the agent starts in, a set of goal state/s, the actions availble to the\n",
        "agent, a transition model telling us what each action does, and an action cost function that tells us how much it would cost to carry\n",
        "out a certain action. We represent the state space typically as a graph. \"\"\"\n",
        "chapter3_2 = \"\"\"Example search problems consist of two types: standardized problems which reflect the methods being used and real world\n",
        "problems that implement the methods in real life. A great model of the search problem is the sliding tile puzzle where tiles are moved in order\n",
        "to get all the numbers in a correct order. Note that the actions are very clearly defined as up, down, left, right and that states are just the\n",
        "different orientations of the tiles on the board.\"\"\"\n",
        "chapter3_3 = \"\"\"This focuses on solving search problems using search trees which represent a subset of the state space. Each node is a state\n",
        "where the root is the initial state of the problem. Best-first search is the first idea of how to expand the frontier of a search algorithm. \n",
        "By using different evaluation functions, we get different algorithms. Many of the algorithms use a queue to hold the frontier, including a priority\n",
        "queue, a FIFO queue, and a LIFO queue. We measure the performance of search algorithms using a few different measures. The first being completeness\n",
        "which refers to whether it will return a solution or failure. Cost optimality is whether we return an optimal solution with lowest path cost. Time \n",
        "and space complexity analyze the efficiency of runtime and space usage. Both are typically measured using $d$ for depth which is number of actions in\n",
        "the optimal solution and $b$ for branching factor which is the number of children nodes that need to be explores at each step.\"\"\"\n",
        "chapter3_4 = \"\"\" BFS alwasy finds an optimal solution have time and space complexity are $O(b^d)$. The memory is typically the reason it isn't super \n",
        "efficient. The runtime of uniform cost search is $O(b^{1 + \\\\frac{C^*}{\\epsilon} })$ which can be worse than BFS since more of the tree may be explored. \n",
        "```\n",
        "def BFS():\n",
        "      frontier = FIFO queue with start\n",
        "      reached = start\n",
        "      while frontier is not empty: \n",
        "        curr = pop frontier\n",
        "        for each child of curr: \n",
        "            if child is goal return\n",
        "            else if not seen yet add to reached and add to frontier\n",
        "``` \n",
        "\n",
        "If we want to save space and a tree search is possible we want to use DFS over BFS. DFS does not always return an optimal solution and is not complete. \n",
        "But when finite, DFS has a memory complexity of $O(bm)$ where $b$ is the branching factor and $m$ is maximum depth of the tree. The space complexity can be further\n",
        "reduced using backtracking search which gets us to $O(m)$. Depth limited is complete if we made a good choice for $l$ and \n",
        "has time of $O(b^l)$ and space of $O(bl)$. Bidirectional search is complete and optimal cost as is iterative deepening. Bidirectional search has runtime of \n",
        "$O(b^{d/2})$ vs iterative with $O(b^d)$ time and $O(bd)$ space. \n",
        "\n",
        "```\n",
        "def IterativeD():\n",
        "    for depth = 0 to infinity: \n",
        "        depth-limited-search(curr_depth)\n",
        "```\n",
        "\n",
        "\n",
        "```\n",
        "def BiDiSearch():\n",
        "    queueStart\n",
        "    queueEnd\n",
        "    while not finished: \n",
        "      if min value is in start frontier:\n",
        "        proceed with search on start frontier\n",
        "        else proceed with search on end frontier\n",
        "```\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",   \n",
        " \"open-loop system\" : \"once a solution has been found an agent can ignore percepts while executing\", \n",
        " \"closed-loop system\" : \"if it's possible that the solution is incorrect, better to still monitor percepts\", \n",
        " \"path\" : \"a selection of actions; a solution is a path from start to goal\",\n",
        " \"optimal solution\" : \"has lowest path cost of all solutions; assume costs are positive\", \n",
        " \"grid world problem\" : \"2D array of cells which agents move between such as the vacuum problem\", \n",
        " \"search algorithm\" : \"takes problem as input and returns solution or failure\", \n",
        " \"frontier\" : \"the nodes of a search tree currently being explored\", \n",
        " \"best-first search\" : \"choose nodes with minium value of evaluation function, $f(n)$\", \n",
        " \"priority queue\" : \"used in best-first search, has a key value for each element\", \n",
        " \"FIFO queue\" : \"first in first out used in BFS\", \n",
        " \"LIFO queue\" : \"last in first out also known as a stack, used in DFS\", \n",
        " \"cycle\" : \"special case of a redunance path which is something we've already seen in our tree\", \n",
        " \"graph search\" : \"checks for already redundant paths; opposite of tree search\", \n",
        " \"Breadth first search\" : \"root expanded first then all children then children's child, keeping track of reached\", \n",
        " \"early goal test\" : \"checks whether a node is a solution as soon as it is reached rather than until it leaves queue (BFS)\", \n",
        " \"uniform cost search\" : \"dijkstra's where the least cost node is always expanded, complete, cost-optimal\", \n",
        " \"depth first search\" : \"explores deepest node in the queue first with no reached states tracked\", \n",
        " \"depth limited search\" : \"modification of DFS that allows us to not go on infinite path\", \n",
        " \"iterative deepening search\" : \"selects good $l$ by trying al values until a solution or failure is returned\", \n",
        " \"bidirectional search\" : \"searches forward from start and backward from goal \"\n",
        "}\n",
        "\n"
      ],
      "outputs": [],
      "metadata": {
        "id": "BN0b1eVYx-nd"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "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))"
      ],
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ],
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "An agent has a four step problem solving process as follows: first they goal formulate, allowing them to \n",
              "know which actions to consider. Then they problem formulate which consists of coming up with a descriptions of the states and\n",
              "different actions that might be involved in reaching the goal. Then the agent has to search in which it\n",
              "performs a sequence of actions until it finds the goal. The final step is the agent executing the solution it has found through \n",
              "the search step. Note that in a fully observable, deterministic, known environment that solution is fixed. If not, the solution\n",
              "would be a branching solution with different plans depending on stimuli. We can define a search problem as containing the following:\n",
              "a set of states called the state space, the initial state that the agent starts in, a set of goal state/s, the actions availble to the\n",
              "agent, a transition model telling us what each action does, and an action cost function that tells us how much it would cost to carry\n",
              "out a certain action. We represent the state space typically as a graph. \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              "Example search problems consist of two types: standardized problems which reflect the methods being used and real world\n",
              "problems that implement the methods in real life. A great model of the search problem is the sliding tile puzzle where tiles are moved in order\n",
              "to get all the numbers in a correct order. Note that the actions are very clearly defined as up, down, left, right and that states are just the\n",
              "different orientations of the tiles on the board.\n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "This focuses on solving search problems using search trees which represent a subset of the state space. Each node is a state\n",
              "where the root is the initial state of the problem. Best-first search is the first idea of how to expand the frontier of a search algorithm. \n",
              "By using different evaluation functions, we get different algorithms. Many of the algorithms use a queue to hold the frontier, including a priority\n",
              "queue, a FIFO queue, and a LIFO queue. We measure the performance of search algorithms using a few different measures. The first being completeness\n",
              "which refers to whether it will return a solution or failure. Cost optimality is whether we return an optimal solution with lowest path cost. Time \n",
              "and space complexity analyze the efficiency of runtime and space usage. Both are typically measured using $d$ for depth which is number of actions in\n",
              "the optimal solution and $b$ for branching factor which is the number of children nodes that need to be explores at each step.\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " BFS alwasy finds an optimal solution have time and space complexity are $O(b^d)$. The memory is typically the reason it isn't super \n",
              "efficient. The runtime of uniform cost search is $O(b^{1 + \\frac{C^*}{\\epsilon} })$ which can be worse than BFS since more of the tree may be explored. \n",
              "```\n",
              "def BFS():\n",
              "      frontier = FIFO queue with start\n",
              "      reached = start\n",
              "      while frontier is not empty: \n",
              "        curr = pop frontier\n",
              "        for each child of curr: \n",
              "            if child is goal return\n",
              "            else if not seen yet add to reached and add to frontier\n",
              "``` \n",
              "\n",
              "If we want to save space and a tree search is possible we want to use DFS over BFS. DFS does not always return an optimal solution and is not complete. \n",
              "But when finite, DFS has a memory complexity of $O(bm)$ where $b$ is the branching factor and $m$ is maximum depth of the tree. The space complexity can be further\n",
              "reduced using backtracking search which gets us to $O(m)$. Depth limited is complete if we made a good choice for $l$ and \n",
              "has time of $O(b^l)$ and space of $O(bl)$. Bidirectional search is complete and optimal cost as is iterative deepening. Bidirectional search has runtime of \n",
              "$O(b^{d/2})$ vs iterative with $O(b^d)$ time and $O(bd)$ space. \n",
              "\n",
              "```\n",
              "def IterativeD():\n",
              "    for depth = 0 to infinity: \n",
              "        depth-limited-search(curr_depth)\n",
              "```\n",
              "\n",
              "\n",
              "```\n",
              "def BiDiSearch():\n",
              "    queueStart\n",
              "    queueEnd\n",
              "    while not finished: \n",
              "      if min value is in start frontier:\n",
              "        proceed with search on start frontier\n",
              "        else proceed with search on end frontier\n",
              "```\n",
              "\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **Open-loop system** - once a solution has been found an agent can ignore percepts while executing\n",
              "* **Closed-loop system** - if it's possible that the solution is incorrect, better to still monitor percepts\n",
              "* **Path** - a selection of actions; a solution is a path from start to goal\n",
              "* **Optimal solution** - has lowest path cost of all solutions; assume costs are positive\n",
              "* **Grid world problem** - 2D array of cells which agents move between such as the vacuum problem\n",
              "* **Search algorithm** - takes problem as input and returns solution or failure\n",
              "* **Frontier** - the nodes of a search tree currently being explored\n",
              "* **Best-first search** - choose nodes with minium value of evaluation function, $f(n)$\n",
              "* **Priority queue** - used in best-first search, has a key value for each element\n",
              "* **Fifo queue** - first in first out used in BFS\n",
              "* **Lifo queue** - last in first out also known as a stack, used in DFS\n",
              "* **Cycle** - special case of a redunance path which is something we've already seen in our tree\n",
              "* **Graph search** - checks for already redundant paths; opposite of tree search\n",
              "* **Breadth first search** - root expanded first then all children then children's child, keeping track of reached\n",
              "* **Early goal test** - checks whether a node is a solution as soon as it is reached rather than until it leaves queue (BFS)\n",
              "* **Uniform cost search** - dijkstra's where the least cost node is always expanded, complete, cost-optimal\n",
              "* **Depth first search** - explores deepest node in the queue first with no reached states tracked\n",
              "* **Depth limited search** - modification of DFS that allows us to not go on infinite path\n",
              "* **Iterative deepening search** - selects good $l$ by trying al values until a solution or failure is returned\n",
              "* **Bidirectional search** - searches forward from start and backward from goal \n"
            ]
          },
          "metadata": {}
        }
      ],
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 474
        },
        "outputId": "21b42a50-b270-439d-ac74-40c061bf0bde"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Module 4 - Informed Search"
      ],
      "metadata": {
        "id": "WHREsHSSyA-h"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 13,
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"Informed search strategies are much more efficient at finding solutions to search problems. The most basic version\n",
        "is greedy best-first search, an interation of best-first search based on use of heuristic function where nodes are expanded with lowest\n",
        "$h(n)$ value. Note that uniform cost search is a greedy algorithm with only $g(n)$. It is complete in finite spaces but not in infinite ones. With good heuristic the complexity can be reduced from $O(|V|)$ to \n",
        "$O(bm)$. The evaluation function gives us the best path between where we currently are and the goal. A* is complete and its optimality depends\n",
        "on how good its heuristic is. If the heuristic is admissible, the A* is cost optimal. A* with a consistence heuristic is defined as optimally efficient\n",
        "in that it goes to all surely expanded nodes. Though A* has a lot of benefits, the number of nodes expanded can be exponential. Using an inadmissible \n",
        "heuristic can result in less optimal solutions but also possibly reduces number of nodes expanded. To reduce memory useage, we can keep reference counts which are the number of times\n",
        "a state has been reached. RBFS and SMA* are optimal search algorithms that help conserve memory. They can solve problems that A* would have run out\n",
        "of memory for.\"\"\"\n",
        "chapter3_6 = \"\"\"Designing a good heuristic has direct implications for the efficiency of A*. We look at relaxed problems to increase\n",
        "efficiency where more actions are given to each node. We can also look at solutions for subproblems of the given problem to act as heuristics.\n",
        "This cost acts as a lower bound for the cost on the full problem. All the possible subproblems are stored in a pattern database. One can also define landmarks and \n",
        "learn from the experiences within the problem itself. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"If $h(n)$ is admissible then A* using tree search is optimal. It explores more nodes than greedy best first search but is \n",
        "guaranteed to find the true optimal path if using an admissible heuristic. The cost of an optimal solution to a relaxed problem is an admissible heuristic\n",
        "for the original problem. The best heuristic is the so called oracle heuristic where we know the true distance. The worst heuristic is assuming we are already there. \n",
        "A* contours get stretched out a bit. Directed generally toward the goal but will explore some paths not near the goal. A* is more conservative than Greedy Best First \n",
        "search since it does not blinding rush toward the goal. In other words it hedges its bets and explores some areas not directly pointing toward the goal. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"has access to domain specific info about where the goals are\",\n",
        "\"heuristic function\" : \"$h(n)$ or estimated cost of minimal path from current node to goal node\", \n",
        "\"straight line distance\" : \"heuristic that calculates distance if line drawn from curr to goal\", \n",
        "\"A* Search\" : \"uses evaluation function $f(n) = g(n) + h(n) where g(n) is path cost from start to current node\",\n",
        "\"admissibility\" : \"an admissible heuristic never overestimates the remaining cost to get to the goal\", \n",
        "\"consistency\" : \"if the heuristic of current node is always less than sum of true cost plus heuristic of next node\", \n",
        "\"monotonic\" : \"value of g always increases as you move along your search\", \n",
        "\"surely expanded nodes\" : \"A* will expand all nodes where $f(n) < C^*$ where $C^*$ is optimal cost\", \n",
        "\"pruning\" : \"A* does not search nodes with higher costs, does not move in that direction\", \n",
        "\"satisficing\" : \"solutions that are not optimal but good enough, allow us to explore fewer nodes\", \n",
        "\"weighted A* search\" : \"use a sort of detour index to weight the heuristic value more heavily; $f(n) = g(n) + W \\\\cdot h(n)$\", \n",
        "\"beam search\" : \"conserves memory by only keeping $k$ nodes with best f values\",\n",
        "\"iterative deepening A* search\" : \"just like for DFS where we don't keep all reached states in memory\", \n",
        "\"manhattan distance\" : \"city block distance which is the sum of the distance of all tiles to goal using horizontal and vertical\", \n",
        "\"effective branching factor\" : \"good heuristic has value close to 1, branching factor for tree with depth $d$ to have $N + 1$ nodes\", \n",
        "\"dominates\" : \"$h_2(n) \\\\ge h_1(n)$ for any node $n$ so $h_2$ would dominante\", \n",
        "\"relaxed problem\" : \"fewer restrictions on actions taken by each node\"\n",
        "}\n",
        "\n"
      ],
      "outputs": [],
      "metadata": {
        "id": "tuFC8w7CyCns"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "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))"
      ],
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ],
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "Informed search strategies are much more efficient at finding solutions to search problems. The most basic version\n",
              "is greedy best-first search, an interation of best-first search based on use of heuristic function where nodes are expanded with lowest\n",
              "$h(n)$ value. Note that uniform cost search is a greedy algorithm with only $g(n)$. It is complete in finite spaces but not in infinite ones. With good heuristic the complexity can be reduced from $O(|V|)$ to \n",
              "$O(bm)$. The evaluation function gives us the best path between where we currently are and the goal. A* is complete and its optimality depends\n",
              "on how good its heuristic is. If the heuristic is admissible, the A* is cost optimal. A* with a consistence heuristic is defined as optimally efficient\n",
              "in that it goes to all surely expanded nodes. Though A* has a lot of benefits, the number of nodes expanded can be exponential. Using an inadmissible \n",
              "heuristic can result in less optimal solutions but also possibly reduces number of nodes expanded. To reduce memory useage, we can keep reference counts which are the number of times\n",
              "a state has been reached. RBFS and SMA* are optimal search algorithms that help conserve memory. They can solve problems that A* would have run out\n",
              "of memory for.\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "Designing a good heuristic has direct implications for the efficiency of A*. We look at relaxed problems to increase\n",
              "efficiency where more actions are given to each node. We can also look at solutions for subproblems of the given problem to act as heuristics.\n",
              "This cost acts as a lower bound for the cost on the full problem. All the possible subproblems are stored in a pattern database. One can also define landmarks and \n",
              "learn from the experiences within the problem itself.\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Informed search** - has access to domain specific info about where the goals are\n",
              "* **Heuristic function** - $h(n)$ or estimated cost of minimal path from current node to goal node\n",
              "* **Straight line distance** - heuristic that calculates distance if line drawn from curr to goal\n",
              "* **A* search** - uses evaluation function $f(n) = g(n) + h(n) where g(n) is path cost from start to current node\n",
              "* **Admissibility** - an admissible heuristic never overestimates the remaining cost to get to the goal\n",
              "* **Consistency** - if the heuristic of current node is always less than sum of true cost plus heuristic of next node\n",
              "* **Monotonic** - value of g always increases as you move along your search\n",
              "* **Surely expanded nodes** - A* will expand all nodes where $f(n) < C^*$ where $C^*$ is optimal cost\n",
              "* **Pruning** - A* does not search nodes with higher costs, does not move in that direction\n",
              "* **Satisficing** - solutions that are not optimal but good enough, allow us to explore fewer nodes\n",
              "* **Weighted a* search** - use a sort of detour index to weight the heuristic value more heavily; $f(n) = g(n) + W \\cdot h(n)$\n",
              "* **Beam search** - conserves memory by only keeping $k$ nodes with best f values\n",
              "* **Iterative deepening a* search** - just like for DFS where we don't keep all reached states in memory\n",
              "* **Manhattan distance** - city block distance which is the sum of the distance of all tiles to goal using horizontal and vertical\n",
              "* **Effective branching factor** - good heuristic has value close to 1, branching factor for tree with depth $d$ to have $N + 1$ nodes\n",
              "* **Dominates** - $h_2(n) \\ge h_1(n)$ for any node $n$ so $h_2$ would dominante\n",
              "* **Relaxed problem** - fewer restrictions on actions taken by each node\n"
            ]
          },
          "metadata": {}
        }
      ],
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 341
        },
        "cellView": "form",
        "outputId": "822c50fc-17b3-444f-d7dd-83cdfb49f6d9"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ],
      "metadata": {
        "id": "F3FPMzG9yUls"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"These consist of multiagent environments. One of the most popular types of games to study are perfect information\n",
        "zero sum games where tehy are fully observable and what is good for one player is to the other player's detriment. We define the two \n",
        "players as MIN and MAX where MAX goes first. \"\"\"\n",
        "chapter5_2 = \"\"\"For games with multiple outcomes we want to use minimax search. Optimal play for MAX assumes that MIN also plays optimally. \n",
        "The minimax decision is set at the root which is the decision made by MAX to maximize its minimax value. The minimax search algorithm tries all actions\n",
        "and chooses the one with the high minimax value. It moves down all the way to the leaves and then backs up, passing the values up the tree.\n",
        "\n",
        "```\n",
        "def minimax():\n",
        "    value, move <- max-value(game, state)\n",
        "\n",
        "def max-value():\n",
        "    for each child in current move: \n",
        "        new-value = min-value(game, child)\n",
        "\n",
        "        if new-value > curr-value:\n",
        "            reset move\n",
        "            alpha = max(new-value, alpha)\n",
        "        if new-value $\\\\ge \\\\beta$:\n",
        "            return\n",
        "\n",
        "def min-value():\n",
        "    for each child in current move:\n",
        "        new-value = max-value(game, child)\n",
        "        if new-value < curr-value: \n",
        "            reset move\n",
        "            beta = min(new-value, beta)\n",
        "        if new-value $\\\\le \\\\alpha$:\n",
        "            return\n",
        "```\n",
        "Minimax algorithm has a runtime of $O(b^m)$ and space complexity of $O(bm)$. This makes minimax inefficient for more complex games\n",
        "We decrease the exponential depth of the game tree using alpha-beta pruning which limites parts of the tree that do not affect the outcome.\n",
        "Consider some value: if the current player has a better choice either at the same level or higher up in the tree, it will never select\n",
        "that value. Let $\\\\alpha$ be the value of the best (highest) choice we have so far for MAX (at least) and let $\\\\beta$ be the value of the best (lowest) choice \n",
        "we have found so far for MIN (at most). The effectiveness of this strategy is dependent on the order we examine the states.\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"We can use heuristic evaluation functions to treat nonterminal nodes like they are terminal and thereby cut off the search early. This\n",
        "converts the general idea of alpha beta into a tree search algorithm. This heuristic returns an estimate value of the utility of a particular\n",
        "state to the current player. We can also implement a cutoff that allows us to only explore to some fixed depth. \"\"\"\n",
        "chapter5_5 = \"\"\"Some games called stochastic games include an element of randomization which require the use of chance nodes. These\n",
        "denote things like the possibility of different dice rolls, each of which will result in a different move strategy. We compute the expected\n",
        "value for the chance nodes of that particular outcome. In order to cut off the search with expectiminimax, we need to modify our evaluation functions \n",
        "a bit by only returning values that are a positive value of the probability of winning. The runtime of this algorithm is $O(b^m n^m)$ where $n$ is the\n",
        "number of distinct dice rolls. Note that we can still prune chance nodes using alpha beta pruning with a little bit of modification.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"Assume that there is some level of uncertainity felt by an agend about some state $s$ to get $P(s)$ for each state. Decision theory addresses the\n",
        "issue of choosing among actions based on how desirable their immediate outcome is. We want to find the expected utility \n",
        "of a particular choice given the evidence which can be found by averaging all the utility values of the outcomes mutiplied by the probability\n",
        "that it occurs. MEU principle gives a general idea of what an intelligent agent needs to do in order to do the right thing but does not give ways\n",
        "to actualize it. \"\"\"\n",
        "chapter16_2 = \"\"\"Think of the set of outcomes of an action as a lottery in which each action represents a ticket. Each lottery contains a set of possible outcomes\n",
        "all assigned specific probabilities. Each outcome is either a state or another lottery. With utility theory, the goal is to understand preferences with regards to\n",
        "complex lotteries and their relationships to the states within them. An agent that violates the axioms of utility theory will exhibit irrational behavior. \"\"\"\n",
        "chapter16_3 = \"\"\" Utility functions are relevant for mapping the lotteries described above to real numbers. Using a process call preference eliciation, we can\n",
        "help design a system that can make decisions or act on behalf of a human. This process requires us to present choices to the human and decide by observing on the underlying\n",
        "utility function representing that person's preferences. Agents that are risk averse show a curve that for any lottery, the utility of getting the lottery is less than\n",
        "just the expected money of the lottery. On the opposite end are risk seeking.  \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"The basis of expectimax is that uncertain outcomes are controlled by chance not an adversary. This occurs with explicity randomness like rolling a dice\n",
        "or with an unpredictable opponent who doesn't place optimally, or when actoins fail. Values now represent average-case outcomes rather than worse-case outcomes. The expectimax search\n",
        "computes the average score under optimal play. Max nodes are the same as in minimax but chance nodes are the min nodes where we calculate their expected utilites and the outcome is \n",
        "uncertain (weighted average). \n",
        "\n",
        "```\n",
        "def exp-value(state):\n",
        "    v = 0\n",
        "    for each successor of state:\n",
        "        p = probability(successor)\n",
        "        v = v + p (value(successor))\n",
        "    return v\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"pruning\" : \"restricts game play by ignoring parts of search tree that are inconsequential\",\n",
        "\"utility function\" : \"final numeric value to a player $p$ when in terminal state $s$, UTILITY($s, p$)\",\n",
        "\"minimax value\" : \"the utility for MAX in that state assuming both players are playing optimally until the end\", \n",
        "\"horizon effect\" : \"when the opponent's move causes damage and is unavoidable but can be prolonged by a sequence of moves\", \n",
        "\"forward pruning\" : \"removes moves that appear to be bad but might be good; see beam search\",\n",
        "\"stochastic games\" : \"include some element of randomization like dice throwing\", \n",
        "\"chance nodes\" : \"denote information about randomized elements of the game\", \n",
        "\"expectiminimax value\" : \"is a generalization of the minimaz value for games with chance nodes\", \n",
        "\"utility function\" : \"an agent's preferences that assign a single value to each state; $U(s)$\", \n",
        "\"maximum expected utility\" : \"rational agent chooses the action to maximize expected utility\", \n",
        "\"orderability\" : \"given two lotteries a rational agent must prefer one or think both are equal, must make a decision\",\n",
        "\"transitivity\" : \"if an agent prefers A to B and C to C then it prefers A to C\",\n",
        "\"continuity\" : \"if lottery B is between two others, the agent will be indifferent toward getting it or the other two\",\n",
        "\"substitutability\" : \"if indifferent between two choices, also indifferent if both are added to another lotter\",\n",
        "\"monotonicity\" : \"if outcomes are the same and agent prefers one lottery, it must prefer the one with the higher probability\",\n",
        "\"decomposability\" : \"lotteries can be reduced to smaller ones using probability laws\", \n",
        "\"value function/ordinal utility function\" : \"in deterministic game play, agent only needs preference ranking on the states invovled\", \n",
        "\"normalized utilities\" : \"use a scale of 0 and 1 to assign utility to things\", \n",
        "\"certainty equivalent\" : \"value an agent accepts instead of a lottery\", \n",
        "\"optimizer's curse\" : \"overestimating the expected utility of best choice\", \n",
        "\"certainity effect\" : \"people prefer gains that are certain\"\n",
        "}\n",
        "\n"
      ],
      "outputs": [],
      "metadata": {
        "id": "iEIOpL7vyWcc"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 16,
      "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))"
      ],
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ],
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "These consist of multiagent environments. One of the most popular types of games to study are perfect information\n",
              "zero sum games where tehy are fully observable and what is good for one player is to the other player's detriment. We define the two \n",
              "players as MIN and MAX where MAX goes first. \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "For games with multiple outcomes we want to use minimax search. Optimal play for MAX assumes that MIN also plays optimally. \n",
              "The minimax decision is set at the root which is the decision made by MAX to maximize its minimax value. The minimax search algorithm tries all actions\n",
              "and chooses the one with the high minimax value. It moves down all the way to the leaves and then backs up, passing the values up the tree.\n",
              "\n",
              "```\n",
              "def minimax():\n",
              "    value, move <- max-value(game, state)\n",
              "\n",
              "def max-value():\n",
              "    for each child in current move: \n",
              "        new-value = min-value(game, child)\n",
              "\n",
              "        if new-value > curr-value:\n",
              "            reset move\n",
              "            alpha = max(new-value, alpha)\n",
              "        if new-value $\\ge \\beta$:\n",
              "            return\n",
              "\n",
              "def min-value():\n",
              "    for each child in current move:\n",
              "        new-value = max-value(game, child)\n",
              "        if new-value < curr-value: \n",
              "            reset move\n",
              "            beta = min(new-value, beta)\n",
              "        if new-value $\\le \\alpha$:\n",
              "            return\n",
              "```\n",
              "Minimax algorithm has a runtime of $O(b^m)$ and space complexity of $O(bm)$. This makes minimax inefficient for more complex games\n",
              "We decrease the exponential depth of the game tree using alpha-beta pruning which limites parts of the tree that do not affect the outcome.\n",
              "Consider some value: if the current player has a better choice either at the same level or higher up in the tree, it will never select\n",
              "that value. Let $\\alpha$ be the value of the best (highest) choice we have so far for MAX (at least) and let $\\beta$ be the value of the best (lowest) choice \n",
              "we have found so far for MIN (at most). The effectiveness of this strategy is dependent on the order we examine the states.\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "We can use heuristic evaluation functions to treat nonterminal nodes like they are terminal and thereby cut off the search early. This\n",
              "converts the general idea of alpha beta into a tree search algorithm. This heuristic returns an estimate value of the utility of a particular\n",
              "state to the current player. We can also implement a cutoff that allows us to only explore to some fixed depth. \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "Some games called stochastic games include an element of randomization which require the use of chance nodes. These\n",
              "denote things like the possibility of different dice rolls, each of which will result in a different move strategy. We compute the expected\n",
              "value for the chance nodes of that particular outcome. In order to cut off the search with expectiminimax, we need to modify our evaluation functions \n",
              "a bit by only returning values that are a positive value of the probability of winning. The runtime of this algorithm is $O(b^m n^m)$ where $n$ is the\n",
              "number of distinct dice rolls. Note that we can still prune chance nodes using alpha beta pruning with a little bit of modification.\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "Assume that there is some level of uncertainity felt by an agend about some state $s$ to get $P(s)$ for each state. Decision theory addresses the\n",
              "issue of choosing among actions based on how desirable their immediate outcome is. We want to find the expected utility \n",
              "of a particular choice given the evidence which can be found by averaging all the utility values of the outcomes mutiplied by the probability\n",
              "that it occurs. MEU principle gives a general idea of what an intelligent agent needs to do in order to do the right thing but does not give ways\n",
              "to actualize it. \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "Think of the set of outcomes of an action as a lottery in which each action represents a ticket. Each lottery contains a set of possible outcomes\n",
              "all assigned specific probabilities. Each outcome is either a state or another lottery. With utility theory, the goal is to understand preferences with regards to\n",
              "complex lotteries and their relationships to the states within them. An agent that violates the axioms of utility theory will exhibit irrational behavior. \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Utility functions are relevant for mapping the lotteries described above to real numbers. Using a process call preference eliciation, we can\n",
              "help design a system that can make decisions or act on behalf of a human. This process requires us to present choices to the human and decide by observing on the underlying\n",
              "utility function representing that person's preferences. Agents that are risk averse show a curve that for any lottery, the utility of getting the lottery is less than\n",
              "just the expected money of the lottery. On the opposite end are risk seeking.  \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Pruning** - restricts game play by ignoring parts of search tree that are inconsequential\n",
              "* **Utility function** - an agent's preferences that assign a single value to each state; $U(s)$\n",
              "* **Minimax value** - the utility for MAX in that state assuming both players are playing optimally until the end\n",
              "* **Horizon effect** - when the opponent's move causes damage and is unavoidable but can be prolonged by a sequence of moves\n",
              "* **Forward pruning** - removes moves that appear to be bad but might be good; see beam search\n",
              "* **Stochastic games** - include some element of randomization like dice throwing\n",
              "* **Chance nodes** - denote information about randomized elements of the game\n",
              "* **Expectiminimax value** - is a generalization of the minimaz value for games with chance nodes\n",
              "* **Maximum expected utility** - rational agent chooses the action to maximize expected utility\n",
              "* **Orderability** - given two lotteries a rational agent must prefer one or think both are equal, must make a decision\n",
              "* **Transitivity** - if an agent prefers A to B and C to C then it prefers A to C\n",
              "* **Continuity** - if lottery B is between two others, the agent will be indifferent toward getting it or the other two\n",
              "* **Substitutability** - if indifferent between two choices, also indifferent if both are added to another lotter\n",
              "* **Monotonicity** - if outcomes are the same and agent prefers one lottery, it must prefer the one with the higher probability\n",
              "* **Decomposability** - lotteries can be reduced to smaller ones using probability laws\n",
              "* **Value function/ordinal utility function** - in deterministic game play, agent only needs preference ranking on the states invovled\n",
              "* **Normalized utilities** - use a scale of 0 and 1 to assign utility to things\n",
              "* **Certainty equivalent** - value an agent accepts instead of a lottery\n",
              "* **Optimizer's curse** - overestimating the expected utility of best choice\n",
              "* **Certainity effect** - people prefer gains that are certain\n"
            ]
          },
          "metadata": {}
        }
      ],
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 674
        },
        "outputId": "e9f5458e-82b4-4fa5-c56a-a0748aba7eaf"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ],
      "metadata": {
        "id": "qVSQhTVSyYYO"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"A constraint satisfaction problem consists of three parts: $X$ a set of variables, $D$ a set of domains for each variable, and $C$ a set of constraints that specify\n",
        "which combinations of values are allowed. Each constraint containing the scope or tuple of variables and the relation can be represented explicitly with the allowed values or as a\n",
        "function computing which values are allowed. CSPs allow us to assign values to variables such that we can create consistent assignments that do not violate specific constraints. A \n",
        "solution to a CSP must be consistent and complete in that all variables are assigned a value legally. One reason that CSPs are often used is because it is easy to formulate problems\n",
        "as such and solvers remove large parts of the search space. Once we have found a partial assignment that violates constraints, we can immiedately stop refining it and also see which \n",
        "variables are causing the problem allowing us to focus on them directly. The easiest CSPs to solve are ones with discrete, finite domains. No solution exists for solving nonlinear \n",
        "constraints with integer variables. Some more unique CSP problems can be respresented as crytarithmetic puzzles where each letter is a different number. These can be reflected in \n",
        "constraint hypergraphs which have nodes and hypernodes to represent n-ary constraints.\"\"\"\n",
        "chapter6_2 = \"\"\"CSPs proceed forward by either creating successors through a new variable assignment or an inference called constraint propogation where constraints are used to reduce \n",
        "the number of legal moves allowed for a variable. We want to enforce node and arc consistency on the graphs. The most popular algorithm for enforcing arc consistency is AC-3. Note that \n",
        "some problems like the map coloring problem are not relevant for arc consistency; in other words, there is no way to enforce it. AC-3 maintains a queue of all the different arcs in the \n",
        "problem and then makes the variables involved fit the constraints. If something gets revised we readd it to the queue otherwise we move on. Doing this ultimately allows us to either solve \n",
        "the problem completely, determine that it is unsolvable (domain of 0) or reduce the domain enough to create a faster search. Note that AC-3 returns false if an inconsistency is found.\n",
        "\n",
        "```\n",
        "def AC-3: \n",
        "    queue = arcs of CSP\n",
        "\n",
        "    while queue not empty: \n",
        "        (x, y) = pop queue\n",
        "        if revise (x,y):\n",
        "            if size of domain = 0 then return false\n",
        "            for each neighbor of x: \n",
        "                add (n, x) to queue\n",
        "    return true\n",
        "\n",
        "def revise: \n",
        "    for each x in domain of variable: \n",
        "        if no value in D allows constraint to be satisfied\n",
        "        delete x from D\n",
        "        revised = true\n",
        "    return revised\n",
        "```\n",
        "The runtime of AC-3 is $O(cd^3)$. Note that $k = 1$ for node consistency, $k = 2$ for arc, and $k = 3$ for path. \n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"This becomes relevant when we have finished AC-3 and still have multiple values left for variable domains. This means we have to search for our final solution. The classic\n",
        "recursive solution to this is selecting one of the remaining values from the domain for an unassigned variable and trying it until either a solution is found or it fails and the algorithm \n",
        "restores the initial state and tries the next value. This is called a backtracking search which is modeled on the depth first search. This keeps only a single representation of an assignment\n",
        "and alters that representation rather than creating new ones. This backtracking search can be improved by using domain-independent heuristics. The first is variable and value ordering or the\n",
        "order in which we select unassigned variables to test. It is not optimal to just go in order of their existence in the set. Insteadn it is better to choose the most constrained varibale by following \n",
        "the minimum remaining-values heuristic. If all variables have the same domain size, they we use the degree heuristic which selects the variable that is involve din the largest number of constraints \n",
        "on other unassigned variables. Once a variable has been selected, we want to select the value in the domain that constraints the least number of neighboring variables known as the least \n",
        "constraining value heuristic. Once we begin a search the most effective tool to get to a solution is inference. One of the basic ways to do this is with forward checking where for each variable unassigned\n",
        "that is connected to another, remove any value that is inconsistent with the value recently choosen for the other variable. This is often combined with MRV heuristic though it has a problem of not \n",
        "looking far enough ahead. MAC or maintaining arc consistency helps up to remove inconsistencies further ahead. When backtracking, rather than going to the most recent decision we can also \n",
        "look at the variable that might fix the problem by looking for the conflict set (variables in conflict with an assignment) and use a backjumping method to the most recent assignments in that set. \n",
        "Note that backjumping is redundant if forward checking or MAC is used. \"\"\"\n",
        "chapter6_4 = \"\"\"We can also used local searches to solve CSPs the rest of the way. We get a complete assignment and then select randomly a conflicted variable and try to change that into something that \n",
        "is more correct. This algorithm is roughly independt of problem size making it particularly efficient. Tabu search is also sometimes used with a plateau search where a small list of recently visited states \n",
        "is forbidden from being returned to. We can also use constraint weighting where we focus the search on the more important constraints in the problem. \"\"\"\n",
        "chapter6_5 = \"\"\"We wnat to think about how to structure CSPs. One of the main ways we can do this is by decomposing it into subproblems. Independence can be found by looking for connected components in the\n",
        "constraint graph. Each connected component is its own subproblem. It is challenging to find completely independent subproblems but some graph structures are easier to solve than others. For example a tree \n",
        "constraint graph can be solved in time linear of number of variables. Arbitrary CSP solving takes exponenital time to number of variables. Tree structured CSPs can be solved using toposort to find the ordering for directional arc consistency. If we are given a graph that is \n",
        "not a tree, we can reduce it into a tree by either removing individual nodes or collapsing nodes into one. We can use the following procedure: \n",
        "\n",
        "    1. choose a subset of variables that we can remove to form a tree constraint graph (subset = cycle cutset)\n",
        "    2. remove from the domains of the remaning variables any values that are inconsistent with a legal assignment of the cutset and if the remaining CSP has a solution return that together with the cutset \n",
        "    assignment\n",
        "\n",
        "This process is known as cutset conditioning which is typically seen as NP complete. We can also do a tree decomposition wherein the original constraintgraph is transformed into a tree where each node has a\n",
        "set of variables. Tree decomposition reduces a CSP into a tree of subproblems. It must fit the following constraints: \n",
        "\n",
        "    * every variable has to appear in at least one node\n",
        "    * if two variables are involved in a constraint, they must appear together in at least one node\n",
        "    * if a variable is in two nodes it must also be in every node along the path connecting those two nodes\n",
        "\n",
        "We can solve a tree decomposition problem in $O(nd^2)$ time. Tree decomposition is more time efficient than cutset conditioning. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"Original search space is $n!d^n$ but because CSPs are communitive we don't need to consider all these. Forward\n",
        "checking only checks constraints on the values immediately adjacent to the current one. It does not provide early detection of failures but does\n",
        "propogate information from assigned to unassigend variables. Constraint propogation extends forward checking and repeatedly enforced constraints locally. \n",
        "The Waltz Algorithm implements arc consistency by assignging every node a set of all possible values and removing every value that is not arc consistent\n",
        "with its neighbors. The algorithm repeats this until there is no more change. Worst case for AC-3 is where all nodes are connected to every other nodes. \n",
        "Therefore we'd have $O(n^2)$ arcs. Checking any arc would take $O(d^2)$ time given $d$ values and each arc can be inserted into the queue $d$ times. Thus\n",
        "the worst case runtiime if $O(n^2d^3)$\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"relation\" : \"each constraint contains $(scope, rel)$ where relation defines what values scope can have\", \n",
        "\"partial assignment\" : \"some variables are unassigned in CSP\", \n",
        "\"partial solution\" : \"a partial assignment that is still consistence\", \n",
        "\"constraint graph\" : \"nodes are variables and edges connect variables involved in a constraint\", \n",
        "\"precedence constraints\" : \"when some task must occur before another\", \n",
        "\"disjunctive constraint\" : \"two variables must not overlap in time, one has to come first\",\n",
        "\"linear programming\" : \"continuous domain CSP problems where constraints are equalities/inequalities\", \n",
        "\"unary constraint\" : \"restricts value of a single variable\", \n",
        "\"binary constraint\" : \"two variables participate, binary CSP uses only unary/binary constraints\", \n",
        "\"global constraint\" : \"arbitrary number of variables involved\", \n",
        "\"preference constraints\" : \"indicate which solutions are preferrable, typically used in constrained optimization problems\",\n",
        "\"local consistency\" : \"if we enforce constraints locally it ultimately will remove inconsistent values for the whole graph\", \n",
        "\"node-consistent\" : \"all values in the domain of a variable satisfy unary constraints\", \n",
        "\"arc-consistent\" : \"every value in domain satisfies binary constraints\", \n",
        "\"path consistency\" : \"strengthens binary constraints by implicitly inferred more constraints using triples of variables\", \n",
        "\"$k$-consistency\" : \"if for any set of $k - 1$ variables, a constant value can always be assigned to any $k$th variable\", \n",
        "\"strongly $k$-consistent\" : \"graph is consistent for all values from $k$ to 1\", \n",
        "\"bounds propogation\" : \"constraining domains to upper and lower bounds\", \n",
        "\"bounds-consistent\" : \"if for every variable and for its upper/loewr bounds, some value satisfies the constraint\", \n",
        "\"commutativity\" : \"reduce the size of the search tree for a CSP, does not matter the variable assignment order\", \n",
        "\"chronological backtracking\" : \"the most recent decision is revisited when an error is found, not the most optimal\", \n",
        "\"constraint learning\" : \"finding minimum set of variables from a conflict set that solves the problem\", \n",
        "\"min condlicts\" : \"heuristic that selects value resulting in smallest number of conflicts with other variables\", \n",
        "\"directional arc consistency\" : \"given an ordering of variables, iff every X is arch consistent with every X ordered after it\", \n",
        "\"value symmetry\" : \"considering the permutations of ways to distribute some values to a set of variables\", \n",
        "\"symmetry breaking constraint\" : \"breaking the value symmetry in assignments of variables\"\n",
        "\n",
        "}\n"
      ],
      "outputs": [],
      "metadata": {
        "id": "Wm4mfW82yaRH"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 18,
      "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))"
      ],
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ],
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "A constraint satisfaction problem consists of three parts: $X$ a set of variables, $D$ a set of domains for each variable, and $C$ a set of constraints that specify\n",
              "which combinations of values are allowed. Each constraint containing the scope or tuple of variables and the relation can be represented explicitly with the allowed values or as a\n",
              "function computing which values are allowed. CSPs allow us to assign values to variables such that we can create consistent assignments that do not violate specific constraints. A \n",
              "solution to a CSP must be consistent and complete in that all variables are assigned a value legally. One reason that CSPs are often used is because it is easy to formulate problems\n",
              "as such and solvers remove large parts of the search space. Once we have found a partial assignment that violates constraints, we can immiedately stop refining it and also see which \n",
              "variables are causing the problem allowing us to focus on them directly. The easiest CSPs to solve are ones with discrete, finite domains. No solution exists for solving nonlinear \n",
              "constraints with integer variables. Some more unique CSP problems can be respresented as crytarithmetic puzzles where each letter is a different number. These can be reflected in \n",
              "constraint hypergraphs which have nodes and hypernodes to represent n-ary constraints.\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "CSPs proceed forward by either creating successors through a new variable assignment or an inference called constraint propogation where constraints are used to reduce \n",
              "the number of legal moves allowed for a variable. We want to enforce node and arc consistency on the graphs. The most popular algorithm for enforcing arc consistency is AC-3. Note that \n",
              "some problems like the map coloring problem are not relevant for arc consistency; in other words, there is no way to enforce it. AC-3 maintains a queue of all the different arcs in the \n",
              "problem and then makes the variables involved fit the constraints. If something gets revised we readd it to the queue otherwise we move on. Doing this ultimately allows us to either solve \n",
              "the problem completely, determine that it is unsolvable (domain of 0) or reduce the domain enough to create a faster search. Note that AC-3 returns false if an inconsistency is found.\n",
              "\n",
              "```\n",
              "def AC-3: \n",
              "    queue = arcs of CSP\n",
              "\n",
              "    while queue not empty: \n",
              "        (x, y) = pop queue\n",
              "        if revise (x,y):\n",
              "            if size of domain = 0 then return false\n",
              "            for each neighbor of x: \n",
              "                add (n, x) to queue\n",
              "    return true\n",
              "\n",
              "def revise: \n",
              "    for each x in domain of variable: \n",
              "        if no value in D allows constraint to be satisfied\n",
              "        delete x from D\n",
              "        revised = true\n",
              "    return revised\n",
              "```\n",
              "The runtime of AC-3 is $O(cd^3)$. Note that $k = 1$ for node consistency, $k = 2$ for arc, and $k = 3$ for path. \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              "This becomes relevant when we have finished AC-3 and still have multiple values left for variable domains. This means we have to search for our final solution. The classic\n",
              "recursive solution to this is selecting one of the remaining values from the domain for an unassigned variable and trying it until either a solution is found or it fails and the algorithm \n",
              "restores the initial state and tries the next value. This is called a backtracking search which is modeled on the depth first search. This keeps only a single representation of an assignment\n",
              "and alters that representation rather than creating new ones. This backtracking search can be improved by using domain-independent heuristics. The first is variable and value ordering or the\n",
              "order in which we select unassigned variables to test. It is not optimal to just go in order of their existence in the set. Insteadn it is better to choose the most constrained varibale by following \n",
              "the minimum remaining-values heuristic. If all variables have the same domain size, they we use the degree heuristic which selects the variable that is involve din the largest number of constraints \n",
              "on other unassigned variables. Once a variable has been selected, we want to select the value in the domain that constraints the least number of neighboring variables known as the least \n",
              "constraining value heuristic. Once we begin a search the most effective tool to get to a solution is inference. One of the basic ways to do this is with forward checking where for each variable unassigned\n",
              "that is connected to another, remove any value that is inconsistent with the value recently choosen for the other variable. This is often combined with MRV heuristic though it has a problem of not \n",
              "looking far enough ahead. MAC or maintaining arc consistency helps up to remove inconsistencies further ahead. When backtracking, rather than going to the most recent decision we can also \n",
              "look at the variable that might fix the problem by looking for the conflict set (variables in conflict with an assignment) and use a backjumping method to the most recent assignments in that set. \n",
              "Note that backjumping is redundant if forward checking or MAC is used. \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              "We can also used local searches to solve CSPs the rest of the way. We get a complete assignment and then select randomly a conflicted variable and try to change that into something that \n",
              "is more correct. This algorithm is roughly independt of problem size making it particularly efficient. Tabu search is also sometimes used with a plateau search where a small list of recently visited states \n",
              "is forbidden from being returned to. We can also use constraint weighting where we focus the search on the more important constraints in the problem. \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              "We wnat to think about how to structure CSPs. One of the main ways we can do this is by decomposing it into subproblems. Independence can be found by looking for connected components in the\n",
              "constraint graph. Each connected component is its own subproblem. It is challenging to find completely independent subproblems but some graph structures are easier to solve than others. For example a tree \n",
              "constraint graph can be solved in time linear of number of variables. Arbitrary CSP solving takes exponenital time to number of variables. Tree structured CSPs can be solved using toposort to find the ordering for directional arc consistency. If we are given a graph that is \n",
              "not a tree, we can reduce it into a tree by either removing individual nodes or collapsing nodes into one. We can use the following procedure: \n",
              "\n",
              "    1. choose a subset of variables that we can remove to form a tree constraint graph (subset = cycle cutset)\n",
              "    2. remove from the domains of the remaning variables any values that are inconsistent with a legal assignment of the cutset and if the remaining CSP has a solution return that together with the cutset \n",
              "    assignment\n",
              "\n",
              "This process is known as cutset conditioning which is typically seen as NP complete. We can also do a tree decomposition wherein the original constraintgraph is transformed into a tree where each node has a\n",
              "set of variables. Tree decomposition reduces a CSP into a tree of subproblems. It must fit the following constraints: \n",
              "\n",
              "    * every variable has to appear in at least one node\n",
              "    * if two variables are involved in a constraint, they must appear together in at least one node\n",
              "    * if a variable is in two nodes it must also be in every node along the path connecting those two nodes\n",
              "\n",
              "We can solve a tree decomposition problem in $O(nd^2)$ time. Tree decomposition is more time efficient than cutset conditioning. \n",
              "\n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Relation** - each constraint contains $(scope, rel)$ where relation defines what values scope can have\n",
              "* **Partial assignment** - some variables are unassigned in CSP\n",
              "* **Partial solution** - a partial assignment that is still consistence\n",
              "* **Constraint graph** - nodes are variables and edges connect variables involved in a constraint\n",
              "* **Precedence constraints** - when some task must occur before another\n",
              "* **Disjunctive constraint** - two variables must not overlap in time, one has to come first\n",
              "* **Linear programming** - continuous domain CSP problems where constraints are equalities/inequalities\n",
              "* **Unary constraint** - restricts value of a single variable\n",
              "* **Binary constraint** - two variables participate, binary CSP uses only unary/binary constraints\n",
              "* **Global constraint** - arbitrary number of variables involved\n",
              "* **Preference constraints** - indicate which solutions are preferrable, typically used in constrained optimization problems\n",
              "* **Local consistency** - if we enforce constraints locally it ultimately will remove inconsistent values for the whole graph\n",
              "* **Node-consistent** - all values in the domain of a variable satisfy unary constraints\n",
              "* **Arc-consistent** - every value in domain satisfies binary constraints\n",
              "* **Path consistency** - strengthens binary constraints by implicitly inferred more constraints using triples of variables\n",
              "* **$k$-consistency** - if for any set of $k - 1$ variables, a constant value can always be assigned to any $k$th variable\n",
              "* **Strongly $k$-consistent** - graph is consistent for all values from $k$ to 1\n",
              "* **Bounds propogation** - constraining domains to upper and lower bounds\n",
              "* **Bounds-consistent** - if for every variable and for its upper/loewr bounds, some value satisfies the constraint\n",
              "* **Commutativity** - reduce the size of the search tree for a CSP, does not matter the variable assignment order\n",
              "* **Chronological backtracking** - the most recent decision is revisited when an error is found, not the most optimal\n",
              "* **Constraint learning** - finding minimum set of variables from a conflict set that solves the problem\n",
              "* **Min condlicts** - heuristic that selects value resulting in smallest number of conflicts with other variables\n",
              "* **Directional arc consistency** - given an ordering of variables, iff every X is arch consistent with every X ordered after it\n",
              "* **Value symmetry** - considering the permutations of ways to distribute some values to a set of variables\n",
              "* **Symmetry breaking constraint** - breaking the value symmetry in assignments of variables\n"
            ]
          },
          "metadata": {}
        }
      ],
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 541
        },
        "outputId": "f51aeef3-74ac-4ec6-b389-54aae53b8cbc"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Module 7 - Logical Agents"
      ],
      "metadata": {
        "id": "RYESi2kMybL8"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 19,
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"In AI, knowledge-based agents use a process of reasoning based on an internal representation of knowledge to make decisions and take actions. We define logic\n",
        "as the general representations used by knowledge-based agents to suit their purposes. The central aspect of a knowledge-based agent it is knowledge base (KB) which is a set of \n",
        "sentences in a language called knowledge representation language. These sentences contain some sort of assertion about the world and are called axioms when they are not derived \n",
        "from other sentences. Adding to the knowledge base and searching the knowledge base is donw through TELL and ASK operations which may include inferencing from old to new sentences.\n",
        "Inference is constrained by the idea that what is ASKed must follow from what was TOLD to the database previously. \n",
        "\n",
        "```\n",
        "def KB-agent(percept): \n",
        "    persistent: KB; t = counter\n",
        "\n",
        "    TELL(KB, make-percept-sentence(percept, t))\n",
        "    action = ASK(KB, make-action-query(t))\n",
        "    TELL(KB, make-action-sentence(action, t))\n",
        "    return action\n",
        "```\n",
        "\n",
        "Every time a knowledge-based agent program is called it has to tell the KB what it perceives. Then it asks the KB what action it should perform. And then the program tells the KB \n",
        "which action was selected and returns it to be executed. Note that ```make-percept-sentence``` creates a sentence saying that the agent perceived the given percept at some specific time. \n",
        "```make-action-query``` constructs a sentence that asks which action should be done. And then ```make-action-sentence``` creates a sentence telling which action should be carried out. \n",
        "These agents work independent of what occurs at the implementation level. Successful agents contain both declarative and procedural elements in its design where one can be compiled into \n",
        "the other. \"\"\"\n",
        "chapter7_2 = \"\"\"The wumpus world is a cave consisting of rooms connected by passageways where somewhere in the caves lies a wumpus that eats anyone who enters. The wumpus can be shot but \n",
        "the agent only has one arrow. Other rooms contain bottomless bits that will trap anyone who enteres. The only positive feature to this environment is a pile of gold in one of the rooms.\n",
        "This environment is deterministic, discrete, static, and single agent. It is sequential because many actions may need to be taken and it is only partially observable since we do not know \n",
        "the agent's location or availability of an arrow for example. \"\"\"\n",
        "chapter7_3 = \"\"\"Sentences contained in a knowledge base must be well formed in accordance with the syntax of its representation language. For example $x + y = 4$ is well formed but $x4y+=$ \n",
        "is not. A logic must also define the semantics of meaning of sentences. Semantics defines the truth of each sentence in terms of which world we are operating in. We often use the word model \n",
        "to describe this possible worlds in order to be more mathematically precise. For example, if sentence $\\\\alpha$ is true in model $m$, it must be that $m$ satisfies $\\\\alpha$ ($M(\\\\alpha)$ \n",
        "represents all models of $\\\\alpha$). Entailment occurs if and only if in every model which sentence $\\\\alpha$ is true, sentence $\\\\beta$ is also true $(M(\\\\alpha)\\\\subseteq M(\\\\beta))$. An\n",
        "inference algorithm that finds only entailed sentences is called truth preserving or sound. Soundness is very desirable because if not sound, an agent is making up things as it moves along.\n",
        "Learning practices allow us to draw connections between these logical reasoning processes and the real world such that rules can be generates from individual experiences and the truth of \n",
        "sentences can be defined by sensor data. \n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"We define propositional logic as a specific syntax and semantics that describe truth statements. The syntax specifies what is an allowable sentence. Atomic sentences consist of\n",
        "only a single symbol. Complex sentences are created from smaller sentences use parentheses and operators called logical connectives. The set of logical connectives consists of five symbols as \n",
        "follows: not ($\\\\not$) which is the negation of a value; and ($\\\\land$); or ($\\\\lor$); implies ($\\\\implies$); if and only if ($\\\\iff$). Note that implications are also known as rules of if-then \n",
        "statements. If and only if is called a biconditional. The not operator binds most tightly which means it only references the atomic sentence directly adjacent to it. Propositional logic semantics\n",
        "dictate that each symbol is given a value of true or false. We have the following five rules:\n",
        "\n",
        "    - $\\\\notP$ is true iff $P$ is false\n",
        "    - $P \\\\land Q$ is true iff both $P$ and $Q$ are true\n",
        "    - $P \\\\lor Q$ is true iff either $P$ or $Q$ is true\n",
        "    - $P \\\\implies Q$ is true unless $P$ is true and $Q$ is false\n",
        "    - $P \\iff Q$ is truee iff $P$ and $Q$ are both true or both false\n",
        "    \n",
        "We can represent these rules in truth tables which allow us to represent more complex information. We represent logical equivalence as $\\\\alpha \\\\equiv \\\\beta$ which is true only if the sentences entail\n",
        "each other. \n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"Determining satisfiability of sentences in propositional logic is referred to as the SAT problem. Note that validity and satisfiability are very closely linked with the following truth: \n",
        "$\\\\alpha \\\\models \\\\beta$ iff the sentence $\\\\alpha \\\\land \\\\not \\\\beta$ is unsatisfiable. The best known inference rule is called Modus Ponens which says that whenever $\\\\alpha \\\\implies \\\\beta$ and $\\\\alpha$ \n",
        "are given, we can infer $\\\\beta$. And-elimination is similar which says that if a conjunction is given, we can infer any of the conjuncts. With resolution, note that we can only have one copy of each literal\n",
        "at the end. We can remove multiply copies by factoring. Note that every sentence in propositional logic is logically equivalent to a conjunction of clauses (disjunctions of literals). \n",
        "An empty clause which is also a disjunction of no disjuncts is always false because a disjunction is true only if one of its disjuncts is true. Forward and backward chanining are algorithms which determine if \n",
        "a single symbol is entailed by a knowledge base of definite clauses. Backward chaining works backwards whether it finds all implications in the knowledge base that have the same specific conclusion. This is known \n",
        "as goal-directed reasoning while forward chaining is data driven reasoning.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Entailment can be applied to derive conclusions in a process known as logical inference.  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge level\" : \"we specify only what the agent knows and its goals in order to determine its behavior\",\n",
        "\"declarative\" : \"fill KB by telling sentences one by one until agent knows how to operate\", \n",
        "\"procedural\" : \"encodes specific behaviors directly into the program\", \n",
        "\"entailment\" : \"idea that one sentence follows logically from another sentence; $\\\\alpha \\\\models \\\\beta$ is sentnce $\\\\alpha$ entails sentence $\\\\beta$\",\n",
        "\"logical inference\" : \"entailment is applied to derive conclusions\", \n",
        "\"model checking\" : \"a type of inference algorithm which enumerates all possible models to check that $(M(KB)\\\\subseteq M(\\\\alpha))$\",\n",
        "\"completeness\" : \"an inference algorithm is this if it can derive any entailed sentence\", \n",
        "\"grounding\" : \"connection between logical reasoning processes and the agent's actual environment\", \n",
        "\"literal\" : \"an atomic sentence (positive) or a negated atomic sentence (negative)\", \n",
        "\"conjunction\" : \"sentence whose main connector symbol is $\\land$; individual parts are called conjuncts\", \n",
        "\"disjunction\" : \"sentence whose main connector symbol is $\\lor$; its parts are disjuncts\", \n",
        "\"implication\" : \"$\\\\implies$ where its premise or antecedent is the beginning and its conclusion or consequent is the end\", \n",
        "\"theorem proving\" : \"using rules of inference directly to sentences to contruct a proof without looking at models\", \n",
        "\"logical equivalence\" : \"two sentences if they are true in the same set of models\", \n",
        "\"validity\" : \"a sentence is valid is it is true in all models; also known as tautologies\", \n",
        "\"deduction theorem\" : \"for any sentences $\\\\alpha$ and $\\\\beta$, $\\\\alpha \\\\models \\\\beta$ iff $\\\\alpha \\\\implies \\\\beta$ is valid\", \n",
        "\"satisfiability\" : \"a sentence if there exists some model that it is true in/satisfies it\", \n",
        "\"monotonicity\" : \"entailed sentences can only increase when information is added to KB; additional info cannot invalidate a preexiting inference\",\n",
        "\"resolution\" : \"returning a complete inference algorithm in comvination with any complete search algorithm\", \n",
        "\"complementary literals\" : \"positive and negative literal of the same atomic sentence\", \n",
        "\"unit clause\" : \"single literal is also the disjunction of one literal\", \n",
        "\"conjunctive normal form\" : \"CNF; conjunction of clauses; AND of ORs\", \n",
        "\"resolution closure\" : \"set of clases which is derivable by continued use of the resolution rule\", \n",
        "\"ground resolution theorem\" : \"if a set of clauses is unsatisfiable then its resolution closure is an empty clause\", \n",
        "\"definite clause\" : \" disjunction of literals where exactly one is positive\", \n",
        "\"Horn clause\" : \"disjunction of literals which at most one is positive\", \n",
        "\"goal clauses\" : \"there are no positive literals in the clause\", \n",
        "\"AND-OR graph\" : \"edges joined by an arc represent a conjunction and edges without an arc are disjunction\", \n",
        "\"data driven reasoning\" : \"reasoning whose center of attention starts with what is known\"\n",
        "}\n",
        "\n"
      ],
      "outputs": [],
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 20,
      "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))"
      ],
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ],
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "In AI, knowledge-based agents use a process of reasoning based on an internal representation of knowledge to make decisions and take actions. We define logic\n",
              "as the general representations used by knowledge-based agents to suit their purposes. The central aspect of a knowledge-based agent it is knowledge base (KB) which is a set of \n",
              "sentences in a language called knowledge representation language. These sentences contain some sort of assertion about the world and are called axioms when they are not derived \n",
              "from other sentences. Adding to the knowledge base and searching the knowledge base is donw through TELL and ASK operations which may include inferencing from old to new sentences.\n",
              "Inference is constrained by the idea that what is ASKed must follow from what was TOLD to the database previously. \n",
              "\n",
              "```\n",
              "def KB-agent(percept): \n",
              "    persistent: KB; t = counter\n",
              "\n",
              "    TELL(KB, make-percept-sentence(percept, t))\n",
              "    action = ASK(KB, make-action-query(t))\n",
              "    TELL(KB, make-action-sentence(action, t))\n",
              "    return action\n",
              "```\n",
              "\n",
              "Every time a knowledge-based agent program is called it has to tell the KB what it perceives. Then it asks the KB what action it should perform. And then the program tells the KB \n",
              "which action was selected and returns it to be executed. Note that ```make-percept-sentence``` creates a sentence saying that the agent perceived the given percept at some specific time. \n",
              "```make-action-query``` constructs a sentence that asks which action should be done. And then ```make-action-sentence``` creates a sentence telling which action should be carried out. \n",
              "These agents work independent of what occurs at the implementation level. Successful agents contain both declarative and procedural elements in its design where one can be compiled into \n",
              "the other. \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              "The wumpus world is a cave consisting of rooms connected by passageways where somewhere in the caves lies a wumpus that eats anyone who enters. The wumpus can be shot but \n",
              "the agent only has one arrow. Other rooms contain bottomless bits that will trap anyone who enteres. The only positive feature to this environment is a pile of gold in one of the rooms.\n",
              "This environment is deterministic, discrete, static, and single agent. It is sequential because many actions may need to be taken and it is only partially observable since we do not know \n",
              "the agent's location or availability of an arrow for example. \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              "Sentences contained in a knowledge base must be well formed in accordance with the syntax of its representation language. For example $x + y = 4$ is well formed but $x4y+=$ \n",
              "is not. A logic must also define the semantics of meaning of sentences. Semantics defines the truth of each sentence in terms of which world we are operating in. We often use the word model \n",
              "to describe this possible worlds in order to be more mathematically precise. For example, if sentence $\\alpha$ is true in model $m$, it must be that $m$ satisfies $\\alpha$ ($M(\\alpha)$ \n",
              "represents all models of $\\alpha$). Entailment occurs if and only if in every model which sentence $\\alpha$ is true, sentence $\\beta$ is also true $(M(\\alpha)\\subseteq M(\\beta))$. An\n",
              "inference algorithm that finds only entailed sentences is called truth preserving or sound. Soundness is very desirable because if not sound, an agent is making up things as it moves along.\n",
              "Learning practices allow us to draw connections between these logical reasoning processes and the real world such that rules can be generates from individual experiences and the truth of \n",
              "sentences can be defined by sensor data. \n",
              "\n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "We define propositional logic as a specific syntax and semantics that describe truth statements. The syntax specifies what is an allowable sentence. Atomic sentences consist of\n",
              "only a single symbol. Complex sentences are created from smaller sentences use parentheses and operators called logical connectives. The set of logical connectives consists of five symbols as \n",
              "follows: not ($\\not$) which is the negation of a value; and ($\\land$); or ($\\lor$); implies ($\\implies$); if and only if ($\\iff$). Note that implications are also known as rules of if-then \n",
              "statements. If and only if is called a biconditional. The not operator binds most tightly which means it only references the atomic sentence directly adjacent to it. Propositional logic semantics\n",
              "dictate that each symbol is given a value of true or false. We have the following five rules:\n",
              "\n",
              "    - $\\notP$ is true iff $P$ is false\n",
              "    - $P \\land Q$ is true iff both $P$ and $Q$ are true\n",
              "    - $P \\lor Q$ is true iff either $P$ or $Q$ is true\n",
              "    - $P \\implies Q$ is true unless $P$ is true and $Q$ is false\n",
              "    - $P \\iff Q$ is truee iff $P$ and $Q$ are both true or both false\n",
              "    \n",
              "We can represent these rules in truth tables which allow us to represent more complex information. We represent logical equivalence as $\\alpha \\equiv \\beta$ which is true only if the sentences entail\n",
              "each other. \n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "Determining satisfiability of sentences in propositional logic is referred to as the SAT problem. Note that validity and satisfiability are very closely linked with the following truth: \n",
              "$\\alpha \\models \\beta$ iff the sentence $\\alpha \\land \\not \\beta$ is unsatisfiable. The best known inference rule is called Modus Ponens which says that whenever $\\alpha \\implies \\beta$ and $\\alpha$ \n",
              "are given, we can infer $\\beta$. And-elimination is similar which says that if a conjunction is given, we can infer any of the conjuncts. With resolution, note that we can only have one copy of each literal\n",
              "at the end. We can remove multiply copies by factoring. Note that every sentence in propositional logic is logically equivalent to a conjunction of clauses (disjunctions of literals). \n",
              "An empty clause which is also a disjunction of no disjuncts is always false because a disjunction is true only if one of its disjuncts is true. Forward and backward chanining are algorithms which determine if \n",
              "a single symbol is entailed by a knowledge base of definite clauses. Backward chaining works backwards whether it finds all implications in the knowledge base that have the same specific conclusion. This is known \n",
              "as goal-directed reasoning while forward chaining is data driven reasoning.\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Knowledge level** - we specify only what the agent knows and its goals in order to determine its behavior\n",
              "* **Declarative** - fill KB by telling sentences one by one until agent knows how to operate\n",
              "* **Procedural** - encodes specific behaviors directly into the program\n",
              "* **Entailment** - idea that one sentence follows logically from another sentence; $\\alpha \\models \\beta$ is sentnce $\\alpha$ entails sentence $\\beta$\n",
              "* **Logical inference** - entailment is applied to derive conclusions\n",
              "* **Model checking** - a type of inference algorithm which enumerates all possible models to check that $(M(KB)\\subseteq M(\\alpha))$\n",
              "* **Completeness** - an inference algorithm is this if it can derive any entailed sentence\n",
              "* **Grounding** - connection between logical reasoning processes and the agent's actual environment\n",
              "* **Literal** - an atomic sentence (positive) or a negated atomic sentence (negative)\n",
              "* **Conjunction** - sentence whose main connector symbol is $\\land$; individual parts are called conjuncts\n",
              "* **Disjunction** - sentence whose main connector symbol is $\\lor$; its parts are disjuncts\n",
              "* **Implication** - $\\implies$ where its premise or antecedent is the beginning and its conclusion or consequent is the end\n",
              "* **Theorem proving** - using rules of inference directly to sentences to contruct a proof without looking at models\n",
              "* **Logiacl equivalence** - two sentences if they are true in the same set of models\n",
              "* **Validity** - a sentence is valid is it is true in all models; also known as tautologies\n",
              "* **Deduction theorem** - for any sentences $\\alpha$ and $\\beta$, $\\alpha \\models \\beta$ iff $\\alpha \\implies \\beta$ is valid\n",
              "* **Satisfiability** - a sentence if there exists some model that it is true in/satisfies it\n",
              "* **Monotonicity** - entailed sentences can only increase when information is added to KB; additional info cannot invalidate a preexiting inference\n",
              "* **Resolution** - returning a complete inference algorithm in comvination with any complete search algorithm\n",
              "* **Complementary literals** - positive and negative literal of the same atomic sentence\n",
              "* **Unit clause** - single literal is also the disjunction of one literal\n",
              "* **Conjunctive normal form** - CNF; conjunction of clauses; AND of ORs\n",
              "* **Resolution closure** - set of clases which is derivable by continued use of the resolution rule\n",
              "* **Ground resolution theorem** - if a set of clauses is unsatisfiable then its resolution closure is an empty clause\n",
              "* **Definite clause** -  disjunction of literals where exactly one is positive\n",
              "* **Horn clause** - disjunction of literals which at most one is positive\n",
              "* **Goal clauses** - there are no positive literals in the clause\n",
              "* **And-or graph** - edges joined by an arc represent a conjunction and edges without an arc are disjunction\n",
              "* **Data driven reasoning** - reasoning whose center of attention starts with what is known\n"
            ]
          },
          "metadata": {}
        }
      ],
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 541
        },
        "outputId": "fd406b8c-6eaa-4be5-be5f-3639d4b7fa43"
      }
    },
    {
      "cell_type": "markdown",
      "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"
      ],
      "metadata": {
        "id": "vX7lbnJd4sT5"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 21,
      "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))"
      ],
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ],
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              "There are many ways to define artificial intelligence; some defining it in terms of similiarity to human behavior, others to\n",
              "an ability to act rationally. Alan Turing theorized the artificial intelligence as acting human definition with the Turing Test which asked whether \n",
              "a machine can think. He did not believe that physicial simulation of a person is necessary to show intelligence. On the other side, Aristotle defined \n",
              "irrefutable reasoning processes as based in laws of thought called logic. Computer agents are expected to operate alone, understand their environment, \n",
              "and adapt to change among other things. Incorporating rationality requires that they achieve the best outcome or best expected outcome given the circumstances.\n",
              "This is called the rational-agent approach which is generally seen as the standard AI model.\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              "John Searle theorized the difference between weak AI wherein a machine acted as if it were intelligent and strong AI \n",
              "wherein the machine is actually consciously thinking. Turing argued for the informality of behavior in which human behavior is too complicated \n",
              "to be represented by a formal set of rules and therefore can never be represented by a computer program.  \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              "In response to the question of whether machines can really think, John Searle proposed the Chinese Room argument which says \n",
              "that a human in a room copying down Chinese symbols and passing them to the outside world. The outside world sees a system that is taking \n",
              "Chinese sentence input and producing fluent responses in Chinese. However, we know that the person inside the room is only transcribing–it does\n",
              "not really have any understanding of what it is transcribing. \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " An agent in an environment can be represented by a human whose eyes, ears, and other organs are sensors, and hands, \n",
              "legs, are actuators. The environment it acts in can be anything but is usually just the part that directly affects the agent, its\n",
              "actions, and its perceptions. \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " One of the challenges of AI is determining whether its purpose is a desirable one. We define this as the problem of \n",
              "defining a performance measure. The concept of rationality depends on four things: the performance measure, the agent's understanding of its \n",
              "environment, the actions the agent can perform, and the agent's percept sequence so far. Note that our understanding of rationality does not\n",
              "require the agent to be omniscient. A rational agent should be learning from what it is taking in. It should also be autonomous in that it \n",
              "leanrs from its previously incorrect or partial knowledge.\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              "In order to define a task environment, we first want to think about what performance measure we want. In other words what \n",
              "are the desirable qualities we want for our agent. Then we want to think about the environment that will have the most influence on our\n",
              "agent. Then we think about the different actions (actuators) and sensors that are relevenat to our problem. There are various different \n",
              "properties of task environments including fully observable (sensors allow an agent to see complete state of environment all the time), \n",
              "partially observable (part of the state is missing from sensor data), single-agent vs. multiagent (in order to determine whether an object \n",
              "is an agent, we ask ourself if its job is to maximize performance measure which depends on the main agent's actions -- an example of this is chess and \n",
              "taxi driving), episodic vs. sequential (the current decision does not affect furture decisions vs. it does), static vs. dynamic (an ever changing \n",
              "environment), discrete vs. continuous (refers to time in the environment), known vs. unknown (how the agent knows the outcomes of the environment).\n",
              "\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              "Simple reflex agents are nice because they are simple but have limited intelligence. Only a little bit of unobservability can \n",
              "ruin the agent. Sometimes randomization can help use fix these problems but generally it is better to use more complex agents. In order to handle\n",
              "partial observability, the agent should keep track of an internal state which allows it to understand some of the currently unobserved parts of the\n",
              "current state. A model-based agent uses the transition model and sensor model to keep track of the state. Utility-based agents take in an additional\n",
              "utility function which analyzes its preferences among all the states. A learning agent is divided into four parts: the learning element which \n",
              "improves function, the performance elemnt which selects actions, and the critic which gives feedback on how the agent is doing. The problem generator\n",
              "is responsible for giving actions that will allow for exploration. \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment; includes program and architecture\n",
              "* **Rational agent** - selecting an action that is expected to maximize performance measure based on its analysis capabilities\n",
              "* **Simple reflect agent** - these types of agents select actions based only on current precept, ignoring everything else\n",
              "* **Precept** - the things that an agent's sensors are analyzing\n",
              "* **Rationality** - doing the right thing\n",
              "* **Turing test** - a computer passes if an interrogator cannot tell the difference between human responses and computer responses\n",
              "* **Syllogisms** - argument formats that always resulted in correct conclusions if given correct premises\n",
              "* **Consciousness** - an understanding of the outside world, oneself, and the idea that one is living; important to strong AI\n",
              "* **Consequentialism** - evaluating whether an action is right by analyzing the consequences of that action\n",
              "* **Omniscience** - this type of agent actually knows the consequences of its actions but is impossible in reality\n",
              "* **Information gathering** - strategically selecting actions in order to modify future percepts\n",
              "* **Task environments** - the problems or situations to which agents are the solutions\n",
              "* **Peas** - performance, environment, actuators, sensors; help you to define a task environment\n",
              "* **Unobservable** - the environment if we have an agent with no sensors\n",
              "* **Deterministic** - when the next state in the environment is completely determined by the current state and any actions taken\n",
              "* **Nondeterministic** - when the next state cannot be predicted based on current information\n",
              "* **Transition model** - keeps track of how the environment changes over time\n",
              "* **Sensor model** - how the state of the world is reflect in an agent's current analysis\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "Strongly typed means that every object has a fixed type.\n",
              "In other words, you would not be allowed to combine two objects with different types like\n",
              "\"hello\" + 3. Dynamically typed means that the type is established at the same time that the\n",
              "variable is defined. So when you write x = \"hello\", the type of x is automatically defined\n",
              "as string.\n",
              "\n",
              "```is``` checks whether variables point to the same object while == checks whether variables point to \n",
              "objects of the same value\n",
              "\n",
              "Strings are immutable which means we cannot reassign values. Lists on the other hand are mutable. \n",
              "We can get a shallow copy of any sequence by doing $y = x[:]$. Tuples are immutable and can be of mixed\n",
              "type. Strings cannot have mixed types but lists can. Accessing items in a string/tuple/list is just $x[1]$.\n",
              "You can also use negative index to get from the right. We can also use slicing to get sequences using the following\n",
              "format: object[start][end][$n$th element]. Sorted(list) will return a copy while list.sort() will sort in place. \n",
              "\n",
              "Dictionaries are unordered and work by hashing so keys have to be immutable. In otherwords, we cannot use lists as \n",
              "keys. If we query a for a key that does not exist, we will get an error. dict.keys() returns a list of the current keys\n",
              "and dict.values() returns a list of the current values. dict.items() returns a list of the item tuples. Default dictionaries \n",
              "automatically initialize nonexistence dictionary values. We also have a class called Counter which creates a a default dictionary\n",
              "to count number of time values appear. \n",
              "\n",
              "Python does not allow function overloading and it is identified by its name only. Functions are first-class objects which means \n",
              "they can be passed as arguments, returned, and assigned as variables/stored in data structures. We instantiate an object using \n",
              "the ``` def __init__(attributes)``` method\n",
              "\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "An agent has a four step problem solving process as follows: first they goal formulate, allowing them to \n",
              "know which actions to consider. Then they problem formulate which consists of coming up with a descriptions of the states and\n",
              "different actions that might be involved in reaching the goal. Then the agent has to search in which it\n",
              "performs a sequence of actions until it finds the goal. The final step is the agent executing the solution it has found through \n",
              "the search step. Note that in a fully observable, deterministic, known environment that solution is fixed. If not, the solution\n",
              "would be a branching solution with different plans depending on stimuli. We can define a search problem as containing the following:\n",
              "a set of states called the state space, the initial state that the agent starts in, a set of goal state/s, the actions availble to the\n",
              "agent, a transition model telling us what each action does, and an action cost function that tells us how much it would cost to carry\n",
              "out a certain action. We represent the state space typically as a graph. \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              "Example search problems consist of two types: standardized problems which reflect the methods being used and real world\n",
              "problems that implement the methods in real life. A great model of the search problem is the sliding tile puzzle where tiles are moved in order\n",
              "to get all the numbers in a correct order. Note that the actions are very clearly defined as up, down, left, right and that states are just the\n",
              "different orientations of the tiles on the board.\n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "This focuses on solving search problems using search trees which represent a subset of the state space. Each node is a state\n",
              "where the root is the initial state of the problem. Best-first search is the first idea of how to expand the frontier of a search algorithm. \n",
              "By using different evaluation functions, we get different algorithms. Many of the algorithms use a queue to hold the frontier, including a priority\n",
              "queue, a FIFO queue, and a LIFO queue. We measure the performance of search algorithms using a few different measures. The first being completeness\n",
              "which refers to whether it will return a solution or failure. Cost optimality is whether we return an optimal solution with lowest path cost. Time \n",
              "and space complexity analyze the efficiency of runtime and space usage. Both are typically measured using $d$ for depth which is number of actions in\n",
              "the optimal solution and $b$ for branching factor which is the number of children nodes that need to be explores at each step.\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " BFS alwasy finds an optimal solution have time and space complexity are $O(b^d)$. The memory is typically the reason it isn't super \n",
              "efficient. The runtime of uniform cost search is $O(b^{1 + \\frac{C^*}{\\epsilon} })$ which can be worse than BFS since more of the tree may be explored. \n",
              "```\n",
              "def BFS():\n",
              "      frontier = FIFO queue with start\n",
              "      reached = start\n",
              "      while frontier is not empty: \n",
              "        curr = pop frontier\n",
              "        for each child of curr: \n",
              "            if child is goal return\n",
              "            else if not seen yet add to reached and add to frontier\n",
              "``` \n",
              "\n",
              "If we want to save space and a tree search is possible we want to use DFS over BFS. DFS does not always return an optimal solution and is not complete. \n",
              "But when finite, DFS has a memory complexity of $O(bm)$ where $b$ is the branching factor and $m$ is maximum depth of the tree. The space complexity can be further\n",
              "reduced using backtracking search which gets us to $O(m)$. Depth limited is complete if we made a good choice for $l$ and \n",
              "has time of $O(b^l)$ and space of $O(bl)$. Bidirectional search is complete and optimal cost as is iterative deepening. Bidirectional search has runtime of \n",
              "$O(b^{d/2})$ vs iterative with $O(b^d)$ time and $O(bd)$ space. \n",
              "\n",
              "```\n",
              "def IterativeD():\n",
              "    for depth = 0 to infinity: \n",
              "        depth-limited-search(curr_depth)\n",
              "```\n",
              "\n",
              "\n",
              "```\n",
              "def BiDiSearch():\n",
              "    queueStart\n",
              "    queueEnd\n",
              "    while not finished: \n",
              "      if min value is in start frontier:\n",
              "        proceed with search on start frontier\n",
              "        else proceed with search on end frontier\n",
              "```\n",
              "\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **Open-loop system** - once a solution has been found an agent can ignore percepts while executing\n",
              "* **Closed-loop system** - if it's possible that the solution is incorrect, better to still monitor percepts\n",
              "* **Path** - a selection of actions; a solution is a path from start to goal\n",
              "* **Optimal solution** - has lowest path cost of all solutions; assume costs are positive\n",
              "* **Grid world problem** - 2D array of cells which agents move between such as the vacuum problem\n",
              "* **Search algorithm** - takes problem as input and returns solution or failure\n",
              "* **Frontier** - the nodes of a search tree currently being explored\n",
              "* **Best-first search** - choose nodes with minium value of evaluation function, $f(n)$\n",
              "* **Priority queue** - used in best-first search, has a key value for each element\n",
              "* **Fifo queue** - first in first out used in BFS\n",
              "* **Lifo queue** - last in first out also known as a stack, used in DFS\n",
              "* **Cycle** - special case of a redunance path which is something we've already seen in our tree\n",
              "* **Graph search** - checks for already redundant paths; opposite of tree search\n",
              "* **Breadth first search** - root expanded first then all children then children's child, keeping track of reached\n",
              "* **Early goal test** - checks whether a node is a solution as soon as it is reached rather than until it leaves queue (BFS)\n",
              "* **Uniform cost search** - dijkstra's where the least cost node is always expanded, complete, cost-optimal\n",
              "* **Depth first search** - explores deepest node in the queue first with no reached states tracked\n",
              "* **Depth limited search** - modification of DFS that allows us to not go on infinite path\n",
              "* **Iterative deepening search** - selects good $l$ by trying al values until a solution or failure is returned\n",
              "* **Bidirectional search** - searches forward from start and backward from goal \n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "Informed search strategies are much more efficient at finding solutions to search problems. The most basic version\n",
              "is greedy best-first search, an interation of best-first search based on use of heuristic function where nodes are expanded with lowest\n",
              "$h(n)$ value. Note that uniform cost search is a greedy algorithm with only $g(n)$. It is complete in finite spaces but not in infinite ones. With good heuristic the complexity can be reduced from $O(|V|)$ to \n",
              "$O(bm)$. The evaluation function gives us the best path between where we currently are and the goal. A* is complete and its optimality depends\n",
              "on how good its heuristic is. If the heuristic is admissible, the A* is cost optimal. A* with a consistence heuristic is defined as optimally efficient\n",
              "in that it goes to all surely expanded nodes. Though A* has a lot of benefits, the number of nodes expanded can be exponential. Using an inadmissible \n",
              "heuristic can result in less optimal solutions but also possibly reduces number of nodes expanded. To reduce memory useage, we can keep reference counts which are the number of times\n",
              "a state has been reached. RBFS and SMA* are optimal search algorithms that help conserve memory. They can solve problems that A* would have run out\n",
              "of memory for.\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "Designing a good heuristic has direct implications for the efficiency of A*. We look at relaxed problems to increase\n",
              "efficiency where more actions are given to each node. We can also look at solutions for subproblems of the given problem to act as heuristics.\n",
              "This cost acts as a lower bound for the cost on the full problem. All the possible subproblems are stored in a pattern database. One can also define landmarks and \n",
              "learn from the experiences within the problem itself.\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Informed search** - has access to domain specific info about where the goals are\n",
              "* **Heuristic function** - $h(n)$ or estimated cost of minimal path from current node to goal node\n",
              "* **Straight line distance** - heuristic that calculates distance if line drawn from curr to goal\n",
              "* **A* search** - uses evaluation function $f(n) = g(n) + h(n) where g(n) is path cost from start to current node\n",
              "* **Admissibility** - an admissible heuristic never overestimates the remaining cost to get to the goal\n",
              "* **Consistency** - if the heuristic of current node is always less than sum of true cost plus heuristic of next node\n",
              "* **Monotonic** - value of g always increases as you move along your search\n",
              "* **Surely expanded nodes** - A* will expand all nodes where $f(n) < C^*$ where $C^*$ is optimal cost\n",
              "* **Pruning** - A* does not search nodes with higher costs, does not move in that direction\n",
              "* **Satisficing** - solutions that are not optimal but good enough, allow us to explore fewer nodes\n",
              "* **Weighted a* search** - use a sort of detour index to weight the heuristic value more heavily; $f(n) = g(n) + W \\cdot h(n)$\n",
              "* **Beam search** - conserves memory by only keeping $k$ nodes with best f values\n",
              "* **Iterative deepening a* search** - just like for DFS where we don't keep all reached states in memory\n",
              "* **Manhattan distance** - city block distance which is the sum of the distance of all tiles to goal using horizontal and vertical\n",
              "* **Effective branching factor** - good heuristic has value close to 1, branching factor for tree with depth $d$ to have $N + 1$ nodes\n",
              "* **Dominates** - $h_2(n) \\ge h_1(n)$ for any node $n$ so $h_2$ would dominante\n",
              "* **Relaxed problem** - fewer restrictions on actions taken by each node\n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "These consist of multiagent environments. One of the most popular types of games to study are perfect information\n",
              "zero sum games where tehy are fully observable and what is good for one player is to the other player's detriment. We define the two \n",
              "players as MIN and MAX where MAX goes first. \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "For games with multiple outcomes we want to use minimax search. Optimal play for MAX assumes that MIN also plays optimally. \n",
              "The minimax decision is set at the root which is the decision made by MAX to maximize its minimax value. The minimax search algorithm tries all actions\n",
              "and chooses the one with the high minimax value. It moves down all the way to the leaves and then backs up, passing the values up the tree.\n",
              "\n",
              "```\n",
              "def minimax():\n",
              "    value, move <- max-value(game, state)\n",
              "\n",
              "def max-value():\n",
              "    for each child in current move: \n",
              "        new-value = min-value(game, child)\n",
              "\n",
              "        if new-value > curr-value:\n",
              "            reset move\n",
              "            alpha = max(new-value, alpha)\n",
              "        if new-value $\\ge \\beta$:\n",
              "            return\n",
              "\n",
              "def min-value():\n",
              "    for each child in current move:\n",
              "        new-value = max-value(game, child)\n",
              "        if new-value < curr-value: \n",
              "            reset move\n",
              "            beta = min(new-value, beta)\n",
              "        if new-value $\\le \\alpha$:\n",
              "            return\n",
              "```\n",
              "Minimax algorithm has a runtime of $O(b^m)$ and space complexity of $O(bm)$. This makes minimax inefficient for more complex games\n",
              "We decrease the exponential depth of the game tree using alpha-beta pruning which limites parts of the tree that do not affect the outcome.\n",
              "Consider some value: if the current player has a better choice either at the same level or higher up in the tree, it will never select\n",
              "that value. Let $\\alpha$ be the value of the best (highest) choice we have so far for MAX (at least) and let $\\beta$ be the value of the best (lowest) choice \n",
              "we have found so far for MIN (at most). The effectiveness of this strategy is dependent on the order we examine the states.\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "We can use heuristic evaluation functions to treat nonterminal nodes like they are terminal and thereby cut off the search early. This\n",
              "converts the general idea of alpha beta into a tree search algorithm. This heuristic returns an estimate value of the utility of a particular\n",
              "state to the current player. We can also implement a cutoff that allows us to only explore to some fixed depth. \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "Some games called stochastic games include an element of randomization which require the use of chance nodes. These\n",
              "denote things like the possibility of different dice rolls, each of which will result in a different move strategy. We compute the expected\n",
              "value for the chance nodes of that particular outcome. In order to cut off the search with expectiminimax, we need to modify our evaluation functions \n",
              "a bit by only returning values that are a positive value of the probability of winning. The runtime of this algorithm is $O(b^m n^m)$ where $n$ is the\n",
              "number of distinct dice rolls. Note that we can still prune chance nodes using alpha beta pruning with a little bit of modification.\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "Assume that there is some level of uncertainity felt by an agend about some state $s$ to get $P(s)$ for each state. Decision theory addresses the\n",
              "issue of choosing among actions based on how desirable their immediate outcome is. We want to find the expected utility \n",
              "of a particular choice given the evidence which can be found by averaging all the utility values of the outcomes mutiplied by the probability\n",
              "that it occurs. MEU principle gives a general idea of what an intelligent agent needs to do in order to do the right thing but does not give ways\n",
              "to actualize it. \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "Think of the set of outcomes of an action as a lottery in which each action represents a ticket. Each lottery contains a set of possible outcomes\n",
              "all assigned specific probabilities. Each outcome is either a state or another lottery. With utility theory, the goal is to understand preferences with regards to\n",
              "complex lotteries and their relationships to the states within them. An agent that violates the axioms of utility theory will exhibit irrational behavior. \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Utility functions are relevant for mapping the lotteries described above to real numbers. Using a process call preference eliciation, we can\n",
              "help design a system that can make decisions or act on behalf of a human. This process requires us to present choices to the human and decide by observing on the underlying\n",
              "utility function representing that person's preferences. Agents that are risk averse show a curve that for any lottery, the utility of getting the lottery is less than\n",
              "just the expected money of the lottery. On the opposite end are risk seeking.  \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Pruning** - restricts game play by ignoring parts of search tree that are inconsequential\n",
              "* **Utility function** - an agent's preferences that assign a single value to each state; $U(s)$\n",
              "* **Minimax value** - the utility for MAX in that state assuming both players are playing optimally until the end\n",
              "* **Horizon effect** - when the opponent's move causes damage and is unavoidable but can be prolonged by a sequence of moves\n",
              "* **Forward pruning** - removes moves that appear to be bad but might be good; see beam search\n",
              "* **Stochastic games** - include some element of randomization like dice throwing\n",
              "* **Chance nodes** - denote information about randomized elements of the game\n",
              "* **Expectiminimax value** - is a generalization of the minimaz value for games with chance nodes\n",
              "* **Maximum expected utility** - rational agent chooses the action to maximize expected utility\n",
              "* **Orderability** - given two lotteries a rational agent must prefer one or think both are equal, must make a decision\n",
              "* **Transitivity** - if an agent prefers A to B and C to C then it prefers A to C\n",
              "* **Continuity** - if lottery B is between two others, the agent will be indifferent toward getting it or the other two\n",
              "* **Substitutability** - if indifferent between two choices, also indifferent if both are added to another lotter\n",
              "* **Monotonicity** - if outcomes are the same and agent prefers one lottery, it must prefer the one with the higher probability\n",
              "* **Decomposability** - lotteries can be reduced to smaller ones using probability laws\n",
              "* **Value function/ordinal utility function** - in deterministic game play, agent only needs preference ranking on the states invovled\n",
              "* **Normalized utilities** - use a scale of 0 and 1 to assign utility to things\n",
              "* **Certainty equivalent** - value an agent accepts instead of a lottery\n",
              "* **Optimizer's curse** - overestimating the expected utility of best choice\n",
              "* **Certainity effect** - people prefer gains that are certain\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "A constraint satisfaction problem consists of three parts: $X$ a set of variables, $D$ a set of domains for each variable, and $C$ a set of constraints that specify\n",
              "which combinations of values are allowed. Each constraint containing the scope or tuple of variables and the relation can be represented explicitly with the allowed values or as a\n",
              "function computing which values are allowed. CSPs allow us to assign values to variables such that we can create consistent assignments that do not violate specific constraints. A \n",
              "solution to a CSP must be consistent and complete in that all variables are assigned a value legally. One reason that CSPs are often used is because it is easy to formulate problems\n",
              "as such and solvers remove large parts of the search space. Once we have found a partial assignment that violates constraints, we can immiedately stop refining it and also see which \n",
              "variables are causing the problem allowing us to focus on them directly. The easiest CSPs to solve are ones with discrete, finite domains. No solution exists for solving nonlinear \n",
              "constraints with integer variables. Some more unique CSP problems can be respresented as crytarithmetic puzzles where each letter is a different number. These can be reflected in \n",
              "constraint hypergraphs which have nodes and hypernodes to represent n-ary constraints.\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "CSPs proceed forward by either creating successors through a new variable assignment or an inference called constraint propogation where constraints are used to reduce \n",
              "the number of legal moves allowed for a variable. We want to enforce node and arc consistency on the graphs. The most popular algorithm for enforcing arc consistency is AC-3. Note that \n",
              "some problems like the map coloring problem are not relevant for arc consistency; in other words, there is no way to enforce it. AC-3 maintains a queue of all the different arcs in the \n",
              "problem and then makes the variables involved fit the constraints. If something gets revised we readd it to the queue otherwise we move on. Doing this ultimately allows us to either solve \n",
              "the problem completely, determine that it is unsolvable (domain of 0) or reduce the domain enough to create a faster search. Note that AC-3 returns false if an inconsistency is found.\n",
              "\n",
              "```\n",
              "def AC-3: \n",
              "    queue = arcs of CSP\n",
              "\n",
              "    while queue not empty: \n",
              "        (x, y) = pop queue\n",
              "        if revise (x,y):\n",
              "            if size of domain = 0 then return false\n",
              "            for each neighbor of x: \n",
              "                add (n, x) to queue\n",
              "    return true\n",
              "\n",
              "def revise: \n",
              "    for each x in domain of variable: \n",
              "        if no value in D allows constraint to be satisfied\n",
              "        delete x from D\n",
              "        revised = true\n",
              "    return revised\n",
              "```\n",
              "The runtime of AC-3 is $O(cd^3)$. Note that $k = 1$ for node consistency, $k = 2$ for arc, and $k = 3$ for path. \n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              "This becomes relevant when we have finished AC-3 and still have multiple values left for variable domains. This means we have to search for our final solution. The classic\n",
              "recursive solution to this is selecting one of the remaining values from the domain for an unassigned variable and trying it until either a solution is found or it fails and the algorithm \n",
              "restores the initial state and tries the next value. This is called a backtracking search which is modeled on the depth first search. This keeps only a single representation of an assignment\n",
              "and alters that representation rather than creating new ones. This backtracking search can be improved by using domain-independent heuristics. The first is variable and value ordering or the\n",
              "order in which we select unassigned variables to test. It is not optimal to just go in order of their existence in the set. Insteadn it is better to choose the most constrained varibale by following \n",
              "the minimum remaining-values heuristic. If all variables have the same domain size, they we use the degree heuristic which selects the variable that is involve din the largest number of constraints \n",
              "on other unassigned variables. Once a variable has been selected, we want to select the value in the domain that constraints the least number of neighboring variables known as the least \n",
              "constraining value heuristic. Once we begin a search the most effective tool to get to a solution is inference. One of the basic ways to do this is with forward checking where for each variable unassigned\n",
              "that is connected to another, remove any value that is inconsistent with the value recently choosen for the other variable. This is often combined with MRV heuristic though it has a problem of not \n",
              "looking far enough ahead. MAC or maintaining arc consistency helps up to remove inconsistencies further ahead. When backtracking, rather than going to the most recent decision we can also \n",
              "look at the variable that might fix the problem by looking for the conflict set (variables in conflict with an assignment) and use a backjumping method to the most recent assignments in that set. \n",
              "Note that backjumping is redundant if forward checking or MAC is used. \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              "We can also used local searches to solve CSPs the rest of the way. We get a complete assignment and then select randomly a conflicted variable and try to change that into something that \n",
              "is more correct. This algorithm is roughly independt of problem size making it particularly efficient. Tabu search is also sometimes used with a plateau search where a small list of recently visited states \n",
              "is forbidden from being returned to. We can also use constraint weighting where we focus the search on the more important constraints in the problem. \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              "We wnat to think about how to structure CSPs. One of the main ways we can do this is by decomposing it into subproblems. Independence can be found by looking for connected components in the\n",
              "constraint graph. Each connected component is its own subproblem. It is challenging to find completely independent subproblems but some graph structures are easier to solve than others. For example a tree \n",
              "constraint graph can be solved in time linear of number of variables. Arbitrary CSP solving takes exponenital time to number of variables. Tree structured CSPs can be solved using toposort to find the ordering for directional arc consistency. If we are given a graph that is \n",
              "not a tree, we can reduce it into a tree by either removing individual nodes or collapsing nodes into one. We can use the following procedure: \n",
              "\n",
              "    1. choose a subset of variables that we can remove to form a tree constraint graph (subset = cycle cutset)\n",
              "    2. remove from the domains of the remaning variables any values that are inconsistent with a legal assignment of the cutset and if the remaining CSP has a solution return that together with the cutset \n",
              "    assignment\n",
              "\n",
              "This process is known as cutset conditioning which is typically seen as NP complete. We can also do a tree decomposition wherein the original constraintgraph is transformed into a tree where each node has a\n",
              "set of variables. Tree decomposition reduces a CSP into a tree of subproblems. It must fit the following constraints: \n",
              "\n",
              "    * every variable has to appear in at least one node\n",
              "    * if two variables are involved in a constraint, they must appear together in at least one node\n",
              "    * if a variable is in two nodes it must also be in every node along the path connecting those two nodes\n",
              "\n",
              "We can solve a tree decomposition problem in $O(nd^2)$ time. Tree decomposition is more time efficient than cutset conditioning. \n",
              "\n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Relation** - each constraint contains $(scope, rel)$ where relation defines what values scope can have\n",
              "* **Partial assignment** - some variables are unassigned in CSP\n",
              "* **Partial solution** - a partial assignment that is still consistence\n",
              "* **Constraint graph** - nodes are variables and edges connect variables involved in a constraint\n",
              "* **Precedence constraints** - when some task must occur before another\n",
              "* **Disjunctive constraint** - two variables must not overlap in time, one has to come first\n",
              "* **Linear programming** - continuous domain CSP problems where constraints are equalities/inequalities\n",
              "* **Unary constraint** - restricts value of a single variable\n",
              "* **Binary constraint** - two variables participate, binary CSP uses only unary/binary constraints\n",
              "* **Global constraint** - arbitrary number of variables involved\n",
              "* **Preference constraints** - indicate which solutions are preferrable, typically used in constrained optimization problems\n",
              "* **Local consistency** - if we enforce constraints locally it ultimately will remove inconsistent values for the whole graph\n",
              "* **Node-consistent** - all values in the domain of a variable satisfy unary constraints\n",
              "* **Arc-consistent** - every value in domain satisfies binary constraints\n",
              "* **Path consistency** - strengthens binary constraints by implicitly inferred more constraints using triples of variables\n",
              "* **$k$-consistency** - if for any set of $k - 1$ variables, a constant value can always be assigned to any $k$th variable\n",
              "* **Strongly $k$-consistent** - graph is consistent for all values from $k$ to 1\n",
              "* **Bounds propogation** - constraining domains to upper and lower bounds\n",
              "* **Bounds-consistent** - if for every variable and for its upper/loewr bounds, some value satisfies the constraint\n",
              "* **Commutativity** - reduce the size of the search tree for a CSP, does not matter the variable assignment order\n",
              "* **Chronological backtracking** - the most recent decision is revisited when an error is found, not the most optimal\n",
              "* **Constraint learning** - finding minimum set of variables from a conflict set that solves the problem\n",
              "* **Min condlicts** - heuristic that selects value resulting in smallest number of conflicts with other variables\n",
              "* **Directional arc consistency** - given an ordering of variables, iff every X is arch consistent with every X ordered after it\n",
              "* **Value symmetry** - considering the permutations of ways to distribute some values to a set of variables\n",
              "* **Symmetry breaking constraint** - breaking the value symmetry in assignments of variables\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "In AI, knowledge-based agents use a process of reasoning based on an internal representation of knowledge to make decisions and take actions. We define logic\n",
              "as the general representations used by knowledge-based agents to suit their purposes. The central aspect of a knowledge-based agent it is knowledge base (KB) which is a set of \n",
              "sentences in a language called knowledge representation language. These sentences contain some sort of assertion about the world and are called axioms when they are not derived \n",
              "from other sentences. Adding to the knowledge base and searching the knowledge base is donw through TELL and ASK operations which may include inferencing from old to new sentences.\n",
              "Inference is constrained by the idea that what is ASKed must follow from what was TOLD to the database previously. \n",
              "\n",
              "```\n",
              "def KB-agent(percept): \n",
              "    persistent: KB; t = counter\n",
              "\n",
              "    TELL(KB, make-percept-sentence(percept, t))\n",
              "    action = ASK(KB, make-action-query(t))\n",
              "    TELL(KB, make-action-sentence(action, t))\n",
              "    return action\n",
              "```\n",
              "\n",
              "Every time a knowledge-based agent program is called it has to tell the KB what it perceives. Then it asks the KB what action it should perform. And then the program tells the KB \n",
              "which action was selected and returns it to be executed. Note that ```make-percept-sentence``` creates a sentence saying that the agent perceived the given percept at some specific time. \n",
              "```make-action-query``` constructs a sentence that asks which action should be done. And then ```make-action-sentence``` creates a sentence telling which action should be carried out. \n",
              "These agents work independent of what occurs at the implementation level. Successful agents contain both declarative and procedural elements in its design where one can be compiled into \n",
              "the other. \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              "The wumpus world is a cave consisting of rooms connected by passageways where somewhere in the caves lies a wumpus that eats anyone who enters. The wumpus can be shot but \n",
              "the agent only has one arrow. Other rooms contain bottomless bits that will trap anyone who enteres. The only positive feature to this environment is a pile of gold in one of the rooms.\n",
              "This environment is deterministic, discrete, static, and single agent. It is sequential because many actions may need to be taken and it is only partially observable since we do not know \n",
              "the agent's location or availability of an arrow for example. \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              "Sentences contained in a knowledge base must be well formed in accordance with the syntax of its representation language. For example $x + y = 4$ is well formed but $x4y+=$ \n",
              "is not. A logic must also define the semantics of meaning of sentences. Semantics defines the truth of each sentence in terms of which world we are operating in. We often use the word model \n",
              "to describe this possible worlds in order to be more mathematically precise. For example, if sentence $\\alpha$ is true in model $m$, it must be that $m$ satisfies $\\alpha$ ($M(\\alpha)$ \n",
              "represents all models of $\\alpha$). Entailment occurs if and only if in every model which sentence $\\alpha$ is true, sentence $\\beta$ is also true $(M(\\alpha)\\subseteq M(\\beta))$. An\n",
              "inference algorithm that finds only entailed sentences is called truth preserving or sound. Soundness is very desirable because if not sound, an agent is making up things as it moves along.\n",
              "Learning practices allow us to draw connections between these logical reasoning processes and the real world such that rules can be generates from individual experiences and the truth of \n",
              "sentences can be defined by sensor data. \n",
              "\n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "We define propositional logic as a specific syntax and semantics that describe truth statements. The syntax specifies what is an allowable sentence. Atomic sentences consist of\n",
              "only a single symbol. Complex sentences are created from smaller sentences use parentheses and operators called logical connectives. The set of logical connectives consists of five symbols as \n",
              "follows: not ($\\not$) which is the negation of a value; and ($\\land$); or ($\\lor$); implies ($\\implies$); if and only if ($\\iff$). Note that implications are also known as rules of if-then \n",
              "statements. If and only if is called a biconditional. The not operator binds most tightly which means it only references the atomic sentence directly adjacent to it. Propositional logic semantics\n",
              "dictate that each symbol is given a value of true or false. We have the following five rules:\n",
              "\n",
              "    - $\\notP$ is true iff $P$ is false\n",
              "    - $P \\land Q$ is true iff both $P$ and $Q$ are true\n",
              "    - $P \\lor Q$ is true iff either $P$ or $Q$ is true\n",
              "    - $P \\implies Q$ is true unless $P$ is true and $Q$ is false\n",
              "    - $P \\iff Q$ is truee iff $P$ and $Q$ are both true or both false\n",
              "    \n",
              "We can represent these rules in truth tables which allow us to represent more complex information. We represent logical equivalence as $\\alpha \\equiv \\beta$ which is true only if the sentences entail\n",
              "each other. \n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "Determining satisfiability of sentences in propositional logic is referred to as the SAT problem. Note that validity and satisfiability are very closely linked with the following truth: \n",
              "$\\alpha \\models \\beta$ iff the sentence $\\alpha \\land \\not \\beta$ is unsatisfiable. The best known inference rule is called Modus Ponens which says that whenever $\\alpha \\implies \\beta$ and $\\alpha$ \n",
              "are given, we can infer $\\beta$. And-elimination is similar which says that if a conjunction is given, we can infer any of the conjuncts. With resolution, note that we can only have one copy of each literal\n",
              "at the end. We can remove multiply copies by factoring. Note that every sentence in propositional logic is logically equivalent to a conjunction of clauses (disjunctions of literals). \n",
              "An empty clause which is also a disjunction of no disjuncts is always false because a disjunction is true only if one of its disjuncts is true. Forward and backward chanining are algorithms which determine if \n",
              "a single symbol is entailed by a knowledge base of definite clauses. Backward chaining works backwards whether it finds all implications in the knowledge base that have the same specific conclusion. This is known \n",
              "as goal-directed reasoning while forward chaining is data driven reasoning.\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Knowledge level** - we specify only what the agent knows and its goals in order to determine its behavior\n",
              "* **Declarative** - fill KB by telling sentences one by one until agent knows how to operate\n",
              "* **Procedural** - encodes specific behaviors directly into the program\n",
              "* **Entailment** - idea that one sentence follows logically from another sentence; $\\alpha \\models \\beta$ is sentnce $\\alpha$ entails sentence $\\beta$\n",
              "* **Logical inference** - entailment is applied to derive conclusions\n",
              "* **Model checking** - a type of inference algorithm which enumerates all possible models to check that $(M(KB)\\subseteq M(\\alpha))$\n",
              "* **Completeness** - an inference algorithm is this if it can derive any entailed sentence\n",
              "* **Grounding** - connection between logical reasoning processes and the agent's actual environment\n",
              "* **Literal** - an atomic sentence (positive) or a negated atomic sentence (negative)\n",
              "* **Conjunction** - sentence whose main connector symbol is $\\land$; individual parts are called conjuncts\n",
              "* **Disjunction** - sentence whose main connector symbol is $\\lor$; its parts are disjuncts\n",
              "* **Implication** - $\\implies$ where its premise or antecedent is the beginning and its conclusion or consequent is the end\n",
              "* **Theorem proving** - using rules of inference directly to sentences to contruct a proof without looking at models\n",
              "* **Logiacl equivalence** - two sentences if they are true in the same set of models\n",
              "* **Validity** - a sentence is valid is it is true in all models; also known as tautologies\n",
              "* **Deduction theorem** - for any sentences $\\alpha$ and $\\beta$, $\\alpha \\models \\beta$ iff $\\alpha \\implies \\beta$ is valid\n",
              "* **Satisfiability** - a sentence if there exists some model that it is true in/satisfies it\n",
              "* **Monotonicity** - entailed sentences can only increase when information is added to KB; additional info cannot invalidate a preexiting inference\n",
              "* **Resolution** - returning a complete inference algorithm in comvination with any complete search algorithm\n",
              "* **Complementary literals** - positive and negative literal of the same atomic sentence\n",
              "* **Unit clause** - single literal is also the disjunction of one literal\n",
              "* **Conjunctive normal form** - CNF; conjunction of clauses; AND of ORs\n",
              "* **Resolution closure** - set of clases which is derivable by continued use of the resolution rule\n",
              "* **Ground resolution theorem** - if a set of clauses is unsatisfiable then its resolution closure is an empty clause\n",
              "* **Definite clause** -  disjunction of literals where exactly one is positive\n",
              "* **Horn clause** - disjunction of literals which at most one is positive\n",
              "* **Goal clauses** - there are no positive literals in the clause\n",
              "* **And-or graph** - edges joined by an arc represent a conjunction and edges without an arc are disjunction\n",
              "* **Data driven reasoning** - reasoning whose center of attention starts with what is known\n"
            ]
          },
          "metadata": {}
        }
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 3366
        },
        "id": "T3cm1WV542_a",
        "outputId": "a929c6c6-b72b-4fd8-bd35-a014674c9230"
      }
    }
  ]
}