{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Ana_Machaidze_CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "dce91a40-6008-4a79-e18f-c7e790e4fc00"
      },
      "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": 177,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "85302756-f9d7-46bc-a3e1-bbcf693cca14"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"\n",
        "\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 178,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 1\n",
            "The length in characters is 1\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": 179,
      "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 = \"\"\" \n",
        "\n",
        "agent perceivs its environment through sensors and acts through actuators \\n\n",
        "percept - agent’s perceptual\n",
        "inputs at any given instance.\\n\n",
        "\n",
        "agent = architercture + program \\n\n",
        "\n",
        "A rational agent is an agent that perceives its environment and and behaves rationally \\n\n",
        "\n",
        "We define a performance measure: \\n\n",
        "• An objective criterion for success of an agent's behavior \\n\n",
        "• given the evidence provided by the percept sequence. \\n\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",
        " \"rational agent\":\n",
        "\" rational agent should select an action that is expected to maximize its performance measure\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 180,
      "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": 876
        },
        "cellView": "form",
        "outputId": "0b022452-e418-4957-fdc4-0612a6898392"
      },
      "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": 181,
      "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\n \n\nagent perceivs its environment through sensors and acts through actuators \n\npercept - agent’s perceptual\ninputs at any given instance.\n\n\nagent = architercture + program \n\n\nA rational agent is an agent that perceives its environment and and behaves rationally \n\n\nWe define a performance measure: \n\n• An objective criterion for success of an agent's behavior \n\n• given the evidence provided by the percept sequence. \n\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* **Rational agent** -  rational agent should select an action that is expected to maximize its performance measure\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "all dat treated as object \\n\n",
        "\n",
        "strings are immutabel \\n\n",
        "lists are mutable, [:] gives shallow copy (new obj, same value) \\n\n",
        "tuples are immutable \\n\n",
        "lists can have multiple type elements \\n \n",
        "Operations on the list: .sort() -in place, .reverse(), sorted(list) - new sorted obj \\n\n",
        "Dictionaary: .keys(), .values(), .items() returns tuples \\n\n",
        "Counter() type of dict where values are counts \\n\n",
        "*args to have undeterined number of variable n function inputn \\n\n",
        "**kwargs variable number of keyword args \\n\n",
        "\n",
        "Easy graph search ex:\\n\n",
        "d = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\\n\n",
        "[v for v in d.search(1, set())] \\n\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 182,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 484
        },
        "outputId": "af646b82-029e-438e-d1f1-bafbbc96723a"
      },
      "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": 183,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\nall dat treated as object \n\n\nstrings are immutabel \n\nlists are mutable, [:] gives shallow copy (new obj, same value) \n\ntuples are immutable \n\nlists can have multiple type elements \n \nOperations on the list: .sort() -in place, .reverse(), sorted(list) - new sorted obj \n\nDictionaary: .keys(), .values(), .items() returns tuples \n\nCounter() type of dict where values are counts \n\n*args to have undeterined number of variable n function inputn \n\n**kwargs variable number of keyword args \n\n\nEasy graph search ex:\n\nd = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\n\n[v for v in d.search(1, set())] \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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" \n",
        "Search Problem:\n",
        "- initial state\n",
        "- set of possible actions\n",
        "- goal state\n",
        "- path cost function \"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "Completeness\n",
        "Time complexity\n",
        "Space complexity\n",
        "Optimality\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "Breadth First Search BFS: the root node is expanded first, then all the successors of the root node are expanded\n",
        "next, then their successors, and so on\n",
        "Uniform Cost Search/ Dijikstra:\n",
        "Depth First Search DFS: \n",
        "Depth-limited and iterative deepening search: \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",  \n",
        "\"uninformed/blind search\" : \"no info about number of steps/path cost from start to goal state\",    \n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 184,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 580
        },
        "outputId": "66a3cce6-fe8d-4d22-9699-d4b1718f8f28"
      },
      "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": 185,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n \nSearch Problem:\n- initial state\n- set of possible actions\n- goal state\n- path cost function \n\n## AIMA Chapter 3.3 Search Algorithms\n\nCompleteness\nTime complexity\nSpace complexity\nOptimality\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nBreadth First Search BFS: the root node is expanded first, then all the successors of the root node are expanded\nnext, then their successors, and so on\nUniform Cost Search/ Dijikstra:\nDepth First Search DFS: \nDepth-limited and iterative deepening search: \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Uninformed/blind search** - no info about number of steps/path cost from start to goal state\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "\n",
        "\n",
        "Greedy best-first search\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 186,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 316
        },
        "outputId": "37b9e4f8-8246-487b-b033-1dace2cb3a59"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 187,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n\n\nGreedy best-first search\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "Minimax search:\n",
        "Given a game tree, the optimal strategy can be determined by working out the minimax value of each state in the tree, which we write as MINIMAX(s). The minimax value is the utility (for MAX) of being in that state, assuming that both players play optimally from there to the end of the game. The minimax value of a terminal state is just its utility. In a non-terminal state, MAX prefers to move to a state of maximum value when it is MAX’s turn to move, and MIN prefers a state of minimum value (that is, minimum value for MAX and thus maximum value for MIN).\n",
        "\\n\n",
        "\n",
        "The minimax algorithm performs a complete depth-first exploration of the game tree. If the maximum depth of the tree is and there are legal moves at each point, then the time complexity of the minimax algorithm is O(b^m). Space complexity: O(bm) for alg that generates all actions or O(m) that generates one at a time.\n",
        "\\n\n",
        "\n",
        "The exponential complexity makes MINIMAX impractical for complex games; for example, chess has a branching factor of about 35 and the average game has depth of about 80 ply, and it is not feasible to search states\n",
        "\\n\n",
        "\n",
        "Alpha-beta pruning: \\n\n",
        "Alpha-beta search computes the same optimal moves as minimax. \\n\n",
        "Alpha - best choice value for MAX  \\n\n",
        "Beta - best choice value for MIN \\n\n",
        "\\n\n",
        "Alpha-beta search prunes by comparing the values of children to the values of previous nodes. If we generate the worst successors first, we don't get to prune anything. If we generate the best successors first, we can prune most of the tree.\n",
        "\\n\n",
        "In the optimal ordering alphabeta takes O(b^m/2) time \\n\n",
        "\n",
        "Type A strategy - considers all possible moves to a certain depth in the search tree,\n",
        "and then uses a heuristic evaluation function to estimate the utility of states at that depth.\n",
        " It explores a wide but shallow portion of the tree. (Historically used in chess) \\n\n",
        "Type B strategy -  ignores moves that look bad, and follows promising lines “as far as possible.”\n",
        " It explores a deep but narrow portion of the tree. (shown good play in chess)\\n\n",
        "\\n\n",
        "They are useful because for games with a large search space, it is not feasible to search the whole tree. \n",
        "As such, we have to make tradeoffs about what part of the tree to search\\n\n",
        "\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\" Heuristic alpha-beta search replaces the utility function with an evaluation function. \\n \n",
        "\\n\n",
        "Evaluation function estimates the value for non-terminal nodes\\n\n",
        "\\n\n",
        "In heuristic alpha-beta pruning, the terminal test is replaced with a cutoff test, which decides when to cut off the search ( at the end or at some depth level)\n",
        "\\n\n",
        "The evaluation function should be applied only to positions that are quiescent.\\n\n",
        "Quiescent: there is no pending move that would wildly swing the valuation (not allow queen to die in chess)\\n\n",
        "\\n\n",
        "horizon effect is when an agent try to erroneously delay the inevitable \\n\n",
        "\\n\n",
        "Forward pruning prunes moves that appear to be bad moves (ex: beam search)\\n\n",
        "\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\" Monte Carlo Tree Search: playing the game to the end while randomly selecting moves.\n",
        "Evaluates action by repeatedly play the game from that state and take the average of the results. \\n\n",
        "\n",
        "An alternative called Monte Carlo tree search (MCTS) evaluates states not by applying a heuristic function, but by playing out the game all the way to the end and using the rules of the game to see who won. Since the moves chosen during the playout may not have been optimal moves, the process is repeated multiple times and the evaluation is an average of the results. \n",
        "\\n\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic Games \\n\n",
        "\n",
        "Games of chance can be handled by expectiminimax, an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children, weighted by the probability of each child\n",
        "\\n\n",
        "expected value: the average over all possible outcomes of the chance nodes\n",
        "\\n\n",
        "Expectiminimax: \\n\n",
        "Terminal, max and min nodes work the same way as before.\\n\n",
        "For chance node, we compute expected value (sum of the value over all outcomes, weighted by the probability of each chance action)\\n\n",
        "\\n\n",
        "evaluation function must return values that are a positive linear transformation of the probability of winning\\n\n",
        "\\n\n",
        "Runtime: O(b^m*n^m) where n is number of distinct rolls.\\n\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" The minimax search algorithm solves perfect information, zero-sum games. \\n\n",
        "\\n\n",
        "Games as search: \\n\n",
        "Initial state: e.g. board configuration of chess  \\n\n",
        "Successor function: list of (move,state) pairs specifying legal moves. \\n\n",
        "Terminal test: Checks if the game is finished \\n\n",
        "Utility function: Gives numerical value of terminal states. \\n\n",
        "MAX uses a search tree to determine the next move. \\n\n",
        "\\n\n",
        "Searches using DFS \\n\n",
        "\\n\n",
        "Runtime: \\n\n",
        "O(b^m) \\n\n",
        "b is the number of legal moves at each node \\n\n",
        "m is the maximum depth of the tree \\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Perfect information\": \"fully observable\",\n",
        "\"Zero sum\": \"what is good for one player is just as bad for the other, there is no win-win outcome\",\n",
        "\"Terminal state\": \"state where game ends\"\n",
        "  \n",
        "}\n",
        "\n"
      ],
      "execution_count": 188,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "63fc0a67-1a99-4935-f423-306f8d2530dc"
      },
      "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": 189,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nMinimax search:\nGiven a game tree, the optimal strategy can be determined by working out the minimax value of each state in the tree, which we write as MINIMAX(s). The minimax value is the utility (for MAX) of being in that state, assuming that both players play optimally from there to the end of the game. The minimax value of a terminal state is just its utility. In a non-terminal state, MAX prefers to move to a state of maximum value when it is MAX’s turn to move, and MIN prefers a state of minimum value (that is, minimum value for MAX and thus maximum value for MIN).\n\n\n\nThe minimax algorithm performs a complete depth-first exploration of the game tree. If the maximum depth of the tree is and there are legal moves at each point, then the time complexity of the minimax algorithm is O(b^m). Space complexity: O(bm) for alg that generates all actions or O(m) that generates one at a time.\n\n\n\nThe exponential complexity makes MINIMAX impractical for complex games; for example, chess has a branching factor of about 35 and the average game has depth of about 80 ply, and it is not feasible to search states\n\n\n\nAlpha-beta pruning: \n\nAlpha-beta search computes the same optimal moves as minimax. \n\nAlpha - best choice value for MAX  \n\nBeta - best choice value for MIN \n\n\n\nAlpha-beta search prunes by comparing the values of children to the values of previous nodes. If we generate the worst successors first, we don't get to prune anything. If we generate the best successors first, we can prune most of the tree.\n\n\nIn the optimal ordering alphabeta takes O(b^m/2) time \n\n\nType A strategy - considers all possible moves to a certain depth in the search tree,\nand then uses a heuristic evaluation function to estimate the utility of states at that depth.\n It explores a wide but shallow portion of the tree. (Historically used in chess) \n\nType B strategy -  ignores moves that look bad, and follows promising lines “as far as possible.”\n It explores a deep but narrow portion of the tree. (shown good play in chess)\n\n\n\nThey are useful because for games with a large search space, it is not feasible to search the whole tree. \nAs such, we have to make tradeoffs about what part of the tree to search\n\n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Heuristic alpha-beta search replaces the utility function with an evaluation function. \n \n\n\nEvaluation function estimates the value for non-terminal nodes\n\n\n\nIn heuristic alpha-beta pruning, the terminal test is replaced with a cutoff test, which decides when to cut off the search ( at the end or at some depth level)\n\n\nThe evaluation function should be applied only to positions that are quiescent.\n\nQuiescent: there is no pending move that would wildly swing the valuation (not allow queen to die in chess)\n\n\n\nhorizon effect is when an agent try to erroneously delay the inevitable \n\n\n\nForward pruning prunes moves that appear to be bad moves (ex: beam search)\n\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Monte Carlo Tree Search: playing the game to the end while randomly selecting moves.\nEvaluates action by repeatedly play the game from that state and take the average of the results. \n\n\nAn alternative called Monte Carlo tree search (MCTS) evaluates states not by applying a heuristic function, but by playing out the game all the way to the end and using the rules of the game to see who won. Since the moves chosen during the playout may not have been optimal moves, the process is repeated multiple times and the evaluation is an average of the results. \n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic Games \n\n\nGames of chance can be handled by expectiminimax, an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children, weighted by the probability of each child\n\n\nexpected value: the average over all possible outcomes of the chance nodes\n\n\nExpectiminimax: \n\nTerminal, max and min nodes work the same way as before.\n\nFor chance node, we compute expected value (sum of the value over all outcomes, weighted by the probability of each chance action)\n\n\n\nevaluation function must return values that are a positive linear transformation of the probability of winning\n\n\n\nRuntime: O(b^m*n^m) where n is number of distinct rolls.\n\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n The minimax search algorithm solves perfect information, zero-sum games. \n\n\n\nGames as search: \n\nInitial state: e.g. board configuration of chess  \n\nSuccessor function: list of (move,state) pairs specifying legal moves. \n\nTerminal test: Checks if the game is finished \n\nUtility function: Gives numerical value of terminal states. \n\nMAX uses a search tree to determine the next move. \n\n\n\nSearches using DFS \n\n\n\nRuntime: \n\nO(b^m) \n\nb is the number of legal moves at each node \n\nm is the maximum depth of the tree \n\n\n \n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Zero sum** - what is good for one player is just as bad for the other, there is no win-win outcome\n* **Terminal state** - state where game ends\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "CSP Problem is defined: \\n\n",
        "State - set of variables/value pairs \\n\n",
        "Conditions - set of constraints on a variable \\n\n",
        "consists of three components: X (set of variables), D (set of domains), C (constraints that specify allowable combinations) \\n\n",
        "The problem is solved when each variable has a value that satisfies all the constraints on the variable.\\n\n",
        "\\\n",
        "Compared to regular search problems CSP states are not black box, agent can see inside the states and move between states accordingly \\n\n",
        "A complete assignment - every variable is assigned and is consistent \\n\n",
        "A partial assignment - some variables are unassigned but it is consistent. \\n\n",
        "\n",
        "CSP is an NP-complete problem, and exists subproblems that can be solved very efficiently.\\n\n",
        "\\n\n",
        "Pros: quickly prune large search places based on constraints.\\n\n",
        "Simples kind of CSP: discrete, finite domains \\n\n",
        "Special solution algorithm exists for linear constraints. For nonlinear constraints on integer variables—the problem is undecidable \\n\n",
        "\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "constraint propagation/inference: using the constraints to reduce the number of legal values for a variable. \n",
        "reduce the legal values for another variable.\\n\n",
        "\n",
        "Node consistent: all the values in the variable’s domain satisfy the variable’s unary \n",
        "constraints. graph is node-consistent if every variable in the graph is node-consistent\\n\n",
        "\\n\n",
        "Arc consistent: every value in its domain satisfies the variable’s binary constraints.\\n\n",
        "A graph is arc-consistent if every variable is arc consistent with every other variable. \\n\n",
        "\\n\n",
        "AC-3 - algorithm (for arc consistency):\\n\n",
        "Initially, queue contains all arcs in the CSP .(Each binary constraint becomes two arcs, one in each direction.)\\n\n",
        "Pop (Xi ,Xj) from queue and make Xi consistent to Xj\\n\n",
        "If something changed, add all neighbour arcs to the queue\\n\n",
        "o/w move to the next arc\\n\n",
        "\n",
        "Complexity: \\n\n",
        "# of variables - n \\n\n",
        "Size of domain - d  \\n\n",
        "Arcs/binary constraints - c \\n\n",
        "\\n\n",
        "Each arc is inserted in the queue at most d times. Checking consistency - O(d^2). Overall - O(cd^2) \\n\n",
        "\n",
        "Path Consistency: \\n\n",
        "Path consistency is inferred by triples of variables. Considers two arc at a time. \\n\n",
        "\n",
        "K-consistency: \\n\n",
        "A CSP is k-consistent if, for any set of k−1 variables and for any consistent assignment to those variables,\n",
        " a consistent value can always be assigned to any kth variable \\n\n",
        "\n",
        "Node consistency = 1-consistency \\n\n",
        "Arc consistency = 2-consistency \\n\n",
        "Path consistency = 3-consistency \\n\n",
        "\n",
        "A CSP is strongly k-consistent if it is k-consistent and is also k-1-consistent, \n",
        "k-2- consistent, all the way down to 1-consistent. Runtime: O(n^2d) \\n\n",
        "\\\n",
        "Worst case runtime: exponential in n, space is also exponential in n \\n\n",
        "\\n\n",
        "\n",
        "Global constraint is one involving an arbitrary number of variables (but not necessarily all variables) \\n\n",
        "\\\n",
        "Alldiff: if variables are involved in the constraint, and if they have possible distinct values altogether, and , \n",
        "then the constraint cannot be satisfied \\n\n",
        "\n",
        "This leads to the following simple algorithm: First, remove any variable in the constraint that has a singleton domain, and delete \n",
        "that variable’s value from the domains of the remaining variables. Repeat as long as there are singleton variables. If at any point an \n",
        "empty domain is produced or there are more variables than domain values left, then an inconsistency has been detected. \\n\n",
        "\\n\n",
        "\\n\n",
        "\n",
        "higher-order constraint is the resource constraint, sometimes called the Atmost constraint. Ex: some of Xs is less than 10 \\n\n",
        "\n",
        "We say that a CSP is bounds-consistent if for every variable X, and for both the lowerbound and upper-bound values of X ,\n",
        " there exists some value of Y that satisfies the constraint between X and Y for every variable . This kind of bounds propagation \n",
        " is widely used in practical constraint problems.\\\n",
        "\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "Domain size: d \\n\n",
        "All complete assignment - leaf nodes at depth n \\n\n",
        "Branching factor - nd. Nex level (n-1)d .. \\n\n",
        "Total #of leaves: n!d^n \\n\n",
        "\n",
        "minimum-remaining-values (MRV) heuristic - choosing the variable with the fewest “legal” values \\n\n",
        "\\n\n",
        "degree heuristic -  attempts to reduce the branching factor on future choices by selecting the variable with the largest number of constraints \\n\n",
        "\\n\n",
        "Least-constraining-value heuristic - chooses the value that rules out the fewest values for neighboring variables \\n\n",
        "\\n\n",
        "In general: heuristic is trying to leave the maximum flexibility for subsequent variable assignments. Choses the ones that will fail first to have less to backtrack on. \\\n",
        "\\n\n",
        "forward checking: \\n\n",
        "\\n\n",
        "In forward checking, whenever a variable X is assigned, we establish arc consistency for X For each unassigned variable Y that is connected to X by a constraint,\n",
        " delete from Y's domain any value that is inconsistent with the value chosen for X.\\n\n",
        "\\n\n",
        "\n",
        " detects the inconsistency earlier than simple backtracking and thus it allows branches of the search tree that will lead to failure to be pruned earlier \\\n",
        " than with simple backtracking.\\n\n",
        "does not detect all inconsistencies because it doesn’t look ahead far enough\\ \\n\n",
        "\\n\n",
        "MAC (for Maintaining Arc Consistency): \\n\n",
        "detects inconsistencies. \\n\n",
        "Recursively propagate constraints when changes are made to the domain of variables.(unlike forward checking) \\n\n",
        "if we assign X, forward checking makes all the arcs incident on X consistent. MAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...)\\\n",
        "\\n\n",
        "chronological backtracking: back up to the preceding variable and try a different value for it \\n\n",
        "\\n\n",
        "conflict set for X is set of assignments that are in conflict with X \\n\n",
        "backjumping search method backtracks to the most recent assignment in the conflict set. A backjumping algorithm that uses conflict sets defined in this way is called conflict-directed backjumping\\\n",
        "\\n\n",
        "\n",
        "Constraint learning - caches the conflicts (no goods) as they are encountered in the search in order to avoid the same conflict later \\n\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "Min-conflict heuristic - select the value that results in the minimum number of conflicts with other variables \\n\n",
        "\\n\n",
        "tabu search - keeping a small list of recently visited states and forbidding the algorithm to return to those states \\n\n",
        "\\n\n",
        "constraint weighting -  constraints are given a numeric weight, initially all 1. At each step of the search, \\n\n",
        " the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. \\n\n",
        " The weights are adjusted by incrementing the weight of each constraint that is violated by the current assignment. \\n\n",
        "Pros: (1) adds topography, making sure that it is possible to improve from the current state \\n\n",
        "(2) adds learning: over time the difficult constraints are assigned higher weights \\n\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "Any tree-structured CSP can be solved in time linear in the number of variables \\n\n",
        "\\n\n",
        "Directional arc consistency or DAC - A CSP is defined to be directional arc-consistent under an ordering of variables X1, X2, .. \n",
        "if and only if every Xi is arc-consistent with each Xj for j > i \\n\n",
        "\\n\n",
        "Cutset conditioning: \\n\n",
        "Algorithm: \\n\n",
        "Choose a subset S of the variables s.t. constraint graph becomes a tree after removal of S. this is called a cycle cutset. \\n\n",
        "For each possible assignment to the variables in S that satisfies all constraints on S, \\n\n",
        " remove from the domains of the remaining variables any values that are inconsistent with the assignment for S, and \\n\n",
        "if the remaining CSP has a solution, return it together with the assignment for S \\n\n",
        "Runtime is O(d^c (n − c)d^2 ). Works well the graph is nearly tree. Otherwise not more efficient than solving CSP directly. \\n\n",
        "\\n\n",
        "Tree decomposition: \\n\n",
        "transform the CSP into a tree of subproblems.  \\n\n",
        "Rules: \\n\n",
        "Every variable in the original problem appears in at least one of the tree nodes.  \\n\n",
        "If two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. \\n\n",
        "If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. \\n\n",
        "\\n\n",
        "Runtime: O(nd^2), n number of tree nodes and d - size of largest domain.\\n\n",
        "Efficient if the tree width of the constraint graph is small.\\n\n",
        "\\n\n",
        "CSPs with constraint graphs of bounded tree width are solvable in polynomial time.\\n\n",
        "\\n\n",
        "Cutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width w \\n\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "CSP as search problem: \\n\n",
        "Initial State: the empty assignment {}. \\n\n",
        "Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict. \\n\n",
        "Goal test: the current assignment is complete. \\n\n",
        "Path cost: a constant cost for every step. \\n\n",
        "\n",
        "Solution always at depth n, can use dfs. \\n\n",
        "\n",
        "The AC-3/ waltz algorithm: \\n\n",
        "By iterating over the graph, the arc- consistency constraints can be propagated along arcs of the graph \\n\n",
        "Search: Use constraints to add labels to find one solution \\n\n",
        "Constraint Propagation: Use constraints to eliminate labels to simultaneously find all solutions \\n\n",
        "Algorithm: \\n\n",
        "Assign every node in the constraint graph a set of all possible values \\n\n",
        "Repeat until there is no change in the set of values associated with any node: \\n\n",
        "For each node i: \\n\n",
        "4. For each neighboring node j in the picture: \\n\n",
        "5. Remove any value from i which is not arc consistent with j \\n\n",
        "\n",
        "Worst case complexity: O(n^2d^3) \\n\n",
        "For planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3) \\n\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"disjunctive constraint\": \"either x1 or x2\",\n",
        "\"precedence constraints\" : \"x1 needs to come before x2\",\n",
        "\"unary constraint\": \"single variable\",\n",
        "\"binary constraint\": \"1 or 2v aribales\",\n",
        "\"global constraint\": \"arbitrary num of variables\",\n",
        "\"symmetry-breaking constraint\": \"arbitrary ordering constraints to remove redundancy and ensure only one solution is possible.\"\n",
        "    \n",
        "}\n"
      ],
      "execution_count": 190,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "3c7b91e8-7a26-4bd8-d44d-5b0a2c913a59"
      },
      "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": 191,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSP Problem is defined: \n\nState - set of variables/value pairs \n\nConditions - set of constraints on a variable \n\nconsists of three components: X (set of variables), D (set of domains), C (constraints that specify allowable combinations) \n\nThe problem is solved when each variable has a value that satisfies all the constraints on the variable.\n\nCompared to regular search problems CSP states are not black box, agent can see inside the states and move between states accordingly \n\nA complete assignment - every variable is assigned and is consistent \n\nA partial assignment - some variables are unassigned but it is consistent. \n\n\nCSP is an NP-complete problem, and exists subproblems that can be solved very efficiently.\n\n\n\nPros: quickly prune large search places based on constraints.\n\nSimples kind of CSP: discrete, finite domains \n\nSpecial solution algorithm exists for linear constraints. For nonlinear constraints on integer variables—the problem is undecidable \n\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nconstraint propagation/inference: using the constraints to reduce the number of legal values for a variable. \nreduce the legal values for another variable.\n\n\nNode consistent: all the values in the variable’s domain satisfy the variable’s unary \nconstraints. graph is node-consistent if every variable in the graph is node-consistent\n\n\n\nArc consistent: every value in its domain satisfies the variable’s binary constraints.\n\nA graph is arc-consistent if every variable is arc consistent with every other variable. \n\n\n\nAC-3 - algorithm (for arc consistency):\n\nInitially, queue contains all arcs in the CSP .(Each binary constraint becomes two arcs, one in each direction.)\n\nPop (Xi ,Xj) from queue and make Xi consistent to Xj\n\nIf something changed, add all neighbour arcs to the queue\n\no/w move to the next arc\n\n\nComplexity: \n\n# of variables - n \n\nSize of domain - d  \n\nArcs/binary constraints - c \n\n\n\nEach arc is inserted in the queue at most d times. Checking consistency - O(d^2). Overall - O(cd^2) \n\n\nPath Consistency: \n\nPath consistency is inferred by triples of variables. Considers two arc at a time. \n\n\nK-consistency: \n\nA CSP is k-consistent if, for any set of k−1 variables and for any consistent assignment to those variables,\n a consistent value can always be assigned to any kth variable \n\n\nNode consistency = 1-consistency \n\nArc consistency = 2-consistency \n\nPath consistency = 3-consistency \n\n\nA CSP is strongly k-consistent if it is k-consistent and is also k-1-consistent, \nk-2- consistent, all the way down to 1-consistent. Runtime: O(n^2d) \n\nWorst case runtime: exponential in n, space is also exponential in n \n\n\n\n\nGlobal constraint is one involving an arbitrary number of variables (but not necessarily all variables) \n\nAlldiff: if variables are involved in the constraint, and if they have possible distinct values altogether, and , \nthen the constraint cannot be satisfied \n\n\nThis leads to the following simple algorithm: First, remove any variable in the constraint that has a singleton domain, and delete \nthat variable’s value from the domains of the remaining variables. Repeat as long as there are singleton variables. If at any point an \nempty domain is produced or there are more variables than domain values left, then an inconsistency has been detected. \n\n\n\n\n\n\nhigher-order constraint is the resource constraint, sometimes called the Atmost constraint. Ex: some of Xs is less than 10 \n\n\nWe say that a CSP is bounds-consistent if for every variable X, and for both the lowerbound and upper-bound values of X ,\n there exists some value of Y that satisfies the constraint between X and Y for every variable . This kind of bounds propagation \n is widely used in practical constraint problems.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nDomain size: d \n\nAll complete assignment - leaf nodes at depth n \n\nBranching factor - nd. Nex level (n-1)d .. \n\nTotal #of leaves: n!d^n \n\n\nminimum-remaining-values (MRV) heuristic - choosing the variable with the fewest “legal” values \n\n\n\ndegree heuristic -  attempts to reduce the branching factor on future choices by selecting the variable with the largest number of constraints \n\n\n\nLeast-constraining-value heuristic - chooses the value that rules out the fewest values for neighboring variables \n\n\n\nIn general: heuristic is trying to leave the maximum flexibility for subsequent variable assignments. Choses the ones that will fail first to have less to backtrack on. \n\nforward checking: \n\n\n\nIn forward checking, whenever a variable X is assigned, we establish arc consistency for X For each unassigned variable Y that is connected to X by a constraint,\n delete from Y's domain any value that is inconsistent with the value chosen for X.\n\n\n\n\n detects the inconsistency earlier than simple backtracking and thus it allows branches of the search tree that will lead to failure to be pruned earlier  than with simple backtracking.\n\ndoes not detect all inconsistencies because it doesn’t look ahead far enough\\ \n\n\n\nMAC (for Maintaining Arc Consistency): \n\ndetects inconsistencies. \n\nRecursively propagate constraints when changes are made to the domain of variables.(unlike forward checking) \n\nif we assign X, forward checking makes all the arcs incident on X consistent. MAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...)\n\nchronological backtracking: back up to the preceding variable and try a different value for it \n\n\n\nconflict set for X is set of assignments that are in conflict with X \n\nbackjumping search method backtracks to the most recent assignment in the conflict set. A backjumping algorithm that uses conflict sets defined in this way is called conflict-directed backjumping\n\n\nConstraint learning - caches the conflicts (no goods) as they are encountered in the search in order to avoid the same conflict later \n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nMin-conflict heuristic - select the value that results in the minimum number of conflicts with other variables \n\n\n\ntabu search - keeping a small list of recently visited states and forbidding the algorithm to return to those states \n\n\n\nconstraint weighting -  constraints are given a numeric weight, initially all 1. At each step of the search, \n\n the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. \n\n The weights are adjusted by incrementing the weight of each constraint that is violated by the current assignment. \n\nPros: (1) adds topography, making sure that it is possible to improve from the current state \n\n(2) adds learning: over time the difficult constraints are assigned higher weights \n\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n\nAny tree-structured CSP can be solved in time linear in the number of variables \n\n\n\nDirectional arc consistency or DAC - A CSP is defined to be directional arc-consistent under an ordering of variables X1, X2, .. \nif and only if every Xi is arc-consistent with each Xj for j > i \n\n\n\nCutset conditioning: \n\nAlgorithm: \n\nChoose a subset S of the variables s.t. constraint graph becomes a tree after removal of S. this is called a cycle cutset. \n\nFor each possible assignment to the variables in S that satisfies all constraints on S, \n\n remove from the domains of the remaining variables any values that are inconsistent with the assignment for S, and \n\nif the remaining CSP has a solution, return it together with the assignment for S \n\nRuntime is O(d^c (n − c)d^2 ). Works well the graph is nearly tree. Otherwise not more efficient than solving CSP directly. \n\n\n\nTree decomposition: \n\ntransform the CSP into a tree of subproblems.  \n\nRules: \n\nEvery variable in the original problem appears in at least one of the tree nodes.  \n\nIf two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. \n\nIf a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. \n\n\n\nRuntime: O(nd^2), n number of tree nodes and d - size of largest domain.\n\nEfficient if the tree width of the constraint graph is small.\n\n\n\nCSPs with constraint graphs of bounded tree width are solvable in polynomial time.\n\n\n\nCutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width w \n\n \n\n## Module 6 Lecture Notes\n \nCSP as search problem: \n\nInitial State: the empty assignment {}. \n\nSuccessor function: Assign value to any unassigned variable provided that there is not a constraint conflict. \n\nGoal test: the current assignment is complete. \n\nPath cost: a constant cost for every step. \n\n\nSolution always at depth n, can use dfs. \n\n\nThe AC-3/ waltz algorithm: \n\nBy iterating over the graph, the arc- consistency constraints can be propagated along arcs of the graph \n\nSearch: Use constraints to add labels to find one solution \n\nConstraint Propagation: Use constraints to eliminate labels to simultaneously find all solutions \n\nAlgorithm: \n\nAssign every node in the constraint graph a set of all possible values \n\nRepeat until there is no change in the set of values associated with any node: \n\nFor each node i: \n\n4. For each neighboring node j in the picture: \n\n5. Remove any value from i which is not arc consistent with j \n\n\nWorst case complexity: O(n^2d^3) \n\nFor planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3) \n\n \n\n## Module 6 Definitions\n* **Disjunctive constraint** - either x1 or x2\n* **Precedence constraints** - x1 needs to come before x2\n* **Unary constraint** - single variable\n* **Binary constraint** - 1 or 2v aribales\n* **Global constraint** - arbitrary num of variables\n* **Symmetry-breaking constraint** - arbitrary ordering constraints to remove redundancy and ensure only one solution is possible.\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "Can reason in addition to internal knowledeg \\n\n",
        "\n",
        "KB consists of sentences in the representation language \\n\n",
        "• Representation language has a syntax that specifies sentences that are well-formed \\n\n",
        "• A logic defines the semantics of the sentences, which is their meaning \\n\n",
        "• The semantics defines the truth of each sentence with respect to a possible world,\n",
        "which we will often call a model.\\n  \n",
        "\n",
        "M(a) set of all models of a \\n\n",
        "\n",
        "Atomic sentences are represented with a single propositional symbols \\n\n",
        "Propositional symbols - statement that can be true or false \\n\n",
        "\n",
        "~ not \\n\n",
        "⋀ and \\n\n",
        "⋁ or \\n\n",
        "\n",
        "Entailment - logical inference \\n\n",
        "\n",
        "Sound – the inference algorithm should only derive entailed sentences. \\n\n",
        "Complete – an inference algorithm is complete if it can derive all sentences that are\n",
        "entailed \\n\n",
        "\n",
        "Logical equivalece: \\n\n",
        "(A ⋀ B) ≡ (B ⋀ A) Commutativity of ⋀ \\n\n",
        "(A ⋁ B) ≡ (B ⋁ A) Commutativity of ⋁ \\n\n",
        "((A ⋀ B) ⋀ C) ≡ (A ⋀ (β ⋀ C)) Associativity of ⋀ \\n\n",
        "((A ⋁ B) ⋁ C) ≡ (A ⋁ (B ⋁ C)) Associativity of ⋁ \\n\n",
        "¬ (¬ A) ≡ A Double-negation elimination \\n\n",
        "(A ⟹ B) ≡ (¬B ⟹ ¬A) Contraposition \\n\n",
        "(A ⟹ B) ≡ (¬A ⋁ B) Implication elimination \\n\n",
        "(A ⇔ B) ≡ ((A ⟹ B) ⋀ (B ⟹A)) Biconditional elimination \\n\n",
        "¬(A ⋀ B) ≡ (¬A ⋁ ¬B) De Morgan \\n\n",
        "¬(A ⋁ B) ≡ (¬A ⋀ ¬B) De Morgan \\n\n",
        "((A ⋀ B) ⋁ C) ≡ ((A ⋀ B) ⋁ (A ⋀ C))) or  ((A ⋁ C) ⋀ (B ⋁ C)) Distributivity of ⋀ over ⋁ \\n\n",
        "((A ⋁ B) ⋀ C) ≡ ((A ⋁ B) ⋀ (A ⋁ C))) Distributivity of ⋁ over ⋀ \\n\n",
        "\n",
        "\n",
        "Conjunctive Normal Form (CNF) \\n\n",
        "Every sentence of propositional logic is logically equivalent to a conjunction of clauses. \\n\n",
        "Clauses are disjunctions of literals. \\n\n",
        "1. Eliminate ⇔ by replacing A ⇔ β with (A ⟹ β) ⋀ (β ⟹A) \\n\n",
        "2. Eliminate ⟹ by replacing A ⟹ β with ¬A ⋁ β \\n\n",
        "3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules \\n\n",
        "4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\n",
        "distributivity law to distribute ⋁ over ⋀ wherever possible.  \\n\n",
        "\n",
        "Inference procedures based on resolution work using the principle of proof by\n",
        "contradiction. \\n\n",
        "To show KB⊨A then we can show that KB ⋀ ¬A is unsatisfiable. \\n\n",
        "Here’s how: \\n\n",
        "• First, convert (KB ⋀ ¬A) into CNF \\n\n",
        "• Then apply the resolution rule to the resulting clauses. \\n\n",
        "• Resolve every pair that contains complementary literals to produce a new clause \\n\n",
        "• If that new clause isn’t already present, then add it to the set. \\n\n",
        "• Continue the process until one of two things happens: \\n\n",
        "1. There are no new clauses that can be added. In this case, the KB does not entail A \\n\n",
        "2. Two clauses resolve to yield the empty clause, in which case the KB does entail A \\n\n",
        "\n",
        "Resolution algorithm is complete \\n\n",
        "\n",
        "\n",
        "Definite clause – disjunction of literals where exactly one is positive \\n\n",
        "• Horn clause – disjunction of literals where at most one is positive \\n\n",
        "• This includes definite clauses \\n\n",
        "• And clauses with no positive literals \\n\n",
        "Horn clauses are closed under resolution. If you apply resolution to a horn clause, you\n",
        "get back a horn clause. \\n\n",
        "\n",
        "Deciding entailment wit corn clauses can be done in linear time\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Axioms\" : \"a sentence that is given\",\n",
        "\"Derived sentences\": \"a new sentence that is derived from others sentences\",\n",
        "\"Inference\": \"The process of deriving new sentences from old sentences\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 192,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0d8a3952-df59-4c3a-d4c4-8020b7a66acf"
      },
      "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": 193,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n \nCan reason in addition to internal knowledeg \n\n\nKB consists of sentences in the representation language \n\n• Representation language has a syntax that specifies sentences that are well-formed \n\n• A logic defines the semantics of the sentences, which is their meaning \n\n• The semantics defines the truth of each sentence with respect to a possible world,\nwhich we will often call a model.\n  \n\nM(a) set of all models of a \n\n\nAtomic sentences are represented with a single propositional symbols \n\nPropositional symbols - statement that can be true or false \n\n\n~ not \n\n⋀ and \n\n⋁ or \n\n\nEntailment - logical inference \n\n\nSound – the inference algorithm should only derive entailed sentences. \n\nComplete – an inference algorithm is complete if it can derive all sentences that are\nentailed \n\n\nLogical equivalece: \n\n(A ⋀ B) ≡ (B ⋀ A) Commutativity of ⋀ \n\n(A ⋁ B) ≡ (B ⋁ A) Commutativity of ⋁ \n\n((A ⋀ B) ⋀ C) ≡ (A ⋀ (β ⋀ C)) Associativity of ⋀ \n\n((A ⋁ B) ⋁ C) ≡ (A ⋁ (B ⋁ C)) Associativity of ⋁ \n\n¬ (¬ A) ≡ A Double-negation elimination \n\n(A ⟹ B) ≡ (¬B ⟹ ¬A) Contraposition \n\n(A ⟹ B) ≡ (¬A ⋁ B) Implication elimination \n\n(A ⇔ B) ≡ ((A ⟹ B) ⋀ (B ⟹A)) Biconditional elimination \n\n¬(A ⋀ B) ≡ (¬A ⋁ ¬B) De Morgan \n\n¬(A ⋁ B) ≡ (¬A ⋀ ¬B) De Morgan \n\n((A ⋀ B) ⋁ C) ≡ ((A ⋀ B) ⋁ (A ⋀ C))) or  ((A ⋁ C) ⋀ (B ⋁ C)) Distributivity of ⋀ over ⋁ \n\n((A ⋁ B) ⋀ C) ≡ ((A ⋁ B) ⋀ (A ⋁ C))) Distributivity of ⋁ over ⋀ \n\n\n\nConjunctive Normal Form (CNF) \n\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses. \n\nClauses are disjunctions of literals. \n\n1. Eliminate ⇔ by replacing A ⇔ β with (A ⟹ β) ⋀ (β ⟹A) \n\n2. Eliminate ⟹ by replacing A ⟹ β with ¬A ⋁ β \n\n3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules \n\n4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\ndistributivity law to distribute ⋁ over ⋀ wherever possible.  \n\n\nInference procedures based on resolution work using the principle of proof by\ncontradiction. \n\nTo show KB⊨A then we can show that KB ⋀ ¬A is unsatisfiable. \n\nHere’s how: \n\n• First, convert (KB ⋀ ¬A) into CNF \n\n• Then apply the resolution rule to the resulting clauses. \n\n• Resolve every pair that contains complementary literals to produce a new clause \n\n• If that new clause isn’t already present, then add it to the set. \n\n• Continue the process until one of two things happens: \n\n1. There are no new clauses that can be added. In this case, the KB does not entail A \n\n2. Two clauses resolve to yield the empty clause, in which case the KB does entail A \n\n\nResolution algorithm is complete \n\n\n\nDefinite clause – disjunction of literals where exactly one is positive \n\n• Horn clause – disjunction of literals where at most one is positive \n\n• This includes definite clauses \n\n• And clauses with no positive literals \n\nHorn clauses are closed under resolution. If you apply resolution to a horn clause, you\nget back a horn clause. \n\n\nDeciding entailment wit corn clauses can be done in linear time\n\n\n## Module 7 Definitions\n* **Axioms** - a sentence that is given\n* **Derived sentences** - a new sentence that is derived from others sentences\n* **Inference** - The process of deriving new sentences from old sentences\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "fcdcc72a-fc6b-4f04-e6e6-f9109da40ee5"
      },
      "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": 194,
      "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\n \n\nagent perceivs its environment through sensors and acts through actuators \n\npercept - agent’s perceptual\ninputs at any given instance.\n\n\nagent = architercture + program \n\n\nA rational agent is an agent that perceives its environment and and behaves rationally \n\n\nWe define a performance measure: \n\n• An objective criterion for success of an agent's behavior \n\n• given the evidence provided by the percept sequence. \n\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* **Rational agent** -  rational agent should select an action that is expected to maximize its performance measure\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\nall dat treated as object \n\n\nstrings are immutabel \n\nlists are mutable, [:] gives shallow copy (new obj, same value) \n\ntuples are immutable \n\nlists can have multiple type elements \n \nOperations on the list: .sort() -in place, .reverse(), sorted(list) - new sorted obj \n\nDictionaary: .keys(), .values(), .items() returns tuples \n\nCounter() type of dict where values are counts \n\n*args to have undeterined number of variable n function inputn \n\n**kwargs variable number of keyword args \n\n\nEasy graph search ex:\n\nd = DiGraph([(1,2),(1,3),(2,4),(4,3),(4,1)])\n\n[v for v in d.search(1, set())] \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 Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n \nSearch Problem:\n- initial state\n- set of possible actions\n- goal state\n- path cost function \n\n## AIMA Chapter 3.3 Search Algorithms\n\nCompleteness\nTime complexity\nSpace complexity\nOptimality\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nBreadth First Search BFS: the root node is expanded first, then all the successors of the root node are expanded\nnext, then their successors, and so on\nUniform Cost Search/ Dijikstra:\nDepth First Search DFS: \nDepth-limited and iterative deepening search: \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Uninformed/blind search** - no info about number of steps/path cost from start to goal state\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n\n\nGreedy best-first search\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nMinimax search:\nGiven a game tree, the optimal strategy can be determined by working out the minimax value of each state in the tree, which we write as MINIMAX(s). The minimax value is the utility (for MAX) of being in that state, assuming that both players play optimally from there to the end of the game. The minimax value of a terminal state is just its utility. In a non-terminal state, MAX prefers to move to a state of maximum value when it is MAX’s turn to move, and MIN prefers a state of minimum value (that is, minimum value for MAX and thus maximum value for MIN).\n\n\n\nThe minimax algorithm performs a complete depth-first exploration of the game tree. If the maximum depth of the tree is and there are legal moves at each point, then the time complexity of the minimax algorithm is O(b^m). Space complexity: O(bm) for alg that generates all actions or O(m) that generates one at a time.\n\n\n\nThe exponential complexity makes MINIMAX impractical for complex games; for example, chess has a branching factor of about 35 and the average game has depth of about 80 ply, and it is not feasible to search states\n\n\n\nAlpha-beta pruning: \n\nAlpha-beta search computes the same optimal moves as minimax. \n\nAlpha - best choice value for MAX  \n\nBeta - best choice value for MIN \n\n\n\nAlpha-beta search prunes by comparing the values of children to the values of previous nodes. If we generate the worst successors first, we don't get to prune anything. If we generate the best successors first, we can prune most of the tree.\n\n\nIn the optimal ordering alphabeta takes O(b^m/2) time \n\n\nType A strategy - considers all possible moves to a certain depth in the search tree,\nand then uses a heuristic evaluation function to estimate the utility of states at that depth.\n It explores a wide but shallow portion of the tree. (Historically used in chess) \n\nType B strategy -  ignores moves that look bad, and follows promising lines “as far as possible.”\n It explores a deep but narrow portion of the tree. (shown good play in chess)\n\n\n\nThey are useful because for games with a large search space, it is not feasible to search the whole tree. \nAs such, we have to make tradeoffs about what part of the tree to search\n\n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Heuristic alpha-beta search replaces the utility function with an evaluation function. \n \n\n\nEvaluation function estimates the value for non-terminal nodes\n\n\n\nIn heuristic alpha-beta pruning, the terminal test is replaced with a cutoff test, which decides when to cut off the search ( at the end or at some depth level)\n\n\nThe evaluation function should be applied only to positions that are quiescent.\n\nQuiescent: there is no pending move that would wildly swing the valuation (not allow queen to die in chess)\n\n\n\nhorizon effect is when an agent try to erroneously delay the inevitable \n\n\n\nForward pruning prunes moves that appear to be bad moves (ex: beam search)\n\n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Monte Carlo Tree Search: playing the game to the end while randomly selecting moves.\nEvaluates action by repeatedly play the game from that state and take the average of the results. \n\n\nAn alternative called Monte Carlo tree search (MCTS) evaluates states not by applying a heuristic function, but by playing out the game all the way to the end and using the rules of the game to see who won. Since the moves chosen during the playout may not have been optimal moves, the process is repeated multiple times and the evaluation is an average of the results. \n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic Games \n\n\nGames of chance can be handled by expectiminimax, an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children, weighted by the probability of each child\n\n\nexpected value: the average over all possible outcomes of the chance nodes\n\n\nExpectiminimax: \n\nTerminal, max and min nodes work the same way as before.\n\nFor chance node, we compute expected value (sum of the value over all outcomes, weighted by the probability of each chance action)\n\n\n\nevaluation function must return values that are a positive linear transformation of the probability of winning\n\n\n\nRuntime: O(b^m*n^m) where n is number of distinct rolls.\n\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n The minimax search algorithm solves perfect information, zero-sum games. \n\n\n\nGames as search: \n\nInitial state: e.g. board configuration of chess  \n\nSuccessor function: list of (move,state) pairs specifying legal moves. \n\nTerminal test: Checks if the game is finished \n\nUtility function: Gives numerical value of terminal states. \n\nMAX uses a search tree to determine the next move. \n\n\n\nSearches using DFS \n\n\n\nRuntime: \n\nO(b^m) \n\nb is the number of legal moves at each node \n\nm is the maximum depth of the tree \n\n\n \n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Zero sum** - what is good for one player is just as bad for the other, there is no win-win outcome\n* **Terminal state** - state where game ends\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSP Problem is defined: \n\nState - set of variables/value pairs \n\nConditions - set of constraints on a variable \n\nconsists of three components: X (set of variables), D (set of domains), C (constraints that specify allowable combinations) \n\nThe problem is solved when each variable has a value that satisfies all the constraints on the variable.\n\nCompared to regular search problems CSP states are not black box, agent can see inside the states and move between states accordingly \n\nA complete assignment - every variable is assigned and is consistent \n\nA partial assignment - some variables are unassigned but it is consistent. \n\n\nCSP is an NP-complete problem, and exists subproblems that can be solved very efficiently.\n\n\n\nPros: quickly prune large search places based on constraints.\n\nSimples kind of CSP: discrete, finite domains \n\nSpecial solution algorithm exists for linear constraints. For nonlinear constraints on integer variables—the problem is undecidable \n\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nconstraint propagation/inference: using the constraints to reduce the number of legal values for a variable. \nreduce the legal values for another variable.\n\n\nNode consistent: all the values in the variable’s domain satisfy the variable’s unary \nconstraints. graph is node-consistent if every variable in the graph is node-consistent\n\n\n\nArc consistent: every value in its domain satisfies the variable’s binary constraints.\n\nA graph is arc-consistent if every variable is arc consistent with every other variable. \n\n\n\nAC-3 - algorithm (for arc consistency):\n\nInitially, queue contains all arcs in the CSP .(Each binary constraint becomes two arcs, one in each direction.)\n\nPop (Xi ,Xj) from queue and make Xi consistent to Xj\n\nIf something changed, add all neighbour arcs to the queue\n\no/w move to the next arc\n\n\nComplexity: \n\n# of variables - n \n\nSize of domain - d  \n\nArcs/binary constraints - c \n\n\n\nEach arc is inserted in the queue at most d times. Checking consistency - O(d^2). Overall - O(cd^2) \n\n\nPath Consistency: \n\nPath consistency is inferred by triples of variables. Considers two arc at a time. \n\n\nK-consistency: \n\nA CSP is k-consistent if, for any set of k−1 variables and for any consistent assignment to those variables,\n a consistent value can always be assigned to any kth variable \n\n\nNode consistency = 1-consistency \n\nArc consistency = 2-consistency \n\nPath consistency = 3-consistency \n\n\nA CSP is strongly k-consistent if it is k-consistent and is also k-1-consistent, \nk-2- consistent, all the way down to 1-consistent. Runtime: O(n^2d) \n\nWorst case runtime: exponential in n, space is also exponential in n \n\n\n\n\nGlobal constraint is one involving an arbitrary number of variables (but not necessarily all variables) \n\nAlldiff: if variables are involved in the constraint, and if they have possible distinct values altogether, and , \nthen the constraint cannot be satisfied \n\n\nThis leads to the following simple algorithm: First, remove any variable in the constraint that has a singleton domain, and delete \nthat variable’s value from the domains of the remaining variables. Repeat as long as there are singleton variables. If at any point an \nempty domain is produced or there are more variables than domain values left, then an inconsistency has been detected. \n\n\n\n\n\n\nhigher-order constraint is the resource constraint, sometimes called the Atmost constraint. Ex: some of Xs is less than 10 \n\n\nWe say that a CSP is bounds-consistent if for every variable X, and for both the lowerbound and upper-bound values of X ,\n there exists some value of Y that satisfies the constraint between X and Y for every variable . This kind of bounds propagation \n is widely used in practical constraint problems.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\nDomain size: d \n\nAll complete assignment - leaf nodes at depth n \n\nBranching factor - nd. Nex level (n-1)d .. \n\nTotal #of leaves: n!d^n \n\n\nminimum-remaining-values (MRV) heuristic - choosing the variable with the fewest “legal” values \n\n\n\ndegree heuristic -  attempts to reduce the branching factor on future choices by selecting the variable with the largest number of constraints \n\n\n\nLeast-constraining-value heuristic - chooses the value that rules out the fewest values for neighboring variables \n\n\n\nIn general: heuristic is trying to leave the maximum flexibility for subsequent variable assignments. Choses the ones that will fail first to have less to backtrack on. \n\nforward checking: \n\n\n\nIn forward checking, whenever a variable X is assigned, we establish arc consistency for X For each unassigned variable Y that is connected to X by a constraint,\n delete from Y's domain any value that is inconsistent with the value chosen for X.\n\n\n\n\n detects the inconsistency earlier than simple backtracking and thus it allows branches of the search tree that will lead to failure to be pruned earlier  than with simple backtracking.\n\ndoes not detect all inconsistencies because it doesn’t look ahead far enough\\ \n\n\n\nMAC (for Maintaining Arc Consistency): \n\ndetects inconsistencies. \n\nRecursively propagate constraints when changes are made to the domain of variables.(unlike forward checking) \n\nif we assign X, forward checking makes all the arcs incident on X consistent. MAC does this, and if the domain of a variable Y changes, does the same for Y (and so on...)\n\nchronological backtracking: back up to the preceding variable and try a different value for it \n\n\n\nconflict set for X is set of assignments that are in conflict with X \n\nbackjumping search method backtracks to the most recent assignment in the conflict set. A backjumping algorithm that uses conflict sets defined in this way is called conflict-directed backjumping\n\n\nConstraint learning - caches the conflicts (no goods) as they are encountered in the search in order to avoid the same conflict later \n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nMin-conflict heuristic - select the value that results in the minimum number of conflicts with other variables \n\n\n\ntabu search - keeping a small list of recently visited states and forbidding the algorithm to return to those states \n\n\n\nconstraint weighting -  constraints are given a numeric weight, initially all 1. At each step of the search, \n\n the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. \n\n The weights are adjusted by incrementing the weight of each constraint that is violated by the current assignment. \n\nPros: (1) adds topography, making sure that it is possible to improve from the current state \n\n(2) adds learning: over time the difficult constraints are assigned higher weights \n\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n\nAny tree-structured CSP can be solved in time linear in the number of variables \n\n\n\nDirectional arc consistency or DAC - A CSP is defined to be directional arc-consistent under an ordering of variables X1, X2, .. \nif and only if every Xi is arc-consistent with each Xj for j > i \n\n\n\nCutset conditioning: \n\nAlgorithm: \n\nChoose a subset S of the variables s.t. constraint graph becomes a tree after removal of S. this is called a cycle cutset. \n\nFor each possible assignment to the variables in S that satisfies all constraints on S, \n\n remove from the domains of the remaining variables any values that are inconsistent with the assignment for S, and \n\nif the remaining CSP has a solution, return it together with the assignment for S \n\nRuntime is O(d^c (n − c)d^2 ). Works well the graph is nearly tree. Otherwise not more efficient than solving CSP directly. \n\n\n\nTree decomposition: \n\ntransform the CSP into a tree of subproblems.  \n\nRules: \n\nEvery variable in the original problem appears in at least one of the tree nodes.  \n\nIf two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the tree nodes. \n\nIf a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. \n\n\n\nRuntime: O(nd^2), n number of tree nodes and d - size of largest domain.\n\nEfficient if the tree width of the constraint graph is small.\n\n\n\nCSPs with constraint graphs of bounded tree width are solvable in polynomial time.\n\n\n\nCutset conditioning can be executed in linear memory, while tree decomposition requries memory exponential in the tree width w \n\n \n\n## Module 6 Lecture Notes\n \nCSP as search problem: \n\nInitial State: the empty assignment {}. \n\nSuccessor function: Assign value to any unassigned variable provided that there is not a constraint conflict. \n\nGoal test: the current assignment is complete. \n\nPath cost: a constant cost for every step. \n\n\nSolution always at depth n, can use dfs. \n\n\nThe AC-3/ waltz algorithm: \n\nBy iterating over the graph, the arc- consistency constraints can be propagated along arcs of the graph \n\nSearch: Use constraints to add labels to find one solution \n\nConstraint Propagation: Use constraints to eliminate labels to simultaneously find all solutions \n\nAlgorithm: \n\nAssign every node in the constraint graph a set of all possible values \n\nRepeat until there is no change in the set of values associated with any node: \n\nFor each node i: \n\n4. For each neighboring node j in the picture: \n\n5. Remove any value from i which is not arc consistent with j \n\n\nWorst case complexity: O(n^2d^3) \n\nFor planar constraint graphs, the number of arcs can only be linear in N and the time complexity is only O(nd^3) \n\n \n\n## Module 6 Definitions\n* **Disjunctive constraint** - either x1 or x2\n* **Precedence constraints** - x1 needs to come before x2\n* **Unary constraint** - single variable\n* **Binary constraint** - 1 or 2v aribales\n* **Global constraint** - arbitrary num of variables\n* **Symmetry-breaking constraint** - arbitrary ordering constraints to remove redundancy and ensure only one solution is possible.\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n \nCan reason in addition to internal knowledeg \n\n\nKB consists of sentences in the representation language \n\n• Representation language has a syntax that specifies sentences that are well-formed \n\n• A logic defines the semantics of the sentences, which is their meaning \n\n• The semantics defines the truth of each sentence with respect to a possible world,\nwhich we will often call a model.\n  \n\nM(a) set of all models of a \n\n\nAtomic sentences are represented with a single propositional symbols \n\nPropositional symbols - statement that can be true or false \n\n\n~ not \n\n⋀ and \n\n⋁ or \n\n\nEntailment - logical inference \n\n\nSound – the inference algorithm should only derive entailed sentences. \n\nComplete – an inference algorithm is complete if it can derive all sentences that are\nentailed \n\n\nLogical equivalece: \n\n(A ⋀ B) ≡ (B ⋀ A) Commutativity of ⋀ \n\n(A ⋁ B) ≡ (B ⋁ A) Commutativity of ⋁ \n\n((A ⋀ B) ⋀ C) ≡ (A ⋀ (β ⋀ C)) Associativity of ⋀ \n\n((A ⋁ B) ⋁ C) ≡ (A ⋁ (B ⋁ C)) Associativity of ⋁ \n\n¬ (¬ A) ≡ A Double-negation elimination \n\n(A ⟹ B) ≡ (¬B ⟹ ¬A) Contraposition \n\n(A ⟹ B) ≡ (¬A ⋁ B) Implication elimination \n\n(A ⇔ B) ≡ ((A ⟹ B) ⋀ (B ⟹A)) Biconditional elimination \n\n¬(A ⋀ B) ≡ (¬A ⋁ ¬B) De Morgan \n\n¬(A ⋁ B) ≡ (¬A ⋀ ¬B) De Morgan \n\n((A ⋀ B) ⋁ C) ≡ ((A ⋀ B) ⋁ (A ⋀ C))) or  ((A ⋁ C) ⋀ (B ⋁ C)) Distributivity of ⋀ over ⋁ \n\n((A ⋁ B) ⋀ C) ≡ ((A ⋁ B) ⋀ (A ⋁ C))) Distributivity of ⋁ over ⋀ \n\n\n\nConjunctive Normal Form (CNF) \n\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses. \n\nClauses are disjunctions of literals. \n\n1. Eliminate ⇔ by replacing A ⇔ β with (A ⟹ β) ⋀ (β ⟹A) \n\n2. Eliminate ⟹ by replacing A ⟹ β with ¬A ⋁ β \n\n3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules \n\n4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply\ndistributivity law to distribute ⋁ over ⋀ wherever possible.  \n\n\nInference procedures based on resolution work using the principle of proof by\ncontradiction. \n\nTo show KB⊨A then we can show that KB ⋀ ¬A is unsatisfiable. \n\nHere’s how: \n\n• First, convert (KB ⋀ ¬A) into CNF \n\n• Then apply the resolution rule to the resulting clauses. \n\n• Resolve every pair that contains complementary literals to produce a new clause \n\n• If that new clause isn’t already present, then add it to the set. \n\n• Continue the process until one of two things happens: \n\n1. There are no new clauses that can be added. In this case, the KB does not entail A \n\n2. Two clauses resolve to yield the empty clause, in which case the KB does entail A \n\n\nResolution algorithm is complete \n\n\n\nDefinite clause – disjunction of literals where exactly one is positive \n\n• Horn clause – disjunction of literals where at most one is positive \n\n• This includes definite clauses \n\n• And clauses with no positive literals \n\nHorn clauses are closed under resolution. If you apply resolution to a horn clause, you\nget back a horn clause. \n\n\nDeciding entailment wit corn clauses can be done in linear time\n\n\n## Module 7 Definitions\n* **Axioms** - a sentence that is given\n* **Derived sentences** - a new sentence that is derived from others sentences\n* **Inference** - The process of deriving new sentences from old sentences\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}