{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521: Midterm #1 Notes Template.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6fbf9f61-eea9-4e9c-e462-6efc5fb3bdc9"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 53,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "a53196e8-6d5b-425e-afa8-315766865af4"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 54,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 55,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "The four models to consider for an AI are: human-thought, human-behavior, rational-thought, and rational-behavior. \n",
        "The best model is the rational-behavior model in which AI agents will act rationally and perform optimally towards a goal. \n",
        "Overall, the goal of AIs is to build agents that are beneficial to human society and to aid humans in achieving their goals.\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        " \n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "The agents interact with the environment by using their sensors to take in information and using their actuators to perform tasks within the environment. \n",
        "The performance of an agent can be defined mathematically by mapping sensory information to a corresponding set of actions.\n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "To be a rational agent, the agent itself must perform well within the environment to produce an optimal solution. \n",
        "Humans can measure how well an agent performs within an environment by using evaluation functions that analyze the sequence of actions the agent took within the environment. \n",
        "To perform rationally, at a given state the agent must select the most optimal choice based on its previous sensory information. \n",
        "The agent must keep doing this to reach the optimal solution.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "The task environment is made up of four elements: Performance measure, Environment, Actuators and Sensors (PEAS). \n",
        "Some properties of the task environment include the observability of the environment, the amount of agents within the environment, the types of agents within the environment, the types of states within the environment, \n",
        "the impact/continuity of a decision within the environment, and the environmental state while the agent thinks. The hardest task environments are the ones with the least amount of information and the environmental state changes frequently.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" \n",
        "An agent is composed of a program that runs on a physical architecture. The program interacts with architecture in order for the agent to perform actions from the sensory information. \n",
        "The simple reflex agent program makes decisions based solely on the current sensory information. \n",
        "The model-based reflex agent programs account for how the world changes even if the agent does not have all the information available. \n",
        "The goal-based agent program is similar to the previous model, but makes decisions based on the ability to get to the goal. \n",
        "The utility-based agent program makes decisions based on the best expected utility it can get from applying an action. \n",
        "The learning agent program takes in information, tries to learn it, evaluates it, and then from those evaluations, updates existing learning and tries again.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"rationality\" : \"the ability to choose the most optimal choice\",\n",
        "\"NLP\" : \"the ability to understand and process human language as a machine\",\n",
        "\"agent\" : \"An entity that interacts with their environment through their given sensors inputs\",\n",
        "\"rational agent\": \"an agent that acts with rationality; tries to get the most optimal outcome\",\n",
        "\"standard model\": \"the idea that the goal of AIs is to do the right thing\",\n",
        "\"limited rationality\": \"making choices based on limited computational power\",\n",
        "\"provably beneficial\": \"AIs should be made to benefit humans and society\",\n",
        "\"agent\" : \"an object that interacts with the environment\",\n",
        "\"environment\": \"the space in which an agent operates within\",\n",
        "\"sensors\": \"tools used to receieve sensory information\",\n",
        "\"actuators\": \"tools used to interact and apply actions within the environment\",\n",
        "\"percept\": \"sensory information that the agent is attending to\",\n",
        "\"percept sequence\": \"perception history\",\n",
        "\"agent function\": \"mapping between perception history and action\",\n",
        "\"agent program\": \"implementation of the agent function ran on the agent archiecture\",\n",
        "\"consequentialism\": \"the idea that the morality of an agent is judged by the consequences the agent causes\",\n",
        "\"performance measure\": \"the measure of how well an agent performs within a given environment\",\n",
        "\"autonomy\": \"the ability to think for ones self\",\n",
        "\"task environment\": \"the problem space in which rational agents work in\",\n",
        "\"PEAS\": \"factors that make up a task environment; Performance measure, Environment, Actuators, Sensors\",\n",
        "\"unobservable\": \"having no information about the state of the environment\",\n",
        "\"competitve\": \"agent against another agent\",\n",
        "\"cooperative\": \"agents working together with other agents\",\n",
        "\"deterministic\": \"next state = current state + action\",\n",
        "\"nondeterministic\": \"there is no fixed function to determine the next state and the next state could be ever changing\",\n",
        "\"stochastic\": \"an environment similar to nondeterminism that deals with chance probabilities\",\n",
        "\"enviromental class\": \"a big group of environments that experiments are tested on\",\n",
        "\"agent architecture\": \"physical sensors and actuators that are controlled by an agent's computing device\",\n",
        "\"simple reflext agent\": \"the current sensory information solely determines the agent's next action\",\n",
        "\"condition-action rule\": \"basically an if-then statement where if a condition is reached, then do an action\",\n",
        "\"internal state\": \"a representation of the entire environment state even when parts of it is not observable\",\n",
        "\"transition model\": \"going from one state to the next via some action\",\n",
        "\"sensor model\": \"a representation of the world via the agent's sensory information\",\n",
        "\"model-based agent\": \"users of models such as the transition model and sensor model\",\n",
        "\"goal\": \"desireable endstate\",\n",
        "\"utility\": \"the usefulness of an action\",\n",
        "\"utility function\": \"a function that measures the usefulness of an action perform by an agent; performance measure\",\n",
        "\"expected utility\": \"the expected outcome for choosing an action\",\n",
        "\"model-free agent\": \"not using models, but still choosing the best outcome in the environment\",\n",
        "\"learning element\": \"items that make improvements to learning\",\n",
        "\"performance element\": \"items that help the actuators perform actions on the environment\",\n",
        "\"problem generator\": \"suggests new ideas that the agent should look at and could possibly learn from\",\n",
        "\"reward\": \"a token received for good performance\",\n",
        "\"penalty\": \"punishment received for bad performance\",\n",
        "\"atomic representation\": \"basically a black box representation that should be taken as whole\",\n",
        "\"factored representation\": \"each state is assigned to a set of variables made up of values\",\n",
        "\"structured representation\": \"a representation that includes that object and their relationships\",\n",
        "\"expressiveness\": \"the ability to capture a representation\",\n",
        "\"localist  representation\": \"a representation where concepts are mapped one-to-one\",\n",
        "\"distributed representation\": \"a representation where a concepts are mapped one-to-many\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 56,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "76db58da-93e2-4a42-97df-fc83bd531daa"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 57,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nThe four models to consider for an AI are: human-thought, human-behavior, rational-thought, and rational-behavior. \nThe best model is the rational-behavior model in which AI agents will act rationally and perform optimally towards a goal. \nOverall, the goal of AIs is to build agents that are beneficial to human society and to aid humans in achieving their goals.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n \n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n\n\n\n## AIMA 2.1 Agents and Environments\n \nThe agents interact with the environment by using their sensors to take in information and using their actuators to perform tasks within the environment. \nThe performance of an agent can be defined mathematically by mapping sensory information to a corresponding set of actions.\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nTo be a rational agent, the agent itself must perform well within the environment to produce an optimal solution. \nHumans can measure how well an agent performs within an environment by using evaluation functions that analyze the sequence of actions the agent took within the environment. \nTo perform rationally, at a given state the agent must select the most optimal choice based on its previous sensory information. \nThe agent must keep doing this to reach the optimal solution.\n\n\n## AIMA 2.3 The Nature of Environments\n\nThe task environment is made up of four elements: Performance measure, Environment, Actuators and Sensors (PEAS). \nSome properties of the task environment include the observability of the environment, the amount of agents within the environment, the types of agents within the environment, the types of states within the environment, \nthe impact/continuity of a decision within the environment, and the environmental state while the agent thinks. The hardest task environments are the ones with the least amount of information and the environmental state changes frequently.\n\n\n## AIMA 2.4 The Structure of Agents\n \nAn agent is composed of a program that runs on a physical architecture. The program interacts with architecture in order for the agent to perform actions from the sensory information. \nThe simple reflex agent program makes decisions based solely on the current sensory information. \nThe model-based reflex agent programs account for how the world changes even if the agent does not have all the information available. \nThe goal-based agent program is similar to the previous model, but makes decisions based on the ability to get to the goal. \nThe utility-based agent program makes decisions based on the best expected utility it can get from applying an action. \nThe learning agent program takes in information, tries to learn it, evaluates it, and then from those evaluations, updates existing learning and tries again.\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Rationality** - the ability to choose the most optimal choice\n* **Nlp** - the ability to understand and process human language as a machine\n* **Agent** - an object that interacts with the environment\n* **Rational agent** - an agent that acts with rationality; tries to get the most optimal outcome\n* **Standard model** - the idea that the goal of AIs is to do the right thing\n* **Limited rationality** - making choices based on limited computational power\n* **Provably beneficial** - AIs should be made to benefit humans and society\n* **Environment** - the space in which an agent operates within\n* **Sensors** - tools used to receieve sensory information\n* **Actuators** - tools used to interact and apply actions within the environment\n* **Percept** - sensory information that the agent is attending to\n* **Percept sequence** - perception history\n* **Agent function** - mapping between perception history and action\n* **Agent program** - implementation of the agent function ran on the agent archiecture\n* **Consequentialism** - the idea that the morality of an agent is judged by the consequences the agent causes\n* **Performance measure** - the measure of how well an agent performs within a given environment\n* **Autonomy** - the ability to think for ones self\n* **Task environment** - the problem space in which rational agents work in\n* **Peas** - factors that make up a task environment; Performance measure, Environment, Actuators, Sensors\n* **Unobservable** - having no information about the state of the environment\n* **Competitve** - agent against another agent\n* **Cooperative** - agents working together with other agents\n* **Deterministic** - next state = current state + action\n* **Nondeterministic** - there is no fixed function to determine the next state and the next state could be ever changing\n* **Stochastic** - an environment similar to nondeterminism that deals with chance probabilities\n* **Enviromental class** - a big group of environments that experiments are tested on\n* **Agent architecture** - physical sensors and actuators that are controlled by an agent's computing device\n* **Simple reflext agent** - the current sensory information solely determines the agent's next action\n* **Condition-action rule** - basically an if-then statement where if a condition is reached, then do an action\n* **Internal state** - a representation of the entire environment state even when parts of it is not observable\n* **Transition model** - going from one state to the next via some action\n* **Sensor model** - a representation of the world via the agent's sensory information\n* **Model-based agent** - users of models such as the transition model and sensor model\n* **Goal** - desireable endstate\n* **Utility** - the usefulness of an action\n* **Utility function** - a function that measures the usefulness of an action perform by an agent; performance measure\n* **Expected utility** - the expected outcome for choosing an action\n* **Model-free agent** - not using models, but still choosing the best outcome in the environment\n* **Learning element** - items that make improvements to learning\n* **Performance element** - items that help the actuators perform actions on the environment\n* **Problem generator** - suggests new ideas that the agent should look at and could possibly learn from\n* **Reward** - a token received for good performance\n* **Penalty** - punishment received for bad performance\n* **Atomic representation** - basically a black box representation that should be taken as whole\n* **Factored representation** - each state is assigned to a set of variables made up of values\n* **Structured representation** - a representation that includes that object and their relationships\n* **Expressiveness** - the ability to capture a representation\n* **Localist  representation** - a representation where concepts are mapped one-to-one\n* **Distributed representation** - a representation where a concepts are mapped one-to-many\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 58,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 210
        },
        "outputId": "4a056dc9-14fb-42ba-88e6-4fa89ae561dc"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 59,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "Agents can solve problems by using four steps: define the goal of the problem, define the problem \n",
        "limitations, search for a solution, deploy the solution in the environment. \n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "A search problem can be defined as a problem with a start state, goal state, in-between states, \n",
        "a set of actions that can be deployed at each state, the cost of deploying an action at any given state, \n",
        "and a set of transitions for each action at any given state.\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "Search problems are generally structured as graph problems. The queue is the most optimized data structure for a search problem, with three variants of priority queue, first-in-first-out queue, and last-in-first-out queue(stack). \n",
        "There are four different performance measures for a search algorithm: completeness, cost optimality, time complexity, and space complexity. \n",
        "The best algorithms will be complete, optimal, low time complexity, and low space complexity.\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "BFS uses a FIFO queue, in which it looks at the children nodes one by one and adds them to the queue level by level. BFS has a time and space complexity of O(b^d). BFS is complete, but not optimal (only optimal when unit cost).\n",
        "\n",
        "Uniform-Cost Search (UCS) expands to the smallest node values first. Space and time complexity are O(b^(1+[C/e])), and can be much worse than BFS, but it is complete and cost-optimal.\n",
        "\n",
        "DFS uses a LIFO queue/stack and looks for the deepest node first and then backtracks upward. DFS is optimal, requires only O(b^m)/O(bm) time/space and can be reduced to O(m) with backtracking. It is not complete and can get lost if there are infinite paths.\n",
        "\n",
        "IDFS is basically DFS with a depth-limited subcall. So like DFS+BFS. IDFS has time complexity O(b^d) and space complexity O(bd) if there’s a solution, otherwise the same as DFS. \n",
        "\n",
        "Bidirectional search searches from the starting node and the goal node and ends when the two searches intersect. Both complete and optimal. Takes less time and space.\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",
        "\"planning agents\": \"agents that rely on factored or structured representation\",\n",
        "\"informed\": \"the ability to have additional information about where the goal is\",\n",
        "\"uninformed\": \"no additional information about where the goal is\",\n",
        "\"solution\": \"a collection of actions and states that starts from the initial state and goes to the goal state\",\n",
        "\"open-loop\": \"a linear one stream system\",\n",
        "\"close-loop\": \"contains a self loop to fix and update information\",\n",
        "\"problem\": \"contains the state space, an action function, a cost function for the action, and a transition model\",\n",
        "\"optimal solution\": \"lowest cost solution that the algorithm can produce\",\n",
        "\"model\": \"an abstraction of a real world problem\",\n",
        "\"abstraction\": \"a high level representation of a problem\",\n",
        "\"standarized problems\": \"problem with fixed environments and definitions; reached for research testing purposes\",\n",
        "\"real-world problems\": \"problems that attempt to solve problems in the real-world\",\n",
        "\"grid world\": \"often represented as a 2-d matrix\",\n",
        "\"route-finding problem\": \"algorithms used to find a goal state\",\n",
        "\"TSP\": \"a type of touring problem in which every state needs to be visited at least once\",\n",
        "\"VLSI layout\": \"the cordination of minizing area/delays and maximizing performance in a chip\",\n",
        "\"cell layout\": \"finding the best way to organize all the smaller components into cell boxes\",\n",
        "\"channel routing\": \"finding the best way to connect wires to cells\",\n",
        "\"search algorithm\": \"with an input of the problem, the output will be either the solution or failure\",\n",
        "\"search tree\": \"the representation of looking at the search space\",\n",
        "\"node\": \"a representation of an existing state\",\n",
        "\"expand\": \"explore what the node is connected to\",\n",
        "\"successor node\": \"a child node that came from a parent node\",\n",
        "\"frontier\": \"unexpanded nodes that have been added\",\n",
        "\"reached\": \"when a node has been expanded\",\n",
        "\"best-first search\": \"an algorithm that always takes the lowest value node based on an f(n)\",\n",
        "\"queue\": \"a data structure that can be used in search problems\",\n",
        "\"priority queue\": \"pop off based on minimum cost\",\n",
        "\"FIFO queue\": \"first-in-first-out; like a person standing in line; used in BFS\",\n",
        "\"LIFO queue\": \"last-in-first-out; like a stack of dishes; used in DFS\",\n",
        "\"cylce\": \"visiting the same node more than once\",\n",
        "\"graph search\": \"search algorithm representation if redundant paths are searched\",\n",
        "\"tree search\": \"search algorithm representation if redundant paths are not searched\",\n",
        "\"systematic\": \"must to able to reach all the states that are connected to the initial state\",\n",
        "\"depth\": \"how many layers does the algorithm go\",\n",
        "\"branching factor\": \"how many children is connected to each parent node\",\n",
        "\"BFS\": \"expands level by level using a FIFO queue\",\n",
        "\"early goal test\": \"when the node gets added to frontier, it gets checked if it is the goal state\",\n",
        "\"late goal test\": \"tests if the node is the goal state only when it gets popped off the queue\",\n",
        "\"uniform-cost search\": \"explores the shortest path cost first; Dijkstra's algorithm\",\n",
        "\"DFS\": \"goes to explore the depths first and then propagate back upward\",\n",
        "\"backtracking search\": \"an space efficient implementation of DFS\",\n",
        "\"depth-limited search\": \"DFS, but with a limit\",\n",
        "\"iterative deepening search\": \"repeatedly recursively calls DFS until it reaches the limit\",\n",
        "\"bidirectional search\": \"search from both the initial state and goal state and look for when they meet\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 60,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "9ba86fb4-4edf-47c6-e99f-0b32bfc3544c"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 61,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nAgents can solve problems by using four steps: define the goal of the problem, define the problem \nlimitations, search for a solution, deploy the solution in the environment. \n\n\n## AIMA Chapter 3.2 Example Problems\n\nA search problem can be defined as a problem with a start state, goal state, in-between states, \na set of actions that can be deployed at each state, the cost of deploying an action at any given state, \nand a set of transitions for each action at any given state.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nSearch problems are generally structured as graph problems. The queue is the most optimized data structure for a search problem, with three variants of priority queue, first-in-first-out queue, and last-in-first-out queue(stack). \nThere are four different performance measures for a search algorithm: completeness, cost optimality, time complexity, and space complexity. \nThe best algorithms will be complete, optimal, low time complexity, and low space complexity.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBFS uses a FIFO queue, in which it looks at the children nodes one by one and adds them to the queue level by level. BFS has a time and space complexity of O(b^d). BFS is complete, but not optimal (only optimal when unit cost).\n\nUniform-Cost Search (UCS) expands to the smallest node values first. Space and time complexity are O(b^(1+[C/e])), and can be much worse than BFS, but it is complete and cost-optimal.\n\nDFS uses a LIFO queue/stack and looks for the deepest node first and then backtracks upward. DFS is optimal, requires only O(b^m)/O(bm) time/space and can be reduced to O(m) with backtracking. It is not complete and can get lost if there are infinite paths.\n\nIDFS is basically DFS with a depth-limited subcall. So like DFS+BFS. IDFS has time complexity O(b^d) and space complexity O(bd) if there’s a solution, otherwise the same as DFS. \n\nBidirectional search searches from the starting node and the goal node and ends when the two searches intersect. Both complete and optimal. Takes less time and space.\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* **Planning agents** - agents that rely on factored or structured representation\n* **Informed** - the ability to have additional information about where the goal is\n* **Uninformed** - no additional information about where the goal is\n* **Solution** - a collection of actions and states that starts from the initial state and goes to the goal state\n* **Open-loop** - a linear one stream system\n* **Close-loop** - contains a self loop to fix and update information\n* **Problem** - contains the state space, an action function, a cost function for the action, and a transition model\n* **Optimal solution** - lowest cost solution that the algorithm can produce\n* **Model** - an abstraction of a real world problem\n* **Abstraction** - a high level representation of a problem\n* **Standarized problems** - problem with fixed environments and definitions; reached for research testing purposes\n* **Real-world problems** - problems that attempt to solve problems in the real-world\n* **Grid world** - often represented as a 2-d matrix\n* **Route-finding problem** - algorithms used to find a goal state\n* **Tsp** - a type of touring problem in which every state needs to be visited at least once\n* **Vlsi layout** - the cordination of minizing area/delays and maximizing performance in a chip\n* **Cell layout** - finding the best way to organize all the smaller components into cell boxes\n* **Channel routing** - finding the best way to connect wires to cells\n* **Search algorithm** - with an input of the problem, the output will be either the solution or failure\n* **Search tree** - the representation of looking at the search space\n* **Node** - a representation of an existing state\n* **Expand** - explore what the node is connected to\n* **Successor node** - a child node that came from a parent node\n* **Frontier** - unexpanded nodes that have been added\n* **Reached** - when a node has been expanded\n* **Best-first search** - an algorithm that always takes the lowest value node based on an f(n)\n* **Queue** - a data structure that can be used in search problems\n* **Priority queue** - pop off based on minimum cost\n* **Fifo queue** - first-in-first-out; like a person standing in line; used in BFS\n* **Lifo queue** - last-in-first-out; like a stack of dishes; used in DFS\n* **Cylce** - visiting the same node more than once\n* **Graph search** - search algorithm representation if redundant paths are searched\n* **Tree search** - search algorithm representation if redundant paths are not searched\n* **Systematic** - must to able to reach all the states that are connected to the initial state\n* **Depth** - how many layers does the algorithm go\n* **Branching factor** - how many children is connected to each parent node\n* **Bfs** - expands level by level using a FIFO queue\n* **Early goal test** - when the node gets added to frontier, it gets checked if it is the goal state\n* **Late goal test** - tests if the node is the goal state only when it gets popped off the queue\n* **Uniform-cost search** - explores the shortest path cost first; Dijkstra's algorithm\n* **Dfs** - goes to explore the depths first and then propagate back upward\n* **Backtracking search** - an space efficient implementation of DFS\n* **Depth-limited search** - DFS, but with a limit\n* **Iterative deepening search** - repeatedly recursively calls DFS until it reaches the limit\n* **Bidirectional search** - search from both the initial state and goal state and look for when they meet\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "Informed search algorithms have heuristic functions that allow them to guess additional information about the distance to the goal.\n",
        "\n",
        "Greedy-best-first search expands nodes with the lowest h(n) value. GBFS is not complete and not optimal. The time and space complexity depends on the amount of vertices.\n",
        "\n",
        "A* search expands nodes with the lowest g(n) + h(n), where g(n) represents the cost to the current node and h(n) represents the cost to the goal node. A* is a complete algorithm, but only optimal with admissible heuristics. Search contours expands uniformly circular in UCS, but in A* it gravitates towards the goal.\n",
        "\n",
        "Weighted A* search could find the goal faster at the cost of searching more spaces.\n",
        "\n",
        "Beam search only keeps the k-best nodes in the frontier and this limits the overall size of the search space.\n",
        "\n",
        "IDA* search combines A* and IDFS, improving the space complexity and the cutoff used is the f(n) = g(n) + h(n)\n",
        "\n",
        "Recursive best-first search improves the space complexity of best-first search to linear space. Recursively propagates the best value of the child upward. RBFS is optimal if heuristic is admissible. Due to the small space complexity explored, it possible that redundant exploration happens for both RBFS and IDA*\n",
        "\n",
        "SMA* is optimal and complete if there is a reachable solution.\n",
        "\n",
        "Bidirectional heuristic search takes the maximum of the front search and the backwards search.\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "Manhattan distance is an admissible heuristic where you calculate how many moves you are away from your correct position\n",
        "\n",
        "Heuristic functions reduce the depth space by a factor making it smaller than uninformed search space\n",
        "\n",
        "A heuristic dominates another if for each n value, the h(n) value is greater than another heuristic. Since both heuristics are assumed to be admissible, that means that the dominant heuristic will be closer to the real answer.\n",
        "\n",
        "Creating admissible heuristics by creating a relaxed version of the current problem. If you can use the heuristic to solve the relaxed version, then the heuristic is admissible.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"hueristic function\": \"additional information that helps determine the distance to the goal\",\n",
        "\"greedy best-first search\": \"an algorithm that expands the smallest huerstic function of a node; f(n)=h(n)\",\n",
        "\"straight-line distance\": \"the distance between two locations determined by a straight line\",\n",
        "\"A* search\": \"an informed algorithm that uses the function of f(n) = g(n) + h(n) to determine priority\",\n",
        "\"admissible heuristic\": \"an optimistic heuristic that will enver overestimate the actual cost to the goal\",\n",
        "\"consistency\": \"the current hueristic value is less than the hueristic value of the successor + the cost\",\n",
        "\"triangle inequality\": \"the sum of two sides of a triangle will always be larger than one side\",\n",
        "\"contour\": \"how the node search space looks as the algorithm runs\",\n",
        "\"monotonic\": \"will always increase\",\n",
        "\"prunes\": \"doesn't explore all the states\",\n",
        "\"satisficing\": \"answers that aren't necessarily correct, but give a good representation of what the answer could be\",\n",
        "\"inadmissible heuristic\": \"an unoptimistic heuristics that overestimates the path\",\n",
        "\"bounded suboptimals search\": \"look for solutions that are within a specific range to the optimal solution\",\n",
        "\"bounded-cost search\": \"only look at solutions that are less than some constant cost\",\n",
        "\"unbounded-cost search\": \"accept any solution if we can find it quickly\",\n",
        "\"speedy search\": \"a variation of greedy best-first search that uses a new hueristic to estimate actions to the goal\",\n",
        "\"reference count\": \"the amount of times a state has been reached\",\n",
        "\"beam search\": \"an algorithm that limits the frontier size to only the best k-options with the highest f-scores\",\n",
        "\"IDA*\": \"an iterative version of A* that uses less memory and uses the g(n)+h(n) as a limit\",\n",
        "\"recursive best-first search (RBFS)\": \"RBFS is a recursive version of best-first search and it only uses linear space complexity\",\n",
        "\"MA*\": \"A* search with a memory bound\",\n",
        "\"SMA*\": \"A simplified version of MA*, add leaves until it reaches the memory bound and once reached, drop the worst leaves\",\n",
        "\"front-to-end\": \"hueristic function estimates the cost to the goal state\",\n",
        "\"front-to-front\": \"hueristic function estimates the distance from the oppposing frontier\",\n",
        "\"effective branching factor b*\": \"the amount of successors connected to an A* node\",\n",
        "\"dominatse\": \"when one hueristic h(n) >= h(n) because this means that the first heuristic is more acccurate\",\n",
        "\"relaxed problems\": \"simplified version of the given problem\",\n",
        "\"pattern database\": \"a structure that stores all the cost for all the subproblems\"   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 62,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "7634e038-a048-4c4f-dce2-2c762314b609"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 63,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nInformed search algorithms have heuristic functions that allow them to guess additional information about the distance to the goal.\n\nGreedy-best-first search expands nodes with the lowest h(n) value. GBFS is not complete and not optimal. The time and space complexity depends on the amount of vertices.\n\nA* search expands nodes with the lowest g(n) + h(n), where g(n) represents the cost to the current node and h(n) represents the cost to the goal node. A* is a complete algorithm, but only optimal with admissible heuristics. Search contours expands uniformly circular in UCS, but in A* it gravitates towards the goal.\n\nWeighted A* search could find the goal faster at the cost of searching more spaces.\n\nBeam search only keeps the k-best nodes in the frontier and this limits the overall size of the search space.\n\nIDA* search combines A* and IDFS, improving the space complexity and the cutoff used is the f(n) = g(n) + h(n)\n\nRecursive best-first search improves the space complexity of best-first search to linear space. Recursively propagates the best value of the child upward. RBFS is optimal if heuristic is admissible. Due to the small space complexity explored, it possible that redundant exploration happens for both RBFS and IDA*\n\nSMA* is optimal and complete if there is a reachable solution.\n\nBidirectional heuristic search takes the maximum of the front search and the backwards search.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nManhattan distance is an admissible heuristic where you calculate how many moves you are away from your correct position\n\nHeuristic functions reduce the depth space by a factor making it smaller than uninformed search space\n\nA heuristic dominates another if for each n value, the h(n) value is greater than another heuristic. Since both heuristics are assumed to be admissible, that means that the dominant heuristic will be closer to the real answer.\n\nCreating admissible heuristics by creating a relaxed version of the current problem. If you can use the heuristic to solve the relaxed version, then the heuristic is admissible.\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Hueristic function** - additional information that helps determine the distance to the goal\n* **Greedy best-first search** - an algorithm that expands the smallest huerstic function of a node; f(n)=h(n)\n* **Straight-line distance** - the distance between two locations determined by a straight line\n* **A* search** - an informed algorithm that uses the function of f(n) = g(n) + h(n) to determine priority\n* **Admissible heuristic** - an optimistic heuristic that will enver overestimate the actual cost to the goal\n* **Consistency** - the current hueristic value is less than the hueristic value of the successor + the cost\n* **Triangle inequality** - the sum of two sides of a triangle will always be larger than one side\n* **Contour** - how the node search space looks as the algorithm runs\n* **Monotonic** - will always increase\n* **Prunes** - doesn't explore all the states\n* **Satisficing** - answers that aren't necessarily correct, but give a good representation of what the answer could be\n* **Inadmissible heuristic** - an unoptimistic heuristics that overestimates the path\n* **Bounded suboptimals search** - look for solutions that are within a specific range to the optimal solution\n* **Bounded-cost search** - only look at solutions that are less than some constant cost\n* **Unbounded-cost search** - accept any solution if we can find it quickly\n* **Speedy search** - a variation of greedy best-first search that uses a new hueristic to estimate actions to the goal\n* **Reference count** - the amount of times a state has been reached\n* **Beam search** - an algorithm that limits the frontier size to only the best k-options with the highest f-scores\n* **Ida*** - an iterative version of A* that uses less memory and uses the g(n)+h(n) as a limit\n* **Recursive best-first search (rbfs)** - RBFS is a recursive version of best-first search and it only uses linear space complexity\n* **Ma*** - A* search with a memory bound\n* **Sma*** - A simplified version of MA*, add leaves until it reaches the memory bound and once reached, drop the worst leaves\n* **Front-to-end** - hueristic function estimates the cost to the goal state\n* **Front-to-front** - hueristic function estimates the distance from the oppposing frontier\n* **Effective branching factor b*** - the amount of successors connected to an A* node\n* **Dominatse** - when one hueristic h(n) >= h(n) because this means that the first heuristic is more acccurate\n* **Relaxed problems** - simplified version of the given problem\n* **Pattern database** - a structure that stores all the cost for all the subproblems\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "Zero-sum games are games where one person's gain is another person's lost and AIs can solve these type of games.\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "Games can be defined as a MAX player and a MIN player; we play from the perspective of MAX. MAX wants to maximize the value and MIN wants to minimize MAX's value.\n",
        "\n",
        "The minimax algorithm choose the best move based on the assumption that the other player will choose their own best move at every turn. It uses a recursive algorithm that propagates the best values upward.\n",
        "\n",
        "Alpha-beta pruning is a more optimized version of the minimax algorithm. Alpha is the atleast value for MAX (the highest value it can get from this path). Beta is the at most value for MIN (the lowest value that it will allow MAX to get if it choose this path)\n",
        "\n",
        "The time complexity of minimax is O(b^m) and space complexity is O(bm). Alpha-Beta Pruning reduces the time to O(b^(m/2))\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "Cutoff test tells the alpha-beta pruning when to stop recursively looking down the tree\n",
        "\n",
        "If the cutoff is reached, then evalutate the game state and then return it.\n",
        "\n",
        "The horizon effect is basically delaying the evitable by using stalling tactics. In an effort to reduce the horizon effect, always choose the best move in every position (singular extension)\n",
        "\n",
        "In an effect to reduce size, deploy forward pruning which prunes bad moves and increases inaccuracy\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Alpha-beta pruning on stochasic games use chance instead of actual values. Therefore, it must use the expected values.\n",
        "\n",
        "New algorithm, expectiminimax.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"imperfect information\" : \"not having all the information within an environment\",\n",
        "\"perfect information\": \"environments that are deterministic and static\",\n",
        "\"zero-sum game\": \"one person's gains is another person's lost\",\n",
        "\"terminal state\": \"the state in which the game terminates\",\n",
        "\"utility function\": \"a function that determines the expected utility of a given action\",\n",
        "\"game tree\": \"a representation of all the states within a game as a tree like structure\",\n",
        "\"minimax search\": \"an recursive algorithm that maximizes utility based on the assumption the opponent will play perfectly\",\n",
        "\"ply\": \"a level within the game tree which belongs to one player\",\n",
        "\"minimax value\": \"the best value that the MAX player can get within the game tree\",\n",
        "\"minimax decision\": \"the best choice that the MAX player can choose to get the minimax value\",\n",
        "\"back up\": \"recursively propagates the value from the leaves to the root node in the game tree\",\n",
        "\"alliance\": \"teaming up\",\n",
        "\"alpha-beta pruning\": \"alpha = MAX's best option (at least) and beta = MIN's best option (at most)\",\n",
        "\"killer moves\": \"the best moves within the game\",\n",
        "\"transposition\": \"getting to the same game state via different set of moves\",\n",
        "\"Type A Strategy\": \"limit the depth of the tree, but consider all possible moves\",\n",
        "\"Type B Strategy\": \"following the good moves to the maximum depth\",\n",
        "\"cutoff test\": \"a test used to determine when the alpha-beta search algorithm should stop searching\",\n",
        "\"expected value\": \"the expected outcome based on value and probability\",\n",
        "\"material value\": \"the worth of each component within a game\",\n",
        "\"weighted linear function\": \"a function based on expected value of weighted values * game feature piece\",\n",
        "\"quiescent\": \"a stable state within the game, where there are no moves to be taken\",\n",
        "\"horizon effect\": \"delaying the inevitable by using stalling tactics\",\n",
        "\"singular extension\": \"always choosing the best move when possible if given the chance\", \n",
        "\"forward pruning\": \"prunes the bad moves even though this might lead to inaccurate answers, faster\",\n",
        "\"late move reduction\": \"reduce the search space for moves that appear later in the game\",\n",
        "\"policy\": \"deploying a strategy that will get the best move for each given state\",\n",
        "\"retrograde\": \"reverse the rules and commit to a backwards search\",\n",
        "\"Monte Carlo tree search\": \"multiple simulations of complete games are ran and the expected utility is the value\",\n",
        "\"playout policy\": \"a simulation policy that is biased towards the best moves\",\n",
        "\"selection policy\": \"focuses the computation on selected parts of the tree\",\n",
        "\"exploration\": \"discovering new states\",\n",
        "\"stochastic games\": \"games that involve chance\",\n",
        "\"chance nodes\": \"a node that gives out has outputs of varying probabilites\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 64,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "87a269bb-c5b0-4cd9-d74c-95a430da933d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 65,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nZero-sum games are games where one person's gain is another person's lost and AIs can solve these type of games.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nGames can be defined as a MAX player and a MIN player; we play from the perspective of MAX. MAX wants to maximize the value and MIN wants to minimize MAX's value.\n\nThe minimax algorithm choose the best move based on the assumption that the other player will choose their own best move at every turn. It uses a recursive algorithm that propagates the best values upward.\n\nAlpha-beta pruning is a more optimized version of the minimax algorithm. Alpha is the atleast value for MAX (the highest value it can get from this path). Beta is the at most value for MIN (the lowest value that it will allow MAX to get if it choose this path)\n\nThe time complexity of minimax is O(b^m) and space complexity is O(bm). Alpha-Beta Pruning reduces the time to O(b^(m/2))\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nCutoff test tells the alpha-beta pruning when to stop recursively looking down the tree\n\nIf the cutoff is reached, then evalutate the game state and then return it.\n\nThe horizon effect is basically delaying the evitable by using stalling tactics. In an effort to reduce the horizon effect, always choose the best move in every position (singular extension)\n\nIn an effect to reduce size, deploy forward pruning which prunes bad moves and increases inaccuracy\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nAlpha-beta pruning on stochasic games use chance instead of actual values. Therefore, it must use the expected values.\n\nNew algorithm, expectiminimax.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Imperfect information** - not having all the information within an environment\n* **Perfect information** - environments that are deterministic and static\n* **Zero-sum game** - one person's gains is another person's lost\n* **Terminal state** - the state in which the game terminates\n* **Utility function** - a function that determines the expected utility of a given action\n* **Game tree** - a representation of all the states within a game as a tree like structure\n* **Minimax search** - an recursive algorithm that maximizes utility based on the assumption the opponent will play perfectly\n* **Ply** - a level within the game tree which belongs to one player\n* **Minimax value** - the best value that the MAX player can get within the game tree\n* **Minimax decision** - the best choice that the MAX player can choose to get the minimax value\n* **Back up** - recursively propagates the value from the leaves to the root node in the game tree\n* **Alliance** - teaming up\n* **Alpha-beta pruning** - alpha = MAX's best option (at least) and beta = MIN's best option (at most)\n* **Killer moves** - the best moves within the game\n* **Transposition** - getting to the same game state via different set of moves\n* **Type a strategy** - limit the depth of the tree, but consider all possible moves\n* **Type b strategy** - following the good moves to the maximum depth\n* **Cutoff test** - a test used to determine when the alpha-beta search algorithm should stop searching\n* **Expected value** - the expected outcome based on value and probability\n* **Material value** - the worth of each component within a game\n* **Weighted linear function** - a function based on expected value of weighted values * game feature piece\n* **Quiescent** - a stable state within the game, where there are no moves to be taken\n* **Horizon effect** - delaying the inevitable by using stalling tactics\n* **Singular extension** - always choosing the best move when possible if given the chance\n* **Forward pruning** - prunes the bad moves even though this might lead to inaccurate answers, faster\n* **Late move reduction** - reduce the search space for moves that appear later in the game\n* **Policy** - deploying a strategy that will get the best move for each given state\n* **Retrograde** - reverse the rules and commit to a backwards search\n* **Monte carlo tree search** - multiple simulations of complete games are ran and the expected utility is the value\n* **Playout policy** - a simulation policy that is biased towards the best moves\n* **Selection policy** - focuses the computation on selected parts of the tree\n* **Exploration** - discovering new states\n* **Stochastic games** - games that involve chance\n* **Chance nodes** - a node that gives out has outputs of varying probabilites\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "CSPs are made up of a set of variables, a set of domains, and a set of constrains. \n",
        "The constraints are made up a pair containing (value of compared nodes, the possible values the nodes can take).\n",
        "\n",
        "A solution is a complete and consistent assignment to a CSP. \n",
        "When every variable is assigned in the problem, then the assignment is considered complete. \n",
        "When the assignment does not violate any constraints for each variable, then that is a consistent assignment for each variable.\n",
        "\n",
        "CSPs are generally considered NP-complete problems.\n",
        "\n",
        "CSPs can be visualzied as graph problems with constraints.\n",
        "\n",
        "Reasons to form a CSP: easy and natural representation of many problems; solver algorithms work well; can reduce the search space\n",
        "\n",
        "CSPs can be used to solve color map assigning and job scheduling\n",
        "\n",
        "An example of CSPs with continous domains is experiments using the Hubble telescope. Linear programming is a well known group of these sort of problems.\n",
        "\n",
        "Unary and Binary are two types of constraints.\n",
        "\n",
        "One type of global constraint is the AllDiff constraint used in Sudoku.\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "CSP algorithms use the core idea of constraint propagation in which constraints can reduce the amount of possible domain values for varaibles around it.\n",
        "\n",
        "If there is local consistency, then all inconsistent values can be removed as we move through the graph.\n",
        "\n",
        "Node consistency is when all variables respect the unary constraint.\n",
        "\n",
        "Arc consistency is when all variables respect the binary constraint.\n",
        "\n",
        "AC3 is an algorithm that enforces arc consistency across a graph. If the algorithm changes a value in the tail, then it has to check the neighbors. Otherwise, if nothing is changed, then it moves onto the next arc pair.\n",
        "\n",
        "AC3 will return failure if it cannot find a solution that is arc consistent. The time complexit is O(cd^3), where c is the amount of binary constraitns and d is the largest domain size.\n",
        "\n",
        "Path consistency is more strict than arc consistency and looks at triplet constraints. \n",
        "We say there is path consistency if for every assignment (Node1, Node2) that is consistent, there is an assignment (Node1, Node3) and (Node3, Node2).\n",
        "If so, then path consistency exists.\n",
        "\n",
        "k-consistency says taht each varaible can have a consistent value; 1-consistent = node-consistency, 2-consistent = arc consistency, 3-consistent = path consistency\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "forward checking is a type of simple inference, but it only checks on one node.\n",
        "\n",
        "MAC <-> AC3 with guessing and backtracking\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP\" : \"factored representation which means that each state has set of variables and each variable has its own value\",\n",
        "\"scope\": \"a tuple of nodes that are being compared\",\n",
        "\"relation\": \"possible values that can be assigned to the scope nodes\",\n",
        "\"assignment\": \"giving nodes a value\",\n",
        "\"consistent\": \"no constraints are broken\",\n",
        "\"complete assignment\": \"each node has a value\",\n",
        "\"solution\": \"when all the assignments are complete and consistent\",\n",
        "\"constraint graph\": \"graph representation of CSP\",\n",
        "\"disjunctive constraint\": \"overlaps are not allowed; they must occur sequentially\",\n",
        "\"precedence constraint\": \"add additional constraint to a task before another task to be started\",\n",
        "\"discrete finite domains\": \"fixed number of domain values\",\n",
        "\"linear constraint\": \"everything must be a linear value\",\n",
        "\"continuous domain\": \"an infinite set of domain values\",\n",
        "\"linear programming\": \"problems that can be solved in linear time\",\n",
        "\"unary constraint\": \"a restriction on the value of a variable\",\n",
        "\"binary constraint\": \"a restriction on which two variables cannot be related to each other\",\n",
        "\"global constraints\": \"constraints that involve more than 3 number of variables\",\n",
        "\"cryptarithmetic\": \"a puzzle in which letters represent numeric values\",\n",
        "\"constraint hypergraph\": \"a graph representation that consist of both regular nodes and hypernodes\",\n",
        "\"dual graph\": \"a way to transform a n-nary CSP to a binary CSP\",\n",
        "\"preference constraints\": \"some solutions are more preferable than others in real world CSPs\",\n",
        "\"constrained optimzation problem\": \"CSPs with preference constraints creates these types of problem\",\n",
        "\"constraint propagation\": \"constraints can reduce other variable possible values\",\n",
        "\"node consistency\": \"each variable follows the unary constraint\",\n",
        "\"arc consistency\": \"each variable follows the binary constraint\",\n",
        "\"path consistency\": \"each variable follows a triplet constraint\",\n",
        "\"k-consistency\": \"basically, a consistent value can be assigned to each and every variable\",\n",
        "\"strongly k-consistent\": \"if the CSP is k to 1 consistent\",\n",
        "\"forward checking\": \"a very simple form of inference\"\n",
        "}\n"
      ],
      "execution_count": 66,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ac241971-8dd4-4428-ce12-93cfafea036d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 67,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nCSPs are made up of a set of variables, a set of domains, and a set of constrains. \nThe constraints are made up a pair containing (value of compared nodes, the possible values the nodes can take).\n\nA solution is a complete and consistent assignment to a CSP. \nWhen every variable is assigned in the problem, then the assignment is considered complete. \nWhen the assignment does not violate any constraints for each variable, then that is a consistent assignment for each variable.\n\nCSPs are generally considered NP-complete problems.\n\nCSPs can be visualzied as graph problems with constraints.\n\nReasons to form a CSP: easy and natural representation of many problems; solver algorithms work well; can reduce the search space\n\nCSPs can be used to solve color map assigning and job scheduling\n\nAn example of CSPs with continous domains is experiments using the Hubble telescope. Linear programming is a well known group of these sort of problems.\n\nUnary and Binary are two types of constraints.\n\nOne type of global constraint is the AllDiff constraint used in Sudoku.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nCSP algorithms use the core idea of constraint propagation in which constraints can reduce the amount of possible domain values for varaibles around it.\n\nIf there is local consistency, then all inconsistent values can be removed as we move through the graph.\n\nNode consistency is when all variables respect the unary constraint.\n\nArc consistency is when all variables respect the binary constraint.\n\nAC3 is an algorithm that enforces arc consistency across a graph. If the algorithm changes a value in the tail, then it has to check the neighbors. Otherwise, if nothing is changed, then it moves onto the next arc pair.\n\nAC3 will return failure if it cannot find a solution that is arc consistent. The time complexit is O(cd^3), where c is the amount of binary constraitns and d is the largest domain size.\n\nPath consistency is more strict than arc consistency and looks at triplet constraints. \nWe say there is path consistency if for every assignment (Node1, Node2) that is consistent, there is an assignment (Node1, Node3) and (Node3, Node2).\nIf so, then path consistency exists.\n\nk-consistency says taht each varaible can have a consistent value; 1-consistent = node-consistency, 2-consistent = arc consistency, 3-consistent = path consistency\n\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nforward checking is a type of simple inference, but it only checks on one node.\n\nMAC <-> AC3 with guessing and backtracking\n\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Csp** - factored representation which means that each state has set of variables and each variable has its own value\n* **Scope** - a tuple of nodes that are being compared\n* **Relation** - possible values that can be assigned to the scope nodes\n* **Assignment** - giving nodes a value\n* **Consistent** - no constraints are broken\n* **Complete assignment** - each node has a value\n* **Solution** - when all the assignments are complete and consistent\n* **Constraint graph** - graph representation of CSP\n* **Disjunctive constraint** - overlaps are not allowed; they must occur sequentially\n* **Precedence constraint** - add additional constraint to a task before another task to be started\n* **Discrete finite domains** - fixed number of domain values\n* **Linear constraint** - everything must be a linear value\n* **Continuous domain** - an infinite set of domain values\n* **Linear programming** - problems that can be solved in linear time\n* **Unary constraint** - a restriction on the value of a variable\n* **Binary constraint** - a restriction on which two variables cannot be related to each other\n* **Global constraints** - constraints that involve more than 3 number of variables\n* **Cryptarithmetic** - a puzzle in which letters represent numeric values\n* **Constraint hypergraph** - a graph representation that consist of both regular nodes and hypernodes\n* **Dual graph** - a way to transform a n-nary CSP to a binary CSP\n* **Preference constraints** - some solutions are more preferable than others in real world CSPs\n* **Constrained optimzation problem** - CSPs with preference constraints creates these types of problem\n* **Constraint propagation** - constraints can reduce other variable possible values\n* **Node consistency** - each variable follows the unary constraint\n* **Arc consistency** - each variable follows the binary constraint\n* **Path consistency** - each variable follows a triplet constraint\n* **K-consistency** - basically, a consistent value can be assigned to each and every variable\n* **Strongly k-consistent** - if the CSP is k to 1 consistent\n* **Forward checking** - a very simple form of inference\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "There are two main types of approaches; declarative and prodecural. Declarative is an iterative approach, whereas procedural is a preprogramed appraoch.\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "Wumpus World example, the agent uses knowledge from previous experiences to make moves\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "conjunctions = ANDs\n",
        "\n",
        "disjunctions = ORs\n",
        "\n",
        "implication = =>\n",
        "\n",
        "bicondition = if and only if <=>\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "SAT problem is NP-Complete; first of its kind\n",
        "\n",
        "Modus Ponens: (a => B, a) / B = B (given a, then B can be inferred)\n",
        "\n",
        "And-Elimination: (a & B) / a = a|B (either a and B can be inffered)\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge base\" : \"contains a set of setences that represents some assertion aboutthe world\",\n",
        "\"knowledge representation langauge\": \"the language for the knowledge base\",\n",
        "\"axiom\": \"a true statement/representation\",\n",
        "\"inference\": \"creating a new sentence based on information of the old one\",\n",
        "\"declaractive\": \"the desuigner can have the agent iterate over the sentences until the agents knows what to do\",\n",
        "\"procedural\": \"programs behavioral desires directly\",\n",
        "\"wumpus world\": \"an imagiary world made of caves connected by passageways\",\n",
        "\"syntax\": \"rules of a langauge\",\n",
        "\"semantics\": \"meanings of a language\",\n",
        "\"truth\": \"the correct value\",\n",
        "\"satisfies\": \"the act of being a proper model for a sentence\",\n",
        "\"entailment\": \"a sentence follows another sentence in the logical sense\",\n",
        "\"logical inference\": \"using previous information to make inferences on the current state\",\n",
        "\"model checking\": \"checks a sentence against all models\",\n",
        "\"truth-preserving\": \"inferences that are created from entailing sentences\",\n",
        "\"completeness\": \"the ability to create any sentence that the inference entails\",\n",
        "\"grounding\": \"connection between real world and logical world, is the knowledge base true in the real world?\",\n",
        "\"validity\": \"only true if it is true for all models\",\n",
        "\"tautologies\": \"always true\",\n",
        "\"satifiability\": \"the ability to be satisfied by some model\",\n",
        "\"reductio ad adsurdum/refutation/proof by contradiction\": \"start with the assumption that the answer is wrong and then end in a condradiction\",\n",
        "\"Modus Ponens\": \"a type of inference rule where the latter part can be infered and affirmed\",\n",
        "\"And-Elimination\": \"given an AND clause, either of the literals can be inferred\",\n",
        "\"resolution\": \"a complete inference algo with another complete inference algo\",\n",
        "\"resolvent\": \"the result of the resolutiojn\"\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 68,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 764
        },
        "outputId": "fdf76d50-0cc1-45e5-f8e7-36a22f5b93ed"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 69,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nThere are two main types of approaches; declarative and prodecural. Declarative is an iterative approach, whereas procedural is a preprogramed appraoch.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\nWumpus World example, the agent uses knowledge from previous experiences to make moves\n\n\n## AIMA Chapter 7.3 Logic\n \n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge base** - contains a set of setences that represents some assertion aboutthe world\n* **Knowledge representation langauge** - the language for the knowledge base\n* **Axiom** - a true statement/representation\n* **Inference** - creating a new sentence based on information of the old one\n* **Declaractive** - the desuigner can have the agent iterate over the sentences until the agents knows what to do\n* **Procedural** - programs behavioral desires directly\n* **Wumpus world** - an imagiary world made of caves connected by passageways\n* **Syntax** - rules of a langauge\n* **Semantics** - meanings of a language\n* **Truth** - the correct value\n* **Satisfies** - the act of being a proper model for a sentence\n* **Entailment** - a sentence follows another sentence in the logical sense\n* **Logical inference** - using previous information to make inferences on the current state\n* **Model checking** - checks a sentence against all models\n* **Truth-preserving** - inferences that are created from entailing sentences\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "0226ba78-264c-4bf8-e5b2-1ac204267b3a"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 71,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nThe four models to consider for an AI are: human-thought, human-behavior, rational-thought, and rational-behavior. \nThe best model is the rational-behavior model in which AI agents will act rationally and perform optimally towards a goal. \nOverall, the goal of AIs is to build agents that are beneficial to human society and to aid humans in achieving their goals.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n \n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n\n\n\n## AIMA 2.1 Agents and Environments\n \nThe agents interact with the environment by using their sensors to take in information and using their actuators to perform tasks within the environment. \nThe performance of an agent can be defined mathematically by mapping sensory information to a corresponding set of actions.\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nTo be a rational agent, the agent itself must perform well within the environment to produce an optimal solution. \nHumans can measure how well an agent performs within an environment by using evaluation functions that analyze the sequence of actions the agent took within the environment. \nTo perform rationally, at a given state the agent must select the most optimal choice based on its previous sensory information. \nThe agent must keep doing this to reach the optimal solution.\n\n\n## AIMA 2.3 The Nature of Environments\n\nThe task environment is made up of four elements: Performance measure, Environment, Actuators and Sensors (PEAS). \nSome properties of the task environment include the observability of the environment, the amount of agents within the environment, the types of agents within the environment, the types of states within the environment, \nthe impact/continuity of a decision within the environment, and the environmental state while the agent thinks. The hardest task environments are the ones with the least amount of information and the environmental state changes frequently.\n\n\n## AIMA 2.4 The Structure of Agents\n \nAn agent is composed of a program that runs on a physical architecture. The program interacts with architecture in order for the agent to perform actions from the sensory information. \nThe simple reflex agent program makes decisions based solely on the current sensory information. \nThe model-based reflex agent programs account for how the world changes even if the agent does not have all the information available. \nThe goal-based agent program is similar to the previous model, but makes decisions based on the ability to get to the goal. \nThe utility-based agent program makes decisions based on the best expected utility it can get from applying an action. \nThe learning agent program takes in information, tries to learn it, evaluates it, and then from those evaluations, updates existing learning and tries again.\n\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Rationality** - the ability to choose the most optimal choice\n* **Nlp** - the ability to understand and process human language as a machine\n* **Agent** - an object that interacts with the environment\n* **Rational agent** - an agent that acts with rationality; tries to get the most optimal outcome\n* **Standard model** - the idea that the goal of AIs is to do the right thing\n* **Limited rationality** - making choices based on limited computational power\n* **Provably beneficial** - AIs should be made to benefit humans and society\n* **Environment** - the space in which an agent operates within\n* **Sensors** - tools used to receieve sensory information\n* **Actuators** - tools used to interact and apply actions within the environment\n* **Percept** - sensory information that the agent is attending to\n* **Percept sequence** - perception history\n* **Agent function** - mapping between perception history and action\n* **Agent program** - implementation of the agent function ran on the agent archiecture\n* **Consequentialism** - the idea that the morality of an agent is judged by the consequences the agent causes\n* **Performance measure** - the measure of how well an agent performs within a given environment\n* **Autonomy** - the ability to think for ones self\n* **Task environment** - the problem space in which rational agents work in\n* **Peas** - factors that make up a task environment; Performance measure, Environment, Actuators, Sensors\n* **Unobservable** - having no information about the state of the environment\n* **Competitve** - agent against another agent\n* **Cooperative** - agents working together with other agents\n* **Deterministic** - next state = current state + action\n* **Nondeterministic** - there is no fixed function to determine the next state and the next state could be ever changing\n* **Stochastic** - an environment similar to nondeterminism that deals with chance probabilities\n* **Enviromental class** - a big group of environments that experiments are tested on\n* **Agent architecture** - physical sensors and actuators that are controlled by an agent's computing device\n* **Simple reflext agent** - the current sensory information solely determines the agent's next action\n* **Condition-action rule** - basically an if-then statement where if a condition is reached, then do an action\n* **Internal state** - a representation of the entire environment state even when parts of it is not observable\n* **Transition model** - going from one state to the next via some action\n* **Sensor model** - a representation of the world via the agent's sensory information\n* **Model-based agent** - users of models such as the transition model and sensor model\n* **Goal** - desireable endstate\n* **Utility** - the usefulness of an action\n* **Utility function** - a function that measures the usefulness of an action perform by an agent; performance measure\n* **Expected utility** - the expected outcome for choosing an action\n* **Model-free agent** - not using models, but still choosing the best outcome in the environment\n* **Learning element** - items that make improvements to learning\n* **Performance element** - items that help the actuators perform actions on the environment\n* **Problem generator** - suggests new ideas that the agent should look at and could possibly learn from\n* **Reward** - a token received for good performance\n* **Penalty** - punishment received for bad performance\n* **Atomic representation** - basically a black box representation that should be taken as whole\n* **Factored representation** - each state is assigned to a set of variables made up of values\n* **Structured representation** - a representation that includes that object and their relationships\n* **Expressiveness** - the ability to capture a representation\n* **Localist  representation** - a representation where concepts are mapped one-to-one\n* **Distributed representation** - a representation where a concepts are mapped one-to-many\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nAgents can solve problems by using four steps: define the goal of the problem, define the problem \nlimitations, search for a solution, deploy the solution in the environment. \n\n\n## AIMA Chapter 3.2 Example Problems\n\nA search problem can be defined as a problem with a start state, goal state, in-between states, \na set of actions that can be deployed at each state, the cost of deploying an action at any given state, \nand a set of transitions for each action at any given state.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nSearch problems are generally structured as graph problems. The queue is the most optimized data structure for a search problem, with three variants of priority queue, first-in-first-out queue, and last-in-first-out queue(stack). \nThere are four different performance measures for a search algorithm: completeness, cost optimality, time complexity, and space complexity. \nThe best algorithms will be complete, optimal, low time complexity, and low space complexity.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBFS uses a FIFO queue, in which it looks at the children nodes one by one and adds them to the queue level by level. BFS has a time and space complexity of O(b^d). BFS is complete, but not optimal (only optimal when unit cost).\n\nUniform-Cost Search (UCS) expands to the smallest node values first. Space and time complexity are O(b^(1+[C/e])), and can be much worse than BFS, but it is complete and cost-optimal.\n\nDFS uses a LIFO queue/stack and looks for the deepest node first and then backtracks upward. DFS is optimal, requires only O(b^m)/O(bm) time/space and can be reduced to O(m) with backtracking. It is not complete and can get lost if there are infinite paths.\n\nIDFS is basically DFS with a depth-limited subcall. So like DFS+BFS. IDFS has time complexity O(b^d) and space complexity O(bd) if there’s a solution, otherwise the same as DFS. \n\nBidirectional search searches from the starting node and the goal node and ends when the two searches intersect. Both complete and optimal. Takes less time and space.\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* **Planning agents** - agents that rely on factored or structured representation\n* **Informed** - the ability to have additional information about where the goal is\n* **Uninformed** - no additional information about where the goal is\n* **Solution** - a collection of actions and states that starts from the initial state and goes to the goal state\n* **Open-loop** - a linear one stream system\n* **Close-loop** - contains a self loop to fix and update information\n* **Problem** - contains the state space, an action function, a cost function for the action, and a transition model\n* **Optimal solution** - lowest cost solution that the algorithm can produce\n* **Model** - an abstraction of a real world problem\n* **Abstraction** - a high level representation of a problem\n* **Standarized problems** - problem with fixed environments and definitions; reached for research testing purposes\n* **Real-world problems** - problems that attempt to solve problems in the real-world\n* **Grid world** - often represented as a 2-d matrix\n* **Route-finding problem** - algorithms used to find a goal state\n* **Tsp** - a type of touring problem in which every state needs to be visited at least once\n* **Vlsi layout** - the cordination of minizing area/delays and maximizing performance in a chip\n* **Cell layout** - finding the best way to organize all the smaller components into cell boxes\n* **Channel routing** - finding the best way to connect wires to cells\n* **Search algorithm** - with an input of the problem, the output will be either the solution or failure\n* **Search tree** - the representation of looking at the search space\n* **Node** - a representation of an existing state\n* **Expand** - explore what the node is connected to\n* **Successor node** - a child node that came from a parent node\n* **Frontier** - unexpanded nodes that have been added\n* **Reached** - when a node has been expanded\n* **Best-first search** - an algorithm that always takes the lowest value node based on an f(n)\n* **Queue** - a data structure that can be used in search problems\n* **Priority queue** - pop off based on minimum cost\n* **Fifo queue** - first-in-first-out; like a person standing in line; used in BFS\n* **Lifo queue** - last-in-first-out; like a stack of dishes; used in DFS\n* **Cylce** - visiting the same node more than once\n* **Graph search** - search algorithm representation if redundant paths are searched\n* **Tree search** - search algorithm representation if redundant paths are not searched\n* **Systematic** - must to able to reach all the states that are connected to the initial state\n* **Depth** - how many layers does the algorithm go\n* **Branching factor** - how many children is connected to each parent node\n* **Bfs** - expands level by level using a FIFO queue\n* **Early goal test** - when the node gets added to frontier, it gets checked if it is the goal state\n* **Late goal test** - tests if the node is the goal state only when it gets popped off the queue\n* **Uniform-cost search** - explores the shortest path cost first; Dijkstra's algorithm\n* **Dfs** - goes to explore the depths first and then propagate back upward\n* **Backtracking search** - an space efficient implementation of DFS\n* **Depth-limited search** - DFS, but with a limit\n* **Iterative deepening search** - repeatedly recursively calls DFS until it reaches the limit\n* **Bidirectional search** - search from both the initial state and goal state and look for when they meet\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nInformed search algorithms have heuristic functions that allow them to guess additional information about the distance to the goal.\n\nGreedy-best-first search expands nodes with the lowest h(n) value. GBFS is not complete and not optimal. The time and space complexity depends on the amount of vertices.\n\nA* search expands nodes with the lowest g(n) + h(n), where g(n) represents the cost to the current node and h(n) represents the cost to the goal node. A* is a complete algorithm, but only optimal with admissible heuristics. Search contours expands uniformly circular in UCS, but in A* it gravitates towards the goal.\n\nWeighted A* search could find the goal faster at the cost of searching more spaces.\n\nBeam search only keeps the k-best nodes in the frontier and this limits the overall size of the search space.\n\nIDA* search combines A* and IDFS, improving the space complexity and the cutoff used is the f(n) = g(n) + h(n)\n\nRecursive best-first search improves the space complexity of best-first search to linear space. Recursively propagates the best value of the child upward. RBFS is optimal if heuristic is admissible. Due to the small space complexity explored, it possible that redundant exploration happens for both RBFS and IDA*\n\nSMA* is optimal and complete if there is a reachable solution.\n\nBidirectional heuristic search takes the maximum of the front search and the backwards search.\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nManhattan distance is an admissible heuristic where you calculate how many moves you are away from your correct position\n\nHeuristic functions reduce the depth space by a factor making it smaller than uninformed search space\n\nA heuristic dominates another if for each n value, the h(n) value is greater than another heuristic. Since both heuristics are assumed to be admissible, that means that the dominant heuristic will be closer to the real answer.\n\nCreating admissible heuristics by creating a relaxed version of the current problem. If you can use the heuristic to solve the relaxed version, then the heuristic is admissible.\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Hueristic function** - additional information that helps determine the distance to the goal\n* **Greedy best-first search** - an algorithm that expands the smallest huerstic function of a node; f(n)=h(n)\n* **Straight-line distance** - the distance between two locations determined by a straight line\n* **A* search** - an informed algorithm that uses the function of f(n) = g(n) + h(n) to determine priority\n* **Admissible heuristic** - an optimistic heuristic that will enver overestimate the actual cost to the goal\n* **Consistency** - the current hueristic value is less than the hueristic value of the successor + the cost\n* **Triangle inequality** - the sum of two sides of a triangle will always be larger than one side\n* **Contour** - how the node search space looks as the algorithm runs\n* **Monotonic** - will always increase\n* **Prunes** - doesn't explore all the states\n* **Satisficing** - answers that aren't necessarily correct, but give a good representation of what the answer could be\n* **Inadmissible heuristic** - an unoptimistic heuristics that overestimates the path\n* **Bounded suboptimals search** - look for solutions that are within a specific range to the optimal solution\n* **Bounded-cost search** - only look at solutions that are less than some constant cost\n* **Unbounded-cost search** - accept any solution if we can find it quickly\n* **Speedy search** - a variation of greedy best-first search that uses a new hueristic to estimate actions to the goal\n* **Reference count** - the amount of times a state has been reached\n* **Beam search** - an algorithm that limits the frontier size to only the best k-options with the highest f-scores\n* **Ida*** - an iterative version of A* that uses less memory and uses the g(n)+h(n) as a limit\n* **Recursive best-first search (rbfs)** - RBFS is a recursive version of best-first search and it only uses linear space complexity\n* **Ma*** - A* search with a memory bound\n* **Sma*** - A simplified version of MA*, add leaves until it reaches the memory bound and once reached, drop the worst leaves\n* **Front-to-end** - hueristic function estimates the cost to the goal state\n* **Front-to-front** - hueristic function estimates the distance from the oppposing frontier\n* **Effective branching factor b*** - the amount of successors connected to an A* node\n* **Dominatse** - when one hueristic h(n) >= h(n) because this means that the first heuristic is more acccurate\n* **Relaxed problems** - simplified version of the given problem\n* **Pattern database** - a structure that stores all the cost for all the subproblems\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nZero-sum games are games where one person's gain is another person's lost and AIs can solve these type of games.\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nGames can be defined as a MAX player and a MIN player; we play from the perspective of MAX. MAX wants to maximize the value and MIN wants to minimize MAX's value.\n\nThe minimax algorithm choose the best move based on the assumption that the other player will choose their own best move at every turn. It uses a recursive algorithm that propagates the best values upward.\n\nAlpha-beta pruning is a more optimized version of the minimax algorithm. Alpha is the atleast value for MAX (the highest value it can get from this path). Beta is the at most value for MIN (the lowest value that it will allow MAX to get if it choose this path)\n\nThe time complexity of minimax is O(b^m) and space complexity is O(bm). Alpha-Beta Pruning reduces the time to O(b^(m/2))\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nCutoff test tells the alpha-beta pruning when to stop recursively looking down the tree\n\nIf the cutoff is reached, then evalutate the game state and then return it.\n\nThe horizon effect is basically delaying the evitable by using stalling tactics. In an effort to reduce the horizon effect, always choose the best move in every position (singular extension)\n\nIn an effect to reduce size, deploy forward pruning which prunes bad moves and increases inaccuracy\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nAlpha-beta pruning on stochasic games use chance instead of actual values. Therefore, it must use the expected values.\n\nNew algorithm, expectiminimax.\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Imperfect information** - not having all the information within an environment\n* **Perfect information** - environments that are deterministic and static\n* **Zero-sum game** - one person's gains is another person's lost\n* **Terminal state** - the state in which the game terminates\n* **Utility function** - a function that determines the expected utility of a given action\n* **Game tree** - a representation of all the states within a game as a tree like structure\n* **Minimax search** - an recursive algorithm that maximizes utility based on the assumption the opponent will play perfectly\n* **Ply** - a level within the game tree which belongs to one player\n* **Minimax value** - the best value that the MAX player can get within the game tree\n* **Minimax decision** - the best choice that the MAX player can choose to get the minimax value\n* **Back up** - recursively propagates the value from the leaves to the root node in the game tree\n* **Alliance** - teaming up\n* **Alpha-beta pruning** - alpha = MAX's best option (at least) and beta = MIN's best option (at most)\n* **Killer moves** - the best moves within the game\n* **Transposition** - getting to the same game state via different set of moves\n* **Type a strategy** - limit the depth of the tree, but consider all possible moves\n* **Type b strategy** - following the good moves to the maximum depth\n* **Cutoff test** - a test used to determine when the alpha-beta search algorithm should stop searching\n* **Expected value** - the expected outcome based on value and probability\n* **Material value** - the worth of each component within a game\n* **Weighted linear function** - a function based on expected value of weighted values * game feature piece\n* **Quiescent** - a stable state within the game, where there are no moves to be taken\n* **Horizon effect** - delaying the inevitable by using stalling tactics\n* **Singular extension** - always choosing the best move when possible if given the chance\n* **Forward pruning** - prunes the bad moves even though this might lead to inaccurate answers, faster\n* **Late move reduction** - reduce the search space for moves that appear later in the game\n* **Policy** - deploying a strategy that will get the best move for each given state\n* **Retrograde** - reverse the rules and commit to a backwards search\n* **Monte carlo tree search** - multiple simulations of complete games are ran and the expected utility is the value\n* **Playout policy** - a simulation policy that is biased towards the best moves\n* **Selection policy** - focuses the computation on selected parts of the tree\n* **Exploration** - discovering new states\n* **Stochastic games** - games that involve chance\n* **Chance nodes** - a node that gives out has outputs of varying probabilites\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nCSPs are made up of a set of variables, a set of domains, and a set of constrains. \nThe constraints are made up a pair containing (value of compared nodes, the possible values the nodes can take).\n\nA solution is a complete and consistent assignment to a CSP. \nWhen every variable is assigned in the problem, then the assignment is considered complete. \nWhen the assignment does not violate any constraints for each variable, then that is a consistent assignment for each variable.\n\nCSPs are generally considered NP-complete problems.\n\nCSPs can be visualzied as graph problems with constraints.\n\nReasons to form a CSP: easy and natural representation of many problems; solver algorithms work well; can reduce the search space\n\nCSPs can be used to solve color map assigning and job scheduling\n\nAn example of CSPs with continous domains is experiments using the Hubble telescope. Linear programming is a well known group of these sort of problems.\n\nUnary and Binary are two types of constraints.\n\nOne type of global constraint is the AllDiff constraint used in Sudoku.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nCSP algorithms use the core idea of constraint propagation in which constraints can reduce the amount of possible domain values for varaibles around it.\n\nIf there is local consistency, then all inconsistent values can be removed as we move through the graph.\n\nNode consistency is when all variables respect the unary constraint.\n\nArc consistency is when all variables respect the binary constraint.\n\nAC3 is an algorithm that enforces arc consistency across a graph. If the algorithm changes a value in the tail, then it has to check the neighbors. Otherwise, if nothing is changed, then it moves onto the next arc pair.\n\nAC3 will return failure if it cannot find a solution that is arc consistent. The time complexit is O(cd^3), where c is the amount of binary constraitns and d is the largest domain size.\n\nPath consistency is more strict than arc consistency and looks at triplet constraints. \nWe say there is path consistency if for every assignment (Node1, Node2) that is consistent, there is an assignment (Node1, Node3) and (Node3, Node2).\nIf so, then path consistency exists.\n\nk-consistency says taht each varaible can have a consistent value; 1-consistent = node-consistency, 2-consistent = arc consistency, 3-consistent = path consistency\n\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nforward checking is a type of simple inference, but it only checks on one node.\n\nMAC <-> AC3 with guessing and backtracking\n\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Csp** - factored representation which means that each state has set of variables and each variable has its own value\n* **Scope** - a tuple of nodes that are being compared\n* **Relation** - possible values that can be assigned to the scope nodes\n* **Assignment** - giving nodes a value\n* **Consistent** - no constraints are broken\n* **Complete assignment** - each node has a value\n* **Solution** - when all the assignments are complete and consistent\n* **Constraint graph** - graph representation of CSP\n* **Disjunctive constraint** - overlaps are not allowed; they must occur sequentially\n* **Precedence constraint** - add additional constraint to a task before another task to be started\n* **Discrete finite domains** - fixed number of domain values\n* **Linear constraint** - everything must be a linear value\n* **Continuous domain** - an infinite set of domain values\n* **Linear programming** - problems that can be solved in linear time\n* **Unary constraint** - a restriction on the value of a variable\n* **Binary constraint** - a restriction on which two variables cannot be related to each other\n* **Global constraints** - constraints that involve more than 3 number of variables\n* **Cryptarithmetic** - a puzzle in which letters represent numeric values\n* **Constraint hypergraph** - a graph representation that consist of both regular nodes and hypernodes\n* **Dual graph** - a way to transform a n-nary CSP to a binary CSP\n* **Preference constraints** - some solutions are more preferable than others in real world CSPs\n* **Constrained optimzation problem** - CSPs with preference constraints creates these types of problem\n* **Constraint propagation** - constraints can reduce other variable possible values\n* **Node consistency** - each variable follows the unary constraint\n* **Arc consistency** - each variable follows the binary constraint\n* **Path consistency** - each variable follows a triplet constraint\n* **K-consistency** - basically, a consistent value can be assigned to each and every variable\n* **Strongly k-consistent** - if the CSP is k to 1 consistent\n* **Forward checking** - a very simple form of inference\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nThere are two main types of approaches; declarative and prodecural. Declarative is an iterative approach, whereas procedural is a preprogramed appraoch.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\nWumpus World example, the agent uses knowledge from previous experiences to make moves\n\n\n## AIMA Chapter 7.3 Logic\n \n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge base** - contains a set of setences that represents some assertion aboutthe world\n* **Knowledge representation langauge** - the language for the knowledge base\n* **Axiom** - a true statement/representation\n* **Inference** - creating a new sentence based on information of the old one\n* **Declaractive** - the desuigner can have the agent iterate over the sentences until the agents knows what to do\n* **Procedural** - programs behavioral desires directly\n* **Wumpus world** - an imagiary world made of caves connected by passageways\n* **Syntax** - rules of a langauge\n* **Semantics** - meanings of a language\n* **Truth** - the correct value\n* **Satisfies** - the act of being a proper model for a sentence\n* **Entailment** - a sentence follows another sentence in the logical sense\n* **Logical inference** - using previous information to make inferences on the current state\n* **Model checking** - checks a sentence against all models\n* **Truth-preserving** - inferences that are created from entailing sentences\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}