{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS521_midterm notes An Duong.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0ae1280a-ccfd-41f0-8c19-c59a45227fba"
      },
      "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": 125,
      "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": "c27d7cc3-a90d-491e-9ad5-b97db7cabbb1"
      },
      "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": 126,
      "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 = \"An Duong\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 127,
      "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 = \"\"\"An agent is something that acts. A rational agent acts to get the best outcome \\\n",
        "or the best expected outcome. The rational agent approach to AI is the best approach because \\\n",
        "rationality standards are mathematically defined. Ai is focused on agents that do the right thing.\"\"\" \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 = \"\"\" Turing test good at testing human gullibility. \\\n",
        "Not really a good measure of AI effectiveness. \"\"\"\n",
        "chapter27_2 = \"\"\"  \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent is anything that can perceive its environment through sensors \\\n",
        "and act via actuators. A human agent has organs for sensors and hands, vocals, etc. for actuators. \\\n",
        "An agent's choice of actions depends on the percepts that it has seen but not those it has not yet seen.\"\"\"\n",
        "chapter2_2 = \"\"\" The rationality of an agent can be measured using a performance measure. \\\n",
        "In general, it is better to create performance measures according to what should be achieved \\\n",
        "in the environment as opposed to how you want the agent to behave. A rational agent seeks to \\\n",
        "maximize the performance measure. Rationality maximizes expected performance, not actual performance.\"\"\"\n",
        "chapter2_3 = \"\"\" A task environment is specified by PEAS. \"\"\"\n",
        "chapter2_4 = \"\"\" The four basic agent programs are simple reflex, model-based reflex, goal-based, and utility-based.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"what agent's sensors are perceiving\",\n",
        "\"percept sequence\" : \"history of percepts agent has seen\",\n",
        "\"agent function\": \"maps percept sequence to action\",\n",
        "\"agent program\": \"implementation of agent function\",\n",
        "\"rational agent\": \"does the right thing\",\n",
        "\"performance measure\": \"how desirable an agent's action sequence is\",\n",
        "\"Definition of a rational agent\": \"for a percept sequence, the agent should select the action that the maximizes performance measure\",\n",
        "\"task environment\": \"problems that agent solves\",\n",
        "\"PEAS\": \"performance, environment, actuators, sensors\",\n",
        "\"fully observable\": \"agent's sensors give information about complete state of environment\",\n",
        "\"multiagent\": \"two or more agents in task environment\",\n",
        "\"deterministic\": \"state will definitely occur as a result of action in current state (no probability)\",\n",
        "\"stochastic\": \"non deterministic, but proabilities are numerically defined (25% vs chance of)\",\n",
        "\"episodic\": \"current decision doesn't affect others\",\n",
        "\"sequential\": \"current decision can affect future decisions\",\n",
        "\"static\": \"environment does not change while agent is thinking\",\n",
        "\"dynamic\": \"environment can change while agent is thinking\",\n",
        "\"discrete\": \"finite number of distinct states\",\n",
        "\"continuous\": \"states shift into a range of states\",\n",
        "\"known\": \"know the rules / information about environment, not necessarily the complete state\",\n",
        "\"architecture\": \"physical device that contains agent program, sensors, and actuators\",\n",
        "\"simple reflex agent\": \"choose actions based on current percept\",\n",
        "\"internal state\": \"information about world depending on percept history\",\n",
        "\"transition model\": \"effects of actions on world, and how world changes independent of agent\",\n",
        "\"sensor model\": \"how state of the world is represented by what agent senses\",\n",
        "\"model based agent\": \"agent with transition model and sensor model and stores information via internal state\",\n",
        "\"utility function\": \"performance measure\",\n",
        "\"expected utility\": \"utility agent expects to get based on probabilities and utilities of each outcome\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 128,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "f44ddf30-f8ff-46b2-f051-b147cba5966f"
      },
      "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": 129,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nAn agent is something that acts. A rational agent acts to get the best outcome or the best expected outcome. The rational agent approach to AI is the best approach because rationality standards are mathematically defined. Ai is focused on agents that do the right thing.\n\n## AIMA Chapter 27.1 The Limits of AI\n Turing test good at testing human gullibility. Not really a good measure of AI effectiveness. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n  \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can perceive its environment through sensors and act via actuators. A human agent has organs for sensors and hands, vocals, etc. for actuators. An agent's choice of actions depends on the percepts that it has seen but not those it has not yet seen.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n The rationality of an agent can be measured using a performance measure. In general, it is better to create performance measures according to what should be achieved in the environment as opposed to how you want the agent to behave. A rational agent seeks to maximize the performance measure. Rationality maximizes expected performance, not actual performance.\n\n## AIMA 2.3 The Nature of Environments\n A task environment is specified by PEAS. \n\n## AIMA 2.4 The Structure of Agents\n The four basic agent programs are simple reflex, model-based reflex, goal-based, and utility-based.\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - what agent's sensors are perceiving\n* **Percept sequence** - history of percepts agent has seen\n* **Agent function** - maps percept sequence to action\n* **Agent program** - implementation of agent function\n* **Rational agent** - does the right thing\n* **Performance measure** - how desirable an agent's action sequence is\n* **Definition of a rational agent** - for a percept sequence, the agent should select the action that the maximizes performance measure\n* **Task environment** - problems that agent solves\n* **Peas** - performance, environment, actuators, sensors\n* **Fully observable** - agent's sensors give information about complete state of environment\n* **Multiagent** - two or more agents in task environment\n* **Deterministic** - state will definitely occur as a result of action in current state (no probability)\n* **Stochastic** - non deterministic, but proabilities are numerically defined (25% vs chance of)\n* **Episodic** - current decision doesn't affect others\n* **Sequential** - current decision can affect future decisions\n* **Static** - environment does not change while agent is thinking\n* **Dynamic** - environment can change while agent is thinking\n* **Discrete** - finite number of distinct states\n* **Continuous** - states shift into a range of states\n* **Known** - know the rules / information about environment, not necessarily the complete state\n* **Architecture** - physical device that contains agent program, sensors, and actuators\n* **Simple reflex agent** - choose actions based on current percept\n* **Internal state** - information about world depending on percept history\n* **Transition model** - effects of actions on world, and how world changes independent of agent\n* **Sensor model** - how state of the world is represented by what agent senses\n* **Model based agent** - agent with transition model and sensor model and stores information via internal state\n* **Utility function** - performance measure\n* **Expected utility** - utility agent expects to get based on probabilities and utilities of each outcome\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 = \"\"\" Python is dynamically typed. Variables come into existence when \\\n",
        "first defined and you can redefine them as a different type. Functions have no type signatures.\n",
        "Strings and tuples are immutable. Lists are mutable. The keys of a dictionary \\\n",
        "and elements of a set must be immutable. == checks whether variables point to objects of same value whilst \\\n",
        "is checks whether variables point to same object. Strings, lists, and tuples are sequences. \\\n",
        "Slicing returns copy of subsequence.\n",
        "```\n",
        "t[1:4] #slicing ends exclusive of last index\n",
        "t[1:-1] #can use negative index\n",
        "t[1:-1:2] #select every n th item\n",
        "t[:2] #copy from beginning of sequence\n",
        "t[2:] #copy to end of sequence\n",
        "``` \n",
        "List operations:\n",
        "```\n",
        "li.reverse() #reverse in place\n",
        "li.sort() #sort in place\n",
        "li.append(element) #append element to end of list\n",
        "li.insert(2, element) #insert element to index of list\n",
        "li.count() #number of element occurences\n",
        "```\n",
        "Dictionaries:\n",
        "```\n",
        "d = {'user':'R2D2', 'pswd': 1234}\n",
        "d['user']\n",
        "```\n",
        "Functions:\n",
        "```\n",
        "def foo(input):\n",
        "  line1\n",
        "  line2\n",
        "  return value\n",
        "```\n",
        "Functions cannot be overloaded, ie. they cannot have the same name. \\\n",
        "Functions can accept a variable number of arguments using *args, keyword args with **kwargs\n",
        "Default parameter values are only evaluated when the def statement they belong to is first executed.\n",
        "Classes:\n",
        "```\n",
        "class Student:\n",
        "  univ = \"upenn\"\n",
        "  def __init__(self, name, dept):\n",
        "    self.student_name = name\n",
        "    ...\n",
        "  def print_details(self):\n",
        "    ...\n",
        "\n",
        "class AI_Student(Student):\n",
        "```\n",
        "For Loops and List / Dict Comprehension\n",
        "```\n",
        "list(range(5)) #returns [0,1,2,3,4]\n",
        "for x in range(5):\n",
        "  print(x)\n",
        "\n",
        "squares = [x*x for x in nums]\n",
        "[n * 3 for (x, n) in li] #can use on tuples\n",
        "[elem * 2 for elem in li if elem > 4]\n",
        "\n",
        "d = { k: v for k,v in lst1 } #dict comprehension\n",
        "s = { x for x in lst2 } #set comprehension\n",
        "```\n",
        "Generators:\n",
        "```\n",
        "def f(n):\n",
        "  #returns after yield and sets breakpoint, can be called again\n",
        "  yield n\n",
        "  yield n+1\n",
        "[i for i in f(6)]\n",
        "```\n",
        "Imports\n",
        "```\n",
        "import math\n",
        "math.sqrt(9)\n",
        "\n",
        "from math import sqrt\n",
        "sqrt(9)\n",
        "\n",
        "import numpy as np\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "}"
      ],
      "execution_count": 130,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "a6781216-5692-4fad-9d60-f7c0db280523"
      },
      "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": 131,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Python is dynamically typed. Variables come into existence when first defined and you can redefine them as a different type. Functions have no type signatures.\nStrings and tuples are immutable. Lists are mutable. The keys of a dictionary and elements of a set must be immutable. == checks whether variables point to objects of same value whilst is checks whether variables point to same object. Strings, lists, and tuples are sequences. Slicing returns copy of subsequence.\n```\nt[1:4] #slicing ends exclusive of last index\nt[1:-1] #can use negative index\nt[1:-1:2] #select every n th item\nt[:2] #copy from beginning of sequence\nt[2:] #copy to end of sequence\n``` \nList operations:\n```\nli.reverse() #reverse in place\nli.sort() #sort in place\nli.append(element) #append element to end of list\nli.insert(2, element) #insert element to index of list\nli.count() #number of element occurences\n```\nDictionaries:\n```\nd = {'user':'R2D2', 'pswd': 1234}\nd['user']\n```\nFunctions:\n```\ndef foo(input):\n  line1\n  line2\n  return value\n```\nFunctions cannot be overloaded, ie. they cannot have the same name. Functions can accept a variable number of arguments using *args, keyword args with **kwargs\nDefault parameter values are only evaluated when the def statement they belong to is first executed.\nClasses:\n```\nclass Student:\n  univ = \"upenn\"\n  def __init__(self, name, dept):\n    self.student_name = name\n    ...\n  def print_details(self):\n    ...\n\nclass AI_Student(Student):\n```\nFor Loops and List / Dict Comprehension\n```\nlist(range(5)) #returns [0,1,2,3,4]\nfor x in range(5):\n  print(x)\n\nsquares = [x*x for x in nums]\n[n * 3 for (x, n) in li] #can use on tuples\n[elem * 2 for elem in li if elem > 4]\n\nd = { k: v for k,v in lst1 } #dict comprehension\ns = { x for x in lst2 } #set comprehension\n```\nGenerators:\n```\ndef f(n):\n  #returns after yield and sets breakpoint, can be called again\n  yield n\n  yield n+1\n[i for i in f(6)]\n```\nImports\n```\nimport math\nmath.sqrt(9)\n\nfrom math import sqrt\nsqrt(9)\n\nimport numpy as np\n```\n\n\n## Module 2 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" A search problem is defined by the state space, initial state, goal states, \\\n",
        "actions, transition model, and action cost function. \"\"\"\n",
        "chapter3_2 = \"\"\"\"\"\"\n",
        "chapter3_3 = \"\"\" You can turn the state space into a search tree. Nodes in the tree are states and \\\n",
        "edges are actions.\\n\n",
        "Best-First Search:\n",
        "For each iteration, choose a node from queue with minimum value of f(n), and return if it is goal node \\\n",
        "else expand it. Child nodes are added if they have not yet been seen or if they are reached from a path \\\n",
        "with a lower path cost than before. This graph search algorithm is complete.\\n\n",
        "\n",
        "For implicit graphs, algorithm complexity is measured using d, m, and b. \"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "Breadth First Search: \n",
        "Root is expanded first, then successors, then their successors.\n",
        "Complete and optimal. However, time and space complexity is O(b^d).\\n\n",
        "\n",
        "Uniform-Cost Search (Dijkstra's):\n",
        "Best-First search with path cost as evaluation function. Spreads out in waves of uniform \\\n",
        "path cost, similar to BFS spreading out in waves of uniform depth. Complete and optimal.\n",
        "However, time and space complexity is O(b^{1+[C*/e]}), where C* is cost of optimal \\\n",
        "solution and e is the lower bound on cost of each action. This complexity could be much\\\n",
        "greater than b^d because the search could explore large trees with paths of low costs before \\\n",
        "exploring a path with high cost that has a meaningful action.\\n\n",
        "\n",
        "Depth-First Search:\n",
        "Expands deepest node in frontier first. Does not store redundant paths. \\\n",
        "Is not optimal and not complete. However, uses much less memory compared to BFS. Space \\\n",
        "complexity O(bm). Time complexity is O(b^m)\\n\n",
        "\n",
        "Depth-Limited Search and iterative Deepening Search:\n",
        "DFS with depth limit l. Time complexity is O(b^l) and space complexity is O(bl). Can \\\n",
        "be incomplete if fails to reach solution with depth l.\n",
        "Iterative Deepening Search calls Depth-Limited Search for increasing values of l until a \\\n",
        "solution is found. Optimal for same cost actions and complete for finite state spaces. \\\n",
        "Time complexity is O(b^d) when there is a solution and O(b^m) otherwise. Space complexity is \\\n",
        "O(bd) when there is a solution and O(bm) otherwise (for finite state spaces).\\n\n",
        "\n",
        "Bidirectional Search:\n",
        "Searches forward from start state and backwards from goal state. Keep track of two frontiers and \\\n",
        "two sets of reached states. We have a solution when the two frontiers collide. Uses best-first\\\n",
        "search. Space and time complexity is O(b^{d/2}).\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
        "\"state space\": \"possible states environment can be in\",\n",
        "\"initial state\": \"starting state\",\n",
        "\"goal states\": \"states we want to end at\",\n",
        "\"actions\": \"actions available to agent at a specific state\",\n",
        "\"transition model\": \"what actions do or what states they result in\",\n",
        "\"action cost function\": \"costs of taking actions\", \n",
        "\"node\": \"state\",\n",
        "\"edge\": \"action\",\n",
        "\"expand\": \"expand node to see possible actions to other states\",\n",
        "\"frontier\": \"nodes that have yet to be expanded / explored\",\n",
        "\"graph search\": \"checks for redundant paths. Uses more memory but runs faster\",\n",
        "\"tree-like search\": \"does not check for redundant paths. Uses less memory but runs slower\",\n",
        "\"complete\": \"guaranteed to find a solution if there is one, and otherwise returns failure\",\n",
        "\"optimal\": \"returns solution with lowest path cost\",\n",
        "\"depth\": \"aka d, the number of actions in an optimal solution\",\n",
        "\"m\": \"maximum number of actions in any path / max depth of all paths\",\n",
        "\"branching factor\": \"aka b, the number of children of a node\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 132,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "fdb1cc3c-8e12-4684-8b22-6bed202a8e8c"
      },
      "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": 133,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n A search problem is defined by the state space, initial state, goal states, actions, transition model, and action cost function. \n\n## AIMA Chapter 3.2 Example Problems\n\n\n## AIMA Chapter 3.3 Search Algorithms\n You can turn the state space into a search tree. Nodes in the tree are states and edges are actions.\n\nBest-First Search:\nFor each iteration, choose a node from queue with minimum value of f(n), and return if it is goal node else expand it. Child nodes are added if they have not yet been seen or if they are reached from a path with a lower path cost than before. This graph search algorithm is complete.\n\n\nFor implicit graphs, algorithm complexity is measured using d, m, and b. \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBreadth First Search: \nRoot is expanded first, then successors, then their successors.\nComplete and optimal. However, time and space complexity is O(b^d).\n\n\nUniform-Cost Search (Dijkstra's):\nBest-First search with path cost as evaluation function. Spreads out in waves of uniform path cost, similar to BFS spreading out in waves of uniform depth. Complete and optimal.\nHowever, time and space complexity is O(b^{1+[C*/e]}), where C* is cost of optimal solution and e is the lower bound on cost of each action. This complexity could be muchgreater than b^d because the search could explore large trees with paths of low costs before exploring a path with high cost that has a meaningful action.\n\n\nDepth-First Search:\nExpands deepest node in frontier first. Does not store redundant paths. Is not optimal and not complete. However, uses much less memory compared to BFS. Space complexity O(bm). Time complexity is O(b^m)\n\n\nDepth-Limited Search and iterative Deepening Search:\nDFS with depth limit l. Time complexity is O(b^l) and space complexity is O(bl). Can be incomplete if fails to reach solution with depth l.\nIterative Deepening Search calls Depth-Limited Search for increasing values of l until a solution is found. Optimal for same cost actions and complete for finite state spaces. Time complexity is O(b^d) when there is a solution and O(b^m) otherwise. Space complexity is O(bd) when there is a solution and O(bm) otherwise (for finite state spaces).\n\n\nBidirectional Search:\nSearches forward from start state and backwards from goal state. Keep track of two frontiers and two sets of reached states. We have a solution when the two frontiers collide. Uses best-firstsearch. Space and time complexity is O(b^{d/2}).\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - possible states environment can be in\n* **Initial state** - starting state\n* **Goal states** - states we want to end at\n* **Actions** - actions available to agent at a specific state\n* **Transition model** - what actions do or what states they result in\n* **Action cost function** - costs of taking actions\n* **Node** - state\n* **Edge** - action\n* **Expand** - expand node to see possible actions to other states\n* **Frontier** - nodes that have yet to be expanded / explored\n* **Graph search** - checks for redundant paths. Uses more memory but runs faster\n* **Tree-like search** - does not check for redundant paths. Uses less memory but runs slower\n* **Complete** - guaranteed to find a solution if there is one, and otherwise returns failure\n* **Optimal** - returns solution with lowest path cost\n* **Depth** - aka d, the number of actions in an optimal solution\n* **M** - maximum number of actions in any path / max depth of all paths\n* **Branching factor** - aka b, the number of children of a node\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "Greedy Best-First Search:\n",
        "Best-first search that expands nodes with lowest h(n) value. Not optimal, but is complete on finite spaces. \\\n",
        "Time and space complexity is O(V), with good heuristic, can reach O(bm).\\n\n",
        "\n",
        "A* Search:\n",
        "Best-first search that uses function f(n) = h(n) + g(n), where g(n) is the path cost from \\\n",
        "start node to node n, and h(n) is estimated shortest path from node n to goal. Is complete, and can be \\\n",
        "optimal with an admissible heuristic. Can be optimal a inadmissible heuristic if h(n) is admissible for \\\n",
        "the shortest path or if h(n) overstimates some costs, but never by more than the difference in costs between the\n",
        "best solution and second to best solution. Weighted A* search weighs h(n) by some constant W, resulting in faster\\\n",
        "searches.\"\"\"\n",
        "chapter3_6 = \"\"\" The quality of a heuristic can be characterized by its branching factor b*. \\\n",
        "The smaller b* is (best is 1) the better, as it means the search will generate less nodes. \\\n",
        "When comparing heuristics, h1 and h2, if h1 >= h2 then h1 dominates h2 and is the more efficient \\\n",
        "heuristic because it will expand less nodes. We can generate heuristics by relaxing the restrictions on a problem, creating a supergraph \\\n",
        "of the original state space. The cost of an optimal solution to this relaxed problem is an admisisble \\\n",
        "heuristic to the original problem.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"has access to heuristic function\",\n",
        "\"admissible heuristic\": \"a heuristic that never overestimates cost to reach a goal\",\n",
        "\"consistency\": \"heuristic is consistent if h(n) <= cost(to successor of n) + h(successor of n). Is admissible\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 134,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 514
        },
        "cellView": "form",
        "outputId": "2060e5a0-56bf-4cf8-e42d-0170445c077b"
      },
      "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": 135,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nGreedy Best-First Search:\nBest-first search that expands nodes with lowest h(n) value. Not optimal, but is complete on finite spaces. Time and space complexity is O(V), with good heuristic, can reach O(bm).\n\n\nA* Search:\nBest-first search that uses function f(n) = h(n) + g(n), where g(n) is the path cost from start node to node n, and h(n) is estimated shortest path from node n to goal. Is complete, and can be optimal with an admissible heuristic. Can be optimal a inadmissible heuristic if h(n) is admissible for the shortest path or if h(n) overstimates some costs, but never by more than the difference in costs between the\nbest solution and second to best solution. Weighted A* search weighs h(n) by some constant W, resulting in fastersearches.\n\n## AIMA Chapter 3.6 Heuristic Functions\n The quality of a heuristic can be characterized by its branching factor b*. The smaller b* is (best is 1) the better, as it means the search will generate less nodes. When comparing heuristics, h1 and h2, if h1 >= h2 then h1 dominates h2 and is the more efficient heuristic because it will expand less nodes. We can generate heuristics by relaxing the restrictions on a problem, creating a supergraph of the original state space. The cost of an optimal solution to this relaxed problem is an admisisble heuristic to the original problem.\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Informed search** - has access to heuristic function\n* **Admissible heuristic** - a heuristic that never overestimates cost to reach a goal\n* **Consistency** - heuristic is consistent if h(n) <= cost(to successor of n) + h(successor of n). Is admissible\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 = \"\"\" A game can be defined with the elements: initial state, the player \\\n",
        "whose turn it is in a specific state, the set of legal moves in state s, the transition model, \\\n",
        "terminal state, and the utility function.\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\" MAX wants to find a sequence of moves to win the game, but MIN will prevent that. \\\n",
        "Thus, MAX's strategy will be a collection of responses to MIN's possible moves. We can use minimax search\n",
        "to come up with a winning move strategy. Minimax assumes perfect, zero-sum games. \\\n",
        "Given a game tree, the optimal strategy is the minimax value. MAX prefers to move to states with \\\n",
        "maximum minimax values whilst MIN wants to move to states with minimum values.\\n\n",
        "\n",
        "Minimax Search:\n",
        "Represents the game as a tree. Recursively goes down the leaves of the tree and then backs up \\\n",
        "minimax values as the recursion unwinds. (ex. if current player is MIN, first gets utility from terminal nodes and then \\\n",
        "sends back up the minimum value, setting the parent node's minimax value to that value). Exploration is depth-first \\\n",
        "like DFS. If b is the number of legal moves at each point and m is the maximum depth of the tree, then \\\n",
        "the time complexity is O(b^m) and the space complexity is O(bm) (if all actions are generated at once, and O(m) if actions \\\n",
        "generated one at a time). For games with more than two players, have node values be vectors representing values \\\n",
        "for each player. Backed-up value at node n is the utility vector of the child state with the highest value for the \\\n",
        "player whose turn it is at n.\\n\n",
        "\n",
        "Alpha-Beta Pruning:\n",
        "Can stop exploring successors by storing alpha and beta values at each node. For a node n in \\\n",
        "the tree, if the current player has a choice to move to it, but the player has a better choice at the \\\n",
        "same level or at a higher point in the tree, then the player will not move to n. The seach prunes \\\n",
        "branches as soon as current node is worse than the current alpha or beta value for MAX and MIN, respectively. \\\n",
        "Pruning effectiveness depends on the ordering of states. Perfect move ordering could result in \\\n",
        "O(b^{m/2}) examined nodes instead of O(b^m). We can try moves that were found to be the best in the \\\n",
        "past through iterative deepening by exploring one ply, recording the best moves, then exploring one ply more, \\\n",
        "ordering those moves by the previous ply's rankings. The best moves are called killer moves and trying them \\\n",
        "first is called the killer move heuristic. We can have redundant moves such that two sequences of moves result in the same \\\n",
        "game state. We can use a transposition table to cache the heuristic values of states to prevent this.\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" We can cut off our search early and apply a heuristic function to the states, which estimates \\\n",
        "their expected utility. We determine if a state is terminal using a terminal test, which returns true for terminal states \\\n",
        "and for states designated to be our cutoff. The heuristic function, EVAL(s), is an estimate of expected utility and must \\\n",
        "have a value between a loss and a win. You can precompute possible move sequences and add them to a table to be looked up later.\"\"\"\n",
        "chapter5_5 = \"\"\" For games of chance, our tree will have chance nodes with branches leading out from them \\\n",
        "denoting possible probability outcomes. States do not have minimax values but instead expected value. \\\n",
        "The presence of chance nodes causes our evaluation function to not just place higher values to better positions, \\\n",
        "as a change of evaluation values can change outcomes. The evaluation function must return values that are a positive \\\n",
        "linear transformation of probability of winning. For dice, if we knew all future dice rolls \\\n",
        "then expectiminimax and minimax will take the same time, O(b^m). Otherwise, Expectiminimax takes O(b^m * n^m), where n is the number \\\n",
        "of distinct rolls. Can do alpha-beta pruning if we place bounds on chance nodes by placing bounds on utility function.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" We can have preference relations between states. Preference relations must obey: orderability, \\\n",
        "transitivity, continuity, substitutability, monotonicity, and decomposability. \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect information\" : \"fully observable\",\n",
        "\"zero-sum\": \"the benefit a player gains from a move is just as harmful to the other player\",\n",
        "\"move\": \"an action a player takes\",\n",
        "\"terminal state\": \"state where game has ended\",\n",
        "\"utility function\": \"score for player p when game is terminal\",\n",
        "\"ply\": \"one move by one player, ie. one layer of the tree\",\n",
        "\"minimax value\": \"the utility for max of being in a specific state\",\n",
        "\"alpha\": \"the highest value choice so far at any choice point along path for MAX, aka at least\",\n",
        "\"beta\": \"the lowest value choice so far at any choice point along path for MIN, aka at most\",\n",
        "\"Type A Strategy\": \"wide but shallow, moves to a specific depth of tree then uses a heuristic to estimate utility for those states\",\n",
        "\"Type B Strategy\": \"deep but narrow, ignores bad moves and follows most promising paths\",\n",
        "\"forward pruning\": \"prunes moves that seem to be bad, at risk of them turning good. Type B\",\n",
        "\"beam search\": \"consider a beam of n best moves on each ply rather than all possible moves. Best move can be pruned.\",\n",
        "\"stochastic games\": \"games with a random element, like dice\",\n",
        "\"expected value\": \"sum of value over all outcomes, weighted by chance of each action\",\n",
        "\"expectiminimax value\": \"utility value for terminal states, expected value for nonterminal states\",\n",
        "\"maximum expected utility\": \"agent should choose maximal expected utility, MEU\",\n",
        "\"lottery\": \"set of possible outcomes, each with probabilities\",\n",
        "\"orderability\": \"agent must prefer a lottery over another, or equally\",\n",
        "\"transitivity\": \"if agent prefers A to B, and B to C, then it prefers A to C\",\n",
        "\"continuity\": \"if B is between A and C, then probability that agent indifferent to B vs lottery of A and C\",\n",
        "\"substitutability\": \"If agent indifferent to A and B, then B can substitute A in a lottery\",\n",
        "\"monotonicity\": \"if agent prefers A to B, then it will choose a lottery with a higher chance for A\",\n",
        "\"decomposabliity\": \"compound lotteries can be simplified\",\n",
        "\"expected utility of lottery\": \"utility of lottery is sum of probability of each outcome times utility of that outcome\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 136,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "fc7c7420-7b18-4976-9a93-933855c65e60"
      },
      "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": 137,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n A game can be defined with the elements: initial state, the player whose turn it is in a specific state, the set of legal moves in state s, the transition model, terminal state, and the utility function.\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n MAX wants to find a sequence of moves to win the game, but MIN will prevent that. Thus, MAX's strategy will be a collection of responses to MIN's possible moves. We can use minimax search\nto come up with a winning move strategy. Minimax assumes perfect, zero-sum games. Given a game tree, the optimal strategy is the minimax value. MAX prefers to move to states with maximum minimax values whilst MIN wants to move to states with minimum values.\n\n\nMinimax Search:\nRepresents the game as a tree. Recursively goes down the leaves of the tree and then backs up minimax values as the recursion unwinds. (ex. if current player is MIN, first gets utility from terminal nodes and then sends back up the minimum value, setting the parent node's minimax value to that value). Exploration is depth-first like DFS. If b is the number of legal moves at each point and m is the maximum depth of the tree, then the time complexity is O(b^m) and the space complexity is O(bm) (if all actions are generated at once, and O(m) if actions generated one at a time). For games with more than two players, have node values be vectors representing values for each player. Backed-up value at node n is the utility vector of the child state with the highest value for the player whose turn it is at n.\n\n\nAlpha-Beta Pruning:\nCan stop exploring successors by storing alpha and beta values at each node. For a node n in the tree, if the current player has a choice to move to it, but the player has a better choice at the same level or at a higher point in the tree, then the player will not move to n. The seach prunes branches as soon as current node is worse than the current alpha or beta value for MAX and MIN, respectively. Pruning effectiveness depends on the ordering of states. Perfect move ordering could result in O(b^{m/2}) examined nodes instead of O(b^m). We can try moves that were found to be the best in the past through iterative deepening by exploring one ply, recording the best moves, then exploring one ply more, ordering those moves by the previous ply's rankings. The best moves are called killer moves and trying them first is called the killer move heuristic. We can have redundant moves such that two sequences of moves result in the same game state. We can use a transposition table to cache the heuristic values of states to prevent this.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n We can cut off our search early and apply a heuristic function to the states, which estimates their expected utility. We determine if a state is terminal using a terminal test, which returns true for terminal states and for states designated to be our cutoff. The heuristic function, EVAL(s), is an estimate of expected utility and must have a value between a loss and a win. You can precompute possible move sequences and add them to a table to be looked up later.\n\n## AIMA Chapter 5.5 Stochastic Games\n For games of chance, our tree will have chance nodes with branches leading out from them denoting possible probability outcomes. States do not have minimax values but instead expected value. The presence of chance nodes causes our evaluation function to not just place higher values to better positions, as a change of evaluation values can change outcomes. The evaluation function must return values that are a positive linear transformation of probability of winning. For dice, if we knew all future dice rolls then expectiminimax and minimax will take the same time, O(b^m). Otherwise, Expectiminimax takes O(b^m * n^m), where n is the number of distinct rolls. Can do alpha-beta pruning if we place bounds on chance nodes by placing bounds on utility function.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n We can have preference relations between states. Preference relations must obey: orderability, transitivity, continuity, substitutability, monotonicity, and decomposability. \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Zero-sum** - the benefit a player gains from a move is just as harmful to the other player\n* **Move** - an action a player takes\n* **Terminal state** - state where game has ended\n* **Utility function** - score for player p when game is terminal\n* **Ply** - one move by one player, ie. one layer of the tree\n* **Minimax value** - the utility for max of being in a specific state\n* **Alpha** - the highest value choice so far at any choice point along path for MAX, aka at least\n* **Beta** - the lowest value choice so far at any choice point along path for MIN, aka at most\n* **Type a strategy** - wide but shallow, moves to a specific depth of tree then uses a heuristic to estimate utility for those states\n* **Type b strategy** - deep but narrow, ignores bad moves and follows most promising paths\n* **Forward pruning** - prunes moves that seem to be bad, at risk of them turning good. Type B\n* **Beam search** - consider a beam of n best moves on each ply rather than all possible moves. Best move can be pruned.\n* **Stochastic games** - games with a random element, like dice\n* **Expected value** - sum of value over all outcomes, weighted by chance of each action\n* **Expectiminimax value** - utility value for terminal states, expected value for nonterminal states\n* **Maximum expected utility** - agent should choose maximal expected utility, MEU\n* **Lottery** - set of possible outcomes, each with probabilities\n* **Orderability** - agent must prefer a lottery over another, or equally\n* **Transitivity** - if agent prefers A to B, and B to C, then it prefers A to C\n* **Continuity** - if B is between A and C, then probability that agent indifferent to B vs lottery of A and C\n* **Substitutability** - If agent indifferent to A and B, then B can substitute A in a lottery\n* **Monotonicity** - if agent prefers A to B, then it will choose a lottery with a higher chance for A\n* **Decomposabliity** - compound lotteries can be simplified\n* **Expected utility of lottery** - utility of lottery is sum of probability of each outcome times utility of that outcome\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 = \"\"\" Compared to search problems, CSPs' states are represented as a set \\\n",
        "of variables as opposed to a black box. A problem is solved when each variable in a state has a value that \\\n",
        "satisfies all constraints on that variable. CSPs consist of components C, D, and X. X is the set of variables \\\n",
        "{X1, ..., Xn}, D is the set of domains, {D1, ..., Dn}, one for each variable, and C is the set of constraints \\\n",
        "that specify desired values. A domain Dk consists of possible values for the variable Xk. CSPs assign values \\\n",
        "to variables. An assignment that does not violate the constraints is called consistent. A complete assignment \\\n",
        "is where all variables are assigned a value. The solution to a CSP is a complete, consistent assignment.\"\"\"\n",
        "chapter6_2 = \"\"\"CSPs can generate successors by choosing a variable assignment or through inference. \\\n",
        "A specific type of inference is constraint propagation, using cconstraints to reduce possible values \\\n",
        "for variables, which can reduce possible values for another variable, recursively. Constraint propagation \\\n",
        "can be intertwined with search, or as a preprocess. We can enforce consistency through local consistency. \\\n",
        "Types of local consistency are: node consistency, where a node's values all satisfy the unary constraint, \\\n",
        "arc consistency, where for variables Xi and Xj, for every value in Di, there is a value in Dj that \\\n",
        "satisfies the binary constraint.\\n\n",
        "AC-3:\n",
        "An algorithm to enforce arc-consistency. Maintain a queue of all arcs. While the queue is not empty: pop an arc out \\\n",
        "and enforce arc consistency, removing inconsistent values from domain of Xi. \\\n",
        "If domain of Xi has changed then add all arcs that contain Xi with the exception \\\n",
        "of the arc with Xj, into the queue. Terminate when queue is empty. For n variables with domain sizes \\\n",
        "at most d and c binary constraints, runtime is O(cd^3).\\n\n",
        "\n",
        "Path consistency tightens binary constraints by using implicit constraints by looking at triples of variables. \\\n",
        "A two variable set Xi,Xj is path consistent with a third variable Xm if for every assignment consistent with \\\n",
        "constraints on Xi, Xj, there is an assignment to Xm that satisfies constraints on Xi,Xm and Xm,Xj (Xm in between the two). \\\n",
        "Stronger consistencies are k consistency. A CSP is k consistent if for any set of k-1 variables and for a consistent \\\n",
        "assignemnt to those variables, we can assign a consistent value to any kth variable. A CSP is strongly \\\n",
        "consistent if it is k consistent, k-1 consistent, ..., 1-consistent. If we have a CSP that is strongly consistent \\\n",
        "we can go through all variables and search only from their domains. The runtime is O(n^2 * d)\"\"\"\n",
        "chapter6_3 = \"\"\" We can search CSPs using backtracking search.\\n\n",
        "Backtracking search:\n",
        "Repeatedly choose an unassigned variable and assign it every value in the domain, and extending \\\n",
        "each choice by a recursive call. If the call succeeds then we have a solution, else we restore \\\n",
        "the assignment to the previous state and try the next value.\\n\n",
        "Choosing Unassigned Variable Strategies:\n",
        "Minimum-remaining-values heuristic (MRV), where we pick the variable with the lowest legal values.\n",
        "Degree heuristic, where we pick the variable that has the most constraints with other unassigned variables.\\n\n",
        "\n",
        "Ordering Domain Value Strategies: \n",
        "Least-Constraining-Value heuristic, where we prefer values that rule out fewest values for neighboring variables\n",
        "\n",
        "In general, variable selection is fail first whilst domain ordering is fail last.\\n\n",
        "\n",
        "Forward Checking:\n",
        "Whenever X is assigned, forward checking establishes arc consistency for it. For each unassigned variable Y \\\n",
        "constrained with X, delete values from Y's domain inconsistent with that assigned for X.\n",
        "Maintaining Arc Consistency (MAC):\n",
        "After Xi is assigned a value, we call AC-3 with only the arcs Xj, Xi in the queue, where Xj are unassigned neighbors of \\\n",
        "Xi.\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" Local search on CSPs is where we start with a value assigned to each variable \\\n",
        "and go through the conflicting variables, selecting values that bring us closer to the solution. We can pick \\\n",
        "the value that results in the minimum number of conflicts, which is the min-conflicts heuristic. We can restrict \\\n",
        "the search by keeping a list of visited states and not allowing the algorithm to revisit the states, called tabu search. We can also \\\n",
        "perform constraint weighting, where we give values to constraints, starting at 1, and increasing constraints' \\\n",
        "weights when current assignment violates them. \"\"\"\n",
        "chapter6_5 = \"\"\" Reducing CSPs into subproblems can drastically decrease runtime. Can convert CSP \\\n",
        "into a graph structure, like a tree. A CSP is a tree when any two variables are connected by only one path. \\\n",
        "A tree structured CSP can be solved in time linear to the number of variables. We have consistency called DAC, or \\\n",
        "directional arc consistency. A CSP is DAC for an ordering of variables X1, X2, ... Xn if and only if \\\n",
        "every Xi is arc consistent with each Xj for j > i. We can perform topological sort on a tree CSP, resulting in DAC. \\\n",
        "This is done in O(nd^2) time. Children are guaranteed to be consistent with parent sinc graph is DAC. \\n\n",
        "Cutset Conditioning:\n",
        "Convert CSP into a tree by fixing values for certain variables and applying consistency for neighbors, then removing fixed \\\n",
        "variables from graph. Fixed values could be wrong, so try again. First, choose a subset S of variables s.t. \\\n",
        "CSP/S becomes tree. S is a cycle cutset. For each possible assignment to variables in S that satisfies constraints, \\\n",
        "remove inconsistent values from domains in CSP - S and if CSP - S has a solution, return that assignment along with assignment \\\n",
        "of S. If cutset is size c, the runtime is O(d^c * (n-c)d^2). \\n\n",
        "Tree Decomposition:\n",
        "The tree decomposition of a CSP is the transformation of the original graph into a tree where each node in the tree \\\n",
        "consists of a set of variables. Basically, nodes are subgraphs of CSP. Tree decomposition must have these requirements:\\n\n",
        "1) Every variable in problem appears in at least one of the nodes. \\n\n",
        "2) If two variables are connected by a constraint in original problem, they must appear together (with the constraint) \\\n",
        "in at least one of the nodes. \\n\n",
        "3) If a variable appears in two nodes in the tree, it must appear in every node on the path connecting the two nodes. \\n\n",
        "Tree decomposed CSP can be solved in O(nd^2) time. The tree width is one less than size of largest node and the tree width \\\n",
        "of the graph is defined as the minimum of all tree widths of its decompositions. If graph has tree width \\\n",
        "w then it can be solved in (nd^{w+1}) time. \\n\n",
        "Tree decomposition is in general faster than cutset conditioning. However, cutset can be performed in linear memory \\\n",
        "whilst tree decomposition needs memory exponential to w.\\n\n",
        "Value Symmetry: For every consistent solution there are d! solutions formed by permuting the values, called value symmetry. \\\n",
        "We can reduce the search space by imposing a symmetry-breaking constraint, like an arbitrary ordering constraint.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"local consistency\" : \"enforcing consistency in local nodes can cause inconsistent values to be eliminated\",\n",
        "\"node consistency\": \"all nodes in graph are consistent with their unary constraints\",\n",
        "\"global constraint\": \"constraint involving an arbitrary number of variables\",\n",
        "\"commutativity\": \"order doesn't matter when assigning values to variables.\",\n",
        "}\n"
      ],
      "execution_count": 138,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "49b0e84c-54b5-497e-b6d0-78897330671e"
      },
      "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": 139,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Compared to search problems, CSPs' states are represented as a set of variables as opposed to a black box. A problem is solved when each variable in a state has a value that satisfies all constraints on that variable. CSPs consist of components C, D, and X. X is the set of variables {X1, ..., Xn}, D is the set of domains, {D1, ..., Dn}, one for each variable, and C is the set of constraints that specify desired values. A domain Dk consists of possible values for the variable Xk. CSPs assign values to variables. An assignment that does not violate the constraints is called consistent. A complete assignment is where all variables are assigned a value. The solution to a CSP is a complete, consistent assignment.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nCSPs can generate successors by choosing a variable assignment or through inference. A specific type of inference is constraint propagation, using cconstraints to reduce possible values for variables, which can reduce possible values for another variable, recursively. Constraint propagation can be intertwined with search, or as a preprocess. We can enforce consistency through local consistency. Types of local consistency are: node consistency, where a node's values all satisfy the unary constraint, arc consistency, where for variables Xi and Xj, for every value in Di, there is a value in Dj that satisfies the binary constraint.\n\nAC-3:\nAn algorithm to enforce arc-consistency. Maintain a queue of all arcs. While the queue is not empty: pop an arc out and enforce arc consistency, removing inconsistent values from domain of Xi. If domain of Xi has changed then add all arcs that contain Xi with the exception of the arc with Xj, into the queue. Terminate when queue is empty. For n variables with domain sizes at most d and c binary constraints, runtime is O(cd^3).\n\n\nPath consistency tightens binary constraints by using implicit constraints by looking at triples of variables. A two variable set Xi,Xj is path consistent with a third variable Xm if for every assignment consistent with constraints on Xi, Xj, there is an assignment to Xm that satisfies constraints on Xi,Xm and Xm,Xj (Xm in between the two). Stronger consistencies are k consistency. A CSP is k consistent if for any set of k-1 variables and for a consistent assignemnt to those variables, we can assign a consistent value to any kth variable. A CSP is strongly consistent if it is k consistent, k-1 consistent, ..., 1-consistent. If we have a CSP that is strongly consistent we can go through all variables and search only from their domains. The runtime is O(n^2 * d)\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n We can search CSPs using backtracking search.\n\nBacktracking search:\nRepeatedly choose an unassigned variable and assign it every value in the domain, and extending each choice by a recursive call. If the call succeeds then we have a solution, else we restore the assignment to the previous state and try the next value.\n\nChoosing Unassigned Variable Strategies:\nMinimum-remaining-values heuristic (MRV), where we pick the variable with the lowest legal values.\nDegree heuristic, where we pick the variable that has the most constraints with other unassigned variables.\n\n\nOrdering Domain Value Strategies: \nLeast-Constraining-Value heuristic, where we prefer values that rule out fewest values for neighboring variables\n\nIn general, variable selection is fail first whilst domain ordering is fail last.\n\n\nForward Checking:\nWhenever X is assigned, forward checking establishes arc consistency for it. For each unassigned variable Y constrained with X, delete values from Y's domain inconsistent with that assigned for X.\nMaintaining Arc Consistency (MAC):\nAfter Xi is assigned a value, we call AC-3 with only the arcs Xj, Xi in the queue, where Xj are unassigned neighbors of Xi.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search on CSPs is where we start with a value assigned to each variable and go through the conflicting variables, selecting values that bring us closer to the solution. We can pick the value that results in the minimum number of conflicts, which is the min-conflicts heuristic. We can restrict the search by keeping a list of visited states and not allowing the algorithm to revisit the states, called tabu search. We can also perform constraint weighting, where we give values to constraints, starting at 1, and increasing constraints' weights when current assignment violates them. \n\n## AIMA Chapter 6.5 The Structure of Problems\n Reducing CSPs into subproblems can drastically decrease runtime. Can convert CSP into a graph structure, like a tree. A CSP is a tree when any two variables are connected by only one path. A tree structured CSP can be solved in time linear to the number of variables. We have consistency called DAC, or directional arc consistency. A CSP is DAC for an ordering of variables X1, X2, ... Xn if and only if every Xi is arc consistent with each Xj for j > i. We can perform topological sort on a tree CSP, resulting in DAC. This is done in O(nd^2) time. Children are guaranteed to be consistent with parent sinc graph is DAC. \n\nCutset Conditioning:\nConvert CSP into a tree by fixing values for certain variables and applying consistency for neighbors, then removing fixed variables from graph. Fixed values could be wrong, so try again. First, choose a subset S of variables s.t. CSP/S becomes tree. S is a cycle cutset. For each possible assignment to variables in S that satisfies constraints, remove inconsistent values from domains in CSP - S and if CSP - S has a solution, return that assignment along with assignment of S. If cutset is size c, the runtime is O(d^c * (n-c)d^2). \n\nTree Decomposition:\nThe tree decomposition of a CSP is the transformation of the original graph into a tree where each node in the tree consists of a set of variables. Basically, nodes are subgraphs of CSP. Tree decomposition must have these requirements:\n\n1) Every variable in problem appears in at least one of the nodes. \n\n2) If two variables are connected by a constraint in original problem, they must appear together (with the constraint) in at least one of the nodes. \n\n3) If a variable appears in two nodes in the tree, it must appear in every node on the path connecting the two nodes. \n\nTree decomposed CSP can be solved in O(nd^2) time. The tree width is one less than size of largest node and the tree width of the graph is defined as the minimum of all tree widths of its decompositions. If graph has tree width w then it can be solved in (nd^{w+1}) time. \n\nTree decomposition is in general faster than cutset conditioning. However, cutset can be performed in linear memory whilst tree decomposition needs memory exponential to w.\n\nValue Symmetry: For every consistent solution there are d! solutions formed by permuting the values, called value symmetry. We can reduce the search space by imposing a symmetry-breaking constraint, like an arbitrary ordering constraint.\n\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Local consistency** - enforcing consistency in local nodes can cause inconsistent values to be eliminated\n* **Node consistency** - all nodes in graph are consistent with their unary constraints\n* **Global constraint** - constraint involving an arbitrary number of variables\n* **Commutativity** - order doesn't matter when assigning values to variables.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Knowledge based agents have a KB or knowledge base. KB is a set \\\n",
        "of sentences expressed in a knowledge representation language and represents an assertion \\\n",
        "about the world. When a sentence is not derived from other sentences it is called an axiom. \\\n",
        "Adding and querying sentences from KB are performed using TELL and ASK. When agent program \\\n",
        "is called it TELLS KB what it perceives, ASKS KB what action to perform, and tells KB what action \\\n",
        "it performed. \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Sentences are expressed based on syntax of the representation language. \\\n",
        "Sentence logic defines the semantics / meaning of the sentence, and whether or not it is true or \\\n",
        "false within the world / model. If a sentence a is true in model M, then M satisfies a, and M is a model \\\n",
        "of a.\"\"\"\n",
        "chapter7_4 = \"\"\" Models set truth values (true or false) for every proposition symbol. Semantics specify how to \\\n",
        "compute truth values for sentences. The rules for complex sentences are : \\n\n",
        "not P is true iff P is false in m \\n\n",
        "P^Q is true iff both P and Q are true in m \\n\n",
        "P disj. Q is true iff P or Q is true in m \\n\n",
        "P => Q is true unless P is true and Q is false in m \\n\n",
        "P <=> Q is true iff P and Q are both true or both false in m\"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"entailment\" : \"a sentence follows logically from another sentence, in every model a is true, b is also true\",\n",
        "\"model checking\": \"enumerate through all possible model and check entailment through inference\",\n",
        "\"sound\": \"an inference algorithm that derives only entailed sentences\",\n",
        "\"complete\": \"an inference algorithm that can derive any sentence that is entailed\",\n",
        "\"atomic sentence\": \"consists of a single propositional symbol\",\n",
        "\"complex sentence\": \"constructed from simpler sentences and logical connectives\",\n",
        "\"logical equivalence\": \"a and b are true in same set of models\",\n",
        "\"validity\": \"sentence is true in all models\",\n",
        "\"deducion theorem\": \"for any sentences a and b, a entails b iff sentence a => b is valid\",\n",
        "\"satisfiability\": \"sentence is true in / satisfied by some model\",\n",
        "\"conjunctive normal form\": \"sentence as a conjunction of clauses, every sentence is equivalent to a CNF\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 140,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 886
        },
        "outputId": "829158b2-d2ba-4014-e6f1-7e878c93152d"
      },
      "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": 141,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge based agents have a KB or knowledge base. KB is a set of sentences expressed in a knowledge representation language and represents an assertion about the world. When a sentence is not derived from other sentences it is called an axiom. Adding and querying sentences from KB are performed using TELL and ASK. When agent program is called it TELLS KB what it perceives, ASKS KB what action to perform, and tells KB what action it performed. \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Sentences are expressed based on syntax of the representation language. Sentence logic defines the semantics / meaning of the sentence, and whether or not it is true or false within the world / model. If a sentence a is true in model M, then M satisfies a, and M is a model of a.\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Models set truth values (true or false) for every proposition symbol. Semantics specify how to compute truth values for sentences. The rules for complex sentences are : \n\nnot P is true iff P is false in m \n\nP^Q is true iff both P and Q are true in m \n\nP disj. Q is true iff P or Q is true in m \n\nP => Q is true unless P is true and Q is false in m \n\nP <=> Q is true iff P and Q are both true or both false in m\n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Entailment** - a sentence follows logically from another sentence, in every model a is true, b is also true\n* **Model checking** - enumerate through all possible model and check entailment through inference\n* **Sound** - an inference algorithm that derives only entailed sentences\n* **Complete** - an inference algorithm that can derive any sentence that is entailed\n* **Atomic sentence** - consists of a single propositional symbol\n* **Complex sentence** - constructed from simpler sentences and logical connectives\n* **Logical equivalence** - a and b are true in same set of models\n* **Validity** - sentence is true in all models\n* **Deducion theorem** - for any sentences a and b, a entails b iff sentence a => b is valid\n* **Satisfiability** - sentence is true in / satisfied by some model\n* **Conjunctive normal form** - sentence as a conjunction of clauses, every sentence is equivalent to a CNF\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": "51afda9f-7955-4838-9455-f106e22f016e"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 142,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nAn agent is something that acts. A rational agent acts to get the best outcome or the best expected outcome. The rational agent approach to AI is the best approach because rationality standards are mathematically defined. Ai is focused on agents that do the right thing.\n\n## AIMA Chapter 27.1 The Limits of AI\n Turing test good at testing human gullibility. Not really a good measure of AI effectiveness. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n  \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can perceive its environment through sensors and act via actuators. A human agent has organs for sensors and hands, vocals, etc. for actuators. An agent's choice of actions depends on the percepts that it has seen but not those it has not yet seen.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n The rationality of an agent can be measured using a performance measure. In general, it is better to create performance measures according to what should be achieved in the environment as opposed to how you want the agent to behave. A rational agent seeks to maximize the performance measure. Rationality maximizes expected performance, not actual performance.\n\n## AIMA 2.3 The Nature of Environments\n A task environment is specified by PEAS. \n\n## AIMA 2.4 The Structure of Agents\n The four basic agent programs are simple reflex, model-based reflex, goal-based, and utility-based.\n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - what agent's sensors are perceiving\n* **Percept sequence** - history of percepts agent has seen\n* **Agent function** - maps percept sequence to action\n* **Agent program** - implementation of agent function\n* **Rational agent** - does the right thing\n* **Performance measure** - how desirable an agent's action sequence is\n* **Definition of a rational agent** - for a percept sequence, the agent should select the action that the maximizes performance measure\n* **Task environment** - problems that agent solves\n* **Peas** - performance, environment, actuators, sensors\n* **Fully observable** - agent's sensors give information about complete state of environment\n* **Multiagent** - two or more agents in task environment\n* **Deterministic** - state will definitely occur as a result of action in current state (no probability)\n* **Stochastic** - non deterministic, but proabilities are numerically defined (25% vs chance of)\n* **Episodic** - current decision doesn't affect others\n* **Sequential** - current decision can affect future decisions\n* **Static** - environment does not change while agent is thinking\n* **Dynamic** - environment can change while agent is thinking\n* **Discrete** - finite number of distinct states\n* **Continuous** - states shift into a range of states\n* **Known** - know the rules / information about environment, not necessarily the complete state\n* **Architecture** - physical device that contains agent program, sensors, and actuators\n* **Simple reflex agent** - choose actions based on current percept\n* **Internal state** - information about world depending on percept history\n* **Transition model** - effects of actions on world, and how world changes independent of agent\n* **Sensor model** - how state of the world is represented by what agent senses\n* **Model based agent** - agent with transition model and sensor model and stores information via internal state\n* **Utility function** - performance measure\n* **Expected utility** - utility agent expects to get based on probabilities and utilities of each outcome\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Python is dynamically typed. Variables come into existence when first defined and you can redefine them as a different type. Functions have no type signatures.\nStrings and tuples are immutable. Lists are mutable. The keys of a dictionary and elements of a set must be immutable. == checks whether variables point to objects of same value whilst is checks whether variables point to same object. Strings, lists, and tuples are sequences. Slicing returns copy of subsequence.\n```\nt[1:4] #slicing ends exclusive of last index\nt[1:-1] #can use negative index\nt[1:-1:2] #select every n th item\nt[:2] #copy from beginning of sequence\nt[2:] #copy to end of sequence\n``` \nList operations:\n```\nli.reverse() #reverse in place\nli.sort() #sort in place\nli.append(element) #append element to end of list\nli.insert(2, element) #insert element to index of list\nli.count() #number of element occurences\n```\nDictionaries:\n```\nd = {'user':'R2D2', 'pswd': 1234}\nd['user']\n```\nFunctions:\n```\ndef foo(input):\n  line1\n  line2\n  return value\n```\nFunctions cannot be overloaded, ie. they cannot have the same name. Functions can accept a variable number of arguments using *args, keyword args with **kwargs\nDefault parameter values are only evaluated when the def statement they belong to is first executed.\nClasses:\n```\nclass Student:\n  univ = \"upenn\"\n  def __init__(self, name, dept):\n    self.student_name = name\n    ...\n  def print_details(self):\n    ...\n\nclass AI_Student(Student):\n```\nFor Loops and List / Dict Comprehension\n```\nlist(range(5)) #returns [0,1,2,3,4]\nfor x in range(5):\n  print(x)\n\nsquares = [x*x for x in nums]\n[n * 3 for (x, n) in li] #can use on tuples\n[elem * 2 for elem in li if elem > 4]\n\nd = { k: v for k,v in lst1 } #dict comprehension\ns = { x for x in lst2 } #set comprehension\n```\nGenerators:\n```\ndef f(n):\n  #returns after yield and sets breakpoint, can be called again\n  yield n\n  yield n+1\n[i for i in f(6)]\n```\nImports\n```\nimport math\nmath.sqrt(9)\n\nfrom math import sqrt\nsqrt(9)\n\nimport numpy as np\n```\n\n\n## Module 2 Definitions\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n A search problem is defined by the state space, initial state, goal states, actions, transition model, and action cost function. \n\n## AIMA Chapter 3.2 Example Problems\n\n\n## AIMA Chapter 3.3 Search Algorithms\n You can turn the state space into a search tree. Nodes in the tree are states and edges are actions.\n\nBest-First Search:\nFor each iteration, choose a node from queue with minimum value of f(n), and return if it is goal node else expand it. Child nodes are added if they have not yet been seen or if they are reached from a path with a lower path cost than before. This graph search algorithm is complete.\n\n\nFor implicit graphs, algorithm complexity is measured using d, m, and b. \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBreadth First Search: \nRoot is expanded first, then successors, then their successors.\nComplete and optimal. However, time and space complexity is O(b^d).\n\n\nUniform-Cost Search (Dijkstra's):\nBest-First search with path cost as evaluation function. Spreads out in waves of uniform path cost, similar to BFS spreading out in waves of uniform depth. Complete and optimal.\nHowever, time and space complexity is O(b^{1+[C*/e]}), where C* is cost of optimal solution and e is the lower bound on cost of each action. This complexity could be muchgreater than b^d because the search could explore large trees with paths of low costs before exploring a path with high cost that has a meaningful action.\n\n\nDepth-First Search:\nExpands deepest node in frontier first. Does not store redundant paths. Is not optimal and not complete. However, uses much less memory compared to BFS. Space complexity O(bm). Time complexity is O(b^m)\n\n\nDepth-Limited Search and iterative Deepening Search:\nDFS with depth limit l. Time complexity is O(b^l) and space complexity is O(bl). Can be incomplete if fails to reach solution with depth l.\nIterative Deepening Search calls Depth-Limited Search for increasing values of l until a solution is found. Optimal for same cost actions and complete for finite state spaces. Time complexity is O(b^d) when there is a solution and O(b^m) otherwise. Space complexity is O(bd) when there is a solution and O(bm) otherwise (for finite state spaces).\n\n\nBidirectional Search:\nSearches forward from start state and backwards from goal state. Keep track of two frontiers and two sets of reached states. We have a solution when the two frontiers collide. Uses best-firstsearch. Space and time complexity is O(b^{d/2}).\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - possible states environment can be in\n* **Initial state** - starting state\n* **Goal states** - states we want to end at\n* **Actions** - actions available to agent at a specific state\n* **Transition model** - what actions do or what states they result in\n* **Action cost function** - costs of taking actions\n* **Node** - state\n* **Edge** - action\n* **Expand** - expand node to see possible actions to other states\n* **Frontier** - nodes that have yet to be expanded / explored\n* **Graph search** - checks for redundant paths. Uses more memory but runs faster\n* **Tree-like search** - does not check for redundant paths. Uses less memory but runs slower\n* **Complete** - guaranteed to find a solution if there is one, and otherwise returns failure\n* **Optimal** - returns solution with lowest path cost\n* **Depth** - aka d, the number of actions in an optimal solution\n* **M** - maximum number of actions in any path / max depth of all paths\n* **Branching factor** - aka b, the number of children of a node\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\nGreedy Best-First Search:\nBest-first search that expands nodes with lowest h(n) value. Not optimal, but is complete on finite spaces. Time and space complexity is O(V), with good heuristic, can reach O(bm).\n\n\nA* Search:\nBest-first search that uses function f(n) = h(n) + g(n), where g(n) is the path cost from start node to node n, and h(n) is estimated shortest path from node n to goal. Is complete, and can be optimal with an admissible heuristic. Can be optimal a inadmissible heuristic if h(n) is admissible for the shortest path or if h(n) overstimates some costs, but never by more than the difference in costs between the\nbest solution and second to best solution. Weighted A* search weighs h(n) by some constant W, resulting in fastersearches.\n\n## AIMA Chapter 3.6 Heuristic Functions\n The quality of a heuristic can be characterized by its branching factor b*. The smaller b* is (best is 1) the better, as it means the search will generate less nodes. When comparing heuristics, h1 and h2, if h1 >= h2 then h1 dominates h2 and is the more efficient heuristic because it will expand less nodes. We can generate heuristics by relaxing the restrictions on a problem, creating a supergraph of the original state space. The cost of an optimal solution to this relaxed problem is an admisisble heuristic to the original problem.\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Informed search** - has access to heuristic function\n* **Admissible heuristic** - a heuristic that never overestimates cost to reach a goal\n* **Consistency** - heuristic is consistent if h(n) <= cost(to successor of n) + h(successor of n). Is admissible\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n A game can be defined with the elements: initial state, the player whose turn it is in a specific state, the set of legal moves in state s, the transition model, terminal state, and the utility function.\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n MAX wants to find a sequence of moves to win the game, but MIN will prevent that. Thus, MAX's strategy will be a collection of responses to MIN's possible moves. We can use minimax search\nto come up with a winning move strategy. Minimax assumes perfect, zero-sum games. Given a game tree, the optimal strategy is the minimax value. MAX prefers to move to states with maximum minimax values whilst MIN wants to move to states with minimum values.\n\n\nMinimax Search:\nRepresents the game as a tree. Recursively goes down the leaves of the tree and then backs up minimax values as the recursion unwinds. (ex. if current player is MIN, first gets utility from terminal nodes and then sends back up the minimum value, setting the parent node's minimax value to that value). Exploration is depth-first like DFS. If b is the number of legal moves at each point and m is the maximum depth of the tree, then the time complexity is O(b^m) and the space complexity is O(bm) (if all actions are generated at once, and O(m) if actions generated one at a time). For games with more than two players, have node values be vectors representing values for each player. Backed-up value at node n is the utility vector of the child state with the highest value for the player whose turn it is at n.\n\n\nAlpha-Beta Pruning:\nCan stop exploring successors by storing alpha and beta values at each node. For a node n in the tree, if the current player has a choice to move to it, but the player has a better choice at the same level or at a higher point in the tree, then the player will not move to n. The seach prunes branches as soon as current node is worse than the current alpha or beta value for MAX and MIN, respectively. Pruning effectiveness depends on the ordering of states. Perfect move ordering could result in O(b^{m/2}) examined nodes instead of O(b^m). We can try moves that were found to be the best in the past through iterative deepening by exploring one ply, recording the best moves, then exploring one ply more, ordering those moves by the previous ply's rankings. The best moves are called killer moves and trying them first is called the killer move heuristic. We can have redundant moves such that two sequences of moves result in the same game state. We can use a transposition table to cache the heuristic values of states to prevent this.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n We can cut off our search early and apply a heuristic function to the states, which estimates their expected utility. We determine if a state is terminal using a terminal test, which returns true for terminal states and for states designated to be our cutoff. The heuristic function, EVAL(s), is an estimate of expected utility and must have a value between a loss and a win. You can precompute possible move sequences and add them to a table to be looked up later.\n\n## AIMA Chapter 5.5 Stochastic Games\n For games of chance, our tree will have chance nodes with branches leading out from them denoting possible probability outcomes. States do not have minimax values but instead expected value. The presence of chance nodes causes our evaluation function to not just place higher values to better positions, as a change of evaluation values can change outcomes. The evaluation function must return values that are a positive linear transformation of probability of winning. For dice, if we knew all future dice rolls then expectiminimax and minimax will take the same time, O(b^m). Otherwise, Expectiminimax takes O(b^m * n^m), where n is the number of distinct rolls. Can do alpha-beta pruning if we place bounds on chance nodes by placing bounds on utility function.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n We can have preference relations between states. Preference relations must obey: orderability, transitivity, continuity, substitutability, monotonicity, and decomposability. \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Perfect information** - fully observable\n* **Zero-sum** - the benefit a player gains from a move is just as harmful to the other player\n* **Move** - an action a player takes\n* **Terminal state** - state where game has ended\n* **Utility function** - score for player p when game is terminal\n* **Ply** - one move by one player, ie. one layer of the tree\n* **Minimax value** - the utility for max of being in a specific state\n* **Alpha** - the highest value choice so far at any choice point along path for MAX, aka at least\n* **Beta** - the lowest value choice so far at any choice point along path for MIN, aka at most\n* **Type a strategy** - wide but shallow, moves to a specific depth of tree then uses a heuristic to estimate utility for those states\n* **Type b strategy** - deep but narrow, ignores bad moves and follows most promising paths\n* **Forward pruning** - prunes moves that seem to be bad, at risk of them turning good. Type B\n* **Beam search** - consider a beam of n best moves on each ply rather than all possible moves. Best move can be pruned.\n* **Stochastic games** - games with a random element, like dice\n* **Expected value** - sum of value over all outcomes, weighted by chance of each action\n* **Expectiminimax value** - utility value for terminal states, expected value for nonterminal states\n* **Maximum expected utility** - agent should choose maximal expected utility, MEU\n* **Lottery** - set of possible outcomes, each with probabilities\n* **Orderability** - agent must prefer a lottery over another, or equally\n* **Transitivity** - if agent prefers A to B, and B to C, then it prefers A to C\n* **Continuity** - if B is between A and C, then probability that agent indifferent to B vs lottery of A and C\n* **Substitutability** - If agent indifferent to A and B, then B can substitute A in a lottery\n* **Monotonicity** - if agent prefers A to B, then it will choose a lottery with a higher chance for A\n* **Decomposabliity** - compound lotteries can be simplified\n* **Expected utility of lottery** - utility of lottery is sum of probability of each outcome times utility of that outcome\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Compared to search problems, CSPs' states are represented as a set of variables as opposed to a black box. A problem is solved when each variable in a state has a value that satisfies all constraints on that variable. CSPs consist of components C, D, and X. X is the set of variables {X1, ..., Xn}, D is the set of domains, {D1, ..., Dn}, one for each variable, and C is the set of constraints that specify desired values. A domain Dk consists of possible values for the variable Xk. CSPs assign values to variables. An assignment that does not violate the constraints is called consistent. A complete assignment is where all variables are assigned a value. The solution to a CSP is a complete, consistent assignment.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nCSPs can generate successors by choosing a variable assignment or through inference. A specific type of inference is constraint propagation, using cconstraints to reduce possible values for variables, which can reduce possible values for another variable, recursively. Constraint propagation can be intertwined with search, or as a preprocess. We can enforce consistency through local consistency. Types of local consistency are: node consistency, where a node's values all satisfy the unary constraint, arc consistency, where for variables Xi and Xj, for every value in Di, there is a value in Dj that satisfies the binary constraint.\n\nAC-3:\nAn algorithm to enforce arc-consistency. Maintain a queue of all arcs. While the queue is not empty: pop an arc out and enforce arc consistency, removing inconsistent values from domain of Xi. If domain of Xi has changed then add all arcs that contain Xi with the exception of the arc with Xj, into the queue. Terminate when queue is empty. For n variables with domain sizes at most d and c binary constraints, runtime is O(cd^3).\n\n\nPath consistency tightens binary constraints by using implicit constraints by looking at triples of variables. A two variable set Xi,Xj is path consistent with a third variable Xm if for every assignment consistent with constraints on Xi, Xj, there is an assignment to Xm that satisfies constraints on Xi,Xm and Xm,Xj (Xm in between the two). Stronger consistencies are k consistency. A CSP is k consistent if for any set of k-1 variables and for a consistent assignemnt to those variables, we can assign a consistent value to any kth variable. A CSP is strongly consistent if it is k consistent, k-1 consistent, ..., 1-consistent. If we have a CSP that is strongly consistent we can go through all variables and search only from their domains. The runtime is O(n^2 * d)\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n We can search CSPs using backtracking search.\n\nBacktracking search:\nRepeatedly choose an unassigned variable and assign it every value in the domain, and extending each choice by a recursive call. If the call succeeds then we have a solution, else we restore the assignment to the previous state and try the next value.\n\nChoosing Unassigned Variable Strategies:\nMinimum-remaining-values heuristic (MRV), where we pick the variable with the lowest legal values.\nDegree heuristic, where we pick the variable that has the most constraints with other unassigned variables.\n\n\nOrdering Domain Value Strategies: \nLeast-Constraining-Value heuristic, where we prefer values that rule out fewest values for neighboring variables\n\nIn general, variable selection is fail first whilst domain ordering is fail last.\n\n\nForward Checking:\nWhenever X is assigned, forward checking establishes arc consistency for it. For each unassigned variable Y constrained with X, delete values from Y's domain inconsistent with that assigned for X.\nMaintaining Arc Consistency (MAC):\nAfter Xi is assigned a value, we call AC-3 with only the arcs Xj, Xi in the queue, where Xj are unassigned neighbors of Xi.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search on CSPs is where we start with a value assigned to each variable and go through the conflicting variables, selecting values that bring us closer to the solution. We can pick the value that results in the minimum number of conflicts, which is the min-conflicts heuristic. We can restrict the search by keeping a list of visited states and not allowing the algorithm to revisit the states, called tabu search. We can also perform constraint weighting, where we give values to constraints, starting at 1, and increasing constraints' weights when current assignment violates them. \n\n## AIMA Chapter 6.5 The Structure of Problems\n Reducing CSPs into subproblems can drastically decrease runtime. Can convert CSP into a graph structure, like a tree. A CSP is a tree when any two variables are connected by only one path. A tree structured CSP can be solved in time linear to the number of variables. We have consistency called DAC, or directional arc consistency. A CSP is DAC for an ordering of variables X1, X2, ... Xn if and only if every Xi is arc consistent with each Xj for j > i. We can perform topological sort on a tree CSP, resulting in DAC. This is done in O(nd^2) time. Children are guaranteed to be consistent with parent sinc graph is DAC. \n\nCutset Conditioning:\nConvert CSP into a tree by fixing values for certain variables and applying consistency for neighbors, then removing fixed variables from graph. Fixed values could be wrong, so try again. First, choose a subset S of variables s.t. CSP/S becomes tree. S is a cycle cutset. For each possible assignment to variables in S that satisfies constraints, remove inconsistent values from domains in CSP - S and if CSP - S has a solution, return that assignment along with assignment of S. If cutset is size c, the runtime is O(d^c * (n-c)d^2). \n\nTree Decomposition:\nThe tree decomposition of a CSP is the transformation of the original graph into a tree where each node in the tree consists of a set of variables. Basically, nodes are subgraphs of CSP. Tree decomposition must have these requirements:\n\n1) Every variable in problem appears in at least one of the nodes. \n\n2) If two variables are connected by a constraint in original problem, they must appear together (with the constraint) in at least one of the nodes. \n\n3) If a variable appears in two nodes in the tree, it must appear in every node on the path connecting the two nodes. \n\nTree decomposed CSP can be solved in O(nd^2) time. The tree width is one less than size of largest node and the tree width of the graph is defined as the minimum of all tree widths of its decompositions. If graph has tree width w then it can be solved in (nd^{w+1}) time. \n\nTree decomposition is in general faster than cutset conditioning. However, cutset can be performed in linear memory whilst tree decomposition needs memory exponential to w.\n\nValue Symmetry: For every consistent solution there are d! solutions formed by permuting the values, called value symmetry. We can reduce the search space by imposing a symmetry-breaking constraint, like an arbitrary ordering constraint.\n\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Local consistency** - enforcing consistency in local nodes can cause inconsistent values to be eliminated\n* **Node consistency** - all nodes in graph are consistent with their unary constraints\n* **Global constraint** - constraint involving an arbitrary number of variables\n* **Commutativity** - order doesn't matter when assigning values to variables.\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Knowledge based agents have a KB or knowledge base. KB is a set of sentences expressed in a knowledge representation language and represents an assertion about the world. When a sentence is not derived from other sentences it is called an axiom. Adding and querying sentences from KB are performed using TELL and ASK. When agent program is called it TELLS KB what it perceives, ASKS KB what action to perform, and tells KB what action it performed. \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Sentences are expressed based on syntax of the representation language. Sentence logic defines the semantics / meaning of the sentence, and whether or not it is true or false within the world / model. If a sentence a is true in model M, then M satisfies a, and M is a model of a.\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Models set truth values (true or false) for every proposition symbol. Semantics specify how to compute truth values for sentences. The rules for complex sentences are : \n\nnot P is true iff P is false in m \n\nP^Q is true iff both P and Q are true in m \n\nP disj. Q is true iff P or Q is true in m \n\nP => Q is true unless P is true and Q is false in m \n\nP <=> Q is true iff P and Q are both true or both false in m\n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Entailment** - a sentence follows logically from another sentence, in every model a is true, b is also true\n* **Model checking** - enumerate through all possible model and check entailment through inference\n* **Sound** - an inference algorithm that derives only entailed sentences\n* **Complete** - an inference algorithm that can derive any sentence that is entailed\n* **Atomic sentence** - consists of a single propositional symbol\n* **Complex sentence** - constructed from simpler sentences and logical connectives\n* **Logical equivalence** - a and b are true in same set of models\n* **Validity** - sentence is true in all models\n* **Deducion theorem** - for any sentences a and b, a entails b iff sentence a => b is valid\n* **Satisfiability** - sentence is true in / satisfied by some model\n* **Conjunctive normal form** - sentence as a conjunction of clauses, every sentence is equivalent to a CNF\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}