{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "mmonoor_CIS521_midterm_notes.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "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": "eeb27853-b9c1-4c9f-ed61-388e07a1ebad"
      },
      "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": 43,
      "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": "79e1517a-b6f5-4e3a-95df-a0bd2a607c7f"
      },
      "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": 44,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True "
      ],
      "execution_count": 45,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\"\"\" \n",
        "\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",
        "chapter27_2 = \"\"\" \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \"\"\"\n",
        "chapter2_2 = \"\"\"  \"\"\"\n",
        "chapter2_3 = \"\"\"  \"\"\"\n",
        "chapter2_4 = \"\"\"  \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"It is best to design performance measures based on what you want to be achieved by the agent rather than how you think the agent should behave. \n",
        "\n",
        "Our environment restrictions are static, fully observable, deterministic, and discrete. \n",
        "Elements needed to formulate a search problem: \n",
        "1. States\n",
        "2. Actions\n",
        "3. Performance measures\n",
        "4. Goal (kind of)\n",
        "5. Solution (kind 0f)\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {'Agents': ' anything that perceives its environments through sensors and can act on its environment through actuators. ', 'Agent function': ' specifies an agent; function maps a sequence of percept vectors P to an action a from a set A. ', 'Rational Agent': ' for each possible percept sequence, a rational agent selects an action that maximizes the expected value of its performance measure. ', 'Consequentialism': ' evaluating an agent’s behaviour by its consequences. ', 'Percept': ' is the agent’s perceptual inputs at any given instance. ', 'Episodic': ' next episode doesn’t depend on current', 'Non-deterministic ': ' chance based', 'Stochastic ': ' probabilistic', 'Simple reflex agent ': ' agent selects actions on the basis of the current percept, ignoring the rest of the percept history. '}\n"
      ],
      "execution_count": 46,
      "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": 824
        },
        "outputId": "e54ee90d-091b-42e9-9c1d-fc37ae149100"
      },
      "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": 47,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Agent function' is too long!\nWARNING: Your definition of 'Rational Agent' is too long!\n# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \n\n## AIMA 2.1 Agents and Environments\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n  \n\n## AIMA 2.3 The Nature of Environments\n  \n\n## AIMA 2.4 The Structure of Agents\n  \n\n## Module 1 Lecture Notes\nIt is best to design performance measures based on what you want to be achieved by the agent rather than how you think the agent should behave. \n\nOur environment restrictions are static, fully observable, deterministic, and discrete. \nElements needed to formulate a search problem: \n1. States\n2. Actions\n3. Performance measures\n4. Goal (kind of)\n5. Solution (kind 0f)\n\n\n## Module 1 Definitions\n* **Agents** -  anything that perceives its environments through sensors and can act on its environment through actuators. \n* **Agent function** -  specifies an agent; function maps a sequence of percept vectors P to an action a from a set A. \n* **Rational agent** -  for each possible percept sequence, a rational agent selects an action that maximizes the expected value of its performance measure. \n* **Consequentialism** -  evaluating an agent’s behaviour by its consequences. \n* **Percept** -  is the agent’s perceptual inputs at any given instance. \n* **Episodic** -  next episode doesn’t depend on current\n* **Non-deterministic ** -  chance based\n* **Stochastic ** -  probabilistic\n* **Simple reflex agent ** -  agent selects actions on the basis of the current percept, ignoring the rest of the percept history. \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" \n",
        "Slices:  \\n\n",
        "a[-1] # last item in the array  \\n\n",
        "a[-2:] # last two items in the array \\n\n",
        "a[:-2] # everything except the last two items \\n\n",
        "a[::-1] # all items in the array, reversed  \\n\n",
        "a[1::-1] # the first two items, reversed  \\n\n",
        "a[:-3:-1] # the last two items, reversed  \\n\n",
        "a[-3::-1] # everything except the last two items, reversed \\n\n",
        " \\n\n",
        "List operations:  \\n\n",
        "li.index(‘a’) <- index of first occurrence  \\n\n",
        "li.count(‘a’) <- number of occurrences  \\n\n",
        "li.remove(‘a’) <- remove first occurrence  \\n\n",
        "li.reverse() <- reverse the list in place  \\n\n",
        "li.sort() <- sort the list in place \\n\n",
        " \\n\n",
        "Args: \\n\n",
        "*args in the function variable lets the function accept non keyword arguments.  \\n\n",
        "**kwargs is a dict of keyword arguments being passed in  \\n\n",
        " \\n\n",
        "Iterators are more memory efficient than lists.  \\n\n",
        "Reloading code from a file: use importlib.reload(py_file) \\n\n",
        "\n",
        "Hash function is defined as any function that can be used to map data of arbitrary size of data to a fixed size data.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {'REPL ': ' read evaluate print loop', 'Strong typing ': ' every object has a fixed type and incompatible objects can’t go together', 'Dynamic typing ': ' variables come into assignment when first assigned. Drawback is that type errors are caught at run time. ', 'Strings ': ' immutable ', 'Magic Methods ': ' allow user', 'Nested list comp ': ' res = [(x, y, z) for x in lst1 if x < 2 for y in lst2 for z in lst3 if x + y + z < 8]', 'Iterators ': '  are objects with a __next__() method', 'Yields ': '  every time we call a next method on the generator, the method runs until it encounters the yield statement and then it stops and returns the value that was yielded. Next time it resumes where it left off.', 'Shallow copy ': ' use y = x [:]'}"
      ],
      "execution_count": 48,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 847
        },
        "outputId": "71ae75db-9160-409e-a187-a890bf2d6863"
      },
      "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": 49,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Nested list comp ' is too long!\nWARNING: Your definition of 'Yields ' is too long!\n# Module 2: Python\n## Module 2 Lecture Notes\n \nSlices:  \n\na[-1] # last item in the array  \n\na[-2:] # last two items in the array \n\na[:-2] # everything except the last two items \n\na[::-1] # all items in the array, reversed  \n\na[1::-1] # the first two items, reversed  \n\na[:-3:-1] # the last two items, reversed  \n\na[-3::-1] # everything except the last two items, reversed \n\n \n\nList operations:  \n\nli.index(‘a’) <- index of first occurrence  \n\nli.count(‘a’) <- number of occurrences  \n\nli.remove(‘a’) <- remove first occurrence  \n\nli.reverse() <- reverse the list in place  \n\nli.sort() <- sort the list in place \n\n \n\nArgs: \n\n*args in the function variable lets the function accept non keyword arguments.  \n\n**kwargs is a dict of keyword arguments being passed in  \n\n \n\nIterators are more memory efficient than lists.  \n\nReloading code from a file: use importlib.reload(py_file) \n\n\nHash function is defined as any function that can be used to map data of arbitrary size of data to a fixed size data.\n\n \n\n## Module 2 Definitions\n* **Repl ** -  read evaluate print loop\n* **Strong typing ** -  every object has a fixed type and incompatible objects can’t go together\n* **Dynamic typing ** -  variables come into assignment when first assigned. Drawback is that type errors are caught at run time. \n* **Strings ** -  immutable \n* **Magic methods ** -  allow user\n* **Nested list comp ** -  res = [(x, y, z) for x in lst1 if x < 2 for y in lst2 for z in lst3 if x + y + z < 8]\n* **Iterators ** -   are objects with a __next__() method\n* **Yields ** -   every time we call a next method on the generator, the method runs until it encounters the yield statement and then it stops and returns the value that was yielded. Next time it resumes where it left off.\n* **Shallow copy ** -  use y = x [:]\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 = \"\"\" Describe the 4 phase problem solving process:  \\n\n",
        "Goal Formulation: The agent adopts a goal so their behaviour can be limited along with actions they have to consider.  \\n\n",
        "Problem Formulation: Agent creates a description of the states and actions that are necessary to reach that goal.  \\n\n",
        "Search: Before taking any action on the real world the agent creates a simulation of the sequences of actions it could take so it ends in the goal step created during goal formulation. This is also the solution.  \\n\n",
        "Execution: having derived a solution, the agent can act on it in the real world.  \\n\n",
        "  \\n\n",
        "What type of environment will result in a solution to any problem as a fixed sequence of actions? \\n\n",
        "Fully observable \\n\n",
        "Deterministic  \\n\n",
        "Known  \\n\n",
        " \\n\n",
        "Explain when an agent should use an open loop vs. closed loop system:  \\n\n",
        "Open loop - When the agent is working with an environment that results in a solution through a fixed sequence of actions, the agent can essentially close his eyes and carry out the solution.  \\n\n",
        "Closed loop- If the environment is unknown/ non-deterministic/ or not fully observable, the agent needs his percept and will require a closed-loop system.  \\n\n",
        "Use a branching strategy that recommends a potential path forward based on what percepts arrive. Essentially, “legolas what does your elf eye see” kind of situation.  \\n\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" What are the components of a search problem? \\n\n",
        "1. State space - all possible states the environment can be in \\n\n",
        "2. Initial state - the starting configuration of the agent.  \\n\n",
        "3. Goal state - there can be one or many.  \\n\n",
        "4. Actions - given a state s, all the actions that the agent can take   \\n\n",
        "5. Transition model - Given an action and a state, describes what the resulting state is.  \\n\n",
        "6. Action cost model - cost of the transition model,  the price we pay to go from a state with an action applied to it to the final state.  \\n\n",
        " \\n\n",
        "What makes something have an optimal solution? \\n\n",
        "The lowest path cost.  \\n\n",
        " \\n\n",
        "What is abstraction and how do we make sure we have a good level of abstraction? \\n\n",
        "Process of removing details  \\n\n",
        "Valid: If we can elaborate any abstract solution into a solution in the more detailed world \\n\n",
        "Useful: if carrying out each action in the solution is easier than carrying it out in the real world.  \\n\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" Search Algorithms: \\n\n",
        " \\n\n",
        "Takes a search problem as an input and returns a solution.  \\n\n",
        " \\n\n",
        "What is the difference between state space and the search tree? \\n\n",
        "The state space describes the possible infinite set of states in the world and all the actions we will need to take to go from one state to the other. The search tree is the path between these states going towards the goal state.  \\n\n",
        " \\n\n",
        "What does expanding a node in a search tree mean? \\n\n",
        "Each node in a search tree tells us the state in the state space and the edges represent corresponding actions. When we expand a node, we consider all the possible actions (edges) and the corresponding states (child nodes) deriving from those actions. We continue by assessing the child states and picking the next child node to expand. Any state that has a node generated has been reached, whether or not we further expanded it.  \\n\n",
        " \\n\n",
        "What does the frontier of a search tree do? \\n\n",
        "It allows us to separate the search tree into two regions. One region where we have nodes that we have reached and expanded, and an exterior region that we have not reached. The frontier is the node we reached but have yet to expand.  \\n\n",
        " \\n\n",
        "BFS is complete even for an infinite-depth search space. \\n\n",
        "\\n\n",
        "Graph vs. tree search: Graph search, we include a set of explored nodes in order to handle repeat states. We also only choose to add nodes to the frontier if they have already not been explored.  \\n\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\" Measuring Problem-Solving Algorithm Performance \\n\n",
        "1. Completeness - are we guaranteed a solution? \\n\n",
        "2. Cost Optimality - does it return the lowest cost solution? \\n\n",
        "3. Time Complexity - run time complexity or real time measurement of finding solution.  \\n\n",
        "4. Space Complexity - memory needed to perform the search or the number of does simultaneously in memory.  \\n\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" BFS - good for finding the shortest path \\n \n",
        "DFS - Expands the deepest nodes in the frontier first. Advantage is that it has better space complexity than BFS. The space complexity of BFS is O(b^d), while DFS has a lower complexity of O(bm). \\n\n",
        "Implemented more of a tree search where a dictionary of visited states is not persisted. In the case of backtracking, only one successor is generated instead of all successors\n",
        "\\n \\n\n",
        "GBFS, UCS, and A* all uses a priority queue\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 = {'        Problem solving agents ': ' agent looks ahead and sees a sequence of actions that will eventually achieve its goals. ', 'Solution ': ' path to a goal state', 'Optimal solution ': ' solution with the lowest path cost. ', 'Atomic representations ': ' states of the world are considered as whole and no internal structures are visible to the problem solving algorithms. ', 'Planning agents ': ' instead of using atomic representations like problem solving agents, use factored or structured representations. ', 'Informed Algorithms ': ' agent knows how far away they are from the solution state. ', 'Uninformed Algorithms ': ' agent does not have an estimate of how far they are away from the solution state. ', 'Systematic ': ' a search algorithm that explores an infinite state space but can eventually reach any state that is connected to the initial state. ', 'Branching factor ': ' number of successors for a node that needs to be considered. ', 'Search Algorithms ': ' algorithms that take a search problem as an input and return a solution. '}\n",
        "\n"
      ],
      "execution_count": 50,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "865c172f-e635-43c7-ac58-3aba36cfe80a"
      },
      "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": 51,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Atomic representations ' is too long!\nWARNING: Your definition of 'Systematic ' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Describe the 4 phase problem solving process:  \n\nGoal Formulation: The agent adopts a goal so their behaviour can be limited along with actions they have to consider.  \n\nProblem Formulation: Agent creates a description of the states and actions that are necessary to reach that goal.  \n\nSearch: Before taking any action on the real world the agent creates a simulation of the sequences of actions it could take so it ends in the goal step created during goal formulation. This is also the solution.  \n\nExecution: having derived a solution, the agent can act on it in the real world.  \n\n  \n\nWhat type of environment will result in a solution to any problem as a fixed sequence of actions? \n\nFully observable \n\nDeterministic  \n\nKnown  \n\n \n\nExplain when an agent should use an open loop vs. closed loop system:  \n\nOpen loop - When the agent is working with an environment that results in a solution through a fixed sequence of actions, the agent can essentially close his eyes and carry out the solution.  \n\nClosed loop- If the environment is unknown/ non-deterministic/ or not fully observable, the agent needs his percept and will require a closed-loop system.  \n\nUse a branching strategy that recommends a potential path forward based on what percepts arrive. Essentially, “legolas what does your elf eye see” kind of situation.  \n\n\n\n## AIMA Chapter 3.2 Example Problems\n What are the components of a search problem? \n\n1. State space - all possible states the environment can be in \n\n2. Initial state - the starting configuration of the agent.  \n\n3. Goal state - there can be one or many.  \n\n4. Actions - given a state s, all the actions that the agent can take   \n\n5. Transition model - Given an action and a state, describes what the resulting state is.  \n\n6. Action cost model - cost of the transition model,  the price we pay to go from a state with an action applied to it to the final state.  \n\n \n\nWhat makes something have an optimal solution? \n\nThe lowest path cost.  \n\n \n\nWhat is abstraction and how do we make sure we have a good level of abstraction? \n\nProcess of removing details  \n\nValid: If we can elaborate any abstract solution into a solution in the more detailed world \n\nUseful: if carrying out each action in the solution is easier than carrying it out in the real world.  \n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n Search Algorithms: \n\n \n\nTakes a search problem as an input and returns a solution.  \n\n \n\nWhat is the difference between state space and the search tree? \n\nThe state space describes the possible infinite set of states in the world and all the actions we will need to take to go from one state to the other. The search tree is the path between these states going towards the goal state.  \n\n \n\nWhat does expanding a node in a search tree mean? \n\nEach node in a search tree tells us the state in the state space and the edges represent corresponding actions. When we expand a node, we consider all the possible actions (edges) and the corresponding states (child nodes) deriving from those actions. We continue by assessing the child states and picking the next child node to expand. Any state that has a node generated has been reached, whether or not we further expanded it.  \n\n \n\nWhat does the frontier of a search tree do? \n\nIt allows us to separate the search tree into two regions. One region where we have nodes that we have reached and expanded, and an exterior region that we have not reached. The frontier is the node we reached but have yet to expand.  \n\n \n\nBFS is complete even for an infinite-depth search space. \n\n\n\nGraph vs. tree search: Graph search, we include a set of explored nodes in order to handle repeat states. We also only choose to add nodes to the frontier if they have already not been explored.  \n\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Measuring Problem-Solving Algorithm Performance \n\n1. Completeness - are we guaranteed a solution? \n\n2. Cost Optimality - does it return the lowest cost solution? \n\n3. Time Complexity - run time complexity or real time measurement of finding solution.  \n\n4. Space Complexity - memory needed to perform the search or the number of does simultaneously in memory.  \n\n \n\n## Module 3 Lecture Notes\n BFS - good for finding the shortest path \n \nDFS - Expands the deepest nodes in the frontier first. Advantage is that it has better space complexity than BFS. The space complexity of BFS is O(b^d), while DFS has a lower complexity of O(bm). \n\nImplemented more of a tree search where a dictionary of visited states is not persisted. In the case of backtracking, only one successor is generated instead of all successors\n\n \n\nGBFS, UCS, and A* all uses a priority queue\n\n\n## Module 3 Definitions\n* **        problem solving agents ** -  agent looks ahead and sees a sequence of actions that will eventually achieve its goals. \n* **Solution ** -  path to a goal state\n* **Optimal solution ** -  solution with the lowest path cost. \n* **Atomic representations ** -  states of the world are considered as whole and no internal structures are visible to the problem solving algorithms. \n* **Planning agents ** -  instead of using atomic representations like problem solving agents, use factored or structured representations. \n* **Informed algorithms ** -  agent knows how far away they are from the solution state. \n* **Uninformed algorithms ** -  agent does not have an estimate of how far they are away from the solution state. \n* **Systematic ** -  a search algorithm that explores an infinite state space but can eventually reach any state that is connected to the initial state. \n* **Branching factor ** -  number of successors for a node that needs to be considered. \n* **Search algorithms ** -  algorithms that take a search problem as an input and return a solution. \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Informed Heuristic Search Algorithms\\n\n",
        "\\n\n",
        "Greedy BFS f(n) = h(n) - BFS search that uses the cost function to expand the best node at each step.\\n\n",
        "Greedy best-first graph search is complete in finite state spaces, but not in infinite ones.\\n\n",
        "The worst-case time and space complexity is O(|V|). With a good heuristic function, however,the complexity can be reduced substantially, on certain problems reaching O(bm).\\n\n",
        "\\n\n",
        "A* Search - uses BFS and an evaluation function \\n\n",
        "f(n) = g(n) + h(n)\\n\n",
        "g(n): path cost from initial state to node n\\n\n",
        "h(n): estimated cost of shortest path from n to a goal state\\n\n",
        "f(n): estimated cost of the best path that goes through n to goal state \\n\n",
        " \\n\n",
        "\tA* is complete and if it uses an admissible heuristic, it is cost-optimal. \\n\n",
        "\\n\n",
        "IDA*: It is a very important and commonly used algorithm for problems that do not fit in memory\n",
        "\\n\n",
        "If C* is the cost of the optimal solution path, then we will DEFINITELY expand all the nodes where they cost of getting to that node f(n) is then than the optimal cost of the solution path C*. A* may expand some of the nodes where f(n)== C*, these are nodes right on the goal conture.\\n\n",
        "\\n\n",
        "A* with a consistent heuristic is optimally efficient. \\n\n",
        "It is also efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.  \\n\n",
        "\t\\n\n",
        "Using inadmissible heuristic with A* - we risk missing the optimal solution but if we are happy with a solution that is close enough, by overestimating the heuristic function we can end up with a solution that expands fewer nodes. A* has the weakness of expanding a lot of nodes and as a result high memory usage.\\n\n",
        "\\n\n",
        "Run time depends on the heuristic but for an unbounded problem with depth d, it is O(bd).\n",
        "The space complexity is O(b^d).\n",
        "\\n\n",
        "branching factor: \\n\n",
        "Smaller branching factor means more nodes will be pruned and make the algorithm more efficient\n",
        "\\n\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "Heuristics \\n\n",
        "\\n\n",
        "If h1(n) >= h2(n), then h1 dominates h2 \\n\n",
        " \\n\n",
        "Heuristic accuracy can impact performance. If a heuristic has an effective branch factor b* close to 1, a relatively large problem can be solved at a reasonable computational cost. We know that every node with h(n) < C* - g(n) will be expanded. With a collection of admissible heuristics, we can pick the best heuristic from a given node by doing h(n) = max(h_1(n)+h_2(n)+..h_k(n)).  \\n\n",
        "A heuristic is admissible if it never overestimates the true cost to a nearest goal. A heuristic is consistent if, when going from neighboring nodes a to b, the heuristic difference/step cost never overestimates the actual step cost. It is actually challenging to come up with a heuristic that is admissible and not consistent.  \\n\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"Since A* is costly to use when it comes to memory, it seems sensible, therefore, to determine how much memory we have available, and\n",
        "allow an algorithm to use all of it. Two algorithms that do this are MA ∗ (memory-bounded\n",
        "A ∗ ) and SMA ∗ (simplified MA ∗ ). SMA ∗ is—well—simpler, so we will describe it. SMA ∗\n",
        "proceeds just like A ∗ , expanding the best leaf until memory is full. At this point, it cannot add\n",
        "a new node to the search tree without dropping an old one. SMA ∗ always drops the worst leaf\n",
        "node—the one with the highest f -value. Like RBFS, SMA ∗ then backs up the value of the\n",
        "forgotten node to its parent. In this way, the ancestor of a forgotten subtree knows the quality\n",
        "of the best path in that subtree. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {'        Informed Search  ': ' using domain specific hints', 'Heuristic Function ': ' estimated cost of the cheapest path from the state at node n to a goal state. ', 'Admissible Heuristic ': ' one that never overestimates the cost of reaching a goal, also seen as optimistic. ', 'Monotonic/ consistent heuristic ': ' path cost always increases as you go along a path because action costs are always positive.', 'Strictly monotonic ': '  has cost always going up where monotonic is where cost doesn’t go down. ', 'Bounded suboptimal search ': ' solution that is guaranteed to be within a constant factor of W, e.g. weighted A*. ', 'Bounded Cost search ': ' solution whose cost is less than a constant C.', 'Unbounded Cost search ': ' accept a solution at any cost as long as we can find it quickly. ', 'Manhattan Distance ': ' sum of horizontal and vertical distances, used when can’t make diagonal moves. ', 'Effective branching factor b* ': ' If the total number of nodes generated by A* for a particular problem is N and the solution depth is d, then b* is the branching factor a tree with uniform depth d will have to have in order to contain N+1 Nodes. '}\n",
        "\n"
      ],
      "execution_count": 52,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5d1e8650-75b8-483e-99f3-b54b4effca5d"
      },
      "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": 53,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Effective branching factor b* ' is too long!\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed Heuristic Search Algorithms\n\n\n\nGreedy BFS f(n) = h(n) - BFS search that uses the cost function to expand the best node at each step.\n\nGreedy best-first graph search is complete in finite state spaces, but not in infinite ones.\n\nThe worst-case time and space complexity is O(|V|). With a good heuristic function, however,the complexity can be reduced substantially, on certain problems reaching O(bm).\n\n\n\nA* Search - uses BFS and an evaluation function \n\nf(n) = g(n) + h(n)\n\ng(n): path cost from initial state to node n\n\nh(n): estimated cost of shortest path from n to a goal state\n\nf(n): estimated cost of the best path that goes through n to goal state \n\n \n\n\tA* is complete and if it uses an admissible heuristic, it is cost-optimal. \n\n\n\nIDA*: It is a very important and commonly used algorithm for problems that do not fit in memory\n\n\nIf C* is the cost of the optimal solution path, then we will DEFINITELY expand all the nodes where they cost of getting to that node f(n) is then than the optimal cost of the solution path C*. A* may expand some of the nodes where f(n)== C*, these are nodes right on the goal conture.\n\n\n\nA* with a consistent heuristic is optimally efficient. \n\nIt is also efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.  \n\n\t\n\nUsing inadmissible heuristic with A* - we risk missing the optimal solution but if we are happy with a solution that is close enough, by overestimating the heuristic function we can end up with a solution that expands fewer nodes. A* has the weakness of expanding a lot of nodes and as a result high memory usage.\n\n\n\nRun time depends on the heuristic but for an unbounded problem with depth d, it is O(bd).\nThe space complexity is O(b^d).\n\n\nbranching factor: \n\nSmaller branching factor means more nodes will be pruned and make the algorithm more efficient\n\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \nHeuristics \n\n\n\nIf h1(n) >= h2(n), then h1 dominates h2 \n\n \n\nHeuristic accuracy can impact performance. If a heuristic has an effective branch factor b* close to 1, a relatively large problem can be solved at a reasonable computational cost. We know that every node with h(n) < C* - g(n) will be expanded. With a collection of admissible heuristics, we can pick the best heuristic from a given node by doing h(n) = max(h_1(n)+h_2(n)+..h_k(n)).  \n\nA heuristic is admissible if it never overestimates the true cost to a nearest goal. A heuristic is consistent if, when going from neighboring nodes a to b, the heuristic difference/step cost never overestimates the actual step cost. It is actually challenging to come up with a heuristic that is admissible and not consistent.  \n\n \n\n## Module 4 Lecture Notes\nSince A* is costly to use when it comes to memory, it seems sensible, therefore, to determine how much memory we have available, and\nallow an algorithm to use all of it. Two algorithms that do this are MA ∗ (memory-bounded\nA ∗ ) and SMA ∗ (simplified MA ∗ ). SMA ∗ is—well—simpler, so we will describe it. SMA ∗\nproceeds just like A ∗ , expanding the best leaf until memory is full. At this point, it cannot add\na new node to the search tree without dropping an old one. SMA ∗ always drops the worst leaf\nnode—the one with the highest f -value. Like RBFS, SMA ∗ then backs up the value of the\nforgotten node to its parent. In this way, the ancestor of a forgotten subtree knows the quality\nof the best path in that subtree. \n\n## Module 4 Definitions\n* **        informed search  ** -  using domain specific hints\n* **Heuristic function ** -  estimated cost of the cheapest path from the state at node n to a goal state. \n* **Admissible heuristic ** -  one that never overestimates the cost of reaching a goal, also seen as optimistic. \n* **Monotonic/ consistent heuristic ** -  path cost always increases as you go along a path because action costs are always positive.\n* **Strictly monotonic ** -   has cost always going up where monotonic is where cost doesn’t go down. \n* **Bounded suboptimal search ** -  solution that is guaranteed to be within a constant factor of W, e.g. weighted A*. \n* **Bounded cost search ** -  solution whose cost is less than a constant C.\n* **Unbounded cost search ** -  accept a solution at any cost as long as we can find it quickly. \n* **Manhattan distance ** -  sum of horizontal and vertical distances, used when can’t make diagonal moves. \n* **Effective branching factor b* ** -  If the total number of nodes generated by A* for a particular problem is N and the solution depth is d, then b* is the branching factor a tree with uniform depth d will have to have in order to contain N+1 Nodes. \n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "Simplest game env: \\n\n",
        "1. Multiagent \\n\n",
        "2. Static - no change while an agent is deliberating \\n\n",
        "3. Discrete - a finite set of percepts and actions \\n\n",
        "4. Fully observable - an agent’s sensors give it the complete state of the env \\n\n",
        "5. Strategic - the next state is determined by the current state and the action executed by both agents. \\n \n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" Minimax Algorithm \\n\n",
        "The minimax algorithm performs a complete depth-first exploration of the game tree. The time complexity of the min-max algorithm O(b^m) where b is the number of legal moves and m is the max depth.  Space complexity is O(bm).\n",
        "The exponential run time does not make this feasible for more complex games. \n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" Alpha-beta pruning is a way for us to reduce the search space by assessing a node n at a depth. If there is a better node to move to at the same level, we will never use n and its corresponding descendents so we eliminate them by pruning that entire subtree.  \\n\n",
        "Alpha-beta search updates the value alpha and beta as it goes along and prunes the remaining branches at a node as soon as the value of the current node and descendants is known to be worse than the alpha or beta values.  \\n\n",
        "\\n\n",
        "Alpha-beta with perfect move ordering where it visits the best successors first can solve a tree that is twice as deep at the same time as minmax. \\n\n",
        "\\n\n",
        "If f(n) > 0, max wins and otherwise min. If f(n) == 0 then its a tie. \\n\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" For chance/ stochastic games, the complexity is o(b^m*n^m) where b is the branching factor, m is the max depth and n is the number of distinct dice rolls. \n",
        "\\n\n",
        "In case of uncertainty in the current state, the agent will assign a probability to each possible current state s. \n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" MCTS performs exploration and exploitation in the following steps:  \\n\n",
        "1. Selection: select a node based on selection policy (could be exploration/ exploitation trade-off) \\n\n",
        "2. Expansion: generate a new child for the selected node \\n\n",
        "3. Simulation: Perform playout for the newly generated node, choosing moves for both players. These moves are not persisted.  \\n\n",
        "4. Back-propagation: Use the result of the simulation to update all the search tree nodes going up to the root. \\n\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Evaluation Function: an estimate of the expected utility of the game from a given position. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {'Monte Carlo tree search': ' does not use a heuristic evaluation function. The value of a state is estimated by the average utility over a number of simulations of complete games starting from the state.  ', 'Stochastic games': ' includes a random element like throwing a dice These types of games have chance nodes with branching leading from chance nodes that represent the probability.', 'Expected value': ' the average overall possible outcomes of the chance nodes.    ', 'Utility Function': ' a function that captures the agent’s preferences by assigning a single number to express the desirability of a state. ', 'Expected Utility Function': ' Average utility value of the outcomes, weighted by the probability that the outcome occurs. ', 'Expected Utility of a Lottery': ' sum of the probability of each outcome times the utility of that outcome. ', 'Ordinal utility function/ value function': ' in a deterministic environment the agent only needs preference ranks on states, the actual values don’t matter. ', 'Risk averse agents': ' agents who prefer a sure thing with a payoff that is less than the expected monetary value of a gamble. ', 'Unbiased': ' expected value of the error is 0. ', 'Optimizer’s curse': ' if we pick the top k options, the tendency for the expected utility for these choices being too high is known as the optimizer’s curse. ', 'Normative theory': ' decision theory is a normative theory because it explains how rational agents should act. ', 'Descriptive theory': ' describes how rational agents actually act. ', 'Framing effect': ' exact wording of a decision problem impacting an agent’s choice', 'Anchoring effect': ' people  are more comfortable making relative utility judgement over absolute ones. ', 'Zero sum': ' one player’s loss is another player’s gain'}\n",
        "\n"
      ],
      "execution_count": 54,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "17b36e85-6466-4022-cc70-a940d65601f1"
      },
      "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": 55,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Monte Carlo tree search' is too long!\nWARNING: Your definition of 'Stochastic games' is too long!\nWARNING: Your definition of 'Utility Function' is too long!\nWARNING: Your definition of 'Risk averse agents' is too long!\nWARNING: Your definition of 'Optimizer’s curse' is too long!\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nSimplest game env: \n\n1. Multiagent \n\n2. Static - no change while an agent is deliberating \n\n3. Discrete - a finite set of percepts and actions \n\n4. Fully observable - an agent’s sensors give it the complete state of the env \n\n5. Strategic - the next state is determined by the current state and the action executed by both agents. \n \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax Algorithm \n\nThe minimax algorithm performs a complete depth-first exploration of the game tree. The time complexity of the min-max algorithm O(b^m) where b is the number of legal moves and m is the max depth.  Space complexity is O(bm).\nThe exponential run time does not make this feasible for more complex games. \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Alpha-beta pruning is a way for us to reduce the search space by assessing a node n at a depth. If there is a better node to move to at the same level, we will never use n and its corresponding descendents so we eliminate them by pruning that entire subtree.  \n\nAlpha-beta search updates the value alpha and beta as it goes along and prunes the remaining branches at a node as soon as the value of the current node and descendants is known to be worse than the alpha or beta values.  \n\n\n\nAlpha-beta with perfect move ordering where it visits the best successors first can solve a tree that is twice as deep at the same time as minmax. \n\n\n\nIf f(n) > 0, max wins and otherwise min. If f(n) == 0 then its a tie. \n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n For chance/ stochastic games, the complexity is o(b^m*n^m) where b is the branching factor, m is the max depth and n is the number of distinct dice rolls. \n\n\nIn case of uncertainty in the current state, the agent will assign a probability to each possible current state s. \n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n MCTS performs exploration and exploitation in the following steps:  \n\n1. Selection: select a node based on selection policy (could be exploration/ exploitation trade-off) \n\n2. Expansion: generate a new child for the selected node \n\n3. Simulation: Perform playout for the newly generated node, choosing moves for both players. These moves are not persisted.  \n\n4. Back-propagation: Use the result of the simulation to update all the search tree nodes going up to the root. \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Evaluation Function: an estimate of the expected utility of the game from a given position. \n\n## Module 5 Definitions\n* **Monte carlo tree search** -  does not use a heuristic evaluation function. The value of a state is estimated by the average utility over a number of simulations of complete games starting from the state.  \n* **Stochastic games** -  includes a random element like throwing a dice These types of games have chance nodes with branching leading from chance nodes that represent the probability.\n* **Expected value** -  the average overall possible outcomes of the chance nodes.    \n* **Utility function** -  a function that captures the agent’s preferences by assigning a single number to express the desirability of a state. \n* **Expected utility function** -  Average utility value of the outcomes, weighted by the probability that the outcome occurs. \n* **Expected utility of a lottery** -  sum of the probability of each outcome times the utility of that outcome. \n* **Ordinal utility function/ value function** -  in a deterministic environment the agent only needs preference ranks on states, the actual values don’t matter. \n* **Risk averse agents** -  agents who prefer a sure thing with a payoff that is less than the expected monetary value of a gamble. \n* **Unbiased** -  expected value of the error is 0. \n* **Optimizer’s curse** -  if we pick the top k options, the tendency for the expected utility for these choices being too high is known as the optimizer’s curse. \n* **Normative theory** -  decision theory is a normative theory because it explains how rational agents should act. \n* **Descriptive theory** -  describes how rational agents actually act. \n* **Framing effect** -  exact wording of a decision problem impacting an agent’s choice\n* **Anchoring effect** -  people  are more comfortable making relative utility judgement over absolute ones. \n* **Zero sum** -  one player’s loss is another player’s gain\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 = \"\"\"Three components for CSP: \\n\n",
        "1. Set of variables\\n\n",
        "2. Allowable domains the variables can take on \\n\n",
        "3. Constraints that specify allowable combinations of values \\n\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" A discrete domain can be infinite but for a finite domain of size d and variable of size n, complexity is O(d^n). \\n\n",
        "Branching factor at root is n*d.  \\n\n",
        "No algorithm for solving generic nonlinear constraints on integer variables, that is undecidable. \\n\n",
        "Arc consistency tightens down the domains (unary constraints) using the arcs (binary\\n\n",
        "constraints). Path consistency tightens the binary constraints by using implicit constraints\\n\n",
        "that are inferred by looking at triples of variables.\\n\n",
        "\\n\n",
        "CSP is commutative where the order of application of any given set of actions does not matter. \\n\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" Types of heuristics to pick: \\n\n",
        "1. Most constrained variable - has least amount of legal values it can take on and poses a bigger constraint on the other variables. Also known as fail first because it picks a variable that is most likely to cause a failure soon. Uses degree heuristic to break ties as it might be in a situation where each variable has an equal number of legal values it can take on at start. \\n\n",
        "2. Least constraining variable - pick a value that rules out the least amount of choices for the remaining neighboring variables. \\n\n",
        "3. Forward checking - check remaining variables and terminate if they don’t have legal values. Propagates information from assigned to unassigned variables but has no way of doing early detection of failures. \\n \"\"\"\n",
        "chapter6_4 = \"\"\"Arc consistency - alternates between search and consistency. \\n\n",
        "AC-3 algorithm worst complexity - O(n^2d^3)\\n\n",
        "\\n\n",
        "If a value is removed from a node n, all its neighbors need to be re-assessed. \n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" CSP algorithms are a good fit for manufacturing processes which have constraints on the order that parts have to be assembled in, and the length of time that it takes to perform each step.  Minimax is a better algorithm for chess.  A* is a better solution for map navigation and puzzles where the goal is to minimize the number of moves.\n",
        "Constraint satisfaction is widely applicable in domains including real numbered-values and integer values with no upper bounds - however, there is not always a known sub-exponential algorithm to find the correct solution.\n",
        "\\n\n",
        "AC-3: \\n\n",
        "A naive approach (enumerating all boards) can solve any sudoku in O(n^n+1) time.  There is no guarantee that AC#3 can solve sudoku puzzles in O(n^3) time if n is the number of columns, because the number of possible arcs is O(n), the number of cells to check is n^2, and the number of possible values of each cell is n.  However, if there is an answer to a sudoku problem, AC3 will find it, and otherwise it will determine that there is no solution. \n",
        "\\n\n",
        "Inference in CSP: Using problem constraints to reduce the number of legal values on variables.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {'Constraint Satisfaction Problem ': ' a problem is solved when each variable has a value that satisfies all constraints on the variable. ', 'Complete assignment ': ' Every variable is assigned a value', 'Arc consistent ': ' a variable is arc consistent if every value in its domain satisfies the variable’s binary constraints. ', 'Degree heuristic ': ' reduces branching factor on future choices by picking variables involved in the largest number of constraints on other unassigned variables. ', 'Backtracking search ': ' a form of depth'}\n"
      ],
      "execution_count": 56,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c05d4cb8-d1dd-453c-c5ab-ce92eab5ef56"
      },
      "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": 57,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Degree heuristic ' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nThree components for CSP: \n\n1. Set of variables\n\n2. Allowable domains the variables can take on \n\n3. Constraints that specify allowable combinations of values \n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n A discrete domain can be infinite but for a finite domain of size d and variable of size n, complexity is O(d^n). \n\nBranching factor at root is n*d.  \n\nNo algorithm for solving generic nonlinear constraints on integer variables, that is undecidable. \n\nArc consistency tightens down the domains (unary constraints) using the arcs (binary\n\nconstraints). Path consistency tightens the binary constraints by using implicit constraints\n\nthat are inferred by looking at triples of variables.\n\n\n\nCSP is commutative where the order of application of any given set of actions does not matter. \n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Types of heuristics to pick: \n\n1. Most constrained variable - has least amount of legal values it can take on and poses a bigger constraint on the other variables. Also known as fail first because it picks a variable that is most likely to cause a failure soon. Uses degree heuristic to break ties as it might be in a situation where each variable has an equal number of legal values it can take on at start. \n\n2. Least constraining variable - pick a value that rules out the least amount of choices for the remaining neighboring variables. \n\n3. Forward checking - check remaining variables and terminate if they don’t have legal values. Propagates information from assigned to unassigned variables but has no way of doing early detection of failures. \n \n\n## AIMA Chapter 6.4 Local Search for CSPs\nArc consistency - alternates between search and consistency. \n\nAC-3 algorithm worst complexity - O(n^2d^3)\n\n\n\nIf a value is removed from a node n, all its neighbors need to be re-assessed. \n\n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n CSP algorithms are a good fit for manufacturing processes which have constraints on the order that parts have to be assembled in, and the length of time that it takes to perform each step.  Minimax is a better algorithm for chess.  A* is a better solution for map navigation and puzzles where the goal is to minimize the number of moves.\nConstraint satisfaction is widely applicable in domains including real numbered-values and integer values with no upper bounds - however, there is not always a known sub-exponential algorithm to find the correct solution.\n\n\nAC-3: \n\nA naive approach (enumerating all boards) can solve any sudoku in O(n^n+1) time.  There is no guarantee that AC#3 can solve sudoku puzzles in O(n^3) time if n is the number of columns, because the number of possible arcs is O(n), the number of cells to check is n^2, and the number of possible values of each cell is n.  However, if there is an answer to a sudoku problem, AC3 will find it, and otherwise it will determine that there is no solution. \n\n\nInference in CSP: Using problem constraints to reduce the number of legal values on variables.\n\n \n\n## Module 6 Definitions\n* **Constraint satisfaction problem ** -  a problem is solved when each variable has a value that satisfies all constraints on the variable. \n* **Complete assignment ** -  Every variable is assigned a value\n* **Arc consistent ** -  a variable is arc consistent if every value in its domain satisfies the variable’s binary constraints. \n* **Degree heuristic ** -  reduces branching factor on future choices by picking variables involved in the largest number of constraints on other unassigned variables. \n* **Backtracking search ** -  a form of depth\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 = \"\"\" Premise of Kb: if KB is true in the real world, then any sentence derived from KB by a sound inference procedure is also true in the real world.  \"\"\"\n",
        "chapter7_2 = \"\"\" Describe the task environment by PEAS description: \\n \n",
        "1. Performance Measure\n",
        "2. Environment\n",
        "3. Actuators\n",
        "4. Sensors\"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "Modus Ponens:\n",
        "Any sentence in the form a implies b and a are given, we can infer what b is. \n",
        "\\n\n",
        "And-Elimination: \\n\n",
        "from conjunction any of the conjuncts can be inferred. \n",
        "\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" Inference is the process of deriving new sentences from old ones. Sound inference algo-\n",
        "rithms derive only sentences that are entailed; complete algorithms derive all sentences\n",
        "that are entailed.\n",
        "\\n\n",
        "Propositional logic does not scale to environments of unbounded size because it lacks\n",
        "the expressive power to deal concisely with time, space, and universal patterns of rela-\n",
        "tionships among objects.\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\" Defining a KB proof: \\n\n",
        "1. Initial state - the initial knowledge base\n",
        "2. Actions - set of actions consists of all the inference rules applied applied to all the sentences that match the top half of the inference rule\n",
        "3. Result - result of an action to add to the bottom part of an inference rule. \n",
        "4. Goal - the state that contains the sentence we are trying to prove.\n",
        "\\n \n",
        "KB-agent - TIME complexity: O(2^n) and space complexity O(n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {'Knowledge-based agents': ' agents that use a process of reasoning over an internal representation of knowledge to decide what actions to take. Knowledge-based agents can accept new tasks in the form of explicitly described goals; they can achieve competence quickly by being told or learning new knowledge about the environment; and they can adapt to changes in the environment by updating the relevant knowledge.', 'Propositional logic': ' factored representation of logic, allowable sentences in KB', 'Inference': ' deriving new sentences from old', 'Axioms': ' sentence is being given and not derived from other sentences in the KB', 'Declarative system building': ' simply telling a KB agent what it needs to know, one by one, starting with an empty KB. ', 'Procedural system building': ' encodes desired behaviours directly as program code. ', 'Semantics': ' the truth of each sentence in the knowledge base with respect to each possible world. ', 'Logical entailment': ' a sentence follows logically from another sentence. ', 'Sound or truth preserving': ' an inference algorithm that derives only entailed sentences. ', 'Complete': ' an inference algorithm is complete if it can derive any sentence that is entailed. ', 'Grounding': ' the connection between logical reasoning processes and the real environment in which the agent exists. ', 'Atomic sentences': ' consist of a single proposition symbol. ', 'theorem proving': ' applying rules of inference directly to the sentences', 'Satisfiability': ' A sentence is satisfiable if it is true in, or satisfied by, some model.', 'Resolution': ' an inference rule that yields a complete inference algorithm when coupled with any complete algorithm. ', 'Complementary literals': ' one literal is a negation of the other ', 'Unit resolution': ' only takes a clause ', 'Factoring': ' removal of multiple copies of literals ', 'CNF': ' a sentence expressed as a conjunction of clauses is said to be in conjunctive normal forms.  CNF requires negation to only occur in literals. ', 'Definite clause': ' disjunction of literals where only one literal is positive (subset of horn)', 'Horn clause': ' disjunction of literals of which at most one is positive. ', 'Goal clauses': ' disjunction of literals that have no positive literals (subset of horn)', 'Atemporal variables': ' symbols associated with permanent aspects of the world that do not need a time component. '}\n",
        "\n"
      ],
      "execution_count": 58,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e811c1c8-0c16-4d7c-8b1e-0ecc507087a8"
      },
      "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": 59,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Knowledge-based agents' is too long!\nWARNING: Your definition of 'CNF' is too long!\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Premise of Kb: if KB is true in the real world, then any sentence derived from KB by a sound inference procedure is also true in the real world.  \n\n## AIMA Chapter 7.2 The Wumpus World\n Describe the task environment by PEAS description: \n \n1. Performance Measure\n2. Environment\n3. Actuators\n4. Sensors\n\n## AIMA Chapter 7.3 Logic\n \nModus Ponens:\nAny sentence in the form a implies b and a are given, we can infer what b is. \n\n\nAnd-Elimination: \n\nfrom conjunction any of the conjuncts can be inferred. \n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Inference is the process of deriving new sentences from old ones. Sound inference algo-\nrithms derive only sentences that are entailed; complete algorithms derive all sentences\nthat are entailed.\n\n\nPropositional logic does not scale to environments of unbounded size because it lacks\nthe expressive power to deal concisely with time, space, and universal patterns of rela-\ntionships among objects.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n Defining a KB proof: \n\n1. Initial state - the initial knowledge base\n2. Actions - set of actions consists of all the inference rules applied applied to all the sentences that match the top half of the inference rule\n3. Result - result of an action to add to the bottom part of an inference rule. \n4. Goal - the state that contains the sentence we are trying to prove.\n\n \nKB-agent - TIME complexity: O(2^n) and space complexity O(n\n\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** -  agents that use a process of reasoning over an internal representation of knowledge to decide what actions to take. Knowledge-based agents can accept new tasks in the form of explicitly described goals; they can achieve competence quickly by being told or learning new knowledge about the environment; and they can adapt to changes in the environment by updating the relevant knowledge.\n* **Propositional logic** -  factored representation of logic, allowable sentences in KB\n* **Inference** -  deriving new sentences from old\n* **Axioms** -  sentence is being given and not derived from other sentences in the KB\n* **Declarative system building** -  simply telling a KB agent what it needs to know, one by one, starting with an empty KB. \n* **Procedural system building** -  encodes desired behaviours directly as program code. \n* **Semantics** -  the truth of each sentence in the knowledge base with respect to each possible world. \n* **Logical entailment** -  a sentence follows logically from another sentence. \n* **Sound or truth preserving** -  an inference algorithm that derives only entailed sentences. \n* **Complete** -  an inference algorithm is complete if it can derive any sentence that is entailed. \n* **Grounding** -  the connection between logical reasoning processes and the real environment in which the agent exists. \n* **Atomic sentences** -  consist of a single proposition symbol. \n* **Theorem proving** -  applying rules of inference directly to the sentences\n* **Satisfiability** -  A sentence is satisfiable if it is true in, or satisfied by, some model.\n* **Resolution** -  an inference rule that yields a complete inference algorithm when coupled with any complete algorithm. \n* **Complementary literals** -  one literal is a negation of the other \n* **Unit resolution** -  only takes a clause \n* **Factoring** -  removal of multiple copies of literals \n* **Cnf** -  a sentence expressed as a conjunction of clauses is said to be in conjunctive normal forms.  CNF requires negation to only occur in literals. \n* **Definite clause** -  disjunction of literals where only one literal is positive (subset of horn)\n* **Horn clause** -  disjunction of literals of which at most one is positive. \n* **Goal clauses** -  disjunction of literals that have no positive literals (subset of horn)\n* **Atemporal variables** -  symbols associated with permanent aspects of the world that do not need a time component. \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": "181cc4f7-a059-45ec-e316-a85695ff42ac"
      },
      "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 + \"\\n\\n\\n#Good luck!\"))"
      ],
      "execution_count": 60,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Agent function' is too long!\nWARNING: Your definition of 'Rational Agent' is too long!\n# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n \n\n## AIMA 2.1 Agents and Environments\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n  \n\n## AIMA 2.3 The Nature of Environments\n  \n\n## AIMA 2.4 The Structure of Agents\n  \n\n## Module 1 Lecture Notes\nIt is best to design performance measures based on what you want to be achieved by the agent rather than how you think the agent should behave. \n\nOur environment restrictions are static, fully observable, deterministic, and discrete. \nElements needed to formulate a search problem: \n1. States\n2. Actions\n3. Performance measures\n4. Goal (kind of)\n5. Solution (kind 0f)\n\n\n## Module 1 Definitions\n* **Agents** -  anything that perceives its environments through sensors and can act on its environment through actuators. \n* **Agent function** -  specifies an agent; function maps a sequence of percept vectors P to an action a from a set A. \n* **Rational agent** -  for each possible percept sequence, a rational agent selects an action that maximizes the expected value of its performance measure. \n* **Consequentialism** -  evaluating an agent’s behaviour by its consequences. \n* **Percept** -  is the agent’s perceptual inputs at any given instance. \n* **Episodic** -  next episode doesn’t depend on current\n* **Non-deterministic ** -  chance based\n* **Stochastic ** -  probabilistic\n* **Simple reflex agent ** -  agent selects actions on the basis of the current percept, ignoring the rest of the percept history. \n\n\n## WARNING: Your definition of 'Nested list comp ' is too long!\nWARNING: Your definition of 'Yields ' is too long!\n# Module 2: Python\n## Module 2 Lecture Notes\n \nSlices:  \n\na[-1] # last item in the array  \n\na[-2:] # last two items in the array \n\na[:-2] # everything except the last two items \n\na[::-1] # all items in the array, reversed  \n\na[1::-1] # the first two items, reversed  \n\na[:-3:-1] # the last two items, reversed  \n\na[-3::-1] # everything except the last two items, reversed \n\n \n\nList operations:  \n\nli.index(‘a’) <- index of first occurrence  \n\nli.count(‘a’) <- number of occurrences  \n\nli.remove(‘a’) <- remove first occurrence  \n\nli.reverse() <- reverse the list in place  \n\nli.sort() <- sort the list in place \n\n \n\nArgs: \n\n*args in the function variable lets the function accept non keyword arguments.  \n\n**kwargs is a dict of keyword arguments being passed in  \n\n \n\nIterators are more memory efficient than lists.  \n\nReloading code from a file: use importlib.reload(py_file) \n\n\nHash function is defined as any function that can be used to map data of arbitrary size of data to a fixed size data.\n\n \n\n## Module 2 Definitions\n* **Repl ** -  read evaluate print loop\n* **Strong typing ** -  every object has a fixed type and incompatible objects can’t go together\n* **Dynamic typing ** -  variables come into assignment when first assigned. Drawback is that type errors are caught at run time. \n* **Strings ** -  immutable \n* **Magic methods ** -  allow user\n* **Nested list comp ** -  res = [(x, y, z) for x in lst1 if x < 2 for y in lst2 for z in lst3 if x + y + z < 8]\n* **Iterators ** -   are objects with a __next__() method\n* **Yields ** -   every time we call a next method on the generator, the method runs until it encounters the yield statement and then it stops and returns the value that was yielded. Next time it resumes where it left off.\n* **Shallow copy ** -  use y = x [:]\n\n\n## WARNING: Your definition of 'Atomic representations ' is too long!\nWARNING: Your definition of 'Systematic ' is too long!\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Describe the 4 phase problem solving process:  \n\nGoal Formulation: The agent adopts a goal so their behaviour can be limited along with actions they have to consider.  \n\nProblem Formulation: Agent creates a description of the states and actions that are necessary to reach that goal.  \n\nSearch: Before taking any action on the real world the agent creates a simulation of the sequences of actions it could take so it ends in the goal step created during goal formulation. This is also the solution.  \n\nExecution: having derived a solution, the agent can act on it in the real world.  \n\n  \n\nWhat type of environment will result in a solution to any problem as a fixed sequence of actions? \n\nFully observable \n\nDeterministic  \n\nKnown  \n\n \n\nExplain when an agent should use an open loop vs. closed loop system:  \n\nOpen loop - When the agent is working with an environment that results in a solution through a fixed sequence of actions, the agent can essentially close his eyes and carry out the solution.  \n\nClosed loop- If the environment is unknown/ non-deterministic/ or not fully observable, the agent needs his percept and will require a closed-loop system.  \n\nUse a branching strategy that recommends a potential path forward based on what percepts arrive. Essentially, “legolas what does your elf eye see” kind of situation.  \n\n\n\n## AIMA Chapter 3.2 Example Problems\n What are the components of a search problem? \n\n1. State space - all possible states the environment can be in \n\n2. Initial state - the starting configuration of the agent.  \n\n3. Goal state - there can be one or many.  \n\n4. Actions - given a state s, all the actions that the agent can take   \n\n5. Transition model - Given an action and a state, describes what the resulting state is.  \n\n6. Action cost model - cost of the transition model,  the price we pay to go from a state with an action applied to it to the final state.  \n\n \n\nWhat makes something have an optimal solution? \n\nThe lowest path cost.  \n\n \n\nWhat is abstraction and how do we make sure we have a good level of abstraction? \n\nProcess of removing details  \n\nValid: If we can elaborate any abstract solution into a solution in the more detailed world \n\nUseful: if carrying out each action in the solution is easier than carrying it out in the real world.  \n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n Search Algorithms: \n\n \n\nTakes a search problem as an input and returns a solution.  \n\n \n\nWhat is the difference between state space and the search tree? \n\nThe state space describes the possible infinite set of states in the world and all the actions we will need to take to go from one state to the other. The search tree is the path between these states going towards the goal state.  \n\n \n\nWhat does expanding a node in a search tree mean? \n\nEach node in a search tree tells us the state in the state space and the edges represent corresponding actions. When we expand a node, we consider all the possible actions (edges) and the corresponding states (child nodes) deriving from those actions. We continue by assessing the child states and picking the next child node to expand. Any state that has a node generated has been reached, whether or not we further expanded it.  \n\n \n\nWhat does the frontier of a search tree do? \n\nIt allows us to separate the search tree into two regions. One region where we have nodes that we have reached and expanded, and an exterior region that we have not reached. The frontier is the node we reached but have yet to expand.  \n\n \n\nBFS is complete even for an infinite-depth search space. \n\n\n\nGraph vs. tree search: Graph search, we include a set of explored nodes in order to handle repeat states. We also only choose to add nodes to the frontier if they have already not been explored.  \n\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Measuring Problem-Solving Algorithm Performance \n\n1. Completeness - are we guaranteed a solution? \n\n2. Cost Optimality - does it return the lowest cost solution? \n\n3. Time Complexity - run time complexity or real time measurement of finding solution.  \n\n4. Space Complexity - memory needed to perform the search or the number of does simultaneously in memory.  \n\n \n\n## Module 3 Lecture Notes\n BFS - good for finding the shortest path \n \nDFS - Expands the deepest nodes in the frontier first. Advantage is that it has better space complexity than BFS. The space complexity of BFS is O(b^d), while DFS has a lower complexity of O(bm). \n\nImplemented more of a tree search where a dictionary of visited states is not persisted. In the case of backtracking, only one successor is generated instead of all successors\n\n \n\nGBFS, UCS, and A* all uses a priority queue\n\n\n## Module 3 Definitions\n* **        problem solving agents ** -  agent looks ahead and sees a sequence of actions that will eventually achieve its goals. \n* **Solution ** -  path to a goal state\n* **Optimal solution ** -  solution with the lowest path cost. \n* **Atomic representations ** -  states of the world are considered as whole and no internal structures are visible to the problem solving algorithms. \n* **Planning agents ** -  instead of using atomic representations like problem solving agents, use factored or structured representations. \n* **Informed algorithms ** -  agent knows how far away they are from the solution state. \n* **Uninformed algorithms ** -  agent does not have an estimate of how far they are away from the solution state. \n* **Systematic ** -  a search algorithm that explores an infinite state space but can eventually reach any state that is connected to the initial state. \n* **Branching factor ** -  number of successors for a node that needs to be considered. \n* **Search algorithms ** -  algorithms that take a search problem as an input and return a solution. \n\n\n## WARNING: Your definition of 'Effective branching factor b* ' is too long!\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed Heuristic Search Algorithms\n\n\n\nGreedy BFS f(n) = h(n) - BFS search that uses the cost function to expand the best node at each step.\n\nGreedy best-first graph search is complete in finite state spaces, but not in infinite ones.\n\nThe worst-case time and space complexity is O(|V|). With a good heuristic function, however,the complexity can be reduced substantially, on certain problems reaching O(bm).\n\n\n\nA* Search - uses BFS and an evaluation function \n\nf(n) = g(n) + h(n)\n\ng(n): path cost from initial state to node n\n\nh(n): estimated cost of shortest path from n to a goal state\n\nf(n): estimated cost of the best path that goes through n to goal state \n\n \n\n\tA* is complete and if it uses an admissible heuristic, it is cost-optimal. \n\n\n\nIDA*: It is a very important and commonly used algorithm for problems that do not fit in memory\n\n\nIf C* is the cost of the optimal solution path, then we will DEFINITELY expand all the nodes where they cost of getting to that node f(n) is then than the optimal cost of the solution path C*. A* may expand some of the nodes where f(n)== C*, these are nodes right on the goal conture.\n\n\n\nA* with a consistent heuristic is optimally efficient. \n\nIt is also efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.  \n\n\t\n\nUsing inadmissible heuristic with A* - we risk missing the optimal solution but if we are happy with a solution that is close enough, by overestimating the heuristic function we can end up with a solution that expands fewer nodes. A* has the weakness of expanding a lot of nodes and as a result high memory usage.\n\n\n\nRun time depends on the heuristic but for an unbounded problem with depth d, it is O(bd).\nThe space complexity is O(b^d).\n\n\nbranching factor: \n\nSmaller branching factor means more nodes will be pruned and make the algorithm more efficient\n\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \nHeuristics \n\n\n\nIf h1(n) >= h2(n), then h1 dominates h2 \n\n \n\nHeuristic accuracy can impact performance. If a heuristic has an effective branch factor b* close to 1, a relatively large problem can be solved at a reasonable computational cost. We know that every node with h(n) < C* - g(n) will be expanded. With a collection of admissible heuristics, we can pick the best heuristic from a given node by doing h(n) = max(h_1(n)+h_2(n)+..h_k(n)).  \n\nA heuristic is admissible if it never overestimates the true cost to a nearest goal. A heuristic is consistent if, when going from neighboring nodes a to b, the heuristic difference/step cost never overestimates the actual step cost. It is actually challenging to come up with a heuristic that is admissible and not consistent.  \n\n \n\n## Module 4 Lecture Notes\nSince A* is costly to use when it comes to memory, it seems sensible, therefore, to determine how much memory we have available, and\nallow an algorithm to use all of it. Two algorithms that do this are MA ∗ (memory-bounded\nA ∗ ) and SMA ∗ (simplified MA ∗ ). SMA ∗ is—well—simpler, so we will describe it. SMA ∗\nproceeds just like A ∗ , expanding the best leaf until memory is full. At this point, it cannot add\na new node to the search tree without dropping an old one. SMA ∗ always drops the worst leaf\nnode—the one with the highest f -value. Like RBFS, SMA ∗ then backs up the value of the\nforgotten node to its parent. In this way, the ancestor of a forgotten subtree knows the quality\nof the best path in that subtree. \n\n## Module 4 Definitions\n* **        informed search  ** -  using domain specific hints\n* **Heuristic function ** -  estimated cost of the cheapest path from the state at node n to a goal state. \n* **Admissible heuristic ** -  one that never overestimates the cost of reaching a goal, also seen as optimistic. \n* **Monotonic/ consistent heuristic ** -  path cost always increases as you go along a path because action costs are always positive.\n* **Strictly monotonic ** -   has cost always going up where monotonic is where cost doesn’t go down. \n* **Bounded suboptimal search ** -  solution that is guaranteed to be within a constant factor of W, e.g. weighted A*. \n* **Bounded cost search ** -  solution whose cost is less than a constant C.\n* **Unbounded cost search ** -  accept a solution at any cost as long as we can find it quickly. \n* **Manhattan distance ** -  sum of horizontal and vertical distances, used when can’t make diagonal moves. \n* **Effective branching factor b* ** -  If the total number of nodes generated by A* for a particular problem is N and the solution depth is d, then b* is the branching factor a tree with uniform depth d will have to have in order to contain N+1 Nodes. \n\n\n## WARNING: Your definition of 'Monte Carlo tree search' is too long!\nWARNING: Your definition of 'Stochastic games' is too long!\nWARNING: Your definition of 'Utility Function' is too long!\nWARNING: Your definition of 'Risk averse agents' is too long!\nWARNING: Your definition of 'Optimizer’s curse' is too long!\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nSimplest game env: \n\n1. Multiagent \n\n2. Static - no change while an agent is deliberating \n\n3. Discrete - a finite set of percepts and actions \n\n4. Fully observable - an agent’s sensors give it the complete state of the env \n\n5. Strategic - the next state is determined by the current state and the action executed by both agents. \n \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Minimax Algorithm \n\nThe minimax algorithm performs a complete depth-first exploration of the game tree. The time complexity of the min-max algorithm O(b^m) where b is the number of legal moves and m is the max depth.  Space complexity is O(bm).\nThe exponential run time does not make this feasible for more complex games. \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Alpha-beta pruning is a way for us to reduce the search space by assessing a node n at a depth. If there is a better node to move to at the same level, we will never use n and its corresponding descendents so we eliminate them by pruning that entire subtree.  \n\nAlpha-beta search updates the value alpha and beta as it goes along and prunes the remaining branches at a node as soon as the value of the current node and descendants is known to be worse than the alpha or beta values.  \n\n\n\nAlpha-beta with perfect move ordering where it visits the best successors first can solve a tree that is twice as deep at the same time as minmax. \n\n\n\nIf f(n) > 0, max wins and otherwise min. If f(n) == 0 then its a tie. \n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n For chance/ stochastic games, the complexity is o(b^m*n^m) where b is the branching factor, m is the max depth and n is the number of distinct dice rolls. \n\n\nIn case of uncertainty in the current state, the agent will assign a probability to each possible current state s. \n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n MCTS performs exploration and exploitation in the following steps:  \n\n1. Selection: select a node based on selection policy (could be exploration/ exploitation trade-off) \n\n2. Expansion: generate a new child for the selected node \n\n3. Simulation: Perform playout for the newly generated node, choosing moves for both players. These moves are not persisted.  \n\n4. Back-propagation: Use the result of the simulation to update all the search tree nodes going up to the root. \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Evaluation Function: an estimate of the expected utility of the game from a given position. \n\n## Module 5 Definitions\n* **Monte carlo tree search** -  does not use a heuristic evaluation function. The value of a state is estimated by the average utility over a number of simulations of complete games starting from the state.  \n* **Stochastic games** -  includes a random element like throwing a dice These types of games have chance nodes with branching leading from chance nodes that represent the probability.\n* **Expected value** -  the average overall possible outcomes of the chance nodes.    \n* **Utility function** -  a function that captures the agent’s preferences by assigning a single number to express the desirability of a state. \n* **Expected utility function** -  Average utility value of the outcomes, weighted by the probability that the outcome occurs. \n* **Expected utility of a lottery** -  sum of the probability of each outcome times the utility of that outcome. \n* **Ordinal utility function/ value function** -  in a deterministic environment the agent only needs preference ranks on states, the actual values don’t matter. \n* **Risk averse agents** -  agents who prefer a sure thing with a payoff that is less than the expected monetary value of a gamble. \n* **Unbiased** -  expected value of the error is 0. \n* **Optimizer’s curse** -  if we pick the top k options, the tendency for the expected utility for these choices being too high is known as the optimizer’s curse. \n* **Normative theory** -  decision theory is a normative theory because it explains how rational agents should act. \n* **Descriptive theory** -  describes how rational agents actually act. \n* **Framing effect** -  exact wording of a decision problem impacting an agent’s choice\n* **Anchoring effect** -  people  are more comfortable making relative utility judgement over absolute ones. \n* **Zero sum** -  one player’s loss is another player’s gain\n\n\n## WARNING: Your definition of 'Degree heuristic ' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nThree components for CSP: \n\n1. Set of variables\n\n2. Allowable domains the variables can take on \n\n3. Constraints that specify allowable combinations of values \n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n A discrete domain can be infinite but for a finite domain of size d and variable of size n, complexity is O(d^n). \n\nBranching factor at root is n*d.  \n\nNo algorithm for solving generic nonlinear constraints on integer variables, that is undecidable. \n\nArc consistency tightens down the domains (unary constraints) using the arcs (binary\n\nconstraints). Path consistency tightens the binary constraints by using implicit constraints\n\nthat are inferred by looking at triples of variables.\n\n\n\nCSP is commutative where the order of application of any given set of actions does not matter. \n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Types of heuristics to pick: \n\n1. Most constrained variable - has least amount of legal values it can take on and poses a bigger constraint on the other variables. Also known as fail first because it picks a variable that is most likely to cause a failure soon. Uses degree heuristic to break ties as it might be in a situation where each variable has an equal number of legal values it can take on at start. \n\n2. Least constraining variable - pick a value that rules out the least amount of choices for the remaining neighboring variables. \n\n3. Forward checking - check remaining variables and terminate if they don’t have legal values. Propagates information from assigned to unassigned variables but has no way of doing early detection of failures. \n \n\n## AIMA Chapter 6.4 Local Search for CSPs\nArc consistency - alternates between search and consistency. \n\nAC-3 algorithm worst complexity - O(n^2d^3)\n\n\n\nIf a value is removed from a node n, all its neighbors need to be re-assessed. \n\n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n CSP algorithms are a good fit for manufacturing processes which have constraints on the order that parts have to be assembled in, and the length of time that it takes to perform each step.  Minimax is a better algorithm for chess.  A* is a better solution for map navigation and puzzles where the goal is to minimize the number of moves.\nConstraint satisfaction is widely applicable in domains including real numbered-values and integer values with no upper bounds - however, there is not always a known sub-exponential algorithm to find the correct solution.\n\n\nAC-3: \n\nA naive approach (enumerating all boards) can solve any sudoku in O(n^n+1) time.  There is no guarantee that AC#3 can solve sudoku puzzles in O(n^3) time if n is the number of columns, because the number of possible arcs is O(n), the number of cells to check is n^2, and the number of possible values of each cell is n.  However, if there is an answer to a sudoku problem, AC3 will find it, and otherwise it will determine that there is no solution. \n\n\nInference in CSP: Using problem constraints to reduce the number of legal values on variables.\n\n \n\n## Module 6 Definitions\n* **Constraint satisfaction problem ** -  a problem is solved when each variable has a value that satisfies all constraints on the variable. \n* **Complete assignment ** -  Every variable is assigned a value\n* **Arc consistent ** -  a variable is arc consistent if every value in its domain satisfies the variable’s binary constraints. \n* **Degree heuristic ** -  reduces branching factor on future choices by picking variables involved in the largest number of constraints on other unassigned variables. \n* **Backtracking search ** -  a form of depth\n\n\n## WARNING: Your definition of 'Knowledge-based agents' is too long!\nWARNING: Your definition of 'CNF' is too long!\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Premise of Kb: if KB is true in the real world, then any sentence derived from KB by a sound inference procedure is also true in the real world.  \n\n## AIMA Chapter 7.2 The Wumpus World\n Describe the task environment by PEAS description: \n \n1. Performance Measure\n2. Environment\n3. Actuators\n4. Sensors\n\n## AIMA Chapter 7.3 Logic\n \nModus Ponens:\nAny sentence in the form a implies b and a are given, we can infer what b is. \n\n\nAnd-Elimination: \n\nfrom conjunction any of the conjuncts can be inferred. \n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Inference is the process of deriving new sentences from old ones. Sound inference algo-\nrithms derive only sentences that are entailed; complete algorithms derive all sentences\nthat are entailed.\n\n\nPropositional logic does not scale to environments of unbounded size because it lacks\nthe expressive power to deal concisely with time, space, and universal patterns of rela-\ntionships among objects.\n\n\n## AIMA 7.5 Propositional Theorem Proving\n Defining a KB proof: \n\n1. Initial state - the initial knowledge base\n2. Actions - set of actions consists of all the inference rules applied applied to all the sentences that match the top half of the inference rule\n3. Result - result of an action to add to the bottom part of an inference rule. \n4. Goal - the state that contains the sentence we are trying to prove.\n\n \nKB-agent - TIME complexity: O(2^n) and space complexity O(n\n\n\n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** -  agents that use a process of reasoning over an internal representation of knowledge to decide what actions to take. Knowledge-based agents can accept new tasks in the form of explicitly described goals; they can achieve competence quickly by being told or learning new knowledge about the environment; and they can adapt to changes in the environment by updating the relevant knowledge.\n* **Propositional logic** -  factored representation of logic, allowable sentences in KB\n* **Inference** -  deriving new sentences from old\n* **Axioms** -  sentence is being given and not derived from other sentences in the KB\n* **Declarative system building** -  simply telling a KB agent what it needs to know, one by one, starting with an empty KB. \n* **Procedural system building** -  encodes desired behaviours directly as program code. \n* **Semantics** -  the truth of each sentence in the knowledge base with respect to each possible world. \n* **Logical entailment** -  a sentence follows logically from another sentence. \n* **Sound or truth preserving** -  an inference algorithm that derives only entailed sentences. \n* **Complete** -  an inference algorithm is complete if it can derive any sentence that is entailed. \n* **Grounding** -  the connection between logical reasoning processes and the real environment in which the agent exists. \n* **Atomic sentences** -  consist of a single proposition symbol. \n* **Theorem proving** -  applying rules of inference directly to the sentences\n* **Satisfiability** -  A sentence is satisfiable if it is true in, or satisfied by, some model.\n* **Resolution** -  an inference rule that yields a complete inference algorithm when coupled with any complete algorithm. \n* **Complementary literals** -  one literal is a negation of the other \n* **Unit resolution** -  only takes a clause \n* **Factoring** -  removal of multiple copies of literals \n* **Cnf** -  a sentence expressed as a conjunction of clauses is said to be in conjunctive normal forms.  CNF requires negation to only occur in literals. \n* **Definite clause** -  disjunction of literals where only one literal is positive (subset of horn)\n* **Horn clause** -  disjunction of literals of which at most one is positive. \n* **Goal clauses** -  disjunction of literals that have no positive literals (subset of horn)\n* **Atemporal variables** -  symbols associated with permanent aspects of the world that do not need a time component. \n\n\n\n#Good luck!",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}