{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for 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": "d8b15813-7379-4138-b0e3-6ebe83ddbecb"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4752c245-bc09-4936-d17b-9f9c82f95b0d"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"Sharanya Venkat\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" 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 = \"\"\" \n",
        "-weak AI—the idea that machines could act as if they were intelligent \n",
        "-strong AI—the assertion that machines that do so are actually consciously thinking (not just simulating thinking).\n",
        "-Measuring AI: Turing test(if agent fools 30% of the time), Games like Go, StarCraft 2 etc.\n",
        "\n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "An agent is anything that perceives its environment through sensors and can act on its environment through actuators\n",
        "\n",
        "- percept:  content an agent’s sensors are perceiving. \n",
        "- An agent’s percept sequence is the complete history of everything the agent has ever perceived.\n",
        "- Mathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action.\n",
        "The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system.\n",
        "- The agent program runs on the physical architecture to produce f (agent function)\n",
        "\n",
        "A rational agent is an agent that perceives its environment and and behaves rationally. For each possible percept sequence P a rational agent selects an action a to maximize the expected value of its performance measure\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "What is rational at any given time depends on four things:\n",
        "- The performance measure that defines the criterion of success.\n",
        "- The agent’s prior knowledge of the environment.\n",
        "- The actions that the agent can perform.\n",
        "- The agent’s percept sequence to date.\n",
        "\n",
        "Doing actions in order to modify future percepts—sometimes called information gathering —is an important part of rationality.\n",
        "\n",
        "A second example of information gathering is provided by the exploration that must be undertaken by a vacuum-cleaning agent in an initially unknown environment.\n",
        "\n",
        "Our definition requires a rational agent not only to gather information but also to learn as much as possible from what it perceives.\n",
        "\n",
        "To the extent that an agent relies on the prior knowledge of its designer rather than on its own percepts and learning processes, we say that the agent lacks autonomy. A rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge.\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "To design a rational agent we need to specify a task environment\n",
        "- a problem specification for which the agent is a solution\n",
        "\n",
        "PEAS: to specify a task environment\n",
        "- Performance measure\n",
        "- Environment\n",
        "- Actuators\n",
        "- Sensors \n",
        "\n",
        "\n",
        "Properties of Task Environments:\n",
        "\n",
        "1. FULLY vs PARTIALLY OBSERVABLE: If the agent has no sensors at all then the environment is unobservable.\n",
        "\n",
        "2. SINGLE-AGENT VS. MULTIAGENT: Multiagent can be competitive(chess) or cooperative(taxi driver), partially competitive(taxi driver searching for a parking spot).\n",
        "\n",
        "3. DETERMINISTIC VS NON DETERMINISTIC: If the next state of the environment is completely determined by the current state and the action executed by the agent(s), then we say the environment is deterministic; otherwise, it is nondeterministic.\n",
        "\n",
        "4. EPISODIC VS. SEQUENTIAL: In episodic, every episode is atomic and independent of the previous episode.Examples of sequential - Chess and taxi driving are sequential\n",
        "\n",
        "5. STATIC vs DYNAMIC: If the environment can change while an agent is deliberating, then we say the environment is dynamic(taxi driver) for that agent; otherwise, it is static (crossword puzzle). If the environment itself does not change with the passage of time but the agent’s performance score does, then we say the environment is semi dynamic (chess with clock).\n",
        "\n",
        "6. DISCRETE VS. CONTINUOUS: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent. For example, the chess environment has a finite number of distinct states (excluding the clock). Chess also has a discrete set of percepts and actions. Taxi driving is a continuous-state and continuous-time problem.\n",
        "\n",
        "6. KNOWN VS. UNKNOWN: Strictly speaking, this distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of the environment.\n",
        "\n",
        "Experiments are often carried out not for a single environment but for many environments drawn from an environment class. For example, to evaluate a taxi driver in simulated traffic, we would want to run many simulations with different traffic, lighting, and weather conditions. We are then interested in the agent’s average performance over the environment class.\n",
        "​​It is quite possible for a known environment to be partially observable—for example, in solitaire card games. Conversely, an unknown environment can be fully observable—in a new video game, the screen may show the entire game state but I still don’t know what the buttons do until I try them.\n",
        "Experiments are often carried out not for a single environment but for many environments drawn from an environment class. For example, to evaluate a taxi driver in simulated traffic,\n",
        "\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "f50f503e-30a6-479a-8a78-d74026fdf44d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n \n-weak AI—the idea that machines could act as if they were intelligent \n-strong AI—the assertion that machines that do so are actually consciously thinking (not just simulating thinking).\n-Measuring AI: Turing test(if agent fools 30% of the time), Games like Go, StarCraft 2 etc.\n\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n \nAn agent is anything that perceives its environment through sensors and can act on its environment through actuators\n\n- percept:  content an agent’s sensors are perceiving. \n- An agent’s percept sequence is the complete history of everything the agent has ever perceived.\n- Mathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action.\nThe agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system.\n- The agent program runs on the physical architecture to produce f (agent function)\n\nA rational agent is an agent that perceives its environment and and behaves rationally. For each possible percept sequence P a rational agent selects an action a to maximize the expected value of its performance measure\n\n\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nWhat is rational at any given time depends on four things:\n- The performance measure that defines the criterion of success.\n- The agent’s prior knowledge of the environment.\n- The actions that the agent can perform.\n- The agent’s percept sequence to date.\n\nDoing actions in order to modify future percepts—sometimes called information gathering —is an important part of rationality.\n\nA second example of information gathering is provided by the exploration that must be undertaken by a vacuum-cleaning agent in an initially unknown environment.\n\nOur definition requires a rational agent not only to gather information but also to learn as much as possible from what it perceives.\n\nTo the extent that an agent relies on the prior knowledge of its designer rather than on its own percepts and learning processes, we say that the agent lacks autonomy. A rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge.\n \n\n## AIMA 2.3 The Nature of Environments\n \nTo design a rational agent we need to specify a task environment\n- a problem specification for which the agent is a solution\n\nPEAS: to specify a task environment\n- Performance measure\n- Environment\n- Actuators\n- Sensors \n\n\nProperties of Task Environments:\n\n1. FULLY vs PARTIALLY OBSERVABLE: If the agent has no sensors at all then the environment is unobservable.\n\n2. SINGLE-AGENT VS. MULTIAGENT: Multiagent can be competitive(chess) or cooperative(taxi driver), partially competitive(taxi driver searching for a parking spot).\n\n3. DETERMINISTIC VS NON DETERMINISTIC: If the next state of the environment is completely determined by the current state and the action executed by the agent(s), then we say the environment is deterministic; otherwise, it is nondeterministic.\n\n4. EPISODIC VS. SEQUENTIAL: In episodic, every episode is atomic and independent of the previous episode.Examples of sequential - Chess and taxi driving are sequential\n\n5. STATIC vs DYNAMIC: If the environment can change while an agent is deliberating, then we say the environment is dynamic(taxi driver) for that agent; otherwise, it is static (crossword puzzle). If the environment itself does not change with the passage of time but the agent’s performance score does, then we say the environment is semi dynamic (chess with clock).\n\n6. DISCRETE VS. CONTINUOUS: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent. For example, the chess environment has a finite number of distinct states (excluding the clock). Chess also has a discrete set of percepts and actions. Taxi driving is a continuous-state and continuous-time problem.\n\n6. KNOWN VS. UNKNOWN: Strictly speaking, this distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of the environment.\n\nExperiments are often carried out not for a single environment but for many environments drawn from an environment class. For example, to evaluate a taxi driver in simulated traffic, we would want to run many simulations with different traffic, lighting, and weather conditions. We are then interested in the agent’s average performance over the environment class.\n​​It is quite possible for a known environment to be partially observable—for example, in solitaire card games. Conversely, an unknown environment can be fully observable—in a new video game, the screen may show the entire game state but I still don’t know what the buttons do until I try them.\nExperiments are often carried out not for a single environment but for many environments drawn from an environment class. For example, to evaluate a taxi driver in simulated traffic,\n\n\n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "fdf3a87d-f300-43fa-deaa-d5a24c4f50ef"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" When the correct action to take is not immediately obvious, an agent may need to to plan ahead: to consider a sequence of actions that form a path to a goal state. Such an agent is called a problem-solving agent, and the computational process it undertakes is called search.\n",
        "\n",
        "environment considered: **episodic, single agent, fully observable, deterministic, static, discrete, and known**.\n",
        "\n",
        "informed algorithms : agent can estimate how far it is from the goal\n",
        "uninformed algorithms : no such estimate is available. An uninformed search algorithm is given no clue about how close a state is to the goal(s).\n",
        "\n",
        "Agent follows a 4 phase problem solving process :\n",
        "- Goal Formulation \n",
        "- Problem Formulation - The agent devises a description of the states and actions nec- essary to reach the goal\n",
        "- Search - Agent tries to find a sequence of actions that reaches the goal - this seq is called solution\n",
        "- Execution - Agent executes actions in the solution\n",
        "\n",
        "It is an important property that in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions\n",
        "\n",
        "Formal Definition of a Search Problem :\n",
        "1. State Space : A set of possible states that the environment can be in\n",
        "2. Initial state\n",
        "3. Set of one or more goal states\n",
        "4. Actions available to the agent - given a particular state set of actions that are legal in that state\n",
        "5. Transition model : Returns what each action does. RESULT(s, a) returns the\n",
        "state that results from doing action a in state s.\n",
        "6. Performance measure/ action cost func \n",
        "7. Goal test \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" \n",
        "A standardized problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms.\n",
        "\n",
        "A real-world problem, such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data.\n",
        "\n",
        "Absolute movements: movement direction acc to viewer\n",
        "\n",
        "Egocentric: movement direction acc to the robot\n",
        "\n",
        "Standardized problems: grid world, sokoban puzzle, sliding tile puzzle\n",
        "\n",
        "Real world problems: Route finding, touring problems, travelling salesperson, VLSI layout, robot navigation, automatic assembly sequence\n",
        "\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" A search algorithm takes a search problem as input and returns a solution, or an indication of failure.\n",
        "\n",
        "Each node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions. The root of the tree corresponds to the initial state of the problem.\n",
        "\n",
        "Three kinds of queues are used in search algorithms:\n",
        "\n",
        "- A priority queue first pops the node with the minimum cost according to some evaluation function, f . It is used in best-first search.\n",
        "- A FIFO queue or first-in-first-out queue first pops the node that was added to the queue first; we shall see it is used in breadth-first search.\n",
        "- A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most recently added node; we shall see it is used in depth-first search.\n",
        "\n",
        "We call a search algorithm a **graph search if it checks for redundant paths** and a **tree-like search if it does not check**.\n",
        "\n",
        "**Graph search is more memory intensive than tree search as it keeps track of redundant paths.**\n",
        "\n",
        "**Graph search is faster than tree search.**\n",
        "\n",
        "\n",
        "We can evaluate an algorithm’s performance in four ways:\n",
        "\n",
        "- Completeness: Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not?\n",
        "- Cost optimality: Does it find a solution with the lowest path cost of all solutions?\n",
        "- Time complexity: How long does it take to find a solution? This can be measured in seconds, or more abstractly by the number of states and actions considered.\n",
        "- Space complexity: How much memory is needed to perform the search?\n",
        "\n",
        "- **BFS**\n",
        "\n",
        "    When all actions have the same cost, an appropriate strategy is breadth-first search, in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on.\n",
        "\n",
        "    Queue used : FIFO\n",
        "\n",
        "    Properties :\n",
        "        - Optimal : if all actions have the same cost. Else its not optimal \n",
        "        - Complete \n",
        "        - Time complexity is O(b^d) \n",
        "        - Space complecity is O(b^d) \n",
        "\n",
        "    The memory requirements are a bigger problem for breadth-first search than the execution time. In general, exponential-complexity search problems cannot be solved by uninformed search for any but the smallest instances.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "\n",
        "- **DFS**\n",
        "\n",
        "    Depth-first search always expands the deepest node in the frontier first.\n",
        "    However, it is usually implemented not as a graph search but as a tree-like search that does not keep a table of reached states.\n",
        "    \n",
        "    Properties :\n",
        "        - Not Optimal : Depth-first search is not cost-optimal; it returns the first solution it finds, even if it is not cheapest.\n",
        "        - Not complete : For finite and acyclic state spaces its complete but for In cyclic state spaces it can get stuck in an infinite loop.Finally, in infinite state spaces, depth- first search is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus, depth-first search is incomplete.\n",
        "        - Time complexity : O(b^m)\n",
        "        - Space Complexity : O(b*m) :\n",
        "    depth-first search has much smaller needs for memory. We don’t keep a reached table at all, and the frontier is very small\n",
        "\n",
        "- **Depth limited Search**\n",
        "\n",
        "    A version of depth-first search in which we supply a depth limit, l, and treat all nodes at depth l as if they had no successors. \n",
        "    Properties - \n",
        "        The time complexity is O(b^l) and the space complexity is O(bl).\n",
        "    Unfortunately, if we make a poor choice for l the algorithm will fail to reach the solution, making it incomplete again.\n",
        "\n",
        "- **Iterative Depth Limited Search**\n",
        "\n",
        "    Iterative deepening search solves the problem of picking a good value for l by trying all values: first 0, then 1, then 2, and so on—until either a solution is found, or the depth- limited search returns the failure\n",
        "\n",
        "    Properties :\n",
        "        - Complete\n",
        "        - Optimal\n",
        "        - Space Complexity - O(bd)\n",
        "        - The time complexity is O(b^d ) when there is a solution, or O(b^m ) when there is none\n",
        "    \n",
        "    In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and\n",
        "the depth of the solution is not known.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "- b = branching factor : max set of possible actions that you can take from any state or number of successors of a node that need to be considered.\n",
        "- d = depth : number of actions in an optimal solution\n",
        "- m = the maximum number of actions in any path\n",
        "\n",
        "Use depth-first if\n",
        "- Space is restricted\n",
        "- There are many possible solutions with long paths and wrong paths are usually terminated quickly\n",
        "- Search can be fine-tuned quickly\n",
        "\n",
        "Use breadth-first if\n",
        "- Possible infinite paths\n",
        "- Some solutions have short paths\n",
        "- Can quickly discard unlikely paths\n",
        "\n",
        "\n",
        "- **UCS or Dijkstra's algorithm**\n",
        "\n",
        "    When actions have different costs, an obvious choice is to use best-first search where the evaluation function is the cost of the path from the root to the current node. Pick the node that leads to least cost\n",
        "    Then the algorithm’s worst-case time and space complexity can be much greater than bfs . This is because uniform-cost search can explore large trees of actions with low costs before exploring paths involving a high-cost and perhaps useful action.\n",
        "\n",
        "    Properties :\n",
        "        - Optimal\n",
        "        - Complete\n",
        "\n",
        "- Backtracking :\n",
        "\n",
        "    A variant of depth-first search called backtracking search uses even less memory. (See Chapter 6 for more details.) In backtracking, only one successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next.\n",
        "    Reduces memory req from O(bm) to O(m)\n",
        "\n",
        "- Bidirectional Search\n",
        "\n",
        "    An alternative approach called bidirectional search simultaneously searches forward from the initial state and backwards from the goal state(s), hoping that the two searches will meet\n",
        "\n",
        "    The motivation is that O(b^d/2 + b^d/2) is much less than O(b^d) \n",
        "    Bidirectional search expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\n",
        "\n",
        "\"Open Loop\": \"when the environment is deterministic, and the agent has found a solution, it need not collect percept sequences while reaching the goal state.\",\n",
        "\n",
        "\"Closed Loop\": \"If there is a chance that the model is incorrect, or the environment is nondeterministic, then the agent would be safer using a closed-loop approach that monitors the percepts.\"\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"Problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
        "\"Reflex agent\" : \" selects an action based only on the current percept. It ignores the rest of the percept history.\",\n",
        "\"Path\" : \"sequence of actions\",\n",
        "\"Solution\" : \"path from initial state to goal state\",\n",
        "\"Optimal solution\" : \"has the lowest path cost among all solutions\",\n",
        "\"Search tree\" : \"a way of representing the paths that a search algorithm has explored\",\n",
        "\"Frontier\" : \"those states that are available for expanding (for applying legal actions to)\",\n",
        "\"early goal test\": \"checking whether a node is a solution as soon as it is generated\", \n",
        "\"late goal test\" : \"waiting until a node is popped off the queue\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "d428d663-c318-4cec-c5b1-68d7f3783235"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n When the correct action to take is not immediately obvious, an agent may need to to plan ahead: to consider a sequence of actions that form a path to a goal state. Such an agent is called a problem-solving agent, and the computational process it undertakes is called search.\n\nenvironment considered: **episodic, single agent, fully observable, deterministic, static, discrete, and known**.\n\ninformed algorithms : agent can estimate how far it is from the goal\nuninformed algorithms : no such estimate is available. An uninformed search algorithm is given no clue about how close a state is to the goal(s).\n\nAgent follows a 4 phase problem solving process :\n- Goal Formulation \n- Problem Formulation - The agent devises a description of the states and actions nec- essary to reach the goal\n- Search - Agent tries to find a sequence of actions that reaches the goal - this seq is called solution\n- Execution - Agent executes actions in the solution\n\nIt is an important property that in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions\n\nFormal Definition of a Search Problem :\n1. State Space : A set of possible states that the environment can be in\n2. Initial state\n3. Set of one or more goal states\n4. Actions available to the agent - given a particular state set of actions that are legal in that state\n5. Transition model : Returns what each action does. RESULT(s, a) returns the\nstate that results from doing action a in state s.\n6. Performance measure/ action cost func \n7. Goal test \n\n\n\n\n## AIMA Chapter 3.2 Example Problems\n \nA standardized problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms.\n\nA real-world problem, such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data.\n\nAbsolute movements: movement direction acc to viewer\n\nEgocentric: movement direction acc to the robot\n\nStandardized problems: grid world, sokoban puzzle, sliding tile puzzle\n\nReal world problems: Route finding, touring problems, travelling salesperson, VLSI layout, robot navigation, automatic assembly sequence\n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n A search algorithm takes a search problem as input and returns a solution, or an indication of failure.\n\nEach node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions. The root of the tree corresponds to the initial state of the problem.\n\nThree kinds of queues are used in search algorithms:\n\n- A priority queue first pops the node with the minimum cost according to some evaluation function, f . It is used in best-first search.\n- A FIFO queue or first-in-first-out queue first pops the node that was added to the queue first; we shall see it is used in breadth-first search.\n- A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most recently added node; we shall see it is used in depth-first search.\n\nWe call a search algorithm a **graph search if it checks for redundant paths** and a **tree-like search if it does not check**.\n\n**Graph search is more memory intensive than tree search as it keeps track of redundant paths.**\n\n**Graph search is faster than tree search.**\n\n\nWe can evaluate an algorithm’s performance in four ways:\n\n- Completeness: Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not?\n- Cost optimality: Does it find a solution with the lowest path cost of all solutions?\n- Time complexity: How long does it take to find a solution? This can be measured in seconds, or more abstractly by the number of states and actions considered.\n- Space complexity: How much memory is needed to perform the search?\n\n- **BFS**\n\n    When all actions have the same cost, an appropriate strategy is breadth-first search, in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on.\n\n    Queue used : FIFO\n\n    Properties :\n        - Optimal : if all actions have the same cost. Else its not optimal \n        - Complete \n        - Time complexity is O(b^d) \n        - Space complecity is O(b^d) \n\n    The memory requirements are a bigger problem for breadth-first search than the execution time. In general, exponential-complexity search problems cannot be solved by uninformed search for any but the smallest instances.\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n\n- **DFS**\n\n    Depth-first search always expands the deepest node in the frontier first.\n    However, it is usually implemented not as a graph search but as a tree-like search that does not keep a table of reached states.\n    \n    Properties :\n        - Not Optimal : Depth-first search is not cost-optimal; it returns the first solution it finds, even if it is not cheapest.\n        - Not complete : For finite and acyclic state spaces its complete but for In cyclic state spaces it can get stuck in an infinite loop.Finally, in infinite state spaces, depth- first search is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus, depth-first search is incomplete.\n        - Time complexity : O(b^m)\n        - Space Complexity : O(b*m) :\n    depth-first search has much smaller needs for memory. We don’t keep a reached table at all, and the frontier is very small\n\n- **Depth limited Search**\n\n    A version of depth-first search in which we supply a depth limit, l, and treat all nodes at depth l as if they had no successors. \n    Properties - \n        The time complexity is O(b^l) and the space complexity is O(bl).\n    Unfortunately, if we make a poor choice for l the algorithm will fail to reach the solution, making it incomplete again.\n\n- **Iterative Depth Limited Search**\n\n    Iterative deepening search solves the problem of picking a good value for l by trying all values: first 0, then 1, then 2, and so on—until either a solution is found, or the depth- limited search returns the failure\n\n    Properties :\n        - Complete\n        - Optimal\n        - Space Complexity - O(bd)\n        - The time complexity is O(b^d ) when there is a solution, or O(b^m ) when there is none\n    \n    In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and\nthe depth of the solution is not known.\n\n \n\n## Module 3 Lecture Notes\n \n- b = branching factor : max set of possible actions that you can take from any state or number of successors of a node that need to be considered.\n- d = depth : number of actions in an optimal solution\n- m = the maximum number of actions in any path\n\nUse depth-first if\n- Space is restricted\n- There are many possible solutions with long paths and wrong paths are usually terminated quickly\n- Search can be fine-tuned quickly\n\nUse breadth-first if\n- Possible infinite paths\n- Some solutions have short paths\n- Can quickly discard unlikely paths\n\n\n- **UCS or Dijkstra's algorithm**\n\n    When actions have different costs, an obvious choice is to use best-first search where the evaluation function is the cost of the path from the root to the current node. Pick the node that leads to least cost\n    Then the algorithm’s worst-case time and space complexity can be much greater than bfs . This is because uniform-cost search can explore large trees of actions with low costs before exploring paths involving a high-cost and perhaps useful action.\n\n    Properties :\n        - Optimal\n        - Complete\n\n- Backtracking :\n\n    A variant of depth-first search called backtracking search uses even less memory. (See Chapter 6 for more details.) In backtracking, only one successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next.\n    Reduces memory req from O(bm) to O(m)\n\n- Bidirectional Search\n\n    An alternative approach called bidirectional search simultaneously searches forward from the initial state and backwards from the goal state(s), hoping that the two searches will meet\n\n    The motivation is that O(b^d/2 + b^d/2) is much less than O(b^d) \n    Bidirectional search expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\n\n\"Open Loop\": \"when the environment is deterministic, and the agent has found a solution, it need not collect percept sequences while reaching the goal state.\",\n\n\"Closed Loop\": \"If there is a chance that the model is incorrect, or the environment is nondeterministic, then the agent would be safer using a closed-loop approach that monitors the percepts.\"\n\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Reflex agent** -  selects an action based only on the current percept. It ignores the rest of the percept history.\n* **Path** - sequence of actions\n* **Solution** - path from initial state to goal state\n* **Optimal solution** - has the lowest path cost among all solutions\n* **Search tree** - a way of representing the paths that a search algorithm has explored\n* **Frontier** - those states that are available for expanding (for applying legal actions to)\n* **Early goal test** - checking whether a node is a solution as soon as it is generated\n* **Late goal test** - waiting until a node is popped off the queue\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "Informed search strategy—one that uses domain-specific hints about the location of goals—can find solutions more efficiently than an uninformed strategy. \n",
        "The hints come in the form of a heuristic function, denoted h(n)\n",
        "\n",
        "**Greedy Best first search**\n",
        "\n",
        "form of best-first search that expands first the node with the lowest h(n) value—the node that appears to be closest to the goal—on the grounds that this is likely to lead to a solution quickly. f (n) = h(n).\n",
        "\n",
        "**A star search**\n",
        "\n",
        "f (n) = g(n) + h(n)\n",
        "where g(n) is the path cost from the initial state to node n, and h(n) is the estimated cost of\n",
        "the shortest path from n to a goal state, so we have\n",
        "    f (n) = estimated cost of the best path that continues from n to a goal.\n",
        "\n",
        "Properties - \n",
        "    - A* is complete\n",
        "    - A* optimality depends on if the heuristic is admissible or not. admissible = optimal\n",
        "\n",
        "**Admissibility** - an admissible heuristic is one that never overestimates the cost to reach a goal. (An admissible heuristic is therefore optimistic.\n",
        "\n",
        "**Consistency** - A slightly stronger property is called consistency. A heuristic h(n) is consistent if, for every node n and every successor n′ of n generated by an action a, we have:\n",
        "h(n) ≤ c(n,a,n′)+h(n′). This is a form of the triangle inequality, which stipulates that a side of a triangle cannot be longer than the sum of the other two sides\n",
        "\n",
        "**Every consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A∗ is cost-optimal**\n",
        "\n",
        "**A* Prunes** : A∗ is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.\n",
        "\n",
        "**f(n) is monotonically increasing iff the heuristic is consistent.**\n",
        "\n",
        "**Satisficing search** - \n",
        "\n",
        "A∗ search has many good qualities, but it expands a lot of nodes. We can explore fewer nodes (taking less time and space) if we are willing to accept solutions that are suboptimal, but are “good enough”—what we call satisficing solutions. If we allow A∗ search to use an inadmissible heuristic—one that may overestimate—then we risk missing the optimal solution, but the heuristic can potentially be more accurate, thereby reducing the number of\n",
        "nodes expanded. \n",
        "\n",
        "**weighted A∗ search** : we weight the heuristic value more heavily, giving us the evaluation function f (n) = g(n) + W × h(n), for some W > 1.\n",
        "\n",
        "In (a), an A∗ search finds the optimal solution, but has to explore a large portion of the state space to find it. In (b), a weighted A∗ search finds a solution that is slightly costlier, but the search time is much faster.\n",
        "\n",
        "\n",
        "Suboptimal Search Algos : \n",
        "\n",
        "1. Bounded suboptimal Search - look for solution that is guaranteed to be within a constant factor W of the optimal cost\n",
        "2. Bounded Cost Search - look for solutions whose cost is less than 'C'\n",
        "3. Unbounded cost search - accept any solution of any cost as long as you find it fast\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "\n",
        "Main issue with A* - > Use of memory \n",
        "\n",
        "Implementation tricks to save space : \n",
        "\n",
        "Memory is split between frontier and reached. Usually frontier is very small comparable to reached but we can use only 1 of these structures to save space. For making our A* efficient, We can keep reference counts of the number of times a state has been reached, and remove it from the reached table when there are no more ways to reach the state.\n",
        "\n",
        "\n",
        "Memory Bounded Search:\n",
        "\n",
        "1. Beam search :  limits the size of the frontier. The easiest approach is to keep only the k nodes with the best f-scores, discarding any other expanded nodes. Incomplete and suboptimal but with a good 'k' algorithm is faster and can find \"near optimal\" solutions\n",
        "\n",
        "2. Iterative Deepening A* search: Gives benefits of A* without having to keep all reached states in memory. Used for problems that dont fit in memory. The cut off isn't depth here, the cut off is f-cost at each iteration.\n",
        "\n",
        "3. Recursive best-first search (RBFS) attempts to mimic the operation of standard best-first search, but using only linear space. RBFS resembles a recursive depth-first search, but rather than continuing indefinitely down the current path, it uses the f_limit variable to keep track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path.\n",
        "RBFS is optimal when h(n) is admissible.\n",
        "\n",
        "IDA* and RBFS use too little memory because they forget most of what they have explored -> both algorithms end up re-exploring the same states again and again\n",
        "\n",
        "MA* and SMA* : memory bounded and simplified memory bounded A* star\n",
        "\n",
        "SMA* proceeds just like A*, expanding the best leaf until memory is full. At this point, it cannot add a new node to the search tree without dropping an old one. SMA always drops the worst leaf node—the one with the highest f -value .\n",
        "SMA* is complete and optimal if there is a reachable solution(depth of goal node is less than memory size)\n",
        "\n",
        "Bidirectional A star:\n",
        "- Front to end: Hf estimates distance to goal and Hb estimates distance to other frontier.\n",
        "- Front to front: attempts to estimate the distance to the other frontier.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Heuristic\": \"estimated cost of the cheapest path from state at node n to goal state.\", \n",
        "\"relaxed problem\" : \"fewer restrictions on the actions than the original problem\",\n",
        "\"relaxed problem cost\" : \"The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0ed5dece-99a8-43c5-8601-89f841c416ca"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nInformed search strategy—one that uses domain-specific hints about the location of goals—can find solutions more efficiently than an uninformed strategy. \nThe hints come in the form of a heuristic function, denoted h(n)\n\n**Greedy Best first search**\n\nform of best-first search that expands first the node with the lowest h(n) value—the node that appears to be closest to the goal—on the grounds that this is likely to lead to a solution quickly. f (n) = h(n).\n\n**A star search**\n\nf (n) = g(n) + h(n)\nwhere g(n) is the path cost from the initial state to node n, and h(n) is the estimated cost of\nthe shortest path from n to a goal state, so we have\n    f (n) = estimated cost of the best path that continues from n to a goal.\n\nProperties - \n    - A* is complete\n    - A* optimality depends on if the heuristic is admissible or not. admissible = optimal\n\n**Admissibility** - an admissible heuristic is one that never overestimates the cost to reach a goal. (An admissible heuristic is therefore optimistic.\n\n**Consistency** - A slightly stronger property is called consistency. A heuristic h(n) is consistent if, for every node n and every successor n′ of n generated by an action a, we have:\nh(n) ≤ c(n,a,n′)+h(n′). This is a form of the triangle inequality, which stipulates that a side of a triangle cannot be longer than the sum of the other two sides\n\n**Every consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A∗ is cost-optimal**\n\n**A* Prunes** : A∗ is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.\n\n**f(n) is monotonically increasing iff the heuristic is consistent.**\n\n**Satisficing search** - \n\nA∗ search has many good qualities, but it expands a lot of nodes. We can explore fewer nodes (taking less time and space) if we are willing to accept solutions that are suboptimal, but are “good enough”—what we call satisficing solutions. If we allow A∗ search to use an inadmissible heuristic—one that may overestimate—then we risk missing the optimal solution, but the heuristic can potentially be more accurate, thereby reducing the number of\nnodes expanded. \n\n**weighted A∗ search** : we weight the heuristic value more heavily, giving us the evaluation function f (n) = g(n) + W × h(n), for some W > 1.\n\nIn (a), an A∗ search finds the optimal solution, but has to explore a large portion of the state space to find it. In (b), a weighted A∗ search finds a solution that is slightly costlier, but the search time is much faster.\n\n\nSuboptimal Search Algos : \n\n1. Bounded suboptimal Search - look for solution that is guaranteed to be within a constant factor W of the optimal cost\n2. Bounded Cost Search - look for solutions whose cost is less than 'C'\n3. Unbounded cost search - accept any solution of any cost as long as you find it fast\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n \n\nMain issue with A* - > Use of memory \n\nImplementation tricks to save space : \n\nMemory is split between frontier and reached. Usually frontier is very small comparable to reached but we can use only 1 of these structures to save space. For making our A* efficient, We can keep reference counts of the number of times a state has been reached, and remove it from the reached table when there are no more ways to reach the state.\n\n\nMemory Bounded Search:\n\n1. Beam search :  limits the size of the frontier. The easiest approach is to keep only the k nodes with the best f-scores, discarding any other expanded nodes. Incomplete and suboptimal but with a good 'k' algorithm is faster and can find \"near optimal\" solutions\n\n2. Iterative Deepening A* search: Gives benefits of A* without having to keep all reached states in memory. Used for problems that dont fit in memory. The cut off isn't depth here, the cut off is f-cost at each iteration.\n\n3. Recursive best-first search (RBFS) attempts to mimic the operation of standard best-first search, but using only linear space. RBFS resembles a recursive depth-first search, but rather than continuing indefinitely down the current path, it uses the f_limit variable to keep track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path.\nRBFS is optimal when h(n) is admissible.\n\nIDA* and RBFS use too little memory because they forget most of what they have explored -> both algorithms end up re-exploring the same states again and again\n\nMA* and SMA* : memory bounded and simplified memory bounded A* star\n\nSMA* proceeds just like A*, expanding the best leaf until memory is full. At this point, it cannot add a new node to the search tree without dropping an old one. SMA always drops the worst leaf node—the one with the highest f -value .\nSMA* is complete and optimal if there is a reachable solution(depth of goal node is less than memory size)\n\nBidirectional A star:\n- Front to end: Hf estimates distance to goal and Hb estimates distance to other frontier.\n- Front to front: attempts to estimate the distance to the other frontier.\n \n\n## Module 4 Definitions\n* **Heuristic** - estimated cost of the cheapest path from state at node n to goal state.\n* **Relaxed problem** - fewer restrictions on the actions than the original problem\n* **Relaxed problem cost** - The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\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",
        "Adversarial Search - Two or more agents have conflicting goals\n",
        "\n",
        "Game Environment - \n",
        "\n",
        "- Multiagent\n",
        "- Static : No change in environment when agent is delibearting\n",
        "- Discrete : Set of actions you take to transition from one state to another is finite\n",
        "- Fully observable : Complete state of environment is known\n",
        "- Strategic : Env is strategic in the sense that next state is determined by the current state and the action executed by the agent and the actions of the opponent\n",
        "\n",
        "What differentiates games from puzzles is that it is *strategic* and *multiagent*\n",
        "\n",
        "Key properties of games - \n",
        "\n",
        "- 2 players alternate moves\n",
        "- Zero sum : what is good for one player is bad for the other. There is no 'win-win' outcome\n",
        "- Clear set of legal moves\n",
        "- Well defined outcomes\n",
        "\n",
        "Most games in AI are \n",
        "1) Deterministic\n",
        "2) 2-player\n",
        "3) Perfect information (synonymous to fully observable)\n",
        "4) turn-talking\n",
        "5) Zero sum\n",
        "\n",
        "Most card games - Stochastic , not deterministic, not fully observable\n",
        "Most real-time games - Continuous rather than discrete\n",
        "\n",
        "**Game as a search** - A game can be formally defined with the following elements:\n",
        "\n",
        "- S0: The initial state, which specifies how the game is set up at the start.\n",
        "- TO-MOVE(s): The player whose turn it is to move in state s.\n",
        "- ACTIONS(s): The set of legal moves in state s.\n",
        "- RESULT(s, a): The transition model, which defines the state resulting from taking action a in state s.\n",
        "- IS-TERMINAL(s): A terminal test, which is true when the game is over and false otherwise. States where the game has ended are called terminal states.\n",
        "- UTILITY(s, p): A utility function (also called an objective function or payoff function), which defines the final numeric value to player p when the game ends in terminal state s.\n",
        "\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "Game Tree -\n",
        "root node : first position in which a decision should be made\n",
        "Eval func f : assigns a real values number to a board position (evaluates the goodness of the current state). Tells us 'how desirable is the current board position'\n",
        "Terminal nodes : represent the way the games could end labelled with the desirability of that ending\n",
        "\n",
        "MINIMAX Algorithm : \n",
        "\n",
        "basic idea : Make the best move for MAX assuming MIN always replies with the best move for MIN. Treat your opponent like a rational actor just like you are.\n",
        "\n",
        "Recursive process - the value at each node in the tree is determined by the value of its children\n",
        "- For a MAX node : backed-up value is the maximum values of its children \n",
        "- For a MIN node : backed up values is the minimum value of its children\n",
        "\n",
        "MINIMAX algorithm performs a complete DFS expansion of the game tree. If depth of tree is 'm' and there are 'b' legal moves\n",
        "\n",
        "- Time complexity : O(b^m)\n",
        "- Space complexity : O(bm)\n",
        "\n",
        "Exponential complexity of minimax makes it impractical for complex games. \n",
        "\n",
        "**Alpha - Beta Pruning :**\n",
        "\n",
        "Notion : Rather than searching the entire search space to fixed depth, we can get rid of branches if we know they wont be picked i.e prune parts of the tree that make no difference to the outcome.\n",
        "\n",
        "To figure out which branches can be prunes we add 2 values alpha and beta\n",
        "\n",
        "alpha : keeps track of MAX's current lower bound on MAX's outcome. Best value seen for MAX till now (at least)\n",
        "\n",
        "beta : keeps track of MIN's current upper bound on MIN's outcome. Best value seen for MIN till now (at most)\n",
        "\n",
        "**Move Ordering** - \n",
        "\n",
        "The effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. \n",
        "If all the worst successors are generated first, then we cant effectively prune the children of a node. If the best succesor had been generated first, then we could have pruned. \n",
        "This is called perfect move ordering where the best succesor is generated first so that the other bad successors can be pruned away. \n",
        "If this could be done perfectly, alpha–beta would need to examine only O(b^m/2) nodes to pick the best move, instead of O(b^m) for minimax. Put another way, alpha– beta with perfect move ordering can solve a tree roughly twice as deep as minimax in the same amount of time.\n",
        "\n",
        "We can't achieve perfect move ordering but we can get fairly close. Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the theoretical limit.\n",
        "killer move heuristic : the best moves are called killer moves so try these first before the rest. \n",
        "In game tree search, repeated states can occur because of *transpositions* —different permutations of the move sequence that end up in the same position, and the problem can be addressed with a *transposition table* that caches the heuristic value of states.\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "\n",
        "**Heuristic - Alpha Beta tree search**\n",
        "\n",
        "To make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal. In other words, we replace the UTILITY function with EVAL, which estimates a state’s utility. We also replace the terminal test by a cutoff test, which must return true for terminal states, but is otherwise free to decide when to cut off the search, based on the search depth and any property of the state that it chooses to consider. That gives us the formula H-MINIMAX(s, d) for the heuristic minimax value of state s at search depth d:\n",
        "\n",
        "1) EVAL instead of UTILITY\n",
        "A heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state s to player p, return an estimate of the distance to the goal.\n",
        "\n",
        "For terminal states it must be that EVAL(s, p) = UTILITY (s, p)\n",
        "For non-terminal states the evaluation must be somewhere in between a loss and a win. UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p).\n",
        "\n",
        "2) IS-CUTOFF instead of IS-TERMINAL\n",
        "\n",
        "\n",
        "Expected Value : averaging\n",
        "\n",
        "Material Value : assigning a value to the pawns in chess (for example)\n",
        "\n",
        "Weighted Function: weighted linear function\n",
        "\n",
        "Cutting Off Search: modifying alpha beta to cut off at non terminal states.\n",
        "\n",
        "These simple approaches can lead to errors due to the approximate nature of the evaluation function.\n",
        "\n",
        "The evaluation function should be applied only to positions that are **quiescent** —that is, positions in which there is no pending move (such as a capturing the queen) that would wildly swing the evaluation.\n",
        "\n",
        "**The horizon effect**\n",
        "\n",
        "more difficult to eliminate. It arises when the program is facing an opponent’s move that causes serious damage and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics.\n",
        "One strategy to mitigate the horizon effect is to allow singular extensions, moves that are “clearly better” than all other moves in a given position, even when the search would normally be cut off at that point.\n",
        "\n",
        "**Forward Pruning** : Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good ones. Thus, the strategy saves computation time at the risk of making an error.\n",
        "This can be done using:\n",
        "\n",
        "- Beam search: consider only a “beam” of the n best moves\n",
        "- ProbCut: uses statistics gained from prior experience to lessen the chance that the best move will be pruned.\n",
        "- Another technique, late move reduction, works under the assumption that move ordering has been done well, and therefore moves that appear later in the list of possible moves are less likely to be good moves.\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic games bring us a little closer to the unpredictability of real life by including a random element, such as the throwing of dice \n",
        "So far we know the oponent was going to make the most optimal move so we knew we were dealing with a fixed outcome. But in certain games the outcome is uncertain. Uncertain outcomes are controlled by chance -> not an adversary\n",
        "\n",
        "idea : We dont know what the result of an action can be because of 1) explicit randomness (rolling dice) 2) unpredictable opponents (opponents aren't optimal) 3) actions can fail\n",
        "\n",
        "So, Here MAX nodes remain the same as MINI-MAX algorithm. MIN node is now a \"chance\" node -> outcome is uncertain here. \n",
        "So we calculate the expected utilities instead of the MIN Value i.e weighted average of children\n",
        "\n",
        "MIN Node value = summation ( probability * child values)\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "The agent’s prefer- ences are captured by a utility function, U (s), which assigns a single number to express the desirability of a state. The expected utility of an action given the evidence, EU(a), is just the average utility value of the outcomes, weighted by the probability that the outcome occurs:\n",
        "\n",
        "EU(a) = ∑ P(RESULT(a)=s′)U(s′).\n",
        "\n",
        "The principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\n",
        "action = argmaxEU(a) \n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "Constraints on Rational Preferences:\n",
        "\n",
        "- Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\n",
        "- Transitivity,\n",
        "- Continuity,\n",
        "- Substitutability,\n",
        "- Monotonicity,\n",
        "- Decomposability.\n",
        "\n",
        "As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function.\n",
        "\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "Psuedo code for MINMAX - \n",
        "\n",
        "- start with the current position as MAX node\n",
        "- expand the game tree to a fixed level\n",
        "- apply the evaluation function at the leaves\n",
        "- calculate the back-up values bottom up\n",
        "- pick a move assigned to MAX at root\n",
        "- wait for MIN to respond\n",
        "\n",
        "5.3 continuation: Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the theoretical limit. The past could be the previous move—often the same threats remain—or it could come from previous exploration of the current move through a process of iterative deepening .\n",
        "The best moves are known as killer moves, and to try them first is called the killer move heuristic.\n",
        "In game tree search, repeated states can occur because of transpositions—different permutations of the move sequence that end up in the same position, and the problem can be addressed with a transposition table that caches the heuristic value of states.\n",
        "\n",
        "Go and Chess - \n",
        "\n",
        "Even with alpha–beta pruning and clever move ordering, minimax won’t work for games like chess and Go, because there are still too many states to explore in the time available.\n",
        "2 stratergies that work for chess is :\n",
        "\n",
        "- Type A : Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree. \n",
        "- Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"quiescent\" : \" positions in which there is no pending move that would wildly swing the evaluation\",  \n",
        "}\n",
        "\n"
      ],
      "execution_count": 19,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b07dd805-8522-4ba4-a086-f791ea786ed9"
      },
      "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": 20,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nAdversarial Search - Two or more agents have conflicting goals\n\nGame Environment - \n\n- Multiagent\n- Static : No change in environment when agent is delibearting\n- Discrete : Set of actions you take to transition from one state to another is finite\n- Fully observable : Complete state of environment is known\n- Strategic : Env is strategic in the sense that next state is determined by the current state and the action executed by the agent and the actions of the opponent\n\nWhat differentiates games from puzzles is that it is *strategic* and *multiagent*\n\nKey properties of games - \n\n- 2 players alternate moves\n- Zero sum : what is good for one player is bad for the other. There is no 'win-win' outcome\n- Clear set of legal moves\n- Well defined outcomes\n\nMost games in AI are \n1) Deterministic\n2) 2-player\n3) Perfect information (synonymous to fully observable)\n4) turn-talking\n5) Zero sum\n\nMost card games - Stochastic , not deterministic, not fully observable\nMost real-time games - Continuous rather than discrete\n\n**Game as a search** - A game can be formally defined with the following elements:\n\n- S0: The initial state, which specifies how the game is set up at the start.\n- TO-MOVE(s): The player whose turn it is to move in state s.\n- ACTIONS(s): The set of legal moves in state s.\n- RESULT(s, a): The transition model, which defines the state resulting from taking action a in state s.\n- IS-TERMINAL(s): A terminal test, which is true when the game is over and false otherwise. States where the game has ended are called terminal states.\n- UTILITY(s, p): A utility function (also called an objective function or payoff function), which defines the final numeric value to player p when the game ends in terminal state s.\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nGame Tree -\nroot node : first position in which a decision should be made\nEval func f : assigns a real values number to a board position (evaluates the goodness of the current state). Tells us 'how desirable is the current board position'\nTerminal nodes : represent the way the games could end labelled with the desirability of that ending\n\nMINIMAX Algorithm : \n\nbasic idea : Make the best move for MAX assuming MIN always replies with the best move for MIN. Treat your opponent like a rational actor just like you are.\n\nRecursive process - the value at each node in the tree is determined by the value of its children\n- For a MAX node : backed-up value is the maximum values of its children \n- For a MIN node : backed up values is the minimum value of its children\n\nMINIMAX algorithm performs a complete DFS expansion of the game tree. If depth of tree is 'm' and there are 'b' legal moves\n\n- Time complexity : O(b^m)\n- Space complexity : O(bm)\n\nExponential complexity of minimax makes it impractical for complex games. \n\n**Alpha - Beta Pruning :**\n\nNotion : Rather than searching the entire search space to fixed depth, we can get rid of branches if we know they wont be picked i.e prune parts of the tree that make no difference to the outcome.\n\nTo figure out which branches can be prunes we add 2 values alpha and beta\n\nalpha : keeps track of MAX's current lower bound on MAX's outcome. Best value seen for MAX till now (at least)\n\nbeta : keeps track of MIN's current upper bound on MIN's outcome. Best value seen for MIN till now (at most)\n\n**Move Ordering** - \n\nThe effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. \nIf all the worst successors are generated first, then we cant effectively prune the children of a node. If the best succesor had been generated first, then we could have pruned. \nThis is called perfect move ordering where the best succesor is generated first so that the other bad successors can be pruned away. \nIf this could be done perfectly, alpha–beta would need to examine only O(b^m/2) nodes to pick the best move, instead of O(b^m) for minimax. Put another way, alpha– beta with perfect move ordering can solve a tree roughly twice as deep as minimax in the same amount of time.\n\nWe can't achieve perfect move ordering but we can get fairly close. Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the theoretical limit.\nkiller move heuristic : the best moves are called killer moves so try these first before the rest. \nIn game tree search, repeated states can occur because of *transpositions* —different permutations of the move sequence that end up in the same position, and the problem can be addressed with a *transposition table* that caches the heuristic value of states.\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n\n**Heuristic - Alpha Beta tree search**\n\nTo make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal. In other words, we replace the UTILITY function with EVAL, which estimates a state’s utility. We also replace the terminal test by a cutoff test, which must return true for terminal states, but is otherwise free to decide when to cut off the search, based on the search depth and any property of the state that it chooses to consider. That gives us the formula H-MINIMAX(s, d) for the heuristic minimax value of state s at search depth d:\n\n1) EVAL instead of UTILITY\nA heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state s to player p, return an estimate of the distance to the goal.\n\nFor terminal states it must be that EVAL(s, p) = UTILITY (s, p)\nFor non-terminal states the evaluation must be somewhere in between a loss and a win. UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p).\n\n2) IS-CUTOFF instead of IS-TERMINAL\n\n\nExpected Value : averaging\n\nMaterial Value : assigning a value to the pawns in chess (for example)\n\nWeighted Function: weighted linear function\n\nCutting Off Search: modifying alpha beta to cut off at non terminal states.\n\nThese simple approaches can lead to errors due to the approximate nature of the evaluation function.\n\nThe evaluation function should be applied only to positions that are **quiescent** —that is, positions in which there is no pending move (such as a capturing the queen) that would wildly swing the evaluation.\n\n**The horizon effect**\n\nmore difficult to eliminate. It arises when the program is facing an opponent’s move that causes serious damage and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics.\nOne strategy to mitigate the horizon effect is to allow singular extensions, moves that are “clearly better” than all other moves in a given position, even when the search would normally be cut off at that point.\n\n**Forward Pruning** : Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good ones. Thus, the strategy saves computation time at the risk of making an error.\nThis can be done using:\n\n- Beam search: consider only a “beam” of the n best moves\n- ProbCut: uses statistics gained from prior experience to lessen the chance that the best move will be pruned.\n- Another technique, late move reduction, works under the assumption that move ordering has been done well, and therefore moves that appear later in the list of possible moves are less likely to be good moves.\n\n\n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games bring us a little closer to the unpredictability of real life by including a random element, such as the throwing of dice \nSo far we know the oponent was going to make the most optimal move so we knew we were dealing with a fixed outcome. But in certain games the outcome is uncertain. Uncertain outcomes are controlled by chance -> not an adversary\n\nidea : We dont know what the result of an action can be because of 1) explicit randomness (rolling dice) 2) unpredictable opponents (opponents aren't optimal) 3) actions can fail\n\nSo, Here MAX nodes remain the same as MINI-MAX algorithm. MIN node is now a \"chance\" node -> outcome is uncertain here. \nSo we calculate the expected utilities instead of the MIN Value i.e weighted average of children\n\nMIN Node value = summation ( probability * child values)\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe agent’s prefer- ences are captured by a utility function, U (s), which assigns a single number to express the desirability of a state. The expected utility of an action given the evidence, EU(a), is just the average utility value of the outcomes, weighted by the probability that the outcome occurs:\n\nEU(a) = ∑ P(RESULT(a)=s′)U(s′).\n\nThe principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\naction = argmaxEU(a) \n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nConstraints on Rational Preferences:\n\n- Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\n- Transitivity,\n- Continuity,\n- Substitutability,\n- Monotonicity,\n- Decomposability.\n\nAs in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function.\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n \nPsuedo code for MINMAX - \n\n- start with the current position as MAX node\n- expand the game tree to a fixed level\n- apply the evaluation function at the leaves\n- calculate the back-up values bottom up\n- pick a move assigned to MAX at root\n- wait for MIN to respond\n\n5.3 continuation: Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the theoretical limit. The past could be the previous move—often the same threats remain—or it could come from previous exploration of the current move through a process of iterative deepening .\nThe best moves are known as killer moves, and to try them first is called the killer move heuristic.\nIn game tree search, repeated states can occur because of transpositions—different permutations of the move sequence that end up in the same position, and the problem can be addressed with a transposition table that caches the heuristic value of states.\n\nGo and Chess - \n\nEven with alpha–beta pruning and clever move ordering, minimax won’t work for games like chess and Go, because there are still too many states to explore in the time available.\n2 stratergies that work for chess is :\n\n- Type A : Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree. \n- Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree.\n\n\n\n## Module 5 Definitions\n* **Quiescent** -  positions in which there is no pending move that would wildly swing the evaluation\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",
        "\n",
        "search algorithm, each state is atomic, or indivisible— a black box with no internal structure. For each problem we need domain-specific code to describe the transitions between states.\n",
        "In this chapter we break open the black box by using a factored representation for each state: a set of variables, each of which has a value. A problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem, or CSP.\n",
        "\n",
        "CSP search algorithms take advantage of the structure of states and use general rather than domain-specific heuristics to enable the solution of complex problems. The main idea is to eliminate large portions of the search space all at once by identifying variable/value combinations that violate the constraints.\n",
        "\n",
        "A constraint satisfaction problem consists of three components, X,D, and C:\n",
        "\n",
        "- X is a set of variables, {X1,...,Xn}.\n",
        "- D is a set of domains, {D1,...,Dn}, one for each variable.\n",
        "- C is a set of constraints that specify allowable combinations of values.\n",
        "\n",
        "A domain, Di, consists of a set of allowable values, {v1,...,vk}, for variable Xi\n",
        "\n",
        "CSPs deal with assignments of values to variables,{Xi=vi,Xj=vj,...}.\n",
        "\n",
        "- An assignment that does not violate any constraints is called a **consistent or legal assignment**\n",
        "- A **complete assignment** is one in which every variable is assigned a value. \n",
        "- solution to a CSP is a **consistent, complete assignment**.\n",
        "\n",
        "A **partial assignment** is one that leaves some variables unassigned\n",
        "A **partial solution** is a partial assignment that is consistent. \n",
        "\n",
        "Solving a CSP is an NP-complete problem in general\n",
        "\n",
        "\n",
        "In CSP -> instead of planning a sequence of actions we want to identify assignments to variables -> main diffreence between search and CSP\n",
        "\n",
        "- Goal is more important than the path\n",
        "- All paths are same depth\n",
        "- CSPs are specialised for identification problems\n",
        "\n",
        "solutions to CSPs can be found by a completely general algorithm given only a formal specification of the CSP. \n",
        "\n",
        "Types of CSP formulisations -\n",
        "\n",
        "All CSP problems have **finite and discrete domains**. \n",
        "Discrete domains can also be **infinite** such as set of real valued numbers, set of integers and can be continuous too. \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "\n",
        "We say that a CSP is bounds-consistent if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of X that satisfies the constraint between X and Y for every variable Y\n",
        "\n",
        "n-ary constraints use a constraint hypergraph\n",
        "\n",
        "Constraint Propogation : using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on.\n",
        "The idea is that this will leave fewer choices to consider when we make the next choice of a variable assignment. Constraint propagation may be intertwined with search, or it may be done as a preprocessing step, before search starts.\n",
        "\n",
        "Local consistency : If we treat each variable as a node in a graph (see Figure 6.1(b)) and each binary constraint as an edge, then the process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph.\n",
        "\n",
        "Types of Local consistency - \n",
        "\n",
        "1. Node consistency : satisfying unary constraints\n",
        "\n",
        "2. Arc consistency : satisfying binary constraints : xi and xj are arc consistent if for every value in domain Di there is a corresponding value w in Dj that satisfies the binary constraint on arc between xi ans xj\n",
        "\n",
        "3. Path consistency : Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n",
        "A two-variable set {Xi,Xj} is path-consistent with respect to a third variable Xm if, for every assignment {Xi = a, X j = b} consistent with the constraints (if any) on {Xi , X j }, there is an assignment to Xm that satisfies the constraints on {Xi,Xm} and {Xm,Xj}. The name refers to the overall consistency of the path from Xi to Xj with Xm in the middle.\n",
        "\n",
        "4. K- consistent : A CSP is k- consistent if, for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. 1-consistency says that, given the empty set, we can make any set of one variable consistent: this is what we called node consistency. 2-consistency is the same as arc consistency. For binary constraint graphs, 3- consistency is the same as path consistency.\n",
        "\n",
        "5. Strongly k- consistent : A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)- consistent, ... all the way down to 1-consistent\n",
        "\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "When after running CSP, domains are not unary. Need to backtrack to check the solution.\n",
        "\n",
        "Types of Backtracking - \n",
        "\n",
        "1. Static ordering backtracking: choosing variables in order\n",
        "\n",
        "2. Random ordering backtracking: choosing variables in random order\n",
        "\n",
        "3. Intelligent backtracking: backtrack the most recent variable which made the assignment inconsistent.\n",
        "\n",
        "\n",
        "Back Tracking Search in CSP : dfs choses one value for one variable at a time and backtracks when a variable has no legal values left to assign.  \n",
        "\n",
        "How to improve ?? -> heuristics \n",
        "\n",
        "1. Which variable should be assigned next ?\n",
        "\n",
        "Chose a variable with fewer remaining legal values first aka **MRV heuristic - Minimum Remaining values heuristic**.\n",
        "\n",
        "If there is a tie pick the **most constraining variable** i.e pick the variable with most constraints on remaining variables.\n",
        "\n",
        "2. What order should that variables value be tried?\n",
        "\n",
        "Given a variable, chose the least constarining value -> the one that rules out fewest remaining variables. \n",
        "\n",
        "3. Can we detect failure early? \n",
        "\n",
        "- Use forward checking : One of the simplest forms of inference is called forward checking. Whenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each unas- signed variable Y that is connected to X by a constraint, delete from Y ’s domain any value that is inconsistent with the value chosen for X .\n",
        "\n",
        "For many problems the search will be more effective if we combine the MRV heuristic with forward checking. Although forward checking detects many inconsistencies, it does not detect all of them. The problem is that it doesn’t look ahead far enough.\n",
        "\n",
        "Thus, AC3 or MAC (Maintainign Arc Consistency) :\n",
        "\n",
        "The algorithm called MAC (for Maintaining Arc Consistency) detects inconsistencies like this. After a variable Xi is assigned a value, the INFERENCE procedure calls AC-3, but instead of a queue of all arcs in the CSP, we start with only the arcs (Xj,Xi) for all Xj that are unassigned variables that are neighbors of Xi. From there, AC-3 does constraint propagation in the usual way, and if any variable has its domain reduced to the empty set, the call to AC-3 fails and we know to backtrack immediately. We can see that MAC is strictly more powerful than forward checking because forward checking does the same thing as MAC on the initial arcs in MAC’s queue; but unlike MAC, forward checking does not recursively propagate constraints when changes are made to the domains of variables.\n",
        "\n",
        "- \n",
        "\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "The most obvious approach is to select the value that results in the minimum number of conflicts with other variables—**the min-conflicts heuristic**. Especially for N queens. Move the queens to minimum conflict position.\n",
        "\n",
        "The landscape of a CSP under the min-conflicts heuristic usually has a series of plateaus.\n",
        "**Plateau search**— allowing sideways moves to another state with the same score—can help local search find its way off this plateau.\n",
        "This wandering on the plateau can be directed with a technique called tabu search: keeping a small list of recently visited states and forbidding the algorithm to return to those states. Simulated annealing can also be used to escape from plateaus.\n",
        "Another technique called constraint weighting aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. This has two benefits: it adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights.\n",
        "Another advantage of local search is that it can be used in online settings when the problem changes.\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "CSP as a search problem : \n",
        "\n",
        " 1. initial state : {}\n",
        "\n",
        " 2. Successor function : Assign values to any unassigned variable provided there is no constraint conflict\n",
        "\n",
        " 3. Goal Test : Is the current assignment complete\n",
        "\n",
        " 4. Path cost : A constant cost at each step\n",
        "\n",
        " In CSP -> solution is always found in depth 'n' for 'n' variables hence DFS can be used.\n",
        "\n",
        " Time Complexity : \n",
        "\n",
        " - Assume n- variables each of which take 'd' values.\n",
        " - Branching factor = n*d, of next level = (n-1)*d leaves\n",
        "\n",
        "**so tree has O(n!d^n) leaves**\n",
        "\n",
        " CSPs cut down the search space because the order of assignment of variables does not matter. problem is **Commutative**. hence, its a **tree search** not a **graph search**.\n",
        "\n",
        "**Now it is reduced from O(n! d^n) to O(d^n) - search space is pruned**\n",
        "\n",
        "**Benefits of CSP** \n",
        "\n",
        "- Clean specification of many problems with a generic goal, succesor function and heuristics\n",
        "- CSPs know which variables violate a constraint and hence know where to focus the search\n",
        "- They automatically prune off all branches that violate constraints \n",
        "\n",
        "Applications : 1) Sudoko 2) Scheduling problems 3) MAP coloring 4) Floor planning VLSI\n",
        "\n",
        "Intelligent backtracking: Keep a conflict set: a set of assignment of variables that caused the conflict for the other variable. (to backtrack on variables that fixed the problem). The backjumping method backtracks to the most recent assignment in the conflict set.\n",
        "Backjumping is the same as forward checking.\n",
        "\n",
        "When we reach a contradiction, backjumping can tell us how far to back up, so we don’t waste time changing variables that won’t fix the problem.\n",
        "\n",
        "Constraint Learning: Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods. (basically a visited array of already checked assignments).\n",
        "No goods can be computed by forward checking or back jumping.\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Disjunctive constraints\": \"that don’t overlap(algebraic plus disjunctive)\"\n",
        " \n",
        "}\n"
      ],
      "execution_count": 23,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ecf48468-b0af-4691-c717-776e108eb48a"
      },
      "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": 24,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \n\nsearch algorithm, each state is atomic, or indivisible— a black box with no internal structure. For each problem we need domain-specific code to describe the transitions between states.\nIn this chapter we break open the black box by using a factored representation for each state: a set of variables, each of which has a value. A problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem, or CSP.\n\nCSP search algorithms take advantage of the structure of states and use general rather than domain-specific heuristics to enable the solution of complex problems. The main idea is to eliminate large portions of the search space all at once by identifying variable/value combinations that violate the constraints.\n\nA constraint satisfaction problem consists of three components, X,D, and C:\n\n- X is a set of variables, {X1,...,Xn}.\n- D is a set of domains, {D1,...,Dn}, one for each variable.\n- C is a set of constraints that specify allowable combinations of values.\n\nA domain, Di, consists of a set of allowable values, {v1,...,vk}, for variable Xi\n\nCSPs deal with assignments of values to variables,{Xi=vi,Xj=vj,...}.\n\n- An assignment that does not violate any constraints is called a **consistent or legal assignment**\n- A **complete assignment** is one in which every variable is assigned a value. \n- solution to a CSP is a **consistent, complete assignment**.\n\nA **partial assignment** is one that leaves some variables unassigned\nA **partial solution** is a partial assignment that is consistent. \n\nSolving a CSP is an NP-complete problem in general\n\n\nIn CSP -> instead of planning a sequence of actions we want to identify assignments to variables -> main diffreence between search and CSP\n\n- Goal is more important than the path\n- All paths are same depth\n- CSPs are specialised for identification problems\n\nsolutions to CSPs can be found by a completely general algorithm given only a formal specification of the CSP. \n\nTypes of CSP formulisations -\n\nAll CSP problems have **finite and discrete domains**. \nDiscrete domains can also be **infinite** such as set of real valued numbers, set of integers and can be continuous too. \n\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n\nWe say that a CSP is bounds-consistent if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of X that satisfies the constraint between X and Y for every variable Y\n\nn-ary constraints use a constraint hypergraph\n\nConstraint Propogation : using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on.\nThe idea is that this will leave fewer choices to consider when we make the next choice of a variable assignment. Constraint propagation may be intertwined with search, or it may be done as a preprocessing step, before search starts.\n\nLocal consistency : If we treat each variable as a node in a graph (see Figure 6.1(b)) and each binary constraint as an edge, then the process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph.\n\nTypes of Local consistency - \n\n1. Node consistency : satisfying unary constraints\n\n2. Arc consistency : satisfying binary constraints : xi and xj are arc consistent if for every value in domain Di there is a corresponding value w in Dj that satisfies the binary constraint on arc between xi ans xj\n\n3. Path consistency : Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\nA two-variable set {Xi,Xj} is path-consistent with respect to a third variable Xm if, for every assignment {Xi = a, X j = b} consistent with the constraints (if any) on {Xi , X j }, there is an assignment to Xm that satisfies the constraints on {Xi,Xm} and {Xm,Xj}. The name refers to the overall consistency of the path from Xi to Xj with Xm in the middle.\n\n4. K- consistent : A CSP is k- consistent if, for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. 1-consistency says that, given the empty set, we can make any set of one variable consistent: this is what we called node consistency. 2-consistency is the same as arc consistency. For binary constraint graphs, 3- consistency is the same as path consistency.\n\n5. Strongly k- consistent : A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)- consistent, ... all the way down to 1-consistent\n\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nWhen after running CSP, domains are not unary. Need to backtrack to check the solution.\n\nTypes of Backtracking - \n\n1. Static ordering backtracking: choosing variables in order\n\n2. Random ordering backtracking: choosing variables in random order\n\n3. Intelligent backtracking: backtrack the most recent variable which made the assignment inconsistent.\n\n\nBack Tracking Search in CSP : dfs choses one value for one variable at a time and backtracks when a variable has no legal values left to assign.  \n\nHow to improve ?? -> heuristics \n\n1. Which variable should be assigned next ?\n\nChose a variable with fewer remaining legal values first aka **MRV heuristic - Minimum Remaining values heuristic**.\n\nIf there is a tie pick the **most constraining variable** i.e pick the variable with most constraints on remaining variables.\n\n2. What order should that variables value be tried?\n\nGiven a variable, chose the least constarining value -> the one that rules out fewest remaining variables. \n\n3. Can we detect failure early? \n\n- Use forward checking : One of the simplest forms of inference is called forward checking. Whenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each unas- signed variable Y that is connected to X by a constraint, delete from Y ’s domain any value that is inconsistent with the value chosen for X .\n\nFor many problems the search will be more effective if we combine the MRV heuristic with forward checking. Although forward checking detects many inconsistencies, it does not detect all of them. The problem is that it doesn’t look ahead far enough.\n\nThus, AC3 or MAC (Maintainign Arc Consistency) :\n\nThe algorithm called MAC (for Maintaining Arc Consistency) detects inconsistencies like this. After a variable Xi is assigned a value, the INFERENCE procedure calls AC-3, but instead of a queue of all arcs in the CSP, we start with only the arcs (Xj,Xi) for all Xj that are unassigned variables that are neighbors of Xi. From there, AC-3 does constraint propagation in the usual way, and if any variable has its domain reduced to the empty set, the call to AC-3 fails and we know to backtrack immediately. We can see that MAC is strictly more powerful than forward checking because forward checking does the same thing as MAC on the initial arcs in MAC’s queue; but unlike MAC, forward checking does not recursively propagate constraints when changes are made to the domains of variables.\n\n- \n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nThe most obvious approach is to select the value that results in the minimum number of conflicts with other variables—**the min-conflicts heuristic**. Especially for N queens. Move the queens to minimum conflict position.\n\nThe landscape of a CSP under the min-conflicts heuristic usually has a series of plateaus.\n**Plateau search**— allowing sideways moves to another state with the same score—can help local search find its way off this plateau.\nThis wandering on the plateau can be directed with a technique called tabu search: keeping a small list of recently visited states and forbidding the algorithm to return to those states. Simulated annealing can also be used to escape from plateaus.\nAnother technique called constraint weighting aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. This has two benefits: it adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights.\nAnother advantage of local search is that it can be used in online settings when the problem changes.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n \nCSP as a search problem : \n\n 1. initial state : {}\n\n 2. Successor function : Assign values to any unassigned variable provided there is no constraint conflict\n\n 3. Goal Test : Is the current assignment complete\n\n 4. Path cost : A constant cost at each step\n\n In CSP -> solution is always found in depth 'n' for 'n' variables hence DFS can be used.\n\n Time Complexity : \n\n - Assume n- variables each of which take 'd' values.\n - Branching factor = n*d, of next level = (n-1)*d leaves\n\n**so tree has O(n!d^n) leaves**\n\n CSPs cut down the search space because the order of assignment of variables does not matter. problem is **Commutative**. hence, its a **tree search** not a **graph search**.\n\n**Now it is reduced from O(n! d^n) to O(d^n) - search space is pruned**\n\n**Benefits of CSP** \n\n- Clean specification of many problems with a generic goal, succesor function and heuristics\n- CSPs know which variables violate a constraint and hence know where to focus the search\n- They automatically prune off all branches that violate constraints \n\nApplications : 1) Sudoko 2) Scheduling problems 3) MAP coloring 4) Floor planning VLSI\n\nIntelligent backtracking: Keep a conflict set: a set of assignment of variables that caused the conflict for the other variable. (to backtrack on variables that fixed the problem). The backjumping method backtracks to the most recent assignment in the conflict set.\nBackjumping is the same as forward checking.\n\nWhen we reach a contradiction, backjumping can tell us how far to back up, so we don’t waste time changing variables that won’t fix the problem.\n\nConstraint Learning: Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods. (basically a visited array of already checked assignments).\nNo goods can be computed by forward checking or back jumping.\n\n\n \n\n## Module 6 Definitions\n* **Disjunctive constraints** - that don’t overlap(algebraic plus disjunctive)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "problem solving agent -> They know what actions are available and what is the result of performing a specific action from a specific state will be but they dont know general facts\n",
        "\n",
        "Logical agents -> Use a process of reasoning over an internal representation of knowledge to decide what actions to take next\n",
        "\n",
        "The central component of a knowledge-based agent is its knowledge base, or KB.\n",
        "\n",
        "A knowledge base is a set of sentences. Each sentence is expressed in a knowledge representation language and represents some assertion about the world. \n",
        "\n",
        "Sentences in KB : \n",
        "- Axiom : Sentence is given\n",
        "- Derived : New sentences are derived from other sentences\n",
        "\n",
        "Process of deriving new sentences from old sentences is called **inference**\n",
        "\n",
        "Each time the agent program is called, it does three things: \n",
        "- First, it Tells the knowledge base what it perceives.\n",
        "- Second, it Asks the knowledge base what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on.\n",
        "- Third, the agent program Tells the knowledge base which action was chosen, and returns the action so that it can be executed.\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives.\n",
        "\n",
        "Conjunction - intersection - and Disjunction - union - or\n",
        "\n",
        "Logical Equivalence : two sentence a and b are logically equivalent if they are true in the same set of models\n",
        "\n",
        "a and b are logically eq iff a|=b and b|=a\n",
        "\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "\n",
        "**monotonicity** : which says that the set of entailed sentences can only increase as information is added to the knowledge base.\n",
        "\n",
        "**Monotonicity => Soundness** : if we add additional info into the KB, it doesn't invalidate any other info that we have already inferred\n",
        "\n",
        "**Converting a sentence to CNF :**\n",
        "\n",
        "Every sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals.\n",
        "\n",
        "- Eliminate ⇔ by replacing a⇔ β with (a ⟹ β) ⋀ (β ⟹a)\n",
        "- Eliminate ⟹ by replacing a ⟹ β with ¬a ⋁ β (implication elimination)\n",
        "- Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n",
        "\n",
        "Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\n",
        "The sentence is now in CNF!\n",
        "\n",
        "**Resolution Algorithm**\n",
        "\n",
        "to show KB |= a we show that KB ^ ¬a is unsatisfiable.\n",
        "\n",
        "1. first convert KB ^ ¬a into CNF\n",
        "2. Apply resolution to resulting clauses\n",
        "3. Resolve every pair that contains complementary literals to produce a new clause\n",
        "4. If that clause is not present then add it to a set\n",
        "Continue until : \n",
        "(a) no new clause to be added to KB (KB does not entail a)\n",
        "(b) two clauses resolve to yield an empty clause (KB entails a)\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "\n",
        "If you restrict the KB to have only certain types of sentences in it (a more restrictive KB) -> enables to use more efficient inference algorithms\n",
        "\n",
        "- Definite Clause : Disjunction of literals where exactly 1 is positive\n",
        "- Horn Clause : Disjunction of literals where atmost 1 is positive\n",
        "\n",
        "Horn Clause is closed under resolution. If you apply resolution to a horn clause, you get back a horn clause.\n",
        "\n",
        "Every definite clause can be written as an implication. \n",
        "\n",
        "Inference with Horn clauses can be done through the forward-chaining and backward-chaining algorithms. Deciding entailment with Horn clauses can be done in linear time with respect to the size of the KB.\n",
        "\n",
        "**Forward Chaining is a kind of data-driven reasoning**. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\n",
        "\n",
        "Backward chaining works backwards from a query. If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n",
        "**Backward chaining is a form of goal-directed reasoning.**\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Sound\" : \"the inference algorithm should only derive valid entailments\",\n",
        "\"Complete\" : \"an inference algorithm is complete if it can derive all valid entailments\"\n",
        "    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ed18abd8-d517-442c-8078-336a254c831b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nproblem solving agent -> They know what actions are available and what is the result of performing a specific action from a specific state will be but they dont know general facts\n\nLogical agents -> Use a process of reasoning over an internal representation of knowledge to decide what actions to take next\n\nThe central component of a knowledge-based agent is its knowledge base, or KB.\n\nA knowledge base is a set of sentences. Each sentence is expressed in a knowledge representation language and represents some assertion about the world. \n\nSentences in KB : \n- Axiom : Sentence is given\n- Derived : New sentences are derived from other sentences\n\nProcess of deriving new sentences from old sentences is called **inference**\n\nEach time the agent program is called, it does three things: \n- First, it Tells the knowledge base what it perceives.\n- Second, it Asks the knowledge base what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on.\n- Third, the agent program Tells the knowledge base which action was chosen, and returns the action so that it can be executed.\n \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nComplex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives.\n\nConjunction - intersection - and Disjunction - union - or\n\nLogical Equivalence : two sentence a and b are logically equivalent if they are true in the same set of models\n\na and b are logically eq iff a|=b and b|=a\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \n\n**monotonicity** : which says that the set of entailed sentences can only increase as information is added to the knowledge base.\n\n**Monotonicity => Soundness** : if we add additional info into the KB, it doesn't invalidate any other info that we have already inferred\n\n**Converting a sentence to CNF :**\n\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals.\n\n- Eliminate ⇔ by replacing a⇔ β with (a ⟹ β) ⋀ (β ⟹a)\n- Eliminate ⟹ by replacing a ⟹ β with ¬a ⋁ β (implication elimination)\n- Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n\nNow the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\nThe sentence is now in CNF!\n\n**Resolution Algorithm**\n\nto show KB |= a we show that KB ^ ¬a is unsatisfiable.\n\n1. first convert KB ^ ¬a into CNF\n2. Apply resolution to resulting clauses\n3. Resolve every pair that contains complementary literals to produce a new clause\n4. If that clause is not present then add it to a set\nContinue until : \n(a) no new clause to be added to KB (KB does not entail a)\n(b) two clauses resolve to yield an empty clause (KB entails a)\n\n\n\n\n \n\n## Module 7 Lecture Notes\n \n\nIf you restrict the KB to have only certain types of sentences in it (a more restrictive KB) -> enables to use more efficient inference algorithms\n\n- Definite Clause : Disjunction of literals where exactly 1 is positive\n- Horn Clause : Disjunction of literals where atmost 1 is positive\n\nHorn Clause is closed under resolution. If you apply resolution to a horn clause, you get back a horn clause.\n\nEvery definite clause can be written as an implication. \n\nInference with Horn clauses can be done through the forward-chaining and backward-chaining algorithms. Deciding entailment with Horn clauses can be done in linear time with respect to the size of the KB.\n\n**Forward Chaining is a kind of data-driven reasoning**. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\n\nBackward chaining works backwards from a query. If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n**Backward chaining is a form of goal-directed reasoning.**\n\n \n\n## Module 7 Definitions\n* **Sound** - the inference algorithm should only derive valid entailments\n* **Complete** - an inference algorithm is complete if it can derive all valid entailments\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": "10c82eeb-b9d4-4e89-8ae9-ece5812e768f"
      },
      "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": 25,
      "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 \n-weak AI—the idea that machines could act as if they were intelligent \n-strong AI—the assertion that machines that do so are actually consciously thinking (not just simulating thinking).\n-Measuring AI: Turing test(if agent fools 30% of the time), Games like Go, StarCraft 2 etc.\n\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n \nAn agent is anything that perceives its environment through sensors and can act on its environment through actuators\n\n- percept:  content an agent’s sensors are perceiving. \n- An agent’s percept sequence is the complete history of everything the agent has ever perceived.\n- Mathematically speaking, we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action.\nThe agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system.\n- The agent program runs on the physical architecture to produce f (agent function)\n\nA rational agent is an agent that perceives its environment and and behaves rationally. For each possible percept sequence P a rational agent selects an action a to maximize the expected value of its performance measure\n\n\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nWhat is rational at any given time depends on four things:\n- The performance measure that defines the criterion of success.\n- The agent’s prior knowledge of the environment.\n- The actions that the agent can perform.\n- The agent’s percept sequence to date.\n\nDoing actions in order to modify future percepts—sometimes called information gathering —is an important part of rationality.\n\nA second example of information gathering is provided by the exploration that must be undertaken by a vacuum-cleaning agent in an initially unknown environment.\n\nOur definition requires a rational agent not only to gather information but also to learn as much as possible from what it perceives.\n\nTo the extent that an agent relies on the prior knowledge of its designer rather than on its own percepts and learning processes, we say that the agent lacks autonomy. A rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge.\n \n\n## AIMA 2.3 The Nature of Environments\n \nTo design a rational agent we need to specify a task environment\n- a problem specification for which the agent is a solution\n\nPEAS: to specify a task environment\n- Performance measure\n- Environment\n- Actuators\n- Sensors \n\n\nProperties of Task Environments:\n\n1. FULLY vs PARTIALLY OBSERVABLE: If the agent has no sensors at all then the environment is unobservable.\n\n2. SINGLE-AGENT VS. MULTIAGENT: Multiagent can be competitive(chess) or cooperative(taxi driver), partially competitive(taxi driver searching for a parking spot).\n\n3. DETERMINISTIC VS NON DETERMINISTIC: If the next state of the environment is completely determined by the current state and the action executed by the agent(s), then we say the environment is deterministic; otherwise, it is nondeterministic.\n\n4. EPISODIC VS. SEQUENTIAL: In episodic, every episode is atomic and independent of the previous episode.Examples of sequential - Chess and taxi driving are sequential\n\n5. STATIC vs DYNAMIC: If the environment can change while an agent is deliberating, then we say the environment is dynamic(taxi driver) for that agent; otherwise, it is static (crossword puzzle). If the environment itself does not change with the passage of time but the agent’s performance score does, then we say the environment is semi dynamic (chess with clock).\n\n6. DISCRETE VS. CONTINUOUS: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent. For example, the chess environment has a finite number of distinct states (excluding the clock). Chess also has a discrete set of percepts and actions. Taxi driving is a continuous-state and continuous-time problem.\n\n6. KNOWN VS. UNKNOWN: Strictly speaking, this distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of the environment.\n\nExperiments are often carried out not for a single environment but for many environments drawn from an environment class. For example, to evaluate a taxi driver in simulated traffic, we would want to run many simulations with different traffic, lighting, and weather conditions. We are then interested in the agent’s average performance over the environment class.\n​​It is quite possible for a known environment to be partially observable—for example, in solitaire card games. Conversely, an unknown environment can be fully observable—in a new video game, the screen may show the entire game state but I still don’t know what the buttons do until I try them.\nExperiments are often carried out not for a single environment but for many environments drawn from an environment class. For example, to evaluate a taxi driver in simulated traffic,\n\n\n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n When the correct action to take is not immediately obvious, an agent may need to to plan ahead: to consider a sequence of actions that form a path to a goal state. Such an agent is called a problem-solving agent, and the computational process it undertakes is called search.\n\nenvironment considered: **episodic, single agent, fully observable, deterministic, static, discrete, and known**.\n\ninformed algorithms : agent can estimate how far it is from the goal\nuninformed algorithms : no such estimate is available. An uninformed search algorithm is given no clue about how close a state is to the goal(s).\n\nAgent follows a 4 phase problem solving process :\n- Goal Formulation \n- Problem Formulation - The agent devises a description of the states and actions nec- essary to reach the goal\n- Search - Agent tries to find a sequence of actions that reaches the goal - this seq is called solution\n- Execution - Agent executes actions in the solution\n\nIt is an important property that in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions\n\nFormal Definition of a Search Problem :\n1. State Space : A set of possible states that the environment can be in\n2. Initial state\n3. Set of one or more goal states\n4. Actions available to the agent - given a particular state set of actions that are legal in that state\n5. Transition model : Returns what each action does. RESULT(s, a) returns the\nstate that results from doing action a in state s.\n6. Performance measure/ action cost func \n7. Goal test \n\n\n\n\n## AIMA Chapter 3.2 Example Problems\n \nA standardized problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms.\n\nA real-world problem, such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data.\n\nAbsolute movements: movement direction acc to viewer\n\nEgocentric: movement direction acc to the robot\n\nStandardized problems: grid world, sokoban puzzle, sliding tile puzzle\n\nReal world problems: Route finding, touring problems, travelling salesperson, VLSI layout, robot navigation, automatic assembly sequence\n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n A search algorithm takes a search problem as input and returns a solution, or an indication of failure.\n\nEach node in the search tree corresponds to a state in the state space and the edges in the search tree correspond to actions. The root of the tree corresponds to the initial state of the problem.\n\nThree kinds of queues are used in search algorithms:\n\n- A priority queue first pops the node with the minimum cost according to some evaluation function, f . It is used in best-first search.\n- A FIFO queue or first-in-first-out queue first pops the node that was added to the queue first; we shall see it is used in breadth-first search.\n- A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most recently added node; we shall see it is used in depth-first search.\n\nWe call a search algorithm a **graph search if it checks for redundant paths** and a **tree-like search if it does not check**.\n\n**Graph search is more memory intensive than tree search as it keeps track of redundant paths.**\n\n**Graph search is faster than tree search.**\n\n\nWe can evaluate an algorithm’s performance in four ways:\n\n- Completeness: Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not?\n- Cost optimality: Does it find a solution with the lowest path cost of all solutions?\n- Time complexity: How long does it take to find a solution? This can be measured in seconds, or more abstractly by the number of states and actions considered.\n- Space complexity: How much memory is needed to perform the search?\n\n- **BFS**\n\n    When all actions have the same cost, an appropriate strategy is breadth-first search, in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on.\n\n    Queue used : FIFO\n\n    Properties :\n        - Optimal : if all actions have the same cost. Else its not optimal \n        - Complete \n        - Time complexity is O(b^d) \n        - Space complecity is O(b^d) \n\n    The memory requirements are a bigger problem for breadth-first search than the execution time. In general, exponential-complexity search problems cannot be solved by uninformed search for any but the smallest instances.\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n\n- **DFS**\n\n    Depth-first search always expands the deepest node in the frontier first.\n    However, it is usually implemented not as a graph search but as a tree-like search that does not keep a table of reached states.\n    \n    Properties :\n        - Not Optimal : Depth-first search is not cost-optimal; it returns the first solution it finds, even if it is not cheapest.\n        - Not complete : For finite and acyclic state spaces its complete but for In cyclic state spaces it can get stuck in an infinite loop.Finally, in infinite state spaces, depth- first search is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus, depth-first search is incomplete.\n        - Time complexity : O(b^m)\n        - Space Complexity : O(b*m) :\n    depth-first search has much smaller needs for memory. We don’t keep a reached table at all, and the frontier is very small\n\n- **Depth limited Search**\n\n    A version of depth-first search in which we supply a depth limit, l, and treat all nodes at depth l as if they had no successors. \n    Properties - \n        The time complexity is O(b^l) and the space complexity is O(bl).\n    Unfortunately, if we make a poor choice for l the algorithm will fail to reach the solution, making it incomplete again.\n\n- **Iterative Depth Limited Search**\n\n    Iterative deepening search solves the problem of picking a good value for l by trying all values: first 0, then 1, then 2, and so on—until either a solution is found, or the depth- limited search returns the failure\n\n    Properties :\n        - Complete\n        - Optimal\n        - Space Complexity - O(bd)\n        - The time complexity is O(b^d ) when there is a solution, or O(b^m ) when there is none\n    \n    In general, iterative deepening is the preferred uninformed search method when the search state space is larger than can fit in memory and\nthe depth of the solution is not known.\n\n \n\n## Module 3 Lecture Notes\n \n- b = branching factor : max set of possible actions that you can take from any state or number of successors of a node that need to be considered.\n- d = depth : number of actions in an optimal solution\n- m = the maximum number of actions in any path\n\nUse depth-first if\n- Space is restricted\n- There are many possible solutions with long paths and wrong paths are usually terminated quickly\n- Search can be fine-tuned quickly\n\nUse breadth-first if\n- Possible infinite paths\n- Some solutions have short paths\n- Can quickly discard unlikely paths\n\n\n- **UCS or Dijkstra's algorithm**\n\n    When actions have different costs, an obvious choice is to use best-first search where the evaluation function is the cost of the path from the root to the current node. Pick the node that leads to least cost\n    Then the algorithm’s worst-case time and space complexity can be much greater than bfs . This is because uniform-cost search can explore large trees of actions with low costs before exploring paths involving a high-cost and perhaps useful action.\n\n    Properties :\n        - Optimal\n        - Complete\n\n- Backtracking :\n\n    A variant of depth-first search called backtracking search uses even less memory. (See Chapter 6 for more details.) In backtracking, only one successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next.\n    Reduces memory req from O(bm) to O(m)\n\n- Bidirectional Search\n\n    An alternative approach called bidirectional search simultaneously searches forward from the initial state and backwards from the goal state(s), hoping that the two searches will meet\n\n    The motivation is that O(b^d/2 + b^d/2) is much less than O(b^d) \n    Bidirectional search expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet.\n\n\"Open Loop\": \"when the environment is deterministic, and the agent has found a solution, it need not collect percept sequences while reaching the goal state.\",\n\n\"Closed Loop\": \"If there is a chance that the model is incorrect, or the environment is nondeterministic, then the agent would be safer using a closed-loop approach that monitors the percepts.\"\n\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Reflex agent** -  selects an action based only on the current percept. It ignores the rest of the percept history.\n* **Path** - sequence of actions\n* **Solution** - path from initial state to goal state\n* **Optimal solution** - has the lowest path cost among all solutions\n* **Search tree** - a way of representing the paths that a search algorithm has explored\n* **Frontier** - those states that are available for expanding (for applying legal actions to)\n* **Early goal test** - checking whether a node is a solution as soon as it is generated\n* **Late goal test** - waiting until a node is popped off the queue\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nInformed search strategy—one that uses domain-specific hints about the location of goals—can find solutions more efficiently than an uninformed strategy. \nThe hints come in the form of a heuristic function, denoted h(n)\n\n**Greedy Best first search**\n\nform of best-first search that expands first the node with the lowest h(n) value—the node that appears to be closest to the goal—on the grounds that this is likely to lead to a solution quickly. f (n) = h(n).\n\n**A star search**\n\nf (n) = g(n) + h(n)\nwhere g(n) is the path cost from the initial state to node n, and h(n) is the estimated cost of\nthe shortest path from n to a goal state, so we have\n    f (n) = estimated cost of the best path that continues from n to a goal.\n\nProperties - \n    - A* is complete\n    - A* optimality depends on if the heuristic is admissible or not. admissible = optimal\n\n**Admissibility** - an admissible heuristic is one that never overestimates the cost to reach a goal. (An admissible heuristic is therefore optimistic.\n\n**Consistency** - A slightly stronger property is called consistency. A heuristic h(n) is consistent if, for every node n and every successor n′ of n generated by an action a, we have:\nh(n) ≤ c(n,a,n′)+h(n′). This is a form of the triangle inequality, which stipulates that a side of a triangle cannot be longer than the sum of the other two sides\n\n**Every consistent heuristic is admissible (but not vice versa), so with a consistent heuristic, A∗ is cost-optimal**\n\n**A* Prunes** : A∗ is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.\n\n**f(n) is monotonically increasing iff the heuristic is consistent.**\n\n**Satisficing search** - \n\nA∗ search has many good qualities, but it expands a lot of nodes. We can explore fewer nodes (taking less time and space) if we are willing to accept solutions that are suboptimal, but are “good enough”—what we call satisficing solutions. If we allow A∗ search to use an inadmissible heuristic—one that may overestimate—then we risk missing the optimal solution, but the heuristic can potentially be more accurate, thereby reducing the number of\nnodes expanded. \n\n**weighted A∗ search** : we weight the heuristic value more heavily, giving us the evaluation function f (n) = g(n) + W × h(n), for some W > 1.\n\nIn (a), an A∗ search finds the optimal solution, but has to explore a large portion of the state space to find it. In (b), a weighted A∗ search finds a solution that is slightly costlier, but the search time is much faster.\n\n\nSuboptimal Search Algos : \n\n1. Bounded suboptimal Search - look for solution that is guaranteed to be within a constant factor W of the optimal cost\n2. Bounded Cost Search - look for solutions whose cost is less than 'C'\n3. Unbounded cost search - accept any solution of any cost as long as you find it fast\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n \n\nMain issue with A* - > Use of memory \n\nImplementation tricks to save space : \n\nMemory is split between frontier and reached. Usually frontier is very small comparable to reached but we can use only 1 of these structures to save space. For making our A* efficient, We can keep reference counts of the number of times a state has been reached, and remove it from the reached table when there are no more ways to reach the state.\n\n\nMemory Bounded Search:\n\n1. Beam search :  limits the size of the frontier. The easiest approach is to keep only the k nodes with the best f-scores, discarding any other expanded nodes. Incomplete and suboptimal but with a good 'k' algorithm is faster and can find \"near optimal\" solutions\n\n2. Iterative Deepening A* search: Gives benefits of A* without having to keep all reached states in memory. Used for problems that dont fit in memory. The cut off isn't depth here, the cut off is f-cost at each iteration.\n\n3. Recursive best-first search (RBFS) attempts to mimic the operation of standard best-first search, but using only linear space. RBFS resembles a recursive depth-first search, but rather than continuing indefinitely down the current path, it uses the f_limit variable to keep track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path.\nRBFS is optimal when h(n) is admissible.\n\nIDA* and RBFS use too little memory because they forget most of what they have explored -> both algorithms end up re-exploring the same states again and again\n\nMA* and SMA* : memory bounded and simplified memory bounded A* star\n\nSMA* proceeds just like A*, expanding the best leaf until memory is full. At this point, it cannot add a new node to the search tree without dropping an old one. SMA always drops the worst leaf node—the one with the highest f -value .\nSMA* is complete and optimal if there is a reachable solution(depth of goal node is less than memory size)\n\nBidirectional A star:\n- Front to end: Hf estimates distance to goal and Hb estimates distance to other frontier.\n- Front to front: attempts to estimate the distance to the other frontier.\n \n\n## Module 4 Definitions\n* **Heuristic** - estimated cost of the cheapest path from state at node n to goal state.\n* **Relaxed problem** - fewer restrictions on the actions than the original problem\n* **Relaxed problem cost** - The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nAdversarial Search - Two or more agents have conflicting goals\n\nGame Environment - \n\n- Multiagent\n- Static : No change in environment when agent is delibearting\n- Discrete : Set of actions you take to transition from one state to another is finite\n- Fully observable : Complete state of environment is known\n- Strategic : Env is strategic in the sense that next state is determined by the current state and the action executed by the agent and the actions of the opponent\n\nWhat differentiates games from puzzles is that it is *strategic* and *multiagent*\n\nKey properties of games - \n\n- 2 players alternate moves\n- Zero sum : what is good for one player is bad for the other. There is no 'win-win' outcome\n- Clear set of legal moves\n- Well defined outcomes\n\nMost games in AI are \n1) Deterministic\n2) 2-player\n3) Perfect information (synonymous to fully observable)\n4) turn-talking\n5) Zero sum\n\nMost card games - Stochastic , not deterministic, not fully observable\nMost real-time games - Continuous rather than discrete\n\n**Game as a search** - A game can be formally defined with the following elements:\n\n- S0: The initial state, which specifies how the game is set up at the start.\n- TO-MOVE(s): The player whose turn it is to move in state s.\n- ACTIONS(s): The set of legal moves in state s.\n- RESULT(s, a): The transition model, which defines the state resulting from taking action a in state s.\n- IS-TERMINAL(s): A terminal test, which is true when the game is over and false otherwise. States where the game has ended are called terminal states.\n- UTILITY(s, p): A utility function (also called an objective function or payoff function), which defines the final numeric value to player p when the game ends in terminal state s.\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nGame Tree -\nroot node : first position in which a decision should be made\nEval func f : assigns a real values number to a board position (evaluates the goodness of the current state). Tells us 'how desirable is the current board position'\nTerminal nodes : represent the way the games could end labelled with the desirability of that ending\n\nMINIMAX Algorithm : \n\nbasic idea : Make the best move for MAX assuming MIN always replies with the best move for MIN. Treat your opponent like a rational actor just like you are.\n\nRecursive process - the value at each node in the tree is determined by the value of its children\n- For a MAX node : backed-up value is the maximum values of its children \n- For a MIN node : backed up values is the minimum value of its children\n\nMINIMAX algorithm performs a complete DFS expansion of the game tree. If depth of tree is 'm' and there are 'b' legal moves\n\n- Time complexity : O(b^m)\n- Space complexity : O(bm)\n\nExponential complexity of minimax makes it impractical for complex games. \n\n**Alpha - Beta Pruning :**\n\nNotion : Rather than searching the entire search space to fixed depth, we can get rid of branches if we know they wont be picked i.e prune parts of the tree that make no difference to the outcome.\n\nTo figure out which branches can be prunes we add 2 values alpha and beta\n\nalpha : keeps track of MAX's current lower bound on MAX's outcome. Best value seen for MAX till now (at least)\n\nbeta : keeps track of MIN's current upper bound on MIN's outcome. Best value seen for MIN till now (at most)\n\n**Move Ordering** - \n\nThe effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. \nIf all the worst successors are generated first, then we cant effectively prune the children of a node. If the best succesor had been generated first, then we could have pruned. \nThis is called perfect move ordering where the best succesor is generated first so that the other bad successors can be pruned away. \nIf this could be done perfectly, alpha–beta would need to examine only O(b^m/2) nodes to pick the best move, instead of O(b^m) for minimax. Put another way, alpha– beta with perfect move ordering can solve a tree roughly twice as deep as minimax in the same amount of time.\n\nWe can't achieve perfect move ordering but we can get fairly close. Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the theoretical limit.\nkiller move heuristic : the best moves are called killer moves so try these first before the rest. \nIn game tree search, repeated states can occur because of *transpositions* —different permutations of the move sequence that end up in the same position, and the problem can be addressed with a *transposition table* that caches the heuristic value of states.\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n\n**Heuristic - Alpha Beta tree search**\n\nTo make use of our limited computation time, we can cut off the search early and apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal. In other words, we replace the UTILITY function with EVAL, which estimates a state’s utility. We also replace the terminal test by a cutoff test, which must return true for terminal states, but is otherwise free to decide when to cut off the search, based on the search depth and any property of the state that it chooses to consider. That gives us the formula H-MINIMAX(s, d) for the heuristic minimax value of state s at search depth d:\n\n1) EVAL instead of UTILITY\nA heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state s to player p, return an estimate of the distance to the goal.\n\nFor terminal states it must be that EVAL(s, p) = UTILITY (s, p)\nFor non-terminal states the evaluation must be somewhere in between a loss and a win. UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p).\n\n2) IS-CUTOFF instead of IS-TERMINAL\n\n\nExpected Value : averaging\n\nMaterial Value : assigning a value to the pawns in chess (for example)\n\nWeighted Function: weighted linear function\n\nCutting Off Search: modifying alpha beta to cut off at non terminal states.\n\nThese simple approaches can lead to errors due to the approximate nature of the evaluation function.\n\nThe evaluation function should be applied only to positions that are **quiescent** —that is, positions in which there is no pending move (such as a capturing the queen) that would wildly swing the evaluation.\n\n**The horizon effect**\n\nmore difficult to eliminate. It arises when the program is facing an opponent’s move that causes serious damage and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics.\nOne strategy to mitigate the horizon effect is to allow singular extensions, moves that are “clearly better” than all other moves in a given position, even when the search would normally be cut off at that point.\n\n**Forward Pruning** : Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good ones. Thus, the strategy saves computation time at the risk of making an error.\nThis can be done using:\n\n- Beam search: consider only a “beam” of the n best moves\n- ProbCut: uses statistics gained from prior experience to lessen the chance that the best move will be pruned.\n- Another technique, late move reduction, works under the assumption that move ordering has been done well, and therefore moves that appear later in the list of possible moves are less likely to be good moves.\n\n\n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games bring us a little closer to the unpredictability of real life by including a random element, such as the throwing of dice \nSo far we know the oponent was going to make the most optimal move so we knew we were dealing with a fixed outcome. But in certain games the outcome is uncertain. Uncertain outcomes are controlled by chance -> not an adversary\n\nidea : We dont know what the result of an action can be because of 1) explicit randomness (rolling dice) 2) unpredictable opponents (opponents aren't optimal) 3) actions can fail\n\nSo, Here MAX nodes remain the same as MINI-MAX algorithm. MIN node is now a \"chance\" node -> outcome is uncertain here. \nSo we calculate the expected utilities instead of the MIN Value i.e weighted average of children\n\nMIN Node value = summation ( probability * child values)\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe agent’s prefer- ences are captured by a utility function, U (s), which assigns a single number to express the desirability of a state. The expected utility of an action given the evidence, EU(a), is just the average utility value of the outcomes, weighted by the probability that the outcome occurs:\n\nEU(a) = ∑ P(RESULT(a)=s′)U(s′).\n\nThe principle of maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\naction = argmaxEU(a) \n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nConstraints on Rational Preferences:\n\n- Orderability: Given any two lotteries, a rational agent must either prefer one or else rate them as equally preferable.\n- Transitivity,\n- Continuity,\n- Substitutability,\n- Monotonicity,\n- Decomposability.\n\nAs in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function.\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n \nPsuedo code for MINMAX - \n\n- start with the current position as MAX node\n- expand the game tree to a fixed level\n- apply the evaluation function at the leaves\n- calculate the back-up values bottom up\n- pick a move assigned to MAX at root\n- wait for MIN to respond\n\n5.3 continuation: Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the theoretical limit. The past could be the previous move—often the same threats remain—or it could come from previous exploration of the current move through a process of iterative deepening .\nThe best moves are known as killer moves, and to try them first is called the killer move heuristic.\nIn game tree search, repeated states can occur because of transpositions—different permutations of the move sequence that end up in the same position, and the problem can be addressed with a transposition table that caches the heuristic value of states.\n\nGo and Chess - \n\nEven with alpha–beta pruning and clever move ordering, minimax won’t work for games like chess and Go, because there are still too many states to explore in the time available.\n2 stratergies that work for chess is :\n\n- Type A : Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree. \n- Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree.\n\n\n\n## Module 5 Definitions\n* **Quiescent** -  positions in which there is no pending move that would wildly swing the evaluation\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \n\nsearch algorithm, each state is atomic, or indivisible— a black box with no internal structure. For each problem we need domain-specific code to describe the transitions between states.\nIn this chapter we break open the black box by using a factored representation for each state: a set of variables, each of which has a value. A problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem, or CSP.\n\nCSP search algorithms take advantage of the structure of states and use general rather than domain-specific heuristics to enable the solution of complex problems. The main idea is to eliminate large portions of the search space all at once by identifying variable/value combinations that violate the constraints.\n\nA constraint satisfaction problem consists of three components, X,D, and C:\n\n- X is a set of variables, {X1,...,Xn}.\n- D is a set of domains, {D1,...,Dn}, one for each variable.\n- C is a set of constraints that specify allowable combinations of values.\n\nA domain, Di, consists of a set of allowable values, {v1,...,vk}, for variable Xi\n\nCSPs deal with assignments of values to variables,{Xi=vi,Xj=vj,...}.\n\n- An assignment that does not violate any constraints is called a **consistent or legal assignment**\n- A **complete assignment** is one in which every variable is assigned a value. \n- solution to a CSP is a **consistent, complete assignment**.\n\nA **partial assignment** is one that leaves some variables unassigned\nA **partial solution** is a partial assignment that is consistent. \n\nSolving a CSP is an NP-complete problem in general\n\n\nIn CSP -> instead of planning a sequence of actions we want to identify assignments to variables -> main diffreence between search and CSP\n\n- Goal is more important than the path\n- All paths are same depth\n- CSPs are specialised for identification problems\n\nsolutions to CSPs can be found by a completely general algorithm given only a formal specification of the CSP. \n\nTypes of CSP formulisations -\n\nAll CSP problems have **finite and discrete domains**. \nDiscrete domains can also be **infinite** such as set of real valued numbers, set of integers and can be continuous too. \n\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n\nWe say that a CSP is bounds-consistent if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of X that satisfies the constraint between X and Y for every variable Y\n\nn-ary constraints use a constraint hypergraph\n\nConstraint Propogation : using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on.\nThe idea is that this will leave fewer choices to consider when we make the next choice of a variable assignment. Constraint propagation may be intertwined with search, or it may be done as a preprocessing step, before search starts.\n\nLocal consistency : If we treat each variable as a node in a graph (see Figure 6.1(b)) and each binary constraint as an edge, then the process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph.\n\nTypes of Local consistency - \n\n1. Node consistency : satisfying unary constraints\n\n2. Arc consistency : satisfying binary constraints : xi and xj are arc consistent if for every value in domain Di there is a corresponding value w in Dj that satisfies the binary constraint on arc between xi ans xj\n\n3. Path consistency : Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\nA two-variable set {Xi,Xj} is path-consistent with respect to a third variable Xm if, for every assignment {Xi = a, X j = b} consistent with the constraints (if any) on {Xi , X j }, there is an assignment to Xm that satisfies the constraints on {Xi,Xm} and {Xm,Xj}. The name refers to the overall consistency of the path from Xi to Xj with Xm in the middle.\n\n4. K- consistent : A CSP is k- consistent if, for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. 1-consistency says that, given the empty set, we can make any set of one variable consistent: this is what we called node consistency. 2-consistency is the same as arc consistency. For binary constraint graphs, 3- consistency is the same as path consistency.\n\n5. Strongly k- consistent : A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)- consistent, ... all the way down to 1-consistent\n\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nWhen after running CSP, domains are not unary. Need to backtrack to check the solution.\n\nTypes of Backtracking - \n\n1. Static ordering backtracking: choosing variables in order\n\n2. Random ordering backtracking: choosing variables in random order\n\n3. Intelligent backtracking: backtrack the most recent variable which made the assignment inconsistent.\n\n\nBack Tracking Search in CSP : dfs choses one value for one variable at a time and backtracks when a variable has no legal values left to assign.  \n\nHow to improve ?? -> heuristics \n\n1. Which variable should be assigned next ?\n\nChose a variable with fewer remaining legal values first aka **MRV heuristic - Minimum Remaining values heuristic**.\n\nIf there is a tie pick the **most constraining variable** i.e pick the variable with most constraints on remaining variables.\n\n2. What order should that variables value be tried?\n\nGiven a variable, chose the least constarining value -> the one that rules out fewest remaining variables. \n\n3. Can we detect failure early? \n\n- Use forward checking : One of the simplest forms of inference is called forward checking. Whenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each unas- signed variable Y that is connected to X by a constraint, delete from Y ’s domain any value that is inconsistent with the value chosen for X .\n\nFor many problems the search will be more effective if we combine the MRV heuristic with forward checking. Although forward checking detects many inconsistencies, it does not detect all of them. The problem is that it doesn’t look ahead far enough.\n\nThus, AC3 or MAC (Maintainign Arc Consistency) :\n\nThe algorithm called MAC (for Maintaining Arc Consistency) detects inconsistencies like this. After a variable Xi is assigned a value, the INFERENCE procedure calls AC-3, but instead of a queue of all arcs in the CSP, we start with only the arcs (Xj,Xi) for all Xj that are unassigned variables that are neighbors of Xi. From there, AC-3 does constraint propagation in the usual way, and if any variable has its domain reduced to the empty set, the call to AC-3 fails and we know to backtrack immediately. We can see that MAC is strictly more powerful than forward checking because forward checking does the same thing as MAC on the initial arcs in MAC’s queue; but unlike MAC, forward checking does not recursively propagate constraints when changes are made to the domains of variables.\n\n- \n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nThe most obvious approach is to select the value that results in the minimum number of conflicts with other variables—**the min-conflicts heuristic**. Especially for N queens. Move the queens to minimum conflict position.\n\nThe landscape of a CSP under the min-conflicts heuristic usually has a series of plateaus.\n**Plateau search**— allowing sideways moves to another state with the same score—can help local search find its way off this plateau.\nThis wandering on the plateau can be directed with a technique called tabu search: keeping a small list of recently visited states and forbidding the algorithm to return to those states. Simulated annealing can also be used to escape from plateaus.\nAnother technique called constraint weighting aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment. This has two benefits: it adds topography to plateaus, making sure that it is possible to improve from the current state, and it also adds learning: over time the difficult constraints are assigned higher weights.\nAnother advantage of local search is that it can be used in online settings when the problem changes.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n \nCSP as a search problem : \n\n 1. initial state : {}\n\n 2. Successor function : Assign values to any unassigned variable provided there is no constraint conflict\n\n 3. Goal Test : Is the current assignment complete\n\n 4. Path cost : A constant cost at each step\n\n In CSP -> solution is always found in depth 'n' for 'n' variables hence DFS can be used.\n\n Time Complexity : \n\n - Assume n- variables each of which take 'd' values.\n - Branching factor = n*d, of next level = (n-1)*d leaves\n\n**so tree has O(n!d^n) leaves**\n\n CSPs cut down the search space because the order of assignment of variables does not matter. problem is **Commutative**. hence, its a **tree search** not a **graph search**.\n\n**Now it is reduced from O(n! d^n) to O(d^n) - search space is pruned**\n\n**Benefits of CSP** \n\n- Clean specification of many problems with a generic goal, succesor function and heuristics\n- CSPs know which variables violate a constraint and hence know where to focus the search\n- They automatically prune off all branches that violate constraints \n\nApplications : 1) Sudoko 2) Scheduling problems 3) MAP coloring 4) Floor planning VLSI\n\nIntelligent backtracking: Keep a conflict set: a set of assignment of variables that caused the conflict for the other variable. (to backtrack on variables that fixed the problem). The backjumping method backtracks to the most recent assignment in the conflict set.\nBackjumping is the same as forward checking.\n\nWhen we reach a contradiction, backjumping can tell us how far to back up, so we don’t waste time changing variables that won’t fix the problem.\n\nConstraint Learning: Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods. (basically a visited array of already checked assignments).\nNo goods can be computed by forward checking or back jumping.\n\n\n \n\n## Module 6 Definitions\n* **Disjunctive constraints** - that don’t overlap(algebraic plus disjunctive)\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nproblem solving agent -> They know what actions are available and what is the result of performing a specific action from a specific state will be but they dont know general facts\n\nLogical agents -> Use a process of reasoning over an internal representation of knowledge to decide what actions to take next\n\nThe central component of a knowledge-based agent is its knowledge base, or KB.\n\nA knowledge base is a set of sentences. Each sentence is expressed in a knowledge representation language and represents some assertion about the world. \n\nSentences in KB : \n- Axiom : Sentence is given\n- Derived : New sentences are derived from other sentences\n\nProcess of deriving new sentences from old sentences is called **inference**\n\nEach time the agent program is called, it does three things: \n- First, it Tells the knowledge base what it perceives.\n- Second, it Asks the knowledge base what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on.\n- Third, the agent program Tells the knowledge base which action was chosen, and returns the action so that it can be executed.\n \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nComplex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives.\n\nConjunction - intersection - and Disjunction - union - or\n\nLogical Equivalence : two sentence a and b are logically equivalent if they are true in the same set of models\n\na and b are logically eq iff a|=b and b|=a\n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \n\n**monotonicity** : which says that the set of entailed sentences can only increase as information is added to the knowledge base.\n\n**Monotonicity => Soundness** : if we add additional info into the KB, it doesn't invalidate any other info that we have already inferred\n\n**Converting a sentence to CNF :**\n\nEvery sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals.\n\n- Eliminate ⇔ by replacing a⇔ β with (a ⟹ β) ⋀ (β ⟹a)\n- Eliminate ⟹ by replacing a ⟹ β with ¬a ⋁ β (implication elimination)\n- Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n\nNow the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\nThe sentence is now in CNF!\n\n**Resolution Algorithm**\n\nto show KB |= a we show that KB ^ ¬a is unsatisfiable.\n\n1. first convert KB ^ ¬a into CNF\n2. Apply resolution to resulting clauses\n3. Resolve every pair that contains complementary literals to produce a new clause\n4. If that clause is not present then add it to a set\nContinue until : \n(a) no new clause to be added to KB (KB does not entail a)\n(b) two clauses resolve to yield an empty clause (KB entails a)\n\n\n\n\n \n\n## Module 7 Lecture Notes\n \n\nIf you restrict the KB to have only certain types of sentences in it (a more restrictive KB) -> enables to use more efficient inference algorithms\n\n- Definite Clause : Disjunction of literals where exactly 1 is positive\n- Horn Clause : Disjunction of literals where atmost 1 is positive\n\nHorn Clause is closed under resolution. If you apply resolution to a horn clause, you get back a horn clause.\n\nEvery definite clause can be written as an implication. \n\nInference with Horn clauses can be done through the forward-chaining and backward-chaining algorithms. Deciding entailment with Horn clauses can be done in linear time with respect to the size of the KB.\n\n**Forward Chaining is a kind of data-driven reasoning**. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\n\nBackward chaining works backwards from a query. If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n**Backward chaining is a form of goal-directed reasoning.**\n\n \n\n## Module 7 Definitions\n* **Sound** - the inference algorithm should only derive valid entailments\n* **Complete** - an inference algorithm is complete if it can derive all valid entailments\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}