{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "brNDGX-kvzds"
   },
   "source": [
    "# Template for Notes for CIS 521 Midterm 1\n",
    "\n",
    "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
    "\n",
    "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
    "\n",
    "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "aPtM8g7R0Pds"
   },
   "source": [
    "# Instructions\n",
    "\n",
    "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
    "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
    "3. Read the notes below about how you can format your summaries.\n",
    "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
    "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
    "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
    "* Run the last cell of this notebook\n",
    "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
    "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
    "* In the print options, change the layout from Landscape to Portrait. \n",
    "* Clicking the Save, will save a PDF that you can then print.\n",
    "\n",
    "## Formatting Notes\n",
    "\n",
    "1. The max length for each section's summary is 500 words / 3000 characters.\n",
    "2. You can also write a 2000 word summary of the lectures for each module.\n",
    "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
    "2. You can use Markdown formatting for your summaries. \n",
    "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
    "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
    "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
    "```\n",
    "def function():\n",
    "      print('hello world')\n",
    "```\n",
    "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "cw5IpDLCZa4W"
   },
   "source": [
    "## Example summary\n",
    "\n",
    "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "lzaavW96tcxM",
    "outputId": "c964d87e-a760-4c9e-af30-630c63b43a8e"
   },
   "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\n",
    "Only the first matching result will be shown. The search string is case sensitive, \\\n",
    "but it can consist of a single character or a sequence of characters. \\\n",
    "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
    "for characters over a range. The caret specifies the non-existence of a character. \\\n",
    "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
    "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
    "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
    "...\n",
    "\"\"\"\n",
    "\n",
    "length = len(chapter_2_1_example.split(\" \"))\n",
    "print(\"The example summary is {len} words long, so you could write an additional \\\n",
    "{remaining} words.\".format(len=length, remaining=(500-length)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "s3Uk9gQTevcj"
   },
   "source": [
    "## Example summary length\n",
    "\n",
    "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "8DvZ57A-djo1",
    "outputId": "7f1f002e-c266-40c0-a15c-d3562c1a87cc"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 500\n",
      "The length in characters is 3030\n"
     ]
    }
   ],
   "source": [
    "# This is an example of a 500 word placeholder\n",
    "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
    " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
    " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
    " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
    " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
    " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
    " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
    " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
    " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
    " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
    " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
    " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
    " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
    " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
    " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
    " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
    " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
    " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
    " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
    " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
    " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
    " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
    " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
    " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
    " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
    " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
    " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
    " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
    " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
    " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
    " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
    " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
    " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
    " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
    " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
    " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
    " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
    " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
    "\n",
    "print(\"The length in words is\", len(placeholder.split(' ')))\n",
    "print(\"The length in characters is\", len(placeholder))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "5yG3-YncJfTB"
   },
   "source": [
    "# Permissions to use your summaries\n",
    "\n",
    "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
    "\n",
    "1. Please enter your name.  \n",
    "\n",
    "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
    "\n",
    "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "2RECnJArJew4"
   },
   "outputs": [],
   "source": [
    "name = \"Hanye Wang\"\n",
    "permission = True\n",
    "anonymous = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GZZXyrV-xuAp"
   },
   "source": [
    "# Module 1 - Intro to AI"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "Y2NfE1CKxzS-"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
    "\n",
    "chapter1_1 = \"\"\"two dimensions—human vs. rational and thought vs. behavior; \\n\n",
    "Turing Test: natural language processing; knowledge representation;automated reasoning;machine learning.\\n\n",
    "Total Turing test: computer vision, robotics. intelligent agent takes the best actions so far.\\n\n",
    "The emphasis is correct inferences, but it is not always best\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
    "chapter27_1 = \"\"\n",
    "chapter27_2 = \"\"\n",
    "\n",
    "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
    "chapter2_1 = \"\"\n",
    "chapter2_2 = \"\"\"consequentialism: how to evaluate right. \\n\n",
    "Design performance measurement is better. \\n\n",
    "omniscience: impossible that know result ahead. \\n\n",
    "agent not only gather info but also learn.\"\"\"\n",
    "chapter2_3 = \"\"\"environment can be fully observable and partially observable; \\n\n",
    "Single agent or multiagent.(Randomized is rational in some competitive environment, but irrational in single-agent environment);\\n\n",
    "**Deterministic and nondeterministic**(the next state is determined by the current action or not), stochastic is about specific probabilities;\\n\n",
    "**episodic and sequential**(next state is independent or not);\\n\n",
    "**static and dynamic**(environment is changing); \\n\n",
    "**discrete/continuous**(about time)\"\"\"\n",
    "chapter2_4 = \"\"\"agent architecture and agent program forms an agent. \\n\n",
    "different agent:\\n\n",
    "**simple reflex agent** only cares current state, not state history.\\n\n",
    "**model-based:** considering internal state information. \\n\n",
    "**goal-based:** search and plan. \\n\n",
    "**unility-based:** maximizes the expected utility.\\n\n",
    "**atomic representation**: each state is independent, **factored representation** can be split to a fixed set of variables or attributes.\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module1_lecture_notes = \"\"\"**strong AI** - actually thinking; **weak AI** - simulating thinking.\\n\n",
    "design performance mearsure based on what we want to achieve.\\n\n",
    "**agent maximizes the 'expected' value of performace measure.**\\n\n",
    "When something behavior has its own performance measure, it is an agent.\\n\n",
    "A **problem-solving** agent must plan ahead.\\n\"\"\"\n",
    "\n",
    "\n",
    "# Definitions of concepts from Module 1.\n",
    "# You can define any bolded term in the textbook, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 20 words long.\n",
    "module1_definitions = {\n",
    "\"agent\" : \"anything that can perceive and act in an environment\",\n",
    "\"percept\" : \"what agent received\",\n",
    "\"Percept sequence\" : \"the history of recieved.\",\n",
    "\"Agent function\": \"the behavior how to be described(abstract math concept)\",\n",
    "\"agent program\": \"about implementation\",\n",
    "\"agent architecture\":\"the physical device\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "elCCgY64spuq"
   },
   "source": [
    "## Preview of your notes for Module 1\n",
    "\n",
    "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "gYYeNcdM_maE",
    "outputId": "11cb6a8d-7c3f-42ff-d7a7-5b9ec7c154d7"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       "two dimensions—human vs. rational and thought vs. behavior; \n",
       "\n",
       "Turing Test: natural language processing; knowledge representation;automated reasoning;machine learning.\n",
       "\n",
       "Total Turing test: computer vision, robotics. intelligent agent takes the best actions so far.\n",
       "\n",
       "The emphasis is correct inferences, but it is not always best\n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       "\n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       "\n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       "\n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       "consequentialism: how to evaluate right. \n",
       "\n",
       "Design performance measurement is better. \n",
       "\n",
       "omniscience: impossible that know result ahead. \n",
       "\n",
       "agent not only gather info but also learn.\n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       "environment can be fully observable and partially observable; \n",
       "\n",
       "Single agent or multiagent.(Randomized is rational in some competitive environment, but irrational in single-agent environment);\n",
       "\n",
       "**Deterministic and nondeterministic**(the next state is determined by the current action or not), stochastic is about specific probabilities;\n",
       "\n",
       "**episodic and sequential**(next state is independent or not);\n",
       "\n",
       "**static and dynamic**(environment is changing); \n",
       "\n",
       "**discrete/continuous**(about time)\n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       "agent architecture and agent program forms an agent. \n",
       "\n",
       "different agent:\n",
       "\n",
       "**simple reflex agent** only cares current state, not state history.\n",
       "\n",
       "**model-based:** considering internal state information. \n",
       "\n",
       "**goal-based:** search and plan. \n",
       "\n",
       "**unility-based:** maximizes the expected utility.\n",
       "\n",
       "**atomic representation**: each state is independent, **factored representation** can be split to a fixed set of variables or attributes.\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       "**strong AI** - actually thinking; **weak AI** - simulating thinking.\n",
       "\n",
       "design performance mearsure based on what we want to achieve.\n",
       "\n",
       "**agent maximizes the 'expected' value of performace measure.**\n",
       "\n",
       "When something behavior has its own performance measure, it is an agent.\n",
       "\n",
       "A **problem-solving** agent must plan ahead.\n",
       "\n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - anything that can perceive and act in an environment\n",
       "* **Percept** - what agent received\n",
       "* **Percept sequence** - the history of recieved.\n",
       "* **Agent function** - the behavior how to be described(abstract math concept)\n",
       "* **Agent program** - about implementation\n",
       "* **Agent architecture** - the physical device\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": {
    "id": "DpBvu7EMx7sy"
   },
   "outputs": [],
   "source": [
    "# No readings for this module.  Instead you can summarize the lecture instead.\n",
    "\n",
    "# Lecture notes \n",
    "module2_lecture_notes = \"\"\"**strong type**: all data are objects. and type is **determined auto**.\\n\n",
    "**Diferent type and their feature.**\\n\n",
    "mutable means we can assign a new value to the element, immutable means the elements cannnot be updated, only the immutable datatype can be used in dictionary's key.\\n\n",
    "**string** : **immutable**,\\n\n",
    "**list** : **mutable**, mixed types, ordered\\n\n",
    "**tuple** : **immutable**, mixed type. \\n\n",
    "**Dictionary**: **key-immutable**, unordered\\n\n",
    "no function **overloading** functions cannot have same name, unlike java.\\n\n",
    "Non-default argument **without default arguments** reports SyntaxError\\n\n",
    "**positional argument** follows keyword argument, so it the order is wrong with specific key provided, iti is fine\\n\n",
    "*args (one star): input is many **non-keyword** arguments, like list below.\\n\n",
    "```\n",
    "def get_elements(*args):\n",
    "    print(args)\n",
    "l=[1,2,3]\n",
    "get_elements(*l)\n",
    "```\n",
    "\n",
    "**kwargs(two stars): accept many **keyword arguments**, like dictionary below.\\n\n",
    "```\n",
    "def print_elements(**kwargs):\n",
    "  print(kwargs)\n",
    "dic={1:2}\n",
    "```\n",
    "1. print_elements(**dic)=>use dic buildt before.\\n\n",
    "2. print_elements(1=2)=>directly input\\n\n",
    "**extend**->class AI_Student(Student), means AI_Student is one tyoe fo student, so it extend the propoty of Student.\\n\n",
    "**Multiple inheritance**, one class can have more than one inheritnace.\\n\n",
    "**override**:To redefine a method of the parent class, include a new definition using the same name in the subclass.\\n\n",
    "**Iterators**->next()/__next__(), we can use next to get the next element, but we cannot use hasnext() in Python iterator. When wll element is visited, it will catch **StopIteration** error.\\n\n",
    "**yield**->**generator**: then it stops and returns the value that was yielded. Next time, it resumes where it left off, whic means it will continue the loop instead of begin a new loop. It can save space in some situation like print  elements after merge two lists\\n\n",
    "when using a class, there are two **calling methods**:\\n\n",
    "```\n",
    "cat1 = Cat(\"kitty\")\n",
    "1. cat1.play()\n",
    "2. Cat.play(cat1)\n",
    "```\n",
    "**Duck**: we can define duck typing outside any class:\\n\n",
    "```\n",
    "class Cat:\n",
    " def play(self):\n",
    "   print(\"the cat plays with me!\")\n",
    "def play(entity):\n",
    "  entity.play()\n",
    "```\n",
    "if the class doesn't have play method, there will be attributeError.\\n\n",
    "**interator**: iterator can make memory be used more efficiently. for lin in opne('file')=> return a iterator\\n\n",
    "Use '%': '%s -> %s'%(u,v) for u in l for v in w\\n\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Each definition should be at most 20 words long.\n",
    "module2_definitions = {\n",
    "\"mutability\" : \"The elements can be changed\",\n",
    "\"Higher order functions\": \"input is function\",\n",
    "\"First-class object\":\"the object that can be passed to other methond as a parameter, can be methond's return value, can be create during processing(created, destoryed dynamically) dynamically), and it have all rights as a normal variable.\\n\",\n",
    "\"magic methods\": \"these user-defined methods can be used as a build-in methods, like '__init__', '__len__', '__copy__', '__cmp__', '__add__', '__neg__'\",\n",
    "\"duck typing\": \"the method doesn't need any interface\"\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "ydOK__lwWgdp",
    "outputId": "a64e06da-deb1-45e8-cb3c-7f4977ddf6b5"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "## WARNING: Your definition of 'First-class object' is too long!\n",
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       "**strong type**: all data are objects. and type is **determined auto**.\n",
       "\n",
       "**Diferent type and their feature.**\n",
       "\n",
       "mutable means we can assign a new value to the element, immutable means the elements cannnot be updated, only the immutable datatype can be used in dictionary's key.\n",
       "\n",
       "**string** : **immutable**,\n",
       "\n",
       "**list** : **mutable**, mixed types, ordered\n",
       "\n",
       "**tuple** : **immutable**, mixed type. \n",
       "\n",
       "**Dictionary**: **key-immutable**, unordered\n",
       "\n",
       "no function **overloading** functions cannot have same name, unlike java.\n",
       "\n",
       "Non-default argument **without default arguments** reports SyntaxError\n",
       "\n",
       "**positional argument** follows keyword argument, so it the order is wrong with specific key provided, iti is fine\n",
       "\n",
       "*args (one star): input is many **non-keyword** arguments, like list below.\n",
       "\n",
       "```\n",
       "def get_elements(*args):\n",
       "    print(args)\n",
       "l=[1,2,3]\n",
       "get_elements(*l)\n",
       "```\n",
       "\n",
       "**kwargs(two stars): accept many **keyword arguments**, like dictionary below.\n",
       "\n",
       "```\n",
       "def print_elements(**kwargs):\n",
       "  print(kwargs)\n",
       "dic={1:2}\n",
       "```\n",
       "1. print_elements(**dic)=>use dic buildt before.\n",
       "\n",
       "2. print_elements(1=2)=>directly input\n",
       "\n",
       "**extend**->class AI_Student(Student), means AI_Student is one tyoe fo student, so it extend the propoty of Student.\n",
       "\n",
       "**Multiple inheritance**, one class can have more than one inheritnace.\n",
       "\n",
       "**override**:To redefine a method of the parent class, include a new definition using the same name in the subclass.\n",
       "\n",
       "**Iterators**->next()/__next__(), we can use next to get the next element, but we cannot use hasnext() in Python iterator. When wll element is visited, it will catch **StopIteration** error.\n",
       "\n",
       "**yield**->**generator**: then it stops and returns the value that was yielded. Next time, it resumes where it left off, whic means it will continue the loop instead of begin a new loop. It can save space in some situation like print  elements after merge two lists\n",
       "\n",
       "when using a class, there are two **calling methods**:\n",
       "\n",
       "```\n",
       "cat1 = Cat(\"kitty\")\n",
       "1. cat1.play()\n",
       "2. Cat.play(cat1)\n",
       "```\n",
       "**Duck**: we can define duck typing outside any class:\n",
       "\n",
       "```\n",
       "class Cat:\n",
       " def play(self):\n",
       "   print(\"the cat plays with me!\")\n",
       "def play(entity):\n",
       "  entity.play()\n",
       "```\n",
       "if the class doesn't have play method, there will be attributeError.\n",
       "\n",
       "**interator**: iterator can make memory be used more efficiently. for lin in opne('file')=> return a iterator\n",
       "\n",
       "Use '%': '%s -> %s'%(u,v) for u in l for v in w\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Mutability** - The elements can be changed\n",
       "* **Higher order functions** - input is function\n",
       "* **First-class object** - the object that can be passed to other methond as a parameter, can be methond's return value, can be create during processing(created, destoryed dynamically) dynamically), and it have all rights as a normal variable.\n",
       "\n",
       "* **Magic methods** - these user-defined methods can be used as a build-in methods, like '__init__', '__len__', '__copy__', '__cmp__', '__add__', '__neg__'\n",
       "* **Duck typing** - the method doesn't need any interface\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "\n",
    "module2_sections = [\n",
    "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
    "]\n",
    "\n",
    "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
    "display(Markdown(module2_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "46MQLR-Gx8dZ"
   },
   "source": [
    "#Module 3 - Search Problems"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "BN0b1eVYx-nd"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
    "chapter3_1 = \"\"\"a search problem can be descripted below: **state space**, **initial state**, **goal states**, **action**, **transition model**, **action cost function**.\"\"\"\n",
    "chapter3_2 = \"\"\n",
    "chapter3_3 = \"\"\"**priority queue: best-first search, queue: bfs, stack: dfs**.\\n\n",
    "**graph search**: **checks for redundant paths**. best-first search, \\n\n",
    "**tree-like search**: **not check redundant paths**.\\n\n",
    "different between graph search and tree search**: how we are traversing the search space.\\n\n",
    "1. In the case of a **graph search**, we use a list, called the closed list (also called **explored set**), to keep track of the nodes that have already been visited and expanded, so that they are not visited and expanded again.\\n\n",
    "2. In the case of a **tree search**, we **do not keep this closed list**. Consequently, the same node can be visited **multiple** (or even infinitely many) times, which means that the produced tree (by the tree search) may contain the same node multiple times.\\n\n",
    "graph search is that it uses **more memory** than tree search.\\n\n",
    "**four metrics of performance**: **completeness, cost optimality, time complexity, space complexity**.\"\"\"\n",
    "chapter3_4 = \"\"\"**uninformed search(no infomation about the distance from current state to the goal)**. \\n\n",
    "BFS-early goal test. Best-first search-late goal test.\\n\n",
    "**not:** $b$ is *maximum branching factor of search tree*; $d$ is *depth of the least cost solution*; $m$ is *maximum depth of the state space (∞)*\\n\n",
    "\n",
    "**BFS**\\n\n",
    "**implement structure**: queue, first in first out.\\n\n",
    "**time**: $O(b^d)$\\n\n",
    "**space**: $O(b^d)$(every node are stored in memeory).\\n\n",
    "Exponential space (and time) is not good.\\n\n",
    "**complete**: YES\\n\n",
    "**Optimal**: YES\\n\n",
    "\n",
    "**DFS**\\n\n",
    "**implement structure**: stack, last in first out.\\n\n",
    "**time**:$O(b^m)$, because it get all solutions, therefore use $m$ instead of $d$.\\n\n",
    "**space**: $O(bm)$, it is linear.\\n\n",
    "**complete**: NO\\n\n",
    "**Optimal**: NO\\n\n",
    "one variant of **DFS** is **backtracking** uses **less memory**, only one successor is generated at a time rather than all successors.\\n\n",
    "\n",
    "**Depth-limited Search**\\n\n",
    "**implement structure**: stack, last in first out.\\n\n",
    "supply a depth limit $l$, and treat all nodes at depth as if they had no successors\\n\n",
    "it is unnecessary to consider infinite cycle.\\n\n",
    "**time**: $O(b^l)$\\n\n",
    "**space**: $O(bl)$\\n\n",
    "**complete**: if $l<d$ then NO\\n\n",
    "**Optimal**: if $l==d$,then YES; if $l>d$, then NO\\n\n",
    "\n",
    "**Dijkstra/uniform-cost search**\\n\n",
    "a extension of BFS, considering path cost\\n\n",
    "**implement structure**: priority queue (min heap)\\n\n",
    "**time**: greater than BFS in worst case and similar to BFS when path cost is equal.\\n\n",
    "**space**: greater than BFS in worst case and similar to BFS when path cost is equal\\n\n",
    "**complete**: YES\\n\n",
    "**Optimal**: YES\\n\n",
    "\n",
    "**Iterative deepening search**\\n\n",
    "try limit $l$ from 1 and on\\n\n",
    "**time**: $O(b^d)$ with solution, $O(b^m)$ without solution. \\n\n",
    "**space**: $O(bd)$ with solution, $O(bm)$ without solution\\n\n",
    "**complete**: YES\\n\n",
    "**Optimal**: YES\\n\n",
    "In general, iterative deepening is the **preferred** uninformed search method when **the search state space is larger than memory requirement and the depth of the solution is not known**\\n\n",
    "```\n",
    "for $l = 0$ to ∞ do:\n",
    "  #depth-limited-serach to level $l$\n",
    "  if it succeeds\n",
    "    then return solution\n",
    "```\n",
    "\n",
    "**bidirectional search**\\n\n",
    "two directions: forward from the initial state and backwards from the goal state(s)\\n\n",
    "**time**: $O(b^{d/2})$\\n\n",
    "**complete**: YES\\n\n",
    "**Optimal**: YES\\n\n",
    "\n",
    "**completed and optimal cost**: **bfs, uniform, iterative, bidirectinal**.\\n\n",
    "**not completed and not optimal**: **dfs, depth-limited(can have loop)**\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module3_lecture_notes = \"\"\"**search tree**: Enumerate in some order all possible paths from the initial state. \\n\n",
    "**search graph** : Check to see if a node has been visited before adding to search queue\\n\n",
    "If there are a lot of solutions, DFS may be much faster than BFS.\"\"\"\n",
    "\n",
    "# Definitions of concepts from Module 3.\n",
    "# You can define any bolded term in the textbook, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 20 words long.\n",
    "module3_definitions = {\n",
    "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",  \n",
    "\"state space\":\"a set of possibile states\",\n",
    "\"completeness\": \"it is ensure that the algo can find the solution or report error\",\n",
    "\"frontier\": \"legal expandable states\",\n",
    "\"Uninformed search\": \"non-goal nodes looks same\",\n",
    "\"informed search\": \"non-goal nodes are different\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "c9e4ddd2-d633-4442-cb5d-8d590ff06360"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       "a search problem can be descripted below: **state space**, **initial state**, **goal states**, **action**, **transition model**, **action cost function**.\n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       "**priority queue: best-first search, queue: bfs, stack: dfs**.\n",
       "\n",
       "**graph search**: **checks for redundant paths**. best-first search, \n",
       "\n",
       "**tree-like search**: **not check redundant paths**.\n",
       "\n",
       "different between graph search and tree search**: how we are traversing the search space.\n",
       "\n",
       "1. In the case of a **graph search**, we use a list, called the closed list (also called **explored set**), to keep track of the nodes that have already been visited and expanded, so that they are not visited and expanded again.\n",
       "\n",
       "2. In the case of a **tree search**, we **do not keep this closed list**. Consequently, the same node can be visited **multiple** (or even infinitely many) times, which means that the produced tree (by the tree search) may contain the same node multiple times.\n",
       "\n",
       "graph search is that it uses **more memory** than tree search.\n",
       "\n",
       "**four metrics of performance**: **completeness, cost optimality, time complexity, space complexity**.\n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       "**uninformed search(no infomation about the distance from current state to the goal)**. \n",
       "\n",
       "BFS-early goal test. Best-first search-late goal test.\n",
       "\n",
       "**not:** $b$ is *maximum branching factor of search tree*; $d$ is *depth of the least cost solution*; $m$ is *maximum depth of the state space (∞)*\n",
       "\n",
       "\n",
       "**BFS**\n",
       "\n",
       "**implement structure**: queue, first in first out.\n",
       "\n",
       "**time**: $O(b^d)$\n",
       "\n",
       "**space**: $O(b^d)$(every node are stored in memeory).\n",
       "\n",
       "Exponential space (and time) is not good.\n",
       "\n",
       "**complete**: YES\n",
       "\n",
       "**Optimal**: YES\n",
       "\n",
       "\n",
       "**DFS**\n",
       "\n",
       "**implement structure**: stack, last in first out.\n",
       "\n",
       "**time**:$O(b^m)$, because it get all solutions, therefore use $m$ instead of $d$.\n",
       "\n",
       "**space**: $O(bm)$, it is linear.\n",
       "\n",
       "**complete**: NO\n",
       "\n",
       "**Optimal**: NO\n",
       "\n",
       "one variant of **DFS** is **backtracking** uses **less memory**, only one successor is generated at a time rather than all successors.\n",
       "\n",
       "\n",
       "**Depth-limited Search**\n",
       "\n",
       "**implement structure**: stack, last in first out.\n",
       "\n",
       "supply a depth limit $l$, and treat all nodes at depth as if they had no successors\n",
       "\n",
       "it is unnecessary to consider infinite cycle.\n",
       "\n",
       "**time**: $O(b^l)$\n",
       "\n",
       "**space**: $O(bl)$\n",
       "\n",
       "**complete**: if $l<d$ then NO\n",
       "\n",
       "**Optimal**: if $l==d$,then YES; if $l>d$, then NO\n",
       "\n",
       "\n",
       "**Dijkstra/uniform-cost search**\n",
       "\n",
       "a extension of BFS, considering path cost\n",
       "\n",
       "**implement structure**: priority queue (min heap)\n",
       "\n",
       "**time**: greater than BFS in worst case and similar to BFS when path cost is equal.\n",
       "\n",
       "**space**: greater than BFS in worst case and similar to BFS when path cost is equal\n",
       "\n",
       "**complete**: YES\n",
       "\n",
       "**Optimal**: YES\n",
       "\n",
       "\n",
       "**Iterative deepening search**\n",
       "\n",
       "try limit $l$ from 1 and on\n",
       "\n",
       "**time**: $O(b^d)$ with solution, $O(b^m)$ without solution. \n",
       "\n",
       "**space**: $O(bd)$ with solution, $O(bm)$ without solution\n",
       "\n",
       "**complete**: YES\n",
       "\n",
       "**Optimal**: YES\n",
       "\n",
       "In general, iterative deepening is the **preferred** uninformed search method when **the search state space is larger than memory requirement and the depth of the solution is not known**\n",
       "\n",
       "```\n",
       "for $l = 0$ to ∞ do:\n",
       "  #depth-limited-serach to level $l$\n",
       "  if it succeeds\n",
       "    then return solution\n",
       "```\n",
       "\n",
       "**bidirectional search**\n",
       "\n",
       "two directions: forward from the initial state and backwards from the goal state(s)\n",
       "\n",
       "**time**: $O(b^{d/2})$\n",
       "\n",
       "**complete**: YES\n",
       "\n",
       "**Optimal**: YES\n",
       "\n",
       "\n",
       "**completed and optimal cost**: **bfs, uniform, iterative, bidirectinal**.\n",
       "\n",
       "**not completed and not optimal**: **dfs, depth-limited(can have loop)**\n",
       "\n",
       "## Module 3 Lecture Notes\n",
       "**search tree**: Enumerate in some order all possible paths from the initial state. \n",
       "\n",
       "**search graph** : Check to see if a node has been visited before adding to search queue\n",
       "\n",
       "If there are a lot of solutions, DFS may be much faster than BFS.\n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "* **State space** - a set of possibile states\n",
       "* **Completeness** - it is ensure that the algo can find the solution or report error\n",
       "* **Frontier** - legal expandable states\n",
       "* **Uninformed search** - non-goal nodes looks same\n",
       "* **Informed search** - non-goal nodes are different\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module3_sections = [\n",
    "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
    "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
    "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
    "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
    "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
    "]\n",
    "\n",
    "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
    "display(Markdown(module3_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WHREsHSSyA-h"
   },
   "source": [
    "#Module 4 - Informed Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "tuFC8w7CyCns"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
    "chapter3_5 = \"\"\"heuristic function gives the path with lowest cost from current position to the goal position.\\n\n",
    "**greedy best-first serach**\\n\n",
    "doesn't guarantee to find the best solution, it is complete in finite case, not infinite case. $O(bm)$.\\n\n",
    "The way to evaluate different node is function $f(n)$, which is the estimated distance from current position to goal\\n\n",
    "So $f(n)=h(n)$\\n\n",
    "\n",
    "**A* search is complete and cost-optimal** with consistent admissible heuristic.\\n\n",
    "**consistency**---$h(n) ≤ c(n, a, n′) + h(n′)$, which is a **triangle inequality**.\\n\n",
    "**With an *inadmissible heuristic*, A* may not be cost-optimal**. If A* search is consistent heuristic, it is optimal efficient because it prunes many possibilities, and the value of $g(n)+h(n)$ is monotonical. but it cannot find the optimal solution when the number of nodes expanded can be **exponential**.\\n\n",
    "**Beam search** keep only the nodes with the best scores as frontier.\"\"\"\n",
    "chapter3_6 = \"\"\"If h1 **dominates** h2, $h1(n)>=h2(n)$, h1 is more accurate than h2. When they ar both admissible, larger value means more accurate\\n\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module4_lecture_notes = \"\"\"tree search: uniform-cost search **frontier = priority queue ordered by $g(n)**$\\n\n",
    "A* is optimal with admissible heuristic\\n\n",
    "**The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.**\\n\n",
    "\n",
    "**uniform-cost search**\\n\n",
    "difference between BFS and UCS is it check the node is goal or not when the node is selected before it is added to the frontier.\\n\n",
    "use priority queue beased on path cost.\\n\n",
    "**best-first search**\\n\n",
    "sort frontier according to the estimate distance from current position to goal, $h(n)=h(n)$\\n\n",
    "**two kind of best-first search**\\n\n",
    "\n",
    "1. **greedy best-forst search**\\n\n",
    "```\n",
    "frontier = PriorityQueue()\n",
    "frontier.put(start, 0)\n",
    "came_from={}\n",
    "came_from[start]=None\n",
    "while not frontier.empty():\n",
    "  current = frontier.get()\n",
    "  if current==goal:\n",
    "    break\n",
    "  for next in graph.neighbors(current):\n",
    "    if next not in came_from:\n",
    "      priority = heuristic(goal, next) # get the distance $h(n)$ from next position to goal\n",
    "      frontier.put(next, priority)\n",
    "      came_from[next]=current\n",
    "```\n",
    "**optimal**: NO\\n\n",
    "**complete**: NO(can be in a cycle)\\n\n",
    "\n",
    "2. **A-star search**\\n\n",
    "expand most promising node in the priority queue\\n\n",
    "**$f(n)=g(n)+h(n)$**\\n\n",
    "**optimal**: YES if it have admissible heiristic\\n\n",
    "\n",
    "**admissible huristics**\\n\n",
    "$0 \\leq h(n) \\leq h*(n)$=> real distance\\n\n",
    "if A is optimal node and B is suboptimal node, and h is admissible, A will finish before B\\n\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module4_definitions = {\n",
    "\"informed search\" : \"have information of goal's location, and the information is given as a heuristic function\",\n",
    "\"Greedy best-first search\": \"a type of best-first search that select node with lowest heuristic value, f(n)=h(n)\",\n",
    "\"A* search\": \"estimate the best value continue from current pos to the goal pos, plus the path value already taken from start state to current pos, f(n)=g(n)+h(n)\",\n",
    "\"admissible heuristic\": \"never overestimate the path cost, so it is optimistic\",\n",
    "\"prune\": \"remove some possibilities without test them\",\n",
    "\"weighted A* search\":\"weight h(h) more heavily so it can be inadmissible heuristic, but find a good enough solution and improve efficiency\",\n",
    "\"bounded suboptimal search\": \"the factor W is constant\",\n",
    "\"bounded-cost search\":\"cost must lower than C\",\n",
    "\"unbounded-cost search\":\"accept any solution if we can get it quickly, like speedy search(greedy best-first search)\",\n",
    "\"relaxed problem\":\"The problem with less restriction compared with original problem in action rules\",\n",
    "\"heuristic funtion\":\"claculate and estimate the distance from current position to the goal\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "b7646e60-a8fa-4b5a-fa22-772bb587d450"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "## WARNING: Your definition of 'A* search' is too long!\n",
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       "heuristic function gives the path with lowest cost from current position to the goal position.\n",
       "\n",
       "**greedy best-first serach**\n",
       "\n",
       "doesn't guarantee to find the best solution, it is complete in finite case, not infinite case. $O(bm)$.\n",
       "\n",
       "The way to evaluate different node is function $f(n)$, which is the estimated distance from current position to goal\n",
       "\n",
       "So $f(n)=h(n)$\n",
       "\n",
       "\n",
       "**A* search is complete and cost-optimal** with consistent admissible heuristic.\n",
       "\n",
       "**consistency**---$h(n) ≤ c(n, a, n′) + h(n′)$, which is a **triangle inequality**.\n",
       "\n",
       "**With an *inadmissible heuristic*, A* may not be cost-optimal**. If A* search is consistent heuristic, it is optimal efficient because it prunes many possibilities, and the value of $g(n)+h(n)$ is monotonical. but it cannot find the optimal solution when the number of nodes expanded can be **exponential**.\n",
       "\n",
       "**Beam search** keep only the nodes with the best scores as frontier.\n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       "If h1 **dominates** h2, $h1(n)>=h2(n)$, h1 is more accurate than h2. When they ar both admissible, larger value means more accurate\n",
       "\n",
       "\n",
       "## Module 4 Lecture Notes\n",
       "tree search: uniform-cost search **frontier = priority queue ordered by $g(n)**$\n",
       "\n",
       "A* is optimal with admissible heuristic\n",
       "\n",
       "**The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.**\n",
       "\n",
       "\n",
       "**uniform-cost search**\n",
       "\n",
       "difference between BFS and UCS is it check the node is goal or not when the node is selected before it is added to the frontier.\n",
       "\n",
       "use priority queue beased on path cost.\n",
       "\n",
       "**best-first search**\n",
       "\n",
       "sort frontier according to the estimate distance from current position to goal, $h(n)=h(n)$\n",
       "\n",
       "**two kind of best-first search**\n",
       "\n",
       "\n",
       "1. **greedy best-forst search**\n",
       "\n",
       "```\n",
       "frontier = PriorityQueue()\n",
       "frontier.put(start, 0)\n",
       "came_from={}\n",
       "came_from[start]=None\n",
       "while not frontier.empty():\n",
       "  current = frontier.get()\n",
       "  if current==goal:\n",
       "    break\n",
       "  for next in graph.neighbors(current):\n",
       "    if next not in came_from:\n",
       "      priority = heuristic(goal, next) # get the distance $h(n)$ from next position to goal\n",
       "      frontier.put(next, priority)\n",
       "      came_from[next]=current\n",
       "```\n",
       "**optimal**: NO\n",
       "\n",
       "**complete**: NO(can be in a cycle)\n",
       "\n",
       "\n",
       "2. **A-star search**\n",
       "\n",
       "expand most promising node in the priority queue\n",
       "\n",
       "**$f(n)=g(n)+h(n)$**\n",
       "\n",
       "**optimal**: YES if it have admissible heiristic\n",
       "\n",
       "\n",
       "**admissible huristics**\n",
       "\n",
       "$0 \\leq h(n) \\leq h*(n)$=> real distance\n",
       "\n",
       "if A is optimal node and B is suboptimal node, and h is admissible, A will finish before B\n",
       "\n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Informed search** - have information of goal's location, and the information is given as a heuristic function\n",
       "* **Greedy best-first search** - a type of best-first search that select node with lowest heuristic value, f(n)=h(n)\n",
       "* **A* search** - estimate the best value continue from current pos to the goal pos, plus the path value already taken from start state to current pos, f(n)=g(n)+h(n)\n",
       "* **Admissible heuristic** - never overestimate the path cost, so it is optimistic\n",
       "* **Prune** - remove some possibilities without test them\n",
       "* **Weighted a* search** - weight h(h) more heavily so it can be inadmissible heuristic, but find a good enough solution and improve efficiency\n",
       "* **Bounded suboptimal search** - the factor W is constant\n",
       "* **Bounded-cost search** - cost must lower than C\n",
       "* **Unbounded-cost search** - accept any solution if we can get it quickly, like speedy search(greedy best-first search)\n",
       "* **Relaxed problem** - The problem with less restriction compared with original problem in action rules\n",
       "* **Heuristic funtion** - claculate and estimate the distance from current position to the goal\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module4_sections = [\n",
    "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
    "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
    "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
    "]\n",
    "\n",
    "module4_markdown = format_module(4, \"Informed Search\", \n",
    "                         module4_sections, \n",
    "                         module4_definitions)\n",
    "display(Markdown(module4_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F3FPMzG9yUls"
   },
   "source": [
    "#Module 5 - Adversarial Search and Games"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
    "chapter5_1 = \"\"\"game is formed by **initial state, the player to move, actions(s)-legal moves, result(transition model), terminal test, utility function**.\"\"\"\n",
    "chapter5_2 = \"\"\"the player chooses the option with **highest minimax value**. \\n\n",
    "The minimax algorithm is **complete dfs**.\\n\n",
    "**Time**: $O(b^m)$-tree. $m$-maximum depth of the tree, $b$-legal moves at each point.\\n\n",
    "**Space**: $O(bm)$-every action once, $O(m)$-generate action once a time.\\n\n",
    "**alpha–beta pruning** prunes many possibilities having no influence. \\n\n",
    "Only exams $O(b^{m/2})$, the branching factor is $sqrt(b)$ instead of $b$.\\n\n",
    "**$alpha$**: the value of the best choice we have found so far **for MAX player**, means **at least**.\\n\n",
    "**$beta$**: the value of the best choice we have found so far **for MIN player**, means **at most**.\\n\n",
    "If the value is **less than alpha for MAX($value<alpha$)** or **greater than beta for MIN$(value>beta$)**, just skip it.\\n\n",
    "**For MAX function, if exploring value is greater than the $beta$, stop exploring, else-set $alpha$ as the largest value.**\\n\n",
    "**For MIN function, if exploring value is less than the $alpha$, stop exploring, else-set $beta$ as the least value.**\"\"\"\n",
    "chapter5_3 = \"\"\n",
    "chapter5_5 = \"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
    "chapter16_1 = \"\"\n",
    "chapter16_2 = \"\"\n",
    "chapter16_3 = \"\"\n",
    "\n",
    "# Lecture notes \n",
    "module5_lecture_notes = \"\"\"Game tree represent the game problem space by a tree.\\n\n",
    "Simplest Game Environment: **nultiagent, static, discrete(infite actions), fully observable, strategic**\\n\n",
    "we use $f(n)$ to **evaluate the situation** of game: \\n\n",
    "1. $f(n)>0$-MAX palyer win in this position\\n\n",
    "2. $f(n)=0$-tied\\n\n",
    "3. $f(n)<0$-MIN palyer win in this position\\n\n",
    "\n",
    "**Minimax**\\n\n",
    "**assumption: MAX take action based on the assumption that MIN player will move perfectly**\\n\n",
    "```\n",
    "def max-value(state):\n",
    "  if the state is a terminal state:\n",
    "    return the state's utility\n",
    "  initialize v=-∞\n",
    "  for each successor of state:\n",
    "    v=max(v, min-value(successor))\n",
    "  return v\n",
    "\n",
    "def min-value(state):\n",
    "  if the state is a terminal state:\n",
    "    return the state's utility\n",
    "  initialize v=+∞\n",
    "  for each successor of state:\n",
    "    v=min(v, max-value(successor))\n",
    "  return v\n",
    "```\n",
    "**Alpha-Beta Pruning**\\n\n",
    "Different between Minimax and Alpha-beta pruning: **keep track of current lower bound(alpha) on MAX and upper bound(beta) on MIN **\\n\n",
    "```\n",
    "def max_value(alpha, beta):\n",
    "  if is-terminal:\n",
    "    return XX\n",
    "  v=-∞\n",
    "  for each a in game.action(state):\n",
    "    v2, a2 <- min_value(alpha, beta):\n",
    "    if v2 > v:\n",
    "      v=v2, move = a\n",
    "      alpha=max(alpha, v) # update alpha value\n",
    "    if v >= beta: #means the value greater than the upper bound\n",
    "      return\n",
    "\n",
    "def min_value(alpha, beta):\n",
    "  if is-terminal:\n",
    "    return XX\n",
    "  v=+∞\n",
    "  for each a in game.action(state):\n",
    "    v2, a2 <- max_value(alpha, beta):\n",
    "    if v2 < v:\n",
    "      v=v2, move = a\n",
    "      alpha=min(beta, v) # update beta value\n",
    "    if v \\leq alpha: #means the value less than the lower bound\n",
    "      return\n",
    "```\n",
    "\\\\\n",
    "**expectimax search**: calculate the average value under optimal play.\\n\n",
    "there are two players: MAX-value and EXP-value.\\n\n",
    "```\n",
    "def exp-value:\n",
    "  for each successor of state:\n",
    "    p=probability(successor)\\n\n",
    "      v+=p*\n",
    "    value(successor)\n",
    "  return v\n",
    "```\n",
    "**expectiminimax**: Environment is an extra “random agent” player that moves after each min/max agent\\n\n",
    "**stochastic game** includes a random element. chance nodes denoting the probabilities associated with each action as well as expecti-minimax values are included in the minimax tree\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module5_definitions = {\n",
    "\"perfect information\" : \"fully observable\",\n",
    "\"utility function\":\"the final numeric value to player when the game ends in terminal state\",\n",
    "\"minimax search\": \"assuming that both players play optimally and the player get the desired result\",\n",
    "\"Expectimax Search\": \"considering outcome is uncertain, so compute the average score under optimal play\",\n",
    "\"random variable\":\"the event whose outcome is unknown\",\n",
    "\"probability distribution\":\"the weights to outcome\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "645ba2f2-636e-4cea-fd38-9e5d81486e01"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       "game is formed by **initial state, the player to move, actions(s)-legal moves, result(transition model), terminal test, utility function**.\n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       "the player chooses the option with **highest minimax value**. \n",
       "\n",
       "The minimax algorithm is **complete dfs**.\n",
       "\n",
       "**Time**: $O(b^m)$-tree. $m$-maximum depth of the tree, $b$-legal moves at each point.\n",
       "\n",
       "**Space**: $O(bm)$-every action once, $O(m)$-generate action once a time.\n",
       "\n",
       "**alpha–beta pruning** prunes many possibilities having no influence. \n",
       "\n",
       "Only exams $O(b^{m/2})$, the branching factor is $sqrt(b)$ instead of $b$.\n",
       "\n",
       "**$alpha$**: the value of the best choice we have found so far **for MAX player**, means **at least**.\n",
       "\n",
       "**$beta$**: the value of the best choice we have found so far **for MIN player**, means **at most**.\n",
       "\n",
       "If the value is **less than alpha for MAX($value<alpha$)** or **greater than beta for MIN$(value>beta$)**, just skip it.\n",
       "\n",
       "**For MAX function, if exploring value is greater than the $beta$, stop exploring, else-set $alpha$ as the largest value.**\n",
       "\n",
       "**For MIN function, if exploring value is less than the $alpha$, stop exploring, else-set $beta$ as the least value.**\n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       "\n",
       "\n",
       "## Module 5 Lecture Notes\n",
       "Game tree represent the game problem space by a tree.\n",
       "\n",
       "Simplest Game Environment: **nultiagent, static, discrete(infite actions), fully observable, strategic**\n",
       "\n",
       "we use $f(n)$ to **evaluate the situation** of game: \n",
       "\n",
       "1. $f(n)>0$-MAX palyer win in this position\n",
       "\n",
       "2. $f(n)=0$-tied\n",
       "\n",
       "3. $f(n)<0$-MIN palyer win in this position\n",
       "\n",
       "\n",
       "**Minimax**\n",
       "\n",
       "**assumption: MAX take action based on the assumption that MIN player will move perfectly**\n",
       "\n",
       "```\n",
       "def max-value(state):\n",
       "  if the state is a terminal state:\n",
       "    return the state's utility\n",
       "  initialize v=-∞\n",
       "  for each successor of state:\n",
       "    v=max(v, min-value(successor))\n",
       "  return v\n",
       "\n",
       "def min-value(state):\n",
       "  if the state is a terminal state:\n",
       "    return the state's utility\n",
       "  initialize v=+∞\n",
       "  for each successor of state:\n",
       "    v=min(v, max-value(successor))\n",
       "  return v\n",
       "```\n",
       "**Alpha-Beta Pruning**\n",
       "\n",
       "Different between Minimax and Alpha-beta pruning: **keep track of current lower bound(alpha) on MAX and upper bound(beta) on MIN **\n",
       "\n",
       "```\n",
       "def max_value(alpha, beta):\n",
       "  if is-terminal:\n",
       "    return XX\n",
       "  v=-∞\n",
       "  for each a in game.action(state):\n",
       "    v2, a2 <- min_value(alpha, beta):\n",
       "    if v2 > v:\n",
       "      v=v2, move = a\n",
       "      alpha=max(alpha, v) # update alpha value\n",
       "    if v >= beta: #means the value greater than the upper bound\n",
       "      return\n",
       "\n",
       "def min_value(alpha, beta):\n",
       "  if is-terminal:\n",
       "    return XX\n",
       "  v=+∞\n",
       "  for each a in game.action(state):\n",
       "    v2, a2 <- max_value(alpha, beta):\n",
       "    if v2 < v:\n",
       "      v=v2, move = a\n",
       "      alpha=min(beta, v) # update beta value\n",
       "    if v \\leq alpha: #means the value less than the lower bound\n",
       "      return\n",
       "```\n",
       "\\\n",
       "**expectimax search**: calculate the average value under optimal play.\n",
       "\n",
       "there are two players: MAX-value and EXP-value.\n",
       "\n",
       "```\n",
       "def exp-value:\n",
       "  for each successor of state:\n",
       "    p=probability(successor)\n",
       "\n",
       "      v+=p*\n",
       "    value(successor)\n",
       "  return v\n",
       "```\n",
       "**expectiminimax**: Environment is an extra “random agent” player that moves after each min/max agent\n",
       "\n",
       "**stochastic game** includes a random element. chance nodes denoting the probabilities associated with each action as well as expecti-minimax values are included in the minimax tree\n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Perfect information** - fully observable\n",
       "* **Utility function** - the final numeric value to player when the game ends in terminal state\n",
       "* **Minimax search** - assuming that both players play optimally and the player get the desired result\n",
       "* **Expectimax search** - considering outcome is uncertain, so compute the average score under optimal play\n",
       "* **Random variable** - the event whose outcome is unknown\n",
       "* **Probability distribution** - the weights to outcome\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module5_sections = [\n",
    "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
    "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
    "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
    "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
    "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
    "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
    "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
    "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
    "]\n",
    "\n",
    "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
    "                         module5_sections, \n",
    "                         module5_definitions)\n",
    "display(Markdown(module5_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "qVSQhTVSyYYO"
   },
   "source": [
    "#Module 6 - \"Constraint Satisfaction Problems\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "Wm4mfW82yaRH"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
    "chapter6_1 = \"\"\"A solution to CSP is **complete and consisten**.\\n\n",
    "a variable consistent means in its domain every value satisfies the binary constraints, if the map is consistent, every variable is arc consistent with others.\"\"\"\n",
    "chapter6_2 = \"\"\"Assume a CSP with n variables, each with domain size at most $d$, and with $c$ BINARY constraints (arcs), **checking for arc consistency is $O(d^2)$**, total is **$O(cd^3)$**.\\n\n",
    "**Path consistency** using implicit constraints that are inferred by **looking at triples of variables**. \\n\n",
    "**1-consistency**=>node consistency; \\n\n",
    "**2-consistency**=>arc consistency; \\n\n",
    "For binary constraint graphs, **3-consistency**=>path consistency; \\n\n",
    "**k-consistency**=>**for any set of k-1 variables and for any consistent assignment to those variables, a fixed value can always be assigned to any kth variable**.\\n\n",
    "**strongly k-consistent**=>it is k-consistent and is also k-1-consistent, k-2-consistent, all the way down to 1-consistent.RUN **$O(dn^2)$**\"\"\"\n",
    "chapter6_3 = \"\"\"Inference: **node, arc, path, and k-consistency**.\\n\n",
    "**Forward checking**. The forward-checking process **establishes arc consistency for the assigned value**-> detect inevitable failure early\"\"\"\n",
    "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
    "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module6_lecture_notes = \"\"\"Assumption: **a single agent, deterministic actions, fully observed state, discrete state space**.\\n\n",
    "CSP: **Represent the constraints that solutions must satisfy**.\\n\n",
    "CSP is formed by **finite set of variables, Nonempty domain of possible values for each variable, and Finite set of constraints**\\n\n",
    "We should use **general purpose algo** to find the solution of CSP.\\n\n",
    "The solution to CSPs should be **complete** and **consistent**\\n\n",
    "CSPs that require a solution that **maximizes an objective function**.\\n\n",
    "CSP as a search problem: **Initial State, Successor function, Goal test and Path cost**.\\n\n",
    "\\\\\n",
    "**representation of CSPs**:\\n\n",
    "1. **constraint graph**-node: varibale; arcs/edges: (binary cinstraints)\\n\n",
    "2. **standard representation pattern**\\n\n",
    "\\\\\n",
    "**variables in CSPs**:\\n\n",
    "1. *discrete variables*: finite domains(domain size $O(d^n)$, domain size$d$) and infinite domains(int, strings)\\n\n",
    "2. *continuous variables*: like start/end times\\n\n",
    "\\\\\n",
    "**variables in constraint**:\\n\n",
    "1. unary constraint: a is not RED\\n\n",
    "2. binary constarint: a not equal to b\\n\n",
    "3. higher-order constraint: 3 or more variable invovled\\n\n",
    "4. preference: a is prefered than b\\n\n",
    "\\\\\n",
    "**always use DFS(backtracking-single-variable) to find solution**\\n\n",
    "The variable assignments are commutative.\\n\n",
    "\n",
    "**Heuristic**: to improve the effiency of backtracking\\n\n",
    "1. try most constrained variable(minimum remaining values (MRV));\\n\n",
    "2. Most constraining variable; \\n\n",
    "3. Least constraining value; \\n\n",
    "4. **Forward checking**. Terminate search when any unassigned variable has no remaining legal values.\\n\n",
    "**AC-3 complexity**:\\n\n",
    "There are $d$ values, checking all arcs uses $O(d^2)$. Each arc (i,j) can only be inserted into the queue $d$ times; **Worst case complexity**: $O(n^{2}d^{3})$\\n\n",
    "\\\\\n",
    "```\n",
    "def AC-3(csp):\n",
    "  queue(contains all arcs in csp)\n",
    "  while queue:\n",
    "    $(X_{i}, X_{j})$=queue.pop()\n",
    "    if REVISE(csp, $X_{i}, X_{j}$):\n",
    "      if len($D_{i}$==0):\n",
    "        return false\n",
    "      for each $X_{k}$ in $X_{i}$.adj-${X_{j}}$:\n",
    "        add ($X_{k}, X_{i}$) to queue\n",
    "  return true\n",
    "\n",
    "def REVISE(csp,$X_{i}, X_{j}$):\n",
    "  revised=false\n",
    "  for x in $D_{i}$:\n",
    "    if no value y in $D_{i}$ let (x, y) satisfy the constraint:\n",
    "      delete x from $D_{i}$\n",
    "      revised=true\n",
    "  return revised\n",
    "\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "**cutset conditioning** reduce CSP to a tree structure.\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module6_definitions = {\n",
    "\"constraint satisfaction problem\" : \"A problem is solved when each variable has a value under related constraints.\",\n",
    "\"consistent assignment\": \"the variable is assigned without violating any constraints.\",\n",
    "\"complete assignment\":\"every varibale is assigned to a value.\",\n",
    "\"constraint propagation\": \"reduce the number of legal values for a variable according to the constrains.\",\n",
    "\"node-consistent\": \"all the values in the variable’s domain satisfy the variable’s unary constraints\",\n",
    "\"arc consistency\":\"a variable is arc consistent if all value in the domain satisfies the variable's binary constraint\",\n",
    "\"chronological backtracking\": \"back up to the preceding variable and try a different value for it\",\n",
    "\"binary CSP\": \"the constraint is related to two variables\"\n",
    "\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "65dd3e21-adba-41cd-8a7f-16075378c153"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       "A solution to CSP is **complete and consisten**.\n",
       "\n",
       "a variable consistent means in its domain every value satisfies the binary constraints, if the map is consistent, every variable is arc consistent with others.\n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       "Assume a CSP with n variables, each with domain size at most $d$, and with $c$ BINARY constraints (arcs), **checking for arc consistency is $O(d^2)$**, total is **$O(cd^3)$**.\n",
       "\n",
       "**Path consistency** using implicit constraints that are inferred by **looking at triples of variables**. \n",
       "\n",
       "**1-consistency**=>node consistency; \n",
       "\n",
       "**2-consistency**=>arc consistency; \n",
       "\n",
       "For binary constraint graphs, **3-consistency**=>path consistency; \n",
       "\n",
       "**k-consistency**=>**for any set of k-1 variables and for any consistent assignment to those variables, a fixed value can always be assigned to any kth variable**.\n",
       "\n",
       "**strongly k-consistent**=>it is k-consistent and is also k-1-consistent, k-2-consistent, all the way down to 1-consistent.RUN **$O(dn^2)$**\n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       "Inference: **node, arc, path, and k-consistency**.\n",
       "\n",
       "**Forward checking**. The forward-checking process **establishes arc consistency for the assigned value**-> detect inevitable failure early\n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       " Your summary here \n",
       "\n",
       "## Module 6 Lecture Notes\n",
       "Assumption: **a single agent, deterministic actions, fully observed state, discrete state space**.\n",
       "\n",
       "CSP: **Represent the constraints that solutions must satisfy**.\n",
       "\n",
       "CSP is formed by **finite set of variables, Nonempty domain of possible values for each variable, and Finite set of constraints**\n",
       "\n",
       "We should use **general purpose algo** to find the solution of CSP.\n",
       "\n",
       "The solution to CSPs should be **complete** and **consistent**\n",
       "\n",
       "CSPs that require a solution that **maximizes an objective function**.\n",
       "\n",
       "CSP as a search problem: **Initial State, Successor function, Goal test and Path cost**.\n",
       "\n",
       "\\\n",
       "**representation of CSPs**:\n",
       "\n",
       "1. **constraint graph**-node: varibale; arcs/edges: (binary cinstraints)\n",
       "\n",
       "2. **standard representation pattern**\n",
       "\n",
       "\\\n",
       "**variables in CSPs**:\n",
       "\n",
       "1. *discrete variables*: finite domains(domain size $O(d^n)$, domain size$d$) and infinite domains(int, strings)\n",
       "\n",
       "2. *continuous variables*: like start/end times\n",
       "\n",
       "\\\n",
       "**variables in constraint**:\n",
       "\n",
       "1. unary constraint: a is not RED\n",
       "\n",
       "2. binary constarint: a not equal to b\n",
       "\n",
       "3. higher-order constraint: 3 or more variable invovled\n",
       "\n",
       "4. preference: a is prefered than b\n",
       "\n",
       "\\\n",
       "**always use DFS(backtracking-single-variable) to find solution**\n",
       "\n",
       "The variable assignments are commutative.\n",
       "\n",
       "\n",
       "**Heuristic**: to improve the effiency of backtracking\n",
       "\n",
       "1. try most constrained variable(minimum remaining values (MRV));\n",
       "\n",
       "2. Most constraining variable; \n",
       "\n",
       "3. Least constraining value; \n",
       "\n",
       "4. **Forward checking**. Terminate search when any unassigned variable has no remaining legal values.\n",
       "\n",
       "**AC-3 complexity**:\n",
       "\n",
       "There are $d$ values, checking all arcs uses $O(d^2)$. Each arc (i,j) can only be inserted into the queue $d$ times; **Worst case complexity**: $O(n^{2}d^{3})$\n",
       "\n",
       "\\\n",
       "```\n",
       "def AC-3(csp):\n",
       "  queue(contains all arcs in csp)\n",
       "  while queue:\n",
       "    $(X_{i}, X_{j})$=queue.pop()\n",
       "    if REVISE(csp, $X_{i}, X_{j}$):\n",
       "      if len($D_{i}$==0):\n",
       "        return false\n",
       "      for each $X_{k}$ in $X_{i}$.adj-${X_{j}}$:\n",
       "        add ($X_{k}, X_{i}$) to queue\n",
       "  return true\n",
       "\n",
       "def REVISE(csp,$X_{i}, X_{j}$):\n",
       "  revised=false\n",
       "  for x in $D_{i}$:\n",
       "    if no value y in $D_{i}$ let (x, y) satisfy the constraint:\n",
       "      delete x from $D_{i}$\n",
       "      revised=true\n",
       "  return revised\n",
       "\n",
       "```\n",
       "\n",
       "\n",
       "\n",
       "**cutset conditioning** reduce CSP to a tree structure.\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Constraint satisfaction problem** - A problem is solved when each variable has a value under related constraints.\n",
       "* **Consistent assignment** - the variable is assigned without violating any constraints.\n",
       "* **Complete assignment** - every varibale is assigned to a value.\n",
       "* **Constraint propagation** - reduce the number of legal values for a variable according to the constrains.\n",
       "* **Node-consistent** - all the values in the variable’s domain satisfy the variable’s unary constraints\n",
       "* **Arc consistency** - a variable is arc consistent if all value in the domain satisfies the variable's binary constraint\n",
       "* **Chronological backtracking** - back up to the preceding variable and try a different value for it\n",
       "* **Binary csp** - the constraint is related to two variables\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": {
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
    "\n",
    "chapter7_1 = \"**axiom sentence** means it is not derived from another sentences\"\n",
    "chapter7_2 = \"\"\n",
    "chapter7_3 = \"\"\n",
    "chapter7_4 = \"\"\n",
    "chapter7_5 = \"\"\n",
    "\n",
    "# Lecture notes \n",
    "module7_lecture_notes = \"\"\"**central component of a knowledge-based agent** is a **knowledge base(KB)**,A KB contains **a set of sentence** contains some assertion.\\n\n",
    "$a|=b$ means $a$ is more specific or stronger than $b$, $M(a)$ belongs to $M(b)$. we can infer $b$ from $a$\\n\n",
    "$KB |-_{i} a$ means $a$ is derived from $KB$ using inference algo $i$.\\n\n",
    "**commutativity of ∧**:(α∧β) ≡ (β ∧α)  \\n\n",
    "**commutativity of ∨**:(α∨β) ≡ (β ∨α)  \\n\n",
    "**associativity of ∧**:((α∧β)∧γ) ≡ (α∧(β ∧γ))  \\n\n",
    "**associativity of ∨**:((α∨β)∨γ) ≡ (α∨(β ∨γ))  \\n\n",
    "**double-negation elimination**: ¬(¬α) ≡ α  \\n\n",
    "**Contraposition**: $a\\Rightarrow b \\equiv ¬ b\\Rightarrow ¬a$;\\n\n",
    "**Implication elimination**: $a \\Rightarrow b \\equiv a ⋁ b$;\\n\n",
    "**Biconditional elimination**: $a\\leftrightarrow b \\equiv a\\Rightarrow b $and $b\\Rightarrow a$;\\n\n",
    "**De Morgan**: $¬ (a ⋀ b) \\equiv ¬ a ⋁ ¬ b ; ¬(a ⋁ b)\\equiv ¬a ⋀ ¬b$.\\n\n",
    "**Distributivity of ⋀ over ⋁**: $(a⋀b)⋁c = (a⋀c)⋁(b⋀c)$.\\n\n",
    "**Distributivity of ⋁ over ⋀**: $(a⋁b)⋀c = (a⋁c)⋀(b⋁c)$.\\n\n",
    "**And Elimination**: $a⋀b \\equiv a$.\\n\n",
    "**Modus Ponens**: $a\\Rightarrow a,b \\equiv b$.\\n\n",
    "\\\\\n",
    "Monotonicity implies Soundness.\\n\n",
    "**If add more info is added to KB, the entailed sentence will be still valid**.\\n\n",
    "Resolution: if two element if opponent, use **unit resolution** to solve.\\n\n",
    "**Conjunctive Normal Form (CNF)**:\\n\n",
    "1. we can eliminate $a \\leftrightarrow b$ to $a\\Rightarrow b ⋀ b\\Rightarrow a$; \\n\n",
    "2. $a\\Rightarrow b$ to $ ¬ a ⋁ b$.\\n\n",
    "3. move internal $¬$; \\n\n",
    "4. use Distributivity of ⋀ over ⋁ or Distributivity of ⋁ over ⋀ to decrease nested ⋀ or ⋁\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module7_definitions = {\n",
    "\"Knowledge-based agents\" : \"agent that makes decision based on internal representation of knowledge\",\n",
    "\"model\":\"a math abstractions that contains a set of truth value with boolean value to some sentences\",\n",
    "\"Logical Entailment\": \"two sentence is linked by logic\",\n",
    "\"logical inference\": \"the sentences can be inferred from the sentence in the KB\",\n",
    "\"Sound\": \"The inference algo can only infer entail sentence\",\n",
    "\"complete\": \"The inference algo can derives all entailed sentences\",\n",
    "\"logically equivalent\":\"two sentences have same set fo model\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "81dc9d00-42b7-428d-8d8f-cdbfdc22ec60"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       "**axiom sentence** means it is not derived from another sentences\n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       "\n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       "\n",
       "\n",
       "## Module 7 Lecture Notes\n",
       "**central component of a knowledge-based agent** is a **knowledge base(KB)**,A KB contains **a set of sentence** contains some assertion.\n",
       "\n",
       "$a|=b$ means $a$ is more specific or stronger than $b$, $M(a)$ belongs to $M(b)$. we can infer $b$ from $a$\n",
       "\n",
       "$KB |-_{i} a$ means $a$ is derived from $KB$ using inference algo $i$.\n",
       "\n",
       "**commutativity of ∧**:(α∧β) ≡ (β ∧α)  \n",
       "\n",
       "**commutativity of ∨**:(α∨β) ≡ (β ∨α)  \n",
       "\n",
       "**associativity of ∧**:((α∧β)∧γ) ≡ (α∧(β ∧γ))  \n",
       "\n",
       "**associativity of ∨**:((α∨β)∨γ) ≡ (α∨(β ∨γ))  \n",
       "\n",
       "**double-negation elimination**: ¬(¬α) ≡ α  \n",
       "\n",
       "**Contraposition**: $a\\Rightarrow b \\equiv ¬ b\\Rightarrow ¬a$;\n",
       "\n",
       "**Implication elimination**: $a \\Rightarrow b \\equiv a ⋁ b$;\n",
       "\n",
       "**Biconditional elimination**: $a\\leftrightarrow b \\equiv a\\Rightarrow b $and $b\\Rightarrow a$;\n",
       "\n",
       "**De Morgan**: $¬ (a ⋀ b) \\equiv ¬ a ⋁ ¬ b ; ¬(a ⋁ b)\\equiv ¬a ⋀ ¬b$.\n",
       "\n",
       "**Distributivity of ⋀ over ⋁**: $(a⋀b)⋁c = (a⋀c)⋁(b⋀c)$.\n",
       "\n",
       "**Distributivity of ⋁ over ⋀**: $(a⋁b)⋀c = (a⋁c)⋀(b⋁c)$.\n",
       "\n",
       "**And Elimination**: $a⋀b \\equiv a$.\n",
       "\n",
       "**Modus Ponens**: $a\\Rightarrow a,b \\equiv b$.\n",
       "\n",
       "\\\n",
       "Monotonicity implies Soundness.\n",
       "\n",
       "**If add more info is added to KB, the entailed sentence will be still valid**.\n",
       "\n",
       "Resolution: if two element if opponent, use **unit resolution** to solve.\n",
       "\n",
       "**Conjunctive Normal Form (CNF)**:\n",
       "\n",
       "1. we can eliminate $a \\leftrightarrow b$ to $a\\Rightarrow b ⋀ b\\Rightarrow a$; \n",
       "\n",
       "2. $a\\Rightarrow b$ to $ ¬ a ⋁ b$.\n",
       "\n",
       "3. move internal $¬$; \n",
       "\n",
       "4. use Distributivity of ⋀ over ⋁ or Distributivity of ⋁ over ⋀ to decrease nested ⋀ or ⋁\n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge-based agents** - agent that makes decision based on internal representation of knowledge\n",
       "* **Model** - a math abstractions that contains a set of truth value with boolean value to some sentences\n",
       "* **Logical entailment** - two sentence is linked by logic\n",
       "* **Logical inference** - the sentences can be inferred from the sentence in the KB\n",
       "* **Sound** - The inference algo can only infer entail sentence\n",
       "* **Complete** - The inference algo can derives all entailed sentences\n",
       "* **Logically equivalent** - two sentences have same set fo model\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/"
    },
    "id": "T3cm1WV542_a",
    "outputId": "08fb42fd-c964-4c5a-ac60-f1e707c0a1cc",
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       "two dimensions—human vs. rational and thought vs. behavior; \n",
       "\n",
       "Turing Test: natural language processing; knowledge representation;automated reasoning;machine learning.\n",
       "\n",
       "Total Turing test: computer vision, robotics. intelligent agent takes the best actions so far.\n",
       "\n",
       "The emphasis is correct inferences, but it is not always best\n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       "\n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       "\n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       "\n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       "consequentialism: how to evaluate right. \n",
       "\n",
       "Design performance measurement is better. \n",
       "\n",
       "omniscience: impossible that know result ahead. \n",
       "\n",
       "agent not only gather info but also learn.\n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       "environment can be fully observable and partially observable; \n",
       "\n",
       "Single agent or multiagent.(Randomized is rational in some competitive environment, but irrational in single-agent environment);\n",
       "\n",
       "**Deterministic and nondeterministic**(the next state is determined by the current action or not), stochastic is about specific probabilities;\n",
       "\n",
       "**episodic and sequential**(next state is independent or not);\n",
       "\n",
       "**static and dynamic**(environment is changing); \n",
       "\n",
       "**discrete/continuous**(about time)\n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       "agent architecture and agent program forms an agent. \n",
       "\n",
       "different agent:\n",
       "\n",
       "**simple reflex agent** only cares current state, not state history.\n",
       "\n",
       "**model-based:** considering internal state information. \n",
       "\n",
       "**goal-based:** search and plan. \n",
       "\n",
       "**unility-based:** maximizes the expected utility.\n",
       "\n",
       "**atomic representation**: each state is independent, **factored representation** can be split to a fixed set of variables or attributes.\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       "**strong AI** - actually thinking; **weak AI** - simulating thinking.\n",
       "\n",
       "design performance mearsure based on what we want to achieve.\n",
       "\n",
       "**agent maximizes the 'expected' value of performace measure.**\n",
       "\n",
       "When something behavior has its own performance measure, it is an agent.\n",
       "\n",
       "A **problem-solving** agent must plan ahead.\n",
       "\n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - anything that can perceive and act in an environment\n",
       "* **Percept** - what agent received\n",
       "* **Percept sequence** - the history of recieved.\n",
       "* **Agent function** - the behavior how to be described(abstract math concept)\n",
       "* **Agent program** - about implementation\n",
       "* **Agent architecture** - the physical device\n",
       "\n",
       "\n",
       "## WARNING: Your definition of 'First-class object' is too long!\n",
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       "**strong type**: all data are objects. and type is **determined auto**.\n",
       "\n",
       "**Diferent type and their feature.**\n",
       "\n",
       "mutable means we can assign a new value to the element, immutable means the elements cannnot be updated, only the immutable datatype can be used in dictionary's key.\n",
       "\n",
       "**string** : **immutable**,\n",
       "\n",
       "**list** : **mutable**, mixed types, ordered\n",
       "\n",
       "**tuple** : **immutable**, mixed type. \n",
       "\n",
       "**Dictionary**: **key-immutable**, unordered\n",
       "\n",
       "no function **overloading** functions cannot have same name, unlike java.\n",
       "\n",
       "Non-default argument **without default arguments** reports SyntaxError\n",
       "\n",
       "**positional argument** follows keyword argument, so it the order is wrong with specific key provided, iti is fine\n",
       "\n",
       "*args (one star): input is many **non-keyword** arguments, like list below.\n",
       "\n",
       "```\n",
       "def get_elements(*args):\n",
       "    print(args)\n",
       "l=[1,2,3]\n",
       "get_elements(*l)\n",
       "```\n",
       "\n",
       "**kwargs(two stars): accept many **keyword arguments**, like dictionary below.\n",
       "\n",
       "```\n",
       "def print_elements(**kwargs):\n",
       "  print(kwargs)\n",
       "dic={1:2}\n",
       "```\n",
       "1. print_elements(**dic)=>use dic buildt before.\n",
       "\n",
       "2. print_elements(1=2)=>directly input\n",
       "\n",
       "**extend**->class AI_Student(Student), means AI_Student is one tyoe fo student, so it extend the propoty of Student.\n",
       "\n",
       "**Multiple inheritance**, one class can have more than one inheritnace.\n",
       "\n",
       "**override**:To redefine a method of the parent class, include a new definition using the same name in the subclass.\n",
       "\n",
       "**Iterators**->next()/__next__(), we can use next to get the next element, but we cannot use hasnext() in Python iterator. When wll element is visited, it will catch **StopIteration** error.\n",
       "\n",
       "**yield**->**generator**: then it stops and returns the value that was yielded. Next time, it resumes where it left off, whic means it will continue the loop instead of begin a new loop. It can save space in some situation like print  elements after merge two lists\n",
       "\n",
       "when using a class, there are two **calling methods**:\n",
       "\n",
       "```\n",
       "cat1 = Cat(\"kitty\")\n",
       "1. cat1.play()\n",
       "2. Cat.play(cat1)\n",
       "```\n",
       "**Duck**: we can define duck typing outside any class:\n",
       "\n",
       "```\n",
       "class Cat:\n",
       " def play(self):\n",
       "   print(\"the cat plays with me!\")\n",
       "def play(entity):\n",
       "  entity.play()\n",
       "```\n",
       "if the class doesn't have play method, there will be attributeError.\n",
       "\n",
       "**interator**: iterator can make memory be used more efficiently. for lin in opne('file')=> return a iterator\n",
       "\n",
       "Use '%': '%s -> %s'%(u,v) for u in l for v in w\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Mutability** - The elements can be changed\n",
       "* **Higher order functions** - input is function\n",
       "* **First-class object** - the object that can be passed to other methond as a parameter, can be methond's return value, can be create during processing(created, destoryed dynamically) dynamically), and it have all rights as a normal variable.\n",
       "\n",
       "* **Magic methods** - these user-defined methods can be used as a build-in methods, like '__init__', '__len__', '__copy__', '__cmp__', '__add__', '__neg__'\n",
       "* **Duck typing** - the method doesn't need any interface\n",
       "\n",
       "\n",
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       "a search problem can be descripted below: **state space**, **initial state**, **goal states**, **action**, **transition model**, **action cost function**.\n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       "**priority queue: best-first search, queue: bfs, stack: dfs**.\n",
       "\n",
       "**graph search**: **checks for redundant paths**. best-first search, \n",
       "\n",
       "**tree-like search**: **not check redundant paths**.\n",
       "\n",
       "different between graph search and tree search**: how we are traversing the search space.\n",
       "\n",
       "1. In the case of a **graph search**, we use a list, called the closed list (also called **explored set**), to keep track of the nodes that have already been visited and expanded, so that they are not visited and expanded again.\n",
       "\n",
       "2. In the case of a **tree search**, we **do not keep this closed list**. Consequently, the same node can be visited **multiple** (or even infinitely many) times, which means that the produced tree (by the tree search) may contain the same node multiple times.\n",
       "\n",
       "graph search is that it uses **more memory** than tree search.\n",
       "\n",
       "**four metrics of performance**: **completeness, cost optimality, time complexity, space complexity**.\n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       "**uninformed search(no infomation about the distance from current state to the goal)**. \n",
       "\n",
       "BFS-early goal test. Best-first search-late goal test.\n",
       "\n",
       "**not:** $b$ is *maximum branching factor of search tree*; $d$ is *depth of the least cost solution*; $m$ is *maximum depth of the state space (∞)*\n",
       "\n",
       "\n",
       "**BFS**\n",
       "\n",
       "**implement structure**: queue, first in first out.\n",
       "\n",
       "**time**: $O(b^d)$\n",
       "\n",
       "**space**: $O(b^d)$(every node are stored in memeory).\n",
       "\n",
       "Exponential space (and time) is not good.\n",
       "\n",
       "**complete**: YES\n",
       "\n",
       "**Optimal**: YES\n",
       "\n",
       "\n",
       "**DFS**\n",
       "\n",
       "**implement structure**: stack, last in first out.\n",
       "\n",
       "**time**:$O(b^m)$, because it get all solutions, therefore use $m$ instead of $d$.\n",
       "\n",
       "**space**: $O(bm)$, it is linear.\n",
       "\n",
       "**complete**: NO\n",
       "\n",
       "**Optimal**: NO\n",
       "\n",
       "one variant of **DFS** is **backtracking** uses **less memory**, only one successor is generated at a time rather than all successors.\n",
       "\n",
       "\n",
       "**Depth-limited Search**\n",
       "\n",
       "**implement structure**: stack, last in first out.\n",
       "\n",
       "supply a depth limit $l$, and treat all nodes at depth as if they had no successors\n",
       "\n",
       "it is unnecessary to consider infinite cycle.\n",
       "\n",
       "**time**: $O(b^l)$\n",
       "\n",
       "**space**: $O(bl)$\n",
       "\n",
       "**complete**: if $l<d$ then NO\n",
       "\n",
       "**Optimal**: if $l==d$,then YES; if $l>d$, then NO\n",
       "\n",
       "\n",
       "**Dijkstra/uniform-cost search**\n",
       "\n",
       "a extension of BFS, considering path cost\n",
       "\n",
       "**implement structure**: priority queue (min heap)\n",
       "\n",
       "**time**: greater than BFS in worst case and similar to BFS when path cost is equal.\n",
       "\n",
       "**space**: greater than BFS in worst case and similar to BFS when path cost is equal\n",
       "\n",
       "**complete**: YES\n",
       "\n",
       "**Optimal**: YES\n",
       "\n",
       "\n",
       "**Iterative deepening search**\n",
       "\n",
       "try limit $l$ from 1 and on\n",
       "\n",
       "**time**: $O(b^d)$ with solution, $O(b^m)$ without solution. \n",
       "\n",
       "**space**: $O(bd)$ with solution, $O(bm)$ without solution\n",
       "\n",
       "**complete**: YES\n",
       "\n",
       "**Optimal**: YES\n",
       "\n",
       "In general, iterative deepening is the **preferred** uninformed search method when **the search state space is larger than memory requirement and the depth of the solution is not known**\n",
       "\n",
       "```\n",
       "for $l = 0$ to ∞ do:\n",
       "  #depth-limited-serach to level $l$\n",
       "  if it succeeds\n",
       "    then return solution\n",
       "```\n",
       "\n",
       "**bidirectional search**\n",
       "\n",
       "two directions: forward from the initial state and backwards from the goal state(s)\n",
       "\n",
       "**time**: $O(b^{d/2})$\n",
       "\n",
       "**complete**: YES\n",
       "\n",
       "**Optimal**: YES\n",
       "\n",
       "\n",
       "**completed and optimal cost**: **bfs, uniform, iterative, bidirectinal**.\n",
       "\n",
       "**not completed and not optimal**: **dfs, depth-limited(can have loop)**\n",
       "\n",
       "## Module 3 Lecture Notes\n",
       "**search tree**: Enumerate in some order all possible paths from the initial state. \n",
       "\n",
       "**search graph** : Check to see if a node has been visited before adding to search queue\n",
       "\n",
       "If there are a lot of solutions, DFS may be much faster than BFS.\n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "* **State space** - a set of possibile states\n",
       "* **Completeness** - it is ensure that the algo can find the solution or report error\n",
       "* **Frontier** - legal expandable states\n",
       "* **Uninformed search** - non-goal nodes looks same\n",
       "* **Informed search** - non-goal nodes are different\n",
       "\n",
       "\n",
       "## WARNING: Your definition of 'A* search' is too long!\n",
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       "heuristic function gives the path with lowest cost from current position to the goal position.\n",
       "\n",
       "**greedy best-first serach**\n",
       "\n",
       "doesn't guarantee to find the best solution, it is complete in finite case, not infinite case. $O(bm)$.\n",
       "\n",
       "The way to evaluate different node is function $f(n)$, which is the estimated distance from current position to goal\n",
       "\n",
       "So $f(n)=h(n)$\n",
       "\n",
       "\n",
       "**A* search is complete and cost-optimal** with consistent admissible heuristic.\n",
       "\n",
       "**consistency**---$h(n) ≤ c(n, a, n′) + h(n′)$, which is a **triangle inequality**.\n",
       "\n",
       "**With an *inadmissible heuristic*, A* may not be cost-optimal**. If A* search is consistent heuristic, it is optimal efficient because it prunes many possibilities, and the value of $g(n)+h(n)$ is monotonical. but it cannot find the optimal solution when the number of nodes expanded can be **exponential**.\n",
       "\n",
       "**Beam search** keep only the nodes with the best scores as frontier.\n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       "If h1 **dominates** h2, $h1(n)>=h2(n)$, h1 is more accurate than h2. When they ar both admissible, larger value means more accurate\n",
       "\n",
       "\n",
       "## Module 4 Lecture Notes\n",
       "tree search: uniform-cost search **frontier = priority queue ordered by $g(n)**$\n",
       "\n",
       "A* is optimal with admissible heuristic\n",
       "\n",
       "**The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.**\n",
       "\n",
       "\n",
       "**uniform-cost search**\n",
       "\n",
       "difference between BFS and UCS is it check the node is goal or not when the node is selected before it is added to the frontier.\n",
       "\n",
       "use priority queue beased on path cost.\n",
       "\n",
       "**best-first search**\n",
       "\n",
       "sort frontier according to the estimate distance from current position to goal, $h(n)=h(n)$\n",
       "\n",
       "**two kind of best-first search**\n",
       "\n",
       "\n",
       "1. **greedy best-forst search**\n",
       "\n",
       "```\n",
       "frontier = PriorityQueue()\n",
       "frontier.put(start, 0)\n",
       "came_from={}\n",
       "came_from[start]=None\n",
       "while not frontier.empty():\n",
       "  current = frontier.get()\n",
       "  if current==goal:\n",
       "    break\n",
       "  for next in graph.neighbors(current):\n",
       "    if next not in came_from:\n",
       "      priority = heuristic(goal, next) # get the distance $h(n)$ from next position to goal\n",
       "      frontier.put(next, priority)\n",
       "      came_from[next]=current\n",
       "```\n",
       "**optimal**: NO\n",
       "\n",
       "**complete**: NO(can be in a cycle)\n",
       "\n",
       "\n",
       "2. **A-star search**\n",
       "\n",
       "expand most promising node in the priority queue\n",
       "\n",
       "**$f(n)=g(n)+h(n)$**\n",
       "\n",
       "**optimal**: YES if it have admissible heiristic\n",
       "\n",
       "\n",
       "**admissible huristics**\n",
       "\n",
       "$0 \\leq h(n) \\leq h*(n)$=> real distance\n",
       "\n",
       "if A is optimal node and B is suboptimal node, and h is admissible, A will finish before B\n",
       "\n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Informed search** - have information of goal's location, and the information is given as a heuristic function\n",
       "* **Greedy best-first search** - a type of best-first search that select node with lowest heuristic value, f(n)=h(n)\n",
       "* **A* search** - estimate the best value continue from current pos to the goal pos, plus the path value already taken from start state to current pos, f(n)=g(n)+h(n)\n",
       "* **Admissible heuristic** - never overestimate the path cost, so it is optimistic\n",
       "* **Prune** - remove some possibilities without test them\n",
       "* **Weighted a* search** - weight h(h) more heavily so it can be inadmissible heuristic, but find a good enough solution and improve efficiency\n",
       "* **Bounded suboptimal search** - the factor W is constant\n",
       "* **Bounded-cost search** - cost must lower than C\n",
       "* **Unbounded-cost search** - accept any solution if we can get it quickly, like speedy search(greedy best-first search)\n",
       "* **Relaxed problem** - The problem with less restriction compared with original problem in action rules\n",
       "* **Heuristic funtion** - claculate and estimate the distance from current position to the goal\n",
       "\n",
       "\n",
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       "game is formed by **initial state, the player to move, actions(s)-legal moves, result(transition model), terminal test, utility function**.\n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       "the player chooses the option with **highest minimax value**. \n",
       "\n",
       "The minimax algorithm is **complete dfs**.\n",
       "\n",
       "**Time**: $O(b^m)$-tree. $m$-maximum depth of the tree, $b$-legal moves at each point.\n",
       "\n",
       "**Space**: $O(bm)$-every action once, $O(m)$-generate action once a time.\n",
       "\n",
       "**alpha–beta pruning** prunes many possibilities having no influence. \n",
       "\n",
       "Only exams $O(b^{m/2})$, the branching factor is $sqrt(b)$ instead of $b$.\n",
       "\n",
       "**$alpha$**: the value of the best choice we have found so far **for MAX player**, means **at least**.\n",
       "\n",
       "**$beta$**: the value of the best choice we have found so far **for MIN player**, means **at most**.\n",
       "\n",
       "If the value is **less than alpha for MAX($value<alpha$)** or **greater than beta for MIN$(value>beta$)**, just skip it.\n",
       "\n",
       "**For MAX function, if exploring value is greater than the $beta$, stop exploring, else-set $alpha$ as the largest value.**\n",
       "\n",
       "**For MIN function, if exploring value is less than the $alpha$, stop exploring, else-set $beta$ as the least value.**\n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       "\n",
       "\n",
       "## Module 5 Lecture Notes\n",
       "Game tree represent the game problem space by a tree.\n",
       "\n",
       "Simplest Game Environment: **nultiagent, static, discrete(infite actions), fully observable, strategic**\n",
       "\n",
       "we use $f(n)$ to **evaluate the situation** of game: \n",
       "\n",
       "1. $f(n)>0$-MAX palyer win in this position\n",
       "\n",
       "2. $f(n)=0$-tied\n",
       "\n",
       "3. $f(n)<0$-MIN palyer win in this position\n",
       "\n",
       "\n",
       "**Minimax**\n",
       "\n",
       "**assumption: MAX take action based on the assumption that MIN player will move perfectly**\n",
       "\n",
       "```\n",
       "def max-value(state):\n",
       "  if the state is a terminal state:\n",
       "    return the state's utility\n",
       "  initialize v=-∞\n",
       "  for each successor of state:\n",
       "    v=max(v, min-value(successor))\n",
       "  return v\n",
       "\n",
       "def min-value(state):\n",
       "  if the state is a terminal state:\n",
       "    return the state's utility\n",
       "  initialize v=+∞\n",
       "  for each successor of state:\n",
       "    v=min(v, max-value(successor))\n",
       "  return v\n",
       "```\n",
       "**Alpha-Beta Pruning**\n",
       "\n",
       "Different between Minimax and Alpha-beta pruning: **keep track of current lower bound(alpha) on MAX and upper bound(beta) on MIN **\n",
       "\n",
       "```\n",
       "def max_value(alpha, beta):\n",
       "  if is-terminal:\n",
       "    return XX\n",
       "  v=-∞\n",
       "  for each a in game.action(state):\n",
       "    v2, a2 <- min_value(alpha, beta):\n",
       "    if v2 > v:\n",
       "      v=v2, move = a\n",
       "      alpha=max(alpha, v) # update alpha value\n",
       "    if v >= beta: #means the value greater than the upper bound\n",
       "      return\n",
       "\n",
       "def min_value(alpha, beta):\n",
       "  if is-terminal:\n",
       "    return XX\n",
       "  v=+∞\n",
       "  for each a in game.action(state):\n",
       "    v2, a2 <- max_value(alpha, beta):\n",
       "    if v2 < v:\n",
       "      v=v2, move = a\n",
       "      alpha=min(beta, v) # update beta value\n",
       "    if v \\leq alpha: #means the value less than the lower bound\n",
       "      return\n",
       "```\n",
       "\\\n",
       "**expectimax search**: calculate the average value under optimal play.\n",
       "\n",
       "there are two players: MAX-value and EXP-value.\n",
       "\n",
       "```\n",
       "def exp-value:\n",
       "  for each successor of state:\n",
       "    p=probability(successor)\n",
       "\n",
       "      v+=p*\n",
       "    value(successor)\n",
       "  return v\n",
       "```\n",
       "**expectiminimax**: Environment is an extra “random agent” player that moves after each min/max agent\n",
       "\n",
       "**stochastic game** includes a random element. chance nodes denoting the probabilities associated with each action as well as expecti-minimax values are included in the minimax tree\n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Perfect information** - fully observable\n",
       "* **Utility function** - the final numeric value to player when the game ends in terminal state\n",
       "* **Minimax search** - assuming that both players play optimally and the player get the desired result\n",
       "* **Expectimax search** - considering outcome is uncertain, so compute the average score under optimal play\n",
       "* **Random variable** - the event whose outcome is unknown\n",
       "* **Probability distribution** - the weights to outcome\n",
       "\n",
       "\n",
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       "A solution to CSP is **complete and consisten**.\n",
       "\n",
       "a variable consistent means in its domain every value satisfies the binary constraints, if the map is consistent, every variable is arc consistent with others.\n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       "Assume a CSP with n variables, each with domain size at most $d$, and with $c$ BINARY constraints (arcs), **checking for arc consistency is $O(d^2)$**, total is **$O(cd^3)$**.\n",
       "\n",
       "**Path consistency** using implicit constraints that are inferred by **looking at triples of variables**. \n",
       "\n",
       "**1-consistency**=>node consistency; \n",
       "\n",
       "**2-consistency**=>arc consistency; \n",
       "\n",
       "For binary constraint graphs, **3-consistency**=>path consistency; \n",
       "\n",
       "**k-consistency**=>**for any set of k-1 variables and for any consistent assignment to those variables, a fixed value can always be assigned to any kth variable**.\n",
       "\n",
       "**strongly k-consistent**=>it is k-consistent and is also k-1-consistent, k-2-consistent, all the way down to 1-consistent.RUN **$O(dn^2)$**\n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       "Inference: **node, arc, path, and k-consistency**.\n",
       "\n",
       "**Forward checking**. The forward-checking process **establishes arc consistency for the assigned value**-> detect inevitable failure early\n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       " Your summary here \n",
       "\n",
       "## Module 6 Lecture Notes\n",
       "Assumption: **a single agent, deterministic actions, fully observed state, discrete state space**.\n",
       "\n",
       "CSP: **Represent the constraints that solutions must satisfy**.\n",
       "\n",
       "CSP is formed by **finite set of variables, Nonempty domain of possible values for each variable, and Finite set of constraints**\n",
       "\n",
       "We should use **general purpose algo** to find the solution of CSP.\n",
       "\n",
       "The solution to CSPs should be **complete** and **consistent**\n",
       "\n",
       "CSPs that require a solution that **maximizes an objective function**.\n",
       "\n",
       "CSP as a search problem: **Initial State, Successor function, Goal test and Path cost**.\n",
       "\n",
       "\\\n",
       "**representation of CSPs**:\n",
       "\n",
       "1. **constraint graph**-node: varibale; arcs/edges: (binary cinstraints)\n",
       "\n",
       "2. **standard representation pattern**\n",
       "\n",
       "\\\n",
       "**variables in CSPs**:\n",
       "\n",
       "1. *discrete variables*: finite domains(domain size $O(d^n)$, domain size$d$) and infinite domains(int, strings)\n",
       "\n",
       "2. *continuous variables*: like start/end times\n",
       "\n",
       "\\\n",
       "**variables in constraint**:\n",
       "\n",
       "1. unary constraint: a is not RED\n",
       "\n",
       "2. binary constarint: a not equal to b\n",
       "\n",
       "3. higher-order constraint: 3 or more variable invovled\n",
       "\n",
       "4. preference: a is prefered than b\n",
       "\n",
       "\\\n",
       "**always use DFS(backtracking-single-variable) to find solution**\n",
       "\n",
       "The variable assignments are commutative.\n",
       "\n",
       "\n",
       "**Heuristic**: to improve the effiency of backtracking\n",
       "\n",
       "1. try most constrained variable(minimum remaining values (MRV));\n",
       "\n",
       "2. Most constraining variable; \n",
       "\n",
       "3. Least constraining value; \n",
       "\n",
       "4. **Forward checking**. Terminate search when any unassigned variable has no remaining legal values.\n",
       "\n",
       "**AC-3 complexity**:\n",
       "\n",
       "There are $d$ values, checking all arcs uses $O(d^2)$. Each arc (i,j) can only be inserted into the queue $d$ times; **Worst case complexity**: $O(n^{2}d^{3})$\n",
       "\n",
       "\\\n",
       "```\n",
       "def AC-3(csp):\n",
       "  queue(contains all arcs in csp)\n",
       "  while queue:\n",
       "    $(X_{i}, X_{j})$=queue.pop()\n",
       "    if REVISE(csp, $X_{i}, X_{j}$):\n",
       "      if len($D_{i}$==0):\n",
       "        return false\n",
       "      for each $X_{k}$ in $X_{i}$.adj-${X_{j}}$:\n",
       "        add ($X_{k}, X_{i}$) to queue\n",
       "  return true\n",
       "\n",
       "def REVISE(csp,$X_{i}, X_{j}$):\n",
       "  revised=false\n",
       "  for x in $D_{i}$:\n",
       "    if no value y in $D_{i}$ let (x, y) satisfy the constraint:\n",
       "      delete x from $D_{i}$\n",
       "      revised=true\n",
       "  return revised\n",
       "\n",
       "```\n",
       "\n",
       "\n",
       "\n",
       "**cutset conditioning** reduce CSP to a tree structure.\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Constraint satisfaction problem** - A problem is solved when each variable has a value under related constraints.\n",
       "* **Consistent assignment** - the variable is assigned without violating any constraints.\n",
       "* **Complete assignment** - every varibale is assigned to a value.\n",
       "* **Constraint propagation** - reduce the number of legal values for a variable according to the constrains.\n",
       "* **Node-consistent** - all the values in the variable’s domain satisfy the variable’s unary constraints\n",
       "* **Arc consistency** - a variable is arc consistent if all value in the domain satisfies the variable's binary constraint\n",
       "* **Chronological backtracking** - back up to the preceding variable and try a different value for it\n",
       "* **Binary csp** - the constraint is related to two variables\n",
       "\n",
       "\n",
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       "**axiom sentence** means it is not derived from another sentences\n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       "\n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       "\n",
       "\n",
       "## Module 7 Lecture Notes\n",
       "**central component of a knowledge-based agent** is a **knowledge base(KB)**,A KB contains **a set of sentence** contains some assertion.\n",
       "\n",
       "$a|=b$ means $a$ is more specific or stronger than $b$, $M(a)$ belongs to $M(b)$. we can infer $b$ from $a$\n",
       "\n",
       "$KB |-_{i} a$ means $a$ is derived from $KB$ using inference algo $i$.\n",
       "\n",
       "**commutativity of ∧**:(α∧β) ≡ (β ∧α)  \n",
       "\n",
       "**commutativity of ∨**:(α∨β) ≡ (β ∨α)  \n",
       "\n",
       "**associativity of ∧**:((α∧β)∧γ) ≡ (α∧(β ∧γ))  \n",
       "\n",
       "**associativity of ∨**:((α∨β)∨γ) ≡ (α∨(β ∨γ))  \n",
       "\n",
       "**double-negation elimination**: ¬(¬α) ≡ α  \n",
       "\n",
       "**Contraposition**: $a\\Rightarrow b \\equiv ¬ b\\Rightarrow ¬a$;\n",
       "\n",
       "**Implication elimination**: $a \\Rightarrow b \\equiv a ⋁ b$;\n",
       "\n",
       "**Biconditional elimination**: $a\\leftrightarrow b \\equiv a\\Rightarrow b $and $b\\Rightarrow a$;\n",
       "\n",
       "**De Morgan**: $¬ (a ⋀ b) \\equiv ¬ a ⋁ ¬ b ; ¬(a ⋁ b)\\equiv ¬a ⋀ ¬b$.\n",
       "\n",
       "**Distributivity of ⋀ over ⋁**: $(a⋀b)⋁c = (a⋀c)⋁(b⋀c)$.\n",
       "\n",
       "**Distributivity of ⋁ over ⋀**: $(a⋁b)⋀c = (a⋁c)⋀(b⋁c)$.\n",
       "\n",
       "**And Elimination**: $a⋀b \\equiv a$.\n",
       "\n",
       "**Modus Ponens**: $a\\Rightarrow a,b \\equiv b$.\n",
       "\n",
       "\\\n",
       "Monotonicity implies Soundness.\n",
       "\n",
       "**If add more info is added to KB, the entailed sentence will be still valid**.\n",
       "\n",
       "Resolution: if two element if opponent, use **unit resolution** to solve.\n",
       "\n",
       "**Conjunctive Normal Form (CNF)**:\n",
       "\n",
       "1. we can eliminate $a \\leftrightarrow b$ to $a\\Rightarrow b ⋀ b\\Rightarrow a$; \n",
       "\n",
       "2. $a\\Rightarrow b$ to $ ¬ a ⋁ b$.\n",
       "\n",
       "3. move internal $¬$; \n",
       "\n",
       "4. use Distributivity of ⋀ over ⋁ or Distributivity of ⋁ over ⋀ to decrease nested ⋀ or ⋁\n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge-based agents** - agent that makes decision based on internal representation of knowledge\n",
       "* **Model** - a math abstractions that contains a set of truth value with boolean value to some sentences\n",
       "* **Logical entailment** - two sentence is linked by logic\n",
       "* **Logical inference** - the sentences can be inferred from the sentence in the KB\n",
       "* **Sound** - The inference algo can only infer entail sentence\n",
       "* **Complete** - The inference algo can derives all entailed sentences\n",
       "* **Logically equivalent** - two sentences have same set fo model\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 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
