{
 "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/",
     "height": 0
    },
    "id": "lzaavW96tcxM",
    "outputId": "b98164e8-c73b-4762-a49e-486c9439bbc8"
   },
   "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/",
     "height": 0
    },
    "id": "8DvZ57A-djo1",
    "outputId": "e77c186a-b459-4bf8-95e1-05c18c709a39"
   },
   "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": {
    "collapsed": true,
    "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": {
    "cellView": "code",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 0
    },
    "id": "Y2NfE1CKxzS-",
    "outputId": "122530c2-3ac3-49b3-c8c4-52d26c624dc0"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 283\n",
      "The length in characters is 1703\n"
     ]
    }
   ],
   "source": [
    "#@title Default title text\n",
    "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
    "\n",
    "chapter1_1 = \"\"\" Definition of AI: Some people defined intelligence as fidelity to humman performance. But formal definition is: **rationality** ('right thing'), \\\n",
    "  subject: thought process and reasoning, intelligent behavior.  \n",
    "   \n",
    "   **The Turing test approach**(the program passes the test if it fools the interrogator 30% of the time.). Computer would need these capabilities: a.NLP; b.knowledge represention; \\\n",
    "  c.automated reasoning; d.ML. **Total Turing test** requires interaction with objects and people in the real world. A robot will need e.CV and f.robotics to pass the test.  \n",
    "  \n",
    "  **The cognitive modeling approach**. Learn about human thought in three ways: a. introspection—trying to catch our own thoughts as they go by; b.psychological experiments;\\\n",
    "  c.brain imaging. The interdisciplinary field of cognitive science brings together computer models from AI and experimental Cognitive science techniques from psychology.  \n",
    "  \n",
    "  **The “laws of thought” approach**. Aristotle's syllogisms -> logic. Only knowledge that is certain -> probability.  \n",
    "  \n",
    "  **The rational agent approach**. A rational agent acts to achieve the best outcome or the best expected outcome (when there is uncertainty).\\\n",
    "  Act rationally needs skills to deduce and to pass the Turing test. Advantage of this approach: more general and more amentable to scientific development.  \n",
    "  \n",
    "  AI has focused on the study and construction of agents that **do the right thing**.  -> standard model (assumes that we will supply a fully specified objective to the machine) \\\n",
    "  The value alignment problem: the values or objectives put into the machine must be aligned with those of the human. We need agents that are provably beneficial to humans.\n",
    "  \"\"\" \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 = \"\"\" Weak AI (acts if they were intelligent) and Strong AI (actually consciously thinking not just simulating thinking)  \n",
    "  \n",
    "  Turing’s “**argument from informality of behavior**” says that human behavior is far too complex to be captured by any formal set of rules. \\\n",
    "  Some phylo criticized Good Old-Fashioned AI (GOFAI) (computationalism). These AIs have difficulties in the qualification problem. The embodied \\\n",
    "  cognition approach claims that the body is embedded in an environment and we need to study the whole system.  \n",
    "  \n",
    "  **The argument from disability**. A machine can nerver do X and can never be exactly human.   \n",
    "  \n",
    "  **Godel ’s incompleteness theorem**: a.G(F) is a sentence of F, but cannot be proved within F. b.If F is consistent, then G(F) is true.\"\"\"\n",
    "chapter27_2 = \"\"\" Turing extends **polite convention** to machines.  \n",
    "  \n",
    "  John Searle (a proponent of biological naturalism) rejects the polite convention. **Chinese room** - only symbol manipulation.  \n",
    "  \n",
    "  The big problem is about consciousness: whether machines can have qualia.\n",
    "  \"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
    "chapter2_1 = \"\"\" An **agent**: anything that can be viewed as perceiving its environment through **sensors** 传感器感知 and \\\n",
    "  acting upon that environment through **actuators** 执行器操作.  \n",
    "  \n",
    "  **Percept and percept history**. An agent’s behavior is described by **the agent function** that maps any given percept \\\n",
    "  sequence to an action (not based on anything that hasn't been preceived). Internally, the agent function (abstract mathematical description) for an artificial \\\n",
    "  agent will be implemented by an **agent program** (concrete implementation). We can tabulating the agent function.\"\"\"\n",
    "chapter2_2 = \"\"\" **The Concept of Rationality - do the right thing**  \n",
    "   \n",
    "   是什么- Consequentialism: See if the sequence of states caused by an agent's actions is desirable. It is better to design **performance measures** according to what \\\n",
    "   one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave. \n",
    "   \n",
    "   判断标准 - its expected performance is at least as good as any other agent’s. The same agent would be irrational under different circumstances - needs to know when to end.  \n",
    "\n",
    "   **Omniscience, learning, and autonomy**  \n",
    "\n",
    "  Distinguish between **rationality and omniscience (perfection）**: Rationality maximizes expected performance, while perfection maximizes actual performance.\n",
    "  \n",
    "  To define rationality: a. do not need to be perfect (we don't know future percept sequence); b. not rational given uninformative percept sequence; c. A rational agent \\\n",
    "  needs to do **information gathering** by exploring the environment. c. A rational agent not only to gather information but also to **learn** as much as possible from \\\n",
    "  what it perceives; d. **autonomous**: not only relies on the prior knowledge but also percepts and learning process.  \n",
    "   \"\"\"\n",
    "chapter2_3 = \"\"\" \n",
    "  **task environment**: the Performance measure, the Environment, and the agent’s Actuators and Sensors.(the **PEAS** (Performance, Environment, Actuators, Sensors) description) \\\n",
    "  The virtual task environments can be just as complex as the “real” world: a software agent (or software robot or softbot).  \n",
    "  \n",
    "  **Properties of task environments**  \n",
    "  a. Fully observable ( if the sensors detect all aspects that are relevant to the choice of action) vs. partially observable;  \n",
    "  b. Single-agent vs. multiagent (can be competitve or cooperative). See whether B’s behavior is best described as maximizing a performance measure whose value depends on agent A’s behavior;  \n",
    "  c. Deterministic vs. nondeterministic or stochastic (given exact probability);  \n",
    "  d. Episodic vs. sequential(the current decision could affect all future decisions);  \n",
    "  e. Static vs. dynamic vs. semidynamic(environment itself doesn't change with the passage of time but the agent’s performance score does);  \n",
    "  f. Discrete vs. continuous. state, time, percepts and actions;  \n",
    "  g. Known vs. unknown.  \"\"\"\n",
    "chapter2_4 = \"\"\" agent =  architecture (physical sensors/actuators) + program \n",
    "  \n",
    "  **Agent programs**  \n",
    "   take current percept as input 图片  \n",
    "\n",
    "  **Simple reflex agents**: condition–action rule, work only if the correct decision can be made on the basis of just the \\\n",
    "  current percept—that is, only if the environment is fully observable. randomize to avoid infinite loops  \n",
    "\n",
    "  **Model-based reflex agents**: keep track of a transition model of the world. uncertainty about the current state and the \n",
    "  agent still has to make a decision.  \n",
    "\n",
    "  **Goal-based agents**: search and planning. Consideration the future and this information is explicitly represented/ \\\n",
    "  can be modified --> more flexible  \n",
    "\n",
    "  **Utility-based agents**: An agent’s utility function is essentially an internalization of the performance measure.\\\n",
    "  an agent that chooses actions to maximize its utility will be rational according to the external performance measure.\n",
    "  \n",
    "  Simple reflex agents respond directly to percepts, whereas model-based reflex agents maintain internal state to \\\n",
    "  track aspects of the world that are not evident in the current percept. Goal-based agents act to achieve their \\\n",
    "  goals, and utility-based agents try to maximize their own expected “happiness.”  \n",
    "\n",
    "  **learning agent**: learning element, performance element and problem generator\n",
    "  \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "\n",
    "# Definitions of concepts from Module 1.\n",
    "# You can define any bolded term in the textbook, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 20 words long.\n",
    "module1_definitions = {\n",
    "\"agent\" : \"anything that can perceive and act in an environment\",\n",
    "\"percept\" : \"what an agent's sensors are perceiving from the environment \",\n",
    "\"percept sequence\" : \"the complete history that an agent has preceived\",\n",
    "\"a rational agent\": \"Given the evidence provided by the percept sequence and built-in knowledge, act to maximize its performance measure\",\n",
    "\"An omniscient agent\": \"Knows the actual outcome of its actions and can act accordingly, which is impossible in reality\",\n",
    "}\n",
    "\n",
    "\n",
    "print(\"The length in words is\", len(chapter1_1.split(' ')))\n",
    "print(\"The length in characters is\", len(chapter1_1))\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": 1998
    },
    "id": "gYYeNcdM_maE",
    "outputId": "05b67f43-771e-4f74-efa5-b55245aa9828"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       " Definition of AI: Some people defined intelligence as fidelity to humman performance. But formal definition is: **rationality** ('right thing'),   subject: thought process and reasoning, intelligent behavior.  \n",
       "   \n",
       "   **The Turing test approach**(the program passes the test if it fools the interrogator 30% of the time.). Computer would need these capabilities: a.NLP; b.knowledge represention;   c.automated reasoning; d.ML. **Total Turing test** requires interaction with objects and people in the real world. A robot will need e.CV and f.robotics to pass the test.  \n",
       "  \n",
       "  **The cognitive modeling approach**. Learn about human thought in three ways: a. introspection—trying to catch our own thoughts as they go by; b.psychological experiments;  c.brain imaging. The interdisciplinary field of cognitive science brings together computer models from AI and experimental Cognitive science techniques from psychology.  \n",
       "  \n",
       "  **The “laws of thought” approach**. Aristotle's syllogisms -> logic. Only knowledge that is certain -> probability.  \n",
       "  \n",
       "  **The rational agent approach**. A rational agent acts to achieve the best outcome or the best expected outcome (when there is uncertainty).  Act rationally needs skills to deduce and to pass the Turing test. Advantage of this approach: more general and more amentable to scientific development.  \n",
       "  \n",
       "  AI has focused on the study and construction of agents that **do the right thing**.  -> standard model (assumes that we will supply a fully specified objective to the machine)   The value alignment problem: the values or objectives put into the machine must be aligned with those of the human. We need agents that are provably beneficial to humans.\n",
       "  \n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       " Weak AI (acts if they were intelligent) and Strong AI (actually consciously thinking not just simulating thinking)  \n",
       "  \n",
       "  Turing’s “**argument from informality of behavior**” says that human behavior is far too complex to be captured by any formal set of rules.   Some phylo criticized Good Old-Fashioned AI (GOFAI) (computationalism). These AIs have difficulties in the qualification problem. The embodied   cognition approach claims that the body is embedded in an environment and we need to study the whole system.  \n",
       "  \n",
       "  **The argument from disability**. A machine can nerver do X and can never be exactly human.   \n",
       "  \n",
       "  **Godel ’s incompleteness theorem**: a.G(F) is a sentence of F, but cannot be proved within F. b.If F is consistent, then G(F) is true.\n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       " Turing extends **polite convention** to machines.  \n",
       "  \n",
       "  John Searle (a proponent of biological naturalism) rejects the polite convention. **Chinese room** - only symbol manipulation.  \n",
       "  \n",
       "  The big problem is about consciousness: whether machines can have qualia.\n",
       "  \n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       " An **agent**: anything that can be viewed as perceiving its environment through **sensors** 传感器感知 and   acting upon that environment through **actuators** 执行器操作.  \n",
       "  \n",
       "  **Percept and percept history**. An agent’s behavior is described by **the agent function** that maps any given percept   sequence to an action (not based on anything that hasn't been preceived). Internally, the agent function (abstract mathematical description) for an artificial   agent will be implemented by an **agent program** (concrete implementation). We can tabulating the agent function.\n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       " **The Concept of Rationality - do the right thing**  \n",
       "   \n",
       "   是什么- Consequentialism: See if the sequence of states caused by an agent's actions is desirable. It is better to design **performance measures** according to what    one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave. \n",
       "   \n",
       "   判断标准 - its expected performance is at least as good as any other agent’s. The same agent would be irrational under different circumstances - needs to know when to end.  \n",
       "\n",
       "   **Omniscience, learning, and autonomy**  \n",
       "\n",
       "  Distinguish between **rationality and omniscience (perfection）**: Rationality maximizes expected performance, while perfection maximizes actual performance.\n",
       "  \n",
       "  To define rationality: a. do not need to be perfect (we don't know future percept sequence); b. not rational given uninformative percept sequence; c. A rational agent   needs to do **information gathering** by exploring the environment. c. A rational agent not only to gather information but also to **learn** as much as possible from   what it perceives; d. **autonomous**: not only relies on the prior knowledge but also percepts and learning process.  \n",
       "   \n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       " \n",
       "  **task environment**: the Performance measure, the Environment, and the agent’s Actuators and Sensors.(the **PEAS** (Performance, Environment, Actuators, Sensors) description)   The virtual task environments can be just as complex as the “real” world: a software agent (or software robot or softbot).  \n",
       "  \n",
       "  **Properties of task environments**  \n",
       "  a. Fully observable ( if the sensors detect all aspects that are relevant to the choice of action) vs. partially observable;  \n",
       "  b. Single-agent vs. multiagent (can be competitve or cooperative). See whether B’s behavior is best described as maximizing a performance measure whose value depends on agent A’s behavior;  \n",
       "  c. Deterministic vs. nondeterministic or stochastic (given exact probability);  \n",
       "  d. Episodic vs. sequential(the current decision could affect all future decisions);  \n",
       "  e. Static vs. dynamic vs. semidynamic(environment itself doesn't change with the passage of time but the agent’s performance score does);  \n",
       "  f. Discrete vs. continuous. state, time, percepts and actions;  \n",
       "  g. Known vs. unknown.  \n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       " agent =  architecture (physical sensors/actuators) + program \n",
       "  \n",
       "  **Agent programs**  \n",
       "   take current percept as input 图片  \n",
       "\n",
       "  **Simple reflex agents**: condition–action rule, work only if the correct decision can be made on the basis of just the   current percept—that is, only if the environment is fully observable. randomize to avoid infinite loops  \n",
       "\n",
       "  **Model-based reflex agents**: keep track of a transition model of the world. uncertainty about the current state and the \n",
       "  agent still has to make a decision.  \n",
       "\n",
       "  **Goal-based agents**: search and planning. Consideration the future and this information is explicitly represented/   can be modified --> more flexible  \n",
       "\n",
       "  **Utility-based agents**: An agent’s utility function is essentially an internalization of the performance measure.  an agent that chooses actions to maximize its utility will be rational according to the external performance measure.\n",
       "  \n",
       "  Simple reflex agents respond directly to percepts, whereas model-based reflex agents maintain internal state to   track aspects of the world that are not evident in the current percept. Goal-based agents act to achieve their   goals, and utility-based agents try to maximize their own expected “happiness.”  \n",
       "\n",
       "  **learning agent**: learning element, performance element and problem generator\n",
       "  \n",
       "\n",
       "## Module 1 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - anything that can perceive and act in an environment\n",
       "* **Percept** - what an agent's sensors are perceiving from the environment \n",
       "* **Percept sequence** - the complete history that an agent has preceived\n",
       "* **A rational agent** - Given the evidence provided by the percept sequence and built-in knowledge, act to maximize its performance measure\n",
       "* **An omniscient agent** - Knows the actual outcome of its actions and can act accordingly, which is impossible in reality\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",
    "  if warnings != \"\":\n",
    "    markdown += \"## \" + warnings\n",
    "\n",
    "  # Check definition lengths\n",
    "  warnings = length_check_definitions(definitions)\n",
    "  if warnings != \"\":\n",
    "    markdown += \"## \" + warnings\n",
    "\n",
    "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
    "\n",
    "\n",
    "  for section, summary in sections:\n",
    "    if show_placeholder and summary == \" Your summary here \":\n",
    "      summary = placeholder\n",
    "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
    "  \n",
    "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
    "  for concept, definition in definitions.items():\n",
    "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
    "  return markdown\n",
    "\n",
    "\n",
    "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
    "display(Markdown(module1_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9xRbdqDox2zD"
   },
   "source": [
    "#Module 2 - Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true,
    "id": "DpBvu7EMx7sy"
   },
   "outputs": [],
   "source": [
    "# No readings for this module.  Instead you can summarize the lecture instead.\n",
    "\n",
    "# Lecture notes \n",
    "module2_lecture_notes = \"\"\" Python is strong type (\"foo\"+2) and dynamic typing (x = \"foo\", x=2)  \n",
    "  Strings,Tuple, keys in Dictionaries (immutable), lists(mutable) \"\"\"\n",
    "\n",
    "# Each definition should be at most 20 words long.\n",
    "module2_definitions = {\n",
    "\"mutability\" : \"allows change\",\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 225
    },
    "id": "ydOK__lwWgdp",
    "outputId": "584671be-baef-40e3-d2c2-644e9626d9c6"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       " Python is strong type (\"foo\"+2) and dynamic typing (x = \"foo\", x=2)  \n",
       "  Strings,Tuple, keys in Dictionaries (immutable), lists(mutable) \n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Mutability** - allows change\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": {
    "collapsed": true,
    "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 = \"\"\" Assume the agent has the access to environment info.   \n",
    "  Four-phase problem-solving process:  \n",
    "  a. Goal formulation, b. Problem formulation: The agent devises a description of the states and actions \\\n",
    "  necessary to reach the goal; c. Search; d. Execution.  \n",
    "  \n",
    "  In a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence \\\n",
    "  of actions.\n",
    "  \n",
    "  **A search problem**  \n",
    "  Defined as : states - state space; initial state; goal states (one or more)/ goal test; actions (applicable); transition model \\\n",
    "  (waht the action does); action cost function/ path cost.  \n",
    "  Other concepts: path, optimal solution, graph.  \n",
    "  \n",
    "  **Formulating problems**\n",
    "  model, abstraction, level of abstraction (level of details).  \n",
    "  If an abstraction is valid: elaborate any abstract solution into a solution in the more detailed world;  \n",
    "  If it is useful: carrying out each of the actions in the solution is easier than the original problem.\n",
    "  If it is a good abstraction:  removing as much detail as possible while retaining validity and ensuring that it is useful.\n",
    "  \"\"\"\n",
    "chapter3_2 = \"\"\" **standardized problem**  \n",
    "  eg. A grid world problem. The state space can be infinite  \n",
    "  **real-world problem**  \n",
    "  Route-finding problem, Touring problems ...\"\"\"\n",
    "chapter3_3 = \"\"\" **Search Algorithms**\n",
    "  a search tree: node - state, edge - action. parent node, child/successor node, frontier. expanded, generated, reached  \n",
    "  \n",
    "  **Best-first Search**  \n",
    "  Choose a node with minimum evaluation function, f(n).  \n",
    "  On each iteration, 1.choose a node on the frontier with minimum f(n) value, \\\n",
    "  2.if its state is a goal state then return, and otherwise apply EXPAND to generate \\\n",
    "  child nodes. Each child node is added to the frontier if it has not been \\\n",
    "  reached before, or is re-added if it is now being reached with a path that \\\n",
    "  has a lower path cost than any previous path.   \n",
    "\n",
    "  **Search data structure**\n",
    "  Node.STATE/PARENT/ACTION/PATH-COST.  IS-EMPTY(frontier)/POP(frontier)/TOP(frontier)/ADD(node, frontier).  \n",
    "  Store the frontier : A priority queue (the minimum cost according to f)/A FIFO queue/A LIFO queue.  \n",
    "  \n",
    "  **A graph search** checks for redundant paths (if a node has been visited) and a tree-like search does not check.\n",
    "  \n",
    "  **Measuring Performance**  \n",
    "  Completeness,  Cost optimality, Time/space complexity  \n",
    "  d, the depth in an optimal solution; m, the maximum number of actions in any path; b, the branching factor.\"\"\"  \n",
    "chapter3_4 = \"\"\" **Uninformed Search**  \n",
    "  \n",
    "  **Breadth-first search** \n",
    "  possible infinite paths; some solutions have short paths; can quickly discard unlikely path  \n",
    "  **Depth-first search**  \n",
    "  if space is restricted; possible solutions with long path and wrong paths terminated quickly; search can be fine-tuned quickly  \n",
    "  **Depth-limited search**  \n",
    "  if l=d, then optimal; if l<d then incomplete; if l>d then not optimal  \n",
    "  **Iterative deepening search**\n",
    "  find best l.  \n",
    "  **bidirectional search**\n",
    "  searches both from the initial state and from the goal state(s)  \n",
    "  bidirectional best-first search, bidirectional uniform-cost search\n",
    "\n",
    "  **Dijkstra’s algorithm or uniform-cost search**  \n",
    "  weighted step-cost. choose a node with lowest path cost function **g(N)**  \n",
    "  tests for goals only when it expands a node, not when it generates a node (make sure it is optimal) \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module3_lecture_notes = \"\"\" \n",
    "```\n",
    "{\n",
    "  function BEST-FIRST-SEARCH(problem,f ) returns a solution node or failure\n",
    "    node←NODE(STATE=problem.INITIAL)\n",
    "    frontier ←a priority queue ordered by f , with node as an element\n",
    "    reached ←a lookup table, with one entry with key problem.INITIAL and value node\n",
    "    while not IS-EMPTY(frontier) do\n",
    "      node←POP(frontier)\n",
    "      if problem.IS-GOAL(node.STATE) then return node\n",
    "      for each child in EXPAND(problem, node) do\n",
    "        s←child.STATE\n",
    "        if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n",
    "          reached[s]←child\n",
    "          add child to frontier\n",
    "    return failure\n",
    "    function EXPAND(problem, node) yields nodes\n",
    "      s←node.STATE\n",
    "      for each action in problem.ACTIONS(s) do\n",
    "        s′ ←problem.RESULT(s, action)\n",
    "        cost ←node.PATH-COST + problem.ACTION-COST(s, action, s′)\n",
    "        yield NODE(STATE=s′, PARENT=node, ACTION=action, PATH-COST=cost)\n",
    "}\n",
    "```\n",
    "\n",
    "```\n",
    "{\n",
    "  function BREADTH-FIRST-SEARCH(problem) returns a solution node or failure\n",
    "    node←NODE(problem.INITIAL)\n",
    "    if problem.IS-GOAL(node.STATE) then return node\n",
    "    frontier ←a FIFO queue, with node as an element\n",
    "    reached ←{problem.INITIAL}\n",
    "    while not IS-EMPTY(frontier) do\n",
    "      node←POP(frontier)\n",
    "      for each child in EXPAND(problem, node) do\n",
    "        s←child.STATE\n",
    "        if problem.IS-GOAL(s) then return child\n",
    "        if s is not in reached then\n",
    "          add s to reached\n",
    "          add child to frontier\n",
    "    return failure\n",
    "  function UNIFORM-COST-SEARCH(problem) returns a solution node, or failure\n",
    "    return BEST-FIRST-SEARCH(problem, PATH-COST)\n",
    "}\n",
    "```\"\"\"\n",
    "\n",
    "# Definitions of concepts from Module 3.\n",
    "# You can define any bolded term in the textbook, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 20 words long.\n",
    "module3_definitions = {\n",
    "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
    "\"search\": \"computation process to formulate the plan\",\n",
    "\"solution\": \"a sequence of actions that reaches the goal or a path from the initial state to a goal state.\",\n",
    "\"optimal solution:\": \"One solution that has the lowest path cost\",\n",
    "\"abstraction\": \"the process of removing detail from a representation to get the model\",\n",
    "\"frontier\": \"states that are available to expand\",\n",
    "\"a systematic search problem\": \"When exploring infinite state space, it can reach any state that is connected to the initial state\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1884
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "598a386c-746c-4a81-ff17-d812c8b52432"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       " Assume the agent has the access to environment info.   \n",
       "  Four-phase problem-solving process:  \n",
       "  a. Goal formulation, b. Problem formulation: The agent devises a description of the states and actions   necessary to reach the goal; c. Search; d. Execution.  \n",
       "  \n",
       "  In a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence   of actions.\n",
       "  \n",
       "  **A search problem**  \n",
       "  Defined as : states - state space; initial state; goal states (one or more)/ goal test; actions (applicable); transition model   (waht the action does); action cost function/ path cost.  \n",
       "  Other concepts: path, optimal solution, graph.  \n",
       "  \n",
       "  **Formulating problems**\n",
       "  model, abstraction, level of abstraction (level of details).  \n",
       "  If an abstraction is valid: elaborate any abstract solution into a solution in the more detailed world;  \n",
       "  If it is useful: carrying out each of the actions in the solution is easier than the original problem.\n",
       "  If it is a good abstraction:  removing as much detail as possible while retaining validity and ensuring that it is useful.\n",
       "  \n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       " **standardized problem**  \n",
       "  eg. A grid world problem. The state space can be infinite  \n",
       "  **real-world problem**  \n",
       "  Route-finding problem, Touring problems ...\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       " **Search Algorithms**\n",
       "  a search tree: node - state, edge - action. parent node, child/successor node, frontier. expanded, generated, reached  \n",
       "  \n",
       "  **Best-first Search**  \n",
       "  Choose a node with minimum evaluation function, f(n).  \n",
       "  On each iteration, 1.choose a node on the frontier with minimum f(n) value,   2.if its state is a goal state then return, and otherwise apply EXPAND to generate   child nodes. Each child node is added to the frontier if it has not been   reached before, or is re-added if it is now being reached with a path that   has a lower path cost than any previous path.   \n",
       "\n",
       "  **Search data structure**\n",
       "  Node.STATE/PARENT/ACTION/PATH-COST.  IS-EMPTY(frontier)/POP(frontier)/TOP(frontier)/ADD(node, frontier).  \n",
       "  Store the frontier : A priority queue (the minimum cost according to f)/A FIFO queue/A LIFO queue.  \n",
       "  \n",
       "  **A graph search** checks for redundant paths (if a node has been visited) and a tree-like search does not check.\n",
       "  \n",
       "  **Measuring Performance**  \n",
       "  Completeness,  Cost optimality, Time/space complexity  \n",
       "  d, the depth in an optimal solution; m, the maximum number of actions in any path; b, the branching factor.\n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       " **Uninformed Search**  \n",
       "  \n",
       "  **Breadth-first search** \n",
       "  possible infinite paths; some solutions have short paths; can quickly discard unlikely path  \n",
       "  **Depth-first search**  \n",
       "  if space is restricted; possible solutions with long path and wrong paths terminated quickly; search can be fine-tuned quickly  \n",
       "  **Depth-limited search**  \n",
       "  if l=d, then optimal; if l<d then incomplete; if l>d then not optimal  \n",
       "  **Iterative deepening search**\n",
       "  find best l.  \n",
       "  **bidirectional search**\n",
       "  searches both from the initial state and from the goal state(s)  \n",
       "  bidirectional best-first search, bidirectional uniform-cost search\n",
       "\n",
       "  **Dijkstra’s algorithm or uniform-cost search**  \n",
       "  weighted step-cost. choose a node with lowest path cost function **g(N)**  \n",
       "  tests for goals only when it expands a node, not when it generates a node (make sure it is optimal) \n",
       "\n",
       "## Module 3 Lecture Notes\n",
       " \n",
       "```\n",
       "{\n",
       "  function BEST-FIRST-SEARCH(problem,f ) returns a solution node or failure\n",
       "    node←NODE(STATE=problem.INITIAL)\n",
       "    frontier ←a priority queue ordered by f , with node as an element\n",
       "    reached ←a lookup table, with one entry with key problem.INITIAL and value node\n",
       "    while not IS-EMPTY(frontier) do\n",
       "      node←POP(frontier)\n",
       "      if problem.IS-GOAL(node.STATE) then return node\n",
       "      for each child in EXPAND(problem, node) do\n",
       "        s←child.STATE\n",
       "        if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n",
       "          reached[s]←child\n",
       "          add child to frontier\n",
       "    return failure\n",
       "    function EXPAND(problem, node) yields nodes\n",
       "      s←node.STATE\n",
       "      for each action in problem.ACTIONS(s) do\n",
       "        s′ ←problem.RESULT(s, action)\n",
       "        cost ←node.PATH-COST + problem.ACTION-COST(s, action, s′)\n",
       "        yield NODE(STATE=s′, PARENT=node, ACTION=action, PATH-COST=cost)\n",
       "}\n",
       "```\n",
       "\n",
       "```\n",
       "{\n",
       "  function BREADTH-FIRST-SEARCH(problem) returns a solution node or failure\n",
       "    node←NODE(problem.INITIAL)\n",
       "    if problem.IS-GOAL(node.STATE) then return node\n",
       "    frontier ←a FIFO queue, with node as an element\n",
       "    reached ←{problem.INITIAL}\n",
       "    while not IS-EMPTY(frontier) do\n",
       "      node←POP(frontier)\n",
       "      for each child in EXPAND(problem, node) do\n",
       "        s←child.STATE\n",
       "        if problem.IS-GOAL(s) then return child\n",
       "        if s is not in reached then\n",
       "          add s to reached\n",
       "          add child to frontier\n",
       "    return failure\n",
       "  function UNIFORM-COST-SEARCH(problem) returns a solution node, or failure\n",
       "    return BEST-FIRST-SEARCH(problem, PATH-COST)\n",
       "}\n",
       "```\n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "* **Search** - computation process to formulate the plan\n",
       "* **Solution** - a sequence of actions that reaches the goal or a path from the initial state to a goal state.\n",
       "* **Optimal solution:** - One solution that has the lowest path cost\n",
       "* **Abstraction** - the process of removing detail from a representation to get the model\n",
       "* **Frontier** - states that are available to expand\n",
       "* **A systematic search problem** - When exploring infinite state space, it can reach any state that is connected to the initial 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",
    "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": {
    "collapsed": true,
    "id": "tuFC8w7CyCns"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
    "chapter3_5 = \"\"\"Use a heuristic function, denoted **h(n)**   \n",
    "  \n",
    "  **Satisficing search: Inadmissible heuristics and weighted A∗**  \n",
    "  A* expands too many nodes --> we can accept inadmissable h(n) (e.g. detour index) and suboptimal solutions but are **satisficing** solutions.  \n",
    "  f (n) = g(n)+W × h(n), for some W > 1.  \n",
    "  If the optimal solution costs C∗, a weighted A∗ search will find a solution that costs between C∗ and W ×C∗ (much closer to C∗ than W ×C∗ in practice).  \n",
    "  \n",
    "  other suboptimal search algorithms: bounded suboptimal search (bounded by w×C*); bounded-cost search (< C); unbounded-cost search (quickly) \\\n",
    "  like speedy search (only consider #actions)  \n",
    "  \n",
    "  **Memory-bounded search**  \n",
    "   To save space : remove states from reached / frontier states, keep reference counts of #times a state has been reached  \n",
    "   **Beam search**: keep only the k nodes with the best f-scores (or δ of the best f-score) and discard other expanded nodes to limit the size of frontier  \n",
    "   **Iterative-deepening A∗ search (IDA∗)**: the cutoff is the f-cost (g + h). Searches an f-contour in each iteration  \n",
    "   **Recursive best-first search (RBFS)**: uses the **f-limit** variable to keep track of the f-value of the best alternative path available from any \\\n",
    "   ancestor of the current node.  \n",
    "   optimal if admissable, IDA* and RBFS use too little memory  \n",
    "   **MA∗ (memory-bounded A*)**  \n",
    "   **SMA∗ (simplified MA∗)**: proccess A* until memory is full, and drop one node with the highest f -value when adding a new one. It backs up the value \\\n",
    "   of the forgotten node to its parent.  \n",
    "   complete when d<memory size; optimal when optimal solution is reachable. time×  \n",
    "   \n",
    "   **Bidirectional heuristic search**: fF(n) = gF(n)+hF(n) and fB(n) = gB(n) + hB(n)  \n",
    "   lb(m,n) = max(gF(m)+ gB(n), fF(m), fB(n)). It works better when there's a worse heuristic\"\"\"\n",
    "chapter3_6 = \"\"\" **consistency**: A heuristic h(n) is consistent if, for every node n and every successor n′ of n generated by an action a, we have: \\\n",
    "  h(n) ≤ c(n,a,n′)+ h(n′) --> on an optimal path. Every consistent heuristic is admissible (but not vice versa).  \n",
    "  \n",
    "  **Search contours**  \n",
    "  g costs are monotonic; f costs are monotonic iff h is consistent ( A∗ with a consistent heuristic is **optimally efficient** ).  \n",
    "  If C∗ is the cost of the optimal solution path, A* expands nodes on the path f (n) < C∗ (surely expanded nodes) and f(n) = C*, but not f (n) > C∗ (pruned)  \n",
    "  \n",
    "  Use **the effective branching factor b*** to characterize the quality of a heuristic  \n",
    "  $ N + 1 = 1+ b* + (b*)^2 + ··· + (b*)^d $ , b* closer to 1 is h is better.  \n",
    "\n",
    "  If it is hard to decide which h is better, use $ h(n) = max\\{h_1(n),...,h_k(n)\\} $  ----------(A)\n",
    "\n",
    "  **Generating heuristics from subproblems: Pattern databases**  \n",
    "  For possible subproblem instance, store exact solution costs. Compute an admissible heuristic $h_{DB}$ for each configuration and use (A). (Or disjoint pattern databases)  \n",
    "\n",
    "  **Generating heuristics with landmarks**  \n",
    "  precomputation of some optimal path costs. choose landmark points; adding shortcuts  \n",
    "\n",
    "  **Learning to search better** metalevel state space  \n",
    "\n",
    "  **Learning heuristics from experience**: features $ h(n) = c_1*x_1(n) + c_2*x_2(n)$\n",
    "   \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module4_lecture_notes = \"\"\" **Greedy best-first search**  \n",
    "  Choose a node with lowest h(n).  \n",
    "  not optimal, not complete (but greedy best-first graph search is complete in finite state spaces), worst case O(b^m), \\\n",
    "  with a good heuristic function can reach O(b*m)  \n",
    "  \n",
    "  **A∗ search**  \n",
    "  Choose a node with lowest f(n) = g(n) + h(n), which is the estimated total cost of the best path through n to a goal. \n",
    "  Use a priority queue, and the goal should be at the top when terminate  \n",
    "  complete, optimal when h(n) is admissable  --> 0 <= h(n) <= h*(n)\n",
    "  \n",
    "  To define h(n) : relaxed problem. If h2(n) >= h1(n), then h2 dominates h1 (both admissable). h*(n) dominates all other heuristics. \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module4_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1193
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "63a6444e-44ac-45e4-da85-695f3d1582cc"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       "Use a heuristic function, denoted **h(n)**   \n",
       "  \n",
       "  **Satisficing search: Inadmissible heuristics and weighted A∗**  \n",
       "  A* expands too many nodes --> we can accept inadmissable h(n) (e.g. detour index) and suboptimal solutions but are **satisficing** solutions.  \n",
       "  f (n) = g(n)+W × h(n), for some W > 1.  \n",
       "  If the optimal solution costs C∗, a weighted A∗ search will find a solution that costs between C∗ and W ×C∗ (much closer to C∗ than W ×C∗ in practice).  \n",
       "  \n",
       "  other suboptimal search algorithms: bounded suboptimal search (bounded by w×C*); bounded-cost search (< C); unbounded-cost search (quickly)   like speedy search (only consider #actions)  \n",
       "  \n",
       "  **Memory-bounded search**  \n",
       "   To save space : remove states from reached / frontier states, keep reference counts of #times a state has been reached  \n",
       "   **Beam search**: keep only the k nodes with the best f-scores (or δ of the best f-score) and discard other expanded nodes to limit the size of frontier  \n",
       "   **Iterative-deepening A∗ search (IDA∗)**: the cutoff is the f-cost (g + h). Searches an f-contour in each iteration  \n",
       "   **Recursive best-first search (RBFS)**: uses the **f-limit** variable to keep track of the f-value of the best alternative path available from any    ancestor of the current node.  \n",
       "   optimal if admissable, IDA* and RBFS use too little memory  \n",
       "   **MA∗ (memory-bounded A*)**  \n",
       "   **SMA∗ (simplified MA∗)**: proccess A* until memory is full, and drop one node with the highest f -value when adding a new one. It backs up the value    of the forgotten node to its parent.  \n",
       "   complete when d<memory size; optimal when optimal solution is reachable. time×  \n",
       "   \n",
       "   **Bidirectional heuristic search**: fF(n) = gF(n)+hF(n) and fB(n) = gB(n) + hB(n)  \n",
       "   lb(m,n) = max(gF(m)+ gB(n), fF(m), fB(n)). It works better when there's a worse heuristic\n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       " **consistency**: A heuristic h(n) is consistent if, for every node n and every successor n′ of n generated by an action a, we have:   h(n) ≤ c(n,a,n′)+ h(n′) --> on an optimal path. Every consistent heuristic is admissible (but not vice versa).  \n",
       "  \n",
       "  **Search contours**  \n",
       "  g costs are monotonic; f costs are monotonic iff h is consistent ( A∗ with a consistent heuristic is **optimally efficient** ).  \n",
       "  If C∗ is the cost of the optimal solution path, A* expands nodes on the path f (n) < C∗ (surely expanded nodes) and f(n) = C*, but not f (n) > C∗ (pruned)  \n",
       "  \n",
       "  Use **the effective branching factor b*** to characterize the quality of a heuristic  \n",
       "  $ N + 1 = 1+ b* + (b*)^2 + ··· + (b*)^d $ , b* closer to 1 is h is better.  \n",
       "\n",
       "  If it is hard to decide which h is better, use $ h(n) = max\\{h_1(n),...,h_k(n)\\} $  ----------(A)\n",
       "\n",
       "  **Generating heuristics from subproblems: Pattern databases**  \n",
       "  For possible subproblem instance, store exact solution costs. Compute an admissible heuristic $h_{DB}$ for each configuration and use (A). (Or disjoint pattern databases)  \n",
       "\n",
       "  **Generating heuristics with landmarks**  \n",
       "  precomputation of some optimal path costs. choose landmark points; adding shortcuts  \n",
       "\n",
       "  **Learning to search better** metalevel state space  \n",
       "\n",
       "  **Learning heuristics from experience**: features $ h(n) = c_1*x_1(n) + c_2*x_2(n)$\n",
       "   \n",
       "\n",
       "## Module 4 Lecture Notes\n",
       " **Greedy best-first search**  \n",
       "  Choose a node with lowest h(n).  \n",
       "  not optimal, not complete (but greedy best-first graph search is complete in finite state spaces), worst case O(b^m),   with a good heuristic function can reach O(b*m)  \n",
       "  \n",
       "  **A∗ search**  \n",
       "  Choose a node with lowest f(n) = g(n) + h(n), which is the estimated total cost of the best path through n to a goal. \n",
       "  Use a priority queue, and the goal should be at the top when terminate  \n",
       "  complete, optimal when h(n) is admissable  --> 0 <= h(n) <= h*(n)\n",
       "  \n",
       "  To define h(n) : relaxed problem. If h2(n) >= h1(n), then h2 dominates h1 (both admissable). h*(n) dominates all other heuristics. \n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Concept** - 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",
    "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": {
    "collapsed": true,
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
    "chapter5_1 = \"\"\"  deterministic, two-player, turn-taking, perfect information, zero-sum games  \n",
    "  **Formalizing the game setup**  \n",
    "  The initial state, The player whose turn it is to move in state s, The set of legal moves in state s, The transition model/ Successor function, A terminal test, \\\n",
    "  A utility function/ evaluation functions f(n)  \n",
    "  A game tree: edges are legal moves and nodes are board positions \"\"\"\n",
    "chapter5_2 = \"\"\" minimiax value and minimax decision  \n",
    "  **The minimax search algorithm**  \n",
    "  time complexity  O(bm). space complexity: O(bm) if generates all actions at once, or O(m) if generates actions one at a time  \n",
    "\n",
    "  **Alpha–Beta Pruning**  \n",
    "  α = the value of the best choice we have found (highest-value) so far at any choice point along the path for MAX. Think: α = “at least.”  \n",
    "  β = the value of the best choice we have found (lowest-value) so far at any choice point along the path for MIN. Think: β = “at most.”  \n",
    "\n",
    "  **move ordering**: first examine the successors that are likely to be best.\n",
    "   \"\"\"\n",
    "chapter5_3 = \"\"\" **Evaluation functions**  \n",
    "  consider features of the state. weighted linear func: EVAL(s) = w1 f1(s) + w2 f2(s) + ··· + wn fn(s)  \n",
    "  \n",
    "  **Cutting off search** : if game.IS-CUTOFF(state, depth) then return game.EVAL(state, player), null  instead of terminal test  \n",
    "\n",
    "  The evaluation function should be applied only to positions that are quiescent(静态). Use singular extensions to avoid horizon effect (unavoidable cost)\n",
    "   \"\"\"\n",
    "chapter5_5 = \"\"\" **expectiminimax value** \"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
    "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
    "chapter16_2 = \"\"\" **Constraints on rational preferences**  \n",
    "   \"\"\"\n",
    "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module5_lecture_notes = \"\"\" **the simplest game environment**  \n",
    "  Multiagent, Static, Discrete, Fully observable, Strategic  \n",
    "  \n",
    "  **Key properties of our games**: two players alternate moves; zero-sum; legal moves are clear; well-defined outcomes  \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module5_definitions = {\n",
    "\"ply\" : \"one move of one player\",    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 967
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "d69b4911-e066-477e-df35-4fda210576f3"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       "  deterministic, two-player, turn-taking, perfect information, zero-sum games  \n",
       "  **Formalizing the game setup**  \n",
       "  The initial state, The player whose turn it is to move in state s, The set of legal moves in state s, The transition model/ Successor function, A terminal test,   A utility function/ evaluation functions f(n)  \n",
       "  A game tree: edges are legal moves and nodes are board positions \n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       " minimiax value and minimax decision  \n",
       "  **The minimax search algorithm**  \n",
       "  time complexity  O(bm). space complexity: O(bm) if generates all actions at once, or O(m) if generates actions one at a time  \n",
       "\n",
       "  **Alpha–Beta Pruning**  \n",
       "  α = the value of the best choice we have found (highest-value) so far at any choice point along the path for MAX. Think: α = “at least.”  \n",
       "  β = the value of the best choice we have found (lowest-value) so far at any choice point along the path for MIN. Think: β = “at most.”  \n",
       "\n",
       "  **move ordering**: first examine the successors that are likely to be best.\n",
       "   \n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       " **Evaluation functions**  \n",
       "  consider features of the state. weighted linear func: EVAL(s) = w1 f1(s) + w2 f2(s) + ··· + wn fn(s)  \n",
       "  \n",
       "  **Cutting off search** : if game.IS-CUTOFF(state, depth) then return game.EVAL(state, player), null  instead of terminal test  \n",
       "\n",
       "  The evaluation function should be applied only to positions that are quiescent(静态). Use singular extensions to avoid horizon effect (unavoidable cost)\n",
       "   \n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       " **expectiminimax value** \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",
       " **Constraints on rational preferences**  \n",
       "   \n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       " Your summary here \n",
       "\n",
       "## Module 5 Lecture Notes\n",
       " **the simplest game environment**  \n",
       "  Multiagent, Static, Discrete, Fully observable, Strategic  \n",
       "  \n",
       "  **Key properties of our games**: two players alternate moves; zero-sum; legal moves are clear; well-defined outcomes  \n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Ply** - one move of one player\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": {
    "collapsed": true,
    "id": "Wm4mfW82yaRH"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
    "chapter6_1 = \"\"\" three components <scope,rel>:  \n",
    "  X is a set of variables, {X1,... ,Xn}.  \n",
    "  D is a set of domains, {D1,...,Dn}, one for each variable.  \n",
    "  C is a set of constraints that specify allowable combinations of values.  \n",
    "  We want to find complete and consistent solutions.  \n",
    "\n",
    "  **Variations on the CSP formalism**  \n",
    "   1. we have discrete, finite domains; 2. infinite domains: linear/nolinear constraints.  \n",
    "   unary/binary/global constraints\n",
    "   \"\"\"\n",
    "chapter6_2 = \"\"\"  node-consistent; arc-consistent (AC-3); path consistency ;  \n",
    "  k-consistency : for any set of k−1 variables and for any consistent assignment to those variables, we can always find a consistent assignment to kth variable.  \n",
    "  strongly k-consistent: if it is k-consistent, (k−1)-consistent, (k−2)- consistent, ... 1-consistent. O(n^2*d), n = #nodes  \n",
    "  \n",
    "   global constraint, resource constraint, bounds constraint  \"\"\"\n",
    "chapter6_3 = \"\"\" \n",
    "   1.CSP as a search problem - **a backtracking search**  \n",
    "      DFS for a CSP problem \n",
    "      If we use DFS, then a tree with  n!*d^n is generated. But CSPs have commutativity! So we only consider a single variable at each node  \n",
    "\n",
    "   2.value ordering -- improve backtracking search  \n",
    "      a. minimum-remaining-values (MRV) heuristic : choose a variable with the fewest “legal” domain values (most constrained)  \n",
    "      b. degree heuristic:  choose the variable which is involved in the largest number of constraints on other unassigned variables (most constraining)    \n",
    "      After a variable has been selected,  \n",
    "      c. least-constraining-value heuristic: the value that rules out the fewest choices for the neighboring variables in the constraint graph  \n",
    "      d. forward checking: track the legal values until no remaining legal values + MRV\n",
    "      e. MAC (for Maintaining Arc Consistency) backtracking using AC-3  \n",
    "    \n",
    "   3. See 6_2  \n",
    "   \n",
    "   \n",
    "   **Intelligent backtracking: Looking backward**  \n",
    "   backtrack to a variable that cause the conflict:  conflict set for one variable -- backjumping method backtracks to the most recent assignment in the conflict set\n",
    "   \n",
    "   constraint learning: find a minimum set of variables from the conflict set\"\"\"\n",
    "chapter6_4 = \"\"\" \n",
    "```\n",
    "{\n",
    "  function MIN-CONFLICTS(csp, max steps) returns a solution or failure\n",
    "    inputs: csp, a constraint satisfaction problem\n",
    "        max steps, the number of steps allowed before giving up\n",
    "\n",
    "    current←an initial complete assignment for csp\n",
    "    for i = 1 to max steps do\n",
    "      if current is a solution for csp then return current\n",
    "      var←a randomly chosen conflicted variable from csp.VARIABLES\n",
    "      value←the value v for var that minimizes CONFLICTS(csp, var, v, current)\n",
    "      set var=value in current\n",
    "    return failure\n",
    "}\n",
    "``` \n",
    "The MIN-CONFLICTS local search algorithm for CSPs. The initial state may be\n",
    "chosen randomly or by a greedy assignment process that chooses a minimal-conflict value\n",
    "for each variable in turn. The CONFLICTS function counts the number of constraints violated\n",
    "by a particular value, given the rest of the current assignment.\"\"\"\n",
    "chapter6_5 = \"\"\" \n",
    "```\n",
    "{\n",
    "  function TREE-CSP-SOLVER(csp) returns a solution, or failure\n",
    "    inputs: csp, a CSP with components X, D, C\n",
    "    n←number of variables in X\n",
    "    assignment←an empty assignment\n",
    "    root←any variable in X\n",
    "    X ←TOPOLOGICALSORT(X,root)\n",
    "    for j = n down to 2 do\n",
    "      MAKE-ARC-CONSISTENT(PARENT(Xj),Xj)\n",
    "      if it cannot be made consistent then return failure\n",
    "    for i = 1 to n do\n",
    "      assignment[Xi]←any consistent value from Di\n",
    "      if there is no consistent value then return failure\n",
    "    return assignment\n",
    "}\n",
    "```\n",
    "\n",
    "The TREE-CSP-SOLVER algorithm for solving tree-structured CSPs. If the\n",
    "CSP has a solution, we will find it in linear time; if not, we will detect a contradiction.\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module6_lecture_notes = \"\"\" use a factored representation for each state, which includes a set of variables, and each of which has a value  \n",
    "\n",
    "  **the AC-3 algorithm** worst-case:O(n^2*d^3 = n^2*d*d^2)\n",
    "  1. Initialoze a queue of all the arcs;  \n",
    "  2. Pop off an arbitrary arc (Xi,Xj) from the queue and make Xi arc-consistent with respect to Xj;  \n",
    "  3. If Di unchanged -> move to next arc; if changed -> add to the queue all arcs (Xk,Xi) where Xk is a neighbor of Xi  \n",
    "  4. If Di becomes empty --> no consistent solution; otherwise remove values from the domains of variables until no more arcs are in the queue.\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module6_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1690
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "0fef3b32-d528-4fec-c7c9-f53d417566ec"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       " three components <scope,rel>:  \n",
       "  X is a set of variables, {X1,... ,Xn}.  \n",
       "  D is a set of domains, {D1,...,Dn}, one for each variable.  \n",
       "  C is a set of constraints that specify allowable combinations of values.  \n",
       "  We want to find complete and consistent solutions.  \n",
       "\n",
       "  **Variations on the CSP formalism**  \n",
       "   1. we have discrete, finite domains; 2. infinite domains: linear/nolinear constraints.  \n",
       "   unary/binary/global constraints\n",
       "   \n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       "  node-consistent; arc-consistent (AC-3); path consistency ;  \n",
       "  k-consistency : for any set of k−1 variables and for any consistent assignment to those variables, we can always find a consistent assignment to kth variable.  \n",
       "  strongly k-consistent: if it is k-consistent, (k−1)-consistent, (k−2)- consistent, ... 1-consistent. O(n^2*d), n = #nodes  \n",
       "  \n",
       "   global constraint, resource constraint, bounds constraint  \n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       " \n",
       "   1.CSP as a search problem - **a backtracking search**  \n",
       "      DFS for a CSP problem \n",
       "      If we use DFS, then a tree with  n!*d^n is generated. But CSPs have commutativity! So we only consider a single variable at each node  \n",
       "\n",
       "   2.value ordering -- improve backtracking search  \n",
       "      a. minimum-remaining-values (MRV) heuristic : choose a variable with the fewest “legal” domain values (most constrained)  \n",
       "      b. degree heuristic:  choose the variable which is involved in the largest number of constraints on other unassigned variables (most constraining)    \n",
       "      After a variable has been selected,  \n",
       "      c. least-constraining-value heuristic: the value that rules out the fewest choices for the neighboring variables in the constraint graph  \n",
       "      d. forward checking: track the legal values until no remaining legal values + MRV\n",
       "      e. MAC (for Maintaining Arc Consistency) backtracking using AC-3  \n",
       "    \n",
       "   3. See 6_2  \n",
       "   \n",
       "   \n",
       "   **Intelligent backtracking: Looking backward**  \n",
       "   backtrack to a variable that cause the conflict:  conflict set for one variable -- backjumping method backtracks to the most recent assignment in the conflict set\n",
       "   \n",
       "   constraint learning: find a minimum set of variables from the conflict set\n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       " \n",
       "```\n",
       "{\n",
       "  function MIN-CONFLICTS(csp, max steps) returns a solution or failure\n",
       "    inputs: csp, a constraint satisfaction problem\n",
       "        max steps, the number of steps allowed before giving up\n",
       "\n",
       "    current←an initial complete assignment for csp\n",
       "    for i = 1 to max steps do\n",
       "      if current is a solution for csp then return current\n",
       "      var←a randomly chosen conflicted variable from csp.VARIABLES\n",
       "      value←the value v for var that minimizes CONFLICTS(csp, var, v, current)\n",
       "      set var=value in current\n",
       "    return failure\n",
       "}\n",
       "``` \n",
       "The MIN-CONFLICTS local search algorithm for CSPs. The initial state may be\n",
       "chosen randomly or by a greedy assignment process that chooses a minimal-conflict value\n",
       "for each variable in turn. The CONFLICTS function counts the number of constraints violated\n",
       "by a particular value, given the rest of the current assignment.\n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       " \n",
       "```\n",
       "{\n",
       "  function TREE-CSP-SOLVER(csp) returns a solution, or failure\n",
       "    inputs: csp, a CSP with components X, D, C\n",
       "    n←number of variables in X\n",
       "    assignment←an empty assignment\n",
       "    root←any variable in X\n",
       "    X ←TOPOLOGICALSORT(X,root)\n",
       "    for j = n down to 2 do\n",
       "      MAKE-ARC-CONSISTENT(PARENT(Xj),Xj)\n",
       "      if it cannot be made consistent then return failure\n",
       "    for i = 1 to n do\n",
       "      assignment[Xi]←any consistent value from Di\n",
       "      if there is no consistent value then return failure\n",
       "    return assignment\n",
       "}\n",
       "```\n",
       "\n",
       "The TREE-CSP-SOLVER algorithm for solving tree-structured CSPs. If the\n",
       "CSP has a solution, we will find it in linear time; if not, we will detect a contradiction.\n",
       "\n",
       "## Module 6 Lecture Notes\n",
       " use a factored representation for each state, which includes a set of variables, and each of which has a value  \n",
       "\n",
       "  **the AC-3 algorithm** worst-case:O(n^2*d^3 = n^2*d*d^2)\n",
       "  1. Initialoze a queue of all the arcs;  \n",
       "  2. Pop off an arbitrary arc (Xi,Xj) from the queue and make Xi arc-consistent with respect to Xj;  \n",
       "  3. If Di unchanged -> move to next arc; if changed -> add to the queue all arcs (Xk,Xi) where Xk is a neighbor of Xi  \n",
       "  4. If Di becomes empty --> no consistent solution; otherwise remove values from the domains of variables until no more arcs are in the queue.\n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Concept** - 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",
    "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": 16,
   "metadata": {
    "collapsed": true,
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
    "\n",
    "chapter7_1 = \"\"\" **Knowledge based agents** can do **reasoning** over an internal **representation** of knowledge to act.  \n",
    "  TELL: add new sentences to the KB; ASK: query what is known. --involves inference  \n",
    "  First, it TELLs the KB what it perceives. Second, it ASKs what action it should perform using reasoning. Third, the agent \\\n",
    "  program TELLs the KB which action was chosen and returned so that it can be executed.\"\"\"\n",
    "\n",
    "chapter7_2 = \"\"\" **wumpus world** -- deterministic, discrete, static, single-agent, sequential, partially observable.    \n",
    "  PEAS Performance measure/ Environment / Actuator/ Sensors \"\"\"\n",
    "chapter7_3 = \"\"\" **Logic**  \n",
    "  KBs consist of sentences, which are follow certain syntax. A logic define the semantics of sentences (defines the truth in a possible world--a model).  \n",
    "  If a sentence $a$ is true in a model $m$, then $m \\quad statisfies \\quad a$ or $m \\quad is \\quad a \\quad model \\quad of \\quad a$. M(a) : the set of all models of a.  \n",
    "  \n",
    "  **logical reasoning**  \n",
    "  **entailment**: the sentence α entails the sentence β (α |= β). It means α |= β if and only if M(α) ⊆ M(β), and α is more specific.  \n",
    "  α is derived from KB by i : KB ⊢i α, in which i is an algorithm (the algorithm is sound if it only derives entailed sentences).\"\"\"\n",
    "chapter7_4 = \"\"\" **Propositional Logic** \"\"\"\n",
    "chapter7_5 = \"\"\" **Propositional Theorem Proving**  \n",
    "   logical equivalence (α ≡ β if and only if α |= β and β |= α); validity/tautologies 重言式(always true in every models)； satisfiability \\\n",
    "   （can be true）; the SAT problem (find out if it can be satisfied)  \n",
    "   \n",
    "   **inference rules**  \n",
    "   Modus Ponens假言推理 : given α ⇒ β and α, β can be inferred.  \n",
    "   And-Elimination 消去合取词: given α ∧ β, we can infer α. \n",
    "   plus All of the logical equivalences  \n",
    "   \n",
    "   **Proof by resolution** -- complete with any complete search algorithm  \n",
    "   **unit resolution**  inference rule: clause + literal(unit clause) -> clause  \n",
    "   **full resolution rule**.  \n",
    "   factoring: to make sure each literal only appears once  \n",
    "\n",
    "   **Conjunctive normal form**  \n",
    "\n",
    "   **A resolution algorithm**  -- complete\n",
    "   a. convert the sentence to CNF; b.apply the resolution rule; c.Each pair that contains complementary literals is resolved -> a new clause \\\n",
    "   (added to the set if it is not already present); d. continue until: no new clause then KB not |= α, empty clause then KB |= α;  \n",
    "\n",
    "   **Completeness of resolution**  \n",
    "   ground resolution theorem: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.  \n",
    "\n",
    "   1. Every definite clause can be written as an implication: a conjunction of positive literals -> a single positive literal.  \n",
    "   2. Inference with Horn clauses can be done through the forward-chaining (data-driven reasoning) or backward-chaining (goal-directed reasoning).  \n",
    "   3. Deciding entailment with Horn clauses can be done in time that is linear in the size of KB.\n",
    "   \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module7_definitions = {\n",
    "\"knowledge base\" : \"a set of sentences that represents some assertion about the world using knowledge representation language \", \n",
    "\"axiom\" : \"the sentence that is given at start\",\n",
    "\"model checking\" : \"enumerates all possible models to check if M(α) ⊆ M(β)\",\n",
    "\"resolution closure RC(S)\" : \"the final clauses of S after resolution\",\n",
    "\"definite clause\" : \" a disjunction of literals with only one positive\",\n",
    "\"Horn clasue\" : \"a disjunction of literals with at most one positive\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1163
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "e8e16944-875d-422f-a2ec-5f00f62162cc"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       " **Knowledge based agents** can do **reasoning** over an internal **representation** of knowledge to act.  \n",
       "  TELL: add new sentences to the KB; ASK: query what is known. --involves inference  \n",
       "  First, it TELLs the KB what it perceives. Second, it ASKs what action it should perform using reasoning. Third, the agent   program TELLs the KB which action was chosen and returned so that it can be executed.\n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       " **wumpus world** -- deterministic, discrete, static, single-agent, sequential, partially observable.    \n",
       "  PEAS Performance measure/ Environment / Actuator/ Sensors \n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       " **Logic**  \n",
       "  KBs consist of sentences, which are follow certain syntax. A logic define the semantics of sentences (defines the truth in a possible world--a model).  \n",
       "  If a sentence $a$ is true in a model $m$, then $m \\quad statisfies \\quad a$ or $m \\quad is \\quad a \\quad model \\quad of \\quad a$. M(a) : the set of all models of a.  \n",
       "  \n",
       "  **logical reasoning**  \n",
       "  **entailment**: the sentence α entails the sentence β (α |= β). It means α |= β if and only if M(α) ⊆ M(β), and α is more specific.  \n",
       "  α is derived from KB by i : KB ⊢i α, in which i is an algorithm (the algorithm is sound if it only derives entailed sentences).\n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       " **Propositional Logic** \n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       " **Propositional Theorem Proving**  \n",
       "   logical equivalence (α ≡ β if and only if α |= β and β |= α); validity/tautologies 重言式(always true in every models)； satisfiability    （can be true）; the SAT problem (find out if it can be satisfied)  \n",
       "   \n",
       "   **inference rules**  \n",
       "   Modus Ponens假言推理 : given α ⇒ β and α, β can be inferred.  \n",
       "   And-Elimination 消去合取词: given α ∧ β, we can infer α. \n",
       "   plus All of the logical equivalences  \n",
       "   \n",
       "   **Proof by resolution** -- complete with any complete search algorithm  \n",
       "   **unit resolution**  inference rule: clause + literal(unit clause) -> clause  \n",
       "   **full resolution rule**.  \n",
       "   factoring: to make sure each literal only appears once  \n",
       "\n",
       "   **Conjunctive normal form**  \n",
       "\n",
       "   **A resolution algorithm**  -- complete\n",
       "   a. convert the sentence to CNF; b.apply the resolution rule; c.Each pair that contains complementary literals is resolved -> a new clause    (added to the set if it is not already present); d. continue until: no new clause then KB not |= α, empty clause then KB |= α;  \n",
       "\n",
       "   **Completeness of resolution**  \n",
       "   ground resolution theorem: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.  \n",
       "\n",
       "   1. Every definite clause can be written as an implication: a conjunction of positive literals -> a single positive literal.  \n",
       "   2. Inference with Horn clauses can be done through the forward-chaining (data-driven reasoning) or backward-chaining (goal-directed reasoning).  \n",
       "   3. Deciding entailment with Horn clauses can be done in time that is linear in the size of KB.\n",
       "   \n",
       "\n",
       "## Module 7 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge base** - a set of sentences that represents some assertion about the world using knowledge representation language \n",
       "* **Axiom** - the sentence that is given at start\n",
       "* **Model checking** - enumerates all possible models to check if M(α) ⊆ M(β)\n",
       "* **Resolution closure rc(s)** - the final clauses of S after resolution\n",
       "* **Definite clause** -  a disjunction of literals with only one positive\n",
       "* **Horn clasue** - a disjunction of literals with at most one 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": 8981
    },
    "id": "T3cm1WV542_a",
    "outputId": "97206427-77a6-4df4-c982-79463b48171d"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       " Definition of AI: Some people defined intelligence as fidelity to humman performance. But formal definition is: **rationality** ('right thing'),   subject: thought process and reasoning, intelligent behavior.  \n",
       "   \n",
       "   **The Turing test approach**(the program passes the test if it fools the interrogator 30% of the time.). Computer would need these capabilities: a.NLP; b.knowledge represention;   c.automated reasoning; d.ML. **Total Turing test** requires interaction with objects and people in the real world. A robot will need e.CV and f.robotics to pass the test.  \n",
       "  \n",
       "  **The cognitive modeling approach**. Learn about human thought in three ways: a. introspection—trying to catch our own thoughts as they go by; b.psychological experiments;  c.brain imaging. The interdisciplinary field of cognitive science brings together computer models from AI and experimental Cognitive science techniques from psychology.  \n",
       "  \n",
       "  **The “laws of thought” approach**. Aristotle's syllogisms -> logic. Only knowledge that is certain -> probability.  \n",
       "  \n",
       "  **The rational agent approach**. A rational agent acts to achieve the best outcome or the best expected outcome (when there is uncertainty).  Act rationally needs skills to deduce and to pass the Turing test. Advantage of this approach: more general and more amentable to scientific development.  \n",
       "  \n",
       "  AI has focused on the study and construction of agents that **do the right thing**.  -> standard model (assumes that we will supply a fully specified objective to the machine)   The value alignment problem: the values or objectives put into the machine must be aligned with those of the human. We need agents that are provably beneficial to humans.\n",
       "  \n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       " Weak AI (acts if they were intelligent) and Strong AI (actually consciously thinking not just simulating thinking)  \n",
       "  \n",
       "  Turing’s “**argument from informality of behavior**” says that human behavior is far too complex to be captured by any formal set of rules.   Some phylo criticized Good Old-Fashioned AI (GOFAI) (computationalism). These AIs have difficulties in the qualification problem. The embodied   cognition approach claims that the body is embedded in an environment and we need to study the whole system.  \n",
       "  \n",
       "  **The argument from disability**. A machine can nerver do X and can never be exactly human.   \n",
       "  \n",
       "  **Godel ’s incompleteness theorem**: a.G(F) is a sentence of F, but cannot be proved within F. b.If F is consistent, then G(F) is true.\n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       " Turing extends **polite convention** to machines.  \n",
       "  \n",
       "  John Searle (a proponent of biological naturalism) rejects the polite convention. **Chinese room** - only symbol manipulation.  \n",
       "  \n",
       "  The big problem is about consciousness: whether machines can have qualia.\n",
       "  \n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       " An **agent**: anything that can be viewed as perceiving its environment through **sensors** 传感器感知 and   acting upon that environment through **actuators** 执行器操作.  \n",
       "  \n",
       "  **Percept and percept history**. An agent’s behavior is described by **the agent function** that maps any given percept   sequence to an action (not based on anything that hasn't been preceived). Internally, the agent function (abstract mathematical description) for an artificial   agent will be implemented by an **agent program** (concrete implementation). We can tabulating the agent function.\n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       " **The Concept of Rationality - do the right thing**  \n",
       "   \n",
       "   是什么- Consequentialism: See if the sequence of states caused by an agent's actions is desirable. It is better to design **performance measures** according to what    one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave. \n",
       "   \n",
       "   判断标准 - its expected performance is at least as good as any other agent’s. The same agent would be irrational under different circumstances - needs to know when to end.  \n",
       "\n",
       "   **Omniscience, learning, and autonomy**  \n",
       "\n",
       "  Distinguish between **rationality and omniscience (perfection）**: Rationality maximizes expected performance, while perfection maximizes actual performance.\n",
       "  \n",
       "  To define rationality: a. do not need to be perfect (we don't know future percept sequence); b. not rational given uninformative percept sequence; c. A rational agent   needs to do **information gathering** by exploring the environment. c. A rational agent not only to gather information but also to **learn** as much as possible from   what it perceives; d. **autonomous**: not only relies on the prior knowledge but also percepts and learning process.  \n",
       "   \n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       " \n",
       "  **task environment**: the Performance measure, the Environment, and the agent’s Actuators and Sensors.(the **PEAS** (Performance, Environment, Actuators, Sensors) description)   The virtual task environments can be just as complex as the “real” world: a software agent (or software robot or softbot).  \n",
       "  \n",
       "  **Properties of task environments**  \n",
       "  a. Fully observable ( if the sensors detect all aspects that are relevant to the choice of action) vs. partially observable;  \n",
       "  b. Single-agent vs. multiagent (can be competitve or cooperative). See whether B’s behavior is best described as maximizing a performance measure whose value depends on agent A’s behavior;  \n",
       "  c. Deterministic vs. nondeterministic or stochastic (given exact probability);  \n",
       "  d. Episodic vs. sequential(the current decision could affect all future decisions);  \n",
       "  e. Static vs. dynamic vs. semidynamic(environment itself doesn't change with the passage of time but the agent’s performance score does);  \n",
       "  f. Discrete vs. continuous. state, time, percepts and actions;  \n",
       "  g. Known vs. unknown.  \n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       " agent =  architecture (physical sensors/actuators) + program \n",
       "  \n",
       "  **Agent programs**  \n",
       "   take current percept as input 图片  \n",
       "\n",
       "  **Simple reflex agents**: condition–action rule, work only if the correct decision can be made on the basis of just the   current percept—that is, only if the environment is fully observable. randomize to avoid infinite loops  \n",
       "\n",
       "  **Model-based reflex agents**: keep track of a transition model of the world. uncertainty about the current state and the \n",
       "  agent still has to make a decision.  \n",
       "\n",
       "  **Goal-based agents**: search and planning. Consideration the future and this information is explicitly represented/   can be modified --> more flexible  \n",
       "\n",
       "  **Utility-based agents**: An agent’s utility function is essentially an internalization of the performance measure.  an agent that chooses actions to maximize its utility will be rational according to the external performance measure.\n",
       "  \n",
       "  Simple reflex agents respond directly to percepts, whereas model-based reflex agents maintain internal state to   track aspects of the world that are not evident in the current percept. Goal-based agents act to achieve their   goals, and utility-based agents try to maximize their own expected “happiness.”  \n",
       "\n",
       "  **learning agent**: learning element, performance element and problem generator\n",
       "  \n",
       "\n",
       "## Module 1 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - anything that can perceive and act in an environment\n",
       "* **Percept** - what an agent's sensors are perceiving from the environment \n",
       "* **Percept sequence** - the complete history that an agent has preceived\n",
       "* **A rational agent** - Given the evidence provided by the percept sequence and built-in knowledge, act to maximize its performance measure\n",
       "* **An omniscient agent** - Knows the actual outcome of its actions and can act accordingly, which is impossible in reality\n",
       "\n",
       "\n",
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       " Python is strong type (\"foo\"+2) and dynamic typing (x = \"foo\", x=2)  \n",
       "  Strings,Tuple, keys in Dictionaries (immutable), lists(mutable) \n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Mutability** - allows change\n",
       "\n",
       "\n",
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       " Assume the agent has the access to environment info.   \n",
       "  Four-phase problem-solving process:  \n",
       "  a. Goal formulation, b. Problem formulation: The agent devises a description of the states and actions   necessary to reach the goal; c. Search; d. Execution.  \n",
       "  \n",
       "  In a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence   of actions.\n",
       "  \n",
       "  **A search problem**  \n",
       "  Defined as : states - state space; initial state; goal states (one or more)/ goal test; actions (applicable); transition model   (waht the action does); action cost function/ path cost.  \n",
       "  Other concepts: path, optimal solution, graph.  \n",
       "  \n",
       "  **Formulating problems**\n",
       "  model, abstraction, level of abstraction (level of details).  \n",
       "  If an abstraction is valid: elaborate any abstract solution into a solution in the more detailed world;  \n",
       "  If it is useful: carrying out each of the actions in the solution is easier than the original problem.\n",
       "  If it is a good abstraction:  removing as much detail as possible while retaining validity and ensuring that it is useful.\n",
       "  \n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       " **standardized problem**  \n",
       "  eg. A grid world problem. The state space can be infinite  \n",
       "  **real-world problem**  \n",
       "  Route-finding problem, Touring problems ...\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       " **Search Algorithms**\n",
       "  a search tree: node - state, edge - action. parent node, child/successor node, frontier. expanded, generated, reached  \n",
       "  \n",
       "  **Best-first Search**  \n",
       "  Choose a node with minimum evaluation function, f(n).  \n",
       "  On each iteration, 1.choose a node on the frontier with minimum f(n) value,   2.if its state is a goal state then return, and otherwise apply EXPAND to generate   child nodes. Each child node is added to the frontier if it has not been   reached before, or is re-added if it is now being reached with a path that   has a lower path cost than any previous path.   \n",
       "\n",
       "  **Search data structure**\n",
       "  Node.STATE/PARENT/ACTION/PATH-COST.  IS-EMPTY(frontier)/POP(frontier)/TOP(frontier)/ADD(node, frontier).  \n",
       "  Store the frontier : A priority queue (the minimum cost according to f)/A FIFO queue/A LIFO queue.  \n",
       "  \n",
       "  **A graph search** checks for redundant paths (if a node has been visited) and a tree-like search does not check.\n",
       "  \n",
       "  **Measuring Performance**  \n",
       "  Completeness,  Cost optimality, Time/space complexity  \n",
       "  d, the depth in an optimal solution; m, the maximum number of actions in any path; b, the branching factor.\n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       " **Uninformed Search**  \n",
       "  \n",
       "  **Breadth-first search** \n",
       "  possible infinite paths; some solutions have short paths; can quickly discard unlikely path  \n",
       "  **Depth-first search**  \n",
       "  if space is restricted; possible solutions with long path and wrong paths terminated quickly; search can be fine-tuned quickly  \n",
       "  **Depth-limited search**  \n",
       "  if l=d, then optimal; if l<d then incomplete; if l>d then not optimal  \n",
       "  **Iterative deepening search**\n",
       "  find best l.  \n",
       "  **bidirectional search**\n",
       "  searches both from the initial state and from the goal state(s)  \n",
       "  bidirectional best-first search, bidirectional uniform-cost search\n",
       "\n",
       "  **Dijkstra’s algorithm or uniform-cost search**  \n",
       "  weighted step-cost. choose a node with lowest path cost function **g(N)**  \n",
       "  tests for goals only when it expands a node, not when it generates a node (make sure it is optimal) \n",
       "\n",
       "## Module 3 Lecture Notes\n",
       " \n",
       "```\n",
       "{\n",
       "  function BEST-FIRST-SEARCH(problem,f ) returns a solution node or failure\n",
       "    node←NODE(STATE=problem.INITIAL)\n",
       "    frontier ←a priority queue ordered by f , with node as an element\n",
       "    reached ←a lookup table, with one entry with key problem.INITIAL and value node\n",
       "    while not IS-EMPTY(frontier) do\n",
       "      node←POP(frontier)\n",
       "      if problem.IS-GOAL(node.STATE) then return node\n",
       "      for each child in EXPAND(problem, node) do\n",
       "        s←child.STATE\n",
       "        if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n",
       "          reached[s]←child\n",
       "          add child to frontier\n",
       "    return failure\n",
       "    function EXPAND(problem, node) yields nodes\n",
       "      s←node.STATE\n",
       "      for each action in problem.ACTIONS(s) do\n",
       "        s′ ←problem.RESULT(s, action)\n",
       "        cost ←node.PATH-COST + problem.ACTION-COST(s, action, s′)\n",
       "        yield NODE(STATE=s′, PARENT=node, ACTION=action, PATH-COST=cost)\n",
       "}\n",
       "```\n",
       "\n",
       "```\n",
       "{\n",
       "  function BREADTH-FIRST-SEARCH(problem) returns a solution node or failure\n",
       "    node←NODE(problem.INITIAL)\n",
       "    if problem.IS-GOAL(node.STATE) then return node\n",
       "    frontier ←a FIFO queue, with node as an element\n",
       "    reached ←{problem.INITIAL}\n",
       "    while not IS-EMPTY(frontier) do\n",
       "      node←POP(frontier)\n",
       "      for each child in EXPAND(problem, node) do\n",
       "        s←child.STATE\n",
       "        if problem.IS-GOAL(s) then return child\n",
       "        if s is not in reached then\n",
       "          add s to reached\n",
       "          add child to frontier\n",
       "    return failure\n",
       "  function UNIFORM-COST-SEARCH(problem) returns a solution node, or failure\n",
       "    return BEST-FIRST-SEARCH(problem, PATH-COST)\n",
       "}\n",
       "```\n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "* **Search** - computation process to formulate the plan\n",
       "* **Solution** - a sequence of actions that reaches the goal or a path from the initial state to a goal state.\n",
       "* **Optimal solution:** - One solution that has the lowest path cost\n",
       "* **Abstraction** - the process of removing detail from a representation to get the model\n",
       "* **Frontier** - states that are available to expand\n",
       "* **A systematic search problem** - When exploring infinite state space, it can reach any state that is connected to the initial state\n",
       "\n",
       "\n",
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       "Use a heuristic function, denoted **h(n)**   \n",
       "  \n",
       "  **Satisficing search: Inadmissible heuristics and weighted A∗**  \n",
       "  A* expands too many nodes --> we can accept inadmissable h(n) (e.g. detour index) and suboptimal solutions but are **satisficing** solutions.  \n",
       "  f (n) = g(n)+W × h(n), for some W > 1.  \n",
       "  If the optimal solution costs C∗, a weighted A∗ search will find a solution that costs between C∗ and W ×C∗ (much closer to C∗ than W ×C∗ in practice).  \n",
       "  \n",
       "  other suboptimal search algorithms: bounded suboptimal search (bounded by w×C*); bounded-cost search (< C); unbounded-cost search (quickly)   like speedy search (only consider #actions)  \n",
       "  \n",
       "  **Memory-bounded search**  \n",
       "   To save space : remove states from reached / frontier states, keep reference counts of #times a state has been reached  \n",
       "   **Beam search**: keep only the k nodes with the best f-scores (or δ of the best f-score) and discard other expanded nodes to limit the size of frontier  \n",
       "   **Iterative-deepening A∗ search (IDA∗)**: the cutoff is the f-cost (g + h). Searches an f-contour in each iteration  \n",
       "   **Recursive best-first search (RBFS)**: uses the **f-limit** variable to keep track of the f-value of the best alternative path available from any    ancestor of the current node.  \n",
       "   optimal if admissable, IDA* and RBFS use too little memory  \n",
       "   **MA∗ (memory-bounded A*)**  \n",
       "   **SMA∗ (simplified MA∗)**: proccess A* until memory is full, and drop one node with the highest f -value when adding a new one. It backs up the value    of the forgotten node to its parent.  \n",
       "   complete when d<memory size; optimal when optimal solution is reachable. time×  \n",
       "   \n",
       "   **Bidirectional heuristic search**: fF(n) = gF(n)+hF(n) and fB(n) = gB(n) + hB(n)  \n",
       "   lb(m,n) = max(gF(m)+ gB(n), fF(m), fB(n)). It works better when there's a worse heuristic\n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       " **consistency**: A heuristic h(n) is consistent if, for every node n and every successor n′ of n generated by an action a, we have:   h(n) ≤ c(n,a,n′)+ h(n′) --> on an optimal path. Every consistent heuristic is admissible (but not vice versa).  \n",
       "  \n",
       "  **Search contours**  \n",
       "  g costs are monotonic; f costs are monotonic iff h is consistent ( A∗ with a consistent heuristic is **optimally efficient** ).  \n",
       "  If C∗ is the cost of the optimal solution path, A* expands nodes on the path f (n) < C∗ (surely expanded nodes) and f(n) = C*, but not f (n) > C∗ (pruned)  \n",
       "  \n",
       "  Use **the effective branching factor b*** to characterize the quality of a heuristic  \n",
       "  $ N + 1 = 1+ b* + (b*)^2 + ··· + (b*)^d $ , b* closer to 1 is h is better.  \n",
       "\n",
       "  If it is hard to decide which h is better, use $ h(n) = max\\{h_1(n),...,h_k(n)\\} $  ----------(A)\n",
       "\n",
       "  **Generating heuristics from subproblems: Pattern databases**  \n",
       "  For possible subproblem instance, store exact solution costs. Compute an admissible heuristic $h_{DB}$ for each configuration and use (A). (Or disjoint pattern databases)  \n",
       "\n",
       "  **Generating heuristics with landmarks**  \n",
       "  precomputation of some optimal path costs. choose landmark points; adding shortcuts  \n",
       "\n",
       "  **Learning to search better** metalevel state space  \n",
       "\n",
       "  **Learning heuristics from experience**: features $ h(n) = c_1*x_1(n) + c_2*x_2(n)$\n",
       "   \n",
       "\n",
       "## Module 4 Lecture Notes\n",
       " **Greedy best-first search**  \n",
       "  Choose a node with lowest h(n).  \n",
       "  not optimal, not complete (but greedy best-first graph search is complete in finite state spaces), worst case O(b^m),   with a good heuristic function can reach O(b*m)  \n",
       "  \n",
       "  **A∗ search**  \n",
       "  Choose a node with lowest f(n) = g(n) + h(n), which is the estimated total cost of the best path through n to a goal. \n",
       "  Use a priority queue, and the goal should be at the top when terminate  \n",
       "  complete, optimal when h(n) is admissable  --> 0 <= h(n) <= h*(n)\n",
       "  \n",
       "  To define h(n) : relaxed problem. If h2(n) >= h1(n), then h2 dominates h1 (both admissable). h*(n) dominates all other heuristics. \n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       "  deterministic, two-player, turn-taking, perfect information, zero-sum games  \n",
       "  **Formalizing the game setup**  \n",
       "  The initial state, The player whose turn it is to move in state s, The set of legal moves in state s, The transition model/ Successor function, A terminal test,   A utility function/ evaluation functions f(n)  \n",
       "  A game tree: edges are legal moves and nodes are board positions \n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       " minimiax value and minimax decision  \n",
       "  **The minimax search algorithm**  \n",
       "  time complexity  O(bm). space complexity: O(bm) if generates all actions at once, or O(m) if generates actions one at a time  \n",
       "\n",
       "  **Alpha–Beta Pruning**  \n",
       "  α = the value of the best choice we have found (highest-value) so far at any choice point along the path for MAX. Think: α = “at least.”  \n",
       "  β = the value of the best choice we have found (lowest-value) so far at any choice point along the path for MIN. Think: β = “at most.”  \n",
       "\n",
       "  **move ordering**: first examine the successors that are likely to be best.\n",
       "   \n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       " **Evaluation functions**  \n",
       "  consider features of the state. weighted linear func: EVAL(s) = w1 f1(s) + w2 f2(s) + ··· + wn fn(s)  \n",
       "  \n",
       "  **Cutting off search** : if game.IS-CUTOFF(state, depth) then return game.EVAL(state, player), null  instead of terminal test  \n",
       "\n",
       "  The evaluation function should be applied only to positions that are quiescent(静态). Use singular extensions to avoid horizon effect (unavoidable cost)\n",
       "   \n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       " **expectiminimax value** \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",
       " **Constraints on rational preferences**  \n",
       "   \n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       " Your summary here \n",
       "\n",
       "## Module 5 Lecture Notes\n",
       " **the simplest game environment**  \n",
       "  Multiagent, Static, Discrete, Fully observable, Strategic  \n",
       "  \n",
       "  **Key properties of our games**: two players alternate moves; zero-sum; legal moves are clear; well-defined outcomes  \n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Ply** - one move of one player\n",
       "\n",
       "\n",
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       " three components <scope,rel>:  \n",
       "  X is a set of variables, {X1,... ,Xn}.  \n",
       "  D is a set of domains, {D1,...,Dn}, one for each variable.  \n",
       "  C is a set of constraints that specify allowable combinations of values.  \n",
       "  We want to find complete and consistent solutions.  \n",
       "\n",
       "  **Variations on the CSP formalism**  \n",
       "   1. we have discrete, finite domains; 2. infinite domains: linear/nolinear constraints.  \n",
       "   unary/binary/global constraints\n",
       "   \n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       "  node-consistent; arc-consistent (AC-3); path consistency ;  \n",
       "  k-consistency : for any set of k−1 variables and for any consistent assignment to those variables, we can always find a consistent assignment to kth variable.  \n",
       "  strongly k-consistent: if it is k-consistent, (k−1)-consistent, (k−2)- consistent, ... 1-consistent. O(n^2*d), n = #nodes  \n",
       "  \n",
       "   global constraint, resource constraint, bounds constraint  \n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       " \n",
       "   1.CSP as a search problem - **a backtracking search**  \n",
       "      DFS for a CSP problem \n",
       "      If we use DFS, then a tree with  n!*d^n is generated. But CSPs have commutativity! So we only consider a single variable at each node  \n",
       "\n",
       "   2.value ordering -- improve backtracking search  \n",
       "      a. minimum-remaining-values (MRV) heuristic : choose a variable with the fewest “legal” domain values (most constrained)  \n",
       "      b. degree heuristic:  choose the variable which is involved in the largest number of constraints on other unassigned variables (most constraining)    \n",
       "      After a variable has been selected,  \n",
       "      c. least-constraining-value heuristic: the value that rules out the fewest choices for the neighboring variables in the constraint graph  \n",
       "      d. forward checking: track the legal values until no remaining legal values + MRV\n",
       "      e. MAC (for Maintaining Arc Consistency) backtracking using AC-3  \n",
       "    \n",
       "   3. See 6_2  \n",
       "   \n",
       "   \n",
       "   **Intelligent backtracking: Looking backward**  \n",
       "   backtrack to a variable that cause the conflict:  conflict set for one variable -- backjumping method backtracks to the most recent assignment in the conflict set\n",
       "   \n",
       "   constraint learning: find a minimum set of variables from the conflict set\n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       " \n",
       "```\n",
       "{\n",
       "  function MIN-CONFLICTS(csp, max steps) returns a solution or failure\n",
       "    inputs: csp, a constraint satisfaction problem\n",
       "        max steps, the number of steps allowed before giving up\n",
       "\n",
       "    current←an initial complete assignment for csp\n",
       "    for i = 1 to max steps do\n",
       "      if current is a solution for csp then return current\n",
       "      var←a randomly chosen conflicted variable from csp.VARIABLES\n",
       "      value←the value v for var that minimizes CONFLICTS(csp, var, v, current)\n",
       "      set var=value in current\n",
       "    return failure\n",
       "}\n",
       "``` \n",
       "The MIN-CONFLICTS local search algorithm for CSPs. The initial state may be\n",
       "chosen randomly or by a greedy assignment process that chooses a minimal-conflict value\n",
       "for each variable in turn. The CONFLICTS function counts the number of constraints violated\n",
       "by a particular value, given the rest of the current assignment.\n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       " \n",
       "```\n",
       "{\n",
       "  function TREE-CSP-SOLVER(csp) returns a solution, or failure\n",
       "    inputs: csp, a CSP with components X, D, C\n",
       "    n←number of variables in X\n",
       "    assignment←an empty assignment\n",
       "    root←any variable in X\n",
       "    X ←TOPOLOGICALSORT(X,root)\n",
       "    for j = n down to 2 do\n",
       "      MAKE-ARC-CONSISTENT(PARENT(Xj),Xj)\n",
       "      if it cannot be made consistent then return failure\n",
       "    for i = 1 to n do\n",
       "      assignment[Xi]←any consistent value from Di\n",
       "      if there is no consistent value then return failure\n",
       "    return assignment\n",
       "}\n",
       "```\n",
       "\n",
       "The TREE-CSP-SOLVER algorithm for solving tree-structured CSPs. If the\n",
       "CSP has a solution, we will find it in linear time; if not, we will detect a contradiction.\n",
       "\n",
       "## Module 6 Lecture Notes\n",
       " use a factored representation for each state, which includes a set of variables, and each of which has a value  \n",
       "\n",
       "  **the AC-3 algorithm** worst-case:O(n^2*d^3 = n^2*d*d^2)\n",
       "  1. Initialoze a queue of all the arcs;  \n",
       "  2. Pop off an arbitrary arc (Xi,Xj) from the queue and make Xi arc-consistent with respect to Xj;  \n",
       "  3. If Di unchanged -> move to next arc; if changed -> add to the queue all arcs (Xk,Xi) where Xk is a neighbor of Xi  \n",
       "  4. If Di becomes empty --> no consistent solution; otherwise remove values from the domains of variables until no more arcs are in the queue.\n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       " **Knowledge based agents** can do **reasoning** over an internal **representation** of knowledge to act.  \n",
       "  TELL: add new sentences to the KB; ASK: query what is known. --involves inference  \n",
       "  First, it TELLs the KB what it perceives. Second, it ASKs what action it should perform using reasoning. Third, the agent   program TELLs the KB which action was chosen and returned so that it can be executed.\n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       " **wumpus world** -- deterministic, discrete, static, single-agent, sequential, partially observable.    \n",
       "  PEAS Performance measure/ Environment / Actuator/ Sensors \n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       " **Logic**  \n",
       "  KBs consist of sentences, which are follow certain syntax. A logic define the semantics of sentences (defines the truth in a possible world--a model).  \n",
       "  If a sentence $a$ is true in a model $m$, then $m \\quad statisfies \\quad a$ or $m \\quad is \\quad a \\quad model \\quad of \\quad a$. M(a) : the set of all models of a.  \n",
       "  \n",
       "  **logical reasoning**  \n",
       "  **entailment**: the sentence α entails the sentence β (α |= β). It means α |= β if and only if M(α) ⊆ M(β), and α is more specific.  \n",
       "  α is derived from KB by i : KB ⊢i α, in which i is an algorithm (the algorithm is sound if it only derives entailed sentences).\n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       " **Propositional Logic** \n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       " **Propositional Theorem Proving**  \n",
       "   logical equivalence (α ≡ β if and only if α |= β and β |= α); validity/tautologies 重言式(always true in every models)； satisfiability    （can be true）; the SAT problem (find out if it can be satisfied)  \n",
       "   \n",
       "   **inference rules**  \n",
       "   Modus Ponens假言推理 : given α ⇒ β and α, β can be inferred.  \n",
       "   And-Elimination 消去合取词: given α ∧ β, we can infer α. \n",
       "   plus All of the logical equivalences  \n",
       "   \n",
       "   **Proof by resolution** -- complete with any complete search algorithm  \n",
       "   **unit resolution**  inference rule: clause + literal(unit clause) -> clause  \n",
       "   **full resolution rule**.  \n",
       "   factoring: to make sure each literal only appears once  \n",
       "\n",
       "   **Conjunctive normal form**  \n",
       "\n",
       "   **A resolution algorithm**  -- complete\n",
       "   a. convert the sentence to CNF; b.apply the resolution rule; c.Each pair that contains complementary literals is resolved -> a new clause    (added to the set if it is not already present); d. continue until: no new clause then KB not |= α, empty clause then KB |= α;  \n",
       "\n",
       "   **Completeness of resolution**  \n",
       "   ground resolution theorem: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.  \n",
       "\n",
       "   1. Every definite clause can be written as an implication: a conjunction of positive literals -> a single positive literal.  \n",
       "   2. Inference with Horn clauses can be done through the forward-chaining (data-driven reasoning) or backward-chaining (goal-directed reasoning).  \n",
       "   3. Deciding entailment with Horn clauses can be done in time that is linear in the size of KB.\n",
       "   \n",
       "\n",
       "## Module 7 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge base** - a set of sentences that represents some assertion about the world using knowledge representation language \n",
       "* **Axiom** - the sentence that is given at start\n",
       "* **Model checking** - enumerates all possible models to check if M(α) ⊆ M(β)\n",
       "* **Resolution closure rc(s)** - the final clauses of S after resolution\n",
       "* **Definite clause** -  a disjunction of literals with only one positive\n",
       "* **Horn clasue** - a disjunction of literals with at most one 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))"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Copy of 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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
