{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_Midterm_Notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9c76bcb4-9fdd-4a9a-ddef-04a76a29282a"
      },
      "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": 1,
      "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": "b53b80d1-a78f-4c17-e17f-a7cb07e73f29"
      },
      "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": 2,
      "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 = \"Ian MacDonald\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 3,
      "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",
        "Artificial Intelligence: Field of study concerning how to create and build intelligent entities\n",
        "\n",
        "Four approaches to AI:\n",
        "- Acting Humanly (Turing Test)\n",
        "- Thinking Humanly (Cognitive Modeling)\n",
        "- Thinking Rationally (Laws of Thought)\n",
        "- Acting Rationally (Rational Agent)\n",
        "\n",
        "Acting Humanly: Can you get a computer to create responses that are indistinguishable from a human's?\n",
        "\n",
        "Thinking Humanly: Can a program think/reason in the way humans can?\n",
        "\n",
        "Thinking Rationally: Can a program apply logical reasoning to find a 'correct' solution?\n",
        "\n",
        "Acting Rationally: Can an agent choose the most 'correct' path?\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "An agent is anything that can gather information about it's environment (using sensors) and then take some sort of action (using actuators).\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "How well an agent is doing is determined by some sort of performance measure - a way of evaluating the desirability of a set of \\\n",
        "environment sequences which occur after a set of actions taken by an agent. Performance measures vary depending on the environment, and \\\n",
        "ideally you design your performance measure based on the desired environment state, not based on how you believe the agent should work. \\\n",
        "\n",
        "Rationality depends on:\n",
        "- Performance measure\n",
        "- Prior knowledge\n",
        "- Possible actions\n",
        "- Percept sequence\n",
        "\n",
        "Rational agents work by selecting actions that are expected to maximize it's performance measure, given it's percept sequence, knowledge gained \\ \n",
        "from the percept sequence, and knowledge about it's environment as well as general or built in knowledge.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "Task environment consists of the PEAS: Performance, Environment, Actuators, Sensors. Environments are said to be fully observable when an agent's\n",
        "sensors give it access to all of the information about the environment. They can also be partially observable, or unobservable.\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "An agent is made up of two components - architecture and program.\n",
        "\n",
        "Different Agent Programs: \n",
        "\n",
        "Simple Reflex Agent - Action is based only on the current percept\n",
        "\n",
        "Model Based Reflex Agent - Action is based on some combination of current state, model of how the environment works, \\\n",
        "and a set of rules\n",
        "\n",
        "Goal Based Agent - Actions are chosen based on the desired end state\n",
        "\n",
        "Utility Based Agent - Actions are chosen based on maxmizing some utility value\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "Rene Descartes - cogito ergo sum (I think, therefore I am), can we design a test only a human can pass?\n",
        "\n",
        "Alan Turing - turing test, can a computer pass as a human in conversation?\n",
        "\n",
        "John Searle - turing test not good, because it's not intelligence, just symbol manipulation\n",
        "\n",
        "Daniel Dennet - Brain in a vat\n",
        "\n",
        "General Notes:\n",
        "- Rational agents are not guaranteed to find optimal solutions\n",
        "- Agent programs are different from agent functions\n",
        "- In some environments, randomized behavior can be rational (avoids pitfalls of predictability)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"Anything that can perceive and act in an environment\",\n",
        "\"rationality\" : \"Ability to choose the most 'correct' action\",\n",
        "\"limited rationality\" : \"Ability to choose the most 'correct' action given some computational constraints\",\n",
        "\"natural language processing\": \"Subset of AI dealing with text, speech, and language\",\n",
        "\"knowledge representation\": \"How information is stored\",\n",
        "\"automated reasoning\": \"Ability to use previously gained knowledge to make decisions and take actions\",\n",
        "\"machine learning\": \"Proccess in which a program learns from past experiences/data\",\n",
        "\"computer vision\": \"Subset of AI dealing with images, videos, etc.\",\n",
        "\"robotics\": \"Field dealing with movement and environment interaction\",\n",
        "\"rational agent\": \"Agent that can successfully choose the most 'correct' path\",\n",
        "\"percept\": \"Anything an agent knows about it's environment at a given moment\",\n",
        "\"percept sequence\": \"History of all past percepts\",\n",
        "\"agent function\": \"Function that takes an input percept sequence and returns an action\",\n",
        "\"agent program\": \"Implementation of the agent function for a particular agent\",\n",
        "\"architecture\" : \"physical makeup of an agent\",\n",
        "\"omniscience\" : \"Knowing exactly what will happen, perfect knowledge\",\n",
        "\"autonomy\" : \"Ability for an agent to fend for itself and learn, rather than relying on built in knowledge\",\n",
        "\"deterministic\" : \"Next state depends only on previous state and action taken\",\n",
        "\"nondeterministic\" : \"Environment where each action has possible outcomes, but is not concerned with probabilities\",\n",
        "\"stochastic\" : \"Next state depends on something besides previous state and action taken\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "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": "7511b709-31e8-4a8b-a0a4-698e37fb6ec0"
      },
      "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": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nArtificial Intelligence: Field of study concerning how to create and build intelligent entities\n\nFour approaches to AI:\n- Acting Humanly (Turing Test)\n- Thinking Humanly (Cognitive Modeling)\n- Thinking Rationally (Laws of Thought)\n- Acting Rationally (Rational Agent)\n\nActing Humanly: Can you get a computer to create responses that are indistinguishable from a human's?\n\nThinking Humanly: Can a program think/reason in the way humans can?\n\nThinking Rationally: Can a program apply logical reasoning to find a 'correct' solution?\n\nActing Rationally: Can an agent choose the most 'correct' path?\n \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n\nAn agent is anything that can gather information about it's environment (using sensors) and then take some sort of action (using actuators).\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nHow well an agent is doing is determined by some sort of performance measure - a way of evaluating the desirability of a set of environment sequences which occur after a set of actions taken by an agent. Performance measures vary depending on the environment, and ideally you design your performance measure based on the desired environment state, not based on how you believe the agent should work. \nRationality depends on:\n- Performance measure\n- Prior knowledge\n- Possible actions\n- Percept sequence\n\nRational agents work by selecting actions that are expected to maximize it's performance measure, given it's percept sequence, knowledge gained \\ \nfrom the percept sequence, and knowledge about it's environment as well as general or built in knowledge.\n\n\n## AIMA 2.3 The Nature of Environments\n \nTask environment consists of the PEAS: Performance, Environment, Actuators, Sensors. Environments are said to be fully observable when an agent's\nsensors give it access to all of the information about the environment. They can also be partially observable, or unobservable.\n\n\n## AIMA 2.4 The Structure of Agents\n\nAn agent is made up of two components - architecture and program.\n\nDifferent Agent Programs: \n\nSimple Reflex Agent - Action is based only on the current percept\n\nModel Based Reflex Agent - Action is based on some combination of current state, model of how the environment works, and a set of rules\n\nGoal Based Agent - Actions are chosen based on the desired end state\n\nUtility Based Agent - Actions are chosen based on maxmizing some utility value\n\n\n## Module 1 Lecture Notes\n\nRene Descartes - cogito ergo sum (I think, therefore I am), can we design a test only a human can pass?\n\nAlan Turing - turing test, can a computer pass as a human in conversation?\n\nJohn Searle - turing test not good, because it's not intelligence, just symbol manipulation\n\nDaniel Dennet - Brain in a vat\n\nGeneral Notes:\n- Rational agents are not guaranteed to find optimal solutions\n- Agent programs are different from agent functions\n- In some environments, randomized behavior can be rational (avoids pitfalls of predictability)\n\n\n## Module 1 Definitions\n* **Agent** - Anything that can perceive and act in an environment\n* **Rationality** - Ability to choose the most 'correct' action\n* **Limited rationality** - Ability to choose the most 'correct' action given some computational constraints\n* **Natural language processing** - Subset of AI dealing with text, speech, and language\n* **Knowledge representation** - How information is stored\n* **Automated reasoning** - Ability to use previously gained knowledge to make decisions and take actions\n* **Machine learning** - Proccess in which a program learns from past experiences/data\n* **Computer vision** - Subset of AI dealing with images, videos, etc.\n* **Robotics** - Field dealing with movement and environment interaction\n* **Rational agent** - Agent that can successfully choose the most 'correct' path\n* **Percept** - Anything an agent knows about it's environment at a given moment\n* **Percept sequence** - History of all past percepts\n* **Agent function** - Function that takes an input percept sequence and returns an action\n* **Agent program** - Implementation of the agent function for a particular agent\n* **Architecture** - physical makeup of an agent\n* **Omniscience** - Knowing exactly what will happen, perfect knowledge\n* **Autonomy** - Ability for an agent to fend for itself and learn, rather than relying on built in knowledge\n* **Deterministic** - Next state depends only on previous state and action taken\n* **Nondeterministic** - Environment where each action has possible outcomes, but is not concerned with probabilities\n* **Stochastic** - Next state depends on something besides previous state and action taken\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 = \"\"\"\n",
        "Python pros:\n",
        "- Fast development (easy to read/write syntax, garbage collected)\n",
        "- Portable (can run almost anywhere)\n",
        "- Built in data types (lists, dicts, sets, etc.)\n",
        "- Support libraries (numpy, pandas, sklearn, pytorch, tensorflow)\n",
        "\n",
        "Statically typed - variables are assigned a type when declared/at compile time\n",
        "\n",
        "Dynamically typed - variable types are assigned at runtime, can be overwritten by a new data type\n",
        "\n",
        "*args: accepts variable number of non-keyword arguments to a function\n",
        "\n",
        "**kwargs: accepts a variable number of keyword arguments to a function\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"whether or not an object can be changed\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 372
        },
        "outputId": "2ed8ba5c-9443-4538-c45e-83a025c49bce"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\nPython pros:\n- Fast development (easy to read/write syntax, garbage collected)\n- Portable (can run almost anywhere)\n- Built in data types (lists, dicts, sets, etc.)\n- Support libraries (numpy, pandas, sklearn, pytorch, tensorflow)\n\nStatically typed - variables are assigned a type when declared/at compile time\n\nDynamically typed - variable types are assigned at runtime, can be overwritten by a new data type\n\n*args: accepts variable number of non-keyword arguments to a function\n\n**kwargs: accepts a variable number of keyword arguments to a function\n\n\n## Module 2 Definitions\n* **Mutability** - whether or not an object can be changed\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"\n",
        "A problem consists of five parts:\n",
        "- Initial State\n",
        "- Possible Actions\n",
        "- Transition Model (what does each action do?)\n",
        "- Goal Test (is this the goal?)\n",
        "- Path Cost \n",
        "\n",
        "A solution is a series of actions that leads to a goal state, and an optimal solution is one with the lowest path cost. \n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "Types of problems:\n",
        "- Toy Problems (for demonstrating concepts)\n",
        "- Real World Problems (solutions are actually useful)\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "Search Algorithm Infrastructure:\n",
        "- State\n",
        "- Parent\n",
        "- Action \n",
        "- Path Cost\n",
        "\n",
        "Complexity Measured Using:\n",
        "- Branching Factor (b)\n",
        "- Depth of shallowest goal node (d)\n",
        "- Max length of any possible path (m)\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "Uninformed search algorithms are algorithms with no knowledge besides what is given in the problem definition.\n",
        "\n",
        "Breadth-first search:\n",
        "Expansion goes by depth - nodes at root level are expanded, and then all successors at the following level are expanded, and so on.\n",
        "\n",
        "Uniform cost search:\n",
        "Expands nodes with the lowest path cost g(n), using a priority queue frontier. The goal test is applied when a node is selected for expansion, not when it is generated, \\\n",
        "as the first generated goal node may not be the optimal one. Additionally, factors in if a better path is found to a node that already exists in the frontier. Solution \\\n",
        "found is guaranteed to be optimal.\n",
        "\n",
        "Depth-first search:\n",
        "Expands deepest nodes first, then backtracks to explore other nodes.\n",
        "\n",
        "Depth-limited search:\n",
        "Depth-first search, but stops exploring paths past a pre specified depth.\n",
        "\n",
        "Iterative deepening depth-first search:\n",
        "Combines benefits of dfs (low memory cost) and bfs (completeness) by implementing depth limited search with increasing depth limit.\n",
        "\n",
        "Bidirectional search:\n",
        "Two simultaneous searches, one starting from the initial state and one starting from the goal state, going forward/backward respectively.\n",
        "\n",
        "General Notes:\n",
        "Graph search - avoids redundant paths and repeated states\n",
        "Tree search - does not check for redundancy\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "Search Algorithm Comparison:\n",
        "\n",
        "Completeness: \n",
        "- BFS: Yes \n",
        "- DFS: No\n",
        "- Depth-limited: No\n",
        "- Iterative deepening: Yes\n",
        "\n",
        "Time Complexity:\n",
        "- BFS: $$b^d$$\n",
        "- DFS: $$b^m$$\n",
        "- Depth-limited: $$b^l$$\n",
        "- Iterative deepening: $$b^d$$\n",
        "\n",
        "Space Complexity: \n",
        "- BFS: $$b^d$$\n",
        "- DFS: bm\n",
        "- Depth-limited: bl\n",
        "- Iterative deepening: bd\n",
        "\n",
        "Optimality:\n",
        "- BFS: Yes\n",
        "- DFS: No\n",
        "- Depth-limited: No\n",
        "- Iterative deepening: Yes\n",
        "\n",
        "Graph search - modified version of tree search where nodes are not revisited (memory intensive as list of seen nodes need to be tracked)\n",
        "\n",
        "Use depth-first when:\n",
        "- Limited space\n",
        "- Many possible solutions with long paths, wrong paths are usually short\n",
        "- Search can be fine-tuned quickly\n",
        "\n",
        "Use breadth-first when:\n",
        "- Infinite possible paths\n",
        "- Solutions tend to be short paths\n",
        "- Unlikely paths can be discarded quickly\n",
        "\n",
        "General notes:\n",
        "- A uniform-cost search without a goal is the same as Dijkstra's algorithm\n",
        "\"\"\"\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",
        "\"node\" : \"State\",\n",
        "\"parent node\" : \"Node before this node\",\n",
        "\"child node\" : \"Possible node after this node\",\n",
        "\"leaf node\" : \"Node with no children\",\n",
        "\"frontier\" : \"Set of all possible children\",\n",
        "\"completeness\" : \"Will the algorithm find a solution if one exists (or report failure if one does not)?\",\n",
        "\"optimality\" : \"Will the solution returned be optimal?\",\n",
        "\"time complexity\" : \"How long does the algorithm take to run?\",\n",
        "\"space complexity\" : \"How much memory does the algorithm take up when running?\",\n",
        "\"branching factor\" : \"maximum amount of successors for any node\",\n",
        "\"depth\" : \"number of steps from start to current node\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "10eac856-18c2-4eb0-e479-8237102e97a7"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nA problem consists of five parts:\n- Initial State\n- Possible Actions\n- Transition Model (what does each action do?)\n- Goal Test (is this the goal?)\n- Path Cost \n\nA solution is a series of actions that leads to a goal state, and an optimal solution is one with the lowest path cost. \n\n\n## AIMA Chapter 3.2 Example Problems\n\nTypes of problems:\n- Toy Problems (for demonstrating concepts)\n- Real World Problems (solutions are actually useful)\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nSearch Algorithm Infrastructure:\n- State\n- Parent\n- Action \n- Path Cost\n\nComplexity Measured Using:\n- Branching Factor (b)\n- Depth of shallowest goal node (d)\n- Max length of any possible path (m)\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nUninformed search algorithms are algorithms with no knowledge besides what is given in the problem definition.\n\nBreadth-first search:\nExpansion goes by depth - nodes at root level are expanded, and then all successors at the following level are expanded, and so on.\n\nUniform cost search:\nExpands nodes with the lowest path cost g(n), using a priority queue frontier. The goal test is applied when a node is selected for expansion, not when it is generated, as the first generated goal node may not be the optimal one. Additionally, factors in if a better path is found to a node that already exists in the frontier. Solution found is guaranteed to be optimal.\n\nDepth-first search:\nExpands deepest nodes first, then backtracks to explore other nodes.\n\nDepth-limited search:\nDepth-first search, but stops exploring paths past a pre specified depth.\n\nIterative deepening depth-first search:\nCombines benefits of dfs (low memory cost) and bfs (completeness) by implementing depth limited search with increasing depth limit.\n\nBidirectional search:\nTwo simultaneous searches, one starting from the initial state and one starting from the goal state, going forward/backward respectively.\n\nGeneral Notes:\nGraph search - avoids redundant paths and repeated states\nTree search - does not check for redundancy\n\n\n## Module 3 Lecture Notes\n\nSearch Algorithm Comparison:\n\nCompleteness: \n- BFS: Yes \n- DFS: No\n- Depth-limited: No\n- Iterative deepening: Yes\n\nTime Complexity:\n- BFS: $$b^d$$\n- DFS: $$b^m$$\n- Depth-limited: $$b^l$$\n- Iterative deepening: $$b^d$$\n\nSpace Complexity: \n- BFS: $$b^d$$\n- DFS: bm\n- Depth-limited: bl\n- Iterative deepening: bd\n\nOptimality:\n- BFS: Yes\n- DFS: No\n- Depth-limited: No\n- Iterative deepening: Yes\n\nGraph search - modified version of tree search where nodes are not revisited (memory intensive as list of seen nodes need to be tracked)\n\nUse depth-first when:\n- Limited space\n- Many possible solutions with long paths, wrong paths are usually short\n- Search can be fine-tuned quickly\n\nUse breadth-first when:\n- Infinite possible paths\n- Solutions tend to be short paths\n- Unlikely paths can be discarded quickly\n\nGeneral notes:\n- A uniform-cost search without a goal is the same as Dijkstra's algorithm\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - An agent that can formulate a plan via search\n* **Node** - State\n* **Parent node** - Node before this node\n* **Child node** - Possible node after this node\n* **Leaf node** - Node with no children\n* **Frontier** - Set of all possible children\n* **Completeness** - Will the algorithm find a solution if one exists (or report failure if one does not)?\n* **Optimality** - Will the solution returned be optimal?\n* **Time complexity** - How long does the algorithm take to run?\n* **Space complexity** - How much memory does the algorithm take up when running?\n* **Branching factor** - maximum amount of successors for any node\n* **Depth** - number of steps from start to current node\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 strategies allow you to use problem-specific knowledge that goes beyond just the problem definition, \\\n",
        "leading to more efficient algorithms. The typical approach is using some kind of best-first search, which selects nodes \\\n",
        "for expanision based on an evaluation function.\n",
        "\n",
        "Greedy best-first search:\n",
        "Expands nodes that are closest to the goal first using only the heuristic function, i.e. f(n) = h(n)\n",
        "\n",
        "A* search:\n",
        "Expands nodes based on how long it is expected to take to reach the goal from that node, as well as the cost to reach that node from the start, g(n). \\\n",
        "Formulaically, f(n) = g(n) + h(n). Optimal if h(n) is an admissable heuristic, consistency required for graph-search applications. Optimally efficient, \\\n",
        "but space constraints make it impractical for large-scale problems.\n",
        "\n",
        "Iterative deepening A* search:\n",
        "Reduces memory requirements, uses f-cost as the increasing cutoff. Has problems with real-valued step costs.\n",
        "\n",
        "Recursive best-first search:\n",
        "Structured similarly to recursive dfs, but keeps a variable storing the current best f value. If the current paths are not any better than \\\n",
        "an already found path, the algorithm will stop exploring and backtrack. Can use too little memory at times, can check nodes redundantly.\n",
        "\n",
        "Memory bounded A* (MA*), Simplified MA * (SMA*):\n",
        "SMA* is like A*, but only stores a certain amount of nodes in memory, dropping off worse nodes when memory is needed.\n",
        "\n",
        "General notes:\n",
        "Consistency is a form of the triangle inequality, anything consistent is also admissable, but not vice versa. \n",
        "Formula for consistency: h(n) <= c(n,a,n') + h(n')\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "Different Heuristics:\n",
        "- Straight line/Euclidean distance\n",
        "- City block/Manhattan distance\n",
        "- Misplaced object count\n",
        "\n",
        "General Notes:\n",
        "A heuristic dominates another heuristic if it better than another one, i.e. h2(n) >= h1(n), h2 dominates h1 and thus is more efficient, expanding less than \\\n",
        "or equivalent number of nodes. In general, better to have heuristics that give higher values, so long as they are still admissable/consistent.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "h*(n): oracle heuristic, exact distance from node to goal, unachievable\n",
        "\n",
        "h_teleportation(n): 0, we're here\n",
        "\n",
        "oracle dominates all heuristics, telportation is dominated by all heuristics\n",
        "\n",
        "Inadmissable heuristics are not optimal because good plans may be pushed too far back and may never be expanded. Admissable heuristics never overestimate the true cost, \\\n",
        "and will slow down bad plans. This means the optimal path will always be explored. \n",
        "\n",
        "Search Algorithm Comparison:\n",
        "\n",
        "Completeness: \n",
        "- Greedy best-first search: No\n",
        "- A*: Yes (finite branching factor, fixed cost at each action)\n",
        "\n",
        "Time Complexity:\n",
        "- Greedy best-first search: $$b^m$$\n",
        "- A*: $$b^d$$\n",
        "\n",
        "Space Complexity: \n",
        "- Greedy best-first search: $$b^m$$\n",
        "- A*: $$b^d$$\n",
        "\n",
        "Optimality:\n",
        "- Greedy best-first search: No\n",
        "- A*: Yes (admissable heuristic, consitent heuristic (graphs))\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"evaluation function\" : \"estimate of the cost of a node, f(n)\",    \n",
        "\"heuristic function\" : \"estimate of the cost of the best path from the node to the goal, h(n)\",\n",
        "\"admissable heuristic\" : \"heuristic function that does not overestimate the true cost to reach the goal, optimistic\",    \n",
        "\"consistency\" : \"estimated cost is never greater than step cost to next node plus estimated cost of next node\",  \n",
        "\"effective branching factor\" : \"average amount of successors generated for nodes\",  \n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "516daed4-abae-4a63-d663-526e6babc3ce"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nInformed search strategies allow you to use problem-specific knowledge that goes beyond just the problem definition, leading to more efficient algorithms. The typical approach is using some kind of best-first search, which selects nodes for expanision based on an evaluation function.\n\nGreedy best-first search:\nExpands nodes that are closest to the goal first using only the heuristic function, i.e. f(n) = h(n)\n\nA* search:\nExpands nodes based on how long it is expected to take to reach the goal from that node, as well as the cost to reach that node from the start, g(n). Formulaically, f(n) = g(n) + h(n). Optimal if h(n) is an admissable heuristic, consistency required for graph-search applications. Optimally efficient, but space constraints make it impractical for large-scale problems.\n\nIterative deepening A* search:\nReduces memory requirements, uses f-cost as the increasing cutoff. Has problems with real-valued step costs.\n\nRecursive best-first search:\nStructured similarly to recursive dfs, but keeps a variable storing the current best f value. If the current paths are not any better than an already found path, the algorithm will stop exploring and backtrack. Can use too little memory at times, can check nodes redundantly.\n\nMemory bounded A* (MA*), Simplified MA * (SMA*):\nSMA* is like A*, but only stores a certain amount of nodes in memory, dropping off worse nodes when memory is needed.\n\nGeneral notes:\nConsistency is a form of the triangle inequality, anything consistent is also admissable, but not vice versa. \nFormula for consistency: h(n) <= c(n,a,n') + h(n')\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nDifferent Heuristics:\n- Straight line/Euclidean distance\n- City block/Manhattan distance\n- Misplaced object count\n\nGeneral Notes:\nA heuristic dominates another heuristic if it better than another one, i.e. h2(n) >= h1(n), h2 dominates h1 and thus is more efficient, expanding less than or equivalent number of nodes. In general, better to have heuristics that give higher values, so long as they are still admissable/consistent.\n\n\n## Module 4 Lecture Notes\n\nh*(n): oracle heuristic, exact distance from node to goal, unachievable\n\nh_teleportation(n): 0, we're here\n\noracle dominates all heuristics, telportation is dominated by all heuristics\n\nInadmissable heuristics are not optimal because good plans may be pushed too far back and may never be expanded. Admissable heuristics never overestimate the true cost, and will slow down bad plans. This means the optimal path will always be explored. \n\nSearch Algorithm Comparison:\n\nCompleteness: \n- Greedy best-first search: No\n- A*: Yes (finite branching factor, fixed cost at each action)\n\nTime Complexity:\n- Greedy best-first search: $$b^m$$\n- A*: $$b^d$$\n\nSpace Complexity: \n- Greedy best-first search: $$b^m$$\n- A*: $$b^d$$\n\nOptimality:\n- Greedy best-first search: No\n- A*: Yes (admissable heuristic, consitent heuristic (graphs))\n\n\n## Module 4 Definitions\n* **Evaluation function** - estimate of the cost of a node, f(n)\n* **Heuristic function** - estimate of the cost of the best path from the node to the goal, h(n)\n* **Admissable heuristic** - heuristic function that does not overestimate the true cost to reach the goal, optimistic\n* **Consistency** - estimated cost is never greater than step cost to next node plus estimated cost of next node\n* **Effective branching factor** - average amount of successors generated for nodes\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",
        "Components of a game:\n",
        "- Initial State\n",
        "- Players\n",
        "- Actions \n",
        "- Transition Model/Move Results\n",
        "- Terminal Test (Is game over?)\n",
        "- Utility Function (Assigns final value of a completed game to each player involved)\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Minimax Algorithm:\n",
        "Recursively computes the minimax values of the search tree, which are then backed up through the tree when the recursion unwinds itself to find \\\n",
        "the optimal action to take. Can be expanded to include more than 2 players by returning a vector of values rather than a single one.\n",
        "\n",
        "Minimax Pseudocode:\n",
        "```\n",
        "function MINIMAX-DECISION(state) returns an action\n",
        "return arg maxa ∈ ACTIONS(s) MIN-VALUE(RESULT(state, a))\n",
        "\n",
        "function MAX-VALUE(state) returns a utility value\n",
        "if TERMINAL-TEST(state) then return UTILITY(state)\n",
        "v ← −∞\n",
        "for each a in ACTIONS(state) do\n",
        "v ← MAX(v, MIN-VALUE(RESULT(s, a)))\n",
        "return v\n",
        "\n",
        "function MIN-VALUE(state) returns a utility value\n",
        "if TERMINAL-TEST(state) then return UTILITY(state)\n",
        "v ← ∞\n",
        "for each a in ACTIONS(state) do\n",
        "v ← MIN(v, MAX-VALUE(RESULT(s, a)))\n",
        "return v\n",
        "```\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "Alpha-Beta Pruning:\n",
        "alpha = lower bound on max's outcome\n",
        "beta = upper bound on min's outcome\n",
        "\n",
        "Max won't allow a move that could lead to a worse score for max then alpha, and min won't allow a move that could lead to a better score for max then beta.\n",
        "\n",
        "Alpha-Beta Pruning Pseudocode:\n",
        "```\n",
        "function ALPHA-BETA-SEARCH(state) returns an action\n",
        "v ← MAX-VALUE(state,−∞,+∞)\n",
        "return the action in ACTIONS(state) with value v\n",
        "\n",
        "function MAX-VALUE(state,α, β) returns a utility value\n",
        "if TERMINAL-TEST(state) then return UTILITY(state)\n",
        "v ← −∞\n",
        "for each a in ACTIONS(state) do\n",
        "v ← MAX(v, MIN-VALUE(RESULT(s,a),α, β))\n",
        "if v ≥ β then return v\n",
        "α ← MAX(α, v)\n",
        "return v\n",
        "\n",
        "function MIN-VALUE(state,α, β) returns a utility value\n",
        "if TERMINAL-TEST(state) then return UTILITY(state)\n",
        "v ← +∞\n",
        "for each a in ACTIONS(state) do\n",
        "v ← MIN(v, MAX-VALUE(RESULT(s,a) ,α, β))\n",
        "if v ≤ α then return v\n",
        "β ← MIN(β, v)\n",
        "return v\n",
        "```\n",
        "\n",
        "Essentially, stores the best values we've found so far for each player, which allows us to ignore paths which are worse than ones we've already found. \\\n",
        "Can be further improved by adding move-ordering strategies to try better moves first (killer move heuristic). \n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Stochastic Games:\n",
        "Game tree is modified to include chance nodes, where the branches of that node have some sort of probability attached to them determining how likely each path \\\n",
        "is to be taken from that point. The value of these nodes is the expected value of the possible paths. In addition to alpha-beta pruning or another type of \\\n",
        "search algorithm, these can be solved using Monte Carlo simulation, having the algorithm play itself over and over with random moves to get an evaluation of \\\n",
        "how good each position is. \n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "Maximum expected utility: should select the action that provides the expected best utility\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "Rational preference constraints:\n",
        "- Orderability\n",
        "- Transitivity\n",
        "- Continuity\n",
        "- Substitutionability\n",
        "- Monotonicity\n",
        "- Decomposability\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "Utility theory: What actions maximize utility, what kind of utility function is at play?\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Simplest game environment:\n",
        "- Multiagent\n",
        "- Static (Environment doesn't change while no actions are occuring)\n",
        "- Discrete (Percepts/Actions are finite)\n",
        "- Fully observable (All players know everything about the game environment at any moment)\n",
        "- Strategic (State determined by current state/action taken by each player)\n",
        "\n",
        "Expectimax search: compute the average score under optimal play\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"multiagent environments\" : \"environments with multiple players who have conflicting goals, aka games\",   \n",
        "\"zero-sum games\" : \"the value of the end of a game adds up to 0 for all players involved\",  \n",
        "\"perfect information\" : \"all possible information about the game is known to all players involved (chess, checkers)\",  \n",
        "\"pruning\" : \"a way to ignore paths you know are going to be sub-optimal\",  \n",
        "\"imperfect information\" : \"not everything about the game is known to both players (hidden cards, etc.)\",  \n",
        "\"search tree\" : \"the part of the larger game tree that is explored in search of a move for a player\",  \n",
        "\"minimax value\" : \"value of that state for the max player, assuming optimal playing by both sides\", \n",
        "\"killer move\" : \"best moves, killer move heuristic tries them before other moves\",  \n",
        "\"transposition table\" : \"set of already explored positions\",   \n",
        "\"stochastic games\" : \"games that include some sort of random element\", \n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "56c13a7e-c5e5-49e2-e3dd-b85d67365472"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nComponents of a game:\n- Initial State\n- Players\n- Actions \n- Transition Model/Move Results\n- Terminal Test (Is game over?)\n- Utility Function (Assigns final value of a completed game to each player involved)\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nMinimax Algorithm:\nRecursively computes the minimax values of the search tree, which are then backed up through the tree when the recursion unwinds itself to find the optimal action to take. Can be expanded to include more than 2 players by returning a vector of values rather than a single one.\n\nMinimax Pseudocode:\n```\nfunction MINIMAX-DECISION(state) returns an action\nreturn arg maxa ∈ ACTIONS(s) MIN-VALUE(RESULT(state, a))\n\nfunction MAX-VALUE(state) returns a utility value\nif TERMINAL-TEST(state) then return UTILITY(state)\nv ← −∞\nfor each a in ACTIONS(state) do\nv ← MAX(v, MIN-VALUE(RESULT(s, a)))\nreturn v\n\nfunction MIN-VALUE(state) returns a utility value\nif TERMINAL-TEST(state) then return UTILITY(state)\nv ← ∞\nfor each a in ACTIONS(state) do\nv ← MIN(v, MAX-VALUE(RESULT(s, a)))\nreturn v\n```\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nAlpha-Beta Pruning:\nalpha = lower bound on max's outcome\nbeta = upper bound on min's outcome\n\nMax won't allow a move that could lead to a worse score for max then alpha, and min won't allow a move that could lead to a better score for max then beta.\n\nAlpha-Beta Pruning Pseudocode:\n```\nfunction ALPHA-BETA-SEARCH(state) returns an action\nv ← MAX-VALUE(state,−∞,+∞)\nreturn the action in ACTIONS(state) with value v\n\nfunction MAX-VALUE(state,α, β) returns a utility value\nif TERMINAL-TEST(state) then return UTILITY(state)\nv ← −∞\nfor each a in ACTIONS(state) do\nv ← MAX(v, MIN-VALUE(RESULT(s,a),α, β))\nif v ≥ β then return v\nα ← MAX(α, v)\nreturn v\n\nfunction MIN-VALUE(state,α, β) returns a utility value\nif TERMINAL-TEST(state) then return UTILITY(state)\nv ← +∞\nfor each a in ACTIONS(state) do\nv ← MIN(v, MAX-VALUE(RESULT(s,a) ,α, β))\nif v ≤ α then return v\nβ ← MIN(β, v)\nreturn v\n```\n\nEssentially, stores the best values we've found so far for each player, which allows us to ignore paths which are worse than ones we've already found. Can be further improved by adding move-ordering strategies to try better moves first (killer move heuristic). \n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic Games:\nGame tree is modified to include chance nodes, where the branches of that node have some sort of probability attached to them determining how likely each path is to be taken from that point. The value of these nodes is the expected value of the possible paths. In addition to alpha-beta pruning or another type of search algorithm, these can be solved using Monte Carlo simulation, having the algorithm play itself over and over with random moves to get an evaluation of how good each position is. \n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nMaximum expected utility: should select the action that provides the expected best utility\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nRational preference constraints:\n- Orderability\n- Transitivity\n- Continuity\n- Substitutionability\n- Monotonicity\n- Decomposability\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nUtility theory: What actions maximize utility, what kind of utility function is at play?\n\n\n## Module 5 Lecture Notes\n\nSimplest game environment:\n- Multiagent\n- Static (Environment doesn't change while no actions are occuring)\n- Discrete (Percepts/Actions are finite)\n- Fully observable (All players know everything about the game environment at any moment)\n- Strategic (State determined by current state/action taken by each player)\n\nExpectimax search: compute the average score under optimal play\n\n\n## Module 5 Definitions\n* **Multiagent environments** - environments with multiple players who have conflicting goals, aka games\n* **Zero-sum games** - the value of the end of a game adds up to 0 for all players involved\n* **Perfect information** - all possible information about the game is known to all players involved (chess, checkers)\n* **Pruning** - a way to ignore paths you know are going to be sub-optimal\n* **Imperfect information** - not everything about the game is known to both players (hidden cards, etc.)\n* **Search tree** - the part of the larger game tree that is explored in search of a move for a player\n* **Minimax value** - value of that state for the max player, assuming optimal playing by both sides\n* **Killer move** - best moves, killer move heuristic tries them before other moves\n* **Transposition table** - set of already explored positions\n* **Stochastic games** - games that include some sort of random element\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",
        "Constraint Satisfaction Problems consist of:\n",
        "X: set of variables\n",
        "D: set of domains, one domain per variable\n",
        "C: set of constraints, determines what combinations of values are allowed\n",
        "\n",
        "Problems are solved through assignment, giving the variables certain values. Assignment types include:\n",
        "Consistent Assignment: Assignment allowed under the set of constraints \n",
        "Complete Assignment: Every variable has been assigned a value\n",
        "Partial Assignment: Some variables have been assigned a value\n",
        "Solution: Complete and consistent assignment\n",
        "\n",
        "Different constraints exist as well, including:\n",
        "Unary constraint: Restricts value of one variable \n",
        "Binary constraint: Relates two variables together, with some restriction on values for one or both\n",
        "Ternary constraint: Same as above but for three variables\n",
        "Global constraint: Restriction for some arbitrary number of variables\n",
        "Preference constraint: Not necessarily a restriction, but certain values are preffered over others\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "Node consistency:\n",
        "All values in a variable's domain are consistent with any unary constraints, i.e. any constraint that has to do with only \\\n",
        "that variable is satisfied.\n",
        "\n",
        "Arc consistency:\n",
        "All values in a variable's domain are consistent with any binary constraints, i.e. any constraint that has to do with the variable \\\n",
        "and another variable are satisfied.\n",
        "\n",
        "AC3 Algorithm:\n",
        "- Start with a set of all possible arcs\n",
        "- Pop an arc off and make sure it is arc consistent\n",
        "- If no values were removed from the domain, pop another arc, otherwise, take any arc that points to the variable who's domain was \\\n",
        "changed and add those arcs back into the set\n",
        "- If a domain is reduced to nothing, report failure\n",
        "- Otherwise, continue until set is empty\n",
        "\n",
        "Will solve some CSP's but not all. Given max domain size d and c binary constraints, time complexity is O($$cd^3$$)\n",
        "\n",
        "Path consistency:\n",
        "Takes arc consistency and adds another element to it, such that the domains must satisfy constraints that a third variable implicitly \\\n",
        "imposes on them.\n",
        "\n",
        "k-consistency:\n",
        "CSP is k consistent if a consistent assignment can be found for any kth variable, given a set of k-1 variables and a consistent assignment to them. \\\n",
        "Strongly k consistent if it is k consistent, k-1 consistent, k-2, etc.\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "Backtracking search:\n",
        "Backtracking search assigns a variable one of the values in it's domain, and then enforces consistency, repeating this proccess until either \\\n",
        "a solution is found, or a state is reached that has no solution. If a no solution state is reached, then the algorithm returns to the last assignment, and assigns \\\n",
        "a different value. If there are no values left, then it backtracks again, until it finds a state where it can assign a new value to a variable. \n",
        "\n",
        "Variable selection can be done randomly/sequentially, but can also be done using some sort of choice method. Minimum-remaining-values heuristic is one way to choose, \\\n",
        "in that method you select the variable with the least amount of options in it's domain, as it is relatively close to a solution already. The degree heuristic is another \\\n",
        "option, in which you select the variable that has the most constraints with other unassigned variables. \n",
        "\n",
        "Value selection can also be done randomly/sequentially, but can also be done using some sort of choice method. Least-constraining-value heuristic picks the value that \\\n",
        "rules out the least amount of options for neighboring variables. \n",
        "\n",
        "Forward checking algorithm:\n",
        "Simple form of inference - every time you assign a value to a variable, you establish arc consistency for that variable by deleting inconsistent values from the domains of \\\n",
        "connected variables. Problem with this is that it only establishes arc consistency for that variable, it doesn't continue to establish it for other variables. \n",
        "\n",
        "Maintaining arc consistency (MAC) algorithm:\n",
        "Solves the problem of the forward checking algorithm not looking ahead by queueing up arcs that are related to the assigned variable. \n",
        "\n",
        "Backtracking methods:\n",
        "Chronological backtracking: undo the most recent assignment\n",
        "Backjumping: undo the most recent assignment in the conflict set, a set of assignments that made the current node unassignable\n",
        "Conflict-directed backjumping: same as above but with a different conflict set\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "Local search for CSPs:\n",
        "Can be effective for solving CSPs. One method is using the min-conflicts heuristic, selecting whichever value leads to the least amount of conflicts with other \\\n",
        "variables. Constraint weighting is also a valid method, giving the individual constraints some sort of weight. The goal is to reduce the total weight, which is recalculated \\\n",
        "after every step. Local search is effective when you have a problem that changes often. \n",
        "\n",
        "Min-conflicts pseudocode:\n",
        "```\n",
        "function MIN-CONFLICTS(csp, max steps) returns a solution or failure\n",
        "inputs: csp, a constraint satisfaction problem\n",
        "max steps, the number of steps allowed before giving up\n",
        "\n",
        "current ← an initial complete assignment for csp\n",
        "for i = 1 to max steps do\n",
        "if current is a solution for csp then return current\n",
        "var ← a randomly chosen conflicted variable from csp.VARIABLES\n",
        "value ← the value v for var that minimizes CONFLICTS(var , v, current, csp)\n",
        "set var = value in current\n",
        "return failure\n",
        "```\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "The structure of a CSP can also be helpful when determining how to solve it.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "CSP Benefits:\n",
        "- General solvability, doesnt require specifics\n",
        "- Knows where constraints are violated, thus where to focus searching\n",
        "- Prunes away branches that violate constraints\n",
        "\n",
        "AC-3 Pseudocode:\n",
        "```\n",
        "function AC-3(csp) return the CSP, possibly with reduced domains\n",
        "inputs: csp, a binary csp with variables {X1, X2, …, Xn}\n",
        "local variables: queue, a queue of arcs initially the arcs in csp\n",
        "while queue is not empty do\n",
        "(Xi, Xj) ¬ queue.pop()\n",
        "if REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\n",
        "for each Xk in NEIGHBORS[Xi ] – {Xj} do\n",
        "add (Xk, Xi) to queue\n",
        "\n",
        "function REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true if we remove a value\n",
        "removed ¬ false\n",
        "for each x in DOMAIN[Xi] do\n",
        "if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\n",
        "then delete x from DOMAIN[Xi]; removed ¬ true\n",
        "return removed\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constraint propagation\" : \"use constraints to remove values from variable domains\",  \n",
        "\"bounds consistent\" : \"value exists satisfying constraint for all possible bounds\",      \n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4341a7cd-f260-49a2-9881-e80c5ded1e4e"
      },
      "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": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nConstraint Satisfaction Problems consist of:\nX: set of variables\nD: set of domains, one domain per variable\nC: set of constraints, determines what combinations of values are allowed\n\nProblems are solved through assignment, giving the variables certain values. Assignment types include:\nConsistent Assignment: Assignment allowed under the set of constraints \nComplete Assignment: Every variable has been assigned a value\nPartial Assignment: Some variables have been assigned a value\nSolution: Complete and consistent assignment\n\nDifferent constraints exist as well, including:\nUnary constraint: Restricts value of one variable \nBinary constraint: Relates two variables together, with some restriction on values for one or both\nTernary constraint: Same as above but for three variables\nGlobal constraint: Restriction for some arbitrary number of variables\nPreference constraint: Not necessarily a restriction, but certain values are preffered over others\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nNode consistency:\nAll values in a variable's domain are consistent with any unary constraints, i.e. any constraint that has to do with only that variable is satisfied.\n\nArc consistency:\nAll values in a variable's domain are consistent with any binary constraints, i.e. any constraint that has to do with the variable and another variable are satisfied.\n\nAC3 Algorithm:\n- Start with a set of all possible arcs\n- Pop an arc off and make sure it is arc consistent\n- If no values were removed from the domain, pop another arc, otherwise, take any arc that points to the variable who's domain was changed and add those arcs back into the set\n- If a domain is reduced to nothing, report failure\n- Otherwise, continue until set is empty\n\nWill solve some CSP's but not all. Given max domain size d and c binary constraints, time complexity is O($$cd^3$$)\n\nPath consistency:\nTakes arc consistency and adds another element to it, such that the domains must satisfy constraints that a third variable implicitly imposes on them.\n\nk-consistency:\nCSP is k consistent if a consistent assignment can be found for any kth variable, given a set of k-1 variables and a consistent assignment to them. Strongly k consistent if it is k consistent, k-1 consistent, k-2, etc.\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nBacktracking search:\nBacktracking search assigns a variable one of the values in it's domain, and then enforces consistency, repeating this proccess until either a solution is found, or a state is reached that has no solution. If a no solution state is reached, then the algorithm returns to the last assignment, and assigns a different value. If there are no values left, then it backtracks again, until it finds a state where it can assign a new value to a variable. \n\nVariable selection can be done randomly/sequentially, but can also be done using some sort of choice method. Minimum-remaining-values heuristic is one way to choose, in that method you select the variable with the least amount of options in it's domain, as it is relatively close to a solution already. The degree heuristic is another option, in which you select the variable that has the most constraints with other unassigned variables. \n\nValue selection can also be done randomly/sequentially, but can also be done using some sort of choice method. Least-constraining-value heuristic picks the value that rules out the least amount of options for neighboring variables. \n\nForward checking algorithm:\nSimple form of inference - every time you assign a value to a variable, you establish arc consistency for that variable by deleting inconsistent values from the domains of connected variables. Problem with this is that it only establishes arc consistency for that variable, it doesn't continue to establish it for other variables. \n\nMaintaining arc consistency (MAC) algorithm:\nSolves the problem of the forward checking algorithm not looking ahead by queueing up arcs that are related to the assigned variable. \n\nBacktracking methods:\nChronological backtracking: undo the most recent assignment\nBackjumping: undo the most recent assignment in the conflict set, a set of assignments that made the current node unassignable\nConflict-directed backjumping: same as above but with a different conflict set\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nLocal search for CSPs:\nCan be effective for solving CSPs. One method is using the min-conflicts heuristic, selecting whichever value leads to the least amount of conflicts with other variables. Constraint weighting is also a valid method, giving the individual constraints some sort of weight. The goal is to reduce the total weight, which is recalculated after every step. Local search is effective when you have a problem that changes often. \n\nMin-conflicts pseudocode:\n```\nfunction MIN-CONFLICTS(csp, max steps) returns a solution or failure\ninputs: csp, a constraint satisfaction problem\nmax steps, the number of steps allowed before giving up\n\ncurrent ← an initial complete assignment for csp\nfor i = 1 to max steps do\nif current is a solution for csp then return current\nvar ← a randomly chosen conflicted variable from csp.VARIABLES\nvalue ← the value v for var that minimizes CONFLICTS(var , v, current, csp)\nset var = value in current\nreturn failure\n```\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nThe structure of a CSP can also be helpful when determining how to solve it.\n\n\n## Module 6 Lecture Notes\n\nCSP Benefits:\n- General solvability, doesnt require specifics\n- Knows where constraints are violated, thus where to focus searching\n- Prunes away branches that violate constraints\n\nAC-3 Pseudocode:\n```\nfunction AC-3(csp) return the CSP, possibly with reduced domains\ninputs: csp, a binary csp with variables {X1, X2, …, Xn}\nlocal variables: queue, a queue of arcs initially the arcs in csp\nwhile queue is not empty do\n(Xi, Xj) ¬ queue.pop()\nif REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\nfor each Xk in NEIGHBORS[Xi ] – {Xj} do\nadd (Xk, Xi) to queue\n\nfunction REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true if we remove a value\nremoved ¬ false\nfor each x in DOMAIN[Xi] do\nif no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\nthen delete x from DOMAIN[Xi]; removed ¬ true\nreturn removed\n```\n\n\n## Module 6 Definitions\n* **Constraint propagation** - use constraints to remove values from variable domains\n* **Bounds consistent** - value exists satisfying constraint for all possible bounds\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "Knowledge based agents generally have some sort of background knowledge, and then when given a percept dive into their knowledge base and return the \\\n",
        "best possible action. The knowledge they gained from this transaction can also be added to the knowledge based to help with future action selection.\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 554
        },
        "outputId": "032f51eb-e2d2-4dc8-f0a5-f700e07d3309"
      },
      "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": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nKnowledge based agents generally have some sort of background knowledge, and then when given a percept dive into their knowledge base and return the best possible action. The knowledge they gained from this transaction can also be added to the knowledge based to help with future action selection.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \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* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "48aa9806-56ff-4132-f688-762d86cf3776"
      },
      "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": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nArtificial Intelligence: Field of study concerning how to create and build intelligent entities\n\nFour approaches to AI:\n- Acting Humanly (Turing Test)\n- Thinking Humanly (Cognitive Modeling)\n- Thinking Rationally (Laws of Thought)\n- Acting Rationally (Rational Agent)\n\nActing Humanly: Can you get a computer to create responses that are indistinguishable from a human's?\n\nThinking Humanly: Can a program think/reason in the way humans can?\n\nThinking Rationally: Can a program apply logical reasoning to find a 'correct' solution?\n\nActing Rationally: Can an agent choose the most 'correct' path?\n \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n\nAn agent is anything that can gather information about it's environment (using sensors) and then take some sort of action (using actuators).\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nHow well an agent is doing is determined by some sort of performance measure - a way of evaluating the desirability of a set of environment sequences which occur after a set of actions taken by an agent. Performance measures vary depending on the environment, and ideally you design your performance measure based on the desired environment state, not based on how you believe the agent should work. \nRationality depends on:\n- Performance measure\n- Prior knowledge\n- Possible actions\n- Percept sequence\n\nRational agents work by selecting actions that are expected to maximize it's performance measure, given it's percept sequence, knowledge gained \\ \nfrom the percept sequence, and knowledge about it's environment as well as general or built in knowledge.\n\n\n## AIMA 2.3 The Nature of Environments\n \nTask environment consists of the PEAS: Performance, Environment, Actuators, Sensors. Environments are said to be fully observable when an agent's\nsensors give it access to all of the information about the environment. They can also be partially observable, or unobservable.\n\n\n## AIMA 2.4 The Structure of Agents\n\nAn agent is made up of two components - architecture and program.\n\nDifferent Agent Programs: \n\nSimple Reflex Agent - Action is based only on the current percept\n\nModel Based Reflex Agent - Action is based on some combination of current state, model of how the environment works, and a set of rules\n\nGoal Based Agent - Actions are chosen based on the desired end state\n\nUtility Based Agent - Actions are chosen based on maxmizing some utility value\n\n\n## Module 1 Lecture Notes\n\nRene Descartes - cogito ergo sum (I think, therefore I am), can we design a test only a human can pass?\n\nAlan Turing - turing test, can a computer pass as a human in conversation?\n\nJohn Searle - turing test not good, because it's not intelligence, just symbol manipulation\n\nDaniel Dennet - Brain in a vat\n\nGeneral Notes:\n- Rational agents are not guaranteed to find optimal solutions\n- Agent programs are different from agent functions\n- In some environments, randomized behavior can be rational (avoids pitfalls of predictability)\n\n\n## Module 1 Definitions\n* **Agent** - Anything that can perceive and act in an environment\n* **Rationality** - Ability to choose the most 'correct' action\n* **Limited rationality** - Ability to choose the most 'correct' action given some computational constraints\n* **Natural language processing** - Subset of AI dealing with text, speech, and language\n* **Knowledge representation** - How information is stored\n* **Automated reasoning** - Ability to use previously gained knowledge to make decisions and take actions\n* **Machine learning** - Proccess in which a program learns from past experiences/data\n* **Computer vision** - Subset of AI dealing with images, videos, etc.\n* **Robotics** - Field dealing with movement and environment interaction\n* **Rational agent** - Agent that can successfully choose the most 'correct' path\n* **Percept** - Anything an agent knows about it's environment at a given moment\n* **Percept sequence** - History of all past percepts\n* **Agent function** - Function that takes an input percept sequence and returns an action\n* **Agent program** - Implementation of the agent function for a particular agent\n* **Architecture** - physical makeup of an agent\n* **Omniscience** - Knowing exactly what will happen, perfect knowledge\n* **Autonomy** - Ability for an agent to fend for itself and learn, rather than relying on built in knowledge\n* **Deterministic** - Next state depends only on previous state and action taken\n* **Nondeterministic** - Environment where each action has possible outcomes, but is not concerned with probabilities\n* **Stochastic** - Next state depends on something besides previous state and action taken\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\nPython pros:\n- Fast development (easy to read/write syntax, garbage collected)\n- Portable (can run almost anywhere)\n- Built in data types (lists, dicts, sets, etc.)\n- Support libraries (numpy, pandas, sklearn, pytorch, tensorflow)\n\nStatically typed - variables are assigned a type when declared/at compile time\n\nDynamically typed - variable types are assigned at runtime, can be overwritten by a new data type\n\n*args: accepts variable number of non-keyword arguments to a function\n\n**kwargs: accepts a variable number of keyword arguments to a function\n\n\n## Module 2 Definitions\n* **Mutability** - whether or not an object can be changed\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\nA problem consists of five parts:\n- Initial State\n- Possible Actions\n- Transition Model (what does each action do?)\n- Goal Test (is this the goal?)\n- Path Cost \n\nA solution is a series of actions that leads to a goal state, and an optimal solution is one with the lowest path cost. \n\n\n## AIMA Chapter 3.2 Example Problems\n\nTypes of problems:\n- Toy Problems (for demonstrating concepts)\n- Real World Problems (solutions are actually useful)\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nSearch Algorithm Infrastructure:\n- State\n- Parent\n- Action \n- Path Cost\n\nComplexity Measured Using:\n- Branching Factor (b)\n- Depth of shallowest goal node (d)\n- Max length of any possible path (m)\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nUninformed search algorithms are algorithms with no knowledge besides what is given in the problem definition.\n\nBreadth-first search:\nExpansion goes by depth - nodes at root level are expanded, and then all successors at the following level are expanded, and so on.\n\nUniform cost search:\nExpands nodes with the lowest path cost g(n), using a priority queue frontier. The goal test is applied when a node is selected for expansion, not when it is generated, as the first generated goal node may not be the optimal one. Additionally, factors in if a better path is found to a node that already exists in the frontier. Solution found is guaranteed to be optimal.\n\nDepth-first search:\nExpands deepest nodes first, then backtracks to explore other nodes.\n\nDepth-limited search:\nDepth-first search, but stops exploring paths past a pre specified depth.\n\nIterative deepening depth-first search:\nCombines benefits of dfs (low memory cost) and bfs (completeness) by implementing depth limited search with increasing depth limit.\n\nBidirectional search:\nTwo simultaneous searches, one starting from the initial state and one starting from the goal state, going forward/backward respectively.\n\nGeneral Notes:\nGraph search - avoids redundant paths and repeated states\nTree search - does not check for redundancy\n\n\n## Module 3 Lecture Notes\n\nSearch Algorithm Comparison:\n\nCompleteness: \n- BFS: Yes \n- DFS: No\n- Depth-limited: No\n- Iterative deepening: Yes\n\nTime Complexity:\n- BFS: $$b^d$$\n- DFS: $$b^m$$\n- Depth-limited: $$b^l$$\n- Iterative deepening: $$b^d$$\n\nSpace Complexity: \n- BFS: $$b^d$$\n- DFS: bm\n- Depth-limited: bl\n- Iterative deepening: bd\n\nOptimality:\n- BFS: Yes\n- DFS: No\n- Depth-limited: No\n- Iterative deepening: Yes\n\nGraph search - modified version of tree search where nodes are not revisited (memory intensive as list of seen nodes need to be tracked)\n\nUse depth-first when:\n- Limited space\n- Many possible solutions with long paths, wrong paths are usually short\n- Search can be fine-tuned quickly\n\nUse breadth-first when:\n- Infinite possible paths\n- Solutions tend to be short paths\n- Unlikely paths can be discarded quickly\n\nGeneral notes:\n- A uniform-cost search without a goal is the same as Dijkstra's algorithm\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - An agent that can formulate a plan via search\n* **Node** - State\n* **Parent node** - Node before this node\n* **Child node** - Possible node after this node\n* **Leaf node** - Node with no children\n* **Frontier** - Set of all possible children\n* **Completeness** - Will the algorithm find a solution if one exists (or report failure if one does not)?\n* **Optimality** - Will the solution returned be optimal?\n* **Time complexity** - How long does the algorithm take to run?\n* **Space complexity** - How much memory does the algorithm take up when running?\n* **Branching factor** - maximum amount of successors for any node\n* **Depth** - number of steps from start to current node\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nInformed search strategies allow you to use problem-specific knowledge that goes beyond just the problem definition, leading to more efficient algorithms. The typical approach is using some kind of best-first search, which selects nodes for expanision based on an evaluation function.\n\nGreedy best-first search:\nExpands nodes that are closest to the goal first using only the heuristic function, i.e. f(n) = h(n)\n\nA* search:\nExpands nodes based on how long it is expected to take to reach the goal from that node, as well as the cost to reach that node from the start, g(n). Formulaically, f(n) = g(n) + h(n). Optimal if h(n) is an admissable heuristic, consistency required for graph-search applications. Optimally efficient, but space constraints make it impractical for large-scale problems.\n\nIterative deepening A* search:\nReduces memory requirements, uses f-cost as the increasing cutoff. Has problems with real-valued step costs.\n\nRecursive best-first search:\nStructured similarly to recursive dfs, but keeps a variable storing the current best f value. If the current paths are not any better than an already found path, the algorithm will stop exploring and backtrack. Can use too little memory at times, can check nodes redundantly.\n\nMemory bounded A* (MA*), Simplified MA * (SMA*):\nSMA* is like A*, but only stores a certain amount of nodes in memory, dropping off worse nodes when memory is needed.\n\nGeneral notes:\nConsistency is a form of the triangle inequality, anything consistent is also admissable, but not vice versa. \nFormula for consistency: h(n) <= c(n,a,n') + h(n')\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\nDifferent Heuristics:\n- Straight line/Euclidean distance\n- City block/Manhattan distance\n- Misplaced object count\n\nGeneral Notes:\nA heuristic dominates another heuristic if it better than another one, i.e. h2(n) >= h1(n), h2 dominates h1 and thus is more efficient, expanding less than or equivalent number of nodes. In general, better to have heuristics that give higher values, so long as they are still admissable/consistent.\n\n\n## Module 4 Lecture Notes\n\nh*(n): oracle heuristic, exact distance from node to goal, unachievable\n\nh_teleportation(n): 0, we're here\n\noracle dominates all heuristics, telportation is dominated by all heuristics\n\nInadmissable heuristics are not optimal because good plans may be pushed too far back and may never be expanded. Admissable heuristics never overestimate the true cost, and will slow down bad plans. This means the optimal path will always be explored. \n\nSearch Algorithm Comparison:\n\nCompleteness: \n- Greedy best-first search: No\n- A*: Yes (finite branching factor, fixed cost at each action)\n\nTime Complexity:\n- Greedy best-first search: $$b^m$$\n- A*: $$b^d$$\n\nSpace Complexity: \n- Greedy best-first search: $$b^m$$\n- A*: $$b^d$$\n\nOptimality:\n- Greedy best-first search: No\n- A*: Yes (admissable heuristic, consitent heuristic (graphs))\n\n\n## Module 4 Definitions\n* **Evaluation function** - estimate of the cost of a node, f(n)\n* **Heuristic function** - estimate of the cost of the best path from the node to the goal, h(n)\n* **Admissable heuristic** - heuristic function that does not overestimate the true cost to reach the goal, optimistic\n* **Consistency** - estimated cost is never greater than step cost to next node plus estimated cost of next node\n* **Effective branching factor** - average amount of successors generated for nodes\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nComponents of a game:\n- Initial State\n- Players\n- Actions \n- Transition Model/Move Results\n- Terminal Test (Is game over?)\n- Utility Function (Assigns final value of a completed game to each player involved)\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nMinimax Algorithm:\nRecursively computes the minimax values of the search tree, which are then backed up through the tree when the recursion unwinds itself to find the optimal action to take. Can be expanded to include more than 2 players by returning a vector of values rather than a single one.\n\nMinimax Pseudocode:\n```\nfunction MINIMAX-DECISION(state) returns an action\nreturn arg maxa ∈ ACTIONS(s) MIN-VALUE(RESULT(state, a))\n\nfunction MAX-VALUE(state) returns a utility value\nif TERMINAL-TEST(state) then return UTILITY(state)\nv ← −∞\nfor each a in ACTIONS(state) do\nv ← MAX(v, MIN-VALUE(RESULT(s, a)))\nreturn v\n\nfunction MIN-VALUE(state) returns a utility value\nif TERMINAL-TEST(state) then return UTILITY(state)\nv ← ∞\nfor each a in ACTIONS(state) do\nv ← MIN(v, MAX-VALUE(RESULT(s, a)))\nreturn v\n```\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\nAlpha-Beta Pruning:\nalpha = lower bound on max's outcome\nbeta = upper bound on min's outcome\n\nMax won't allow a move that could lead to a worse score for max then alpha, and min won't allow a move that could lead to a better score for max then beta.\n\nAlpha-Beta Pruning Pseudocode:\n```\nfunction ALPHA-BETA-SEARCH(state) returns an action\nv ← MAX-VALUE(state,−∞,+∞)\nreturn the action in ACTIONS(state) with value v\n\nfunction MAX-VALUE(state,α, β) returns a utility value\nif TERMINAL-TEST(state) then return UTILITY(state)\nv ← −∞\nfor each a in ACTIONS(state) do\nv ← MAX(v, MIN-VALUE(RESULT(s,a),α, β))\nif v ≥ β then return v\nα ← MAX(α, v)\nreturn v\n\nfunction MIN-VALUE(state,α, β) returns a utility value\nif TERMINAL-TEST(state) then return UTILITY(state)\nv ← +∞\nfor each a in ACTIONS(state) do\nv ← MIN(v, MAX-VALUE(RESULT(s,a) ,α, β))\nif v ≤ α then return v\nβ ← MIN(β, v)\nreturn v\n```\n\nEssentially, stores the best values we've found so far for each player, which allows us to ignore paths which are worse than ones we've already found. Can be further improved by adding move-ordering strategies to try better moves first (killer move heuristic). \n\n\n## AIMA Chapter 5.5 Stochastic Games\n\nStochastic Games:\nGame tree is modified to include chance nodes, where the branches of that node have some sort of probability attached to them determining how likely each path is to be taken from that point. The value of these nodes is the expected value of the possible paths. In addition to alpha-beta pruning or another type of search algorithm, these can be solved using Monte Carlo simulation, having the algorithm play itself over and over with random moves to get an evaluation of how good each position is. \n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\nMaximum expected utility: should select the action that provides the expected best utility\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\nRational preference constraints:\n- Orderability\n- Transitivity\n- Continuity\n- Substitutionability\n- Monotonicity\n- Decomposability\n\n\n## AIMA Chapter 16.3 Utility Functions\n\nUtility theory: What actions maximize utility, what kind of utility function is at play?\n\n\n## Module 5 Lecture Notes\n\nSimplest game environment:\n- Multiagent\n- Static (Environment doesn't change while no actions are occuring)\n- Discrete (Percepts/Actions are finite)\n- Fully observable (All players know everything about the game environment at any moment)\n- Strategic (State determined by current state/action taken by each player)\n\nExpectimax search: compute the average score under optimal play\n\n\n## Module 5 Definitions\n* **Multiagent environments** - environments with multiple players who have conflicting goals, aka games\n* **Zero-sum games** - the value of the end of a game adds up to 0 for all players involved\n* **Perfect information** - all possible information about the game is known to all players involved (chess, checkers)\n* **Pruning** - a way to ignore paths you know are going to be sub-optimal\n* **Imperfect information** - not everything about the game is known to both players (hidden cards, etc.)\n* **Search tree** - the part of the larger game tree that is explored in search of a move for a player\n* **Minimax value** - value of that state for the max player, assuming optimal playing by both sides\n* **Killer move** - best moves, killer move heuristic tries them before other moves\n* **Transposition table** - set of already explored positions\n* **Stochastic games** - games that include some sort of random element\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\nConstraint Satisfaction Problems consist of:\nX: set of variables\nD: set of domains, one domain per variable\nC: set of constraints, determines what combinations of values are allowed\n\nProblems are solved through assignment, giving the variables certain values. Assignment types include:\nConsistent Assignment: Assignment allowed under the set of constraints \nComplete Assignment: Every variable has been assigned a value\nPartial Assignment: Some variables have been assigned a value\nSolution: Complete and consistent assignment\n\nDifferent constraints exist as well, including:\nUnary constraint: Restricts value of one variable \nBinary constraint: Relates two variables together, with some restriction on values for one or both\nTernary constraint: Same as above but for three variables\nGlobal constraint: Restriction for some arbitrary number of variables\nPreference constraint: Not necessarily a restriction, but certain values are preffered over others\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n\nNode consistency:\nAll values in a variable's domain are consistent with any unary constraints, i.e. any constraint that has to do with only that variable is satisfied.\n\nArc consistency:\nAll values in a variable's domain are consistent with any binary constraints, i.e. any constraint that has to do with the variable and another variable are satisfied.\n\nAC3 Algorithm:\n- Start with a set of all possible arcs\n- Pop an arc off and make sure it is arc consistent\n- If no values were removed from the domain, pop another arc, otherwise, take any arc that points to the variable who's domain was changed and add those arcs back into the set\n- If a domain is reduced to nothing, report failure\n- Otherwise, continue until set is empty\n\nWill solve some CSP's but not all. Given max domain size d and c binary constraints, time complexity is O($$cd^3$$)\n\nPath consistency:\nTakes arc consistency and adds another element to it, such that the domains must satisfy constraints that a third variable implicitly imposes on them.\n\nk-consistency:\nCSP is k consistent if a consistent assignment can be found for any kth variable, given a set of k-1 variables and a consistent assignment to them. Strongly k consistent if it is k consistent, k-1 consistent, k-2, etc.\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nBacktracking search:\nBacktracking search assigns a variable one of the values in it's domain, and then enforces consistency, repeating this proccess until either a solution is found, or a state is reached that has no solution. If a no solution state is reached, then the algorithm returns to the last assignment, and assigns a different value. If there are no values left, then it backtracks again, until it finds a state where it can assign a new value to a variable. \n\nVariable selection can be done randomly/sequentially, but can also be done using some sort of choice method. Minimum-remaining-values heuristic is one way to choose, in that method you select the variable with the least amount of options in it's domain, as it is relatively close to a solution already. The degree heuristic is another option, in which you select the variable that has the most constraints with other unassigned variables. \n\nValue selection can also be done randomly/sequentially, but can also be done using some sort of choice method. Least-constraining-value heuristic picks the value that rules out the least amount of options for neighboring variables. \n\nForward checking algorithm:\nSimple form of inference - every time you assign a value to a variable, you establish arc consistency for that variable by deleting inconsistent values from the domains of connected variables. Problem with this is that it only establishes arc consistency for that variable, it doesn't continue to establish it for other variables. \n\nMaintaining arc consistency (MAC) algorithm:\nSolves the problem of the forward checking algorithm not looking ahead by queueing up arcs that are related to the assigned variable. \n\nBacktracking methods:\nChronological backtracking: undo the most recent assignment\nBackjumping: undo the most recent assignment in the conflict set, a set of assignments that made the current node unassignable\nConflict-directed backjumping: same as above but with a different conflict set\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\nLocal search for CSPs:\nCan be effective for solving CSPs. One method is using the min-conflicts heuristic, selecting whichever value leads to the least amount of conflicts with other variables. Constraint weighting is also a valid method, giving the individual constraints some sort of weight. The goal is to reduce the total weight, which is recalculated after every step. Local search is effective when you have a problem that changes often. \n\nMin-conflicts pseudocode:\n```\nfunction MIN-CONFLICTS(csp, max steps) returns a solution or failure\ninputs: csp, a constraint satisfaction problem\nmax steps, the number of steps allowed before giving up\n\ncurrent ← an initial complete assignment for csp\nfor i = 1 to max steps do\nif current is a solution for csp then return current\nvar ← a randomly chosen conflicted variable from csp.VARIABLES\nvalue ← the value v for var that minimizes CONFLICTS(var , v, current, csp)\nset var = value in current\nreturn failure\n```\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\nThe structure of a CSP can also be helpful when determining how to solve it.\n\n\n## Module 6 Lecture Notes\n\nCSP Benefits:\n- General solvability, doesnt require specifics\n- Knows where constraints are violated, thus where to focus searching\n- Prunes away branches that violate constraints\n\nAC-3 Pseudocode:\n```\nfunction AC-3(csp) return the CSP, possibly with reduced domains\ninputs: csp, a binary csp with variables {X1, X2, …, Xn}\nlocal variables: queue, a queue of arcs initially the arcs in csp\nwhile queue is not empty do\n(Xi, Xj) ¬ queue.pop()\nif REMOVE-INCONSISTENT-VALUES(Xi, Xj) then\nfor each Xk in NEIGHBORS[Xi ] – {Xj} do\nadd (Xk, Xi) to queue\n\nfunction REMOVE-INCONSISTENT-VALUES(Xi, Xj) return true if we remove a value\nremoved ¬ false\nfor each x in DOMAIN[Xi] do\nif no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj\nthen delete x from DOMAIN[Xi]; removed ¬ true\nreturn removed\n```\n\n\n## Module 6 Definitions\n* **Constraint propagation** - use constraints to remove values from variable domains\n* **Bounds consistent** - value exists satisfying constraint for all possible bounds\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\nKnowledge based agents generally have some sort of background knowledge, and then when given a percept dive into their knowledge base and return the best possible action. The knowledge they gained from this transaction can also be added to the knowledge based to help with future action selection.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \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* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4L--QhYW-icm"
      },
      "source": [
        ""
      ],
      "execution_count": 18,
      "outputs": []
    }
  ]
}