{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CIS 521 Midterm I Notes.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "51c191d5-c7a8-49ab-f0be-51e1d1fab9a4"
      },
      "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": 3,
      "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": "56f9946e-b3b8-4282-85ca-50bd81197afa"
      },
      "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": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 5,
      "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 = \"\"\" Intelligence can be have internal characterization (thought processes and reasoning),\n",
        "or external characterization (behavior). \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" N/A \"\"\"\n",
        "chapter27_2 = \"\"\" N/A \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" N/A \"\"\"\n",
        "chapter2_2 = \"\"\" N/A \"\"\"\n",
        "chapter2_3 = \"\"\" For an agent type of medical diagnosis system, we have P: healthy patient, reduced costs,\n",
        "E: patient, hospital, staff, A: display of questions, tests, diagnoses, treatments, S: touchscreen/voice entry of symptoms and findings.\n",
        "For an agent type of satellite image analysis system, we have P: correct categorization of objects, terrain, E: orbiting satellite, weather,\n",
        "A: display of scene categorization, S: high-resolution digital camera. Other example agents are part-picking robot, refinery controller, interactive English tutor.\n",
        "\\n\n",
        "A known (outomces for all actions are given vs unknown (the agent will have to learn how it works\n",
        "in order to make good decisions) environment distinction with fully and partially observable environments:\n",
        "Known + partially observable example: solitaire (know the rules but unable to see the cards that are not turned over).\n",
        "Unknown + fully observable example: new video game, screen shows entire game state, but still don't know what the buttons \n",
        "do until you try them.\n",
        " \"\"\"\n",
        "chapter2_4 = \"\"\" The challenge for AI is to find out how to write programs that produce rational beavhior\n",
        "from a smaller program raher than from a vast table.\n",
        "\\n\n",
        "We should handle partial observability by keeping track of the part of the world that is currently unseen (maintain\n",
        "some sort of internal state based on percept history!). \n",
        "\\n\n",
        "Goals only provide a distinction between 'happy' and 'unhappy' states. A utility function tells us how good a state is.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Alan Turing designed a test that asks whether machines can really think. It tests whether a human can \n",
        "distinguish between a human and machine designed to generate human-like responses. John Searle believed that the \n",
        "Turing Test did not test whether machines possessed intelligence. With the Chinese Room experiment (room containing human\n",
        "with no knowledge of Chinese, a rule book, and paper), Searle argues that the participant can do things that may simulate intelligence,\n",
        "but in reality he has no actual understanding of Chinese.\n",
        "\\n\n",
        "There are 4 views of AI: thinking humanly, thinking rationally, acting humanly, and acting rationally.\n",
        "An __agent__ is anything that perceives its environment through sensors and can act on its environment through actuators.\n",
        "A __percept__ is the agent's perceptual inputs at any given instance. An agent function $f: P \\\\rightarrow A$ maps\n",
        "a sequence of percept vectors $P$ to an action $a$ from a set $A$: $P=\\\\{p_0,p_1,\\\\ldots,p_t\\\\}$,  $A=\\\\{a_0,a_1,\\\\ldots,a_k\\\\}$.\n",
        "\\n\n",
        "The __agent program__ runs on the physical architecture to product $f$: agent = architecture + program.\n",
        "\\n\n",
        "A __rational agent__ perceives its environment and behaves rationally. A rational agent selects an action $a$ to maximize (expected value of its) performance measure.\n",
        "\\n\n",
        "A __performance measure__ gives us a criterion for success of an agent's behavior given the evidence provided by the percept sequence.\n",
        "Example performance measures for a vacuum cleaner agent may be: +1 for each clean square at time $T$, +1 for cleaning a square, -1 for each move, -1000 for more than $k$ dirty squares.\n",
        "\\n\n",
        "To design a rational agent, we need to specify a task environment wiht PEAS: Performance measure, Environment, Actuators, Sensors.\n",
        "The rational agent should construct an agent function $f$ that maximizes the expected value of the performance measure and design an agent program that implements $f$.\n",
        "\\n\n",
        "__Fully observable (chess) vs Partially observable (autonomous car)__.\n",
        "\\n\n",
        "__Deterministic__ (chess) means agent can select an action and know the state of the world completely, __Stochastic__ is probabilistic, meaning we can quantify how likely each outcome is.\n",
        "\\n\n",
        "__Episodic__ means each decision is independent of past decisions, __Sequential__ means we need to plan ahead (more challenging than episodic).\n",
        "\\n\n",
        "__Static__ (sudoku) means envionrment is unchanged until taking next action, __Dynamic__ (autonomous car) means the environment is changing while the agent thinks.\n",
        "\\n\n",
        "__Discrete__ means there is a limited number of clearly defined actions or a finite set of actions to take, __Continuous__ rely on changing data sources like time.\n",
        "\\n\n",
        "__Single agent__ (crossword puzzle), __Multi-agent__ (chess, pacman). When we have multi-agents, we need strategies.\n",
        "\\n\n",
        "Agent vs part of the environment? When something can be described as having its own performance measure, then we should consider it to be an agent.\n",
        "\\n\n",
        "The hardest environment is continuous, partially observable, stochastic, multi-agent. But for now we will assume our environment is static, fully observable, deterministic, discrete.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"Turing test\" : \"experiment to test whether machines can really think, passes if a human cannot distinguish\",\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"rational agent\" : \"agent that acts rationally, to achieve the best/best expected outcome\",\n",
        "\"simple reflex agent\" \"agent that select actions on the current percept, ignoring the history\"\n",
        "\"limited rationality\" : \"not enough time to do all possible computations, but acting appropriately\",\n",
        "\"percept\" : \"what the agent is perceiving\",\n",
        "\"percept sequence\" : \"the history of what the agent has perceived\",\n",
        "\"agent function\" : \"maps a percept sequence to an action\",\n",
        "\"goal\" : \"desirable situations/states\",\n",
        "\"utility function\": \"internalized performance measure\",\n",
        "\"atomic representation\" : \"states of the world are indivisible with no internal structure\",\n",
        "\"factored representation\" : \"splitting states into a fixed set of variables/attributes, each having a value\",\n",
        "\"consequentialism\" : \"measure behavior by consequences of its behaviors\",\n",
        "\"omniscience\" : \"knowing actual outcome of actions, impossible in reality\",\n",
        "\"task environments\" : \"the 'problems' in which the agents are the 'solution'\",\n",
        "\"weak AI\" : \"machines act as if they were intelligent, simulate thinking\",\n",
        "\"strong AI\" : \"machines actually are consciously thinking\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "8b8e36a0-3c26-49ee-ce34-93f071ee6cd6"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Intelligence can be have internal characterization (thought processes and reasoning),\nor external characterization (behavior). \n\n## AIMA Chapter 27.1 The Limits of AI\n N/A \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n N/A \n\n## AIMA 2.1 Agents and Environments\n N/A \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n N/A \n\n## AIMA 2.3 The Nature of Environments\n For an agent type of medical diagnosis system, we have P: healthy patient, reduced costs,\nE: patient, hospital, staff, A: display of questions, tests, diagnoses, treatments, S: touchscreen/voice entry of symptoms and findings.\nFor an agent type of satellite image analysis system, we have P: correct categorization of objects, terrain, E: orbiting satellite, weather,\nA: display of scene categorization, S: high-resolution digital camera. Other example agents are part-picking robot, refinery controller, interactive English tutor.\n\n\nA known (outomces for all actions are given vs unknown (the agent will have to learn how it works\nin order to make good decisions) environment distinction with fully and partially observable environments:\nKnown + partially observable example: solitaire (know the rules but unable to see the cards that are not turned over).\nUnknown + fully observable example: new video game, screen shows entire game state, but still don't know what the buttons \ndo until you try them.\n \n\n## AIMA 2.4 The Structure of Agents\n The challenge for AI is to find out how to write programs that produce rational beavhior\nfrom a smaller program raher than from a vast table.\n\n\nWe should handle partial observability by keeping track of the part of the world that is currently unseen (maintain\nsome sort of internal state based on percept history!). \n\n\nGoals only provide a distinction between 'happy' and 'unhappy' states. A utility function tells us how good a state is.\n\n## Module 1 Lecture Notes\n Alan Turing designed a test that asks whether machines can really think. It tests whether a human can \ndistinguish between a human and machine designed to generate human-like responses. John Searle believed that the \nTuring Test did not test whether machines possessed intelligence. With the Chinese Room experiment (room containing human\nwith no knowledge of Chinese, a rule book, and paper), Searle argues that the participant can do things that may simulate intelligence,\nbut in reality he has no actual understanding of Chinese.\n\n\nThere are 4 views of AI: thinking humanly, thinking rationally, acting humanly, and acting rationally.\nAn __agent__ is anything that perceives its environment through sensors and can act on its environment through actuators.\nA __percept__ is the agent's perceptual inputs at any given instance. An agent function $f: P \\rightarrow A$ maps\na sequence of percept vectors $P$ to an action $a$ from a set $A$: $P=\\{p_0,p_1,\\ldots,p_t\\}$,  $A=\\{a_0,a_1,\\ldots,a_k\\}$.\n\n\nThe __agent program__ runs on the physical architecture to product $f$: agent = architecture + program.\n\n\nA __rational agent__ perceives its environment and behaves rationally. A rational agent selects an action $a$ to maximize (expected value of its) performance measure.\n\n\nA __performance measure__ gives us a criterion for success of an agent's behavior given the evidence provided by the percept sequence.\nExample performance measures for a vacuum cleaner agent may be: +1 for each clean square at time $T$, +1 for cleaning a square, -1 for each move, -1000 for more than $k$ dirty squares.\n\n\nTo design a rational agent, we need to specify a task environment wiht PEAS: Performance measure, Environment, Actuators, Sensors.\nThe rational agent should construct an agent function $f$ that maximizes the expected value of the performance measure and design an agent program that implements $f$.\n\n\n__Fully observable (chess) vs Partially observable (autonomous car)__.\n\n\n__Deterministic__ (chess) means agent can select an action and know the state of the world completely, __Stochastic__ is probabilistic, meaning we can quantify how likely each outcome is.\n\n\n__Episodic__ means each decision is independent of past decisions, __Sequential__ means we need to plan ahead (more challenging than episodic).\n\n\n__Static__ (sudoku) means envionrment is unchanged until taking next action, __Dynamic__ (autonomous car) means the environment is changing while the agent thinks.\n\n\n__Discrete__ means there is a limited number of clearly defined actions or a finite set of actions to take, __Continuous__ rely on changing data sources like time.\n\n\n__Single agent__ (crossword puzzle), __Multi-agent__ (chess, pacman). When we have multi-agents, we need strategies.\n\n\nAgent vs part of the environment? When something can be described as having its own performance measure, then we should consider it to be an agent.\n\n\nThe hardest environment is continuous, partially observable, stochastic, multi-agent. But for now we will assume our environment is static, fully observable, deterministic, discrete.\n\n\n## Module 1 Definitions\n* **Turing test** - experiment to test whether machines can really think, passes if a human cannot distinguish\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - agent that acts rationally, to achieve the best/best expected outcome\n* **Simple reflex agentagent that select actions on the current percept, ignoring the historylimited rationality** - not enough time to do all possible computations, but acting appropriately\n* **Percept** - what the agent is perceiving\n* **Percept sequence** - the history of what the agent has perceived\n* **Agent function** - maps a percept sequence to an action\n* **Goal** - desirable situations/states\n* **Utility function** - internalized performance measure\n* **Atomic representation** - states of the world are indivisible with no internal structure\n* **Factored representation** - splitting states into a fixed set of variables/attributes, each having a value\n* **Consequentialism** - measure behavior by consequences of its behaviors\n* **Omniscience** - knowing actual outcome of actions, impossible in reality\n* **Task environments** - the 'problems' in which the agents are the 'solution'\n* **Weak ai** - machines act as if they were intelligent, simulate thinking\n* **Strong ai** - machines actually are consciously thinking\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 = \"\"\" In Python, all data is treated as objects (deleted by garbage collection).\n",
        "\\n\n",
        "__Literals__: integers (1, 2), Floats (1.0, 2e9), Boolean (True, False)\n",
        "\\n\n",
        "__Operations__: arithmetic (+, -, *, /), power ((*)(*)), modulo (%), comparison (<=, >=, ==, !=), logic (and, or, not).\n",
        "\\n\n",
        "There is no ++ or -- in Python!\n",
        "\\n\n",
        "You can concatentate strings with '+'. You can format strings as such: print(\"%s can speak $d languages\" $(\"C3P0\", 6000000)).\n",
        "\\n\n",
        "__Strings__ are immutable. Lists are mutable. Use y = x[:] to obtain a shallow copy of any sequence (new object of the same value).\n",
        "\\n\n",
        "== checks if two things are the same value, is checks whether the variables point to the same object.\n",
        "\\n\n",
        "__Functions__: strip() gets rid of whitespaces at beginning and end. split(delim) makes an array of the string separated\n",
        "by the delim.\n",
        "\\n\n",
        "Slicing examples (lst[initial:end:indexjump]): t=(23, 'abc', 4.56, (2,3), 'def')\n",
        "\\n\n",
        "t[1:4] -> ('abc', 4.56, (2,3)). We don't include the last index in the slice.\n",
        "\\n\n",
        "t[1:-1] -> ('abc', 4.56, (2,3))\n",
        "\\n\n",
        "t[1:-1:2] -> ('abc', (2,3))\n",
        "\\n\n",
        "t[:2] -> (23, 'abc'). Copies from the beginning of the sequence.\n",
        "\\n\n",
        "t[2:] -> (4.56, (2,3), 'def). Copies to the end of the sequence.\n",
        "\\n\n",
        "Operations on lists example: li = [1, 11, 3, 4, 5]\n",
        "\\n\n",
        "li.append('a') -> [1, 11, 3, 4, 5, 'a']\n",
        "\\n\n",
        "li.insert(2,'i') -> [1, 11, 'i', 3, 4, 5, 'a']. Inserted at index 2.\n",
        "\\n\n",
        "Operations on list example: li = [5, 2, 6, 8]\n",
        "\\n\n",
        "li.reverse() -> [8, 6, 2, 5]. Reversed the list in place.\n",
        "\\n\n",
        "li.sort() -> [2, 5, 6, 8]. Sorted the list in place.\n",
        "\\n\n",
        "sorted(li) -> [2, 5, 6, 8]. Returns a copy sorted.\n",
        "\\n\n",
        "__Dictionaries__ must have immutable keys, so lists CANNOT be keys since they are mutable! For dictionaries, we can only\n",
        "look things up by key, not by value.\n",
        "\\n\n",
        "d.keys() returns a list of the current keys. d.value() returns a list of current values. d.items() gives a list of item tuples.\n",
        "\\n\n",
        "__Functions__ are defined first with def, the function name and its arguments and a return. Python allows us to return multiple values like: return mean, median, mode (of type tuple).\n",
        "We CANNOT have function overloading (same method names). We can also provide default values for a function's arguments.\n",
        "\\n\n",
        "For example, def myfun(b, c=3, d=\"hello\"): return b+c.\n",
        "\\n\n",
        "myfun(5,3,\"bob\") returns 8.\n",
        "\\n\n",
        "myfun(5,3) returns 8.\n",
        "\\n\n",
        "myfun(5) returns 8.\n",
        "\\n\n",
        "Functions can also be called with arguments out of ordered, but the arguments must be specified in the call.\n",
        "\\n\n",
        "__\\*args__ allows us to accept a variable number of NON-keyword arguments to a function.\n",
        "\\n\n",
        "Example: def print_everything(\\*args): print(args)\n",
        "\\n\n",
        "print_everything('a','b','c') prints ('a','b','c')\n",
        "\\n\n",
        "lst = ['a','b','c']. print_everything(lst) prints ('a','b','c').\n",
        "\\n\n",
        "__\\*\\*kwargs__ allows us to accept a variable number of keyword arguments to a function.\n",
        "Example: def print_keyword_args(\\*\\*kwargs): print(kwargs)\n",
        "\\n\n",
        "print_keyword_args(first_name=\"John\", last_name=\"Doe\") prints {'first_name': 'John', 'last_name': Doe'}\n",
        "\\n\n",
        "my_dict = {'first_name': 'John', 'last_name': Doe'}. print_keyword_args(\\*\\*my_dict) prints {'first_name': 'John', 'last_name': Doe'}.\n",
        "\\n\n",
        "In a class, every method has \"self\" as an argument. \\__function\\__ are __magic methods__, meaning there's ways \n",
        "to call the function without calling __function__ (i.e. __init__ is called with new).\n",
        "\\n\n",
        "Magic methods include \\__init\\__, \\__len\\__, \\__copy\\__, \\__cmp\\__, \\__add\\__, \\__neg\\__.\n",
        "\\n\n",
        "A class can extend the definition of another class (can use or extend methods and attributes already defined in the previous one).\n",
        "Do this by: class AI_Student(Student).\n",
        "\\n\n",
        "__List comprehensions__ can replace for loops. For example:\n",
        "\\n\n",
        "Example 1:\n",
        "\\n\n",
        "nums = list(range(10))\n",
        "\\n\n",
        "sq = [n*n for n in nums]\n",
        "\\n\n",
        "print(sq) # [0, 1, 4, 9, 16,...]\n",
        "\\n\n",
        "Example 2:\n",
        "\\n\n",
        "li = [3, 6, 2, 7, 1, 9]\n",
        "\\n\n",
        "[elem * 2 for elem in li if elem > 4] # [12, 14, 18]\n",
        "\\n\n",
        "__Generators__ are iterators (with __next__()) method. Functions that contain the yield keywork AUTOMATICALLY return a generator when called.\n",
        "Each time we call __next__ method of the generator, the method runs until it encounters a yield. Then it stops and returns the value that was yielded.\n",
        "Next time, it resumes where it left off.\n",
        "\\n\n",
        "Benefits of generators: less code than standard iterator, maintains local state automatically, values are computed as needed\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"strong typing\" : \"each object has a fixed type, interpreter doesn't allow incompatible types\",\n",
        "\"types\" : \"int, float, str, tuple, dict, list, bool (True, False), None, generator, function\",\n",
        "\"dynamic typing\" : \"variables come into existence when first assigned\",\n",
        "\"shallow copy\" : \"new object of the same value\",\n",
        "\"sequence types\" : \"tuples, strings, lists\",\n",
        "\"tuple\" : \"immutable ordered sequence of items, can be of mixed types\",\n",
        "\"list\" : \"mutable ordered sequence of items of mixed types\",\n",
        "\"dictionary\" : \"unordered, uses hashing, immutable keys, gives O(1) average add, lookup, update\",\n",
        "\"immutable\" : \"cannot modify without making a new copy\",\n",
        "\"first-class object\" : \"entity that can by dynamically created, destroyed, passed to a function, returned as a variable, eg. functions\",\n",
        "\"iterator\" : \"object with a __next__() method, no hasnext in Python\"\n",
        "}"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "730fc194-f815-4a57-a573-202377990e8e"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n In Python, all data is treated as objects (deleted by garbage collection).\n\n\n__Literals__: integers (1, 2), Floats (1.0, 2e9), Boolean (True, False)\n\n\n__Operations__: arithmetic (+, -, *, /), power ((*)(*)), modulo (%), comparison (<=, >=, ==, !=), logic (and, or, not).\n\n\nThere is no ++ or -- in Python!\n\n\nYou can concatentate strings with '+'. You can format strings as such: print(\"%s can speak $d languages\" $(\"C3P0\", 6000000)).\n\n\n__Strings__ are immutable. Lists are mutable. Use y = x[:] to obtain a shallow copy of any sequence (new object of the same value).\n\n\n== checks if two things are the same value, is checks whether the variables point to the same object.\n\n\n__Functions__: strip() gets rid of whitespaces at beginning and end. split(delim) makes an array of the string separated\nby the delim.\n\n\nSlicing examples (lst[initial:end:indexjump]): t=(23, 'abc', 4.56, (2,3), 'def')\n\n\nt[1:4] -> ('abc', 4.56, (2,3)). We don't include the last index in the slice.\n\n\nt[1:-1] -> ('abc', 4.56, (2,3))\n\n\nt[1:-1:2] -> ('abc', (2,3))\n\n\nt[:2] -> (23, 'abc'). Copies from the beginning of the sequence.\n\n\nt[2:] -> (4.56, (2,3), 'def). Copies to the end of the sequence.\n\n\nOperations on lists example: li = [1, 11, 3, 4, 5]\n\n\nli.append('a') -> [1, 11, 3, 4, 5, 'a']\n\n\nli.insert(2,'i') -> [1, 11, 'i', 3, 4, 5, 'a']. Inserted at index 2.\n\n\nOperations on list example: li = [5, 2, 6, 8]\n\n\nli.reverse() -> [8, 6, 2, 5]. Reversed the list in place.\n\n\nli.sort() -> [2, 5, 6, 8]. Sorted the list in place.\n\n\nsorted(li) -> [2, 5, 6, 8]. Returns a copy sorted.\n\n\n__Dictionaries__ must have immutable keys, so lists CANNOT be keys since they are mutable! For dictionaries, we can only\nlook things up by key, not by value.\n\n\nd.keys() returns a list of the current keys. d.value() returns a list of current values. d.items() gives a list of item tuples.\n\n\n__Functions__ are defined first with def, the function name and its arguments and a return. Python allows us to return multiple values like: return mean, median, mode (of type tuple).\nWe CANNOT have function overloading (same method names). We can also provide default values for a function's arguments.\n\n\nFor example, def myfun(b, c=3, d=\"hello\"): return b+c.\n\n\nmyfun(5,3,\"bob\") returns 8.\n\n\nmyfun(5,3) returns 8.\n\n\nmyfun(5) returns 8.\n\n\nFunctions can also be called with arguments out of ordered, but the arguments must be specified in the call.\n\n\n__\\*args__ allows us to accept a variable number of NON-keyword arguments to a function.\n\n\nExample: def print_everything(\\*args): print(args)\n\n\nprint_everything('a','b','c') prints ('a','b','c')\n\n\nlst = ['a','b','c']. print_everything(lst) prints ('a','b','c').\n\n\n__\\*\\*kwargs__ allows us to accept a variable number of keyword arguments to a function.\nExample: def print_keyword_args(\\*\\*kwargs): print(kwargs)\n\n\nprint_keyword_args(first_name=\"John\", last_name=\"Doe\") prints {'first_name': 'John', 'last_name': Doe'}\n\n\nmy_dict = {'first_name': 'John', 'last_name': Doe'}. print_keyword_args(\\*\\*my_dict) prints {'first_name': 'John', 'last_name': Doe'}.\n\n\nIn a class, every method has \"self\" as an argument. \\__function\\__ are __magic methods__, meaning there's ways \nto call the function without calling __function__ (i.e. __init__ is called with new).\n\n\nMagic methods include \\__init\\__, \\__len\\__, \\__copy\\__, \\__cmp\\__, \\__add\\__, \\__neg\\__.\n\n\nA class can extend the definition of another class (can use or extend methods and attributes already defined in the previous one).\nDo this by: class AI_Student(Student).\n\n\n__List comprehensions__ can replace for loops. For example:\n\n\nExample 1:\n\n\nnums = list(range(10))\n\n\nsq = [n*n for n in nums]\n\n\nprint(sq) # [0, 1, 4, 9, 16,...]\n\n\nExample 2:\n\n\nli = [3, 6, 2, 7, 1, 9]\n\n\n[elem * 2 for elem in li if elem > 4] # [12, 14, 18]\n\n\n__Generators__ are iterators (with __next__()) method. Functions that contain the yield keywork AUTOMATICALLY return a generator when called.\nEach time we call __next__ method of the generator, the method runs until it encounters a yield. Then it stops and returns the value that was yielded.\nNext time, it resumes where it left off.\n\n\nBenefits of generators: less code than standard iterator, maintains local state automatically, values are computed as needed\n\n\n## Module 2 Definitions\n* **Strong typing** - each object has a fixed type, interpreter doesn't allow incompatible types\n* **Types** - int, float, str, tuple, dict, list, bool (True, False), None, generator, function\n* **Dynamic typing** - variables come into existence when first assigned\n* **Shallow copy** - new object of the same value\n* **Sequence types** - tuples, strings, lists\n* **Tuple** - immutable ordered sequence of items, can be of mixed types\n* **List** - mutable ordered sequence of items of mixed types\n* **Dictionary** - unordered, uses hashing, immutable keys, gives O(1) average add, lookup, update\n* **Immutable** - cannot modify without making a new copy\n* **First-class object** - entity that can by dynamically created, destroyed, passed to a function, returned as a variable, eg. functions\n* **Iterator** - object with a __next__() method, no hasnext in Python\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": "yqLgdY8frchF"
      },
      "source": [
        ""
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "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 seearch problem can be defined formally with __states__/__state space__, __initial state__, __goal states__, __actions__,\n",
        "__transition model__ (describes what each action does), __action cost function__ (agent should use a cost function to reflect its own performance measure).\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" \n",
        "For a grid world (2d rectangular array of cells) with two-cells we can formulate as a search problem as follows:\n",
        "\\n\n",
        "__States__: Agent can be in either of the two cells. The cells can either contain dirt or not. In a world with $n$ cells, we have $n\\cdot 2^n$ states.\n",
        "\\n\n",
        "__Initial state__: Any state can be the initial.\n",
        "\\n\n",
        "__Actions__: Three actions: suck, move left, move right.\n",
        "\\n\n",
        "__Transition model__: Suck removes any dirt, left moves left, right moves right unless hitting a wall.\n",
        "\\n\n",
        "__Goal states__: The states in which every cell is clean.\n",
        "\\n\n",
        "__Action cost__: Each action costs 1. \n",
        "\\n\n",
        "Traveling salesman problem is a touring problem (describe a set of locations that must be visited, rather than a single destination).\n",
        "\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\" \n",
        "Best First Search chooses a node $n$ with a minimum value of an evaluation function $f(n)$.\n",
        "\\n\n",
        "$|V|$ = number of vertices (state nodes), $|E|$ = number of edgs (distinct state/action pairs). $d$ = depth or nuber of actions in \n",
        "an optimal solution, $m$ = maximum number of actions in any path, $b$ = branching factor, or the number of successors of a node\n",
        "that need to be considered.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" Uninformed search has no idea how close a state is to the goal. \n",
        "__Uniform cost search__ idea -> spread out in waves of uniform cost (not uniform depth). Complexity is characterized in terms of \n",
        "$C^*$, the cost of the optimal solution, and $\\\\epsilon$, a lower bound on the cost of each action. The worst-case time and space\n",
        "complexity is $O(b^{1+\\\\lfloor C^*/\\\\epsilon \\\\rfloor})$, which can be much greater than $b^d$. Uniform-cost search is complete and cost-optimal.\n",
        "\\n\n",
        "__Depth-first search__ expands deepest node in the frontier. Implemented usually as tree-like search, does not keep track of reached states.\n",
        "DFS is not cost-optimal; it returns the first solution it finds. DFS has much smaller space complexity. A DFS search takes time proportional to the number of states\n",
        "and has space complexity of only $O(bm)$, where $b$ is the branching factor and $m$ is the maximum depth of the tree.\n",
        "\\n\n",
        "To prevent DFS from wandering down an infinite path, we use __depth-limited serach__. We go only to a limit $l$. The time complexity is $O(b^l)$, and space\n",
        "complexity is $O(bl)$. __Iterative deepening search__ chooses $l$ to be 0, then 1, then 2, ... until a solution is found or we reach failure. The \n",
        "space complexity is $O(bd)$ when there is a solution, or $O(bm)$ where we have no solution. Like BFS, optimal for problems with same cost.\n",
        "The time complexity is $O(b^d)$ when there is solution, or $O(b^m)$ when none.\n",
        "\\n\n",
        "```\n",
        "function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure \n",
        "  for depth = 0 to ∞ do\n",
        "    result←DEPTH-LIMITED-SEARCH(problem,depth) \n",
        "    if result ̸= cutoff then return result\n",
        "\n",
        "function DEPTH-LIMITED-SEARCH(problem, l) returns a node or failure or cutoff \n",
        "  frontier←a LIFO queue (stack)\n",
        "  result ← failure\n",
        "  while not IS-EMPTY(frontier) do\n",
        "    node←POP(frontier)\n",
        "    if problem.IS-GOAL(node.STATE) then return node \n",
        "    if DEPTH(node) > l then\n",
        "      result ← cutoff\n",
        "    else if not IS-CYCLE(node) do\n",
        "      for each child in EXPAND(problem, node) do \n",
        "        add child to frontier\n",
        "  return result\n",
        "```\n",
        "\n",
        "__Bidirectional search__ searches forward from the initial state and backwards from the goal state(s). The motivation for this\n",
        "search is that $b^{d/2} + b^{d/2}$ is much less than $b^d$. We keep track of two frontiers and two reached sets.\n",
        "```\n",
        "BFS: Complete, optimal cost, O(b^d) time, O(b^d) space\n",
        "Uniform-cost: Complete, optimal cost, O(b^{1+(C*/epsilon)} time, O(b^{1+(C*/epsilon)} space\n",
        "Depth-first: Not complete, not optimal cost, O(b^m) time, O(bm) space\n",
        "Depth-limited: Not complete, not optimal cost, O(b^l) time, O(bl) space\n",
        "Iterative deepening: Complete, optimal, O(b^d) time, O(bd) space\n",
        "Bidirectional: Complete, optimal cost, O(b^{d/2}) time, O(b^{d/2}) space\n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "A reflex agent is one that selects an action based only on the current percept and ignores percept history.\n",
        "A problem-solving agent plans ahead. For a task environment that is fully observable, deterministic, known environment, then the solution\n",
        "is a fixed sequence of actions. In environments that are partially observable or nondeterministic, then the solution must recommend future actions\n",
        "depending on the percepts it receives.\n",
        "\\n\n",
        "For the 8-tile puzzle:\n",
        "\\n\n",
        "__States__: configurations of the puzzle (9! configurations)\n",
        "\\n\n",
        "__Actions__: Move one of the movable pieces (<= 4 possible actions)\n",
        "\\n\n",
        "__Performance measure__: minimize the total moves\n",
        "\\n\n",
        "The __state space__ is the set of all states reachable from the initial state by any sequence of actions.\n",
        "\\n\n",
        "In __uninformed search__, all non-goal nodes in the frontier look equally good.\n",
        "\\n\n",
        "$b$ = maximum branching factor of search tree. $d$ = depth of the shallowest goal node. $m$ = maximum length of any path in the state space (potentially $\\\\inf$)\n",
        "\\n\n",
        "In deciding between DFS and BFS, we should use...\n",
        "\\n\n",
        "DFS: __Space is restricted__, many possible solutions with long paths and wrongs paths can be terminated quickly\n",
        "\\n\n",
        "BFS: __Possible infinite paths__, some solutions have shorter paths, can quickly discard unlikely paths\n",
        "\\n\n",
        "Iterative deepening search uses depth-limited search as a subroutine with increasing $l$.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",   \n",
        "\"path\" : \"a sequence of actions\",\n",
        "\"abstraction\" : \"removing details from a representation\",\n",
        "\"search algorithm\" : \"input is search problem and returns a solution\",\n",
        "\"search tree\" : \"shows paths from initial to hoping to find goal state\",\n",
        "\"frontier\": \"the next unexpanded nodes\",\n",
        "\"graph search\" : \"checks for redundanct paths\",\n",
        "\"tree search\" : \"does not check for redundant paths\"\n",
        "}\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "931fbb07-1703-456c-d076-10526d42da04"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n A seearch problem can be defined formally with __states__/__state space__, __initial state__, __goal states__, __actions__,\n__transition model__ (describes what each action does), __action cost function__ (agent should use a cost function to reflect its own performance measure).\n\n\n## AIMA Chapter 3.2 Example Problems\n \nFor a grid world (2d rectangular array of cells) with two-cells we can formulate as a search problem as follows:\n\n\n__States__: Agent can be in either of the two cells. The cells can either contain dirt or not. In a world with $n$ cells, we have $n\\cdot 2^n$ states.\n\n\n__Initial state__: Any state can be the initial.\n\n\n__Actions__: Three actions: suck, move left, move right.\n\n\n__Transition model__: Suck removes any dirt, left moves left, right moves right unless hitting a wall.\n\n\n__Goal states__: The states in which every cell is clean.\n\n\n__Action cost__: Each action costs 1. \n\n\nTraveling salesman problem is a touring problem (describe a set of locations that must be visited, rather than a single destination).\n\n\n\n## AIMA Chapter 3.3 Search Algorithms\n \nBest First Search chooses a node $n$ with a minimum value of an evaluation function $f(n)$.\n\n\n$|V|$ = number of vertices (state nodes), $|E|$ = number of edgs (distinct state/action pairs). $d$ = depth or nuber of actions in \nan optimal solution, $m$ = maximum number of actions in any path, $b$ = branching factor, or the number of successors of a node\nthat need to be considered.\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uninformed search has no idea how close a state is to the goal. \n__Uniform cost search__ idea -> spread out in waves of uniform cost (not uniform depth). Complexity is characterized in terms of \n$C^*$, the cost of the optimal solution, and $\\epsilon$, a lower bound on the cost of each action. The worst-case time and space\ncomplexity is $O(b^{1+\\lfloor C^*/\\epsilon \\rfloor})$, which can be much greater than $b^d$. Uniform-cost search is complete and cost-optimal.\n\n\n__Depth-first search__ expands deepest node in the frontier. Implemented usually as tree-like search, does not keep track of reached states.\nDFS is not cost-optimal; it returns the first solution it finds. DFS has much smaller space complexity. A DFS search takes time proportional to the number of states\nand has space complexity of only $O(bm)$, where $b$ is the branching factor and $m$ is the maximum depth of the tree.\n\n\nTo prevent DFS from wandering down an infinite path, we use __depth-limited serach__. We go only to a limit $l$. The time complexity is $O(b^l)$, and space\ncomplexity is $O(bl)$. __Iterative deepening search__ chooses $l$ to be 0, then 1, then 2, ... until a solution is found or we reach failure. The \nspace complexity is $O(bd)$ when there is a solution, or $O(bm)$ where we have no solution. Like BFS, optimal for problems with same cost.\nThe time complexity is $O(b^d)$ when there is solution, or $O(b^m)$ when none.\n\n\n```\nfunction ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure \n  for depth = 0 to ∞ do\n    result←DEPTH-LIMITED-SEARCH(problem,depth) \n    if result ̸= cutoff then return result\n\nfunction DEPTH-LIMITED-SEARCH(problem, l) returns a node or failure or cutoff \n  frontier←a LIFO queue (stack)\n  result ← failure\n  while not IS-EMPTY(frontier) do\n    node←POP(frontier)\n    if problem.IS-GOAL(node.STATE) then return node \n    if DEPTH(node) > l then\n      result ← cutoff\n    else if not IS-CYCLE(node) do\n      for each child in EXPAND(problem, node) do \n        add child to frontier\n  return result\n```\n\n__Bidirectional search__ searches forward from the initial state and backwards from the goal state(s). The motivation for this\nsearch is that $b^{d/2} + b^{d/2}$ is much less than $b^d$. We keep track of two frontiers and two reached sets.\n```\nBFS: Complete, optimal cost, O(b^d) time, O(b^d) space\nUniform-cost: Complete, optimal cost, O(b^{1+(C*/epsilon)} time, O(b^{1+(C*/epsilon)} space\nDepth-first: Not complete, not optimal cost, O(b^m) time, O(bm) space\nDepth-limited: Not complete, not optimal cost, O(b^l) time, O(bl) space\nIterative deepening: Complete, optimal, O(b^d) time, O(bd) space\nBidirectional: Complete, optimal cost, O(b^{d/2}) time, O(b^{d/2}) space\n```\n\n\n## Module 3 Lecture Notes\n\nA reflex agent is one that selects an action based only on the current percept and ignores percept history.\nA problem-solving agent plans ahead. For a task environment that is fully observable, deterministic, known environment, then the solution\nis a fixed sequence of actions. In environments that are partially observable or nondeterministic, then the solution must recommend future actions\ndepending on the percepts it receives.\n\n\nFor the 8-tile puzzle:\n\n\n__States__: configurations of the puzzle (9! configurations)\n\n\n__Actions__: Move one of the movable pieces (<= 4 possible actions)\n\n\n__Performance measure__: minimize the total moves\n\n\nThe __state space__ is the set of all states reachable from the initial state by any sequence of actions.\n\n\nIn __uninformed search__, all non-goal nodes in the frontier look equally good.\n\n\n$b$ = maximum branching factor of search tree. $d$ = depth of the shallowest goal node. $m$ = maximum length of any path in the state space (potentially $\\inf$)\n\n\nIn deciding between DFS and BFS, we should use...\n\n\nDFS: __Space is restricted__, many possible solutions with long paths and wrongs paths can be terminated quickly\n\n\nBFS: __Possible infinite paths__, some solutions have shorter paths, can quickly discard unlikely paths\n\n\nIterative deepening search uses depth-limited search as a subroutine with increasing $l$.\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Path** - a sequence of actions\n* **Abstraction** - removing details from a representation\n* **Search algorithm** - input is search problem and returns a solution\n* **Search tree** - shows paths from initial to hoping to find goal state\n* **Frontier** - the next unexpanded nodes\n* **Graph search** - checks for redundanct paths\n* **Tree search** - does not check for redundant paths\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4bc9f3f3-d3e5-446b-fe8f-9a18710e8411"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "__Greedy best-first search__ expands the node with the lowest $h(n)$ value. The evaluation function $f(n) = h(n)$.\n",
        "This is complete in finite state spaces, but not in infinite ones. The worst-case time and space complexity is $O(|V|)$, but a good\n",
        "heuristic can reduce this complexity substantially (some problems reach $O(bm)$).\n",
        "\\n\n",
        "__A\\* search__ is a best-first search that uses the evaluation function $f(n)=g(n)+h(n)$ where $g(n)$ is the path\n",
        "cost from the initial state to node $n$, and $h(n)$ is the estimated cost of the shortest path from $n$ to the goal state.\n",
        "So then we have $f(n)=$ the estimated cost of the best path that continues from $n$ to a goal. When we extend a path, the $g$ costs should be\n",
        "monotonic (always increasing as you go along a path since action costs are always positive). A\\* search is complete, cost-optimal, and optimally efficient.\n",
        "\\n\n",
        "__Weighted A\\* search__ weighs the heuristic value more heavily, and we have evaluation function $f(n)=g(n)+W\\\\times h(n)$. This is \n",
        "a \"somewhat-greedy\" search.\n",
        "\\n\n",
        "The main nissue with A\\* is its use of memory (that is split between the frontier and visited states).\n",
        "\\n\n",
        "__Beam seach__ limits the size of the frontier by keeping only $k$ nodes with the best $f$-scores.\n",
        "\\n\n",
        "__Iterative deepening A\\* search__, or IDA\\* gives us what iterative-deepening does to DFS. The cutoff is the $f$-cost.\n",
        "\\n\n",
        "__Recursive best-first search__, or RBFS mimics best-first, but only uses linear space. It resembles a recursive depth-first search but uses the $f_limit$ variable\n",
        "to keep track fo the $f$-value of the best alternative path available from any ancestor of the current node. If the current node exceeds the limit, the recursion goes back to the alternative\n",
        "path. RBFS is somewhat more efficient that IDA\\* but it has excessive node generation still. It is optimal if $h(n)$ is admissible.\n",
        "\\n\n",
        "IDA\\* and RBFS suffer from using too little memory! I.e. IDA\\* only maintains a single number: $f$-cost limit. DBFS retains more but only linear space.\n",
        "\\n\n",
        "Bidirectional heuristic uses $f_F(n) = g_F(n) + h_F(n)$ for nodes in the forward direction and $f_B(n) = g_B(n) + h_B(n)$ for nodes in the\n",
        "backward direction.\n",
        " \"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\"\n",
        "For the 15-puzzle, there are 16!/2 states so we need a really good admissible heuristic. Some candidates are:\n",
        "\\n\n",
        "$h_1$: number of misplaced tiles\n",
        "\\n\n",
        "$h_2$: the sum of distances of the tiles from their goal positions. Manhatten distances.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "So far, we've assumed that all moves are equal in cost ($g(N)$ = depth(N) in search tree). But more generally, we should\n",
        "consider a potentially unique cost at each step. For __uniform-cost search__ (UNINFORMED), we expand the node\n",
        "with the lowest path cost by using a frontier that is a priority queue ordered by $g(n)$. With UCS, there could still be\n",
        "a solution on the queue that is less costly.\n",
        "\\n\n",
        "_Greedy best first_ search is exactly UCS with $f(n)$ replacing $g(n)$. And here, we have $f(n)=h(n)$. It is \n",
        "not optimal and not complete.\n",
        "\\n\n",
        "__A\\* search__ is the best known form of best first search. It has $f(n)=g(n)+h(n)$. $h(n)$ must be admissible (never overestimating).\n",
        "\\n\n",
        "A relaxed problem has fewer restrictions on the actions than the original. $h_{oop}$ for 8-tile puzzle where tile can move anywhere (out of place),\n",
        "$h_{md}$ for 8-tile puzzle where a tile can move to any adjacent square (manhatten distance).\n",
        "\\n\n",
        "If $h_2(n) \\geq h_1(n)$ for all $n$ then $h_2$ __dominates__ $h_1$. $h_2$ is more accurate than $h_1$. $h*(n)$ is the Oracle heuristic, or the true distance from the root to $n$.\n",
        "\\n\n",
        "__Summary:__\n",
        "\\n\n",
        "__Uniform cost search__: $f(n)=g(n)$\n",
        "\\n\n",
        "__Greedy best first search__: $f(n) = h(n)$\n",
        "\\n\n",
        "__A\\* search__: $f(n) = g(n)+h(n)$\n",
        "\n",
        "```\n",
        "function BEST-FIRST-SEARCH(problem, f ) returns a solution node or failure node←NODE(STATE=problem.INITIAL)\n",
        "  frontier ← a priority queue ordered by f , with node as an element\n",
        "  reached←a lookup table, with one entry with key problem.INITIAL and value node \n",
        "  while not IS-EMPTY(frontier) do\n",
        "    node←POP(frontier)\n",
        "    if problem.IS-GOAL(node.STATE) then return node \n",
        "      for each child in EXPAND(problem, node) do\n",
        "        s←child.STATE\n",
        "        if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n",
        "          reached[s] ← child\n",
        "          add child to frontier return failure\n",
        "\n",
        "function EXPAND(problem,node) yields nodes\n",
        "  s←node.STATE\n",
        "  for each action in problem.ACTIONS(s) do\n",
        "    s′ ←problem.RESULT(s,action)\n",
        "    cost←node.PATH-COST + problem.ACTION-COST(s,action,s′)\n",
        "    yield NODE(STATE=s′, PARENT=node, ACTION=action, PATH-COST=cost)\n",
        "\n",
        "```\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"uses hints about location of goal(s) to find the solution more efficiently\",\n",
        "\"heuristic function\" : \"estimated cost of path\",\n",
        "\"satisficing\" : \"solutions that are suboptimal but 'good enough'\",\n",
        "\"relaxed problem\" : \"fewer restrictions than on the og problem\"\n",
        "}\n",
        "\n",
        "length = len(chapter3_5.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)))\n"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 333 words long, so you could write an additional 167 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0633cb8e-d047-4f17-fc57-e7cb312d7d43"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n__Greedy best-first search__ expands the node with the lowest $h(n)$ value. The evaluation function $f(n) = h(n)$.\nThis is complete in finite state spaces, but not in infinite ones. The worst-case time and space complexity is $O(|V|)$, but a good\nheuristic can reduce this complexity substantially (some problems reach $O(bm)$).\n\n\n__A\\* search__ is a best-first search that uses the evaluation function $f(n)=g(n)+h(n)$ where $g(n)$ is the path\ncost from the initial state to node $n$, and $h(n)$ is the estimated cost of the shortest path from $n$ to the goal state.\nSo then we have $f(n)=$ the estimated cost of the best path that continues from $n$ to a goal. When we extend a path, the $g$ costs should be\nmonotonic (always increasing as you go along a path since action costs are always positive). A\\* search is complete, cost-optimal, and optimally efficient.\n\n\n__Weighted A\\* search__ weighs the heuristic value more heavily, and we have evaluation function $f(n)=g(n)+W\\times h(n)$. This is \na \"somewhat-greedy\" search.\n\n\nThe main nissue with A\\* is its use of memory (that is split between the frontier and visited states).\n\n\n__Beam seach__ limits the size of the frontier by keeping only $k$ nodes with the best $f$-scores.\n\n\n__Iterative deepening A\\* search__, or IDA\\* gives us what iterative-deepening does to DFS. The cutoff is the $f$-cost.\n\n\n__Recursive best-first search__, or RBFS mimics best-first, but only uses linear space. It resembles a recursive depth-first search but uses the $f_limit$ variable\nto keep track fo the $f$-value of the best alternative path available from any ancestor of the current node. If the current node exceeds the limit, the recursion goes back to the alternative\npath. RBFS is somewhat more efficient that IDA\\* but it has excessive node generation still. It is optimal if $h(n)$ is admissible.\n\n\nIDA\\* and RBFS suffer from using too little memory! I.e. IDA\\* only maintains a single number: $f$-cost limit. DBFS retains more but only linear space.\n\n\nBidirectional heuristic uses $f_F(n) = g_F(n) + h_F(n)$ for nodes in the forward direction and $f_B(n) = g_B(n) + h_B(n)$ for nodes in the\nbackward direction.\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n\nFor the 15-puzzle, there are 16!/2 states so we need a really good admissible heuristic. Some candidates are:\n\n\n$h_1$: number of misplaced tiles\n\n\n$h_2$: the sum of distances of the tiles from their goal positions. Manhatten distances.\n\n\n## Module 4 Lecture Notes\n\nSo far, we've assumed that all moves are equal in cost ($g(N)$ = depth(N) in search tree). But more generally, we should\nconsider a potentially unique cost at each step. For __uniform-cost search__ (UNINFORMED), we expand the node\nwith the lowest path cost by using a frontier that is a priority queue ordered by $g(n)$. With UCS, there could still be\na solution on the queue that is less costly.\n\n\n_Greedy best first_ search is exactly UCS with $f(n)$ replacing $g(n)$. And here, we have $f(n)=h(n)$. It is \nnot optimal and not complete.\n\n\n__A\\* search__ is the best known form of best first search. It has $f(n)=g(n)+h(n)$. $h(n)$ must be admissible (never overestimating).\n\n\nA relaxed problem has fewer restrictions on the actions than the original. $h_{oop}$ for 8-tile puzzle where tile can move anywhere (out of place),\n$h_{md}$ for 8-tile puzzle where a tile can move to any adjacent square (manhatten distance).\n\n\nIf $h_2(n) \\geq h_1(n)$ for all $n$ then $h_2$ __dominates__ $h_1$. $h_2$ is more accurate than $h_1$. $h*(n)$ is the Oracle heuristic, or the true distance from the root to $n$.\n\n\n__Summary:__\n\n\n__Uniform cost search__: $f(n)=g(n)$\n\n\n__Greedy best first search__: $f(n) = h(n)$\n\n\n__A\\* search__: $f(n) = g(n)+h(n)$\n\n```\nfunction BEST-FIRST-SEARCH(problem, f ) returns a solution node or failure node←NODE(STATE=problem.INITIAL)\n  frontier ← a priority queue ordered by f , with node as an element\n  reached←a lookup table, with one entry with key problem.INITIAL and value node \n  while not IS-EMPTY(frontier) do\n    node←POP(frontier)\n    if problem.IS-GOAL(node.STATE) then return node \n      for each child in EXPAND(problem, node) do\n        s←child.STATE\n        if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n          reached[s] ← child\n          add child to frontier return failure\n\nfunction EXPAND(problem,node) yields nodes\n  s←node.STATE\n  for each action in problem.ACTIONS(s) do\n    s′ ←problem.RESULT(s,action)\n    cost←node.PATH-COST + problem.ACTION-COST(s,action,s′)\n    yield NODE(STATE=s′, PARENT=node, ACTION=action, PATH-COST=cost)\n\n```\n\n \n\n## Module 4 Definitions\n* **Informed search** - uses hints about location of goal(s) to find the solution more efficiently\n* **Heuristic function** - estimated cost of path\n* **Satisficing** - solutions that are suboptimal but 'good enough'\n* **Relaxed problem** - fewer restrictions than on the og problem\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "Most commonnly studied games are perfect information, zero-sum games. These are fully observable, no win-win outcome games.\n",
        "We call the two players MAX and MIN. A game can be defined as follows:\n",
        "\\n\n",
        "$S_0$: The __initial state__\n",
        "\\n\n",
        "The player whose turn it is to move in state $s$\n",
        "\\n\n",
        "The set of legal moves in state $s$\n",
        "\\n\n",
        "The __transition model__ that defines the result from taking action $a$ from state $s$\n",
        "\\n\n",
        "A __terminal test__ to see if the game is over\n",
        "\\n\n",
        "A __utility function__ that defines a numeric value to the player when the game ends in terminal state $s$.\n",
        "\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "MAX's strategy is contingent on MIN. We can use __minimax search__.\n",
        "\\n\n",
        "The __minimax value__ is the utility for MAX in that state (assuming both players play optimally).\n",
        "\\n\n",
        "The time complexity of minimax is $O(b^m)$. The space complexity is $O(bm)$ if we have an algorithm that generates all actions\n",
        "at once or $O(m)$ for an algorithm that generates actions one at a time.\n",
        "\\n\n",
        "For multiplayer games, we must consider nonterminal states. For each state, we have a vector of values that describe\n",
        "the utilities for each player. If a player is going to reach a terminal state, they look at the best possible value that they can\n",
        "get out of the choices for the terminal states.\n",
        "\\n\n",
        "With __alpha-beta pruning__ we can remove large parts of the tree that make no difference to the outcome.\n",
        "$$\\\\alpha = \\\\text{the value of the best (i.e. highest-value) choice we have found so far at any choice point along the path for MAX}$$\n",
        "$$\\\\beta = \\\\text{the value of the best (i.e. lowest-value) choice we have found so far at any choice point along the path for MIN}$$\n",
        "\n",
        "```\n",
        "function MINIMAX-SEARCH(game, state) returns an action \n",
        "  player←game.TO-MOVE(state)\n",
        "  value, move←MAX-VALUE(game, state)\n",
        "  return move\n",
        "\n",
        "function MAX-VALUE(game, state) returns a (utility, move) pair\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n",
        "    v←−∞\n",
        "    for each a in game.ACTIONS(state) do\n",
        "      v2, a2←MIN-VALUE(game, game.RESULT(state, a)) \n",
        "      if v2 > v then\n",
        "        v, move←v2, a \n",
        "    return v, move\n",
        "\n",
        "function MIN-VALUE(game, state) returns a (utility, move) pair\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n",
        "    v←+∞\n",
        "    for each a in game.ACTIONS(state) do\n",
        "      v2, a2←MAX-VALUE(game, game.RESULT(state, a)) \n",
        "      if v2 < v then\n",
        "        v, move←v2, a \n",
        "    return v, move\n",
        "\n",
        "```\n",
        "__Alpha-beta pruning algorithm:__\n",
        "```\n",
        "function ALPHA-BETA-SEARCH(game, state) returns an action player←game.TO-MOVE(state)\n",
        "  value, move←MAX-VALUE(game, state,−∞,+∞)\n",
        "  return move\n",
        "\n",
        "function MAX-VALUE(game, state, α, β) returns a (utility, move) pair\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null v←−∞\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2, a2←MIN-VALUE(game, game.RESULT(state, a),α,β) \n",
        "    if v2 > v then\n",
        "      v, move←v2, a\n",
        "      α←MAX(α, v)\n",
        "    if v ≥ β then return v, move\n",
        "  return v, move\n",
        "\n",
        "function MIN-VALUE(game, state, α, β) returns a (utility, move) pair\n",
        "  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null v←+∞\n",
        "  for each a in game.ACTIONS(state) do\n",
        "    v2, a2←MAX-VALUE(game, game.RESULT(state, a),α,β) \n",
        "    if v2 < v then\n",
        "      v, move←v2, a\n",
        "      β←MIN(β, v)\n",
        "    if v ≤ α then return v, move\n",
        "  return v, move\n",
        "```\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "chapter5_3 = \"\"\" To make use of limited computation time, we can cut off the search early an apply a heuristic evaluation function to states.\n",
        "This replaces the utility function with Eval and the terminal test with a cutoff test (returns True for terminal states) that decides\n",
        "when to cut off the search. In alpha-beta search pseudocode, we check if the game is at cutoff and then return the Eval at that state (instead\n",
        "of checking if we are at a terminal state and then returning the utility).\n",
        "\\n\n",
        "With __beam search__, on each ply we only consider the $n$ best moves. This is dangerous because the best move may be pruned away.\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Backgammon is a stochastic game that combines luck and skill. For stochastic nodes, we must include __chance nodes__ in addition to MAX and MIN\n",
        "nodes. \n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" N/A \"\"\"\n",
        "chapter16_2 = \"\"\" N/A \"\"\"\n",
        "chapter16_3 = \"\"\" N/A \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Evaluation functions $f(n)$ evaluates how good a board position is based on static features onf that board alone.\n",
        "\\n\n",
        "$f(n)>0$ if MAX is winning in position $n$\n",
        "\\n\n",
        "$f(n)=0$ if tied\n",
        "\\n\n",
        "$f(n)<0$ if MIN is winning in position $n$.\n",
        "\\n\n",
        "For tic-tac-toe, $f(n)$ = $ of 3 lengths open for MAX - # of 3 lengths open for MIN.\n",
        "\\n\n",
        "The Minimax procedure is as follows:\n",
        "\\n\n",
        "1. Start with the current position as MAX node\n",
        "\\n\n",
        "2. Expand the game tree a fixed number of ply\n",
        "\\n\n",
        "3. Apply the evaluation function to the leaf positions.\n",
        "\\n\n",
        "4. Calculate back-up values bottom-up.\n",
        "\\n\n",
        "5. Pick the move assigned to MAX at the root.\n",
        "\\n\n",
        "6. Wait for MIN to respond.\n",
        "\\n\n",
        "In __minimax search__, we have a state-space search tree, players alternate turns, and we compute each node's __minimax value__ (best achievable utility against a rational adversary).\n",
        "For alpha-beta pruning, we realize that MAX will never allow a move that could lead to a worse score (for MAX) than $\\\\alpha$. Similarly, MIN will never\n",
        "allow a move that could lead to a better score (for MAX) than $\\\\beta$. Thus, we stop evaluating a branch whenever:\n",
        "\\n\n",
        "- When evaluating a MAX node: a value $v \\\\geq \\\\beta$ is backed-up because MIN will never select that MAX node.\n",
        "\\n\n",
        "- When evaluating a MIN node: a value $v \\\\leq \\\\alpha$ is found because MAX will never select that MIN node.\n",
        "\\n\n",
        "__Expectimax__ considers games that are controlled by chance and not an adversary. Here, we have the following:\n",
        "\\n\n",
        "- MAX nodes like in minimax search\n",
        "- Chance nodes are like MIN nodes but the outcome is uncertain\n",
        "- Calculate expected utilities, i.e. weighted average of children\n",
        "\\n\n",
        "We can't use alpha-beta pruning as before since we are doing an average. There are probabilities so we can't be certain.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"perfect infomration, zero-sum games\" : \"fully-observable and no 'win-win' outcomes\",   \n",
        "\"state space graph\" : \"vertices = states, edges = moves\",\n",
        "\"game tree\" : \"search tree that follows every sequence to a terminal state\",\n",
        "\"ply\" : \"move from one player to the next, one level down in the tree\",\n",
        "\"minimax decision\" : \"the best choice for MAX\",\n",
        "\"heuristic evaluation function\" : \"estimates the expected utility of a state\",\n",
        "\"forward pruning\" : \"eliminates moves that seem bad but may be good ones\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ca35e37d-3b48-47aa-9969-2d890b7ef57a"
      },
      "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": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nMost commonnly studied games are perfect information, zero-sum games. These are fully observable, no win-win outcome games.\nWe call the two players MAX and MIN. A game can be defined as follows:\n\n\n$S_0$: The __initial state__\n\n\nThe player whose turn it is to move in state $s$\n\n\nThe set of legal moves in state $s$\n\n\nThe __transition model__ that defines the result from taking action $a$ from state $s$\n\n\nA __terminal test__ to see if the game is over\n\n\nA __utility function__ that defines a numeric value to the player when the game ends in terminal state $s$.\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nMAX's strategy is contingent on MIN. We can use __minimax search__.\n\n\nThe __minimax value__ is the utility for MAX in that state (assuming both players play optimally).\n\n\nThe time complexity of minimax is $O(b^m)$. The space complexity is $O(bm)$ if we have an algorithm that generates all actions\nat once or $O(m)$ for an algorithm that generates actions one at a time.\n\n\nFor multiplayer games, we must consider nonterminal states. For each state, we have a vector of values that describe\nthe utilities for each player. If a player is going to reach a terminal state, they look at the best possible value that they can\nget out of the choices for the terminal states.\n\n\nWith __alpha-beta pruning__ we can remove large parts of the tree that make no difference to the outcome.\n$$\\alpha = \\text{the value of the best (i.e. highest-value) choice we have found so far at any choice point along the path for MAX}$$\n$$\\beta = \\text{the value of the best (i.e. lowest-value) choice we have found so far at any choice point along the path for MIN}$$\n\n```\nfunction MINIMAX-SEARCH(game, state) returns an action \n  player←game.TO-MOVE(state)\n  value, move←MAX-VALUE(game, state)\n  return move\n\nfunction MAX-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n    v←−∞\n    for each a in game.ACTIONS(state) do\n      v2, a2←MIN-VALUE(game, game.RESULT(state, a)) \n      if v2 > v then\n        v, move←v2, a \n    return v, move\n\nfunction MIN-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n    v←+∞\n    for each a in game.ACTIONS(state) do\n      v2, a2←MAX-VALUE(game, game.RESULT(state, a)) \n      if v2 < v then\n        v, move←v2, a \n    return v, move\n\n```\n__Alpha-beta pruning algorithm:__\n```\nfunction ALPHA-BETA-SEARCH(game, state) returns an action player←game.TO-MOVE(state)\n  value, move←MAX-VALUE(game, state,−∞,+∞)\n  return move\n\nfunction MAX-VALUE(game, state, α, β) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null v←−∞\n  for each a in game.ACTIONS(state) do\n    v2, a2←MIN-VALUE(game, game.RESULT(state, a),α,β) \n    if v2 > v then\n      v, move←v2, a\n      α←MAX(α, v)\n    if v ≥ β then return v, move\n  return v, move\n\nfunction MIN-VALUE(game, state, α, β) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null v←+∞\n  for each a in game.ACTIONS(state) do\n    v2, a2←MAX-VALUE(game, game.RESULT(state, a),α,β) \n    if v2 < v then\n      v, move←v2, a\n      β←MIN(β, v)\n    if v ≤ α then return v, move\n  return v, move\n```\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n To make use of limited computation time, we can cut off the search early an apply a heuristic evaluation function to states.\nThis replaces the utility function with Eval and the terminal test with a cutoff test (returns True for terminal states) that decides\nwhen to cut off the search. In alpha-beta search pseudocode, we check if the game is at cutoff and then return the Eval at that state (instead\nof checking if we are at a terminal state and then returning the utility).\n\n\nWith __beam search__, on each ply we only consider the $n$ best moves. This is dangerous because the best move may be pruned away.\n \n\n## AIMA Chapter 5.5 Stochastic Games\n\nBackgammon is a stochastic game that combines luck and skill. For stochastic nodes, we must include __chance nodes__ in addition to MAX and MIN\nnodes. \n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n N/A \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n N/A \n\n## AIMA Chapter 16.3 Utility Functions\n N/A \n\n## Module 5 Lecture Notes\n\nEvaluation functions $f(n)$ evaluates how good a board position is based on static features onf that board alone.\n\n\n$f(n)>0$ if MAX is winning in position $n$\n\n\n$f(n)=0$ if tied\n\n\n$f(n)<0$ if MIN is winning in position $n$.\n\n\nFor tic-tac-toe, $f(n)$ = $ of 3 lengths open for MAX - # of 3 lengths open for MIN.\n\n\nThe Minimax procedure is as follows:\n\n\n1. Start with the current position as MAX node\n\n\n2. Expand the game tree a fixed number of ply\n\n\n3. Apply the evaluation function to the leaf positions.\n\n\n4. Calculate back-up values bottom-up.\n\n\n5. Pick the move assigned to MAX at the root.\n\n\n6. Wait for MIN to respond.\n\n\nIn __minimax search__, we have a state-space search tree, players alternate turns, and we compute each node's __minimax value__ (best achievable utility against a rational adversary).\nFor alpha-beta pruning, we realize that MAX will never allow a move that could lead to a worse score (for MAX) than $\\alpha$. Similarly, MIN will never\nallow a move that could lead to a better score (for MAX) than $\\beta$. Thus, we stop evaluating a branch whenever:\n\n\n- When evaluating a MAX node: a value $v \\geq \\beta$ is backed-up because MIN will never select that MAX node.\n\n\n- When evaluating a MIN node: a value $v \\leq \\alpha$ is found because MAX will never select that MIN node.\n\n\n__Expectimax__ considers games that are controlled by chance and not an adversary. Here, we have the following:\n\n\n- MAX nodes like in minimax search\n- Chance nodes are like MIN nodes but the outcome is uncertain\n- Calculate expected utilities, i.e. weighted average of children\n\n\nWe can't use alpha-beta pruning as before since we are doing an average. There are probabilities so we can't be certain.\n\n\n## Module 5 Definitions\n* **Perfect infomration, zero-sum games** - fully-observable and no 'win-win' outcomes\n* **State space graph** - vertices = states, edges = moves\n* **Game tree** - search tree that follows every sequence to a terminal state\n* **Ply** - move from one player to the next, one level down in the tree\n* **Minimax decision** - the best choice for MAX\n* **Heuristic evaluation function** - estimates the expected utility of a state\n* **Forward pruning** - eliminates moves that seem bad but may be good ones\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "A constraint satisfaction problem consists of:\n",
        "\\n\n",
        "- $\\\\Chi$, a set of variables\n",
        "\\n\n",
        "- $D$, a set of domains, one for each variable, specifying allowable values for the variable\n",
        "\\n\n",
        "- $C$, a set of constraints that specify the allowable combinations of values\n",
        "\\n\n",
        "CSPs deal with __assignments__ of values to variables. The simplest kind of CSPs have discrete, finite domains. \n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "We often talk about __arc consistency__,\n",
        "or if every value in a variable's domain satisfies the variable's binary constraints. __AC-3__ enforces arc-consistency.\n",
        "First, AC-3 maintains a queue of arcs to consider (all of them at first), and then pops off an arbitrary arc $(X_i, X_j)$ and makes $X_i$ arc consistent\n",
        "with respect to $X_j$. If it changes, we add all arcs $(X_k, X_i)$ where $X_k$ is a neighbor of $X_i$. With a CSP of $n$ variables each with domain size of at most $d$, and with $c$\n",
        "binary constraints (arc), we have $O(cd^3)$, since each arc can only be inserted in the queue at most $d$ times because $X_i$ has at most $d$ values to delete.\\n\n",
        "```\n",
        "function AC-3(csp) returns false if an inconsistency is found and true otherwise \n",
        "  queue ← a queue of arcs, initially all the arcs in csp\n",
        "  while queue is not empty do (Xi, Xj)←POP(queue)\n",
        "    if REVISE(csp, Xi, Xj) then\n",
        "      if size of Di = 0 then return false\n",
        "      for each Xk in Xi.NEIGHBORS - {Xj} do\n",
        "        add (Xk, Xi) to queue \n",
        "  return true\n",
        "\n",
        "function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi \n",
        "  revised ← false\n",
        "  for each x in Di do\n",
        "    if no value y in D j allows (x,y) to satisfy the constraint between Xi and X j then \n",
        "      delete x from Di\n",
        "      revised ← true\n",
        "  return revised\n",
        "```\n",
        "\n",
        "\\n\n",
        "__Path consistency__ tightens binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n",
        "$\\\\{X_i, X_j\\\\}$ is path consistent with respect to $X_m$ if, for every assignment $\\\\{X_i=a, X_j=b\\\\}$ consistent with the constaints on $\\\\{X_i, X_j\\\\}$, there is\n",
        "an assignment to $X_m$ that satisfies the constraints on $\\\\{X_i, X_m\\\\}$ and $\\\\{X_m, X_j\\\\}$.\n",
        "\\n\n",
        "__$k$-consistency__refers to for any set of $k-1$ variables, a consistent value can always be assigned to any $k$th variable.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "When we finish the constraint propagations and still have variables that can take on multiple values, we must now search for a solution.\n",
        "One form of inference is called __forward checking__. When $X$ is assigned, we establish arc consistency for it (for each variable that is connected to $X$\n",
        "by a constraint, delete from that variable any value that is inconsistent with the value chosen for $X$).\n",
        "\\n\n",
        "__Maintaining Arc Consistency__ MAC algorithm etects inconsistencies using AC-3 but instead of a queue with all of the arcs in the CSP, we start with only\n",
        "$(X_j, X_i)$ for all $X_j$ that are unassigned variables that are neightbors of $X_i$.\n",
        "\\n\n",
        "With __chronological backtracking__, we back up to the preceding variable and try a different value for it (when a branch of the search fails).\n",
        "\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" N/A \"\"\"\n",
        "chapter6_5 = \"\"\" We can reduce a constraint graph by __cutset conditioning__.\n",
        "\\n\n",
        "1.Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset.\n",
        "\\n\n",
        "2. For each possible assignment to the variables in S that satisfies all constraints on S, (a) remove from the domains of the remaining variables any values that are inconsis- tent with the assignment for S, and\n",
        "(b) if the remaining CSP has a solution, return it together with the assignment for S.\n",
        "\\n\n",
        "Another way to reduce is by __tree decomposition__, or a transformation of the og graph to a tree where each node consists of a set of variables.\n",
        "It must satisfy:\n",
        "\\n\n",
        "- Every variable in the original problem appears in at least one of the tree nodes.\n",
        "\\n\n",
        "- If two variables are connected by a constraint in the original problem, they must appear\n",
        "together (along with the constraint) in at least one of the tree nodes.\n",
        "\\n\n",
        "- If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "Benefits of CSP:\n",
        "\\n\n",
        "- Clean specification of many problems, generic goal, successor function, and heuristics\n",
        "\\n\n",
        "- CSP knows which variables violate a constraint\n",
        "\\n\n",
        "- CSPs prune off branches that violate constraints\n",
        "\\n\n",
        "__Unary__ constraints involve a single variable, __binary__ constraints involve pairs, __higher-order__ constraints involve 3 or more.\n",
        "__Preference__ constraints are what they sound like, could be represented by a cost for each variable assignment.\n",
        "We can model CSPs as a search problem. We have $n$ variables of domain size $d$. So the branching factor at the root is $n\\\\times d$. The branching factor at the next level is\n",
        "$(n-1)\\\\times d$. The tree has $n!d^n$ leaves.\n",
        "\\n\n",
        "Depth-first search for CSPs with single-variable assignments is called __backtracking__ search., it is the basic __uninformed__ algorithm for CSPs. We can improve with different heuristics.\n",
        "\\n\n",
        "__Heuristic 1: Most constrained variable__. Choose a variable with the fewest legal moves (__minimum remaining values MRV heuristic__). This is also called the Fast Fail method.\n",
        "\\n\n",
        "__Heuristic 2: Most constraining variable__. Tie-breaker among most contrained variables. Choose the variable with the most constraints on the reamining variables.\n",
        "\\n\n",
        "__Heuristic 3: Least constraining value__. Given a variable, choose the least constraining value (the one that rules out the fewest values in the reamining variables).\n",
        "\\n\n",
        "__Heuristic 4: Forward checking__. Keep track of reamining legal values for unassigned variables.\n",
        "\\n\n",
        "Forward checking propagates info, but doesn't provide early failure detection. __Constraint propagation__ goes beyond forward checking and repeatedly enforces constraints locally.\n",
        "Constraint propagation (inference!) eliminates possible values for a variable. __Arc consistency__ satisfies binary constraints. In a constraint graph, nodes are variables and edges are constraints.\n",
        "For a pair of nodes that are constrained, we represent the graph as two directed arcs that connect them.\n",
        "\\n\n",
        "The __Waltz/Mackworth Constraint Propagaation Algorithm__:\n",
        "\\n\n",
        "1. Assign every node in the constraint graph a set of all possible values\n",
        "\\n\n",
        "2. Repeat until there is no change in the set of values associated with any node:\n",
        "\\n\n",
        "3. For each node $i$, for each neighboring node $j$, remove any value from $i$ which is not arc consistent with $j$\n",
        "\\n\n",
        "We get to __AC-3__ by addressing the inconsistencies. Namely, at each iteration, we only need to examine those $X_i$ where at least one neighbor of $X_i$\n",
        "has lost a value and removing a value on $X_i$ can only make $Y_j$ arc-inconsistent with respect to $X_i$ itself. Thus we only need to check that $(j,i)$ is still arc consistent.\n",
        "\\n\n",
        "Time complexity of AC-3:\n",
        "\\n\n",
        "- All nodes can be connected to every other node, $O(n^2)$ arcs\n",
        "\\n\n",
        "- If there are $d$ values, checking each arc takes $O(d^2)$\n",
        "\\n\n",
        "- Each arc can only be inserted into the queue $d$ times\n",
        "\\n\n",
        "The time complexity is $O(n^2d^3)$.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"complete assignment\" : \"every variable has an assignment\",   \n",
        "\"solution\" : \"a consistent and complete assignment for a CSP\",\n",
        "\"precedence constraints\" : \"one task must happen before another\",\n",
        "\"disjunctive constraint\" : \"one task must not overlap in time with another\",\n",
        "\"binary constraint\" : \"relating two different variables\",\n",
        "\"global constraint\" : \"relating arbitrary number of variables\",\n",
        "\"constraint propagation\" : \"reducing the number of possible moves by using the constraints\",\n",
        "\"arc consistent\" : \"every value in a variable's domain satisfies the variable's binary constraints\",\n",
        "\"minimum remaining values (MRV) heuristic\" : \"choosing the variable with the fewest possible values\",\n",
        "\"min-conflicts heuristic\" : \"select value that results in least conflicts with other variables\"\n",
        "}\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "40azaKeqbk7u"
      },
      "source": [
        ""
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "685d6343-86c7-4fec-8a73-cd68338047c1"
      },
      "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": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nA constraint satisfaction problem consists of:\n\n\n- $\\Chi$, a set of variables\n\n\n- $D$, a set of domains, one for each variable, specifying allowable values for the variable\n\n\n- $C$, a set of constraints that specify the allowable combinations of values\n\n\nCSPs deal with __assignments__ of values to variables. The simplest kind of CSPs have discrete, finite domains. \n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nWe often talk about __arc consistency__,\nor if every value in a variable's domain satisfies the variable's binary constraints. __AC-3__ enforces arc-consistency.\nFirst, AC-3 maintains a queue of arcs to consider (all of them at first), and then pops off an arbitrary arc $(X_i, X_j)$ and makes $X_i$ arc consistent\nwith respect to $X_j$. If it changes, we add all arcs $(X_k, X_i)$ where $X_k$ is a neighbor of $X_i$. With a CSP of $n$ variables each with domain size of at most $d$, and with $c$\nbinary constraints (arc), we have $O(cd^3)$, since each arc can only be inserted in the queue at most $d$ times because $X_i$ has at most $d$ values to delete.\n\n```\nfunction AC-3(csp) returns false if an inconsistency is found and true otherwise \n  queue ← a queue of arcs, initially all the arcs in csp\n  while queue is not empty do (Xi, Xj)←POP(queue)\n    if REVISE(csp, Xi, Xj) then\n      if size of Di = 0 then return false\n      for each Xk in Xi.NEIGHBORS - {Xj} do\n        add (Xk, Xi) to queue \n  return true\n\nfunction REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi \n  revised ← false\n  for each x in Di do\n    if no value y in D j allows (x,y) to satisfy the constraint between Xi and X j then \n      delete x from Di\n      revised ← true\n  return revised\n```\n\n\n\n__Path consistency__ tightens binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n$\\{X_i, X_j\\}$ is path consistent with respect to $X_m$ if, for every assignment $\\{X_i=a, X_j=b\\}$ consistent with the constaints on $\\{X_i, X_j\\}$, there is\nan assignment to $X_m$ that satisfies the constraints on $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$.\n\n\n__$k$-consistency__refers to for any set of $k-1$ variables, a consistent value can always be assigned to any $k$th variable.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nWhen we finish the constraint propagations and still have variables that can take on multiple values, we must now search for a solution.\nOne form of inference is called __forward checking__. When $X$ is assigned, we establish arc consistency for it (for each variable that is connected to $X$\nby a constraint, delete from that variable any value that is inconsistent with the value chosen for $X$).\n\n\n__Maintaining Arc Consistency__ MAC algorithm etects inconsistencies using AC-3 but instead of a queue with all of the arcs in the CSP, we start with only\n$(X_j, X_i)$ for all $X_j$ that are unassigned variables that are neightbors of $X_i$.\n\n\nWith __chronological backtracking__, we back up to the preceding variable and try a different value for it (when a branch of the search fails).\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n N/A \n\n## AIMA Chapter 6.5 The Structure of Problems\n We can reduce a constraint graph by __cutset conditioning__.\n\n\n1.Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset.\n\n\n2. For each possible assignment to the variables in S that satisfies all constraints on S, (a) remove from the domains of the remaining variables any values that are inconsis- tent with the assignment for S, and\n(b) if the remaining CSP has a solution, return it together with the assignment for S.\n\n\nAnother way to reduce is by __tree decomposition__, or a transformation of the og graph to a tree where each node consists of a set of variables.\nIt must satisfy:\n\n\n- Every variable in the original problem appears in at least one of the tree nodes.\n\n\n- If two variables are connected by a constraint in the original problem, they must appear\ntogether (along with the constraint) in at least one of the tree nodes.\n\n\n- If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes.\n \n\n## Module 6 Lecture Notes\n\nBenefits of CSP:\n\n\n- Clean specification of many problems, generic goal, successor function, and heuristics\n\n\n- CSP knows which variables violate a constraint\n\n\n- CSPs prune off branches that violate constraints\n\n\n__Unary__ constraints involve a single variable, __binary__ constraints involve pairs, __higher-order__ constraints involve 3 or more.\n__Preference__ constraints are what they sound like, could be represented by a cost for each variable assignment.\nWe can model CSPs as a search problem. We have $n$ variables of domain size $d$. So the branching factor at the root is $n\\times d$. The branching factor at the next level is\n$(n-1)\\times d$. The tree has $n!d^n$ leaves.\n\n\nDepth-first search for CSPs with single-variable assignments is called __backtracking__ search., it is the basic __uninformed__ algorithm for CSPs. We can improve with different heuristics.\n\n\n__Heuristic 1: Most constrained variable__. Choose a variable with the fewest legal moves (__minimum remaining values MRV heuristic__). This is also called the Fast Fail method.\n\n\n__Heuristic 2: Most constraining variable__. Tie-breaker among most contrained variables. Choose the variable with the most constraints on the reamining variables.\n\n\n__Heuristic 3: Least constraining value__. Given a variable, choose the least constraining value (the one that rules out the fewest values in the reamining variables).\n\n\n__Heuristic 4: Forward checking__. Keep track of reamining legal values for unassigned variables.\n\n\nForward checking propagates info, but doesn't provide early failure detection. __Constraint propagation__ goes beyond forward checking and repeatedly enforces constraints locally.\nConstraint propagation (inference!) eliminates possible values for a variable. __Arc consistency__ satisfies binary constraints. In a constraint graph, nodes are variables and edges are constraints.\nFor a pair of nodes that are constrained, we represent the graph as two directed arcs that connect them.\n\n\nThe __Waltz/Mackworth Constraint Propagaation Algorithm__:\n\n\n1. Assign every node in the constraint graph a set of all possible values\n\n\n2. Repeat until there is no change in the set of values associated with any node:\n\n\n3. For each node $i$, for each neighboring node $j$, remove any value from $i$ which is not arc consistent with $j$\n\n\nWe get to __AC-3__ by addressing the inconsistencies. Namely, at each iteration, we only need to examine those $X_i$ where at least one neighbor of $X_i$\nhas lost a value and removing a value on $X_i$ can only make $Y_j$ arc-inconsistent with respect to $X_i$ itself. Thus we only need to check that $(j,i)$ is still arc consistent.\n\n\nTime complexity of AC-3:\n\n\n- All nodes can be connected to every other node, $O(n^2)$ arcs\n\n\n- If there are $d$ values, checking each arc takes $O(d^2)$\n\n\n- Each arc can only be inserted into the queue $d$ times\n\n\nThe time complexity is $O(n^2d^3)$.\n \n\n## Module 6 Definitions\n* **Complete assignment** - every variable has an assignment\n* **Solution** - a consistent and complete assignment for a CSP\n* **Precedence constraints** - one task must happen before another\n* **Disjunctive constraint** - one task must not overlap in time with another\n* **Binary constraint** - relating two different variables\n* **Global constraint** - relating arbitrary number of variables\n* **Constraint propagation** - reducing the number of possible moves by using the constraints\n* **Arc consistent** - every value in a variable's domain satisfies the variable's binary constraints\n* **Minimum remaining values (mrv) heuristic** - choosing the variable with the fewest possible values\n* **Min-conflicts heuristic** - select value that results in least conflicts with other 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 = \"\"\" N/A \"\"\"\n",
        "chapter7_2 = \"\"\" N/A \"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "Entailment is when a sentence follows logically from a nother sentence, and we write it as $\\\\alpha \\\\models \\\\beta$. $M(\\\\alpha)$ is the set of all models of $\\\\alpha$. We can also write\n",
        "$$\\\\alpha \\\\models \\\\beta iff M(\\\\alpha) \\\\subseteq M(\\\\beta)$$\n",
        "Note that $\\\\alpha$ is a stronger assertion than $\\\\beta$.\n",
        "\\n\n",
        "If KB is true in the real world, then any sentence $\\\\alpha$ derived from KB by a sound inference procedure is also true in the real world.\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "¬ (not). A sentence such as ¬W1,3 is called the negation of W1,3. A literal is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal).\n",
        "\\n\n",
        "∧ (and). A sentence whose main connective is ∧, such as W1,3 ∧ P3,1 , is called a conjunction.\n",
        "\\n\n",
        "∨ (or). A sentence whose main connective is ∨, such as (W1,3 ∧P3,1)∨W2,2, is a disjunction.\n",
        "\\n\n",
        "⇒ (implies). A sentence such as (W1,3 ∧ P3,1) ⇒ ¬W2,2 is called an implication (or conditional). Its premise or antecedent is (W1,3 ∧ P3,1), and its conclusion or consequent is ¬W2,2.\n",
        "\\n\n",
        "⇔ (if and only if). The sentence W1,3 ⇔ ¬W2,2 is a biconditional.\n",
        "\\n\n",
        "__Truth table:__\n",
        "\\n\n",
        "__P = False, Q = False:__ P⇒Q = True, P⇔Q = True\n",
        "\\n\n",
        "__P = False, Q = True:__ P⇒Q = True, P⇔Q = False\n",
        "\\n\n",
        "__P = True, Q = False:__ P⇒Q = False, P⇔Q = False\n",
        "\\n\n",
        "__P = True, Q = True:__ P⇒Q = True, P⇔Q = False\n",
        "\"\"\"\n",
        "\n",
        "chapter7_5 = \"\"\"\n",
        "The __deduction theorem__ says that For any sentences $\\\\alpha$ and $\\\\beta$, $\\\\alpha \\\\models \\\\beta$ iff the sentence $\\\\alpha$⇒ $\\\\beta$ is valid.\n",
        "\\n\n",
        "__Standard logical equivalences__:\n",
        "\\n\n",
        "__(A∧B) $\\\\equiv$ (B∧A)__. Commutativity of ∧\n",
        "\\n\n",
        "__(A∨B) $\\\\equiv$ (B∨A)__. Commutatibity of ∨\n",
        "\\n\n",
        "__((A∧B)∧C) $\\\\equiv$ (A∧(B∧C))__. Associativity of ∧.\n",
        "\\n\n",
        "__((A∨B)∨C) $\\\\equiv$ (A∨(B∨C))__. Associativity of ∨.\n",
        "\\n\n",
        "__¬(¬A) $\\\\equiv$ A__. Double negation elimination.\n",
        "\\n\n",
        "__(A⇒B) $\\\\equiv$ (¬B⇒¬A)__. Contraposition.\n",
        "\\n\n",
        "__(A⇒B) $\\\\equiv$ (¬A∨B)__. Implication elimination.\n",
        "\\n\n",
        "__(A⇔B) $\\\\equiv$ ((A⇒B)∧(B⇒A))__. Buconditional elimination.\n",
        "\\n\n",
        "__¬(A∧B) $\\\\equiv$ (¬A∨¬B)__. DeMorgan.\n",
        "\\n\n",
        "__¬(A∨B) $\\\\equiv$ (¬A∧¬B)__. DeMorgan.\n",
        "\\n\n",
        "__(A∧(B∨C)) $\\\\equiv$ ((A∧B)∨(A∧C))__. Distributivity of ∧ over ∨.\n",
        "\\n\n",
        "__(A∨∧(B∧C)) $\\\\equiv$ ((A∨B)∧(A∨C))__. Distributivity of ∧ over ∨.\n",
        "\\n\n",
        "__Modus Ponens__ is the following:\n",
        "$$\\\\frac{\\\\alpha \\\\Rightarrow \\\\beta, \\\\alpha}{\\\\beta}$$\n",
        "The notation means that whenever the sentences of the form $\\\\alpha \\\\Rightarrow \\\\beta$ or $\\\\alpha$ are given, then the sentence $\\\\beta$ can be inferred.\n",
        "\\n\n",
        "__And-Elimination__ is the following:\n",
        "$$\\\\frac{\\\\alpha \\\\wedge \\\\beta}{\\\\alpha}$$\n",
        "It says that whenever we have a conjunction, any of the conjuncts can be inferred. For example, with (WumpusAhead $\\\\wedge$ WumpusAlive), WumpusAlive can be inferred.\n",
        "\\n\n",
        "Modus Ponens and And-Elimination are sound.\n",
        "\\n\n",
        "A sentence expressed as a conjunction of clauses is said to be in __conjunctive normal form__ or __CNF__. Follow these steps to convert to CNF:\n",
        "\\n\n",
        "1. Eliminate ⇔ by replacing $\\\\alpha$ ⇔ $\\\\beta$ with $(\\\\alpha \\\\Rightarrow \\\\beta) \\wedge (\\\\beta \\\\Rightarrow \\\\alpha)$.\n",
        "\\n\n",
        "2. Eliminate $\\\\Rightarrow$ by replacing $\\\\alpha \\\\Rightarrow \\\\beta$ with $\\\\neg \\\\alpha \\\\vee \\\\beta$.\n",
        "\\n\n",
        "3. CNF requires $\\\\neg$ to appear only in literals, so we move them inwards with double-negation elimination and DeMorgan's laws.\n",
        "\\n\n",
        "4. We apply the distributivity law. Now the original sentence is in CNF \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "__Axioms__ are sentences that are given and __derived sentences__ are sentences that are new and derived from others.\n",
        "\\n\n",
        "If a sentence $\\\\alpha$ is true in model $m$ we say $m$ satisfies $\\\\alpha$ or $m$ is a model of $\\\\alpha$. $M(\\\\alpha)$ is the set of all models of $\\\\alpha$.\n",
        "\\n\n",
        "__Biconditional Elimination__:\n",
        "$$\\\\frac{\\\\alpha \\\\Leftrightarrow \\\\beta}{(\\\\alpha \\Rightarrow \\\\beta) \\wedge (\\\\beta \\\\Rightarrow \\\\alpha)}$$\n",
        "$$\\\\frac{(\\\\alpha \\Rightarrow \\\\beta) \\wedge (\\\\beta \\\\Rightarrow \\\\alpha)}{\\\\alpha \\\\Leftrightarrow \\\\beta}$$\n",
        "Basically for all the other logical rules, we can make this same form as above^\n",
        "\\n\n",
        "Monotonicity says that the set of entailed sentences can only increase as information is added to the KB. If KB $\\\\models \\\\alpha$ then KB $\\\\wedge \\\\beta \\\\models \\\\alpha$.\n",
        "\\n\n",
        "\\n\n",
        "__Resolution__: If $l_i$ and $m$ are complementary literaly (one is the negation of another), then we can eliminate them via __unit resolution__.\n",
        "\\n\n",
        "$$\\\\frac{l_1 \\\\vee \\\\ldots l_k, m}{l_1\\\\vee l_{i-1} \\\\vee \\\\ldots \\\\vee l_{i+1} \\\\vee l_k}$$\n",
        "\n",
        "__Resolution Algorithm__: To show KB $\\\\models \\\\alpha$ we can show that KB $\\\\wedge \\\\neg \\\\alpha$ is unsatisfiable.\n",
        "\\n\n",
        "- First convert (KB $\\\\wedge \\\\alpha$) into CNF\n",
        "\\n\n",
        "- Then apply the resolution rule to the resulting clauses\n",
        "\\n\n",
        "- Resolve every pair that contains complementary literals to produce a new clause\n",
        "\\n\n",
        "- If that new clause isn't already present, then add it to the set\n",
        "\\n\n",
        "- Continue the process until one of two things happens: (1) There are no clauses that can be added. In this case, the KB __does not__ entail $\\\\alpha$, \n",
        "(2) Two clauses resolve to yield the empty clause, in which case the KB __does__ entail $\\\\alpha$.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge base\" : \"a set of sentences that give us knowledge\",   \n",
        "\"inference\" : \"deriving new sentences from old ones\",\n",
        "\"entailment\" : \"a sentence following logically from another sentence\",\n",
        "\"sound\" : \"true inferences\",\n",
        "\"complete\" : \"can derive any sentence that is entailed\",\n",
        "\"atomic sentence\" : \"just one single proposition symbol\",\n",
        "\"logical equivalence\" : \"two sentences are logically equivalent if they are true in the same models\",\n",
        "\"valid\" : \"if a sentence is true in all models\",\n",
        "\"satisfiability\" : \"if a sentence is true in some model\",\n",
        "\"definite clause\" : \"a disjunction of literals where only one is positive\",\n",
        "\"Horn clause\" : \"a disjunction of literals where at most one is positive\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "a4eda0c4-3f58-4609-dcce-fca932b2a76c"
      },
      "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": 19,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n N/A \n\n## AIMA Chapter 7.2 The Wumpus World\n N/A \n\n## AIMA Chapter 7.3 Logic\n \nEntailment is when a sentence follows logically from a nother sentence, and we write it as $\\alpha \\models \\beta$. $M(\\alpha)$ is the set of all models of $\\alpha$. We can also write\n$$\\alpha \\models \\beta iff M(\\alpha) \\subseteq M(\\beta)$$\nNote that $\\alpha$ is a stronger assertion than $\\beta$.\n\n\nIf KB is true in the real world, then any sentence $\\alpha$ derived from KB by a sound inference procedure is also true in the real world.\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n¬ (not). A sentence such as ¬W1,3 is called the negation of W1,3. A literal is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal).\n\n\n∧ (and). A sentence whose main connective is ∧, such as W1,3 ∧ P3,1 , is called a conjunction.\n\n\n∨ (or). A sentence whose main connective is ∨, such as (W1,3 ∧P3,1)∨W2,2, is a disjunction.\n\n\n⇒ (implies). A sentence such as (W1,3 ∧ P3,1) ⇒ ¬W2,2 is called an implication (or conditional). Its premise or antecedent is (W1,3 ∧ P3,1), and its conclusion or consequent is ¬W2,2.\n\n\n⇔ (if and only if). The sentence W1,3 ⇔ ¬W2,2 is a biconditional.\n\n\n__Truth table:__\n\n\n__P = False, Q = False:__ P⇒Q = True, P⇔Q = True\n\n\n__P = False, Q = True:__ P⇒Q = True, P⇔Q = False\n\n\n__P = True, Q = False:__ P⇒Q = False, P⇔Q = False\n\n\n__P = True, Q = True:__ P⇒Q = True, P⇔Q = False\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nThe __deduction theorem__ says that For any sentences $\\alpha$ and $\\beta$, $\\alpha \\models \\beta$ iff the sentence $\\alpha$⇒ $\\beta$ is valid.\n\n\n__Standard logical equivalences__:\n\n\n__(A∧B) $\\equiv$ (B∧A)__. Commutativity of ∧\n\n\n__(A∨B) $\\equiv$ (B∨A)__. Commutatibity of ∨\n\n\n__((A∧B)∧C) $\\equiv$ (A∧(B∧C))__. Associativity of ∧.\n\n\n__((A∨B)∨C) $\\equiv$ (A∨(B∨C))__. Associativity of ∨.\n\n\n__¬(¬A) $\\equiv$ A__. Double negation elimination.\n\n\n__(A⇒B) $\\equiv$ (¬B⇒¬A)__. Contraposition.\n\n\n__(A⇒B) $\\equiv$ (¬A∨B)__. Implication elimination.\n\n\n__(A⇔B) $\\equiv$ ((A⇒B)∧(B⇒A))__. Buconditional elimination.\n\n\n__¬(A∧B) $\\equiv$ (¬A∨¬B)__. DeMorgan.\n\n\n__¬(A∨B) $\\equiv$ (¬A∧¬B)__. DeMorgan.\n\n\n__(A∧(B∨C)) $\\equiv$ ((A∧B)∨(A∧C))__. Distributivity of ∧ over ∨.\n\n\n__(A∨∧(B∧C)) $\\equiv$ ((A∨B)∧(A∨C))__. Distributivity of ∧ over ∨.\n\n\n__Modus Ponens__ is the following:\n$$\\frac{\\alpha \\Rightarrow \\beta, \\alpha}{\\beta}$$\nThe notation means that whenever the sentences of the form $\\alpha \\Rightarrow \\beta$ or $\\alpha$ are given, then the sentence $\\beta$ can be inferred.\n\n\n__And-Elimination__ is the following:\n$$\\frac{\\alpha \\wedge \\beta}{\\alpha}$$\nIt says that whenever we have a conjunction, any of the conjuncts can be inferred. For example, with (WumpusAhead $\\wedge$ WumpusAlive), WumpusAlive can be inferred.\n\n\nModus Ponens and And-Elimination are sound.\n\n\nA sentence expressed as a conjunction of clauses is said to be in __conjunctive normal form__ or __CNF__. Follow these steps to convert to CNF:\n\n\n1. Eliminate ⇔ by replacing $\\alpha$ ⇔ $\\beta$ with $(\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Rightarrow \\alpha)$.\n\n\n2. Eliminate $\\Rightarrow$ by replacing $\\alpha \\Rightarrow \\beta$ with $\\neg \\alpha \\vee \\beta$.\n\n\n3. CNF requires $\\neg$ to appear only in literals, so we move them inwards with double-negation elimination and DeMorgan's laws.\n\n\n4. We apply the distributivity law. Now the original sentence is in CNF \n\n## Module 7 Lecture Notes\n\n__Axioms__ are sentences that are given and __derived sentences__ are sentences that are new and derived from others.\n\n\nIf a sentence $\\alpha$ is true in model $m$ we say $m$ satisfies $\\alpha$ or $m$ is a model of $\\alpha$. $M(\\alpha)$ is the set of all models of $\\alpha$.\n\n\n__Biconditional Elimination__:\n$$\\frac{\\alpha \\Leftrightarrow \\beta}{(\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Rightarrow \\alpha)}$$\n$$\\frac{(\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Rightarrow \\alpha)}{\\alpha \\Leftrightarrow \\beta}$$\nBasically for all the other logical rules, we can make this same form as above^\n\n\nMonotonicity says that the set of entailed sentences can only increase as information is added to the KB. If KB $\\models \\alpha$ then KB $\\wedge \\beta \\models \\alpha$.\n\n\n\n\n__Resolution__: If $l_i$ and $m$ are complementary literaly (one is the negation of another), then we can eliminate them via __unit resolution__.\n\n\n$$\\frac{l_1 \\vee \\ldots l_k, m}{l_1\\vee l_{i-1} \\vee \\ldots \\vee l_{i+1} \\vee l_k}$$\n\n__Resolution Algorithm__: To show KB $\\models \\alpha$ we can show that KB $\\wedge \\neg \\alpha$ is unsatisfiable.\n\n\n- First convert (KB $\\wedge \\alpha$) into CNF\n\n\n- Then apply the resolution rule to the resulting clauses\n\n\n- Resolve every pair that contains complementary literals to produce a new clause\n\n\n- If that new clause isn't already present, then add it to the set\n\n\n- Continue the process until one of two things happens: (1) There are no clauses that can be added. In this case, the KB __does not__ entail $\\alpha$, \n(2) Two clauses resolve to yield the empty clause, in which case the KB __does__ entail $\\alpha$.\n \n\n## Module 7 Definitions\n* **Knowledge base** - a set of sentences that give us knowledge\n* **Inference** - deriving new sentences from old ones\n* **Entailment** - a sentence following logically from another sentence\n* **Sound** - true inferences\n* **Complete** - can derive any sentence that is entailed\n* **Atomic sentence** - just one single proposition symbol\n* **Logical equivalence** - two sentences are logically equivalent if they are true in the same models\n* **Valid** - if a sentence is true in all models\n* **Satisfiability** - if a sentence is true in some model\n* **Definite clause** - a disjunction of literals where only one is positive\n* **Horn clause** - a disjunction of literals where at most one is positive\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": "a59aa4d1-0cdb-4305-a530-8cae8e2f5f65"
      },
      "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": 20,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Intelligence can be have internal characterization (thought processes and reasoning),\nor external characterization (behavior). \n\n## AIMA Chapter 27.1 The Limits of AI\n N/A \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n N/A \n\n## AIMA 2.1 Agents and Environments\n N/A \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n N/A \n\n## AIMA 2.3 The Nature of Environments\n For an agent type of medical diagnosis system, we have P: healthy patient, reduced costs,\nE: patient, hospital, staff, A: display of questions, tests, diagnoses, treatments, S: touchscreen/voice entry of symptoms and findings.\nFor an agent type of satellite image analysis system, we have P: correct categorization of objects, terrain, E: orbiting satellite, weather,\nA: display of scene categorization, S: high-resolution digital camera. Other example agents are part-picking robot, refinery controller, interactive English tutor.\n\n\nA known (outomces for all actions are given vs unknown (the agent will have to learn how it works\nin order to make good decisions) environment distinction with fully and partially observable environments:\nKnown + partially observable example: solitaire (know the rules but unable to see the cards that are not turned over).\nUnknown + fully observable example: new video game, screen shows entire game state, but still don't know what the buttons \ndo until you try them.\n \n\n## AIMA 2.4 The Structure of Agents\n The challenge for AI is to find out how to write programs that produce rational beavhior\nfrom a smaller program raher than from a vast table.\n\n\nWe should handle partial observability by keeping track of the part of the world that is currently unseen (maintain\nsome sort of internal state based on percept history!). \n\n\nGoals only provide a distinction between 'happy' and 'unhappy' states. A utility function tells us how good a state is.\n\n## Module 1 Lecture Notes\n Alan Turing designed a test that asks whether machines can really think. It tests whether a human can \ndistinguish between a human and machine designed to generate human-like responses. John Searle believed that the \nTuring Test did not test whether machines possessed intelligence. With the Chinese Room experiment (room containing human\nwith no knowledge of Chinese, a rule book, and paper), Searle argues that the participant can do things that may simulate intelligence,\nbut in reality he has no actual understanding of Chinese.\n\n\nThere are 4 views of AI: thinking humanly, thinking rationally, acting humanly, and acting rationally.\nAn __agent__ is anything that perceives its environment through sensors and can act on its environment through actuators.\nA __percept__ is the agent's perceptual inputs at any given instance. An agent function $f: P \\rightarrow A$ maps\na sequence of percept vectors $P$ to an action $a$ from a set $A$: $P=\\{p_0,p_1,\\ldots,p_t\\}$,  $A=\\{a_0,a_1,\\ldots,a_k\\}$.\n\n\nThe __agent program__ runs on the physical architecture to product $f$: agent = architecture + program.\n\n\nA __rational agent__ perceives its environment and behaves rationally. A rational agent selects an action $a$ to maximize (expected value of its) performance measure.\n\n\nA __performance measure__ gives us a criterion for success of an agent's behavior given the evidence provided by the percept sequence.\nExample performance measures for a vacuum cleaner agent may be: +1 for each clean square at time $T$, +1 for cleaning a square, -1 for each move, -1000 for more than $k$ dirty squares.\n\n\nTo design a rational agent, we need to specify a task environment wiht PEAS: Performance measure, Environment, Actuators, Sensors.\nThe rational agent should construct an agent function $f$ that maximizes the expected value of the performance measure and design an agent program that implements $f$.\n\n\n__Fully observable (chess) vs Partially observable (autonomous car)__.\n\n\n__Deterministic__ (chess) means agent can select an action and know the state of the world completely, __Stochastic__ is probabilistic, meaning we can quantify how likely each outcome is.\n\n\n__Episodic__ means each decision is independent of past decisions, __Sequential__ means we need to plan ahead (more challenging than episodic).\n\n\n__Static__ (sudoku) means envionrment is unchanged until taking next action, __Dynamic__ (autonomous car) means the environment is changing while the agent thinks.\n\n\n__Discrete__ means there is a limited number of clearly defined actions or a finite set of actions to take, __Continuous__ rely on changing data sources like time.\n\n\n__Single agent__ (crossword puzzle), __Multi-agent__ (chess, pacman). When we have multi-agents, we need strategies.\n\n\nAgent vs part of the environment? When something can be described as having its own performance measure, then we should consider it to be an agent.\n\n\nThe hardest environment is continuous, partially observable, stochastic, multi-agent. But for now we will assume our environment is static, fully observable, deterministic, discrete.\n\n\n## Module 1 Definitions\n* **Turing test** - experiment to test whether machines can really think, passes if a human cannot distinguish\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - agent that acts rationally, to achieve the best/best expected outcome\n* **Simple reflex agentagent that select actions on the current percept, ignoring the historylimited rationality** - not enough time to do all possible computations, but acting appropriately\n* **Percept** - what the agent is perceiving\n* **Percept sequence** - the history of what the agent has perceived\n* **Agent function** - maps a percept sequence to an action\n* **Goal** - desirable situations/states\n* **Utility function** - internalized performance measure\n* **Atomic representation** - states of the world are indivisible with no internal structure\n* **Factored representation** - splitting states into a fixed set of variables/attributes, each having a value\n* **Consequentialism** - measure behavior by consequences of its behaviors\n* **Omniscience** - knowing actual outcome of actions, impossible in reality\n* **Task environments** - the 'problems' in which the agents are the 'solution'\n* **Weak ai** - machines act as if they were intelligent, simulate thinking\n* **Strong ai** - machines actually are consciously thinking\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n In Python, all data is treated as objects (deleted by garbage collection).\n\n\n__Literals__: integers (1, 2), Floats (1.0, 2e9), Boolean (True, False)\n\n\n__Operations__: arithmetic (+, -, *, /), power ((*)(*)), modulo (%), comparison (<=, >=, ==, !=), logic (and, or, not).\n\n\nThere is no ++ or -- in Python!\n\n\nYou can concatentate strings with '+'. You can format strings as such: print(\"%s can speak $d languages\" $(\"C3P0\", 6000000)).\n\n\n__Strings__ are immutable. Lists are mutable. Use y = x[:] to obtain a shallow copy of any sequence (new object of the same value).\n\n\n== checks if two things are the same value, is checks whether the variables point to the same object.\n\n\n__Functions__: strip() gets rid of whitespaces at beginning and end. split(delim) makes an array of the string separated\nby the delim.\n\n\nSlicing examples (lst[initial:end:indexjump]): t=(23, 'abc', 4.56, (2,3), 'def')\n\n\nt[1:4] -> ('abc', 4.56, (2,3)). We don't include the last index in the slice.\n\n\nt[1:-1] -> ('abc', 4.56, (2,3))\n\n\nt[1:-1:2] -> ('abc', (2,3))\n\n\nt[:2] -> (23, 'abc'). Copies from the beginning of the sequence.\n\n\nt[2:] -> (4.56, (2,3), 'def). Copies to the end of the sequence.\n\n\nOperations on lists example: li = [1, 11, 3, 4, 5]\n\n\nli.append('a') -> [1, 11, 3, 4, 5, 'a']\n\n\nli.insert(2,'i') -> [1, 11, 'i', 3, 4, 5, 'a']. Inserted at index 2.\n\n\nOperations on list example: li = [5, 2, 6, 8]\n\n\nli.reverse() -> [8, 6, 2, 5]. Reversed the list in place.\n\n\nli.sort() -> [2, 5, 6, 8]. Sorted the list in place.\n\n\nsorted(li) -> [2, 5, 6, 8]. Returns a copy sorted.\n\n\n__Dictionaries__ must have immutable keys, so lists CANNOT be keys since they are mutable! For dictionaries, we can only\nlook things up by key, not by value.\n\n\nd.keys() returns a list of the current keys. d.value() returns a list of current values. d.items() gives a list of item tuples.\n\n\n__Functions__ are defined first with def, the function name and its arguments and a return. Python allows us to return multiple values like: return mean, median, mode (of type tuple).\nWe CANNOT have function overloading (same method names). We can also provide default values for a function's arguments.\n\n\nFor example, def myfun(b, c=3, d=\"hello\"): return b+c.\n\n\nmyfun(5,3,\"bob\") returns 8.\n\n\nmyfun(5,3) returns 8.\n\n\nmyfun(5) returns 8.\n\n\nFunctions can also be called with arguments out of ordered, but the arguments must be specified in the call.\n\n\n__\\*args__ allows us to accept a variable number of NON-keyword arguments to a function.\n\n\nExample: def print_everything(\\*args): print(args)\n\n\nprint_everything('a','b','c') prints ('a','b','c')\n\n\nlst = ['a','b','c']. print_everything(lst) prints ('a','b','c').\n\n\n__\\*\\*kwargs__ allows us to accept a variable number of keyword arguments to a function.\nExample: def print_keyword_args(\\*\\*kwargs): print(kwargs)\n\n\nprint_keyword_args(first_name=\"John\", last_name=\"Doe\") prints {'first_name': 'John', 'last_name': Doe'}\n\n\nmy_dict = {'first_name': 'John', 'last_name': Doe'}. print_keyword_args(\\*\\*my_dict) prints {'first_name': 'John', 'last_name': Doe'}.\n\n\nIn a class, every method has \"self\" as an argument. \\__function\\__ are __magic methods__, meaning there's ways \nto call the function without calling __function__ (i.e. __init__ is called with new).\n\n\nMagic methods include \\__init\\__, \\__len\\__, \\__copy\\__, \\__cmp\\__, \\__add\\__, \\__neg\\__.\n\n\nA class can extend the definition of another class (can use or extend methods and attributes already defined in the previous one).\nDo this by: class AI_Student(Student).\n\n\n__List comprehensions__ can replace for loops. For example:\n\n\nExample 1:\n\n\nnums = list(range(10))\n\n\nsq = [n*n for n in nums]\n\n\nprint(sq) # [0, 1, 4, 9, 16,...]\n\n\nExample 2:\n\n\nli = [3, 6, 2, 7, 1, 9]\n\n\n[elem * 2 for elem in li if elem > 4] # [12, 14, 18]\n\n\n__Generators__ are iterators (with __next__()) method. Functions that contain the yield keywork AUTOMATICALLY return a generator when called.\nEach time we call __next__ method of the generator, the method runs until it encounters a yield. Then it stops and returns the value that was yielded.\nNext time, it resumes where it left off.\n\n\nBenefits of generators: less code than standard iterator, maintains local state automatically, values are computed as needed\n\n\n## Module 2 Definitions\n* **Strong typing** - each object has a fixed type, interpreter doesn't allow incompatible types\n* **Types** - int, float, str, tuple, dict, list, bool (True, False), None, generator, function\n* **Dynamic typing** - variables come into existence when first assigned\n* **Shallow copy** - new object of the same value\n* **Sequence types** - tuples, strings, lists\n* **Tuple** - immutable ordered sequence of items, can be of mixed types\n* **List** - mutable ordered sequence of items of mixed types\n* **Dictionary** - unordered, uses hashing, immutable keys, gives O(1) average add, lookup, update\n* **Immutable** - cannot modify without making a new copy\n* **First-class object** - entity that can by dynamically created, destroyed, passed to a function, returned as a variable, eg. functions\n* **Iterator** - object with a __next__() method, no hasnext in Python\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n A seearch problem can be defined formally with __states__/__state space__, __initial state__, __goal states__, __actions__,\n__transition model__ (describes what each action does), __action cost function__ (agent should use a cost function to reflect its own performance measure).\n\n\n## AIMA Chapter 3.2 Example Problems\n \nFor a grid world (2d rectangular array of cells) with two-cells we can formulate as a search problem as follows:\n\n\n__States__: Agent can be in either of the two cells. The cells can either contain dirt or not. In a world with $n$ cells, we have $n\\cdot 2^n$ states.\n\n\n__Initial state__: Any state can be the initial.\n\n\n__Actions__: Three actions: suck, move left, move right.\n\n\n__Transition model__: Suck removes any dirt, left moves left, right moves right unless hitting a wall.\n\n\n__Goal states__: The states in which every cell is clean.\n\n\n__Action cost__: Each action costs 1. \n\n\nTraveling salesman problem is a touring problem (describe a set of locations that must be visited, rather than a single destination).\n\n\n\n## AIMA Chapter 3.3 Search Algorithms\n \nBest First Search chooses a node $n$ with a minimum value of an evaluation function $f(n)$.\n\n\n$|V|$ = number of vertices (state nodes), $|E|$ = number of edgs (distinct state/action pairs). $d$ = depth or nuber of actions in \nan optimal solution, $m$ = maximum number of actions in any path, $b$ = branching factor, or the number of successors of a node\nthat need to be considered.\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Uninformed search has no idea how close a state is to the goal. \n__Uniform cost search__ idea -> spread out in waves of uniform cost (not uniform depth). Complexity is characterized in terms of \n$C^*$, the cost of the optimal solution, and $\\epsilon$, a lower bound on the cost of each action. The worst-case time and space\ncomplexity is $O(b^{1+\\lfloor C^*/\\epsilon \\rfloor})$, which can be much greater than $b^d$. Uniform-cost search is complete and cost-optimal.\n\n\n__Depth-first search__ expands deepest node in the frontier. Implemented usually as tree-like search, does not keep track of reached states.\nDFS is not cost-optimal; it returns the first solution it finds. DFS has much smaller space complexity. A DFS search takes time proportional to the number of states\nand has space complexity of only $O(bm)$, where $b$ is the branching factor and $m$ is the maximum depth of the tree.\n\n\nTo prevent DFS from wandering down an infinite path, we use __depth-limited serach__. We go only to a limit $l$. The time complexity is $O(b^l)$, and space\ncomplexity is $O(bl)$. __Iterative deepening search__ chooses $l$ to be 0, then 1, then 2, ... until a solution is found or we reach failure. The \nspace complexity is $O(bd)$ when there is a solution, or $O(bm)$ where we have no solution. Like BFS, optimal for problems with same cost.\nThe time complexity is $O(b^d)$ when there is solution, or $O(b^m)$ when none.\n\n\n```\nfunction ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure \n  for depth = 0 to ∞ do\n    result←DEPTH-LIMITED-SEARCH(problem,depth) \n    if result ̸= cutoff then return result\n\nfunction DEPTH-LIMITED-SEARCH(problem, l) returns a node or failure or cutoff \n  frontier←a LIFO queue (stack)\n  result ← failure\n  while not IS-EMPTY(frontier) do\n    node←POP(frontier)\n    if problem.IS-GOAL(node.STATE) then return node \n    if DEPTH(node) > l then\n      result ← cutoff\n    else if not IS-CYCLE(node) do\n      for each child in EXPAND(problem, node) do \n        add child to frontier\n  return result\n```\n\n__Bidirectional search__ searches forward from the initial state and backwards from the goal state(s). The motivation for this\nsearch is that $b^{d/2} + b^{d/2}$ is much less than $b^d$. We keep track of two frontiers and two reached sets.\n```\nBFS: Complete, optimal cost, O(b^d) time, O(b^d) space\nUniform-cost: Complete, optimal cost, O(b^{1+(C*/epsilon)} time, O(b^{1+(C*/epsilon)} space\nDepth-first: Not complete, not optimal cost, O(b^m) time, O(bm) space\nDepth-limited: Not complete, not optimal cost, O(b^l) time, O(bl) space\nIterative deepening: Complete, optimal, O(b^d) time, O(bd) space\nBidirectional: Complete, optimal cost, O(b^{d/2}) time, O(b^{d/2}) space\n```\n\n\n## Module 3 Lecture Notes\n\nA reflex agent is one that selects an action based only on the current percept and ignores percept history.\nA problem-solving agent plans ahead. For a task environment that is fully observable, deterministic, known environment, then the solution\nis a fixed sequence of actions. In environments that are partially observable or nondeterministic, then the solution must recommend future actions\ndepending on the percepts it receives.\n\n\nFor the 8-tile puzzle:\n\n\n__States__: configurations of the puzzle (9! configurations)\n\n\n__Actions__: Move one of the movable pieces (<= 4 possible actions)\n\n\n__Performance measure__: minimize the total moves\n\n\nThe __state space__ is the set of all states reachable from the initial state by any sequence of actions.\n\n\nIn __uninformed search__, all non-goal nodes in the frontier look equally good.\n\n\n$b$ = maximum branching factor of search tree. $d$ = depth of the shallowest goal node. $m$ = maximum length of any path in the state space (potentially $\\inf$)\n\n\nIn deciding between DFS and BFS, we should use...\n\n\nDFS: __Space is restricted__, many possible solutions with long paths and wrongs paths can be terminated quickly\n\n\nBFS: __Possible infinite paths__, some solutions have shorter paths, can quickly discard unlikely paths\n\n\nIterative deepening search uses depth-limited search as a subroutine with increasing $l$.\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Path** - a sequence of actions\n* **Abstraction** - removing details from a representation\n* **Search algorithm** - input is search problem and returns a solution\n* **Search tree** - shows paths from initial to hoping to find goal state\n* **Frontier** - the next unexpanded nodes\n* **Graph search** - checks for redundanct paths\n* **Tree search** - does not check for redundant paths\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n__Greedy best-first search__ expands the node with the lowest $h(n)$ value. The evaluation function $f(n) = h(n)$.\nThis is complete in finite state spaces, but not in infinite ones. The worst-case time and space complexity is $O(|V|)$, but a good\nheuristic can reduce this complexity substantially (some problems reach $O(bm)$).\n\n\n__A\\* search__ is a best-first search that uses the evaluation function $f(n)=g(n)+h(n)$ where $g(n)$ is the path\ncost from the initial state to node $n$, and $h(n)$ is the estimated cost of the shortest path from $n$ to the goal state.\nSo then we have $f(n)=$ the estimated cost of the best path that continues from $n$ to a goal. When we extend a path, the $g$ costs should be\nmonotonic (always increasing as you go along a path since action costs are always positive). A\\* search is complete, cost-optimal, and optimally efficient.\n\n\n__Weighted A\\* search__ weighs the heuristic value more heavily, and we have evaluation function $f(n)=g(n)+W\\times h(n)$. This is \na \"somewhat-greedy\" search.\n\n\nThe main nissue with A\\* is its use of memory (that is split between the frontier and visited states).\n\n\n__Beam seach__ limits the size of the frontier by keeping only $k$ nodes with the best $f$-scores.\n\n\n__Iterative deepening A\\* search__, or IDA\\* gives us what iterative-deepening does to DFS. The cutoff is the $f$-cost.\n\n\n__Recursive best-first search__, or RBFS mimics best-first, but only uses linear space. It resembles a recursive depth-first search but uses the $f_limit$ variable\nto keep track fo the $f$-value of the best alternative path available from any ancestor of the current node. If the current node exceeds the limit, the recursion goes back to the alternative\npath. RBFS is somewhat more efficient that IDA\\* but it has excessive node generation still. It is optimal if $h(n)$ is admissible.\n\n\nIDA\\* and RBFS suffer from using too little memory! I.e. IDA\\* only maintains a single number: $f$-cost limit. DBFS retains more but only linear space.\n\n\nBidirectional heuristic uses $f_F(n) = g_F(n) + h_F(n)$ for nodes in the forward direction and $f_B(n) = g_B(n) + h_B(n)$ for nodes in the\nbackward direction.\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n\nFor the 15-puzzle, there are 16!/2 states so we need a really good admissible heuristic. Some candidates are:\n\n\n$h_1$: number of misplaced tiles\n\n\n$h_2$: the sum of distances of the tiles from their goal positions. Manhatten distances.\n\n\n## Module 4 Lecture Notes\n\nSo far, we've assumed that all moves are equal in cost ($g(N)$ = depth(N) in search tree). But more generally, we should\nconsider a potentially unique cost at each step. For __uniform-cost search__ (UNINFORMED), we expand the node\nwith the lowest path cost by using a frontier that is a priority queue ordered by $g(n)$. With UCS, there could still be\na solution on the queue that is less costly.\n\n\n_Greedy best first_ search is exactly UCS with $f(n)$ replacing $g(n)$. And here, we have $f(n)=h(n)$. It is \nnot optimal and not complete.\n\n\n__A\\* search__ is the best known form of best first search. It has $f(n)=g(n)+h(n)$. $h(n)$ must be admissible (never overestimating).\n\n\nA relaxed problem has fewer restrictions on the actions than the original. $h_{oop}$ for 8-tile puzzle where tile can move anywhere (out of place),\n$h_{md}$ for 8-tile puzzle where a tile can move to any adjacent square (manhatten distance).\n\n\nIf $h_2(n) \\geq h_1(n)$ for all $n$ then $h_2$ __dominates__ $h_1$. $h_2$ is more accurate than $h_1$. $h*(n)$ is the Oracle heuristic, or the true distance from the root to $n$.\n\n\n__Summary:__\n\n\n__Uniform cost search__: $f(n)=g(n)$\n\n\n__Greedy best first search__: $f(n) = h(n)$\n\n\n__A\\* search__: $f(n) = g(n)+h(n)$\n\n```\nfunction BEST-FIRST-SEARCH(problem, f ) returns a solution node or failure node←NODE(STATE=problem.INITIAL)\n  frontier ← a priority queue ordered by f , with node as an element\n  reached←a lookup table, with one entry with key problem.INITIAL and value node \n  while not IS-EMPTY(frontier) do\n    node←POP(frontier)\n    if problem.IS-GOAL(node.STATE) then return node \n      for each child in EXPAND(problem, node) do\n        s←child.STATE\n        if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n          reached[s] ← child\n          add child to frontier return failure\n\nfunction EXPAND(problem,node) yields nodes\n  s←node.STATE\n  for each action in problem.ACTIONS(s) do\n    s′ ←problem.RESULT(s,action)\n    cost←node.PATH-COST + problem.ACTION-COST(s,action,s′)\n    yield NODE(STATE=s′, PARENT=node, ACTION=action, PATH-COST=cost)\n\n```\n\n \n\n## Module 4 Definitions\n* **Informed search** - uses hints about location of goal(s) to find the solution more efficiently\n* **Heuristic function** - estimated cost of path\n* **Satisficing** - solutions that are suboptimal but 'good enough'\n* **Relaxed problem** - fewer restrictions than on the og problem\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\nMost commonnly studied games are perfect information, zero-sum games. These are fully observable, no win-win outcome games.\nWe call the two players MAX and MIN. A game can be defined as follows:\n\n\n$S_0$: The __initial state__\n\n\nThe player whose turn it is to move in state $s$\n\n\nThe set of legal moves in state $s$\n\n\nThe __transition model__ that defines the result from taking action $a$ from state $s$\n\n\nA __terminal test__ to see if the game is over\n\n\nA __utility function__ that defines a numeric value to the player when the game ends in terminal state $s$.\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nMAX's strategy is contingent on MIN. We can use __minimax search__.\n\n\nThe __minimax value__ is the utility for MAX in that state (assuming both players play optimally).\n\n\nThe time complexity of minimax is $O(b^m)$. The space complexity is $O(bm)$ if we have an algorithm that generates all actions\nat once or $O(m)$ for an algorithm that generates actions one at a time.\n\n\nFor multiplayer games, we must consider nonterminal states. For each state, we have a vector of values that describe\nthe utilities for each player. If a player is going to reach a terminal state, they look at the best possible value that they can\nget out of the choices for the terminal states.\n\n\nWith __alpha-beta pruning__ we can remove large parts of the tree that make no difference to the outcome.\n$$\\alpha = \\text{the value of the best (i.e. highest-value) choice we have found so far at any choice point along the path for MAX}$$\n$$\\beta = \\text{the value of the best (i.e. lowest-value) choice we have found so far at any choice point along the path for MIN}$$\n\n```\nfunction MINIMAX-SEARCH(game, state) returns an action \n  player←game.TO-MOVE(state)\n  value, move←MAX-VALUE(game, state)\n  return move\n\nfunction MAX-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null\n    v←−∞\n    for each a in game.ACTIONS(state) do\n      v2, a2←MIN-VALUE(game, game.RESULT(state, a)) \n      if v2 > v then\n        v, move←v2, a \n    return v, move\n\nfunction MIN-VALUE(game, state) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n    v←+∞\n    for each a in game.ACTIONS(state) do\n      v2, a2←MAX-VALUE(game, game.RESULT(state, a)) \n      if v2 < v then\n        v, move←v2, a \n    return v, move\n\n```\n__Alpha-beta pruning algorithm:__\n```\nfunction ALPHA-BETA-SEARCH(game, state) returns an action player←game.TO-MOVE(state)\n  value, move←MAX-VALUE(game, state,−∞,+∞)\n  return move\n\nfunction MAX-VALUE(game, state, α, β) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null v←−∞\n  for each a in game.ACTIONS(state) do\n    v2, a2←MIN-VALUE(game, game.RESULT(state, a),α,β) \n    if v2 > v then\n      v, move←v2, a\n      α←MAX(α, v)\n    if v ≥ β then return v, move\n  return v, move\n\nfunction MIN-VALUE(game, state, α, β) returns a (utility, move) pair\n  if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null v←+∞\n  for each a in game.ACTIONS(state) do\n    v2, a2←MAX-VALUE(game, game.RESULT(state, a),α,β) \n    if v2 < v then\n      v, move←v2, a\n      β←MIN(β, v)\n    if v ≤ α then return v, move\n  return v, move\n```\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n To make use of limited computation time, we can cut off the search early an apply a heuristic evaluation function to states.\nThis replaces the utility function with Eval and the terminal test with a cutoff test (returns True for terminal states) that decides\nwhen to cut off the search. In alpha-beta search pseudocode, we check if the game is at cutoff and then return the Eval at that state (instead\nof checking if we are at a terminal state and then returning the utility).\n\n\nWith __beam search__, on each ply we only consider the $n$ best moves. This is dangerous because the best move may be pruned away.\n \n\n## AIMA Chapter 5.5 Stochastic Games\n\nBackgammon is a stochastic game that combines luck and skill. For stochastic nodes, we must include __chance nodes__ in addition to MAX and MIN\nnodes. \n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n N/A \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n N/A \n\n## AIMA Chapter 16.3 Utility Functions\n N/A \n\n## Module 5 Lecture Notes\n\nEvaluation functions $f(n)$ evaluates how good a board position is based on static features onf that board alone.\n\n\n$f(n)>0$ if MAX is winning in position $n$\n\n\n$f(n)=0$ if tied\n\n\n$f(n)<0$ if MIN is winning in position $n$.\n\n\nFor tic-tac-toe, $f(n)$ = $ of 3 lengths open for MAX - # of 3 lengths open for MIN.\n\n\nThe Minimax procedure is as follows:\n\n\n1. Start with the current position as MAX node\n\n\n2. Expand the game tree a fixed number of ply\n\n\n3. Apply the evaluation function to the leaf positions.\n\n\n4. Calculate back-up values bottom-up.\n\n\n5. Pick the move assigned to MAX at the root.\n\n\n6. Wait for MIN to respond.\n\n\nIn __minimax search__, we have a state-space search tree, players alternate turns, and we compute each node's __minimax value__ (best achievable utility against a rational adversary).\nFor alpha-beta pruning, we realize that MAX will never allow a move that could lead to a worse score (for MAX) than $\\alpha$. Similarly, MIN will never\nallow a move that could lead to a better score (for MAX) than $\\beta$. Thus, we stop evaluating a branch whenever:\n\n\n- When evaluating a MAX node: a value $v \\geq \\beta$ is backed-up because MIN will never select that MAX node.\n\n\n- When evaluating a MIN node: a value $v \\leq \\alpha$ is found because MAX will never select that MIN node.\n\n\n__Expectimax__ considers games that are controlled by chance and not an adversary. Here, we have the following:\n\n\n- MAX nodes like in minimax search\n- Chance nodes are like MIN nodes but the outcome is uncertain\n- Calculate expected utilities, i.e. weighted average of children\n\n\nWe can't use alpha-beta pruning as before since we are doing an average. There are probabilities so we can't be certain.\n\n\n## Module 5 Definitions\n* **Perfect infomration, zero-sum games** - fully-observable and no 'win-win' outcomes\n* **State space graph** - vertices = states, edges = moves\n* **Game tree** - search tree that follows every sequence to a terminal state\n* **Ply** - move from one player to the next, one level down in the tree\n* **Minimax decision** - the best choice for MAX\n* **Heuristic evaluation function** - estimates the expected utility of a state\n* **Forward pruning** - eliminates moves that seem bad but may be good ones\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nA constraint satisfaction problem consists of:\n\n\n- $\\Chi$, a set of variables\n\n\n- $D$, a set of domains, one for each variable, specifying allowable values for the variable\n\n\n- $C$, a set of constraints that specify the allowable combinations of values\n\n\nCSPs deal with __assignments__ of values to variables. The simplest kind of CSPs have discrete, finite domains. \n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nWe often talk about __arc consistency__,\nor if every value in a variable's domain satisfies the variable's binary constraints. __AC-3__ enforces arc-consistency.\nFirst, AC-3 maintains a queue of arcs to consider (all of them at first), and then pops off an arbitrary arc $(X_i, X_j)$ and makes $X_i$ arc consistent\nwith respect to $X_j$. If it changes, we add all arcs $(X_k, X_i)$ where $X_k$ is a neighbor of $X_i$. With a CSP of $n$ variables each with domain size of at most $d$, and with $c$\nbinary constraints (arc), we have $O(cd^3)$, since each arc can only be inserted in the queue at most $d$ times because $X_i$ has at most $d$ values to delete.\n\n```\nfunction AC-3(csp) returns false if an inconsistency is found and true otherwise \n  queue ← a queue of arcs, initially all the arcs in csp\n  while queue is not empty do (Xi, Xj)←POP(queue)\n    if REVISE(csp, Xi, Xj) then\n      if size of Di = 0 then return false\n      for each Xk in Xi.NEIGHBORS - {Xj} do\n        add (Xk, Xi) to queue \n  return true\n\nfunction REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi \n  revised ← false\n  for each x in Di do\n    if no value y in D j allows (x,y) to satisfy the constraint between Xi and X j then \n      delete x from Di\n      revised ← true\n  return revised\n```\n\n\n\n__Path consistency__ tightens binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n$\\{X_i, X_j\\}$ is path consistent with respect to $X_m$ if, for every assignment $\\{X_i=a, X_j=b\\}$ consistent with the constaints on $\\{X_i, X_j\\}$, there is\nan assignment to $X_m$ that satisfies the constraints on $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$.\n\n\n__$k$-consistency__refers to for any set of $k-1$ variables, a consistent value can always be assigned to any $k$th variable.\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nWhen we finish the constraint propagations and still have variables that can take on multiple values, we must now search for a solution.\nOne form of inference is called __forward checking__. When $X$ is assigned, we establish arc consistency for it (for each variable that is connected to $X$\nby a constraint, delete from that variable any value that is inconsistent with the value chosen for $X$).\n\n\n__Maintaining Arc Consistency__ MAC algorithm etects inconsistencies using AC-3 but instead of a queue with all of the arcs in the CSP, we start with only\n$(X_j, X_i)$ for all $X_j$ that are unassigned variables that are neightbors of $X_i$.\n\n\nWith __chronological backtracking__, we back up to the preceding variable and try a different value for it (when a branch of the search fails).\n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n N/A \n\n## AIMA Chapter 6.5 The Structure of Problems\n We can reduce a constraint graph by __cutset conditioning__.\n\n\n1.Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after removal of S. S is called a cycle cutset.\n\n\n2. For each possible assignment to the variables in S that satisfies all constraints on S, (a) remove from the domains of the remaining variables any values that are inconsis- tent with the assignment for S, and\n(b) if the remaining CSP has a solution, return it together with the assignment for S.\n\n\nAnother way to reduce is by __tree decomposition__, or a transformation of the og graph to a tree where each node consists of a set of variables.\nIt must satisfy:\n\n\n- Every variable in the original problem appears in at least one of the tree nodes.\n\n\n- If two variables are connected by a constraint in the original problem, they must appear\ntogether (along with the constraint) in at least one of the tree nodes.\n\n\n- If a variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes.\n \n\n## Module 6 Lecture Notes\n\nBenefits of CSP:\n\n\n- Clean specification of many problems, generic goal, successor function, and heuristics\n\n\n- CSP knows which variables violate a constraint\n\n\n- CSPs prune off branches that violate constraints\n\n\n__Unary__ constraints involve a single variable, __binary__ constraints involve pairs, __higher-order__ constraints involve 3 or more.\n__Preference__ constraints are what they sound like, could be represented by a cost for each variable assignment.\nWe can model CSPs as a search problem. We have $n$ variables of domain size $d$. So the branching factor at the root is $n\\times d$. The branching factor at the next level is\n$(n-1)\\times d$. The tree has $n!d^n$ leaves.\n\n\nDepth-first search for CSPs with single-variable assignments is called __backtracking__ search., it is the basic __uninformed__ algorithm for CSPs. We can improve with different heuristics.\n\n\n__Heuristic 1: Most constrained variable__. Choose a variable with the fewest legal moves (__minimum remaining values MRV heuristic__). This is also called the Fast Fail method.\n\n\n__Heuristic 2: Most constraining variable__. Tie-breaker among most contrained variables. Choose the variable with the most constraints on the reamining variables.\n\n\n__Heuristic 3: Least constraining value__. Given a variable, choose the least constraining value (the one that rules out the fewest values in the reamining variables).\n\n\n__Heuristic 4: Forward checking__. Keep track of reamining legal values for unassigned variables.\n\n\nForward checking propagates info, but doesn't provide early failure detection. __Constraint propagation__ goes beyond forward checking and repeatedly enforces constraints locally.\nConstraint propagation (inference!) eliminates possible values for a variable. __Arc consistency__ satisfies binary constraints. In a constraint graph, nodes are variables and edges are constraints.\nFor a pair of nodes that are constrained, we represent the graph as two directed arcs that connect them.\n\n\nThe __Waltz/Mackworth Constraint Propagaation Algorithm__:\n\n\n1. Assign every node in the constraint graph a set of all possible values\n\n\n2. Repeat until there is no change in the set of values associated with any node:\n\n\n3. For each node $i$, for each neighboring node $j$, remove any value from $i$ which is not arc consistent with $j$\n\n\nWe get to __AC-3__ by addressing the inconsistencies. Namely, at each iteration, we only need to examine those $X_i$ where at least one neighbor of $X_i$\nhas lost a value and removing a value on $X_i$ can only make $Y_j$ arc-inconsistent with respect to $X_i$ itself. Thus we only need to check that $(j,i)$ is still arc consistent.\n\n\nTime complexity of AC-3:\n\n\n- All nodes can be connected to every other node, $O(n^2)$ arcs\n\n\n- If there are $d$ values, checking each arc takes $O(d^2)$\n\n\n- Each arc can only be inserted into the queue $d$ times\n\n\nThe time complexity is $O(n^2d^3)$.\n \n\n## Module 6 Definitions\n* **Complete assignment** - every variable has an assignment\n* **Solution** - a consistent and complete assignment for a CSP\n* **Precedence constraints** - one task must happen before another\n* **Disjunctive constraint** - one task must not overlap in time with another\n* **Binary constraint** - relating two different variables\n* **Global constraint** - relating arbitrary number of variables\n* **Constraint propagation** - reducing the number of possible moves by using the constraints\n* **Arc consistent** - every value in a variable's domain satisfies the variable's binary constraints\n* **Minimum remaining values (mrv) heuristic** - choosing the variable with the fewest possible values\n* **Min-conflicts heuristic** - select value that results in least conflicts with other variables\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n N/A \n\n## AIMA Chapter 7.2 The Wumpus World\n N/A \n\n## AIMA Chapter 7.3 Logic\n \nEntailment is when a sentence follows logically from a nother sentence, and we write it as $\\alpha \\models \\beta$. $M(\\alpha)$ is the set of all models of $\\alpha$. We can also write\n$$\\alpha \\models \\beta iff M(\\alpha) \\subseteq M(\\beta)$$\nNote that $\\alpha$ is a stronger assertion than $\\beta$.\n\n\nIf KB is true in the real world, then any sentence $\\alpha$ derived from KB by a sound inference procedure is also true in the real world.\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n¬ (not). A sentence such as ¬W1,3 is called the negation of W1,3. A literal is either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal).\n\n\n∧ (and). A sentence whose main connective is ∧, such as W1,3 ∧ P3,1 , is called a conjunction.\n\n\n∨ (or). A sentence whose main connective is ∨, such as (W1,3 ∧P3,1)∨W2,2, is a disjunction.\n\n\n⇒ (implies). A sentence such as (W1,3 ∧ P3,1) ⇒ ¬W2,2 is called an implication (or conditional). Its premise or antecedent is (W1,3 ∧ P3,1), and its conclusion or consequent is ¬W2,2.\n\n\n⇔ (if and only if). The sentence W1,3 ⇔ ¬W2,2 is a biconditional.\n\n\n__Truth table:__\n\n\n__P = False, Q = False:__ P⇒Q = True, P⇔Q = True\n\n\n__P = False, Q = True:__ P⇒Q = True, P⇔Q = False\n\n\n__P = True, Q = False:__ P⇒Q = False, P⇔Q = False\n\n\n__P = True, Q = True:__ P⇒Q = True, P⇔Q = False\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\nThe __deduction theorem__ says that For any sentences $\\alpha$ and $\\beta$, $\\alpha \\models \\beta$ iff the sentence $\\alpha$⇒ $\\beta$ is valid.\n\n\n__Standard logical equivalences__:\n\n\n__(A∧B) $\\equiv$ (B∧A)__. Commutativity of ∧\n\n\n__(A∨B) $\\equiv$ (B∨A)__. Commutatibity of ∨\n\n\n__((A∧B)∧C) $\\equiv$ (A∧(B∧C))__. Associativity of ∧.\n\n\n__((A∨B)∨C) $\\equiv$ (A∨(B∨C))__. Associativity of ∨.\n\n\n__¬(¬A) $\\equiv$ A__. Double negation elimination.\n\n\n__(A⇒B) $\\equiv$ (¬B⇒¬A)__. Contraposition.\n\n\n__(A⇒B) $\\equiv$ (¬A∨B)__. Implication elimination.\n\n\n__(A⇔B) $\\equiv$ ((A⇒B)∧(B⇒A))__. Buconditional elimination.\n\n\n__¬(A∧B) $\\equiv$ (¬A∨¬B)__. DeMorgan.\n\n\n__¬(A∨B) $\\equiv$ (¬A∧¬B)__. DeMorgan.\n\n\n__(A∧(B∨C)) $\\equiv$ ((A∧B)∨(A∧C))__. Distributivity of ∧ over ∨.\n\n\n__(A∨∧(B∧C)) $\\equiv$ ((A∨B)∧(A∨C))__. Distributivity of ∧ over ∨.\n\n\n__Modus Ponens__ is the following:\n$$\\frac{\\alpha \\Rightarrow \\beta, \\alpha}{\\beta}$$\nThe notation means that whenever the sentences of the form $\\alpha \\Rightarrow \\beta$ or $\\alpha$ are given, then the sentence $\\beta$ can be inferred.\n\n\n__And-Elimination__ is the following:\n$$\\frac{\\alpha \\wedge \\beta}{\\alpha}$$\nIt says that whenever we have a conjunction, any of the conjuncts can be inferred. For example, with (WumpusAhead $\\wedge$ WumpusAlive), WumpusAlive can be inferred.\n\n\nModus Ponens and And-Elimination are sound.\n\n\nA sentence expressed as a conjunction of clauses is said to be in __conjunctive normal form__ or __CNF__. Follow these steps to convert to CNF:\n\n\n1. Eliminate ⇔ by replacing $\\alpha$ ⇔ $\\beta$ with $(\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Rightarrow \\alpha)$.\n\n\n2. Eliminate $\\Rightarrow$ by replacing $\\alpha \\Rightarrow \\beta$ with $\\neg \\alpha \\vee \\beta$.\n\n\n3. CNF requires $\\neg$ to appear only in literals, so we move them inwards with double-negation elimination and DeMorgan's laws.\n\n\n4. We apply the distributivity law. Now the original sentence is in CNF \n\n## Module 7 Lecture Notes\n\n__Axioms__ are sentences that are given and __derived sentences__ are sentences that are new and derived from others.\n\n\nIf a sentence $\\alpha$ is true in model $m$ we say $m$ satisfies $\\alpha$ or $m$ is a model of $\\alpha$. $M(\\alpha)$ is the set of all models of $\\alpha$.\n\n\n__Biconditional Elimination__:\n$$\\frac{\\alpha \\Leftrightarrow \\beta}{(\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Rightarrow \\alpha)}$$\n$$\\frac{(\\alpha \\Rightarrow \\beta) \\wedge (\\beta \\Rightarrow \\alpha)}{\\alpha \\Leftrightarrow \\beta}$$\nBasically for all the other logical rules, we can make this same form as above^\n\n\nMonotonicity says that the set of entailed sentences can only increase as information is added to the KB. If KB $\\models \\alpha$ then KB $\\wedge \\beta \\models \\alpha$.\n\n\n\n\n__Resolution__: If $l_i$ and $m$ are complementary literaly (one is the negation of another), then we can eliminate them via __unit resolution__.\n\n\n$$\\frac{l_1 \\vee \\ldots l_k, m}{l_1\\vee l_{i-1} \\vee \\ldots \\vee l_{i+1} \\vee l_k}$$\n\n__Resolution Algorithm__: To show KB $\\models \\alpha$ we can show that KB $\\wedge \\neg \\alpha$ is unsatisfiable.\n\n\n- First convert (KB $\\wedge \\alpha$) into CNF\n\n\n- Then apply the resolution rule to the resulting clauses\n\n\n- Resolve every pair that contains complementary literals to produce a new clause\n\n\n- If that new clause isn't already present, then add it to the set\n\n\n- Continue the process until one of two things happens: (1) There are no clauses that can be added. In this case, the KB __does not__ entail $\\alpha$, \n(2) Two clauses resolve to yield the empty clause, in which case the KB __does__ entail $\\alpha$.\n \n\n## Module 7 Definitions\n* **Knowledge base** - a set of sentences that give us knowledge\n* **Inference** - deriving new sentences from old ones\n* **Entailment** - a sentence following logically from another sentence\n* **Sound** - true inferences\n* **Complete** - can derive any sentence that is entailed\n* **Atomic sentence** - just one single proposition symbol\n* **Logical equivalence** - two sentences are logically equivalent if they are true in the same models\n* **Valid** - if a sentence is true in all models\n* **Satisfiability** - if a sentence is true in some model\n* **Definite clause** - a disjunction of literals where only one is positive\n* **Horn clause** - a disjunction of literals where at most one is positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}