{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Anisa's FINAL 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/",
          "height": 0
        },
        "outputId": "63271225-f209-4a86-80b9-3b9f5c46bb00"
      },
      "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": 197,
      "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/",
          "height": 0
        },
        "outputId": "5ac7eb63-ac81-4dcb-8060-f95797ff059b"
      },
      "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": 198,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 199,
      "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 = \"\"\" Chapter 1.1 summary. \"\"\" \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 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"The goal of a rational agent is to act rationally \\\n",
        "(not just think rationally, and not to imitate humans). An agent perceives through \\\n",
        "sensors and acts through actuators. An agent function maps a sequence of percept \\\n",
        "vectors to an action. An agent program is not the same as the function, which is \\\n",
        "the “what’; program is the “how”, the actual program that runs on the physical \\\n",
        "architecture of the agent. To be rational is to maximize the expected value of \\\n",
        "the performance measure given info available. Rationality is not omniscience so \\\n",
        "success is not guaranteed. The task environment is the problem specification for \\\n",
        "which the agent is a solution. It's defined by PEAS: Performance measure, \\\n",
        "Environment, Actuators, Sensors. Types of environments: \\\n",
        "-- fully observable (chess) VS partially observable (taxi, poker, medical diagnosis) \\\n",
        "--deterministic (chess, sudoku) VS nondeterministic VS stochastic \\\n",
        "(wheel of fortune, backgammon, probabilities are known) \\\n",
        "--episodic (one thing at a time, not concerned about a sequence, i.e. image analysis \\\n",
        "or part-picking robot) VS sequential (results depend on a sequence of events: \\\n",
        "chess, taxi, backgammon)\\\n",
        "--static (chess) VS dynamic (taxi, does environment change while you’re deciding \\\n",
        "what to do)\n",
        "--discrete (chess) VS continuous (taxi, image analysis) \\\n",
        "--single agent VS multiagent \\\n",
        "How we do know if something is part of environment or is another agent? \\\n",
        "If it has its own performance measure, then it's another agent. \\\n",
        "A reflex agent chooses an action based on the current percept only and ignores \\\n",
        "the rest of the percept history. A problem-solving agent must plan ahead and do search.\n",
        "\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",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 200,
      "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": 895
        },
        "cellView": "form",
        "outputId": "0b6d7b15-7e52-4eea-e056-e5a7c306fca4"
      },
      "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": 201,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \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 Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\nThe goal of a rational agent is to act rationally (not just think rationally, and not to imitate humans). An agent perceives through sensors and acts through actuators. An agent function maps a sequence of percept vectors to an action. An agent program is not the same as the function, which is the “what’; program is the “how”, the actual program that runs on the physical architecture of the agent. To be rational is to maximize the expected value of the performance measure given info available. Rationality is not omniscience so success is not guaranteed. The task environment is the problem specification for which the agent is a solution. It's defined by PEAS: Performance measure, Environment, Actuators, Sensors. Types of environments: -- fully observable (chess) VS partially observable (taxi, poker, medical diagnosis) --deterministic (chess, sudoku) VS nondeterministic VS stochastic (wheel of fortune, backgammon, probabilities are known) --episodic (one thing at a time, not concerned about a sequence, i.e. image analysis or part-picking robot) VS sequential (results depend on a sequence of events: chess, taxi, backgammon)--static (chess) VS dynamic (taxi, does environment change while you’re deciding what to do)\n--discrete (chess) VS continuous (taxi, image analysis) --single agent VS multiagent How we do know if something is part of environment or is another agent? If it has its own performance measure, then it's another agent. A reflex agent chooses an action based on the current percept only and ignores the rest of the percept history. A problem-solving agent must plan ahead and do search.\n\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "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 = \"\"\" You can concatenate lists using the + operator.\\\n",
        "You can’t concatenate dictionaries that way. Trying to remove something that \\\n",
        "isn’t present in a set will cause a key error. You can’t reassign items in a \\\n",
        "tuple, but if the item is a list or dictionary, you can access that item, \\\n",
        "and if mutable, you can change it. The slice operation returns a new list. Strings \\\n",
        "do not support item assignment, so you can't replace a char in a string \\\n",
        "with a different char just by reassigning it.\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 202,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 243
        },
        "outputId": "dea804cf-040d-4b38-b802-70f04411f390"
      },
      "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": 203,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n You can concatenate lists using the + operator.You can’t concatenate dictionaries that way. Trying to remove something that isn’t present in a set will cause a key error. You can’t reassign items in a tuple, but if the item is a list or dictionary, you can access that item, and if mutable, you can change it. The slice operation returns a new list. Strings do not support item assignment, so you can't replace a char in a string with a different char just by reassigning it.\n \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" A problem-solving agent tries to find a path to the goal state. \\\n",
        "This problem is called search. Every state is atomic, meaning that it has no internal \\\n",
        "structure. What you see is all there is. The search can be uninformed or informed, \\\n",
        "depending on whether it knows anything about distance from the goal. To search \\\n",
        "successfully, we need to formulate the search problem: what is the goal, how are we \\\n",
        "abstracting the environment into states and actions, what kind of search will we use \\\n",
        "to find a solution. Simpler search problems involve open-loop systems in which the \\\n",
        "environment is essentially fixed and once the agent has come up with a solution, \\\n",
        "it can execute it without taking in any new percepts. Closed-loop would keep paying \\\n",
        "attention and the solution would be a branching strategy that depends on percepts. \\\n",
        "The action cost function helps you determine the cost of a path as you move along. \\\n",
        "Some simple problems make every action cost the same (such as 1). You could give \\\n",
        "some actions a higher cost to try to influence behavior. An optimal solution is just \\\n",
        "a path to the goal that has the lowest cost among all solutions.  \n",
        " \"\"\"\n",
        "chapter3_2 = \"\"\" Standardized problems contrast with real world problems and are \\\n",
        "much simpler, but they're helpful for illustrating search techniques and establishing \\\n",
        "benchmarks for researchers to evaluate algorithm efficiency. Some real world problems \\\n",
        "solved with search are protein design (an assembly problem), automatic assembly \\\n",
        "sequencing of complex objects (as in factories), and route-finding in networks, \\\n",
        "military operations, and airline travel. \"\"\"\n",
        "chapter3_3 = \"\"\" A search tree is not the same thing as a state space graph. \\\n",
        "The state space graph contains all possible states and the transitions between \\\n",
        "them (an edge between two states indicates an action that produces this transtion), \\\n",
        "but a search tree describes paths between the states. Each node in the search tree \\\n",
        "is not a state but rather a path. It could store the path explicitly or allow for \\\n",
        "path reconstruction by storing its parent. To expand a node is to consider all \\\n",
        "possible actions from that node, which in turn create different successor/child nodes. \\\n",
        "A node is reached if it has been generated, but it is not expanded unless its \\\n",
        "successors have been generated. The frontier contains unexpanded nodes from which \\\n",
        "we choose the next node for exploration depending on our search strategy. Best-first \\\n",
        "search refers to the general approach of picking the node from the frontier with the \\\n",
        "minimum value for some evaluation function f(n). This kind of search uses a priority \\\n",
        "queue which always pops off the node with minimum f(n). Breadth-First Search uses \\\n",
        "a FIFO queue and DFS uses LIFO (a stack). Redundant paths are possible in problems \\\n",
        "where the same state can be reached via cycles or via a worse path than has already \\\n",
        "been found. To avoid this you can track reached states in a lookup table. This \\\n",
        "transforms the tree-like search into a graph search. This takes memory so if the \\\n",
        "problem doesn't require it (if certain constraints rule out redundancy, better not \\\n",
        "to use it. A compromise is to rule out short cycles but not all redundant paths. \\\n",
        "This can be done in constant time by only checking a few nodes up the chain. \\\n",
        "To be complete, a search strategy must be systematic.\"\"\"\n",
        "chapter3_4 = \"\"\" Uninformed search strategies have no idea how close the goal is. \\\n",
        "BFS is uninformed, but since it's systematic, it's complete even on infinite spaces, \\\n",
        "unlike DFS which is complete only in finite spaces. A nice feature of BFS is that \\\n",
        "it finds the shortest path to the goal assuming all actions have the same cost. \\\n",
        "It actions have different costs, then the path with fewest edges is not necessarily \\\n",
        "the cost-optimal path. BFS space/time complexity are both O(b^d). Exponential runtimes \\\n",
        "like this make any but the smallest instances intractable, so generally uninformed \\\n",
        "search only works for very small instances. While BFS moves outward in waves of \\\n",
        "uniform depth, uniform-cost search moves in waves of uniform path-cost. This is a \\\n",
        "type of best-first search where f(n) is the path-cost. This is better than BFS if \\\n",
        "actions have different costs. Uniform-cost search is complete and cost-optimal but \\\n",
        "can take even longer than BFS if it ends up exploring large trees that are cheap \\\n",
        "but fruitless before gettting to higher-cost but useful actions. DFS uses much less \\\n",
        "memory but is not cost-optimal or complete. However, iterative deepening search \\\n",
        "can be complete and cost-optimal if action costs are identical. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"Search problems involve: states, actions, performance \\\n",
        "measure. The solution to search problem is sequence of actions that form a path \\\n",
        "to the goal state. The solution may be a fixed sequence for a simpler environment \\\n",
        "or a branching strategy for a less observable or predictable environment. The \\\n",
        "transition model specifies which actions are available in a state and how they will \\\n",
        "change to a new state. The path cost must be additive and reflect performance measure. \\\n",
        "The solution is optimal if no other solution has lower path cost. The way you formulate \\\n",
        "a search problem greatly affects its efficiency. Consider which properties matter \\\n",
        "(for a state), what actions are possible, and how to represent them. The state space \\\n",
        "is the set of all states reachable from initial state by any sequence of actions. \\\n",
        "The frontier is set of all states available for expanding from current state; \\\n",
        "to expand a state is to apply legal action to that state. Tree search is a basic \\\n",
        "kind of search algorithm. The root is the initial state. Unlike graphs, tree search \\\n",
        "treats different paths to same state as unique, which can turn a linear problem \\\n",
        "into an exponential one. Using graphs instead can remedy this. A node is more than \\\n",
        "just a state. It can have other information such as parent node, action, depth, \\\n",
        "path cost. Graph search algorithms primarily differ from tree search in that \\\n",
        "graphs keep track of nodes that have already been explored and only expand nodes \\\n",
        "that aren’t in the frontier or the explored set. The search strategy is simply \\\n",
        "the order of tree expansion (LIFO, FIFO, priority).\\ \n",
        "Uniform-cost search is guaranteed to find an optimal solution, and Dijkstra's \\\n",
        "algorithm is just uniform-cost search without a goal. \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",
        "\"complete\" : \"guaranteed to find a solution or report failure\",\n",
        "\"optimal\" : \"finds solution with the lowest path cost\", \n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 204,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1103
        },
        "outputId": "4034cb8f-777f-4f63-ca99-f602ceafaf97"
      },
      "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": 205,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n A problem-solving agent tries to find a path to the goal state. This problem is called search. Every state is atomic, meaning that it has no internal structure. What you see is all there is. The search can be uninformed or informed, depending on whether it knows anything about distance from the goal. To search successfully, we need to formulate the search problem: what is the goal, how are we abstracting the environment into states and actions, what kind of search will we use to find a solution. Simpler search problems involve open-loop systems in which the environment is essentially fixed and once the agent has come up with a solution, it can execute it without taking in any new percepts. Closed-loop would keep paying attention and the solution would be a branching strategy that depends on percepts. The action cost function helps you determine the cost of a path as you move along. Some simple problems make every action cost the same (such as 1). You could give some actions a higher cost to try to influence behavior. An optimal solution is just a path to the goal that has the lowest cost among all solutions.  \n \n\n## AIMA Chapter 3.2 Example Problems\n Standardized problems contrast with real world problems and are much simpler, but they're helpful for illustrating search techniques and establishing benchmarks for researchers to evaluate algorithm efficiency. Some real world problems solved with search are protein design (an assembly problem), automatic assembly sequencing of complex objects (as in factories), and route-finding in networks, military operations, and airline travel. \n\n## AIMA Chapter 3.3 Search Algorithms\n A search tree is not the same thing as a state space graph. The state space graph contains all possible states and the transitions between them (an edge between two states indicates an action that produces this transtion), but a search tree describes paths between the states. Each node in the search tree is not a state but rather a path. It could store the path explicitly or allow for path reconstruction by storing its parent. To expand a node is to consider all possible actions from that node, which in turn create different successor/child nodes. A node is reached if it has been generated, but it is not expanded unless its successors have been generated. The frontier contains unexpanded nodes from which we choose the next node for exploration depending on our search strategy. Best-first search refers to the general approach of picking the node from the frontier with the minimum value for some evaluation function f(n). This kind of search uses a priority queue which always pops off the node with minimum f(n). Breadth-First Search uses a FIFO queue and DFS uses LIFO (a stack). Redundant paths are possible in problems where the same state can be reached via cycles or via a worse path than has already been found. To avoid this you can track reached states in a lookup table. This transforms the tree-like search into a graph search. This takes memory so if the problem doesn't require it (if certain constraints rule out redundancy, better not to use it. A compromise is to rule out short cycles but not all redundant paths. This can be done in constant time by only checking a few nodes up the chain. To be complete, a search strategy must be systematic.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uninformed search strategies have no idea how close the goal is. BFS is uninformed, but since it's systematic, it's complete even on infinite spaces, unlike DFS which is complete only in finite spaces. A nice feature of BFS is that it finds the shortest path to the goal assuming all actions have the same cost. It actions have different costs, then the path with fewest edges is not necessarily the cost-optimal path. BFS space/time complexity are both O(b^d). Exponential runtimes like this make any but the smallest instances intractable, so generally uninformed search only works for very small instances. While BFS moves outward in waves of uniform depth, uniform-cost search moves in waves of uniform path-cost. This is a type of best-first search where f(n) is the path-cost. This is better than BFS if actions have different costs. Uniform-cost search is complete and cost-optimal but can take even longer than BFS if it ends up exploring large trees that are cheap but fruitless before gettting to higher-cost but useful actions. DFS uses much less memory but is not cost-optimal or complete. However, iterative deepening search can be complete and cost-optimal if action costs are identical. \n\n## Module 3 Lecture Notes\nSearch problems involve: states, actions, performance measure. The solution to search problem is sequence of actions that form a path to the goal state. The solution may be a fixed sequence for a simpler environment or a branching strategy for a less observable or predictable environment. The transition model specifies which actions are available in a state and how they will change to a new state. The path cost must be additive and reflect performance measure. The solution is optimal if no other solution has lower path cost. The way you formulate a search problem greatly affects its efficiency. Consider which properties matter (for a state), what actions are possible, and how to represent them. The state space is the set of all states reachable from initial state by any sequence of actions. The frontier is set of all states available for expanding from current state; to expand a state is to apply legal action to that state. Tree search is a basic kind of search algorithm. The root is the initial state. Unlike graphs, tree search treats different paths to same state as unique, which can turn a linear problem into an exponential one. Using graphs instead can remedy this. A node is more than just a state. It can have other information such as parent node, action, depth, path cost. Graph search algorithms primarily differ from tree search in that graphs keep track of nodes that have already been explored and only expand nodes that aren’t in the frontier or the explored set. The search strategy is simply the order of tree expansion (LIFO, FIFO, priority).\\ \nUniform-cost search is guaranteed to find an optimal solution, and Dijkstra's algorithm is just uniform-cost search without a goal. \n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Complete** - guaranteed to find a solution or report failure\n* **Optimal** - finds solution with the lowest path cost\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Informed search strategies are informed with hints about the distance \\\n",
        "to the goal. The hint is a heuristic function h(n). Greedy best-first search uses \\\n",
        "only h(n) and nothing else, i.e. f(n) = h(n). The most common informed search strategy \\\n",
        "is A* Search, for which f(n) = g(n) + h(n), i.e. it considers the path-cost to a \\\n",
        "node and the estimated distance to the goal from that node. A* is complete but it's \\\n",
        "only optimal if the heuristic is admissible. An admissible heuristic is optimistic: \\\n",
        "it never overestimates the real distance to the goal. Even better if the heuristic is consistent, \\\n",
        "which means that f(n) values will always increase monotonically along a path to the \\\n",
        "goal, so the first time the goal is reached, we know there is no shorter path yet to \\\n",
        "be found. In other words, if the heuristic is consistent, we always reach a state \\\n",
        "for the first time via the optimal path. Consistent implies admissible but the reverse \\\n",
        "is not always true. If the heuristic is not consistent, you can't declare victory \\\n",
        "the first time you reach the goal; there may be a shorter path from a node that \\\n",
        "hasn't been expanded yet. Sometimes it's worth it to use an inadmissible heuristic; it \\\n",
        "may return a non-optimal solution, but could be way faster. If optimality is less \\\n",
        "important than speed, this might be a good approach. Weighted-A* Search is an example; \\\n",
        "it weights h(n) more heavily to focus the search toward the goal without totally \\\n",
        "ignoring path costs. There are other ways of balancing or defining priorities: \\\n",
        "bounded suboptimal search looks for a solution within a constant factor of the \\\n",
        "optimal cost; bounded-cost wants a solution less than some constant; unbounded-cost \\\n",
        "wants a solution of any cost as fast as possible. A* 's main problem is the large \\\n",
        "memory requirement of storing nodes both in the reached table and on the frontier. \\\n",
        "Some modified algorithms offer ways to reduce memory requirements. IDA* (iterative-\\\n",
        "deeping A*) is similar to that for DFS but uses f(n) as the cutoff and increases it \\\n",
        "in each iteration to the next lowest f(n) not visited before. Only efficient if \\\n",
        "f-costs are integers, otherwise might expand by one state each time. Other options \\\n",
        "are Recursive Best First Search (RBFS), Memory-Bounded A* (MA*), and Simplified \\\n",
        "MA* (SMA*). \"\"\"\n",
        "chapter3_6 = \"\"\" If one heuristic dominates another, it is more efficient. h1 \\\n",
        "dominates h2 if for any node h1(n) > h2(n). How do people come up with heuristic \\\n",
        "functions? They might relax the original problem or derive them from the solution \\\n",
        "cost of a subproblem. Pattern databases store solution costs for subproblems; \\\n",
        "you can obtain the h(n) for a node by looking up its state in the database. You \\\n",
        "could also precompute landmarks, which is a lot of computation up front, but it's \\\n",
        "amortized over many future search requests. Google Maps does this. Heuristics can \\\n",
        "also be learned from experience via machine learning; this might make use of \\\n",
        "certain features of a state that are relevant to predicting its heuristic value.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" We can obtain more efficient A* performance by \\\n",
        "substituting a heuristic with a lower effective branching factor (b*) or by \\\n",
        "substituting a heuristic that dominates our current one. IDA* and RBFS are \\\n",
        "variations on A* that use less memory, but they can suffer from using too little \\\n",
        "memory. MA* and SMA* use all available memory, and once it's full, they drop an \\\n",
        "old node in order to add a new one to the search tree. A*'s use of space, with \\\n",
        "pruning, is O(b^d). Euclidean distance is a consistent and admissible heuristic \\\n",
        "for estimating travel distance between two locations. A* search isn't until it \\\n",
        "expands the goal node. It keeps a priority queue ordered by minimum f(n) value \\\n",
        "(f(n) = g(n) + h(n)), and keeps dequeueing the min value node. So even if we \\\n",
        "reach the goal, we just add it to the queue, and then take the next node with \\\n",
        "min value. When we dequeue the goal, its f(n) value will be the cost of the \\\n",
        "optimal path to it.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 206,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 800
        },
        "outputId": "0a3e0dad-a2aa-4a96-cd6b-4bbb616c8ceb"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 207,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed search strategies are informed with hints about the distance to the goal. The hint is a heuristic function h(n). Greedy best-first search uses only h(n) and nothing else, i.e. f(n) = h(n). The most common informed search strategy is A* Search, for which f(n) = g(n) + h(n), i.e. it considers the path-cost to a node and the estimated distance to the goal from that node. A* is complete but it's only optimal if the heuristic is admissible. An admissible heuristic is optimistic: it never overestimates the real distance to the goal. Even better if the heuristic is consistent, which means that f(n) values will always increase monotonically along a path to the goal, so the first time the goal is reached, we know there is no shorter path yet to be found. In other words, if the heuristic is consistent, we always reach a state for the first time via the optimal path. Consistent implies admissible but the reverse is not always true. If the heuristic is not consistent, you can't declare victory the first time you reach the goal; there may be a shorter path from a node that hasn't been expanded yet. Sometimes it's worth it to use an inadmissible heuristic; it may return a non-optimal solution, but could be way faster. If optimality is less important than speed, this might be a good approach. Weighted-A* Search is an example; it weights h(n) more heavily to focus the search toward the goal without totally ignoring path costs. There are other ways of balancing or defining priorities: bounded suboptimal search looks for a solution within a constant factor of the optimal cost; bounded-cost wants a solution less than some constant; unbounded-cost wants a solution of any cost as fast as possible. A* 's main problem is the large memory requirement of storing nodes both in the reached table and on the frontier. Some modified algorithms offer ways to reduce memory requirements. IDA* (iterative-deeping A*) is similar to that for DFS but uses f(n) as the cutoff and increases it in each iteration to the next lowest f(n) not visited before. Only efficient if f-costs are integers, otherwise might expand by one state each time. Other options are Recursive Best First Search (RBFS), Memory-Bounded A* (MA*), and Simplified MA* (SMA*). \n\n## AIMA Chapter 3.6 Heuristic Functions\n If one heuristic dominates another, it is more efficient. h1 dominates h2 if for any node h1(n) > h2(n). How do people come up with heuristic functions? They might relax the original problem or derive them from the solution cost of a subproblem. Pattern databases store solution costs for subproblems; you can obtain the h(n) for a node by looking up its state in the database. You could also precompute landmarks, which is a lot of computation up front, but it's amortized over many future search requests. Google Maps does this. Heuristics can also be learned from experience via machine learning; this might make use of certain features of a state that are relevant to predicting its heuristic value.\n\n## Module 4 Lecture Notes\nSearch problems involve: states, actions, performance measure. The solution to search problem is sequence of actions that form a path to the goal state. The solution may be a fixed sequence for a simpler environment or a branching strategy for a less observable or predictable environment. The transition model specifies which actions are available in a state and how they will change to a new state. The path cost must be additive and reflect performance measure. The solution is optimal if no other solution has lower path cost. The way you formulate a search problem greatly affects its efficiency. Consider which properties matter (for a state), what actions are possible, and how to represent them. The state space is the set of all states reachable from initial state by any sequence of actions. The frontier is set of all states available for expanding from current state; to expand a state is to apply legal action to that state. Tree search is a basic kind of search algorithm. The root is the initial state. Unlike graphs, tree search treats different paths to same state as unique, which can turn a linear problem into an exponential one. Using graphs instead can remedy this. A node is more than just a state. It can have other information such as parent node, action, depth, path cost. Graph search algorithms primarily differ from tree search in that graphs keep track of nodes that have already been explored and only expand nodes that aren’t in the frontier or the explored set. The search strategy is simply the order of tree expansion (LIFO, FIFO, priority).\\ \nUniform-cost search is guaranteed to find an optimal solution, and Dijkstra's algorithm is just uniform-cost search without a goal. \n \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" An environment is competitive if it has multiple agents with \\\n",
        "conflicting goals. Determining the best action in this context is an adversial \\\n",
        "search problem. To abstract many agents at once, we could abstract them as an economy \\\n",
        "that operates in aggregate, or simply as part of a nondeterministic environment, \\\n",
        "but modeling them as adversaries captures their goal-oriented behavior better. \\\n",
        "Minimax search is an adversarial game-tree search algorithm that finds the optimal \\\n",
        "move. Pruning improves efficiency by ignoring pointless portions of the search tree. \\\n",
        "At any given state, there are two ways to estimate who is winning: either use a \\\n",
        "heuristic evaluation function, or run many quick simulations and average them. \\\n",
        "The most commonly studied adversarial games are zero-sum, meaning that +1 for \\\n",
        "you is -1 for your adversary. These games can be represented with a state-space \\\n",
        "graph, where vertices are states and edges are moves. A game tree is a search tree \\\n",
        "over that graph and could be infinite or just huge (for chess, 10^40 nodes). So we \\\n",
        "need efficient ways to explore the tree. Making an optimal move is more complex \\\n",
        "in adversial games because it requires a conditional strategy that takes into \\\n",
        "account how the adversary will act, just as in war.\"\"\"\n",
        "chapter5_2 = \"\"\"  We use minimax search to determine the optimal move at each state. \\\n",
        "Max goes first. The nodes in the game tree represent whose turn it is to move. The \\\n",
        "edges out of that node are the possible moves. We expand to a certain level, estimate \\\n",
        "the utility of that state, and then return the value of the optimal move from that \\ \n",
        "state, which will be the min value for MIN and the max for MAX. So for every state \\\n",
        "except terminal ones, the value is determined by some calculation of how things play \\\n",
        "out optimally. Minimax is a recursive depth-first algorithm where the base case is a \\\n",
        "terminal state. If m is the max depth of the game tree, it's O(b^m) time and O(bm) \\\n",
        "or O(m) space. This time is impractical for complex games but we can approximate it. \\\n",
        "Alpha-beta pruning cuts the exponent in half. Alpha is the lower-bound for MAX \\\n",
        "(the at least, starts at negative infinity) and Beta is the upper-bound for MIN \\\n",
        "(the at most, starts at positive infinity). Minimax updates these values each time \\\n",
        "something better is found and thereafter will not explore any subtree whose outcome \\\n",
        "would be worse for the opponent, because it knows the opponent will not choose a \\\n",
        "suboptimal path. Essentially, if it's MAX's turn, and for one action the play-out \\\n",
        "based on MIN's optimal moves would result in an outcome lower than MAX's lower bound, \\\n",
        "the algorithm can immediately stop considering any other branches of that subtree, \\\n",
        "because MAX knows that MIN would pick that lower action, won't choose the action \\\n",
        "leading to this sub-optimal (for MAX) subtree. The effectiveness of pruning depends \\\n",
        "on the ordering of the moves. If they go from worst to best, then each new move will \\\n",
        "be worth exploring. Ideally they would go from best to worst, which would halve the \\\n",
        "max depth, reducing the branching factor to its square root and enabling Minimax \\\n",
        "to solve a tree twice as deep in the same amount of time (putting the best moves \\\n",
        "first is called the killer move heuristic). We can't know the best move, but we \\\n",
        "can approximate it. Random choice results in 3/4 the max depth. Even more effective \\\n",
        "is to predict the best move based on data gained as the game is played. Another \\\n",
        "way to improve efficiency is to track previously seen states. Transpositions are \\\n",
        "different permutations of the move sequence that result in the same state. If we \\\n",
        "cache the heuristic value of states in a transposition table, we can avoid redundant \\\n",
        "work. For chess, this technique can cut time in half. Since some game trees are still \\\n",
        "unwieldy even with move ordering and caching, Type A and Type B techniques are used \\\n",
        "to further improve efficiency. Type A limits depth but not breadth (wide but shallow) \\\n",
        "and evaluates pseudo-terminal nodes with a heuristic function. Type B limits breadth \\\n",
        "but not depth (deep but narrow).\\\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\" To limit the depth even when states aren't actually terminal, \\\n",
        "we test for the cutoff instead of terminality, and we estimate the value of that \\\n",
        "state with a heuristic evaluation function. If the state is actually terminal, its \\\n",
        "evaluation is its actually utility; otherwise the estimate is somewhere between \\\n",
        "a loss and a win. This estimate shouldn't take too long or it defeats the purpose. \\\n",
        "The estimate can be based on assigning material value to features of the state, and \\\n",
        "can use a weighted linear function with normalized weights. Clearly these values \\\n",
        "should be correlated with actual chances of winning. These values may come from \\\n",
        "human experience or machine learning. While the cutoff can be a fixed limit, \\\n",
        "iterative deepening is more effective. The cutoff is also more effective if only \\\n",
        "applied to quiescent positions (no pending move that would swing big), in which \\\n",
        "case a quick quiescene search must be done to estimate this. It's tough to eliminate \\\n",
        "the horizon effect (staving off an inevitable loss with delay tactics). A more \\\n",
        "aggressive version of alpha-beta pruning is forward pruning. Unlike alpha-beta, \\\n",
        "forward pruning could prune moves that are actually good. Its aim is to trim \n",
        "probably-bad moves to save time. It can be done with beam search (just try the \\\n",
        "n best moves) or using probabilities based on prior experience. Or you can use \\\n",
        "late move reduction, which reduces the depth to which moves later in the list are \\\n",
        "explored, unless the value returned exceeds alpha, in which case the search is run \\\n",
        "to full depth. One last time saver: the opening game and endgame have fewer possible \\\n",
        "moves and therefore moves can actually be chosen with table lookup instead of \\\n",
        "costly search strategies. A policy is a mapping from every possible state to \\\n",
        "the best move from the state.\"\"\"\n",
        "chapter5_5 = \"\"\" Some adversarial games like backgammon are also stochastic and \\\n",
        "involve chance with known probabilities. Their game trees have chance nodes between \\\n",
        "MAX and MIN nodes, and the minimax values are based on the expected value (sum of \\\n",
        "the value over all outcomes, weighted by the probability of each chance action). \\\n",
        "In the expectiminimax algorithm this is called expectiminimax value.\\\n",
        "It's critical that these values are a positive \\\n",
        "linear transformation of the probability of winning, and not just values with an \\\n",
        "accurate preference order. We want values to reflect the probability of winning \\\n",
        "from some state. While minimax takes O(b^m), expectiminimax takes O(b^m * n^m) where\n",
        "n is the number of distinct dice rolls. This reflects consideration of all possible \\\n",
        "dice roll sequences. This means that the possible ways the game could unfold have \\\n",
        "been massively increased and we need a way to simplify the search. We are already \\\n",
        "alpha-beta pruning MIN and MAX nodes and we can do something similar for chance \\\n",
        "nodes. Essentially, you bound the upper and lower range of the utility function \\\n",
        "so you can upper-bound a chance node's value without examining all of its children. \\\n",
        "You could also use forward pruning (such as beam search) or skip the evaluation function \\\n",
        "and use Monte Carlo instead.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" We have considered some simple goal-based agents that clearly \\\n",
        "differentiate between good and bad states, but now we'll consider decision-theoretic \\\n",
        "agents that assign a continuous range of values to states. This involves a combination \\\n",
        "of utility theory and probability theory. The basic principle of decision theory is \\\n",
        "maximum expected utility (MEU), which is different from performance measure because \\\n",
        "performance measure gives a score to the historical sequence of states, while MEU \\\n",
        "estimates the value of the next state. The simplest form of decision theory assumes an \\\n",
        "episodic environment and thus considers only the immediate outcomes of actions. Every \\\n",
        "outcome has some probability of occuring and some utility. The expected utility of an \\\n",
        "action is the average utility of all outcomes weighted by their probability of occurring. \\\n",
        "MEU says that an agent should maximize the EU, but does not itself say how that should \\\n",
        "be done.  \"\"\"\n",
        "chapter16_2 = \"\"\" To understand why averaging expected utility is rational, we can \\\n",
        "show that MEU follows logically if we write down constraints on rational preferences \\\n",
        "that a rational agent should have. These constraints are the axioms of utility \\\n",
        "theory: orderability, transivitity, continuity, substitutability, monotonicity, \\\n",
        "decomposability. Violations of these axioms is patently irrational. It turns out \\\n",
        "that an agent can act rationally (meaning consistent with its rational preferences) \\\n",
        "only by choosing an action that maximizes expected utility, even if it's not doing \\\n",
        "so explicitly. \"\"\"\n",
        "chapter16_3 = \"\"\" We may want our decision-theoretic agent to make decision that \\\n",
        "reflect human preferences, and thus we may need to figure out a human's utility \\\n",
        "function. You can do this by preference elicitation. We'd like a scale for this \\\n",
        "utility that's bounded by some best and worst value; these are 0 and 1 in a normalized \\\n",
        "utility. Decision theory is a normative theory, meaning it describes how a rational \\\n",
        "agent should act, in contrast to descriptive theory which describes how people \\\n",
        "actually act. Humans have many biases such as the anchoring effect that result in \\\n",
        "irrational decisions.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"For alpha-beta pruning, MIN updates beta \\\n",
        "(to minimize it) and compares to MAX's alpha. \\\n",
        "If beta <= alpha, it stops evaluating because MAX won't follow this path.\\\n",
        "MAX updates alpha and compares to MIN's beta. Again, if beta <= alpha, it stops and \\\n",
        "returns that alpha value. Basically, both MAX and MIN keep going as long as beta \\\n",
        "is bigger than alpha. If we explore all branches of a node, the alpha and beta \\\n",
        "are the same at the end. If we pruned early, either alpha or beta is the original \\\n",
        "+/- infinity value. If a child beta is less than the parent alpha, it never gets \\\n",
        "updated and stays + infinity.\\\n",
        "The easiest way to encapsulate consistency is this: if a heuristic is consistent, \\\n",
        "f(n) will always increase monotonically on the path to the goal. The key implication \\\n",
        "is that once you hit the goal, you know you've hit it with the shortest path. \\\n",
        "If the heuristic isn't consistent, there could still be a shorter path that you \\\n",
        "haven't found yet.\\\n",
        "Here's an example: say that A is actually 10 away from goal, and B is 8 away. \\\n",
        "And say that h(A) is 9 and h(B) is 8. This heuristic is admissible because it \\\n",
        "didn't overestimate the real distances, but it's not consistent. Here's why. \\\n",
        "The step cost from A to B is 2, so the sum of that cost and h(B) is 2+8=10. \\\n",
        "But h(A) is only 9. It's logically inconsistent that the estimated distance \\\n",
        "from A is less than the path from A to B plus the estimate from B. To be consistent, \\\n",
        "the estimate from A would have to be greater than or equal to the cost of going \\\n",
        "from A to B plus B's estimated distance from the goal.\\\n",
        "For an optimal solution, TreeSearch-A* admissible heuristic is sufficient, but \n",
        "\\GraphSearch A* requires a consistent heuristic.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\" : \"fully observable\",\n",
        "\"imperfect information\" : \"partially observable\",\n",
        "\"move\" : \"action\",\n",
        "\"position\" : \"state\",\n",
        "\"transition model\" : \"rules for the state that results from taking some \\\n",
        "action from some state\",\n",
        "\"terminal test\" : \"True when game is over, otherwise False\",\n",
        "\"utility function\" : \"defines final numeric value for a player in terminal state\", \n",
        "\"ply\" : \"one move by one player\",   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 208,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1847
        },
        "outputId": "ec85a3d1-503f-499b-c548-051250f98423"
      },
      "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": 209,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n An environment is competitive if it has multiple agents with conflicting goals. Determining the best action in this context is an adversial search problem. To abstract many agents at once, we could abstract them as an economy that operates in aggregate, or simply as part of a nondeterministic environment, but modeling them as adversaries captures their goal-oriented behavior better. Minimax search is an adversarial game-tree search algorithm that finds the optimal move. Pruning improves efficiency by ignoring pointless portions of the search tree. At any given state, there are two ways to estimate who is winning: either use a heuristic evaluation function, or run many quick simulations and average them. The most commonly studied adversarial games are zero-sum, meaning that +1 for you is -1 for your adversary. These games can be represented with a state-space graph, where vertices are states and edges are moves. A game tree is a search tree over that graph and could be infinite or just huge (for chess, 10^40 nodes). So we need efficient ways to explore the tree. Making an optimal move is more complex in adversial games because it requires a conditional strategy that takes into account how the adversary will act, just as in war.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n  We use minimax search to determine the optimal move at each state. Max goes first. The nodes in the game tree represent whose turn it is to move. The edges out of that node are the possible moves. We expand to a certain level, estimate the utility of that state, and then return the value of the optimal move from that \\ \nstate, which will be the min value for MIN and the max for MAX. So for every state except terminal ones, the value is determined by some calculation of how things play out optimally. Minimax is a recursive depth-first algorithm where the base case is a terminal state. If m is the max depth of the game tree, it's O(b^m) time and O(bm) or O(m) space. This time is impractical for complex games but we can approximate it. Alpha-beta pruning cuts the exponent in half. Alpha is the lower-bound for MAX (the at least, starts at negative infinity) and Beta is the upper-bound for MIN (the at most, starts at positive infinity). Minimax updates these values each time something better is found and thereafter will not explore any subtree whose outcome would be worse for the opponent, because it knows the opponent will not choose a suboptimal path. Essentially, if it's MAX's turn, and for one action the play-out based on MIN's optimal moves would result in an outcome lower than MAX's lower bound, the algorithm can immediately stop considering any other branches of that subtree, because MAX knows that MIN would pick that lower action, won't choose the action leading to this sub-optimal (for MAX) subtree. The effectiveness of pruning depends on the ordering of the moves. If they go from worst to best, then each new move will be worth exploring. Ideally they would go from best to worst, which would halve the max depth, reducing the branching factor to its square root and enabling Minimax to solve a tree twice as deep in the same amount of time (putting the best moves first is called the killer move heuristic). We can't know the best move, but we can approximate it. Random choice results in 3/4 the max depth. Even more effective is to predict the best move based on data gained as the game is played. Another way to improve efficiency is to track previously seen states. Transpositions are different permutations of the move sequence that result in the same state. If we cache the heuristic value of states in a transposition table, we can avoid redundant work. For chess, this technique can cut time in half. Since some game trees are still unwieldy even with move ordering and caching, Type A and Type B techniques are used to further improve efficiency. Type A limits depth but not breadth (wide but shallow) and evaluates pseudo-terminal nodes with a heuristic function. Type B limits breadth but not depth (deep but narrow). \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n To limit the depth even when states aren't actually terminal, we test for the cutoff instead of terminality, and we estimate the value of that state with a heuristic evaluation function. If the state is actually terminal, its evaluation is its actually utility; otherwise the estimate is somewhere between a loss and a win. This estimate shouldn't take too long or it defeats the purpose. The estimate can be based on assigning material value to features of the state, and can use a weighted linear function with normalized weights. Clearly these values should be correlated with actual chances of winning. These values may come from human experience or machine learning. While the cutoff can be a fixed limit, iterative deepening is more effective. The cutoff is also more effective if only applied to quiescent positions (no pending move that would swing big), in which case a quick quiescene search must be done to estimate this. It's tough to eliminate the horizon effect (staving off an inevitable loss with delay tactics). A more aggressive version of alpha-beta pruning is forward pruning. Unlike alpha-beta, forward pruning could prune moves that are actually good. Its aim is to trim \nprobably-bad moves to save time. It can be done with beam search (just try the n best moves) or using probabilities based on prior experience. Or you can use late move reduction, which reduces the depth to which moves later in the list are explored, unless the value returned exceeds alpha, in which case the search is run to full depth. One last time saver: the opening game and endgame have fewer possible moves and therefore moves can actually be chosen with table lookup instead of costly search strategies. A policy is a mapping from every possible state to the best move from the state.\n\n## AIMA Chapter 5.5 Stochastic Games\n Some adversarial games like backgammon are also stochastic and involve chance with known probabilities. Their game trees have chance nodes between MAX and MIN nodes, and the minimax values are based on the expected value (sum of the value over all outcomes, weighted by the probability of each chance action). In the expectiminimax algorithm this is called expectiminimax value.It's critical that these values are a positive linear transformation of the probability of winning, and not just values with an accurate preference order. We want values to reflect the probability of winning from some state. While minimax takes O(b^m), expectiminimax takes O(b^m * n^m) where\nn is the number of distinct dice rolls. This reflects consideration of all possible dice roll sequences. This means that the possible ways the game could unfold have been massively increased and we need a way to simplify the search. We are already alpha-beta pruning MIN and MAX nodes and we can do something similar for chance nodes. Essentially, you bound the upper and lower range of the utility function so you can upper-bound a chance node's value without examining all of its children. You could also use forward pruning (such as beam search) or skip the evaluation function and use Monte Carlo instead.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n We have considered some simple goal-based agents that clearly differentiate between good and bad states, but now we'll consider decision-theoretic agents that assign a continuous range of values to states. This involves a combination of utility theory and probability theory. The basic principle of decision theory is maximum expected utility (MEU), which is different from performance measure because performance measure gives a score to the historical sequence of states, while MEU estimates the value of the next state. The simplest form of decision theory assumes an episodic environment and thus considers only the immediate outcomes of actions. Every outcome has some probability of occuring and some utility. The expected utility of an action is the average utility of all outcomes weighted by their probability of occurring. MEU says that an agent should maximize the EU, but does not itself say how that should be done.  \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n To understand why averaging expected utility is rational, we can show that MEU follows logically if we write down constraints on rational preferences that a rational agent should have. These constraints are the axioms of utility theory: orderability, transivitity, continuity, substitutability, monotonicity, decomposability. Violations of these axioms is patently irrational. It turns out that an agent can act rationally (meaning consistent with its rational preferences) only by choosing an action that maximizes expected utility, even if it's not doing so explicitly. \n\n## AIMA Chapter 16.3 Utility Functions\n We may want our decision-theoretic agent to make decision that reflect human preferences, and thus we may need to figure out a human's utility function. You can do this by preference elicitation. We'd like a scale for this utility that's bounded by some best and worst value; these are 0 and 1 in a normalized utility. Decision theory is a normative theory, meaning it describes how a rational agent should act, in contrast to descriptive theory which describes how people actually act. Humans have many biases such as the anchoring effect that result in irrational decisions.\n\n## Module 5 Lecture Notes\nFor alpha-beta pruning, MIN updates beta (to minimize it) and compares to MAX's alpha. If beta <= alpha, it stops evaluating because MAX won't follow this path.MAX updates alpha and compares to MIN's beta. Again, if beta <= alpha, it stops and returns that alpha value. Basically, both MAX and MIN keep going as long as beta is bigger than alpha. If we explore all branches of a node, the alpha and beta are the same at the end. If we pruned early, either alpha or beta is the original +/- infinity value. If a child beta is less than the parent alpha, it never gets updated and stays + infinity.The easiest way to encapsulate consistency is this: if a heuristic is consistent, f(n) will always increase monotonically on the path to the goal. The key implication is that once you hit the goal, you know you've hit it with the shortest path. If the heuristic isn't consistent, there could still be a shorter path that you haven't found yet.Here's an example: say that A is actually 10 away from goal, and B is 8 away. And say that h(A) is 9 and h(B) is 8. This heuristic is admissible because it didn't overestimate the real distances, but it's not consistent. Here's why. The step cost from A to B is 2, so the sum of that cost and h(B) is 2+8=10. But h(A) is only 9. It's logically inconsistent that the estimated distance from A is less than the path from A to B plus the estimate from B. To be consistent, the estimate from A would have to be greater than or equal to the cost of going from A to B plus B's estimated distance from the goal.For an optimal solution, TreeSearch-A* admissible heuristic is sufficient, but \n\\GraphSearch A* requires a consistent heuristic.\n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Imperfect information** - partially observable\n* **Move** - action\n* **Position** - state\n* **Transition model** - rules for the state that results from taking some action from some state\n* **Terminal test** - True when game is over, otherwise False\n* **Utility function** - defines final numeric value for a player in terminal state\n* **Ply** - one move by one player\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 = \"\"\" In search problems that specify states as black boxes with \\\n",
        "no internal structure, we need domain-specific code to find transitions between \\\n",
        "states. CSPs give structure to states and thus enable us to use general-purpose \\\n",
        "algorithms and heuristics to solve these problems. When each state is a set of \\\n",
        "variables with value assignments, this is called a factored representation. The \\\n",
        "constraint on two variables may be defined by a relation that could be implicit \\\n",
        "or explicit. An implicit relation describes the relationship as something like \\\n",
        "x < y, while an explicit relation would have sets of allowable assignments to \\\n",
        "x and y from their domains. So basically a relation is a way of expressing a \\\n",
        "constraint. CSPs may be represented with a constraint graph in which nodes represent \\\n",
        "variables and edges represent constraints between the variables. CSPs can prune \\\n",
        "large swaths of the search space by discarding further refinements of a partial \\\n",
        "assignment once it has violated a constraint. Precedence constraints specify that \\\n",
        "one task must occur before another; in this case the variables represent start \\\n",
        "times and the relation could be an inequality. Domains can be finite or infinite, \\\n",
        "discrete or continuous. Discrete and finite is the easiest kind to solve. There are \\\n",
        "special algorithms for CSPs with linear constraints on integer variables, but \\\n",
        "problems with nonlinear constraints are undecidable. Linear programming problems \\\n",
        "are CSPs with continous domains where constraints must be linear equalities or \\\n",
        "inequalities. A unary constraint restricts the value of a single variable while \\\n",
        "a binary constraint relates two variables. A global constraint involves an arbitratry \\\n",
        "number of variables but not necessarily all of them. Preference constraints indicate \\\n",
        "preferred solutions and can be encoded as costs on individual variable assignments. \\\n",
        "This kind of CSP would be solved with optimization search methods and is called \\\n",
        "a constrained optimization problem.\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"Constraint propagation uses inference to reduce the domain of \\\n",
        "a variable, which may have a domino effect on the domains of other variables. \\\n",
        "AC-3 enforces arc consistency by maintaining a queue of arcs initialized to all \\\n",
        "arcs (binary constraints) in the CSP. If there is no satisfying assignment for \\\n",
        "a value in the tail to some value in the head, that value is removed from the \\\n",
        "tail and its neighbors are added back to the queue, since now their domains may \\\n",
        "need to be updated again. If any domain is revised down to nothing, we know there \\\n",
        "is no consistent solution. Path consistency enforces constraints on triples of \\\n",
        "variables. Sometimes enforcing a higher-order constraint such as All Diff is more \\\n",
        "effecive than enforcing its translation into binary constraints. One important \\\n",
        "higher-order constraint is the resource (at most) constraint. If the sum of the \\\n",
        "assignments to a set of variables exceeds some bound, the resource constraint is \\\n",
        "violated. We can also check for bounds consistency with bounds propagation.\"\"\"\n",
        "chapter6_3 = \"\"\" In CSP backtracking search we only consider a single variable at each node \\\n",
        "in the search tree because CSP problems are commutative: it doesn't matter which \\\n",
        "order we assign the variables in. Backtracking search is a common way to solve CSPs. \\\n",
        "The basic algorithm is to choose an unassigned variable and try to extend that assignment \\\n",
        "into a solution via a recursive call. If the assignment fails, we try the next value \\\n",
        "in the domain for that variable, and so on. This can still take awhile if the \\\n",
        "problematic assignment was early on and we backtrack in a depth-first fashion, so \\\n",
        "it can be improved with domain-independent heuristics. When we select an \\\n",
        "unassigned variable, it's best to choose that with the minimum remaining values \\\n",
        "(this is the MRV heuristic). When we select a value from a variable's domain, \\\n",
        "we may want to choose the least-constraining value. Both of these take time \\\n",
        "but could speed things up if they lead to more efficient backtracking. It \\\n",
        "also greatly improves efficiency to interleave search and inference. Each time \\\n",
        "we assign a value to a variable, we can make an inference about the domains of \\\n",
        "other variables. A simple form of this kind of inference is forward-checking: \\\n",
        "when X is assigned a value, it establishes arc consistency for all neighbors of \n",
        "X, such that X is the head, so values are deleted from any tail (any neighbor Y) \\\n",
        "if they are inconsistent with the value picked for X. Even more powerful is the \n",
        "Maintain Arc Consistency algorithm, which calls AC-3 after each assignment, but \\\n",
        "the queue of arcs is initialized only to the neighbors of X rather than all arcs. \\\n",
        "We can change the way we backtrack too. The default is chronological backtracking: \\\n",
        "just go back to the most recent assignment. This can be improved upon by maintaining \\\n",
        "a conflict set and doing conflict-directed backjumping.\"\"\"\n",
        "chapter6_4 = \"\"\"CSPs can also be solved using local search, which actually starts \\\n",
        "with a complete assignment to all the variables and then changes the value of one \\\n",
        "variable at a time using the min-conflicts heuristic: select the value that results \\\n",
        "in the minimum number of conflicts. This can be surprisingly effective and even \\\n",
        "works on the n-queens problem roughly independent of problem size! Constraint \\\n",
        "weighting and tabu search are other forms of local search. Local search is also \\\n",
        "great for something like repairing an airport schedule with a minimum number of \\\n",
        "changes because it can start from the current assignment, whereas backtracking \\\n",
        "search would start from scratch and might arrive at a very different solution.\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"One way to find solutions faster is to decompose a problem into \\\n",
        "independent subproblems, which can be identified as the connected components in \\\n",
        "the constraint graph. This can have massive time reductions but unfortunately \\\n",
        "completely independent subproblems are rare. Other graph structures can have \\\n",
        "benefits too. Any tree-structured CSP can be solved in time linear in the number \\\n",
        "of variables. If the variables are ordered as a topological sort with directional \\\n",
        "arc consistency, you can simply walk through them from the root and assign as you \\\n",
        "go. Sometimes it is possible to reduce other graphs to trees by removing nodes \\\n",
        "or collapsing nodes together. A cycle cutset is some subset of the nodes whose \\\n",
        "removal turns the graph into a tree. The algorithm for this transformation is called \\\n",
        "cutset conditioning. Another strategy for turning a graph into a tree is tree \\\n",
        "decomposition. We can also reduce the search space by a factor of d! by breaking \\\n",
        "value symmetry by introducing a symmetry-breaking constraint so that we don't \\\n",
        "explore all permutations of a satisfying assignment.\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 210,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1187
        },
        "outputId": "16ddf6cd-b6b4-42bd-8533-0bd086f71940"
      },
      "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": 211,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n In search problems that specify states as black boxes with no internal structure, we need domain-specific code to find transitions between states. CSPs give structure to states and thus enable us to use general-purpose algorithms and heuristics to solve these problems. When each state is a set of variables with value assignments, this is called a factored representation. The constraint on two variables may be defined by a relation that could be implicit or explicit. An implicit relation describes the relationship as something like x < y, while an explicit relation would have sets of allowable assignments to x and y from their domains. So basically a relation is a way of expressing a constraint. CSPs may be represented with a constraint graph in which nodes represent variables and edges represent constraints between the variables. CSPs can prune large swaths of the search space by discarding further refinements of a partial assignment once it has violated a constraint. Precedence constraints specify that one task must occur before another; in this case the variables represent start times and the relation could be an inequality. Domains can be finite or infinite, discrete or continuous. Discrete and finite is the easiest kind to solve. There are special algorithms for CSPs with linear constraints on integer variables, but problems with nonlinear constraints are undecidable. Linear programming problems are CSPs with continous domains where constraints must be linear equalities or inequalities. A unary constraint restricts the value of a single variable while a binary constraint relates two variables. A global constraint involves an arbitratry number of variables but not necessarily all of them. Preference constraints indicate preferred solutions and can be encoded as costs on individual variable assignments. This kind of CSP would be solved with optimization search methods and is called a constrained optimization problem.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nConstraint propagation uses inference to reduce the domain of a variable, which may have a domino effect on the domains of other variables. AC-3 enforces arc consistency by maintaining a queue of arcs initialized to all arcs (binary constraints) in the CSP. If there is no satisfying assignment for a value in the tail to some value in the head, that value is removed from the tail and its neighbors are added back to the queue, since now their domains may need to be updated again. If any domain is revised down to nothing, we know there is no consistent solution. Path consistency enforces constraints on triples of variables. Sometimes enforcing a higher-order constraint such as All Diff is more effecive than enforcing its translation into binary constraints. One important higher-order constraint is the resource (at most) constraint. If the sum of the assignments to a set of variables exceeds some bound, the resource constraint is violated. We can also check for bounds consistency with bounds propagation.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n In CSP backtracking search we only consider a single variable at each node in the search tree because CSP problems are commutative: it doesn't matter which order we assign the variables in. Backtracking search is a common way to solve CSPs. The basic algorithm is to choose an unassigned variable and try to extend that assignment into a solution via a recursive call. If the assignment fails, we try the next value in the domain for that variable, and so on. This can still take awhile if the problematic assignment was early on and we backtrack in a depth-first fashion, so it can be improved with domain-independent heuristics. When we select an unassigned variable, it's best to choose that with the minimum remaining values (this is the MRV heuristic). When we select a value from a variable's domain, we may want to choose the least-constraining value. Both of these take time but could speed things up if they lead to more efficient backtracking. It also greatly improves efficiency to interleave search and inference. Each time we assign a value to a variable, we can make an inference about the domains of other variables. A simple form of this kind of inference is forward-checking: when X is assigned a value, it establishes arc consistency for all neighbors of \nX, such that X is the head, so values are deleted from any tail (any neighbor Y) if they are inconsistent with the value picked for X. Even more powerful is the \nMaintain Arc Consistency algorithm, which calls AC-3 after each assignment, but the queue of arcs is initialized only to the neighbors of X rather than all arcs. We can change the way we backtrack too. The default is chronological backtracking: just go back to the most recent assignment. This can be improved upon by maintaining a conflict set and doing conflict-directed backjumping.\n\n## AIMA Chapter 6.4 Local Search for CSPs\nCSPs can also be solved using local search, which actually starts with a complete assignment to all the variables and then changes the value of one variable at a time using the min-conflicts heuristic: select the value that results in the minimum number of conflicts. This can be surprisingly effective and even works on the n-queens problem roughly independent of problem size! Constraint weighting and tabu search are other forms of local search. Local search is also great for something like repairing an airport schedule with a minimum number of changes because it can start from the current assignment, whereas backtracking search would start from scratch and might arrive at a very different solution.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\nOne way to find solutions faster is to decompose a problem into independent subproblems, which can be identified as the connected components in the constraint graph. This can have massive time reductions but unfortunately completely independent subproblems are rare. Other graph structures can have benefits too. Any tree-structured CSP can be solved in time linear in the number of variables. If the variables are ordered as a topological sort with directional arc consistency, you can simply walk through them from the root and assign as you go. Sometimes it is possible to reduce other graphs to trees by removing nodes or collapsing nodes together. A cycle cutset is some subset of the nodes whose removal turns the graph into a tree. The algorithm for this transformation is called cutset conditioning. Another strategy for turning a graph into a tree is tree decomposition. We can also reduce the search space by a factor of d! by breaking value symmetry by introducing a symmetry-breaking constraint so that we don't explore all permutations of a satisfying assignment.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Knowledge-based agents reason over an internal representation of \\\n",
        "the world. Logic is actually a class of representations. This ability to store, \\ \n",
        "update, and derive general facts is powerful; these algorithms can adapt, learn quickly, \\\n",
        "and function independently of the domain in which they are applied. In contrast, the \\\n",
        "scope and application of problem-solving agents' abstractions are far more limited. \\\n",
        "A knowledge base consists of a set of assertions about the world, \\\n",
        "which are called sentences. These sentences are written in a specific knowledge \\\n",
        "representation language that allows for logical operations. Axioms are the given \\\n",
        "assertions and every other sentence is derived from them. You TELL a KB new sentences \\\n",
        "and ASK whether particular sentences are inferrable from its contents. Unlike other \\\n",
        "agents we've seen, KB agents operate at the knowledge level rather than the implementation \\\n",
        "level: their behavior is determined only by their specified knowledge and goals. \\\n",
        "The procedural approach directly encodes behaviors, while the declarative approach \\\n",
        "allows behavior to follow from the knowledge. It's often optimal to combine these. \"\"\"\n",
        "chapter7_2 = \"\"\" Agents operate in task environments, which we define with PEAS: \\\n",
        "Performance Measure, Environment, Actuators, Sensors. In the Wumpus World the agent \\\n",
        "at first knows only the rules of the environment but cannot observe most of it. \\\n",
        "It begins expanding its KB via the percepts it receives and the inferences it can \\\n",
        "then make. Given the rules of logic, these inferences are guaranteed correct as long \\\n",
        "as its KB and the information it receives are accurate. \"\"\"\n",
        "chapter7_3 = \"\"\" Every knowledge representation language has a syntax that specifies \\\n",
        "well-formed sentences so they can be systematically operated on, as with arithmetic. \\\n",
        "The semantics of the language define the truth or meaning of the sentences relative \\\n",
        "to a particular model of the world. A model satisfies a sentence if that sentence is \\\n",
        "true in that model. Sentence A entails sentence B if B is true in every model in which \\\n",
        "A is true, i.e. if M(A) is a subset of M(B). Given this definition, there could be \\\n",
        "models in which B is true but A is not. Since a KB can be thought of as a single \\\n",
        "sentence, the KB itself can also be true or \\\n",
        "false with respect to some model. In fact, if we have abstracted the environment into \\\n",
        "particular variables, the set of all possible models would contain all possible \\ \n",
        "combinations of assignments to those variables. Inferring can \\\n",
        "be a process of ruling out possibilities and narrowing things down as you determine \\\n",
        "which models contradict the KB and which possibilities remain in the consistent models. \\\n",
        "You can ASK whether A is true by model-checking in this way: is M(KB) a subset of M(A)?. \"\"\"\n",
        "chapter7_4 = \"\"\" Propositional logic is a particular knowledge representation language. \\\n",
        "Its syntax enables an algorithm for making logical inferences. This implements the \\\n",
        "notion of logical entailemnt. In PL an atomic sentence is a single proposition symbol that can \\\n",
        "be true or false. We use logical connectives to combine these and produce complex sentences. \\\n",
        "A literal is either a positive or negated atomic sentence. The five most common \\\n",
        "connectives are: negation, conjunction, disjunction, implication, and biconditional. \\\n",
        "BNF Grammar specifies how these connectives operate on proposition symbols and gives rules \\\n",
        "for operator precedence to resolve ambiguity. \\\n",
        "A model is essentially a setting of the truth value for every \\\n",
        "proposition symbol. PL's semantics tell us the rules for when complex sentences \\\n",
        "can be considered true or false in a model. A truth table is one way to express these semantics. \\\n",
        "To construct a knowledge base, it helps to start with the \\\n",
        "immutable aspects of the world and then incorporate mutable ones via percepts.\\\n",
        "Once the KB is constructed, we use logical inference to check \\\n",
        "whether it entails some sentence A. One way to do this is with model-checking: \\\n",
        "enumerate all models, and see if A is true in every model where KB is true. This \\\n",
        "method is sound and complete but it takes exponential time: for n symbols, there are \\\n",
        "2^n possible models. This is true for every known inference (entailment) algorithm \\\n",
        "for propositional logic; they are co-NP-complete. There are other more efficient algorithms. \\\n",
        "Theorem proving is a different method of entailment. It does not \\\n",
        "require consulting models. We use some new ideas here. If two sentences entail \\\n",
        "each other, they are logically equivalent. A sentence is valid if it's true in all \\\n",
        "models. The Deduction Theorem states that A entails B iff (A implies B) is valid. \\\n",
        "In contrast, A is satisfiable if it's true in SOME model, not necessarily all. \\\n",
        "Determining satisfiability (the SAT problem) is NP-complete, so many problems can \\\n",
        "be reduced to this form. Satisfiability can actually be used to prove validity: \\\n",
        "if (A and not B) is unsatisfiable, it must be true in all models, and therefore is valid.\\\n",
        "This is essentially a proof by contradiction. Distributivity: A and (B or C) = \\\n",
        "(A and B) or (A and C). A or (B and C) = (A or B) and (A or C).\\\n",
        "A proof is just a chain of conclusions that leads to a desired \\\n",
        "goal. We may use logical equivalence to transform sentences as we move through a \\\n",
        "proof. One example is implication elimination: (A implies B) equals ((not A) or B). \\\n",
        "We derive proofs using inference rules. A common inference rule is Modus Ponens: \\\n",
        "given that A implies B and given A, we can infer B. Another rule is And-Elimination: \\\n",
        "from a conjunction, any of the conjuncts can be inferred.\"\"\"\n",
        "chapter7_5 = \"\"\" We can actually use search \\\n",
        "algorithms to find a proof, i.e. a path from initial state (KB) to goal state (sentence \\\n",
        "we want to prove). The actions are the inference rules, and the results are the \\\n",
        "inferences in the bottom half of each rule that we add to the KB. This can be way \\\n",
        "more efficient than model checking because it ignores irrelevant propositions.\\\n",
        "Logical systems are monotonic, meaning that the KB can only increase as new sentences \\\n",
        "are added; no previous sentences can be changed. Human logic is different because \\\n",
        "we change our minds.\\\n",
        "Theorem proving is sound but is only complete if the inference \\\n",
        "rules are adequate. It's possible for a search algorithm to be complete, assuming \\\n",
        "the goal is reachable, but if the inference rules can't provide a path to that goal \\\n",
        "then the inference algorithm is incomplete despite the completeness of the search \\\n",
        "algorithm. The resolution rule ensures that any inference algorithm is complete \\\n",
        "if coupled with a complete search algorithm. The resolution rule essentially says \\\n",
        "that (A and notA) resolves to the empty clause. If a disjunction of literals contains \\\n",
        "complementary (one negates the other) literals, the resolvent will not contain those \\\n",
        "complementary literals. Factoring removes multiple copies of literals: A or A is just A. \\\n",
        "To use the resolution rule we must express all sentences as clauses (disjunctions of \\\n",
        "literals), aka CNF: convert biconditionals to conjunctions, then do implication \\\n",
        "elimination, then move negation inwards with DeMorgan, then apply distribution to \\\n",
        "get rid of nested AND/OR operators. The resolution algorithm proves that KB entails \\\n",
        "A by proving that (KB and notA) is unsatisfiable. It uses proof by contradiction: \\\n",
        "the KB is converted to CNF and the resolution rule is applied to these clauses \\\n",
        "until either no new clauses can be added to KB (it does not entail A) or two \\\n",
        "clauses resolves to the empty clause (a contradiction: KB entails A). \\\n",
        "We can speed up the resolution algorithm if we're able to express \\\n",
        "all clauses as definite clauses (disjunction of literals in which exactly 1 is positive) \\\n",
        " or horn clauses (at most 1 is positive, so 0 or 1). Goal clauses have no positive literals. \\\n",
        " Inference with horn clauses can be done with forward-chaining or backward-chaining \\\n",
        " algorithms in time linear with size of KB. \\\n",
        " Forward-chaining determines if query Q is entailed by KB. \\\n",
        "Process: if all premises of an implication are known, its conclusion is added to KB. \\\n",
        "Continues until Q is added or no new inferences possible. It's sound and complete. \\\n",
        "Example of data-driven reasoning, moving forward from what is known. Backward-chaining \\\n",
        "works backward from query Q. If Q known, done. If not, find all implications in \\\n",
        "KB whose conclusion is Q. If it can prove all premises in any of those (using \\\n",
        "backward chaining), then Q is true. Example of goal-directed reasoning. Can be much \\\n",
        "less than linear in size of KB. \"\"\"\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" We use rules of logical equivalence to translate \\\n",
        "sentences into CNF form. Follow these steps. 1: Biconditional elimination. 2: \\\n",
        " Implication elimination. 3: Move negation inwards by eliminating double negation \\\n",
        " and using DeMorgan's rules. 4: Distribute ⋁ over ⋀ wherever possible to get rid \\\n",
        " of nested ⋁ and ⋀ operators. Basically, keep replacing P ⋁ (Q ⋀ R) with \\\n",
        "  (P ⋁ Q) ⋀ (P ⋁ R).\\\n",
        "  Example: \n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Distributivity of ⋁ over ⋀\" : \"((𝛂 ⋁ β) ⋀ ɣ) ≡ ((𝛂 ⋁ β) ⋀ (𝛂 ⋁ ɣ)))\", \n",
        "\"Distributivity of ⋀ over ⋁\" : \"((𝛂 ⋀ β) ⋁ ɣ) ≡ ((𝛂 ⋀ β) ⋁ (𝛂 ⋀ ɣ)))\",\n",
        "\"Implication elimination\" : \"(𝛂 ⟹ β) ≡ (¬𝛂 ⋁ β)\",\n",
        "\"DeMorgan1\" : \" ¬(𝛂 ⋀ β) ≡ (¬𝛂 ⋁ ¬β)\",\n",
        "\"DeMorgan2\" : \"¬(𝛂 ⋁ β) ≡ (¬𝛂 ⋀ ¬β)\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 212,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1459
        },
        "outputId": "24cc909c-8702-4e50-c090-90a72236cc39"
      },
      "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": 213,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge-based agents reason over an internal representation of the world. Logic is actually a class of representations. This ability to store, \\ \nupdate, and derive general facts is powerful; these algorithms can adapt, learn quickly, and function independently of the domain in which they are applied. In contrast, the scope and application of problem-solving agents' abstractions are far more limited. A knowledge base consists of a set of assertions about the world, which are called sentences. These sentences are written in a specific knowledge representation language that allows for logical operations. Axioms are the given assertions and every other sentence is derived from them. You TELL a KB new sentences and ASK whether particular sentences are inferrable from its contents. Unlike other agents we've seen, KB agents operate at the knowledge level rather than the implementation level: their behavior is determined only by their specified knowledge and goals. The procedural approach directly encodes behaviors, while the declarative approach allows behavior to follow from the knowledge. It's often optimal to combine these. \n\n## AIMA Chapter 7.2 The Wumpus World\n Agents operate in task environments, which we define with PEAS: Performance Measure, Environment, Actuators, Sensors. In the Wumpus World the agent at first knows only the rules of the environment but cannot observe most of it. It begins expanding its KB via the percepts it receives and the inferences it can then make. Given the rules of logic, these inferences are guaranteed correct as long as its KB and the information it receives are accurate. \n\n## AIMA Chapter 7.3 Logic\n Every knowledge representation language has a syntax that specifies well-formed sentences so they can be systematically operated on, as with arithmetic. The semantics of the language define the truth or meaning of the sentences relative to a particular model of the world. A model satisfies a sentence if that sentence is true in that model. Sentence A entails sentence B if B is true in every model in which A is true, i.e. if M(A) is a subset of M(B). Given this definition, there could be models in which B is true but A is not. Since a KB can be thought of as a single sentence, the KB itself can also be true or false with respect to some model. In fact, if we have abstracted the environment into particular variables, the set of all possible models would contain all possible \\ \ncombinations of assignments to those variables. Inferring can be a process of ruling out possibilities and narrowing things down as you determine which models contradict the KB and which possibilities remain in the consistent models. You can ASK whether A is true by model-checking in this way: is M(KB) a subset of M(A)?. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Propositional logic is a particular knowledge representation language. Its syntax enables an algorithm for making logical inferences. This implements the notion of logical entailemnt. In PL an atomic sentence is a single proposition symbol that can be true or false. We use logical connectives to combine these and produce complex sentences. A literal is either a positive or negated atomic sentence. The five most common connectives are: negation, conjunction, disjunction, implication, and biconditional. BNF Grammar specifies how these connectives operate on proposition symbols and gives rules for operator precedence to resolve ambiguity. A model is essentially a setting of the truth value for every proposition symbol. PL's semantics tell us the rules for when complex sentences can be considered true or false in a model. A truth table is one way to express these semantics. To construct a knowledge base, it helps to start with the immutable aspects of the world and then incorporate mutable ones via percepts.Once the KB is constructed, we use logical inference to check whether it entails some sentence A. One way to do this is with model-checking: enumerate all models, and see if A is true in every model where KB is true. This method is sound and complete but it takes exponential time: for n symbols, there are 2^n possible models. This is true for every known inference (entailment) algorithm for propositional logic; they are co-NP-complete. There are other more efficient algorithms. Theorem proving is a different method of entailment. It does not require consulting models. We use some new ideas here. If two sentences entail each other, they are logically equivalent. A sentence is valid if it's true in all models. The Deduction Theorem states that A entails B iff (A implies B) is valid. In contrast, A is satisfiable if it's true in SOME model, not necessarily all. Determining satisfiability (the SAT problem) is NP-complete, so many problems can be reduced to this form. Satisfiability can actually be used to prove validity: if (A and not B) is unsatisfiable, it must be true in all models, and therefore is valid.This is essentially a proof by contradiction. Distributivity: A and (B or C) = (A and B) or (A and C). A or (B and C) = (A or B) and (A or C).A proof is just a chain of conclusions that leads to a desired goal. We may use logical equivalence to transform sentences as we move through a proof. One example is implication elimination: (A implies B) equals ((not A) or B). We derive proofs using inference rules. A common inference rule is Modus Ponens: given that A implies B and given A, we can infer B. Another rule is And-Elimination: from a conjunction, any of the conjuncts can be inferred.\n\n## AIMA 7.5 Propositional Theorem Proving\n We can actually use search algorithms to find a proof, i.e. a path from initial state (KB) to goal state (sentence we want to prove). The actions are the inference rules, and the results are the inferences in the bottom half of each rule that we add to the KB. This can be way more efficient than model checking because it ignores irrelevant propositions.Logical systems are monotonic, meaning that the KB can only increase as new sentences are added; no previous sentences can be changed. Human logic is different because we change our minds.Theorem proving is sound but is only complete if the inference rules are adequate. It's possible for a search algorithm to be complete, assuming the goal is reachable, but if the inference rules can't provide a path to that goal then the inference algorithm is incomplete despite the completeness of the search algorithm. The resolution rule ensures that any inference algorithm is complete if coupled with a complete search algorithm. The resolution rule essentially says that (A and notA) resolves to the empty clause. If a disjunction of literals contains complementary (one negates the other) literals, the resolvent will not contain those complementary literals. Factoring removes multiple copies of literals: A or A is just A. To use the resolution rule we must express all sentences as clauses (disjunctions of literals), aka CNF: convert biconditionals to conjunctions, then do implication elimination, then move negation inwards with DeMorgan, then apply distribution to get rid of nested AND/OR operators. The resolution algorithm proves that KB entails A by proving that (KB and notA) is unsatisfiable. It uses proof by contradiction: the KB is converted to CNF and the resolution rule is applied to these clauses until either no new clauses can be added to KB (it does not entail A) or two clauses resolves to the empty clause (a contradiction: KB entails A). We can speed up the resolution algorithm if we're able to express all clauses as definite clauses (disjunction of literals in which exactly 1 is positive)  or horn clauses (at most 1 is positive, so 0 or 1). Goal clauses have no positive literals.  Inference with horn clauses can be done with forward-chaining or backward-chaining  algorithms in time linear with size of KB.  Forward-chaining determines if query Q is entailed by KB. Process: if all premises of an implication are known, its conclusion is added to KB. Continues until Q is added or no new inferences possible. It's sound and complete. Example of data-driven reasoning, moving forward from what is known. Backward-chaining works backward from query Q. If Q known, done. If not, find all implications in KB whose conclusion is Q. If it can prove all premises in any of those (using backward chaining), then Q is true. Example of goal-directed reasoning. Can be much less than linear in size of KB. \n\n## Module 7 Lecture Notes\n We use rules of logical equivalence to translate sentences into CNF form. Follow these steps. 1: Biconditional elimination. 2:  Implication elimination. 3: Move negation inwards by eliminating double negation  and using DeMorgan's rules. 4: Distribute ⋁ over ⋀ wherever possible to get rid  of nested ⋁ and ⋀ operators. Basically, keep replacing P ⋁ (Q ⋀ R) with   (P ⋁ Q) ⋀ (P ⋁ R).  Example: \n \n\n## Module 7 Definitions\n* **Distributivity of ⋁ over ⋀** - ((𝛂 ⋁ β) ⋀ ɣ) ≡ ((𝛂 ⋁ β) ⋀ (𝛂 ⋁ ɣ)))\n* **Distributivity of ⋀ over ⋁** - ((𝛂 ⋀ β) ⋁ ɣ) ≡ ((𝛂 ⋀ β) ⋁ (𝛂 ⋀ ɣ)))\n* **Implication elimination** - (𝛂 ⟹ β) ≡ (¬𝛂 ⋁ β)\n* **Demorgan1** -  ¬(𝛂 ⋀ β) ≡ (¬𝛂 ⋁ ¬β)\n* **Demorgan2** - ¬(𝛂 ⋁ β) ≡ (¬𝛂 ⋀ ¬β)\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": 7395
        },
        "id": "T3cm1WV542_a",
        "outputId": "d30b9f4f-60fa-4797-aba4-219690f76d60"
      },
      "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": 214,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \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 Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\nThe goal of a rational agent is to act rationally (not just think rationally, and not to imitate humans). An agent perceives through sensors and acts through actuators. An agent function maps a sequence of percept vectors to an action. An agent program is not the same as the function, which is the “what’; program is the “how”, the actual program that runs on the physical architecture of the agent. To be rational is to maximize the expected value of the performance measure given info available. Rationality is not omniscience so success is not guaranteed. The task environment is the problem specification for which the agent is a solution. It's defined by PEAS: Performance measure, Environment, Actuators, Sensors. Types of environments: -- fully observable (chess) VS partially observable (taxi, poker, medical diagnosis) --deterministic (chess, sudoku) VS nondeterministic VS stochastic (wheel of fortune, backgammon, probabilities are known) --episodic (one thing at a time, not concerned about a sequence, i.e. image analysis or part-picking robot) VS sequential (results depend on a sequence of events: chess, taxi, backgammon)--static (chess) VS dynamic (taxi, does environment change while you’re deciding what to do)\n--discrete (chess) VS continuous (taxi, image analysis) --single agent VS multiagent How we do know if something is part of environment or is another agent? If it has its own performance measure, then it's another agent. A reflex agent chooses an action based on the current percept only and ignores the rest of the percept history. A problem-solving agent must plan ahead and do search.\n\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n You can concatenate lists using the + operator.You can’t concatenate dictionaries that way. Trying to remove something that isn’t present in a set will cause a key error. You can’t reassign items in a tuple, but if the item is a list or dictionary, you can access that item, and if mutable, you can change it. The slice operation returns a new list. Strings do not support item assignment, so you can't replace a char in a string with a different char just by reassigning it.\n \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n A problem-solving agent tries to find a path to the goal state. This problem is called search. Every state is atomic, meaning that it has no internal structure. What you see is all there is. The search can be uninformed or informed, depending on whether it knows anything about distance from the goal. To search successfully, we need to formulate the search problem: what is the goal, how are we abstracting the environment into states and actions, what kind of search will we use to find a solution. Simpler search problems involve open-loop systems in which the environment is essentially fixed and once the agent has come up with a solution, it can execute it without taking in any new percepts. Closed-loop would keep paying attention and the solution would be a branching strategy that depends on percepts. The action cost function helps you determine the cost of a path as you move along. Some simple problems make every action cost the same (such as 1). You could give some actions a higher cost to try to influence behavior. An optimal solution is just a path to the goal that has the lowest cost among all solutions.  \n \n\n## AIMA Chapter 3.2 Example Problems\n Standardized problems contrast with real world problems and are much simpler, but they're helpful for illustrating search techniques and establishing benchmarks for researchers to evaluate algorithm efficiency. Some real world problems solved with search are protein design (an assembly problem), automatic assembly sequencing of complex objects (as in factories), and route-finding in networks, military operations, and airline travel. \n\n## AIMA Chapter 3.3 Search Algorithms\n A search tree is not the same thing as a state space graph. The state space graph contains all possible states and the transitions between them (an edge between two states indicates an action that produces this transtion), but a search tree describes paths between the states. Each node in the search tree is not a state but rather a path. It could store the path explicitly or allow for path reconstruction by storing its parent. To expand a node is to consider all possible actions from that node, which in turn create different successor/child nodes. A node is reached if it has been generated, but it is not expanded unless its successors have been generated. The frontier contains unexpanded nodes from which we choose the next node for exploration depending on our search strategy. Best-first search refers to the general approach of picking the node from the frontier with the minimum value for some evaluation function f(n). This kind of search uses a priority queue which always pops off the node with minimum f(n). Breadth-First Search uses a FIFO queue and DFS uses LIFO (a stack). Redundant paths are possible in problems where the same state can be reached via cycles or via a worse path than has already been found. To avoid this you can track reached states in a lookup table. This transforms the tree-like search into a graph search. This takes memory so if the problem doesn't require it (if certain constraints rule out redundancy, better not to use it. A compromise is to rule out short cycles but not all redundant paths. This can be done in constant time by only checking a few nodes up the chain. To be complete, a search strategy must be systematic.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uninformed search strategies have no idea how close the goal is. BFS is uninformed, but since it's systematic, it's complete even on infinite spaces, unlike DFS which is complete only in finite spaces. A nice feature of BFS is that it finds the shortest path to the goal assuming all actions have the same cost. It actions have different costs, then the path with fewest edges is not necessarily the cost-optimal path. BFS space/time complexity are both O(b^d). Exponential runtimes like this make any but the smallest instances intractable, so generally uninformed search only works for very small instances. While BFS moves outward in waves of uniform depth, uniform-cost search moves in waves of uniform path-cost. This is a type of best-first search where f(n) is the path-cost. This is better than BFS if actions have different costs. Uniform-cost search is complete and cost-optimal but can take even longer than BFS if it ends up exploring large trees that are cheap but fruitless before gettting to higher-cost but useful actions. DFS uses much less memory but is not cost-optimal or complete. However, iterative deepening search can be complete and cost-optimal if action costs are identical. \n\n## Module 3 Lecture Notes\nSearch problems involve: states, actions, performance measure. The solution to search problem is sequence of actions that form a path to the goal state. The solution may be a fixed sequence for a simpler environment or a branching strategy for a less observable or predictable environment. The transition model specifies which actions are available in a state and how they will change to a new state. The path cost must be additive and reflect performance measure. The solution is optimal if no other solution has lower path cost. The way you formulate a search problem greatly affects its efficiency. Consider which properties matter (for a state), what actions are possible, and how to represent them. The state space is the set of all states reachable from initial state by any sequence of actions. The frontier is set of all states available for expanding from current state; to expand a state is to apply legal action to that state. Tree search is a basic kind of search algorithm. The root is the initial state. Unlike graphs, tree search treats different paths to same state as unique, which can turn a linear problem into an exponential one. Using graphs instead can remedy this. A node is more than just a state. It can have other information such as parent node, action, depth, path cost. Graph search algorithms primarily differ from tree search in that graphs keep track of nodes that have already been explored and only expand nodes that aren’t in the frontier or the explored set. The search strategy is simply the order of tree expansion (LIFO, FIFO, priority).\\ \nUniform-cost search is guaranteed to find an optimal solution, and Dijkstra's algorithm is just uniform-cost search without a goal. \n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Complete** - guaranteed to find a solution or report failure\n* **Optimal** - finds solution with the lowest path cost\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed search strategies are informed with hints about the distance to the goal. The hint is a heuristic function h(n). Greedy best-first search uses only h(n) and nothing else, i.e. f(n) = h(n). The most common informed search strategy is A* Search, for which f(n) = g(n) + h(n), i.e. it considers the path-cost to a node and the estimated distance to the goal from that node. A* is complete but it's only optimal if the heuristic is admissible. An admissible heuristic is optimistic: it never overestimates the real distance to the goal. Even better if the heuristic is consistent, which means that f(n) values will always increase monotonically along a path to the goal, so the first time the goal is reached, we know there is no shorter path yet to be found. In other words, if the heuristic is consistent, we always reach a state for the first time via the optimal path. Consistent implies admissible but the reverse is not always true. If the heuristic is not consistent, you can't declare victory the first time you reach the goal; there may be a shorter path from a node that hasn't been expanded yet. Sometimes it's worth it to use an inadmissible heuristic; it may return a non-optimal solution, but could be way faster. If optimality is less important than speed, this might be a good approach. Weighted-A* Search is an example; it weights h(n) more heavily to focus the search toward the goal without totally ignoring path costs. There are other ways of balancing or defining priorities: bounded suboptimal search looks for a solution within a constant factor of the optimal cost; bounded-cost wants a solution less than some constant; unbounded-cost wants a solution of any cost as fast as possible. A* 's main problem is the large memory requirement of storing nodes both in the reached table and on the frontier. Some modified algorithms offer ways to reduce memory requirements. IDA* (iterative-deeping A*) is similar to that for DFS but uses f(n) as the cutoff and increases it in each iteration to the next lowest f(n) not visited before. Only efficient if f-costs are integers, otherwise might expand by one state each time. Other options are Recursive Best First Search (RBFS), Memory-Bounded A* (MA*), and Simplified MA* (SMA*). \n\n## AIMA Chapter 3.6 Heuristic Functions\n If one heuristic dominates another, it is more efficient. h1 dominates h2 if for any node h1(n) > h2(n). How do people come up with heuristic functions? They might relax the original problem or derive them from the solution cost of a subproblem. Pattern databases store solution costs for subproblems; you can obtain the h(n) for a node by looking up its state in the database. You could also precompute landmarks, which is a lot of computation up front, but it's amortized over many future search requests. Google Maps does this. Heuristics can also be learned from experience via machine learning; this might make use of certain features of a state that are relevant to predicting its heuristic value.\n\n## Module 4 Lecture Notes\nSearch problems involve: states, actions, performance measure. The solution to search problem is sequence of actions that form a path to the goal state. The solution may be a fixed sequence for a simpler environment or a branching strategy for a less observable or predictable environment. The transition model specifies which actions are available in a state and how they will change to a new state. The path cost must be additive and reflect performance measure. The solution is optimal if no other solution has lower path cost. The way you formulate a search problem greatly affects its efficiency. Consider which properties matter (for a state), what actions are possible, and how to represent them. The state space is the set of all states reachable from initial state by any sequence of actions. The frontier is set of all states available for expanding from current state; to expand a state is to apply legal action to that state. Tree search is a basic kind of search algorithm. The root is the initial state. Unlike graphs, tree search treats different paths to same state as unique, which can turn a linear problem into an exponential one. Using graphs instead can remedy this. A node is more than just a state. It can have other information such as parent node, action, depth, path cost. Graph search algorithms primarily differ from tree search in that graphs keep track of nodes that have already been explored and only expand nodes that aren’t in the frontier or the explored set. The search strategy is simply the order of tree expansion (LIFO, FIFO, priority).\\ \nUniform-cost search is guaranteed to find an optimal solution, and Dijkstra's algorithm is just uniform-cost search without a goal. \n \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n An environment is competitive if it has multiple agents with conflicting goals. Determining the best action in this context is an adversial search problem. To abstract many agents at once, we could abstract them as an economy that operates in aggregate, or simply as part of a nondeterministic environment, but modeling them as adversaries captures their goal-oriented behavior better. Minimax search is an adversarial game-tree search algorithm that finds the optimal move. Pruning improves efficiency by ignoring pointless portions of the search tree. At any given state, there are two ways to estimate who is winning: either use a heuristic evaluation function, or run many quick simulations and average them. The most commonly studied adversarial games are zero-sum, meaning that +1 for you is -1 for your adversary. These games can be represented with a state-space graph, where vertices are states and edges are moves. A game tree is a search tree over that graph and could be infinite or just huge (for chess, 10^40 nodes). So we need efficient ways to explore the tree. Making an optimal move is more complex in adversial games because it requires a conditional strategy that takes into account how the adversary will act, just as in war.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n  We use minimax search to determine the optimal move at each state. Max goes first. The nodes in the game tree represent whose turn it is to move. The edges out of that node are the possible moves. We expand to a certain level, estimate the utility of that state, and then return the value of the optimal move from that \\ \nstate, which will be the min value for MIN and the max for MAX. So for every state except terminal ones, the value is determined by some calculation of how things play out optimally. Minimax is a recursive depth-first algorithm where the base case is a terminal state. If m is the max depth of the game tree, it's O(b^m) time and O(bm) or O(m) space. This time is impractical for complex games but we can approximate it. Alpha-beta pruning cuts the exponent in half. Alpha is the lower-bound for MAX (the at least, starts at negative infinity) and Beta is the upper-bound for MIN (the at most, starts at positive infinity). Minimax updates these values each time something better is found and thereafter will not explore any subtree whose outcome would be worse for the opponent, because it knows the opponent will not choose a suboptimal path. Essentially, if it's MAX's turn, and for one action the play-out based on MIN's optimal moves would result in an outcome lower than MAX's lower bound, the algorithm can immediately stop considering any other branches of that subtree, because MAX knows that MIN would pick that lower action, won't choose the action leading to this sub-optimal (for MAX) subtree. The effectiveness of pruning depends on the ordering of the moves. If they go from worst to best, then each new move will be worth exploring. Ideally they would go from best to worst, which would halve the max depth, reducing the branching factor to its square root and enabling Minimax to solve a tree twice as deep in the same amount of time (putting the best moves first is called the killer move heuristic). We can't know the best move, but we can approximate it. Random choice results in 3/4 the max depth. Even more effective is to predict the best move based on data gained as the game is played. Another way to improve efficiency is to track previously seen states. Transpositions are different permutations of the move sequence that result in the same state. If we cache the heuristic value of states in a transposition table, we can avoid redundant work. For chess, this technique can cut time in half. Since some game trees are still unwieldy even with move ordering and caching, Type A and Type B techniques are used to further improve efficiency. Type A limits depth but not breadth (wide but shallow) and evaluates pseudo-terminal nodes with a heuristic function. Type B limits breadth but not depth (deep but narrow). \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n To limit the depth even when states aren't actually terminal, we test for the cutoff instead of terminality, and we estimate the value of that state with a heuristic evaluation function. If the state is actually terminal, its evaluation is its actually utility; otherwise the estimate is somewhere between a loss and a win. This estimate shouldn't take too long or it defeats the purpose. The estimate can be based on assigning material value to features of the state, and can use a weighted linear function with normalized weights. Clearly these values should be correlated with actual chances of winning. These values may come from human experience or machine learning. While the cutoff can be a fixed limit, iterative deepening is more effective. The cutoff is also more effective if only applied to quiescent positions (no pending move that would swing big), in which case a quick quiescene search must be done to estimate this. It's tough to eliminate the horizon effect (staving off an inevitable loss with delay tactics). A more aggressive version of alpha-beta pruning is forward pruning. Unlike alpha-beta, forward pruning could prune moves that are actually good. Its aim is to trim \nprobably-bad moves to save time. It can be done with beam search (just try the n best moves) or using probabilities based on prior experience. Or you can use late move reduction, which reduces the depth to which moves later in the list are explored, unless the value returned exceeds alpha, in which case the search is run to full depth. One last time saver: the opening game and endgame have fewer possible moves and therefore moves can actually be chosen with table lookup instead of costly search strategies. A policy is a mapping from every possible state to the best move from the state.\n\n## AIMA Chapter 5.5 Stochastic Games\n Some adversarial games like backgammon are also stochastic and involve chance with known probabilities. Their game trees have chance nodes between MAX and MIN nodes, and the minimax values are based on the expected value (sum of the value over all outcomes, weighted by the probability of each chance action). In the expectiminimax algorithm this is called expectiminimax value.It's critical that these values are a positive linear transformation of the probability of winning, and not just values with an accurate preference order. We want values to reflect the probability of winning from some state. While minimax takes O(b^m), expectiminimax takes O(b^m * n^m) where\nn is the number of distinct dice rolls. This reflects consideration of all possible dice roll sequences. This means that the possible ways the game could unfold have been massively increased and we need a way to simplify the search. We are already alpha-beta pruning MIN and MAX nodes and we can do something similar for chance nodes. Essentially, you bound the upper and lower range of the utility function so you can upper-bound a chance node's value without examining all of its children. You could also use forward pruning (such as beam search) or skip the evaluation function and use Monte Carlo instead.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n We have considered some simple goal-based agents that clearly differentiate between good and bad states, but now we'll consider decision-theoretic agents that assign a continuous range of values to states. This involves a combination of utility theory and probability theory. The basic principle of decision theory is maximum expected utility (MEU), which is different from performance measure because performance measure gives a score to the historical sequence of states, while MEU estimates the value of the next state. The simplest form of decision theory assumes an episodic environment and thus considers only the immediate outcomes of actions. Every outcome has some probability of occuring and some utility. The expected utility of an action is the average utility of all outcomes weighted by their probability of occurring. MEU says that an agent should maximize the EU, but does not itself say how that should be done.  \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n To understand why averaging expected utility is rational, we can show that MEU follows logically if we write down constraints on rational preferences that a rational agent should have. These constraints are the axioms of utility theory: orderability, transivitity, continuity, substitutability, monotonicity, decomposability. Violations of these axioms is patently irrational. It turns out that an agent can act rationally (meaning consistent with its rational preferences) only by choosing an action that maximizes expected utility, even if it's not doing so explicitly. \n\n## AIMA Chapter 16.3 Utility Functions\n We may want our decision-theoretic agent to make decision that reflect human preferences, and thus we may need to figure out a human's utility function. You can do this by preference elicitation. We'd like a scale for this utility that's bounded by some best and worst value; these are 0 and 1 in a normalized utility. Decision theory is a normative theory, meaning it describes how a rational agent should act, in contrast to descriptive theory which describes how people actually act. Humans have many biases such as the anchoring effect that result in irrational decisions.\n\n## Module 5 Lecture Notes\nFor alpha-beta pruning, MIN updates beta (to minimize it) and compares to MAX's alpha. If beta <= alpha, it stops evaluating because MAX won't follow this path.MAX updates alpha and compares to MIN's beta. Again, if beta <= alpha, it stops and returns that alpha value. Basically, both MAX and MIN keep going as long as beta is bigger than alpha. If we explore all branches of a node, the alpha and beta are the same at the end. If we pruned early, either alpha or beta is the original +/- infinity value. If a child beta is less than the parent alpha, it never gets updated and stays + infinity.The easiest way to encapsulate consistency is this: if a heuristic is consistent, f(n) will always increase monotonically on the path to the goal. The key implication is that once you hit the goal, you know you've hit it with the shortest path. If the heuristic isn't consistent, there could still be a shorter path that you haven't found yet.Here's an example: say that A is actually 10 away from goal, and B is 8 away. And say that h(A) is 9 and h(B) is 8. This heuristic is admissible because it didn't overestimate the real distances, but it's not consistent. Here's why. The step cost from A to B is 2, so the sum of that cost and h(B) is 2+8=10. But h(A) is only 9. It's logically inconsistent that the estimated distance from A is less than the path from A to B plus the estimate from B. To be consistent, the estimate from A would have to be greater than or equal to the cost of going from A to B plus B's estimated distance from the goal.For an optimal solution, TreeSearch-A* admissible heuristic is sufficient, but \n\\GraphSearch A* requires a consistent heuristic.\n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Imperfect information** - partially observable\n* **Move** - action\n* **Position** - state\n* **Transition model** - rules for the state that results from taking some action from some state\n* **Terminal test** - True when game is over, otherwise False\n* **Utility function** - defines final numeric value for a player in terminal state\n* **Ply** - one move by one player\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n In search problems that specify states as black boxes with no internal structure, we need domain-specific code to find transitions between states. CSPs give structure to states and thus enable us to use general-purpose algorithms and heuristics to solve these problems. When each state is a set of variables with value assignments, this is called a factored representation. The constraint on two variables may be defined by a relation that could be implicit or explicit. An implicit relation describes the relationship as something like x < y, while an explicit relation would have sets of allowable assignments to x and y from their domains. So basically a relation is a way of expressing a constraint. CSPs may be represented with a constraint graph in which nodes represent variables and edges represent constraints between the variables. CSPs can prune large swaths of the search space by discarding further refinements of a partial assignment once it has violated a constraint. Precedence constraints specify that one task must occur before another; in this case the variables represent start times and the relation could be an inequality. Domains can be finite or infinite, discrete or continuous. Discrete and finite is the easiest kind to solve. There are special algorithms for CSPs with linear constraints on integer variables, but problems with nonlinear constraints are undecidable. Linear programming problems are CSPs with continous domains where constraints must be linear equalities or inequalities. A unary constraint restricts the value of a single variable while a binary constraint relates two variables. A global constraint involves an arbitratry number of variables but not necessarily all of them. Preference constraints indicate preferred solutions and can be encoded as costs on individual variable assignments. This kind of CSP would be solved with optimization search methods and is called a constrained optimization problem.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nConstraint propagation uses inference to reduce the domain of a variable, which may have a domino effect on the domains of other variables. AC-3 enforces arc consistency by maintaining a queue of arcs initialized to all arcs (binary constraints) in the CSP. If there is no satisfying assignment for a value in the tail to some value in the head, that value is removed from the tail and its neighbors are added back to the queue, since now their domains may need to be updated again. If any domain is revised down to nothing, we know there is no consistent solution. Path consistency enforces constraints on triples of variables. Sometimes enforcing a higher-order constraint such as All Diff is more effecive than enforcing its translation into binary constraints. One important higher-order constraint is the resource (at most) constraint. If the sum of the assignments to a set of variables exceeds some bound, the resource constraint is violated. We can also check for bounds consistency with bounds propagation.\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n In CSP backtracking search we only consider a single variable at each node in the search tree because CSP problems are commutative: it doesn't matter which order we assign the variables in. Backtracking search is a common way to solve CSPs. The basic algorithm is to choose an unassigned variable and try to extend that assignment into a solution via a recursive call. If the assignment fails, we try the next value in the domain for that variable, and so on. This can still take awhile if the problematic assignment was early on and we backtrack in a depth-first fashion, so it can be improved with domain-independent heuristics. When we select an unassigned variable, it's best to choose that with the minimum remaining values (this is the MRV heuristic). When we select a value from a variable's domain, we may want to choose the least-constraining value. Both of these take time but could speed things up if they lead to more efficient backtracking. It also greatly improves efficiency to interleave search and inference. Each time we assign a value to a variable, we can make an inference about the domains of other variables. A simple form of this kind of inference is forward-checking: when X is assigned a value, it establishes arc consistency for all neighbors of \nX, such that X is the head, so values are deleted from any tail (any neighbor Y) if they are inconsistent with the value picked for X. Even more powerful is the \nMaintain Arc Consistency algorithm, which calls AC-3 after each assignment, but the queue of arcs is initialized only to the neighbors of X rather than all arcs. We can change the way we backtrack too. The default is chronological backtracking: just go back to the most recent assignment. This can be improved upon by maintaining a conflict set and doing conflict-directed backjumping.\n\n## AIMA Chapter 6.4 Local Search for CSPs\nCSPs can also be solved using local search, which actually starts with a complete assignment to all the variables and then changes the value of one variable at a time using the min-conflicts heuristic: select the value that results in the minimum number of conflicts. This can be surprisingly effective and even works on the n-queens problem roughly independent of problem size! Constraint weighting and tabu search are other forms of local search. Local search is also great for something like repairing an airport schedule with a minimum number of changes because it can start from the current assignment, whereas backtracking search would start from scratch and might arrive at a very different solution.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\nOne way to find solutions faster is to decompose a problem into independent subproblems, which can be identified as the connected components in the constraint graph. This can have massive time reductions but unfortunately completely independent subproblems are rare. Other graph structures can have benefits too. Any tree-structured CSP can be solved in time linear in the number of variables. If the variables are ordered as a topological sort with directional arc consistency, you can simply walk through them from the root and assign as you go. Sometimes it is possible to reduce other graphs to trees by removing nodes or collapsing nodes together. A cycle cutset is some subset of the nodes whose removal turns the graph into a tree. The algorithm for this transformation is called cutset conditioning. Another strategy for turning a graph into a tree is tree decomposition. We can also reduce the search space by a factor of d! by breaking value symmetry by introducing a symmetry-breaking constraint so that we don't explore all permutations of a satisfying assignment.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge-based agents reason over an internal representation of the world. Logic is actually a class of representations. This ability to store, \\ \nupdate, and derive general facts is powerful; these algorithms can adapt, learn quickly, and function independently of the domain in which they are applied. In contrast, the scope and application of problem-solving agents' abstractions are far more limited. A knowledge base consists of a set of assertions about the world, which are called sentences. These sentences are written in a specific knowledge representation language that allows for logical operations. Axioms are the given assertions and every other sentence is derived from them. You TELL a KB new sentences and ASK whether particular sentences are inferrable from its contents. Unlike other agents we've seen, KB agents operate at the knowledge level rather than the implementation level: their behavior is determined only by their specified knowledge and goals. The procedural approach directly encodes behaviors, while the declarative approach allows behavior to follow from the knowledge. It's often optimal to combine these. \n\n## AIMA Chapter 7.2 The Wumpus World\n Agents operate in task environments, which we define with PEAS: Performance Measure, Environment, Actuators, Sensors. In the Wumpus World the agent at first knows only the rules of the environment but cannot observe most of it. It begins expanding its KB via the percepts it receives and the inferences it can then make. Given the rules of logic, these inferences are guaranteed correct as long as its KB and the information it receives are accurate. \n\n## AIMA Chapter 7.3 Logic\n Every knowledge representation language has a syntax that specifies well-formed sentences so they can be systematically operated on, as with arithmetic. The semantics of the language define the truth or meaning of the sentences relative to a particular model of the world. A model satisfies a sentence if that sentence is true in that model. Sentence A entails sentence B if B is true in every model in which A is true, i.e. if M(A) is a subset of M(B). Given this definition, there could be models in which B is true but A is not. Since a KB can be thought of as a single sentence, the KB itself can also be true or false with respect to some model. In fact, if we have abstracted the environment into particular variables, the set of all possible models would contain all possible \\ \ncombinations of assignments to those variables. Inferring can be a process of ruling out possibilities and narrowing things down as you determine which models contradict the KB and which possibilities remain in the consistent models. You can ASK whether A is true by model-checking in this way: is M(KB) a subset of M(A)?. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Propositional logic is a particular knowledge representation language. Its syntax enables an algorithm for making logical inferences. This implements the notion of logical entailemnt. In PL an atomic sentence is a single proposition symbol that can be true or false. We use logical connectives to combine these and produce complex sentences. A literal is either a positive or negated atomic sentence. The five most common connectives are: negation, conjunction, disjunction, implication, and biconditional. BNF Grammar specifies how these connectives operate on proposition symbols and gives rules for operator precedence to resolve ambiguity. A model is essentially a setting of the truth value for every proposition symbol. PL's semantics tell us the rules for when complex sentences can be considered true or false in a model. A truth table is one way to express these semantics. To construct a knowledge base, it helps to start with the immutable aspects of the world and then incorporate mutable ones via percepts.Once the KB is constructed, we use logical inference to check whether it entails some sentence A. One way to do this is with model-checking: enumerate all models, and see if A is true in every model where KB is true. This method is sound and complete but it takes exponential time: for n symbols, there are 2^n possible models. This is true for every known inference (entailment) algorithm for propositional logic; they are co-NP-complete. There are other more efficient algorithms. Theorem proving is a different method of entailment. It does not require consulting models. We use some new ideas here. If two sentences entail each other, they are logically equivalent. A sentence is valid if it's true in all models. The Deduction Theorem states that A entails B iff (A implies B) is valid. In contrast, A is satisfiable if it's true in SOME model, not necessarily all. Determining satisfiability (the SAT problem) is NP-complete, so many problems can be reduced to this form. Satisfiability can actually be used to prove validity: if (A and not B) is unsatisfiable, it must be true in all models, and therefore is valid.This is essentially a proof by contradiction. Distributivity: A and (B or C) = (A and B) or (A and C). A or (B and C) = (A or B) and (A or C).A proof is just a chain of conclusions that leads to a desired goal. We may use logical equivalence to transform sentences as we move through a proof. One example is implication elimination: (A implies B) equals ((not A) or B). We derive proofs using inference rules. A common inference rule is Modus Ponens: given that A implies B and given A, we can infer B. Another rule is And-Elimination: from a conjunction, any of the conjuncts can be inferred.\n\n## AIMA 7.5 Propositional Theorem Proving\n We can actually use search algorithms to find a proof, i.e. a path from initial state (KB) to goal state (sentence we want to prove). The actions are the inference rules, and the results are the inferences in the bottom half of each rule that we add to the KB. This can be way more efficient than model checking because it ignores irrelevant propositions.Logical systems are monotonic, meaning that the KB can only increase as new sentences are added; no previous sentences can be changed. Human logic is different because we change our minds.Theorem proving is sound but is only complete if the inference rules are adequate. It's possible for a search algorithm to be complete, assuming the goal is reachable, but if the inference rules can't provide a path to that goal then the inference algorithm is incomplete despite the completeness of the search algorithm. The resolution rule ensures that any inference algorithm is complete if coupled with a complete search algorithm. The resolution rule essentially says that (A and notA) resolves to the empty clause. If a disjunction of literals contains complementary (one negates the other) literals, the resolvent will not contain those complementary literals. Factoring removes multiple copies of literals: A or A is just A. To use the resolution rule we must express all sentences as clauses (disjunctions of literals), aka CNF: convert biconditionals to conjunctions, then do implication elimination, then move negation inwards with DeMorgan, then apply distribution to get rid of nested AND/OR operators. The resolution algorithm proves that KB entails A by proving that (KB and notA) is unsatisfiable. It uses proof by contradiction: the KB is converted to CNF and the resolution rule is applied to these clauses until either no new clauses can be added to KB (it does not entail A) or two clauses resolves to the empty clause (a contradiction: KB entails A). We can speed up the resolution algorithm if we're able to express all clauses as definite clauses (disjunction of literals in which exactly 1 is positive)  or horn clauses (at most 1 is positive, so 0 or 1). Goal clauses have no positive literals.  Inference with horn clauses can be done with forward-chaining or backward-chaining  algorithms in time linear with size of KB.  Forward-chaining determines if query Q is entailed by KB. Process: if all premises of an implication are known, its conclusion is added to KB. Continues until Q is added or no new inferences possible. It's sound and complete. Example of data-driven reasoning, moving forward from what is known. Backward-chaining works backward from query Q. If Q known, done. If not, find all implications in KB whose conclusion is Q. If it can prove all premises in any of those (using backward chaining), then Q is true. Example of goal-directed reasoning. Can be much less than linear in size of KB. \n\n## Module 7 Lecture Notes\n We use rules of logical equivalence to translate sentences into CNF form. Follow these steps. 1: Biconditional elimination. 2:  Implication elimination. 3: Move negation inwards by eliminating double negation  and using DeMorgan's rules. 4: Distribute ⋁ over ⋀ wherever possible to get rid  of nested ⋁ and ⋀ operators. Basically, keep replacing P ⋁ (Q ⋀ R) with   (P ⋁ Q) ⋀ (P ⋁ R).  Example: \n \n\n## Module 7 Definitions\n* **Distributivity of ⋁ over ⋀** - ((𝛂 ⋁ β) ⋀ ɣ) ≡ ((𝛂 ⋁ β) ⋀ (𝛂 ⋁ ɣ)))\n* **Distributivity of ⋀ over ⋁** - ((𝛂 ⋀ β) ⋁ ɣ) ≡ ((𝛂 ⋀ β) ⋁ (𝛂 ⋀ ɣ)))\n* **Implication elimination** - (𝛂 ⟹ β) ≡ (¬𝛂 ⋁ β)\n* **Demorgan1** -  ¬(𝛂 ⋀ β) ≡ (¬𝛂 ⋁ ¬β)\n* **Demorgan2** - ¬(𝛂 ⋁ β) ≡ (¬𝛂 ⋀ ¬β)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}