{
 "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",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "lzaavW96tcxM",
    "outputId": "7c5cdea4-fab7-49d0-daab-45049c3068af"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The example summary is 116 words long, so you could write an additional 384 words.\n"
     ]
    }
   ],
   "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)))"
   ]
  },
  {
   "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",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "8DvZ57A-djo1",
    "outputId": "0fba2813-5f70-45b4-a740-0e496effad3c"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 500\n",
      "The length in characters is 3030\n"
     ]
    }
   ],
   "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))"
   ]
  },
  {
   "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",
   "execution_count": 3,
   "metadata": {
    "id": "2RECnJArJew4"
   },
   "outputs": [],
   "source": [
    "name = \"\"\n",
    "permission = True\n",
    "anonymous = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GZZXyrV-xuAp"
   },
   "source": [
    "# Module 1 - Intro to AI"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "Y2NfE1CKxzS-"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
    "\n",
    "chapter1_1 = \"\"\"This section introduced four ascpets of AI: think humanly/rationaly and act humanly/rationaly.\n",
    "To act humanly, we usually need the machine to pass the turing test.\n",
    "To pass a turing test, the computer need the ability of NLP, Knowledge representation, Automated reasoning, Machine learning. \n",
    "To pass a total turing test, the computer need the ability of computer vision and speech recognition, Robotics.\n",
    "The difference between turing test and total turing test is that total turing test requires the machine to interact with humans.\n",
    "In our class, we focus on the aspect that acting rationaly. This is the most common approach to AI. We focus on make the \n",
    "agent do the right thing.'right' is defined by an objective.\"\"\" \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 = \"\"\"This section talked about the limits of AI from three aspects. \n",
    "1. human behaviors can never be captured in a formal set of rules.\n",
    "2. The machine might be able to out perform human in some specific tasks, but they cannot be exactly human.\n",
    "3. For any formal axiomatic framework F, there is a G(F) such that G(F) is a sentence of F but cannot be proved within F, and if F is consistent then G(F) is ture.\n",
    "\"\"\"\n",
    "chapter27_2 = \"\"\"This section talked about can machine really think.\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
    "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
    "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
    "chapter2_3 = \"\"\" Types of different task environment: FULLY OBSERVABLE VS. PARTIALLY OBSERVABLE, SINGLE-AGENT VS. MULTIAGENT,\n",
    "Deterministic vs. nondeterministic(nondeterministic is used for environment where no specific probabilities are given while stochastic is used when the porb is known.)\n",
    "EPISODIC VS. SEQUENTIAL, STATIC VS. DYNAMIC, DISCRETE VS. CONTINUOUS, KNOWN VS. UNKNOWN:\"\"\"\n",
    "chapter2_4 = \"\"\"This section introduced different kinds of agents: \\n\n",
    "Simple reflex agents: select actions on the basis of the current percept, ignoring the rest of the percept history. \\n\n",
    "Model-based reflex agents: an agent uses transition models and sensor models to allow itself to keep track of the state of the world, and this will make up the limitation of the agent's sensors. \\n\n",
    "Goal-based agents: it keeps track of a set of goals it is trying to achieve, and chooses an action that will (eventually) lead to the achievement of its goals. \\n\n",
    "Utility-based agents: it chooses the action that leads to the best expected utility, where expected utility is computed by averaging over all possible outcome states, weighted by the probability of the outcome. \\n\n",
    "An agent’s choice of action at a given instant depends only on its past percepts.\\n\n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module1_lecture_notes = \"\"\"Rational agents can only maximize expected performance instead of actual performance.\n",
    "A task environment is a problem specification for which the agent is a solution, \n",
    "it consists of four parts: Performance measure, Environment, Actuators, Sensors.\n",
    "A simple reflex agent is one that selects an action based on the current percept, and ignores the rest of the percept history.\n",
    "A problem-solving agent must plan ahead. It will consider a sequence of actions that form a path to a goal state. \n",
    "The computational process that it undertakes is called search.\"\"\"\n",
    "\n",
    "\n",
    "# Definitions of concepts from Module 1.\n",
    "# You can define any bolded term in the textbook, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 20 words long.\n",
    "module1_definitions = {\n",
    "    \"agent\" : \"anything that perceives its environment through sensors and can act on its environment through actuators\",\n",
    "    \"rational agent1\": \"an agent that always acts to get the best outcome\", \n",
    "    \"rational agent2\": \",but a rational agent is not guaranteed to find optimal solutions.\",\n",
    "    \"percept\" : \"the content an agent’s sensors are perceiving\",\n",
    "    \"agent function\" : \"an abstract function that maps any given percept to action\",\n",
    "    \"agent program\": \"a concrete implementation of the agent function with a physical system\",\n",
    "    \"omniscience\": \"maximize actual reward(impossible due to computational limitation)\",\n",
    "    \"Rule of thumb for performance measures\": \"design measurements according to what you want to be achieved, not how you think the agent should behave\",\n",
    "    \"model-free agent\": \"can learn policy without ever learning exactly how that action changes the environment.\",\n",
    "    \"performance element\": \"responsible for selecting external actions\",\n",
    "    \"learning element\": \"responsible for making improvements\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "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",
   "execution_count": 5,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 725
    },
    "id": "gYYeNcdM_maE",
    "outputId": "0caad8dd-ad20-4626-cb91-923d00b0fbab"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       "This section introduced four ascpets of AI: think humanly/rationaly and act humanly/rationaly.\n",
       "To act humanly, we usually need the machine to pass the turing test.\n",
       "To pass a turing test, the computer need the ability of NLP, Knowledge representation, Automated reasoning, Machine learning. \n",
       "To pass a total turing test, the computer need the ability of computer vision and speech recognition, Robotics.\n",
       "The difference between turing test and total turing test is that total turing test requires the machine to interact with humans.\n",
       "In our class, we focus on the aspect that acting rationaly. This is the most common approach to AI. We focus on make the \n",
       "agent do the right thing.'right' is defined by an objective.\n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       "This section talked about the limits of AI from three aspects. \n",
       "1. human behaviors can never be captured in a formal set of rules.\n",
       "2. The machine might be able to out perform human in some specific tasks, but they cannot be exactly human.\n",
       "3. For any formal axiomatic framework F, there is a G(F) such that G(F) is a sentence of F but cannot be proved within F, and if F is consistent then G(F) is ture.\n",
       "\n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       "This section talked about can machine really think.\n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       " Your summary here \n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       " Your summary here \n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       " Types of different task environment: FULLY OBSERVABLE VS. PARTIALLY OBSERVABLE, SINGLE-AGENT VS. MULTIAGENT,\n",
       "Deterministic vs. nondeterministic(nondeterministic is used for environment where no specific probabilities are given while stochastic is used when the porb is known.)\n",
       "EPISODIC VS. SEQUENTIAL, STATIC VS. DYNAMIC, DISCRETE VS. CONTINUOUS, KNOWN VS. UNKNOWN:\n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       "This section introduced different kinds of agents: \n",
       "\n",
       "Simple reflex agents: select actions on the basis of the current percept, ignoring the rest of the percept history. \n",
       "\n",
       "Model-based reflex agents: an agent uses transition models and sensor models to allow itself to keep track of the state of the world, and this will make up the limitation of the agent's sensors. \n",
       "\n",
       "Goal-based agents: it keeps track of a set of goals it is trying to achieve, and chooses an action that will (eventually) lead to the achievement of its goals. \n",
       "\n",
       "Utility-based agents: it chooses the action that leads to the best expected utility, where expected utility is computed by averaging over all possible outcome states, weighted by the probability of the outcome. \n",
       "\n",
       "An agent’s choice of action at a given instant depends only on its past percepts.\n",
       "\n",
       "\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       "Rational agents can only maximize expected performance instead of actual performance.\n",
       "A task environment is a problem specification for which the agent is a solution, \n",
       "it consists of four parts: Performance measure, Environment, Actuators, Sensors.\n",
       "A simple reflex agent is one that selects an action based on the current percept, and ignores the rest of the percept history.\n",
       "A problem-solving agent must plan ahead. It will consider a sequence of actions that form a path to a goal state. \n",
       "The computational process that it undertakes is called search.\n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - anything that perceives its environment through sensors and can act on its environment through actuators\n",
       "* **Rational agent1** - an agent that always acts to get the best outcome\n",
       "* **Rational agent2** - ,but a rational agent is not guaranteed to find optimal solutions.\n",
       "* **Percept** - the content an agent’s sensors are perceiving\n",
       "* **Agent function** - an abstract function that maps any given percept to action\n",
       "* **Agent program** - a concrete implementation of the agent function with a physical system\n",
       "* **Omniscience** - maximize actual reward(impossible due to computational limitation)\n",
       "* **Rule of thumb for performance measures** - design measurements according to what you want to be achieved, not how you think the agent should behave\n",
       "* **Model-free agent** - can learn policy without ever learning exactly how that action changes the environment.\n",
       "* **Performance element** - responsible for selecting external actions\n",
       "* **Learning element** - responsible for making improvements\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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",
    "    print(warnings)\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",
    "    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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9xRbdqDox2zD"
   },
   "source": [
    "#Module 2 - Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "DpBvu7EMx7sy"
   },
   "outputs": [],
   "source": [
    "# No readings for this module.  Instead you can summarize the lecture instead.\n",
    "\n",
    "# Lecture notes \n",
    "module2_lecture_notes = \"\"\"Benefits of using generators:\\n\n",
    "Less code than writing a standard iterator\n",
    "Maintains local state automatically\n",
    "Values are computed one at a time, as they’re needed Avoids storing the entire sequence in memory\n",
    "Good for aggregating (summing, counting) items. One pass. Crucial for infinite sequences\n",
    "Bad if you need to inspect the individual values\"\"\"\n",
    "\n",
    "# Each definition should be at most 20 words long.\n",
    "module2_definitions = {\n",
    "\"mutability\" : \"without copying, change one will affect the other\",\n",
    "\"list comprehension\": \"[expression for name in list if filter]\"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 209
    },
    "id": "ydOK__lwWgdp",
    "outputId": "237a5fc3-0d0f-4240-8ebf-655b10675954"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       "Benefits of using generators:\n",
       "\n",
       "Less code than writing a standard iterator\n",
       "Maintains local state automatically\n",
       "Values are computed one at a time, as they’re needed Avoids storing the entire sequence in memory\n",
       "Good for aggregating (summing, counting) items. One pass. Crucial for infinite sequences\n",
       "Bad if you need to inspect the individual values\n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Mutability** - without copying, change one will affect the other\n",
       "* **List comprehension** - [expression for name in list if filter]\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "46MQLR-Gx8dZ"
   },
   "source": [
    "#Module 3 - Search Problems"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "BN0b1eVYx-nd"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
    "chapter3_1 = \"\"\"The following six elements are needed to formulate a search problem:\\n\n",
    "state space, initial state, terminal state, actions, trainsition model, action cost function.\"\"\"\n",
    "chapter3_2 = \"\"\"This section introduced us to several different search problems.\"\"\"\n",
    "chapter3_3 = \"\"\"An overview of search algorithms. Four aspects to evaluate a search algorithm: completeness, optimality, space complexity, time complexity.\\n\n",
    "Tree search costs less memory but more time than graph search.\\n\n",
    "Completeness: Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not?\\n\n",
    "Optimality: Does it find a solution with the lowest path cost of all solutions?\\n\"\"\"\n",
    "chapter3_4 = \"\"\"BFS(this uses late goal testing, bfs can use early goal testing):\\n\n",
    "<img src=./search_algo.png width=600 height=100 />\\n\n",
    "DFS: frontier changes to stack\\n\n",
    "UCS: frontier changes to priority queue\\n \n",
    "The following is the comparison between different search algos.\\n\n",
    "<img src=./comparison.png width=600 height=100 />\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Definitions of concepts from Module 3.\n",
    "# You can define any bolded term in the textbook, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 20 words long.\n",
    "module3_definitions = {\n",
    "    \"problem-solving agent\" : \"an agent that can formulate a plan via search, it uses atomic representation\",\n",
    "    \"optimal solution\": \"the solution has the lowest path cost among all solutions\",\n",
    "    \"tree/graph search\": \"a graph search checks redundant paths while tree search doesn't\",\n",
    "    \"early goal test\": \"checking whether a node is a solution as soon as it is generated\",\n",
    "    \"late goal test\": \"checking whether a node is a solution when it is popped\",\n",
    "    \"uninformed\": \"only has access to the problem definition\",\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 474
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "21b42a50-b270-439d-ac74-40c061bf0bde"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       "The following six elements are needed to formulate a search problem:\n",
       "\n",
       "state space, initial state, terminal state, actions, trainsition model, action cost function.\n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       "This section introduced us to several different search problems.\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       "An overview of search algorithms. Four aspects to evaluate a search algorithm: completeness, optimality, space complexity, time complexity.\n",
       "\n",
       "Tree search costs less memory but more time than graph search.\n",
       "\n",
       "Completeness: Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not?\n",
       "\n",
       "Optimality: Does it find a solution with the lowest path cost of all solutions?\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       "BFS(this uses late goal testing, bfs can use early goal testing):\n",
       "\n",
       "<img src=./search_algo.png width=600 height=100 />\n",
       "\n",
       "DFS: frontier changes to stack\n",
       "\n",
       "UCS: frontier changes to priority queue\n",
       " \n",
       "The following is the comparison between different search algos.\n",
       "\n",
       "<img src=./comparison.png width=600 height=100 />\n",
       "\n",
       "\n",
       "\n",
       "## Module 3 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search, it uses atomic representation\n",
       "* **Optimal solution** - the solution has the lowest path cost among all solutions\n",
       "* **Tree/graph search** - a graph search checks redundant paths while tree search doesn't\n",
       "* **Early goal test** - checking whether a node is a solution as soon as it is generated\n",
       "* **Late goal test** - checking whether a node is a solution when it is popped\n",
       "* **Uninformed** - only has access to the problem definition\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WHREsHSSyA-h"
   },
   "source": [
    "#Module 4 - Informed Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "tuFC8w7CyCns"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
    "chapter3_5 = \"\"\"A* search:\\n\n",
    "<img src=./A_star.png width=600 height=100 />\\n\n",
    "With an admissible heuristic(also called optmistic), A* search is optimal.\\n\n",
    "With a consistent heuristic, A* search will only put each node once into the frontier.\\n\n",
    "One problem with A* search is the memeory issue because sometimes it will put the same node several times into the frontier.\\n\n",
    "A* with a consistent heuristic is optimally efficient\\n\"\"\"\n",
    "chapter3_6 = \"\"\"For any node, if $h_1(n) \\geq h_2(n)$, then we say $h_1$ dominates $h_2$\\n\n",
    "If the total number of nodes generated by A* for a particular problem is N and the solution depth is d, \n",
    "then b* is the branching factor that a uniform tree of depth would have to have in order to contain nodes. \n",
    "So we have: $N+1=1+b^*+(b^*)^2 ... +(b^*)^d$\\n\n",
    "The performance of heuristic search algorithms depends on the quality of the heuristic function. \n",
    "One can sometimes construct good heuristics by relaxing the problem definition, \n",
    "by storing precomputed solution costs for subproblems in a pattern database, by defining landmarks, \n",
    "or by learning from experience with the problem class.\\n\n",
    "IDA* (iterative deepening A* search) is an iterative deepening version of A*, and\n",
    "thus adresses the space complexity issue.\\n\n",
    "RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are\n",
    "robust, optimal search algorithms that use limited amounts of memory; given enough\n",
    "time, they can solve problems for which A* runs out of memory.\\n\n",
    "BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and\n",
    "suboptimal, but it often finds reasonably good solutions and runs faster than complete searches.\\n\n",
    "WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.(not optimal, but complete)\\n\n",
    "IDA*, SMA*, and RBFS are optimal search algorithms which are more space efficient.\\n\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module4_lecture_notes = \"\"\"\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module4_definitions = {\n",
    "    \"admissible heuristic\": \"one that never overestimates the cost to reach a goal\",   \n",
    "    \"consistent heuristic\": \"$h(n)\\leq c(n, a, n^{\\prime}) + h(n^{\\prime})$\",\n",
    "    \"relaxed problem\": \"A problem with fewer restrictions on actions\",\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 341
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "822c50fc-17b3-444f-d7dd-83cdfb49f6d9"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       "A* search:\n",
       "\n",
       "<img src=./A_star.png width=600 height=100 />\n",
       "\n",
       "With an admissible heuristic(also called optmistic), A* search is optimal.\n",
       "\n",
       "With a consistent heuristic, A* search will only put each node once into the frontier.\n",
       "\n",
       "One problem with A* search is the memeory issue because sometimes it will put the same node several times into the frontier.\n",
       "\n",
       "A* with a consistent heuristic is optimally efficient\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       "For any node, if $h_1(n) \\geq h_2(n)$, then we say $h_1$ dominates $h_2$\n",
       "\n",
       "If the total number of nodes generated by A* for a particular problem is N and the solution depth is d, \n",
       "then b* is the branching factor that a uniform tree of depth would have to have in order to contain nodes. \n",
       "So we have: $N+1=1+b^*+(b^*)^2 ... +(b^*)^d$\n",
       "\n",
       "The performance of heuristic search algorithms depends on the quality of the heuristic function. \n",
       "One can sometimes construct good heuristics by relaxing the problem definition, \n",
       "by storing precomputed solution costs for subproblems in a pattern database, by defining landmarks, \n",
       "or by learning from experience with the problem class.\n",
       "\n",
       "IDA* (iterative deepening A* search) is an iterative deepening version of A*, and\n",
       "thus adresses the space complexity issue.\n",
       "\n",
       "RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are\n",
       "robust, optimal search algorithms that use limited amounts of memory; given enough\n",
       "time, they can solve problems for which A* runs out of memory.\n",
       "\n",
       "BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and\n",
       "suboptimal, but it often finds reasonably good solutions and runs faster than complete searches.\n",
       "\n",
       "WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.(not optimal, but complete)\n",
       "\n",
       "IDA*, SMA*, and RBFS are optimal search algorithms which are more space efficient.\n",
       "\n",
       "\n",
       "\n",
       "## Module 4 Lecture Notes\n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Admissible heuristic** - one that never overestimates the cost to reach a goal\n",
       "* **Consistent heuristic** - $h(n)\\leq c(n, a, n^{\\prime}) + h(n^{\\prime})$\n",
       "* **Relaxed problem** - A problem with fewer restrictions on actions\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F3FPMzG9yUls"
   },
   "source": [
    "#Module 5 - Adversarial Search and Games"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
    "chapter5_1 = \"\"\"A game can be defined by the initial state (how the board is set up), \n",
    "the legal actions in each state, \n",
    "the result of each action, \n",
    "a terminal test (which says when the game is over), \n",
    "and a utility function that applies to terminal states to say who won and what the final score is.\\n\n",
    "A game is differed from search problems in that it has multiple agents.\"\"\"\n",
    "chapter5_2 = \"\"\"In two-player, discrete, deterministic, turn-taking zero-sum games with perfect\n",
    "information, the minimax algorithm can select optimal moves by a depth-first\n",
    "enumeration of the game tree.\\n \n",
    "The value at that node is the value of the best terminal state reach by both player playing optimally. \n",
    "That means that the current player tries to maximize the score and the other player tries to minimize it.\\n\n",
    "\"\"\"\n",
    "chapter5_3 = \"\"\"The alpha–beta search algorithm computes the same optimal move as minimax, but\n",
    "achieves much greater efficiency by eliminating subtrees that are provably irrelevant.\n",
    "Usually, it is not feasible to consider the whole game tree (even with alpha–beta), so we\n",
    "need to cut the search off at some point and apply a heuristic evaluation function that estimates the utility of a state.\"\"\"\n",
    "chapter5_5 = \"\"\"Games of chance can be handled by expectiminimax, \n",
    "an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children, \n",
    "weighted by the probability of each child.\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
    "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
    "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
    "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module5_definitions = {\n",
    "    \"Stochastic games\" : \"games in which the results of a movement is not deterministic.\",\n",
    "    \"Alpha\": \"highest-value we have found so far at any choice point along the path for MAX.\",\n",
    "    \"Beta\": \"lowest-value we have found so far at any choice point along the path for MIN.\",\n",
    "    \"perfect information\": \"same for fully observable\",\n",
    "    \"zero-sum\": \"what is good for one player is just as bad for the other, no win-win\",\n",
    "    \"complexity of minimax\": \"$O(b^m)$\",\n",
    "    \"complexity of perfect order alpha-beta pruning\": \"$O(b^{m/2})$\",\n",
    "    \"Type A strategy\": \"considers all possible moves to a certain depth in the search tree, wide but shallow.\",\n",
    "    \"A Type B strategy\": \"ignores moves that look bad, and follows promising lines as far as possible. deep but narrow\",\n",
    "    \"cutoff test\": \"decides when to cut off the search\",\n",
    "    \"quiescent1\": \"The evaluation function should be applied only to positions that are quiescent\",\n",
    "    \"quiescent2\": \"A move is quiescent if there is no pending move that would wildly swing the valuation\",\n",
    "    \"horizon effect\": \"when an agent try to erroneously delay the inevitable\",\n",
    "    \"Forward pruning\": \"prunes moves that appear to be poor moves(but still possiblely good)(beam search)\",\n",
    "    \"utility function\": \"assigns a single number to express the desirability of a state.\",\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 674
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "e9f5458e-82b4-4fa5-c56a-a0748aba7eaf"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       "A game can be defined by the initial state (how the board is set up), \n",
       "the legal actions in each state, \n",
       "the result of each action, \n",
       "a terminal test (which says when the game is over), \n",
       "and a utility function that applies to terminal states to say who won and what the final score is.\n",
       "\n",
       "A game is differed from search problems in that it has multiple agents.\n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       "In two-player, discrete, deterministic, turn-taking zero-sum games with perfect\n",
       "information, the minimax algorithm can select optimal moves by a depth-first\n",
       "enumeration of the game tree.\n",
       " \n",
       "The value at that node is the value of the best terminal state reach by both player playing optimally. \n",
       "That means that the current player tries to maximize the score and the other player tries to minimize it.\n",
       "\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       "The alpha–beta search algorithm computes the same optimal move as minimax, but\n",
       "achieves much greater efficiency by eliminating subtrees that are provably irrelevant.\n",
       "Usually, it is not feasible to consider the whole game tree (even with alpha–beta), so we\n",
       "need to cut the search off at some point and apply a heuristic evaluation function that estimates the utility of a state.\n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       "Games of chance can be handled by expectiminimax, \n",
       "an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children, \n",
       "weighted by the probability of each child.\n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       " Your summary here \n",
       "\n",
       "## Module 5 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Stochastic games** - games in which the results of a movement is not deterministic.\n",
       "* **Alpha** - highest-value we have found so far at any choice point along the path for MAX.\n",
       "* **Beta** - lowest-value we have found so far at any choice point along the path for MIN.\n",
       "* **Perfect information** - same for fully observable\n",
       "* **Zero-sum** - what is good for one player is just as bad for the other, no win-win\n",
       "* **Complexity of minimax** - $O(b^m)$\n",
       "* **Complexity of perfect order alpha-beta pruning** - $O(b^{m/2})$\n",
       "* **Type a strategy** - considers all possible moves to a certain depth in the search tree, wide but shallow.\n",
       "* **A type b strategy** - ignores moves that look bad, and follows promising lines as far as possible. deep but narrow\n",
       "* **Cutoff test** - decides when to cut off the search\n",
       "* **Quiescent1** - The evaluation function should be applied only to positions that are quiescent\n",
       "* **Quiescent2** - A move is quiescent if there is no pending move that would wildly swing the valuation\n",
       "* **Horizon effect** - when an agent try to erroneously delay the inevitable\n",
       "* **Forward pruning** - prunes moves that appear to be poor moves(but still possiblely good)(beam search)\n",
       "* **Utility function** - assigns a single number to express the desirability of a state.\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "qVSQhTVSyYYO"
   },
   "source": [
    "#Module 6 - \"Constraint Satisfaction Problems\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "Wm4mfW82yaRH"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
    "chapter6_1 = \"\"\"CSPs represent a state with a set of variable/value pairs\\n\n",
    "CSPs represent the conditions for a solution with a set of constraints on the variables\\n\n",
    "In search problems, states are black boxes with a transition model to move between boxes, while in CSP the agent can see inside the states and move accordingly.\\n\n",
    "There is no existing solution for general nonlinear constraints for integers.\\n\n",
    "CSPs can rule out variable assignments using search and inference.\\n\"\"\"\n",
    "chapter6_2 = \"\"\"We can do constraint propagation(using the constraints to rule out variable assignment) base on local consistency.\\n\n",
    "A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\\n\n",
    "The key behind inference in CSPs is enforcing k-consistency(1-consistency is node consistency, 2-consistency is arc-consistency, 3-consistency is path-consistency).\\n\n",
    "A CSP is strong k-consistent if it is k-consistent, k-1 consistent... 1-consistent.\\n\n",
    "AC-3 is an algorithm for enforcing arc consistency.\\n\n",
    "The following is the persudocode for AC-3:\n",
    "```\n",
    "def remove_inconsistent_values(self, cell1, cell2):\n",
    "    cell2_values = self.get_values(cell2).copy()\n",
    "    removed = False\n",
    "    if len(cell2_values) == 1:\n",
    "        element = cell2_values.pop()\n",
    "        if element in self.board[cell1]:\n",
    "            self.board[cell1].remove(element)\n",
    "            removed = True\n",
    "    return removed\n",
    "    \n",
    "def infer_ac3(self):\n",
    "    q = queue.Queue()\n",
    "    for arc in self.ARCS:\n",
    "        q.put(arc)\n",
    "    update = False\n",
    "    while not q.empty():\n",
    "        cell1, cell2 = q.get()\n",
    "        removed = self.remove_inconsistent_values(cell1, cell2)\n",
    "        if removed:\n",
    "            update = True\n",
    "            for neighbour in get_neighbour(cell1):\n",
    "                if neighbour != cell2:\n",
    "                    q.put((neighbour, cell1))\n",
    "    return update\n",
    "```\n",
    "Assume a CSP with n variables, each with domain size at most d, and with c binary constraints (arcs). Since each arc can\n",
    "only be inserted into the queue at most d times(as each variable has at most d values to delete), and checking consistency of an arc\n",
    "takes $O(d^2)$ times, so the time complexity for ac-3 is $O(cd^3)$. Note that since $c<n(n-1)$, the upper bound for time complexity is $O(n^2d^3)$\n",
    "\"\"\"\n",
    "chapter6_3 = \"\"\"Backtracking search is a form of depth first search commonly used for solving CSPs.\\n\n",
    "Backtracking occurs when no legal assignment can be found for a variable.\\n\n",
    "MRV(Minimum Remaining Value) chooses the variable with the fewest “legal” values.\\n\n",
    "degree heuristic chooses the variable that is involved in the largest number of constraints on other unassigned variables.\\n\n",
    "least-constraining-value chooses the value for a variable that rules out the fewest choices for the neighboring variables in the constraint graph.\\n\n",
    "The difference between AC-3 and forward checking is that forward checking only maintaining arc-consistency with neighbours when the value of a node is removed, \n",
    "while AC-3 repeatedly enforcing arc-consistency whenever there is a value for a node is deleted.\\n\n",
    "MAC vs forward checking: MAC recursively propogrates constraints, whereas forward checking does not.\\n\n",
    "MAC vs AC-3: MAC is a way of interleaving search and inference. AC-3 is pure inference.\\n\n",
    "Constraint learning records the conflicts as they are encountered in the search in order to avoid the same conflict later.\\n\n",
    "\n",
    "\"\"\"\n",
    "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
    "chapter6_5 = \"\"\"\n",
    "Solving an arbitrary CSP takes exponential time in the number of variables.\\n\n",
    "Tree-CSP can be solved in $O(nd^2)$ where n is the number of variables and d is the size of the largest domain, which is linear to the number of variables.\\n\n",
    "We can decompose the problem into small tree-like CSP.\\n\n",
    "### Cutset Conditioning(used to reduce a general CSP to a tree structured one):\\n\n",
    "1. Choose a subset of the CSP’s variables such that the constraint graph becomes a tree after removal of S. \n",
    "S is called a cycle cutset.\\n\n",
    "2. For each possible assignment to the variables in that satisfies all constraints on S,\\n\n",
    "\\t a. remove from the domains of the remaining variables any values that are\n",
    "inconsistent with the assignment for S, and\\n\n",
    "\\t b. if the remaining CSP has a solution, return it together with the assignment for S.\\n\n",
    "Suppose the cycle cutset size is c, we need to try $d^c$ different assignments of values for the cutset, and the remaining\n",
    "tree problem of size $n-c$ needs $O((n-c)d^2)$, so the total time complexity for cutset conditioning is $O(d^c(n-c)d^2)$.\n",
    "If the graph is \"nearly a tree\", meaning that c is small, then the complexity would be good.\\n\n",
    "\n",
    "### Tree decomposition(transform a CSP into a tree of subproblems):\\n\n",
    "We can transform the original graph into a tree where each nodes contains several original vertices(variable) of the graph and satisfy the following condition:\n",
    "1. Each original variable appears in at least one node.\\n\n",
    "2. If two variables are connected by some constraints in the original graph, then it should appear together in at least one node.\\n\n",
    "3. If one variable appears at the same time in two node, then it should also appear in every node that is in the path between these two node.\\n\n",
    "Once we get the tree, we can solve the problem in $O(nd^2)$ where n is the number of nodes and d is the size of largest domain.\n",
    "(note that the domain here is a tuple of possible values for variables inside the node). \n",
    "The complexity is reasonable when we have a small d, when the tree width(the number of variables in one node) is small.\\n\n",
    "Tree decomposition is more efficient in time than cutset conditioning because whenever you have a cycle-cutset of size c, \n",
    "there is also a tree width of size w < c+1 and it may be far smaller in some cases. \n",
    "but the advantage of the cycle-cutset approach is that it can be executed in linear memory, while tree decomposition requires memory exponential in tree width w.\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module6_definitions = {\n",
    "    \"unary constraint\" : \"constraint for a single variable\", \n",
    "    \"binary constraint\": \"constraint relates two variables\",\n",
    "    \"global constraint\": \"constraint involving an arbitrary number of variables\",\n",
    "    \"constraint propagation\": \"using the constraints to reduce the number of legal values for a variable\"\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 541
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "f51aeef3-74ac-4ec6-b389-54aae53b8cbc"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       "CSPs represent a state with a set of variable/value pairs\n",
       "\n",
       "CSPs represent the conditions for a solution with a set of constraints on the variables\n",
       "\n",
       "In search problems, states are black boxes with a transition model to move between boxes, while in CSP the agent can see inside the states and move accordingly.\n",
       "\n",
       "There is no existing solution for general nonlinear constraints for integers.\n",
       "\n",
       "CSPs can rule out variable assignments using search and inference.\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       "We can do constraint propagation(using the constraints to rule out variable assignment) base on local consistency.\n",
       "\n",
       "A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n",
       "\n",
       "The key behind inference in CSPs is enforcing k-consistency(1-consistency is node consistency, 2-consistency is arc-consistency, 3-consistency is path-consistency).\n",
       "\n",
       "A CSP is strong k-consistent if it is k-consistent, k-1 consistent... 1-consistent.\n",
       "\n",
       "AC-3 is an algorithm for enforcing arc consistency.\n",
       "\n",
       "The following is the persudocode for AC-3:\n",
       "```\n",
       "def remove_inconsistent_values(self, cell1, cell2):\n",
       "    cell2_values = self.get_values(cell2).copy()\n",
       "    removed = False\n",
       "    if len(cell2_values) == 1:\n",
       "        element = cell2_values.pop()\n",
       "        if element in self.board[cell1]:\n",
       "            self.board[cell1].remove(element)\n",
       "            removed = True\n",
       "    return removed\n",
       "    \n",
       "def infer_ac3(self):\n",
       "    q = queue.Queue()\n",
       "    for arc in self.ARCS:\n",
       "        q.put(arc)\n",
       "    update = False\n",
       "    while not q.empty():\n",
       "        cell1, cell2 = q.get()\n",
       "        removed = self.remove_inconsistent_values(cell1, cell2)\n",
       "        if removed:\n",
       "            update = True\n",
       "            for neighbour in get_neighbour(cell1):\n",
       "                if neighbour != cell2:\n",
       "                    q.put((neighbour, cell1))\n",
       "    return update\n",
       "```\n",
       "Assume a CSP with n variables, each with domain size at most d, and with c binary constraints (arcs). Since each arc can\n",
       "only be inserted into the queue at most d times(as each variable has at most d values to delete), and checking consistency of an arc\n",
       "takes $O(d^2)$ times, so the time complexity for ac-3 is $O(cd^3)$. Note that since $c<n(n-1)$, the upper bound for time complexity is $O(n^2d^3)$\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       "Backtracking search is a form of depth first search commonly used for solving CSPs.\n",
       "\n",
       "Backtracking occurs when no legal assignment can be found for a variable.\n",
       "\n",
       "MRV(Minimum Remaining Value) chooses the variable with the fewest “legal” values.\n",
       "\n",
       "degree heuristic chooses the variable that is involved in the largest number of constraints on other unassigned variables.\n",
       "\n",
       "least-constraining-value chooses the value for a variable that rules out the fewest choices for the neighboring variables in the constraint graph.\n",
       "\n",
       "The difference between AC-3 and forward checking is that forward checking only maintaining arc-consistency with neighbours when the value of a node is removed, \n",
       "while AC-3 repeatedly enforcing arc-consistency whenever there is a value for a node is deleted.\n",
       "\n",
       "MAC vs forward checking: MAC recursively propogrates constraints, whereas forward checking does not.\n",
       "\n",
       "MAC vs AC-3: MAC is a way of interleaving search and inference. AC-3 is pure inference.\n",
       "\n",
       "Constraint learning records the conflicts as they are encountered in the search in order to avoid the same conflict later.\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       "\n",
       "Solving an arbitrary CSP takes exponential time in the number of variables.\n",
       "\n",
       "Tree-CSP can be solved in $O(nd^2)$ where n is the number of variables and d is the size of the largest domain, which is linear to the number of variables.\n",
       "\n",
       "We can decompose the problem into small tree-like CSP.\n",
       "\n",
       "### Cutset Conditioning(used to reduce a general CSP to a tree structured one):\n",
       "\n",
       "1. Choose a subset of the CSP’s variables such that the constraint graph becomes a tree after removal of S. \n",
       "S is called a cycle cutset.\n",
       "\n",
       "2. For each possible assignment to the variables in that satisfies all constraints on S,\n",
       "\n",
       "\t a. remove from the domains of the remaining variables any values that are\n",
       "inconsistent with the assignment for S, and\n",
       "\n",
       "\t b. if the remaining CSP has a solution, return it together with the assignment for S.\n",
       "\n",
       "Suppose the cycle cutset size is c, we need to try $d^c$ different assignments of values for the cutset, and the remaining\n",
       "tree problem of size $n-c$ needs $O((n-c)d^2)$, so the total time complexity for cutset conditioning is $O(d^c(n-c)d^2)$.\n",
       "If the graph is \"nearly a tree\", meaning that c is small, then the complexity would be good.\n",
       "\n",
       "\n",
       "### Tree decomposition(transform a CSP into a tree of subproblems):\n",
       "\n",
       "We can transform the original graph into a tree where each nodes contains several original vertices(variable) of the graph and satisfy the following condition:\n",
       "1. Each original variable appears in at least one node.\n",
       "\n",
       "2. If two variables are connected by some constraints in the original graph, then it should appear together in at least one node.\n",
       "\n",
       "3. If one variable appears at the same time in two node, then it should also appear in every node that is in the path between these two node.\n",
       "\n",
       "Once we get the tree, we can solve the problem in $O(nd^2)$ where n is the number of nodes and d is the size of largest domain.\n",
       "(note that the domain here is a tuple of possible values for variables inside the node). \n",
       "The complexity is reasonable when we have a small d, when the tree width(the number of variables in one node) is small.\n",
       "\n",
       "Tree decomposition is more efficient in time than cutset conditioning because whenever you have a cycle-cutset of size c, \n",
       "there is also a tree width of size w < c+1 and it may be far smaller in some cases. \n",
       "but the advantage of the cycle-cutset approach is that it can be executed in linear memory, while tree decomposition requires memory exponential in tree width w.\n",
       "\n",
       "\n",
       "## Module 6 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Unary constraint** - constraint for a single variable\n",
       "* **Binary constraint** - constraint relates two variables\n",
       "* **Global constraint** - constraint involving an arbitrary number of variables\n",
       "* **Constraint propagation** - using the constraints to reduce the number of legal values for a variable\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RYESi2kMybL8"
   },
   "source": [
    "#Module 7 - Logical Agents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
    "\n",
    "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
    "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
    "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
    "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
    "chapter7_5 = \"\"\"\n",
    "Commonly used equivalence:\\n\n",
    "<img src=./equivalence.png width=600 height=100 />\\n\n",
    "Resolution:\\n\n",
    "$\\\\frac{(P\\\\lor \\\\lnot Q \\\\lor R) \\\\land (\\\\lnot P \\\\lor Q)}{Q \\\\lor \\\\lnot Q \\\\lor R}$\n",
    "\n",
    "We should note here only one pair can be resolved.\\n\n",
    "Resolution algorithm:\\n\n",
    "<img src=./resolution_algo.png width=600 height=100 />\\n\n",
    "Resolution is complete.\\n\n",
    "Problems with Horn clauses can be done in linear time with respect to the size of the KB.\\n\n",
    "\n",
    "Forward Chaining is a kind of data-driven reasoning.\\n\n",
    "An agent can start with known data, adding premises as new percepts come in, \n",
    "and then incrementally apply the forward chaining algorithm to derive new conclusions. \n",
    "It doesn’t have to have a specific query in mind to do so.\\n\n",
    "Forward Chaining persudocode:\\n\n",
    "<img src=./forward_chaining.png width=600 height=100 />\\n\n",
    "Backward chaining works backwards from a query.\\n \n",
    "If the query is known to be true, then no work is needed. \n",
    "Otherwise, the algorithm finds implications in the KB whose conclusions is the query. \n",
    "If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\\n\n",
    "Backward chaining is a form of goal-directed reasoning.\n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module7_definitions = {\n",
    "    \"knowledge-based agents\" : \"use a process of reasoning over an internal representation of knowledge to decide what actions to take.\",  \n",
    "    \"knowledge base\": \"a set of sentences expressed in knowledge representation language and represents some assertion about the world.\",\n",
    "    \"definite clause\": \"disjunction of literals where exactly one is positive\",\n",
    "    \"horn clause\": \"disjunction of literals of which at most one is positive\",\n",
    "    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 541
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "fd406b8c-6eaa-4be5-be5f-3639d4b7fa43"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/markdown": [
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       " Your summary here \n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       "\n",
       "Commonly used equivalence:\n",
       "\n",
       "<img src=./equivalence.png width=600 height=100 />\n",
       "\n",
       "Resolution:\n",
       "\n",
       "$\\frac{(P\\lor \\lnot Q \\lor R) \\land (\\lnot P \\lor Q)}{Q \\lor \\lnot Q \\lor R}$\n",
       "\n",
       "We should note here only one pair can be resolved.\n",
       "\n",
       "Resolution algorithm:\n",
       "\n",
       "<img src=./resolution_algo.png width=600 height=100 />\n",
       "\n",
       "Resolution is complete.\n",
       "\n",
       "Problems with Horn clauses can be done in linear time with respect to the size of the KB.\n",
       "\n",
       "\n",
       "Forward Chaining is a kind of data-driven reasoning.\n",
       "\n",
       "An agent can start with known data, adding premises as new percepts come in, \n",
       "and then incrementally apply the forward chaining algorithm to derive new conclusions. \n",
       "It doesn’t have to have a specific query in mind to do so.\n",
       "\n",
       "Forward Chaining persudocode:\n",
       "\n",
       "<img src=./forward_chaining.png width=600 height=100 />\n",
       "\n",
       "Backward chaining works backwards from a query.\n",
       " \n",
       "If the query is known to be true, then no work is needed. \n",
       "Otherwise, the algorithm finds implications in the KB whose conclusions is the query. \n",
       "If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n",
       "\n",
       "Backward chaining is a form of goal-directed reasoning.\n",
       "\n",
       "\n",
       "## Module 7 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge-based agents** - use a process of reasoning over an internal representation of knowledge to decide what actions to take.\n",
       "* **Knowledge base** - a set of sentences expressed in knowledge representation language and represents some assertion about the world.\n",
       "* **Definite clause** - disjunction of literals where exactly one is positive\n",
       "* **Horn clause** - disjunction of literals of which at most one is positive\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "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",
   "execution_count": 18,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 3366
    },
    "id": "T3cm1WV542_a",
    "outputId": "a929c6c6-b72b-4fd8-bd35-a014674c9230"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       "This section introduced four ascpets of AI: think humanly/rationaly and act humanly/rationaly.\n",
       "To act humanly, we usually need the machine to pass the turing test.\n",
       "To pass a turing test, the computer need the ability of NLP, Knowledge representation, Automated reasoning, Machine learning. \n",
       "To pass a total turing test, the computer need the ability of computer vision and speech recognition, Robotics.\n",
       "The difference between turing test and total turing test is that total turing test requires the machine to interact with humans.\n",
       "In our class, we focus on the aspect that acting rationaly. This is the most common approach to AI. We focus on make the \n",
       "agent do the right thing.'right' is defined by an objective.\n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       "This section talked about the limits of AI from three aspects. \n",
       "1. human behaviors can never be captured in a formal set of rules.\n",
       "2. The machine might be able to out perform human in some specific tasks, but they cannot be exactly human.\n",
       "3. For any formal axiomatic framework F, there is a G(F) such that G(F) is a sentence of F but cannot be proved within F, and if F is consistent then G(F) is ture.\n",
       "\n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       "This section talked about can machine really think.\n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       " Your summary here \n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       " Your summary here \n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       " Types of different task environment: FULLY OBSERVABLE VS. PARTIALLY OBSERVABLE, SINGLE-AGENT VS. MULTIAGENT,\n",
       "Deterministic vs. nondeterministic(nondeterministic is used for environment where no specific probabilities are given while stochastic is used when the porb is known.)\n",
       "EPISODIC VS. SEQUENTIAL, STATIC VS. DYNAMIC, DISCRETE VS. CONTINUOUS, KNOWN VS. UNKNOWN:\n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       "This section introduced different kinds of agents: \n",
       "\n",
       "Simple reflex agents: select actions on the basis of the current percept, ignoring the rest of the percept history. \n",
       "\n",
       "Model-based reflex agents: an agent uses transition models and sensor models to allow itself to keep track of the state of the world, and this will make up the limitation of the agent's sensors. \n",
       "\n",
       "Goal-based agents: it keeps track of a set of goals it is trying to achieve, and chooses an action that will (eventually) lead to the achievement of its goals. \n",
       "\n",
       "Utility-based agents: it chooses the action that leads to the best expected utility, where expected utility is computed by averaging over all possible outcome states, weighted by the probability of the outcome. \n",
       "\n",
       "An agent’s choice of action at a given instant depends only on its past percepts.\n",
       "\n",
       "\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       "Rational agents can only maximize expected performance instead of actual performance.\n",
       "A task environment is a problem specification for which the agent is a solution, \n",
       "it consists of four parts: Performance measure, Environment, Actuators, Sensors.\n",
       "A simple reflex agent is one that selects an action based on the current percept, and ignores the rest of the percept history.\n",
       "A problem-solving agent must plan ahead. It will consider a sequence of actions that form a path to a goal state. \n",
       "The computational process that it undertakes is called search.\n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - anything that perceives its environment through sensors and can act on its environment through actuators\n",
       "* **Rational agent1** - an agent that always acts to get the best outcome\n",
       "* **Rational agent2** - ,but a rational agent is not guaranteed to find optimal solutions.\n",
       "* **Percept** - the content an agent’s sensors are perceiving\n",
       "* **Agent function** - an abstract function that maps any given percept to action\n",
       "* **Agent program** - a concrete implementation of the agent function with a physical system\n",
       "* **Omniscience** - maximize actual reward(impossible due to computational limitation)\n",
       "* **Rule of thumb for performance measures** - design measurements according to what you want to be achieved, not how you think the agent should behave\n",
       "* **Model-free agent** - can learn policy without ever learning exactly how that action changes the environment.\n",
       "* **Performance element** - responsible for selecting external actions\n",
       "* **Learning element** - responsible for making improvements\n",
       "\n",
       "\n",
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       "Benefits of using generators:\n",
       "\n",
       "Less code than writing a standard iterator\n",
       "Maintains local state automatically\n",
       "Values are computed one at a time, as they’re needed Avoids storing the entire sequence in memory\n",
       "Good for aggregating (summing, counting) items. One pass. Crucial for infinite sequences\n",
       "Bad if you need to inspect the individual values\n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Mutability** - without copying, change one will affect the other\n",
       "* **List comprehension** - [expression for name in list if filter]\n",
       "\n",
       "\n",
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       "The following six elements are needed to formulate a search problem:\n",
       "\n",
       "state space, initial state, terminal state, actions, trainsition model, action cost function.\n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       "This section introduced us to several different search problems.\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       "An overview of search algorithms. Four aspects to evaluate a search algorithm: completeness, optimality, space complexity, time complexity.\n",
       "\n",
       "Tree search costs less memory but more time than graph search.\n",
       "\n",
       "Completeness: Is the algorithm guaranteed to find a solution when there is one, and to correctly report failure when there is not?\n",
       "\n",
       "Optimality: Does it find a solution with the lowest path cost of all solutions?\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       "BFS(this uses late goal testing, bfs can use early goal testing):\n",
       "\n",
       "<img src=./search_algo.png width=600 height=100 />\n",
       "\n",
       "DFS: frontier changes to stack\n",
       "\n",
       "UCS: frontier changes to priority queue\n",
       " \n",
       "The following is the comparison between different search algos.\n",
       "\n",
       "<img src=./comparison.png width=600 height=100 />\n",
       "\n",
       "\n",
       "\n",
       "## Module 3 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search, it uses atomic representation\n",
       "* **Optimal solution** - the solution has the lowest path cost among all solutions\n",
       "* **Tree/graph search** - a graph search checks redundant paths while tree search doesn't\n",
       "* **Early goal test** - checking whether a node is a solution as soon as it is generated\n",
       "* **Late goal test** - checking whether a node is a solution when it is popped\n",
       "* **Uninformed** - only has access to the problem definition\n",
       "\n",
       "\n",
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       "A* search:\n",
       "\n",
       "<img src=./A_star.png width=600 height=100 />\n",
       "\n",
       "With an admissible heuristic(also called optmistic), A* search is optimal.\n",
       "\n",
       "With a consistent heuristic, A* search will only put each node once into the frontier.\n",
       "\n",
       "One problem with A* search is the memeory issue because sometimes it will put the same node several times into the frontier.\n",
       "\n",
       "A* with a consistent heuristic is optimally efficient\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       "For any node, if $h_1(n) \\geq h_2(n)$, then we say $h_1$ dominates $h_2$\n",
       "\n",
       "If the total number of nodes generated by A* for a particular problem is N and the solution depth is d, \n",
       "then b* is the branching factor that a uniform tree of depth would have to have in order to contain nodes. \n",
       "So we have: $N+1=1+b^*+(b^*)^2 ... +(b^*)^d$\n",
       "\n",
       "The performance of heuristic search algorithms depends on the quality of the heuristic function. \n",
       "One can sometimes construct good heuristics by relaxing the problem definition, \n",
       "by storing precomputed solution costs for subproblems in a pattern database, by defining landmarks, \n",
       "or by learning from experience with the problem class.\n",
       "\n",
       "IDA* (iterative deepening A* search) is an iterative deepening version of A*, and\n",
       "thus adresses the space complexity issue.\n",
       "\n",
       "RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are\n",
       "robust, optimal search algorithms that use limited amounts of memory; given enough\n",
       "time, they can solve problems for which A* runs out of memory.\n",
       "\n",
       "BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and\n",
       "suboptimal, but it often finds reasonably good solutions and runs faster than complete searches.\n",
       "\n",
       "WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.(not optimal, but complete)\n",
       "\n",
       "IDA*, SMA*, and RBFS are optimal search algorithms which are more space efficient.\n",
       "\n",
       "\n",
       "\n",
       "## Module 4 Lecture Notes\n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Admissible heuristic** - one that never overestimates the cost to reach a goal\n",
       "* **Consistent heuristic** - $h(n)\\leq c(n, a, n^{\\prime}) + h(n^{\\prime})$\n",
       "* **Relaxed problem** - A problem with fewer restrictions on actions\n",
       "\n",
       "\n",
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       "A game can be defined by the initial state (how the board is set up), \n",
       "the legal actions in each state, \n",
       "the result of each action, \n",
       "a terminal test (which says when the game is over), \n",
       "and a utility function that applies to terminal states to say who won and what the final score is.\n",
       "\n",
       "A game is differed from search problems in that it has multiple agents.\n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       "In two-player, discrete, deterministic, turn-taking zero-sum games with perfect\n",
       "information, the minimax algorithm can select optimal moves by a depth-first\n",
       "enumeration of the game tree.\n",
       " \n",
       "The value at that node is the value of the best terminal state reach by both player playing optimally. \n",
       "That means that the current player tries to maximize the score and the other player tries to minimize it.\n",
       "\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       "The alpha–beta search algorithm computes the same optimal move as minimax, but\n",
       "achieves much greater efficiency by eliminating subtrees that are provably irrelevant.\n",
       "Usually, it is not feasible to consider the whole game tree (even with alpha–beta), so we\n",
       "need to cut the search off at some point and apply a heuristic evaluation function that estimates the utility of a state.\n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       "Games of chance can be handled by expectiminimax, \n",
       "an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children, \n",
       "weighted by the probability of each child.\n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       " Your summary here \n",
       "\n",
       "## Module 5 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Stochastic games** - games in which the results of a movement is not deterministic.\n",
       "* **Alpha** - highest-value we have found so far at any choice point along the path for MAX.\n",
       "* **Beta** - lowest-value we have found so far at any choice point along the path for MIN.\n",
       "* **Perfect information** - same for fully observable\n",
       "* **Zero-sum** - what is good for one player is just as bad for the other, no win-win\n",
       "* **Complexity of minimax** - $O(b^m)$\n",
       "* **Complexity of perfect order alpha-beta pruning** - $O(b^{m/2})$\n",
       "* **Type a strategy** - considers all possible moves to a certain depth in the search tree, wide but shallow.\n",
       "* **A type b strategy** - ignores moves that look bad, and follows promising lines as far as possible. deep but narrow\n",
       "* **Cutoff test** - decides when to cut off the search\n",
       "* **Quiescent1** - The evaluation function should be applied only to positions that are quiescent\n",
       "* **Quiescent2** - A move is quiescent if there is no pending move that would wildly swing the valuation\n",
       "* **Horizon effect** - when an agent try to erroneously delay the inevitable\n",
       "* **Forward pruning** - prunes moves that appear to be poor moves(but still possiblely good)(beam search)\n",
       "* **Utility function** - assigns a single number to express the desirability of a state.\n",
       "\n",
       "\n",
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       "CSPs represent a state with a set of variable/value pairs\n",
       "\n",
       "CSPs represent the conditions for a solution with a set of constraints on the variables\n",
       "\n",
       "In search problems, states are black boxes with a transition model to move between boxes, while in CSP the agent can see inside the states and move accordingly.\n",
       "\n",
       "There is no existing solution for general nonlinear constraints for integers.\n",
       "\n",
       "CSPs can rule out variable assignments using search and inference.\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       "We can do constraint propagation(using the constraints to rule out variable assignment) base on local consistency.\n",
       "\n",
       "A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n",
       "\n",
       "The key behind inference in CSPs is enforcing k-consistency(1-consistency is node consistency, 2-consistency is arc-consistency, 3-consistency is path-consistency).\n",
       "\n",
       "A CSP is strong k-consistent if it is k-consistent, k-1 consistent... 1-consistent.\n",
       "\n",
       "AC-3 is an algorithm for enforcing arc consistency.\n",
       "\n",
       "The following is the persudocode for AC-3:\n",
       "```\n",
       "def remove_inconsistent_values(self, cell1, cell2):\n",
       "    cell2_values = self.get_values(cell2).copy()\n",
       "    removed = False\n",
       "    if len(cell2_values) == 1:\n",
       "        element = cell2_values.pop()\n",
       "        if element in self.board[cell1]:\n",
       "            self.board[cell1].remove(element)\n",
       "            removed = True\n",
       "    return removed\n",
       "    \n",
       "def infer_ac3(self):\n",
       "    q = queue.Queue()\n",
       "    for arc in self.ARCS:\n",
       "        q.put(arc)\n",
       "    update = False\n",
       "    while not q.empty():\n",
       "        cell1, cell2 = q.get()\n",
       "        removed = self.remove_inconsistent_values(cell1, cell2)\n",
       "        if removed:\n",
       "            update = True\n",
       "            for neighbour in get_neighbour(cell1):\n",
       "                if neighbour != cell2:\n",
       "                    q.put((neighbour, cell1))\n",
       "    return update\n",
       "```\n",
       "Assume a CSP with n variables, each with domain size at most d, and with c binary constraints (arcs). Since each arc can\n",
       "only be inserted into the queue at most d times(as each variable has at most d values to delete), and checking consistency of an arc\n",
       "takes $O(d^2)$ times, so the time complexity for ac-3 is $O(cd^3)$. Note that since $c<n(n-1)$, the upper bound for time complexity is $O(n^2d^3)$\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       "Backtracking search is a form of depth first search commonly used for solving CSPs.\n",
       "\n",
       "Backtracking occurs when no legal assignment can be found for a variable.\n",
       "\n",
       "MRV(Minimum Remaining Value) chooses the variable with the fewest “legal” values.\n",
       "\n",
       "degree heuristic chooses the variable that is involved in the largest number of constraints on other unassigned variables.\n",
       "\n",
       "least-constraining-value chooses the value for a variable that rules out the fewest choices for the neighboring variables in the constraint graph.\n",
       "\n",
       "The difference between AC-3 and forward checking is that forward checking only maintaining arc-consistency with neighbours when the value of a node is removed, \n",
       "while AC-3 repeatedly enforcing arc-consistency whenever there is a value for a node is deleted.\n",
       "\n",
       "MAC vs forward checking: MAC recursively propogrates constraints, whereas forward checking does not.\n",
       "\n",
       "MAC vs AC-3: MAC is a way of interleaving search and inference. AC-3 is pure inference.\n",
       "\n",
       "Constraint learning records the conflicts as they are encountered in the search in order to avoid the same conflict later.\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       "\n",
       "Solving an arbitrary CSP takes exponential time in the number of variables.\n",
       "\n",
       "Tree-CSP can be solved in $O(nd^2)$ where n is the number of variables and d is the size of the largest domain, which is linear to the number of variables.\n",
       "\n",
       "We can decompose the problem into small tree-like CSP.\n",
       "\n",
       "### Cutset Conditioning(used to reduce a general CSP to a tree structured one):\n",
       "\n",
       "1. Choose a subset of the CSP’s variables such that the constraint graph becomes a tree after removal of S. \n",
       "S is called a cycle cutset.\n",
       "\n",
       "2. For each possible assignment to the variables in that satisfies all constraints on S,\n",
       "\n",
       "\t a. remove from the domains of the remaining variables any values that are\n",
       "inconsistent with the assignment for S, and\n",
       "\n",
       "\t b. if the remaining CSP has a solution, return it together with the assignment for S.\n",
       "\n",
       "Suppose the cycle cutset size is c, we need to try $d^c$ different assignments of values for the cutset, and the remaining\n",
       "tree problem of size $n-c$ needs $O((n-c)d^2)$, so the total time complexity for cutset conditioning is $O(d^c(n-c)d^2)$.\n",
       "If the graph is \"nearly a tree\", meaning that c is small, then the complexity would be good.\n",
       "\n",
       "\n",
       "### Tree decomposition(transform a CSP into a tree of subproblems):\n",
       "\n",
       "We can transform the original graph into a tree where each nodes contains several original vertices(variable) of the graph and satisfy the following condition:\n",
       "1. Each original variable appears in at least one node.\n",
       "\n",
       "2. If two variables are connected by some constraints in the original graph, then it should appear together in at least one node.\n",
       "\n",
       "3. If one variable appears at the same time in two node, then it should also appear in every node that is in the path between these two node.\n",
       "\n",
       "Once we get the tree, we can solve the problem in $O(nd^2)$ where n is the number of nodes and d is the size of largest domain.\n",
       "(note that the domain here is a tuple of possible values for variables inside the node). \n",
       "The complexity is reasonable when we have a small d, when the tree width(the number of variables in one node) is small.\n",
       "\n",
       "Tree decomposition is more efficient in time than cutset conditioning because whenever you have a cycle-cutset of size c, \n",
       "there is also a tree width of size w < c+1 and it may be far smaller in some cases. \n",
       "but the advantage of the cycle-cutset approach is that it can be executed in linear memory, while tree decomposition requires memory exponential in tree width w.\n",
       "\n",
       "\n",
       "## Module 6 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Unary constraint** - constraint for a single variable\n",
       "* **Binary constraint** - constraint relates two variables\n",
       "* **Global constraint** - constraint involving an arbitrary number of variables\n",
       "* **Constraint propagation** - using the constraints to reduce the number of legal values for a variable\n",
       "\n",
       "\n",
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       " Your summary here \n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       "\n",
       "Commonly used equivalence:\n",
       "<img src=./equivalence.png width=600 height=100 />\n",
       "\n",
       "Resolution:\n",
       "\n",
       "$\\frac{(P\\lor \\lnot Q \\lor R) \\land (\\lnot P \\lor Q)}{Q \\lor \\lnot Q \\lor R}$\n",
       "\n",
       "We should note here only one pair can be resolved.\n",
       "\n",
       "Resolution algorithm:\n",
       "\n",
       "<img src=./resolution_algo.png width=600 height=100 />\n",
       "\n",
       "Resolution is complete.\n",
       "\n",
       "Problems with Horn clauses can be done in linear time with respect to the size of the KB.\n",
       "\n",
       "\n",
       "Forward Chaining is a kind of data-driven reasoning.\n",
       "\n",
       "An agent can start with known data, adding premises as new percepts come in, \n",
       "and then incrementally apply the forward chaining algorithm to derive new conclusions. \n",
       "It doesn’t have to have a specific query in mind to do so.\n",
       "\n",
       "Forward Chaining persudocode:\n",
       "\n",
       "<img src=./forward_chaining.png width=600 height=100 />\n",
       "\n",
       "Backward chaining works backwards from a query.\n",
       " \n",
       "If the query is known to be true, then no work is needed. \n",
       "Otherwise, the algorithm finds implications in the KB whose conclusions is the query. \n",
       "If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n",
       "\n",
       "Backward chaining is a form of goal-directed reasoning.\n",
       "\n",
       "\n",
       "## Module 7 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge-based agents** - use a process of reasoning over an internal representation of knowledge to decide what actions to take.\n",
       "* **Knowledge base** - a set of sentences expressed in knowledge representation language and represents some assertion about the world.\n",
       "* **Definite clause** - disjunction of literals where exactly one is positive\n",
       "* **Horn clause** - disjunction of literals of which at most one is positive\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "FINAL Template_for CIS521_midterm notes.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
