{
  "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": 52,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "e43ef26f-5a79-4fb9-ed04-339a94e2e1c2"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 53,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "5a6761dd-aaa8-4543-f988-e84b8da7fa31"
      },
      "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": 54,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 55,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Chapter 1.1 summary. \"\"\" \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 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "Due to computational constraints, perfect rationality is impossible to achieve.\n",
        "Goal of rational agent: with a PEAS task environment, we have to create a agent function max expected value of performance measure \\\n",
        " create a program that implement the function\n",
        "If an object has its own performance measure, we can consider it as agent\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\" : \"perceptual input such as sensor input\",\n",
        "\"agent program\" : \"runs on architecture to produce a function\",\n",
        "\"Four views of Artificial Intelligence\": \"Thinking humanly, Thinking rationally, Acting humanly,Acting rationally \",\n",
        "\"Rational Agent.\": \"Behaves rationally after seeing the environment --> do the right thing\",\n",
        "\"Rational Agent.\": \"Goal is to Maximize performance measure and rational != 100% success\",\n",
        "\"Task Environments.\": \"Deffination of a whole problem\",\n",
        "\"PEAS for task enviroments.\": \"Performance measure, enviroment, actuators, sensors\",\n",
        "\"Goal of rational gent design.\": \"GIVEN PEAS task, 1. create a function max performance measure, 2. design agent program\",\n",
        "\"Hardest environment\": \"1. continuous, 2. partially observable, 3. stochastic 4. multiagent\",\n",
        "\n",
        "\"etc.\": \"your definitions here\",\n",
        "\n",
        "\n",
        "\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": 56,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 878
        },
        "id": "gYYeNcdM_maE",
        "outputId": "420323e7-4adc-4027-f061-10216a7e7fc6"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Chapter 1.1 summary. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " \n",
              "Due to computational constraints, perfect rationality is impossible to achieve.\n",
              "Goal of rational agent: with a PEAS task environment, we have to create a agent function max expected value of performance measure  create a program that implement the function\n",
              "If an object has its own performance measure, we can consider it as agent\n",
              "\n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - perceptual input such as sensor input\n",
              "* **Agent program** - runs on architecture to produce a function\n",
              "* **Four views of artificial intelligence** - Thinking humanly, Thinking rationally, Acting humanly,Acting rationally \n",
              "* **Rational agent.** - Goal is to Maximize performance measure and rational != 100% success\n",
              "* **Task environments.** - Deffination of a whole problem\n",
              "* **Peas for task enviroments.** - Performance measure, enviroment, actuators, sensors\n",
              "* **Goal of rational gent design.** - GIVEN PEAS task, 1. create a function max performance measure, 2. design agent program\n",
              "* **Hardest environment** - 1. continuous, 2. partially observable, 3. stochastic 4. multiagent\n",
              "* **Etc.** - your definitions here\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": 57,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DpBvu7EMx7sy",
        "outputId": "86c95c7a-6df9-4e00-a446-51e9c560afa9"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 450\n"
          ]
        }
      ],
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "@ Structure: whitespace deliminited, use \\ to end line, indentation meaningful \\n\n",
        "@ Objects and types: data is objects; strong typing: every object has a determined type and change do operations that limited on certain types \\\n",
        "such as \"foo\" + 2 is not allowed \\n\n",
        "@  Static type (java): type is declared and can not change, dynamic typing (Python): type change change anytime and it will be updated, ex: x = \"abc\", then x = 1      \\n\n",
        "@ String, tuple(cant be modified after created)immutable, list mutable, y = x[:] create shallow copy. == check values same, \"is\" check object address same \\n\n",
        "@ List operation:  t[1:-1:n] selection of every nth item , t[0:-1]. does a copy of ori list, a.index('c') index of first occurrence of c, a.remove('a') also remove first occurrence \\n\n",
        "@ String operation: split(), \" \".join(word_list), captitalize(), upper() --> make everything upper case, strip('.') --> remove front and end . \\n\n",
        "@ Dic: defaultdict initialize dict for empty keys, keys(), values(), items(), Set: create set() or {}, add(), remove() error if not exist, pop() remove random. \\n\n",
        "@ Python no function overloading, function name unique, but operator can overload inside a class \\n\n",
        "@ '*'args, function('*'args): print(args) , then, function(1,2,3) --> return (1,2,3), lst = [1,2,3], function('*'lst) --> return (1,2,3)   \\n\n",
        "@ '**'kwargs, function('**kwargs'): print(kwargs), then, function(a=1, b=2) ---> return {a:1,b:2}, dict={a:1, b:2}, function('**dict') --> return {a:1, b:2}  \\n\n",
        "@ Global scope, def function(x) return x + i, i is the global variable, will be updated  \\n\n",
        "@ Sub Class: class Dog(Animal): def _init(self, name): Animal._init_(self,name), use parent's init function \\n\n",
        "@ Function as input: def compose(f,g,x):return f(g(x)), compose(str, sum, [5,5]) --> return \"10\" \\n\n",
        "@ Class overwrite method: def show(self): Animal.show(self), additional lines of function \\n\n",
        "@ Super() class: inherit from multiple parent, can be confusing if parents have same function name \\n\n",
        "@ if __name__ == '__main__': , run this first for any python scripts \\n\n",
        "@ Duck Typing: def lift_off(entity): entity.fly() , lift_off(duck), or lift_off(plane), automaticly determine the output \\n\n",
        "@ List: list(range(5)) , [a+1 for a in list if a == 5] \\n\n",
        "@ Iterator: iterable object has _iter_() method --> convert to iterator , iter([a,b,c]) --> iterator object, these objects have next() method, [a,b,c]._iter_().next() = a. For loop will make a list into a iterator and keep calling next(), and wait till stopiteration exception \\n\n",
        "@ Generator: iterator uses less memory， def function(i): yield i , type(function(1)) --> generator, [i for i in function(5)]  \\n\n",
        "@ Generator Benefit: less code, keep local state auto, not store all in memory because compute once at time, good for infinite sequence. Cons: cant see each individual value \\n\n",
        "@ Importlib good for reloading from file \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(module2_lecture_notes.split(' ')))\n",
        "\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"String immutable, list mutable, y = x[:] create shallow copy\",\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 58,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 931
        },
        "id": "ydOK__lwWgdp",
        "outputId": "e6a974fc-a577-4cc7-f3fd-ef8752907c8c"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "\n",
              "@ Structure: whitespace deliminited, use \\ to end line, indentation meaningful \n",
              "\n",
              "@ Objects and types: data is objects; strong typing: every object has a determined type and change do operations that limited on certain types such as \"foo\" + 2 is not allowed \n",
              "\n",
              "@  Static type (java): type is declared and can not change, dynamic typing (Python): type change change anytime and it will be updated, ex: x = \"abc\", then x = 1      \n",
              "\n",
              "@ String, tuple(cant be modified after created)immutable, list mutable, y = x[:] create shallow copy. == check values same, \"is\" check object address same \n",
              "\n",
              "@ List operation:  t[1:-1:n] selection of every nth item , t[0:-1]. does a copy of ori list, a.index('c') index of first occurrence of c, a.remove('a') also remove first occurrence \n",
              "\n",
              "@ String operation: split(), \" \".join(word_list), captitalize(), upper() --> make everything upper case, strip('.') --> remove front and end . \n",
              "\n",
              "@ Dic: defaultdict initialize dict for empty keys, keys(), values(), items(), Set: create set() or {}, add(), remove() error if not exist, pop() remove random. \n",
              "\n",
              "@ Python no function overloading, function name unique, but operator can overload inside a class \n",
              "\n",
              "@ '*'args, function('*'args): print(args) , then, function(1,2,3) --> return (1,2,3), lst = [1,2,3], function('*'lst) --> return (1,2,3)   \n",
              "\n",
              "@ '**'kwargs, function('**kwargs'): print(kwargs), then, function(a=1, b=2) ---> return {a:1,b:2}, dict={a:1, b:2}, function('**dict') --> return {a:1, b:2}  \n",
              "\n",
              "@ Global scope, def function(x) return x + i, i is the global variable, will be updated  \n",
              "\n",
              "@ Sub Class: class Dog(Animal): def _init(self, name): Animal._init_(self,name), use parent's init function \n",
              "\n",
              "@ Function as input: def compose(f,g,x):return f(g(x)), compose(str, sum, [5,5]) --> return \"10\" \n",
              "\n",
              "@ Class overwrite method: def show(self): Animal.show(self), additional lines of function \n",
              "\n",
              "@ Super() class: inherit from multiple parent, can be confusing if parents have same function name \n",
              "\n",
              "@ if __name__ == '__main__': , run this first for any python scripts \n",
              "\n",
              "@ Duck Typing: def lift_off(entity): entity.fly() , lift_off(duck), or lift_off(plane), automaticly determine the output \n",
              "\n",
              "@ List: list(range(5)) , [a+1 for a in list if a == 5] \n",
              "\n",
              "@ Iterator: iterable object has _iter_() method --> convert to iterator , iter([a,b,c]) --> iterator object, these objects have next() method, [a,b,c]._iter_().next() = a. For loop will make a list into a iterator and keep calling next(), and wait till stopiteration exception \n",
              "\n",
              "@ Generator: iterator uses less memory， def function(i): yield i , type(function(1)) --> generator, [i for i in function(5)]  \n",
              "\n",
              "@ Generator Benefit: less code, keep local state auto, not store all in memory because compute once at time, good for infinite sequence. Cons: cant see each individual value \n",
              "\n",
              "@ Importlib good for reloading from file \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - String immutable, list mutable, y = x[:] create shallow copy\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": 59,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "BN0b1eVYx-nd",
        "outputId": "2748409f-ef93-4514-a33a-6f19116672ac"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 450\n"
          ]
        }
      ],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "@ Reflex Agents: ignore history, make decision on the current percept, vs problem solving agent which plan ahead, it will consider a sequence of actions to the goal \\n\n",
        "@  Fully observable, determinsitic, known env --> fixed solution, partially observable, non deterministic --> branching strategy, not determined \\n\n",
        "@  Defination of search problems: 1. states, actions, transition model that create successors, path cost (performance measure), goal test \\n\n",
        "@  Steps to form a search problem: 1. How to represent states, inital and goal 2. Represent Action, action and transition model 3. Path Cost, performance measure.  \\n\n",
        "@  Search problem is an abstract of real world, easier than real problem \\n\n",
        "@   \\n\n",
        "@. To define search problem: State space, Initial state, Goal states, Actions, Transition model, Action cost function \\n\n",
        "@  Basic search algorithm: Tree search. Root is start state, nodes is output of transition model, different paths to the same node is distinct.  \\n\n",
        "@  Node class contains state or matrix, parent, children, action, cost, depth \\n\n",
        "@  Repeated states: cycles --> make the linear problem to exponential \\n\n",
        "@  Graph search vs tree search: graph search checks if the node visited before, graph search faster and uses more space \\n\n",
        "@  Uninformed search : all non-goal nodes equally good. Informed search: some node better than others \\n\n",
        "@  A search method is uninformed if only has access to the problem definition \\n\n",
        "@   \\n\n",
        "@  Search Strategies: evaluation metric: 1. completeness --> find solution or not 2. optimal solution? 3. time complexity 4. space complexity \\n\n",
        "@  d = depth, b = max branching factor, m = max length of solution (goes to inf) \\n\n",
        "@  Different strategy have different queue structures (LIFO, FIFO, priority) \\n\n",
        "@   \\n\n",
        "@  BFS --- FIFO Queue, successor goes to the end of the queue \\n\n",
        "   def bfs:     \\n\n",
        "       if initial_state == goal: return initial_state \\n\n",
        "       frontier_fifo_queue = Queue() \\n\n",
        "       visited = {inital_state} \\n\n",
        "       parent = {} \\n\n",
        "       cost = {} \\n\n",
        "       while frontier_fifo_queue is not empty:\\n\n",
        "            current_node = frontier.pop() \\n\n",
        "            for each child in expand(current_node):  \\n\n",
        "              if child == goal: return child \\n\n",
        "              if child not in visited: \\n\n",
        "                  visited.add(current_node) \\n\n",
        "                  frontier.add(child) \\n\n",
        "        return can't find answer -- > failed \\n\n",
        "        \\n\n",
        "    def expand(node):     \\n\n",
        "       for each action in Actions(node): \\n\n",
        "          new_state, action_cost = take_action(action)\n",
        "          cost = parent_node_cost + action_cost\n",
        "          yield new Node(state=new state, parent=node, action=action, path_cost = cost)\n",
        "\n",
        "@   \\n\n",
        "@  DFS --- LIFO Queue, successor goes to the front of the queue \\n\n",
        "\n",
        "@  Compare DFS and BFS \\n\n",
        "    BFS pro: complete -- will always find answer, optimal -- find the best answer\n",
        "        con: space complexity high, need to save all the nodes travelled\n",
        "    DFS pro: save space, only keep b*m nodes\n",
        "        cons: not complete when path is inf, not optimal, use b^m time, bad if m much bigger than d\n",
        "@   When to use dfs: if space is not enough, wrong paths are not inf, so end quicker, or if solutions path are long \\n\n",
        "@   When to use bfs: if there are inf paths, bfs will avoid them, solution paths are shorter than average \\n\n",
        "@   \\n\n",
        "@   Depth-limited search: DFS but stop at a certain depth, not optimal, not complete \\n\n",
        "@   Iterative deepening search: To improve depth limited search, we can use for loop to increase depth limit from 0 to inf \\n\n",
        "    for depth_limit from 0 to inf:\n",
        "      depth_limit_search(depth_limit)\n",
        "      if find answer:\n",
        "        return solution\n",
        "        # else keep going and increase depth limit\n",
        "@   IDS: Complete and optimal, as efficient as BFS \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        "\"state\" : \"which object in which cell, the matrix\",    \n",
        "\"state space\" : \"all states can be reached from start state\",    \n",
        "\"path\" : \"sequence of actions from state a to b\",    \n",
        "\"solution\" : \"== goal\",    \n",
        "\"search tree\" : \"root = start state, leaves are successor state\",    \n",
        "\"frontier\" : \"states that can expand, have next steps (queue)\",\n",
        "\"optimal solution\" : \"lowest cost solution\",    \n",
        "\"solution\" : \"sequence of actions to goal, list of actions\",    \n",
        "\"asdfasdf\" : \"asdfasdfasdf\",    \n",
        "\"asdfasdf\" : \"asdfasdfasdf\",    \n",
        "\"asdfasdf\" : \"asdfasdfasdf\",    \n",
        "\"asdfasdf\" : \"asdfasdfasdf\",    \n",
        "\"asdfasdf\" : \"asdfasdfasdf\",    \n",
        "\"asdfasdf\" : \"asdfasdfasdf\",    \n",
        "\n",
        "\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(module2_lecture_notes.split(' ')))\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 60,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "ab256a0c-8cd1-4fb7-b255-cc16877659e9"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " Your summary here \n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "@ Reflex Agents: ignore history, make decision on the current percept, vs problem solving agent which plan ahead, it will consider a sequence of actions to the goal \n",
              "\n",
              "@  Fully observable, determinsitic, known env --> fixed solution, partially observable, non deterministic --> branching strategy, not determined \n",
              "\n",
              "@  Defination of search problems: 1. states, actions, transition model that create successors, path cost (performance measure), goal test \n",
              "\n",
              "@  Steps to form a search problem: 1. How to represent states, inital and goal 2. Represent Action, action and transition model 3. Path Cost, performance measure.  \n",
              "\n",
              "@  Search problem is an abstract of real world, easier than real problem \n",
              "\n",
              "@   \n",
              "\n",
              "@. To define search problem: State space, Initial state, Goal states, Actions, Transition model, Action cost function \n",
              "\n",
              "@  Basic search algorithm: Tree search. Root is start state, nodes is output of transition model, different paths to the same node is distinct.  \n",
              "\n",
              "@  Node class contains state or matrix, parent, children, action, cost, depth \n",
              "\n",
              "@  Repeated states: cycles --> make the linear problem to exponential \n",
              "\n",
              "@  Graph search vs tree search: graph search checks if the node visited before, graph search faster and uses more space \n",
              "\n",
              "@  Uninformed search : all non-goal nodes equally good. Informed search: some node better than others \n",
              "\n",
              "@  A search method is uninformed if only has access to the problem definition \n",
              "\n",
              "@   \n",
              "\n",
              "@  Search Strategies: evaluation metric: 1. completeness --> find solution or not 2. optimal solution? 3. time complexity 4. space complexity \n",
              "\n",
              "@  d = depth, b = max branching factor, m = max length of solution (goes to inf) \n",
              "\n",
              "@  Different strategy have different queue structures (LIFO, FIFO, priority) \n",
              "\n",
              "@   \n",
              "\n",
              "@  BFS --- FIFO Queue, successor goes to the end of the queue \n",
              "\n",
              "   def bfs:     \n",
              "\n",
              "       if initial_state == goal: return initial_state \n",
              "\n",
              "       frontier_fifo_queue = Queue() \n",
              "\n",
              "       visited = {inital_state} \n",
              "\n",
              "       parent = {} \n",
              "\n",
              "       cost = {} \n",
              "\n",
              "       while frontier_fifo_queue is not empty:\n",
              "\n",
              "            current_node = frontier.pop() \n",
              "\n",
              "            for each child in expand(current_node):  \n",
              "\n",
              "              if child == goal: return child \n",
              "\n",
              "              if child not in visited: \n",
              "\n",
              "                  visited.add(current_node) \n",
              "\n",
              "                  frontier.add(child) \n",
              "\n",
              "        return can't find answer -- > failed \n",
              "\n",
              "        \n",
              "\n",
              "    def expand(node):     \n",
              "\n",
              "       for each action in Actions(node): \n",
              "\n",
              "          new_state, action_cost = take_action(action)\n",
              "          cost = parent_node_cost + action_cost\n",
              "          yield new Node(state=new state, parent=node, action=action, path_cost = cost)\n",
              "\n",
              "@   \n",
              "\n",
              "@  DFS --- LIFO Queue, successor goes to the front of the queue \n",
              "\n",
              "\n",
              "@  Compare DFS and BFS \n",
              "\n",
              "    BFS pro: complete -- will always find answer, optimal -- find the best answer\n",
              "        con: space complexity high, need to save all the nodes travelled\n",
              "    DFS pro: save space, only keep b*m nodes\n",
              "        cons: not complete when path is inf, not optimal, use b^m time, bad if m much bigger than d\n",
              "@   When to use dfs: if space is not enough, wrong paths are not inf, so end quicker, or if solutions path are long \n",
              "\n",
              "@   When to use bfs: if there are inf paths, bfs will avoid them, solution paths are shorter than average \n",
              "\n",
              "@   \n",
              "\n",
              "@   Depth-limited search: DFS but stop at a certain depth, not optimal, not complete \n",
              "\n",
              "@   Iterative deepening search: To improve depth limited search, we can use for loop to increase depth limit from 0 to inf \n",
              "\n",
              "    for depth_limit from 0 to inf:\n",
              "      depth_limit_search(depth_limit)\n",
              "      if find answer:\n",
              "        return solution\n",
              "        # else keep going and increase depth limit\n",
              "@   IDS: Complete and optimal, as efficient as BFS \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **State** - which object in which cell, the matrix\n",
              "* **State space** - all states can be reached from start state\n",
              "* **Path** - sequence of actions from state a to b\n",
              "* **Solution** - sequence of actions to goal, list of actions\n",
              "* **Search tree** - root = start state, leaves are successor state\n",
              "* **Frontier** - states that can expand, have next steps (queue)\n",
              "* **Optimal solution** - lowest cost solution\n",
              "* **Asdfasdf** - asdfasdfasdf\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": 61,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "@  Uniformed Search: assume all moves have equal cost, ex: each move 1 cost \\n\n",
        "@  It's the extension of BFS, it expand node with lowest path cost, it has a priority queue to store the cost of current path \\n\n",
        "@  Check if goal, when selected for expansion (right after while loop, after pop), not when enqueue, because if check during enqueue, we could potentially miss the better solution \\n\n",
        "@  Uniformed search node expansion based on lowest path cost \\n\n",
        "@  BFS based on shallowest node \\n\n",
        "@  DFS based on deepest node \\n\n",
        "@  To improve on Uniformed search, introduce Best First Search, expansion with min evaluation function \\n\n",
        "@  There are two instance of Best First Search, Greedy Best first search and A star \\n\n",
        "@  Greedy only consider the estimation, expansion based on estimation that closest to goal \\n\n",
        "@  def greedy best-first search: \\n\n",
        "      frontier = PriorityQueue() \\n\n",
        "      frontier.put(start, 0) \\n\n",
        "      came_from[start] = None \\n\n",
        "      while not frontier.empty(): \\n\n",
        "          current = frontier.get() \\n\n",
        "          if current == goal: \\n\n",
        "            break \\n\n",
        "          for next in successors(current): \\n\n",
        "            if next not in came_from: \\n\n",
        "              priority = heuristic(goal, next) \\n\n",
        "              # distance from next node to goal \\n\n",
        "              frontier.put(next, priority) \\n\n",
        "              came_from[next] = current \\n\n",
        "@ greedy, complete? no, can stuck in loops, optimal, no, can be tricked by direct line distance  \\n\n",
        "@   \\n\n",
        "@ A star search --> best-known form of best-first search, expand most promising first, avoid expanding expensive paths \\n\n",
        "@ Combine g(n) the real cost so far + h(n) estimated cost from next to goal  \\n\n",
        "@ Difference with greedy, priority = heuristic(goal, next) + current_cost  \\n\n",
        "@ Admissibility:   \\n\n",
        "  admissible: never over estimate the cost to goal, --> optimistic, slow down bad plans --> optimal\n",
        "  inadmissible: can overestimate, thus trap good plans --> pessimistic\n",
        "@ Relaxed problem: less restrictions on actions than original problem  \\n\n",
        "@ Cost of the relaxed problem is admissible heuristic for original problem \\n\n",
        "@ Determine a good heuristic: h(n) that closest to the orignal problem is the best heuristic, but can have higher cost  \\n\n",
        "@ Bad heuristics: return 0 --> same as uniformed search  \\n\n",
        "@ Uninformed search only have access to problem definition vs. informed search have access to both problem definition and heuristic function  \\n\n",
        "@ A star problem: space complexity too high  \\n\n",
        "@ To improve this, iterative-deepening A star: use total_cost g(n) + h(n) as cut off, start with the cost 0 as threshold, run A star until find a cost greater than the threshold, then break and update the threshold to the new cost. Keep increasing threshold until find solution \\n\n",
        "@ Problem with IDA or RBFS (recursive best first search) is that they use too little memory, they forget most of things, so they revisit nodes over and over again \\n\n",
        "@ To improve this, MA star (memory bound A star) and SMA star, which expan nodes and save to memory until memory full, so next iteration, it will just use the memory to construct the tree, like Dynamic Programming  \\n\n",
        "@ IDA, SMA, RBFS are optimal, and more space efficient than A star (dont need to save everything in memory)  \\n\n",
        "@ Beam search limits the size of frontier, but it is not optimal, not complete, why use it? run faster than complete searches  \\n\n",
        "@ Weighted a star: f(n) = g(n) + weight x h(n), not optimal, yes complete, why use? expands fewer nodes  \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 62,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "2b94ae42-6c9f-4f37-97cc-309c76142b27"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Lecture Notes\n",
              "\n",
              "@  Uniformed Search: assume all moves have equal cost, ex: each move 1 cost \n",
              "\n",
              "@  It's the extension of BFS, it expand node with lowest path cost, it has a priority queue to store the cost of current path \n",
              "\n",
              "@  Check if goal, when selected for expansion (right after while loop, after pop), not when enqueue, because if check during enqueue, we could potentially miss the better solution \n",
              "\n",
              "@  Uniformed search node expansion based on lowest path cost \n",
              "\n",
              "@  BFS based on shallowest node \n",
              "\n",
              "@  DFS based on deepest node \n",
              "\n",
              "@  To improve on Uniformed search, introduce Best First Search, expansion with min evaluation function \n",
              "\n",
              "@  There are two instance of Best First Search, Greedy Best first search and A star \n",
              "\n",
              "@  Greedy only consider the estimation, expansion based on estimation that closest to goal \n",
              "\n",
              "@  def greedy best-first search: \n",
              "\n",
              "      frontier = PriorityQueue() \n",
              "\n",
              "      frontier.put(start, 0) \n",
              "\n",
              "      came_from[start] = None \n",
              "\n",
              "      while not frontier.empty(): \n",
              "\n",
              "          current = frontier.get() \n",
              "\n",
              "          if current == goal: \n",
              "\n",
              "            break \n",
              "\n",
              "          for next in successors(current): \n",
              "\n",
              "            if next not in came_from: \n",
              "\n",
              "              priority = heuristic(goal, next) \n",
              "\n",
              "              # distance from next node to goal \n",
              "\n",
              "              frontier.put(next, priority) \n",
              "\n",
              "              came_from[next] = current \n",
              "\n",
              "@ greedy, complete? no, can stuck in loops, optimal, no, can be tricked by direct line distance  \n",
              "\n",
              "@   \n",
              "\n",
              "@ A star search --> best-known form of best-first search, expand most promising first, avoid expanding expensive paths \n",
              "\n",
              "@ Combine g(n) the real cost so far + h(n) estimated cost from next to goal  \n",
              "\n",
              "@ Difference with greedy, priority = heuristic(goal, next) + current_cost  \n",
              "\n",
              "@ Admissibility:   \n",
              "\n",
              "  admissible: never over estimate the cost to goal, --> optimistic, slow down bad plans --> optimal\n",
              "  inadmissible: can overestimate, thus trap good plans --> pessimistic\n",
              "@ Relaxed problem: less restrictions on actions than original problem  \n",
              "\n",
              "@ Cost of the relaxed problem is admissible heuristic for original problem \n",
              "\n",
              "@ Determine a good heuristic: h(n) that closest to the orignal problem is the best heuristic, but can have higher cost  \n",
              "\n",
              "@ Bad heuristics: return 0 --> same as uniformed search  \n",
              "\n",
              "@ Uninformed search only have access to problem definition vs. informed search have access to both problem definition and heuristic function  \n",
              "\n",
              "@ A star problem: space complexity too high  \n",
              "\n",
              "@ To improve this, iterative-deepening A star: use total_cost g(n) + h(n) as cut off, start with the cost 0 as threshold, run A star until find a cost greater than the threshold, then break and update the threshold to the new cost. Keep increasing threshold until find solution \n",
              "\n",
              "@ Problem with IDA or RBFS (recursive best first search) is that they use too little memory, they forget most of things, so they revisit nodes over and over again \n",
              "\n",
              "@ To improve this, MA star (memory bound A star) and SMA star, which expan nodes and save to memory until memory full, so next iteration, it will just use the memory to construct the tree, like Dynamic Programming  \n",
              "\n",
              "@ IDA, SMA, RBFS are optimal, and more space efficient than A star (dont need to save everything in memory)  \n",
              "\n",
              "@ Beam search limits the size of frontier, but it is not optimal, not complete, why use it? run faster than complete searches  \n",
              "\n",
              "@ Weighted a star: f(n) = g(n) + weight x h(n), not optimal, yes complete, why use? expands fewer nodes  \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 63,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "iEIOpL7vyWcc",
        "outputId": "74f60977-136b-418d-bfb1-183fdcf4b265"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 1262\n"
          ]
        }
      ],
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "\n",
        "@ Simplest game environment: multiagent, static (no change when agent move), discrete (finite set of actions and percepts), fully observable (see everything, perfect information), strategic (new state = current state * action by a * action by b)  \\n\n",
        "@ Our game: two players, zero sum(win or lose), set of legal moves, defined results (w,l, draw)  \\n\n",
        "@ Form a game: Max and Min, Max goes first, they then take turns. 1. start state (matrix config) 2. sucessor function, 3. goal test 4. utility function (performance measure, int value for outcomes, w, l , draw)  \\n\n",
        "@ Game Tree: node --> board position, matrix, edges --> actions, legal moves, root --> inital state  \\n\n",
        "@   \\n\n",
        "@ Adversarial Search: all cost from Max's vantage point, Max --> maximize max's result, Min --> minimize max's result \\n\n",
        "@ Max action on Even levels (level 0 starts), Min action on Odd levels  \\n\n",
        "@ Evaluation function(board position) ---> score, without referring to path. Terminal nodes --> ending of the game (With label W, L ,D)  \\n\n",
        "@ Evaluation function: evalues board position (without knowning history), we can measure because the board is static, and zero sum (we can use 1 function to evaluate for two players). f(n) > 0 if Max is in advantage. For example, tic-tac-toe: f(n) = number of opening position for MAX - number of opening position for MIN  \\n\n",
        "@   \\n\n",
        "@ The Minimax Rule: max and min will choose best value move, best for Max --> max value of Max's children, best for Min --> min value of Min's children  \\n\n",
        "@ def max-value(state):  \\n\n",
        "  if the state == terminal state (win or lose or draw): \\n\n",
        "      return state utility \\n\n",
        "  init value = -inf \\n\n",
        "  for successor of state: \\n\n",
        "    value = max(value, min-value(successor)) \\n\n",
        "  return value \\n\n",
        "  \n",
        "@   \\n\n",
        "@   \\n\n",
        "@ def min-value(state):  \\n\n",
        "  if the state == terminal state (win or lose or draw): \\n\n",
        "      return state utility \\n\n",
        "  init value = inf \\n\n",
        "  for successor of state: \\n\n",
        "    value = min(value, max-value(successor)) \\n\n",
        "  return value \\n\n",
        "@   \\n\n",
        "@ min does not play optimally? Max will do better always  \\n\n",
        "@   \\n\n",
        "@  Alpha-Beta Pruning \\n\n",
        "@  α = MAX's current min value on its outcome, β: min's current max value on its outcome \\n\n",
        "@  Max will not select min node that value < α, Min will not select max node that value >= β  \\n\n",
        "@   \\n\n",
        "@ def max-value_alpha_beta(state):  \\n\n",
        "  if the state == terminal state (win or lose or draw): \\n\n",
        "      return state utility \\n\n",
        "  init value = -inf \\n\n",
        "  for successor of state: \\n\n",
        "    value = max(value, min-value(successor)) \\n\n",
        "    alpha = MAX(alpha, value) \\n\n",
        "    if value >= beta: \\n \n",
        "      then return value  \\n \n",
        "  return value \\n\n",
        "\n",
        "    # beta is the smallest value, min will choose, \n",
        "    # if value >= beta, that means min will no choose this branch,\n",
        "    # thus no need to go further /n\n",
        "\n",
        "@   \\n\n",
        "\n",
        "@ def min-value_alpha_beta(state):  \\n\n",
        "  if the state == terminal state (win or lose or draw): \\n\n",
        "      return state utility \\n\n",
        "  init value = inf \\n\n",
        "  for successor of state: \\n\n",
        "    value = min(value, max-value(successor)) \\n\n",
        "    beta = Min(beta, value) \\n\n",
        "    if value <= alpha: \\n \n",
        "      then return value  \\n \n",
        "  return value \\n\n",
        "\n",
        "    # alpha is the largest value, max will choose, \n",
        "    # if value <= alpha, that means max will no choose this branch,\n",
        "    # thus no need to go further /n\n",
        "@   \\n\n",
        "@  Expectimax Search \\n\n",
        "@  When we dont know the outcome, ex: rolling dice. Value of action are now average value \\n\n",
        "@  Expectimax search: find average score under optimal decision, Max are still max, min becomes chance node \\n\n",
        "@   \\n\n",
        "@  def value(state): \\n\n",
        "      if state == terminal state: return state utility \\n\n",
        "      if next_level is MAX (even level): return max_value(state) \\n\n",
        "      if next_level is EXP (odd level): return expect_value(state) \\n\n",
        "\n",
        "@   \\n\n",
        "@  def max_value(state): \\n\n",
        "      init v = -inf \\n\n",
        "      for successor of state: \\n\n",
        "          v = max(v, value(successor)) \\n\n",
        "      return v \\n\n",
        "@   \\n\n",
        "@  def exp_value(state): \\n\n",
        "      init v = 0 \\n\n",
        "      for successor of state: \\n\n",
        "        p = probality(successor) \\n\n",
        "        v = v + p * value(successor) \\n\n",
        "      return v \\n\n",
        "@   \\n\n",
        "@ Probability  \\n\n",
        "@ random variable: an event with unknow outcome  \\n\n",
        "@  probaility distribution is assignment of weights to outcomes or possiblity for each outcome in the event \\n\n",
        "@  probality all sum to 1, all positive \\n\n",
        "@   \\n\n",
        "@ objectivist/ frequentist: probability is average over repeated experiments, rolling dice for 1000 times and find average  \\n\n",
        "@ Subjectivist / Bayesian : degrees of belif about unobserved variables, an experts belieft on how things will be  \\n\n",
        "@   \\n\n",
        "@ Expectiminmax: another random agent, play in between max and min  \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@ Facts to know  \\n\n",
        "\n",
        "@  Games vs search problems: games have multiple agents \\n\n",
        "@  Perfect information = fully observable \\n\n",
        "@  Untility function --> determine terminal state payoff \\n\n",
        "@  Minimax same order as DFS, always the deepest first \\n\n",
        "@  Minimax time complexity = b^m   same as DFS \\n\n",
        "@  Running time of alpha beta impact by the order we examine nodes, because if we always find worst successor first, we have to keep going, just like min max game search \\n\n",
        "@  Alpha-beta time complexity = b^0.5m \\n\n",
        "@  Type A strategy exlores wide but shallow part of the tree \\n\n",
        "@  Type B deep but narrow \\n\n",
        "@  If the game is too big, we have to choose between A and B, because cant search every node \\n\n",
        "@  Heuristic alpha beta use evaluation function instead of utililty function, it also evaluate the non-terminal nodes. It uses cutoff test instead of terminal test. It will cut off the game early. Evaluation on quiescent positions only (position without any big changes for next step) \\n\n",
        "@  Horizon effect: when agent try to delay the inevitable (dead game) \\n\n",
        "@  Forward pruning (Type B strategy) --> bad moves (Ex: beam search) \\n\n",
        "@  MCTS (monte carlo tree search) ---> random selecting moves --> evaluate the state by playing randomly at the state and find the average value\\n\n",
        "@  Define a game: 1. time for player to make a move 2. terminal states 3. set of legal moves can make 4. utility function 5. initial state \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "print(\"The length in words is\", len(module5_lecture_notes.split(' ')))\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 64,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "4dcbed20-5fcf-4ac6-e5a5-d7b476e9c1b3"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              "\n",
              "\n",
              "@ Simplest game environment: multiagent, static (no change when agent move), discrete (finite set of actions and percepts), fully observable (see everything, perfect information), strategic (new state = current state * action by a * action by b)  \n",
              "\n",
              "@ Our game: two players, zero sum(win or lose), set of legal moves, defined results (w,l, draw)  \n",
              "\n",
              "@ Form a game: Max and Min, Max goes first, they then take turns. 1. start state (matrix config) 2. sucessor function, 3. goal test 4. utility function (performance measure, int value for outcomes, w, l , draw)  \n",
              "\n",
              "@ Game Tree: node --> board position, matrix, edges --> actions, legal moves, root --> inital state  \n",
              "\n",
              "@   \n",
              "\n",
              "@ Adversarial Search: all cost from Max's vantage point, Max --> maximize max's result, Min --> minimize max's result \n",
              "\n",
              "@ Max action on Even levels (level 0 starts), Min action on Odd levels  \n",
              "\n",
              "@ Evaluation function(board position) ---> score, without referring to path. Terminal nodes --> ending of the game (With label W, L ,D)  \n",
              "\n",
              "@ Evaluation function: evalues board position (without knowning history), we can measure because the board is static, and zero sum (we can use 1 function to evaluate for two players). f(n) > 0 if Max is in advantage. For example, tic-tac-toe: f(n) = number of opening position for MAX - number of opening position for MIN  \n",
              "\n",
              "@   \n",
              "\n",
              "@ The Minimax Rule: max and min will choose best value move, best for Max --> max value of Max's children, best for Min --> min value of Min's children  \n",
              "\n",
              "@ def max-value(state):  \n",
              "\n",
              "  if the state == terminal state (win or lose or draw): \n",
              "\n",
              "      return state utility \n",
              "\n",
              "  init value = -inf \n",
              "\n",
              "  for successor of state: \n",
              "\n",
              "    value = max(value, min-value(successor)) \n",
              "\n",
              "  return value \n",
              "\n",
              "  \n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@ def min-value(state):  \n",
              "\n",
              "  if the state == terminal state (win or lose or draw): \n",
              "\n",
              "      return state utility \n",
              "\n",
              "  init value = inf \n",
              "\n",
              "  for successor of state: \n",
              "\n",
              "    value = min(value, max-value(successor)) \n",
              "\n",
              "  return value \n",
              "\n",
              "@   \n",
              "\n",
              "@ min does not play optimally? Max will do better always  \n",
              "\n",
              "@   \n",
              "\n",
              "@  Alpha-Beta Pruning \n",
              "\n",
              "@  α = MAX's current min value on its outcome, β: min's current max value on its outcome \n",
              "\n",
              "@  Max will not select min node that value < α, Min will not select max node that value >= β  \n",
              "\n",
              "@   \n",
              "\n",
              "@ def max-value_alpha_beta(state):  \n",
              "\n",
              "  if the state == terminal state (win or lose or draw): \n",
              "\n",
              "      return state utility \n",
              "\n",
              "  init value = -inf \n",
              "\n",
              "  for successor of state: \n",
              "\n",
              "    value = max(value, min-value(successor)) \n",
              "\n",
              "    alpha = MAX(alpha, value) \n",
              "\n",
              "    if value >= beta: \n",
              " \n",
              "      then return value  \n",
              " \n",
              "  return value \n",
              "\n",
              "\n",
              "    # beta is the smallest value, min will choose, \n",
              "    # if value >= beta, that means min will no choose this branch,\n",
              "    # thus no need to go further /n\n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "@ def min-value_alpha_beta(state):  \n",
              "\n",
              "  if the state == terminal state (win or lose or draw): \n",
              "\n",
              "      return state utility \n",
              "\n",
              "  init value = inf \n",
              "\n",
              "  for successor of state: \n",
              "\n",
              "    value = min(value, max-value(successor)) \n",
              "\n",
              "    beta = Min(beta, value) \n",
              "\n",
              "    if value <= alpha: \n",
              " \n",
              "      then return value  \n",
              " \n",
              "  return value \n",
              "\n",
              "\n",
              "    # alpha is the largest value, max will choose, \n",
              "    # if value <= alpha, that means max will no choose this branch,\n",
              "    # thus no need to go further /n\n",
              "@   \n",
              "\n",
              "@  Expectimax Search \n",
              "\n",
              "@  When we dont know the outcome, ex: rolling dice. Value of action are now average value \n",
              "\n",
              "@  Expectimax search: find average score under optimal decision, Max are still max, min becomes chance node \n",
              "\n",
              "@   \n",
              "\n",
              "@  def value(state): \n",
              "\n",
              "      if state == terminal state: return state utility \n",
              "\n",
              "      if next_level is MAX (even level): return max_value(state) \n",
              "\n",
              "      if next_level is EXP (odd level): return expect_value(state) \n",
              "\n",
              "\n",
              "@   \n",
              "\n",
              "@  def max_value(state): \n",
              "\n",
              "      init v = -inf \n",
              "\n",
              "      for successor of state: \n",
              "\n",
              "          v = max(v, value(successor)) \n",
              "\n",
              "      return v \n",
              "\n",
              "@   \n",
              "\n",
              "@  def exp_value(state): \n",
              "\n",
              "      init v = 0 \n",
              "\n",
              "      for successor of state: \n",
              "\n",
              "        p = probality(successor) \n",
              "\n",
              "        v = v + p * value(successor) \n",
              "\n",
              "      return v \n",
              "\n",
              "@   \n",
              "\n",
              "@ Probability  \n",
              "\n",
              "@ random variable: an event with unknow outcome  \n",
              "\n",
              "@  probaility distribution is assignment of weights to outcomes or possiblity for each outcome in the event \n",
              "\n",
              "@  probality all sum to 1, all positive \n",
              "\n",
              "@   \n",
              "\n",
              "@ objectivist/ frequentist: probability is average over repeated experiments, rolling dice for 1000 times and find average  \n",
              "\n",
              "@ Subjectivist / Bayesian : degrees of belif about unobserved variables, an experts belieft on how things will be  \n",
              "\n",
              "@   \n",
              "\n",
              "@ Expectiminmax: another random agent, play in between max and min  \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@ Facts to know  \n",
              "\n",
              "\n",
              "@  Games vs search problems: games have multiple agents \n",
              "\n",
              "@  Perfect information = fully observable \n",
              "\n",
              "@  Untility function --> determine terminal state payoff \n",
              "\n",
              "@  Minimax same order as DFS, always the deepest first \n",
              "\n",
              "@  Minimax time complexity = b^m   same as DFS \n",
              "\n",
              "@  Running time of alpha beta impact by the order we examine nodes, because if we always find worst successor first, we have to keep going, just like min max game search \n",
              "\n",
              "@  Alpha-beta time complexity = b^0.5m \n",
              "\n",
              "@  Type A strategy exlores wide but shallow part of the tree \n",
              "\n",
              "@  Type B deep but narrow \n",
              "\n",
              "@  If the game is too big, we have to choose between A and B, because cant search every node \n",
              "\n",
              "@  Heuristic alpha beta use evaluation function instead of utililty function, it also evaluate the non-terminal nodes. It uses cutoff test instead of terminal test. It will cut off the game early. Evaluation on quiescent positions only (position without any big changes for next step) \n",
              "\n",
              "@  Horizon effect: when agent try to delay the inevitable (dead game) \n",
              "\n",
              "@  Forward pruning (Type B strategy) --> bad moves (Ex: beam search) \n",
              "\n",
              "@  MCTS (monte carlo tree search) ---> random selecting moves --> evaluate the state by playing randomly at the state and find the average value\n",
              "\n",
              "@  Define a game: 1. time for player to make a move 2. terminal states 3. set of legal moves can make 4. utility function 5. initial state \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "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": 65,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Wm4mfW82yaRH",
        "outputId": "59b2ae26-64bb-4a1a-d553-61e2f462ba23"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 1310\n"
          ]
        }
      ],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "\n",
        "@ Search problem: 1 agent (game problems have more), deterministic actions, fully observable (perfect information), discrete state space (finite)  \\n\n",
        "@ Two types of search problems: planning --> BFS, DFS, sequence is important, identification: variable assignment --> path doesnt matter, Constraints satisfaction problems \\n\n",
        "@ Constraints satisfaction problem: represent constrainst in uniform declarative leanguage that the algorithm should work on all problems  \\n\n",
        "@ CSP consists: 1. finite set of variables 2. set of possible values for each varaible 3. set of constraints ex: variable x1 != variable x2  \\n\n",
        "@ CSP is done when all variables have a value, outcome should be compelete and consistent  \\n\n",
        "@ CSP pros: generic, eliminate branch violate constraints, can tell which one violate constraint easily  \\n\n",
        "@ Representation: graph, node --> variable, arc/edge --> constraints  \\n\n",
        "@ Different kinds of CSP: discrete variables (finite domain and infinite domain) , continuous variables (time)  \\n\n",
        "@ Different kinds of constraints: unary --> a!= pig, binary --> x1 != x2, higher-oder --> sudoku, preference/soft constraints --> a better than c, represent by cost  \\n\n",
        "@   \\n\n",
        "@ Solve CSP problem: 1. As search problem (DFS/ backtracking), 2. Improve on backtracking, choose assgined variable (a. most constrained b. most constraining c. least contraining d. forward checking)  3. inference \\n\n",
        "@ Idea 1: search problem  (Backtracking/ Uninformed DFS) \\n\n",
        "@ Each depth is a variable, width is number of values tried for this variable  \\n\n",
        "@   \\n\n",
        "@ Form problem: 1. init state, empty assignment 2. successor function: assgin values without conflict 3. if == goal, commplete 4. path cost: step cost  \\n\n",
        "@ Solution always in depth n for n variable, ex: map problem, depth always = number of variables  \\n\n",
        "@ n number variables, d = number domain of values, branching factor at root = n * d, next level = (n-1) * d , number of leaves n! * d^n  \\n\n",
        "@ It's a tree search not a graph search, beacuse variable assignments are communtative, and the number of leaves can reduce to d^n because commutative  \\n\n",
        "@ Back tracking means use DFS to assign one values for one variable at a time and return when no values to assign  \\n\n",
        "@   \\n\n",
        "@ Idea 2: improve backtracking (add Heuristic function)  \\n\n",
        "@ Which variable assign first: a. most constrained variable (MRV, variable with fewer legal values) b. to break tie for a, most constraining variable (degree heuristic: variable that affets neighbors the most) \\n\n",
        "@ How to try values:  least constraining values (value that reduce fewer options for neighbors) \\n\n",
        "@ How to detect failure early: forward checking --> keep track remaining values for all variables, if a variable has no values left, it means failed, so break early  \\n\n",
        "@ Drawck for forward checking: only consider empty variables, doesnt detect all failures such as (A and B are all red on the map)  \\n\n",
        "@   \\n\n",
        "@ To improve  \\n\n",
        "@ Idea 3: Inference (Constraint propagation)  \\n\n",
        "@ Steps now: 1. Search, assign value to a variable 2. Constraint propagation: eliminiate illegal values for all variables  \\n\n",
        "@ Consistency: node --> unary constraint, arc --> binary cons  \\n\n",
        "@ Arc cons: X to Y is consistent if and only every value x of X there is some allowed y  \\n\n",
        "@ Waltz/Mackworth Algorithm:  \\n\n",
        "    assign all variable a set of possible values,  for example: sudoku (1,1) {1,2,3,5} \\n\n",
        "    while still changes in the matrix: \\n\n",
        "      for each node i :  \\n\n",
        "          for each of its neightbors j : \\n\n",
        "            remove illegal values from i set based j set (set i - set j). \\n\n",
        "@ Problems: inefficient, 1. no need to check all nodes, just check affected, only these neighbors of node i that have conflict with i (push neighbors into queue if conflict); 2. if x and y have conflict, push all neighbors of x, except y 3. Removing a value from Xi can only cause Yj to be inconsistent with regard to Xi. --> just ensure that (j,i) arc-consistent.   \\n\n",
        "@   \\n\n",
        "@ To improve: ---> AC-3  \\n\n",
        "\n",
        "'''\n",
        "\n",
        "    def remove_inconsistent_values(self, cell1, cell2):\n",
        "        if (cell1,cell2) in self.ARCS:\n",
        "            if len(self.board[cell2]) == 1:\n",
        "                if self.board[cell2].issubset(self.board[cell1]):\n",
        "                    self.board[cell1] = self.board[cell1] - self.board[cell2]\n",
        "                    return True\n",
        "        return False\n",
        "\n",
        "\n",
        "    def infer_ac3(self):\n",
        "        q = Queue()\n",
        "        for arc in self.ARCS:\n",
        "            q.put(arc)\n",
        "        while q.empty() == False:\n",
        "            arc = q.get()\n",
        "            if self.remove_inconsistent_values(arc[0],arc[1]):\n",
        "                for other_arcs in self.ARCS:\n",
        "                    if arc[0] == other_arcs[1]:\n",
        "                        q.put(other_arcs)\n",
        "'''\n",
        "@   \\n\n",
        "@ All nodes can connect to others, total number of arcs = 2*n*(n-1), O(n^2), n = number of variables  \\n\n",
        "@ d values, check arc(i,j) takes O(d^2), each arc can be in queue d times  \\n\n",
        "@ Worst complexity O(n^2 d^3), planar graphs, num arcs is linear, so complexity is O(nd^3)  \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@ Facts  \\n\n",
        "@ CSP represent a state with a set of variable value pairs  \\n\n",
        "@ CSPs represent the conditions for a solution with a set of constraints on the variables\\n\n",
        "@ CSP vs search problem: serach problem states are unseen, need to move using transition model, but CSP we can see inside states  \\n\n",
        "@ CSP has 2 ways ruling out variable assignment: 1. search: generate successors (like search problem) or 2: inference, constraints propagation \\n\n",
        "@ The key idea behind inference in CSPs is enforcing k consistency  \\n\n",
        "@ Node consistency is k-consistency for k = 1, arc consistency is k = 2, path is k = 3 \\n\n",
        "@ AC-3 is algorithm for arc consistency, so it cant solve all CSP, only k = 2  \\n\n",
        "@ Backtracking starts when no legal assignment found  \\n\n",
        "@ Constraint learning records conflicts found in search to avoid later  \\n\n",
        "@ Solve arbitray CSP --> exponential to the num of variables \\n\n",
        "@ Tree CSP take linear time to num of variables, planar graphs as well \\n\n",
        "@ Cutest conditioning used to reduce CSP to tree structure, but it only works if found small cutset, no always better  \\n\n",
        "@ Tree decomposition --> CSP to tree of subproblems, only work if width of tree of contraint graph is small  \\n\n",
        "@ Tree decomp time efficent than Cutset, but cutset better space efficient \\n\n",
        "@ MAC --> maintain arc consistency  \\n\n",
        "@ MAC vs AC-3: mac assign variable in backtracking search, not enqueue all arcs, only enqueue arc on assgineed variables (AC3 enqueue all arc at beginning) \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "@   \\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "print(\"The length in words is\", len(module6_lecture_notes.split(' ')))\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 66,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "3cac28ec-1bbf-412b-ec03-22a67923602a"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " Your summary here \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",
              "\n",
              "\n",
              "@ Search problem: 1 agent (game problems have more), deterministic actions, fully observable (perfect information), discrete state space (finite)  \n",
              "\n",
              "@ Two types of search problems: planning --> BFS, DFS, sequence is important, identification: variable assignment --> path doesnt matter, Constraints satisfaction problems \n",
              "\n",
              "@ Constraints satisfaction problem: represent constrainst in uniform declarative leanguage that the algorithm should work on all problems  \n",
              "\n",
              "@ CSP consists: 1. finite set of variables 2. set of possible values for each varaible 3. set of constraints ex: variable x1 != variable x2  \n",
              "\n",
              "@ CSP is done when all variables have a value, outcome should be compelete and consistent  \n",
              "\n",
              "@ CSP pros: generic, eliminate branch violate constraints, can tell which one violate constraint easily  \n",
              "\n",
              "@ Representation: graph, node --> variable, arc/edge --> constraints  \n",
              "\n",
              "@ Different kinds of CSP: discrete variables (finite domain and infinite domain) , continuous variables (time)  \n",
              "\n",
              "@ Different kinds of constraints: unary --> a!= pig, binary --> x1 != x2, higher-oder --> sudoku, preference/soft constraints --> a better than c, represent by cost  \n",
              "\n",
              "@   \n",
              "\n",
              "@ Solve CSP problem: 1. As search problem (DFS/ backtracking), 2. Improve on backtracking, choose assgined variable (a. most constrained b. most constraining c. least contraining d. forward checking)  3. inference \n",
              "\n",
              "@ Idea 1: search problem  (Backtracking/ Uninformed DFS) \n",
              "\n",
              "@ Each depth is a variable, width is number of values tried for this variable  \n",
              "\n",
              "@   \n",
              "\n",
              "@ Form problem: 1. init state, empty assignment 2. successor function: assgin values without conflict 3. if == goal, commplete 4. path cost: step cost  \n",
              "\n",
              "@ Solution always in depth n for n variable, ex: map problem, depth always = number of variables  \n",
              "\n",
              "@ n number variables, d = number domain of values, branching factor at root = n * d, next level = (n-1) * d , number of leaves n! * d^n  \n",
              "\n",
              "@ It's a tree search not a graph search, beacuse variable assignments are communtative, and the number of leaves can reduce to d^n because commutative  \n",
              "\n",
              "@ Back tracking means use DFS to assign one values for one variable at a time and return when no values to assign  \n",
              "\n",
              "@   \n",
              "\n",
              "@ Idea 2: improve backtracking (add Heuristic function)  \n",
              "\n",
              "@ Which variable assign first: a. most constrained variable (MRV, variable with fewer legal values) b. to break tie for a, most constraining variable (degree heuristic: variable that affets neighbors the most) \n",
              "\n",
              "@ How to try values:  least constraining values (value that reduce fewer options for neighbors) \n",
              "\n",
              "@ How to detect failure early: forward checking --> keep track remaining values for all variables, if a variable has no values left, it means failed, so break early  \n",
              "\n",
              "@ Drawck for forward checking: only consider empty variables, doesnt detect all failures such as (A and B are all red on the map)  \n",
              "\n",
              "@   \n",
              "\n",
              "@ To improve  \n",
              "\n",
              "@ Idea 3: Inference (Constraint propagation)  \n",
              "\n",
              "@ Steps now: 1. Search, assign value to a variable 2. Constraint propagation: eliminiate illegal values for all variables  \n",
              "\n",
              "@ Consistency: node --> unary constraint, arc --> binary cons  \n",
              "\n",
              "@ Arc cons: X to Y is consistent if and only every value x of X there is some allowed y  \n",
              "\n",
              "@ Waltz/Mackworth Algorithm:  \n",
              "\n",
              "    assign all variable a set of possible values,  for example: sudoku (1,1) {1,2,3,5} \n",
              "\n",
              "    while still changes in the matrix: \n",
              "\n",
              "      for each node i :  \n",
              "\n",
              "          for each of its neightbors j : \n",
              "\n",
              "            remove illegal values from i set based j set (set i - set j). \n",
              "\n",
              "@ Problems: inefficient, 1. no need to check all nodes, just check affected, only these neighbors of node i that have conflict with i (push neighbors into queue if conflict); 2. if x and y have conflict, push all neighbors of x, except y 3. Removing a value from Xi can only cause Yj to be inconsistent with regard to Xi. --> just ensure that (j,i) arc-consistent.   \n",
              "\n",
              "@   \n",
              "\n",
              "@ To improve: ---> AC-3  \n",
              "\n",
              "\n",
              "'''\n",
              "\n",
              "    def remove_inconsistent_values(self, cell1, cell2):\n",
              "        if (cell1,cell2) in self.ARCS:\n",
              "            if len(self.board[cell2]) == 1:\n",
              "                if self.board[cell2].issubset(self.board[cell1]):\n",
              "                    self.board[cell1] = self.board[cell1] - self.board[cell2]\n",
              "                    return True\n",
              "        return False\n",
              "\n",
              "\n",
              "    def infer_ac3(self):\n",
              "        q = Queue()\n",
              "        for arc in self.ARCS:\n",
              "            q.put(arc)\n",
              "        while q.empty() == False:\n",
              "            arc = q.get()\n",
              "            if self.remove_inconsistent_values(arc[0],arc[1]):\n",
              "                for other_arcs in self.ARCS:\n",
              "                    if arc[0] == other_arcs[1]:\n",
              "                        q.put(other_arcs)\n",
              "'''\n",
              "@   \n",
              "\n",
              "@ All nodes can connect to others, total number of arcs = 2*n*(n-1), O(n^2), n = number of variables  \n",
              "\n",
              "@ d values, check arc(i,j) takes O(d^2), each arc can be in queue d times  \n",
              "\n",
              "@ Worst complexity O(n^2 d^3), planar graphs, num arcs is linear, so complexity is O(nd^3)  \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@ Facts  \n",
              "\n",
              "@ CSP represent a state with a set of variable value pairs  \n",
              "\n",
              "@ CSPs represent the conditions for a solution with a set of constraints on the variables\n",
              "\n",
              "@ CSP vs search problem: serach problem states are unseen, need to move using transition model, but CSP we can see inside states  \n",
              "\n",
              "@ CSP has 2 ways ruling out variable assignment: 1. search: generate successors (like search problem) or 2: inference, constraints propagation \n",
              "\n",
              "@ The key idea behind inference in CSPs is enforcing k consistency  \n",
              "\n",
              "@ Node consistency is k-consistency for k = 1, arc consistency is k = 2, path is k = 3 \n",
              "\n",
              "@ AC-3 is algorithm for arc consistency, so it cant solve all CSP, only k = 2  \n",
              "\n",
              "@ Backtracking starts when no legal assignment found  \n",
              "\n",
              "@ Constraint learning records conflicts found in search to avoid later  \n",
              "\n",
              "@ Solve arbitray CSP --> exponential to the num of variables \n",
              "\n",
              "@ Tree CSP take linear time to num of variables, planar graphs as well \n",
              "\n",
              "@ Cutest conditioning used to reduce CSP to tree structure, but it only works if found small cutset, no always better  \n",
              "\n",
              "@ Tree decomposition --> CSP to tree of subproblems, only work if width of tree of contraint graph is small  \n",
              "\n",
              "@ Tree decomp time efficent than Cutset, but cutset better space efficient \n",
              "\n",
              "@ MAC --> maintain arc consistency  \n",
              "\n",
              "@ MAC vs AC-3: mac assign variable in backtracking search, not enqueue all arcs, only enqueue arc on assgineed variables (AC3 enqueue all arc at beginning) \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 67,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "@  Knowledge based agent: reasoning over knowledge to act. Problem solving agent search over states to find plan and states are atomic \\n\n",
        "@  Knowledge Base (representation language): Axioms --> given sentences, derived sentence --> inference from old sentences;  \\n\n",
        "@  Logic defines semantic/ meaning of sentences, the semantics defines the truth of the world/model \\n\n",
        "@  Models is fixed set of truth values for each sentences, M(a) means all the models that satisfies setence a \\n\n",
        "@  Logical entailment \\n\n",
        "@  a⊨β if and only if M(a) ⊆ M(β), a entails b --> a is specific/stronger than b, ex: b: he is a anima, a: he is a dog \\n\n",
        "@  Possible worlds: find worlds that compatible with KB, M(KB) ⊆ M(a1 ) \\n\n",
        "@  Logical inference: derive from logical entails, KB ⊢i a, a is derived from kb by i  \\n\n",
        "@  Propostitional Logic: cheat sheet \\n\n",
        "@  Truth Table \\n\n",
        "@  Conjunction(and) TTT, TFF, FTF, FFF\\n\n",
        "@  Disjunction(or) TTT, TFT, FTT, FFF \\n\n",
        "@  Conditional / if⟹ TTT, TFF, FTT, FFT \\n\n",
        "@  Biconditional/ iff <-> TTT, TFF FTF, FFT \\n\n",
        "@  a⊨β if and only if M(a) ⊆ M(β), which means every model in b is true, a should also be true \\n\n",
        "@  Inference algorithm: to emuerate the sentences by using entails and derive \\n\n",
        "@  Evaluate inference algorithm: soundness (only derive entailed sentences) and completeness (derive all entailed sentences) \\n\n",
        "@   \\n\n",
        "@  Logical equaivalent: if a and b have same set of models, in other words a ≡ β iff a⊨β and b⊨a \\n\n",
        "@  Rules: cheat sheet  \\n\n",
        "@  Monotonicity: we can add sentences to KB without invalid anything we inferred, because we are adding restrictions and make the possible worlds smaller. if KB⊨a then KB ⋀ β ⊨a \\n\n",
        "@  Proof search algorithm: 1. init knowledge base 2. apply inference rules to sentences 3. add new sentences to KB 4. if we find the goal sentence (1,1 is a pit) return True \\n\n",
        "@  Search algorithm soundness? yes, because we only add sentences, complete? yes, proof by resolution \\n\n",
        "@   \\n\n",
        "@  Resolution --> guarrenteen complete inference algorithm \\n\n",
        "@  Conjunctive Normal Form (CNF): all sentences in propositional logic can transform to conjunction of calusers  \\n\n",
        "@  Resolution algorithm: 1. convert (KB and -a) into CNF, 2. apply resolution rule to result clauses 3. Resolve every pair that contains complementary literals to produce a new clause\n",
        "• If that new clause isn’t already present, then add it to the set.\n",
        "• Continue the process until one of two things happens:\n",
        "1. There are no new clauses that can be added. In this case, the KB does not entail \n",
        "2. Two clauses resolve to yield the empty clause, in which case the KB does entail  \\n\n",
        "@  Definite clause: exactly one is positive -a or -b or c  \\n\n",
        "@ Horn clauses: at most one disjunction is positive: -a or -b or c (include definite clauses)  \\n\n",
        "@ Horn clauses are closed under resolution. apply resolution to a horn clause, return a horn clause.   \\n\n",
        "@   \\n\n",
        "@ Forward Chaining: data-driven reasoning An agent can begin with known data, adding premises as new percepts arrive, and then apply the forward chaining process progressively to generate new conclusions. It does not have to be motivated by a specific inquiry to do so.  \\n\n",
        "@ Backward chaining work backwards from a query. query correct then, no effort is required. Otherwise, the algorithm searches the KB for implications based on the query's conclusions. If all of the premises of one of those can be demonstrated to be true (through backward chaining), the inquiry is true.  \\n\n",
        "@   \\n\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 68,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "ac56d976-12b7-4ed6-e657-b9d664847250"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              "\n",
              "@  Knowledge based agent: reasoning over knowledge to act. Problem solving agent search over states to find plan and states are atomic \n",
              "\n",
              "@  Knowledge Base (representation language): Axioms --> given sentences, derived sentence --> inference from old sentences;  \n",
              "\n",
              "@  Logic defines semantic/ meaning of sentences, the semantics defines the truth of the world/model \n",
              "\n",
              "@  Models is fixed set of truth values for each sentences, M(a) means all the models that satisfies setence a \n",
              "\n",
              "@  Logical entailment \n",
              "\n",
              "@  a⊨β if and only if M(a) ⊆ M(β), a entails b --> a is specific/stronger than b, ex: b: he is a anima, a: he is a dog \n",
              "\n",
              "@  Possible worlds: find worlds that compatible with KB, M(KB) ⊆ M(a1 ) \n",
              "\n",
              "@  Logical inference: derive from logical entails, KB ⊢i a, a is derived from kb by i  \n",
              "\n",
              "@  Propostitional Logic: cheat sheet \n",
              "\n",
              "@  Truth Table \n",
              "\n",
              "@  Conjunction(and) TTT, TFF, FTF, FFF\n",
              "\n",
              "@  Disjunction(or) TTT, TFT, FTT, FFF \n",
              "\n",
              "@  Conditional / if⟹ TTT, TFF, FTT, FFT \n",
              "\n",
              "@  Biconditional/ iff <-> TTT, TFF FTF, FFT \n",
              "\n",
              "@  a⊨β if and only if M(a) ⊆ M(β), which means every model in b is true, a should also be true \n",
              "\n",
              "@  Inference algorithm: to emuerate the sentences by using entails and derive \n",
              "\n",
              "@  Evaluate inference algorithm: soundness (only derive entailed sentences) and completeness (derive all entailed sentences) \n",
              "\n",
              "@   \n",
              "\n",
              "@  Logical equaivalent: if a and b have same set of models, in other words a ≡ β iff a⊨β and b⊨a \n",
              "\n",
              "@  Rules: cheat sheet  \n",
              "\n",
              "@  Monotonicity: we can add sentences to KB without invalid anything we inferred, because we are adding restrictions and make the possible worlds smaller. if KB⊨a then KB ⋀ β ⊨a \n",
              "\n",
              "@  Proof search algorithm: 1. init knowledge base 2. apply inference rules to sentences 3. add new sentences to KB 4. if we find the goal sentence (1,1 is a pit) return True \n",
              "\n",
              "@  Search algorithm soundness? yes, because we only add sentences, complete? yes, proof by resolution \n",
              "\n",
              "@   \n",
              "\n",
              "@  Resolution --> guarrenteen complete inference algorithm \n",
              "\n",
              "@  Conjunctive Normal Form (CNF): all sentences in propositional logic can transform to conjunction of calusers  \n",
              "\n",
              "@  Resolution algorithm: 1. convert (KB and -a) into CNF, 2. apply resolution rule to result clauses 3. Resolve every pair that contains complementary literals to produce a new clause\n",
              "• If that new clause isn’t already present, then add it to the set.\n",
              "• Continue the process until one of two things happens:\n",
              "1. There are no new clauses that can be added. In this case, the KB does not entail \n",
              "2. Two clauses resolve to yield the empty clause, in which case the KB does entail  \n",
              "\n",
              "@  Definite clause: exactly one is positive -a or -b or c  \n",
              "\n",
              "@ Horn clauses: at most one disjunction is positive: -a or -b or c (include definite clauses)  \n",
              "\n",
              "@ Horn clauses are closed under resolution. apply resolution to a horn clause, return a horn clause.   \n",
              "\n",
              "@   \n",
              "\n",
              "@ Forward Chaining: data-driven reasoning An agent can begin with known data, adding premises as new percepts arrive, and then apply the forward chaining process progressively to generate new conclusions. It does not have to be motivated by a specific inquiry to do so.  \n",
              "\n",
              "@ Backward chaining work backwards from a query. query correct then, no effort is required. Otherwise, the algorithm searches the KB for implications based on the query's conclusions. If all of the premises of one of those can be demonstrated to be true (through backward chaining), the inquiry is true.  \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "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": 69,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "9a442105-2064-44de-ed88-485f36afc7b2"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Chapter 1.1 summary. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " \n",
              "Due to computational constraints, perfect rationality is impossible to achieve.\n",
              "Goal of rational agent: with a PEAS task environment, we have to create a agent function max expected value of performance measure  create a program that implement the function\n",
              "If an object has its own performance measure, we can consider it as agent\n",
              "\n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Agent** - anything that can perceive and act in an environment\n",
              "* **Percept** - perceptual input such as sensor input\n",
              "* **Agent program** - runs on architecture to produce a function\n",
              "* **Four views of artificial intelligence** - Thinking humanly, Thinking rationally, Acting humanly,Acting rationally \n",
              "* **Rational agent.** - Goal is to Maximize performance measure and rational != 100% success\n",
              "* **Task environments.** - Deffination of a whole problem\n",
              "* **Peas for task enviroments.** - Performance measure, enviroment, actuators, sensors\n",
              "* **Goal of rational gent design.** - GIVEN PEAS task, 1. create a function max performance measure, 2. design agent program\n",
              "* **Hardest environment** - 1. continuous, 2. partially observable, 3. stochastic 4. multiagent\n",
              "* **Etc.** - your definitions here\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "\n",
              "@ Structure: whitespace deliminited, use \\ to end line, indentation meaningful \n",
              "\n",
              "@ Objects and types: data is objects; strong typing: every object has a determined type and change do operations that limited on certain types such as \"foo\" + 2 is not allowed \n",
              "\n",
              "@  Static type (java): type is declared and can not change, dynamic typing (Python): type change change anytime and it will be updated, ex: x = \"abc\", then x = 1      \n",
              "\n",
              "@ String, tuple(cant be modified after created)immutable, list mutable, y = x[:] create shallow copy. == check values same, \"is\" check object address same \n",
              "\n",
              "@ List operation:  t[1:-1:n] selection of every nth item , t[0:-1]. does a copy of ori list, a.index('c') index of first occurrence of c, a.remove('a') also remove first occurrence \n",
              "\n",
              "@ String operation: split(), \" \".join(word_list), captitalize(), upper() --> make everything upper case, strip('.') --> remove front and end . \n",
              "\n",
              "@ Dic: defaultdict initialize dict for empty keys, keys(), values(), items(), Set: create set() or {}, add(), remove() error if not exist, pop() remove random. \n",
              "\n",
              "@ Python no function overloading, function name unique, but operator can overload inside a class \n",
              "\n",
              "@ '*'args, function('*'args): print(args) , then, function(1,2,3) --> return (1,2,3), lst = [1,2,3], function('*'lst) --> return (1,2,3)   \n",
              "\n",
              "@ '**'kwargs, function('**kwargs'): print(kwargs), then, function(a=1, b=2) ---> return {a:1,b:2}, dict={a:1, b:2}, function('**dict') --> return {a:1, b:2}  \n",
              "\n",
              "@ Global scope, def function(x) return x + i, i is the global variable, will be updated  \n",
              "\n",
              "@ Sub Class: class Dog(Animal): def _init(self, name): Animal._init_(self,name), use parent's init function \n",
              "\n",
              "@ Function as input: def compose(f,g,x):return f(g(x)), compose(str, sum, [5,5]) --> return \"10\" \n",
              "\n",
              "@ Class overwrite method: def show(self): Animal.show(self), additional lines of function \n",
              "\n",
              "@ Super() class: inherit from multiple parent, can be confusing if parents have same function name \n",
              "\n",
              "@ if __name__ == '__main__': , run this first for any python scripts \n",
              "\n",
              "@ Duck Typing: def lift_off(entity): entity.fly() , lift_off(duck), or lift_off(plane), automaticly determine the output \n",
              "\n",
              "@ List: list(range(5)) , [a+1 for a in list if a == 5] \n",
              "\n",
              "@ Iterator: iterable object has _iter_() method --> convert to iterator , iter([a,b,c]) --> iterator object, these objects have next() method, [a,b,c]._iter_().next() = a. For loop will make a list into a iterator and keep calling next(), and wait till stopiteration exception \n",
              "\n",
              "@ Generator: iterator uses less memory， def function(i): yield i , type(function(1)) --> generator, [i for i in function(5)]  \n",
              "\n",
              "@ Generator Benefit: less code, keep local state auto, not store all in memory because compute once at time, good for infinite sequence. Cons: cant see each individual value \n",
              "\n",
              "@ Importlib good for reloading from file \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - String immutable, list mutable, y = x[:] create shallow copy\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " Your summary here \n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "@ Reflex Agents: ignore history, make decision on the current percept, vs problem solving agent which plan ahead, it will consider a sequence of actions to the goal \n",
              "\n",
              "@  Fully observable, determinsitic, known env --> fixed solution, partially observable, non deterministic --> branching strategy, not determined \n",
              "\n",
              "@  Defination of search problems: 1. states, actions, transition model that create successors, path cost (performance measure), goal test \n",
              "\n",
              "@  Steps to form a search problem: 1. How to represent states, inital and goal 2. Represent Action, action and transition model 3. Path Cost, performance measure.  \n",
              "\n",
              "@  Search problem is an abstract of real world, easier than real problem \n",
              "\n",
              "@   \n",
              "\n",
              "@. To define search problem: State space, Initial state, Goal states, Actions, Transition model, Action cost function \n",
              "\n",
              "@  Basic search algorithm: Tree search. Root is start state, nodes is output of transition model, different paths to the same node is distinct.  \n",
              "\n",
              "@  Node class contains state or matrix, parent, children, action, cost, depth \n",
              "\n",
              "@  Repeated states: cycles --> make the linear problem to exponential \n",
              "\n",
              "@  Graph search vs tree search: graph search checks if the node visited before, graph search faster and uses more space \n",
              "\n",
              "@  Uninformed search : all non-goal nodes equally good. Informed search: some node better than others \n",
              "\n",
              "@  A search method is uninformed if only has access to the problem definition \n",
              "\n",
              "@   \n",
              "\n",
              "@  Search Strategies: evaluation metric: 1. completeness --> find solution or not 2. optimal solution? 3. time complexity 4. space complexity \n",
              "\n",
              "@  d = depth, b = max branching factor, m = max length of solution (goes to inf) \n",
              "\n",
              "@  Different strategy have different queue structures (LIFO, FIFO, priority) \n",
              "\n",
              "@   \n",
              "\n",
              "@  BFS --- FIFO Queue, successor goes to the end of the queue \n",
              "\n",
              "   def bfs:     \n",
              "\n",
              "       if initial_state == goal: return initial_state \n",
              "\n",
              "       frontier_fifo_queue = Queue() \n",
              "\n",
              "       visited = {inital_state} \n",
              "\n",
              "       parent = {} \n",
              "\n",
              "       cost = {} \n",
              "\n",
              "       while frontier_fifo_queue is not empty:\n",
              "\n",
              "            current_node = frontier.pop() \n",
              "\n",
              "            for each child in expand(current_node):  \n",
              "\n",
              "              if child == goal: return child \n",
              "\n",
              "              if child not in visited: \n",
              "\n",
              "                  visited.add(current_node) \n",
              "\n",
              "                  frontier.add(child) \n",
              "\n",
              "        return can't find answer -- > failed \n",
              "\n",
              "        \n",
              "\n",
              "    def expand(node):     \n",
              "\n",
              "       for each action in Actions(node): \n",
              "\n",
              "          new_state, action_cost = take_action(action)\n",
              "          cost = parent_node_cost + action_cost\n",
              "          yield new Node(state=new state, parent=node, action=action, path_cost = cost)\n",
              "\n",
              "@   \n",
              "\n",
              "@  DFS --- LIFO Queue, successor goes to the front of the queue \n",
              "\n",
              "\n",
              "@  Compare DFS and BFS \n",
              "\n",
              "    BFS pro: complete -- will always find answer, optimal -- find the best answer\n",
              "        con: space complexity high, need to save all the nodes travelled\n",
              "    DFS pro: save space, only keep b*m nodes\n",
              "        cons: not complete when path is inf, not optimal, use b^m time, bad if m much bigger than d\n",
              "@   When to use dfs: if space is not enough, wrong paths are not inf, so end quicker, or if solutions path are long \n",
              "\n",
              "@   When to use bfs: if there are inf paths, bfs will avoid them, solution paths are shorter than average \n",
              "\n",
              "@   \n",
              "\n",
              "@   Depth-limited search: DFS but stop at a certain depth, not optimal, not complete \n",
              "\n",
              "@   Iterative deepening search: To improve depth limited search, we can use for loop to increase depth limit from 0 to inf \n",
              "\n",
              "    for depth_limit from 0 to inf:\n",
              "      depth_limit_search(depth_limit)\n",
              "      if find answer:\n",
              "        return solution\n",
              "        # else keep going and increase depth limit\n",
              "@   IDS: Complete and optimal, as efficient as BFS \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **State** - which object in which cell, the matrix\n",
              "* **State space** - all states can be reached from start state\n",
              "* **Path** - sequence of actions from state a to b\n",
              "* **Solution** - sequence of actions to goal, list of actions\n",
              "* **Search tree** - root = start state, leaves are successor state\n",
              "* **Frontier** - states that can expand, have next steps (queue)\n",
              "* **Optimal solution** - lowest cost solution\n",
              "* **Asdfasdf** - asdfasdfasdf\n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Lecture Notes\n",
              "\n",
              "@  Uniformed Search: assume all moves have equal cost, ex: each move 1 cost \n",
              "\n",
              "@  It's the extension of BFS, it expand node with lowest path cost, it has a priority queue to store the cost of current path \n",
              "\n",
              "@  Check if goal, when selected for expansion (right after while loop, after pop), not when enqueue, because if check during enqueue, we could potentially miss the better solution \n",
              "\n",
              "@  Uniformed search node expansion based on lowest path cost \n",
              "\n",
              "@  BFS based on shallowest node \n",
              "\n",
              "@  DFS based on deepest node \n",
              "\n",
              "@  To improve on Uniformed search, introduce Best First Search, expansion with min evaluation function \n",
              "\n",
              "@  There are two instance of Best First Search, Greedy Best first search and A star \n",
              "\n",
              "@  Greedy only consider the estimation, expansion based on estimation that closest to goal \n",
              "\n",
              "@  def greedy best-first search: \n",
              "\n",
              "      frontier = PriorityQueue() \n",
              "\n",
              "      frontier.put(start, 0) \n",
              "\n",
              "      came_from[start] = None \n",
              "\n",
              "      while not frontier.empty(): \n",
              "\n",
              "          current = frontier.get() \n",
              "\n",
              "          if current == goal: \n",
              "\n",
              "            break \n",
              "\n",
              "          for next in successors(current): \n",
              "\n",
              "            if next not in came_from: \n",
              "\n",
              "              priority = heuristic(goal, next) \n",
              "\n",
              "              # distance from next node to goal \n",
              "\n",
              "              frontier.put(next, priority) \n",
              "\n",
              "              came_from[next] = current \n",
              "\n",
              "@ greedy, complete? no, can stuck in loops, optimal, no, can be tricked by direct line distance  \n",
              "\n",
              "@   \n",
              "\n",
              "@ A star search --> best-known form of best-first search, expand most promising first, avoid expanding expensive paths \n",
              "\n",
              "@ Combine g(n) the real cost so far + h(n) estimated cost from next to goal  \n",
              "\n",
              "@ Difference with greedy, priority = heuristic(goal, next) + current_cost  \n",
              "\n",
              "@ Admissibility:   \n",
              "\n",
              "  admissible: never over estimate the cost to goal, --> optimistic, slow down bad plans --> optimal\n",
              "  inadmissible: can overestimate, thus trap good plans --> pessimistic\n",
              "@ Relaxed problem: less restrictions on actions than original problem  \n",
              "\n",
              "@ Cost of the relaxed problem is admissible heuristic for original problem \n",
              "\n",
              "@ Determine a good heuristic: h(n) that closest to the orignal problem is the best heuristic, but can have higher cost  \n",
              "\n",
              "@ Bad heuristics: return 0 --> same as uniformed search  \n",
              "\n",
              "@ Uninformed search only have access to problem definition vs. informed search have access to both problem definition and heuristic function  \n",
              "\n",
              "@ A star problem: space complexity too high  \n",
              "\n",
              "@ To improve this, iterative-deepening A star: use total_cost g(n) + h(n) as cut off, start with the cost 0 as threshold, run A star until find a cost greater than the threshold, then break and update the threshold to the new cost. Keep increasing threshold until find solution \n",
              "\n",
              "@ Problem with IDA or RBFS (recursive best first search) is that they use too little memory, they forget most of things, so they revisit nodes over and over again \n",
              "\n",
              "@ To improve this, MA star (memory bound A star) and SMA star, which expan nodes and save to memory until memory full, so next iteration, it will just use the memory to construct the tree, like Dynamic Programming  \n",
              "\n",
              "@ IDA, SMA, RBFS are optimal, and more space efficient than A star (dont need to save everything in memory)  \n",
              "\n",
              "@ Beam search limits the size of frontier, but it is not optimal, not complete, why use it? run faster than complete searches  \n",
              "\n",
              "@ Weighted a star: f(n) = g(n) + weight x h(n), not optimal, yes complete, why use? expands fewer nodes  \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              "\n",
              "\n",
              "@ Simplest game environment: multiagent, static (no change when agent move), discrete (finite set of actions and percepts), fully observable (see everything, perfect information), strategic (new state = current state * action by a * action by b)  \n",
              "\n",
              "@ Our game: two players, zero sum(win or lose), set of legal moves, defined results (w,l, draw)  \n",
              "\n",
              "@ Form a game: Max and Min, Max goes first, they then take turns. 1. start state (matrix config) 2. sucessor function, 3. goal test 4. utility function (performance measure, int value for outcomes, w, l , draw)  \n",
              "\n",
              "@ Game Tree: node --> board position, matrix, edges --> actions, legal moves, root --> inital state  \n",
              "\n",
              "@   \n",
              "\n",
              "@ Adversarial Search: all cost from Max's vantage point, Max --> maximize max's result, Min --> minimize max's result \n",
              "\n",
              "@ Max action on Even levels (level 0 starts), Min action on Odd levels  \n",
              "\n",
              "@ Evaluation function(board position) ---> score, without referring to path. Terminal nodes --> ending of the game (With label W, L ,D)  \n",
              "\n",
              "@ Evaluation function: evalues board position (without knowning history), we can measure because the board is static, and zero sum (we can use 1 function to evaluate for two players). f(n) > 0 if Max is in advantage. For example, tic-tac-toe: f(n) = number of opening position for MAX - number of opening position for MIN  \n",
              "\n",
              "@   \n",
              "\n",
              "@ The Minimax Rule: max and min will choose best value move, best for Max --> max value of Max's children, best for Min --> min value of Min's children  \n",
              "\n",
              "@ def max-value(state):  \n",
              "\n",
              "  if the state == terminal state (win or lose or draw): \n",
              "\n",
              "      return state utility \n",
              "\n",
              "  init value = -inf \n",
              "\n",
              "  for successor of state: \n",
              "\n",
              "    value = max(value, min-value(successor)) \n",
              "\n",
              "  return value \n",
              "\n",
              "  \n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@ def min-value(state):  \n",
              "\n",
              "  if the state == terminal state (win or lose or draw): \n",
              "\n",
              "      return state utility \n",
              "\n",
              "  init value = inf \n",
              "\n",
              "  for successor of state: \n",
              "\n",
              "    value = min(value, max-value(successor)) \n",
              "\n",
              "  return value \n",
              "\n",
              "@   \n",
              "\n",
              "@ min does not play optimally? Max will do better always  \n",
              "\n",
              "@   \n",
              "\n",
              "@  Alpha-Beta Pruning \n",
              "\n",
              "@  α = MAX's current min value on its outcome, β: min's current max value on its outcome \n",
              "\n",
              "@  Max will not select min node that value < α, Min will not select max node that value >= β  \n",
              "\n",
              "@   \n",
              "\n",
              "@ def max-value_alpha_beta(state):  \n",
              "\n",
              "  if the state == terminal state (win or lose or draw): \n",
              "\n",
              "      return state utility \n",
              "\n",
              "  init value = -inf \n",
              "\n",
              "  for successor of state: \n",
              "\n",
              "    value = max(value, min-value(successor)) \n",
              "\n",
              "    alpha = MAX(alpha, value) \n",
              "\n",
              "    if value >= beta: \n",
              " \n",
              "      then return value  \n",
              " \n",
              "  return value \n",
              "\n",
              "\n",
              "    # beta is the smallest value, min will choose, \n",
              "    # if value >= beta, that means min will no choose this branch,\n",
              "    # thus no need to go further /n\n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "@ def min-value_alpha_beta(state):  \n",
              "\n",
              "  if the state == terminal state (win or lose or draw): \n",
              "\n",
              "      return state utility \n",
              "\n",
              "  init value = inf \n",
              "\n",
              "  for successor of state: \n",
              "\n",
              "    value = min(value, max-value(successor)) \n",
              "\n",
              "    beta = Min(beta, value) \n",
              "\n",
              "    if value <= alpha: \n",
              " \n",
              "      then return value  \n",
              " \n",
              "  return value \n",
              "\n",
              "\n",
              "    # alpha is the largest value, max will choose, \n",
              "    # if value <= alpha, that means max will no choose this branch,\n",
              "    # thus no need to go further /n\n",
              "@   \n",
              "\n",
              "@  Expectimax Search \n",
              "\n",
              "@  When we dont know the outcome, ex: rolling dice. Value of action are now average value \n",
              "\n",
              "@  Expectimax search: find average score under optimal decision, Max are still max, min becomes chance node \n",
              "\n",
              "@   \n",
              "\n",
              "@  def value(state): \n",
              "\n",
              "      if state == terminal state: return state utility \n",
              "\n",
              "      if next_level is MAX (even level): return max_value(state) \n",
              "\n",
              "      if next_level is EXP (odd level): return expect_value(state) \n",
              "\n",
              "\n",
              "@   \n",
              "\n",
              "@  def max_value(state): \n",
              "\n",
              "      init v = -inf \n",
              "\n",
              "      for successor of state: \n",
              "\n",
              "          v = max(v, value(successor)) \n",
              "\n",
              "      return v \n",
              "\n",
              "@   \n",
              "\n",
              "@  def exp_value(state): \n",
              "\n",
              "      init v = 0 \n",
              "\n",
              "      for successor of state: \n",
              "\n",
              "        p = probality(successor) \n",
              "\n",
              "        v = v + p * value(successor) \n",
              "\n",
              "      return v \n",
              "\n",
              "@   \n",
              "\n",
              "@ Probability  \n",
              "\n",
              "@ random variable: an event with unknow outcome  \n",
              "\n",
              "@  probaility distribution is assignment of weights to outcomes or possiblity for each outcome in the event \n",
              "\n",
              "@  probality all sum to 1, all positive \n",
              "\n",
              "@   \n",
              "\n",
              "@ objectivist/ frequentist: probability is average over repeated experiments, rolling dice for 1000 times and find average  \n",
              "\n",
              "@ Subjectivist / Bayesian : degrees of belif about unobserved variables, an experts belieft on how things will be  \n",
              "\n",
              "@   \n",
              "\n",
              "@ Expectiminmax: another random agent, play in between max and min  \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@ Facts to know  \n",
              "\n",
              "\n",
              "@  Games vs search problems: games have multiple agents \n",
              "\n",
              "@  Perfect information = fully observable \n",
              "\n",
              "@  Untility function --> determine terminal state payoff \n",
              "\n",
              "@  Minimax same order as DFS, always the deepest first \n",
              "\n",
              "@  Minimax time complexity = b^m   same as DFS \n",
              "\n",
              "@  Running time of alpha beta impact by the order we examine nodes, because if we always find worst successor first, we have to keep going, just like min max game search \n",
              "\n",
              "@  Alpha-beta time complexity = b^0.5m \n",
              "\n",
              "@  Type A strategy exlores wide but shallow part of the tree \n",
              "\n",
              "@  Type B deep but narrow \n",
              "\n",
              "@  If the game is too big, we have to choose between A and B, because cant search every node \n",
              "\n",
              "@  Heuristic alpha beta use evaluation function instead of utililty function, it also evaluate the non-terminal nodes. It uses cutoff test instead of terminal test. It will cut off the game early. Evaluation on quiescent positions only (position without any big changes for next step) \n",
              "\n",
              "@  Horizon effect: when agent try to delay the inevitable (dead game) \n",
              "\n",
              "@  Forward pruning (Type B strategy) --> bad moves (Ex: beam search) \n",
              "\n",
              "@  MCTS (monte carlo tree search) ---> random selecting moves --> evaluate the state by playing randomly at the state and find the average value\n",
              "\n",
              "@  Define a game: 1. time for player to make a move 2. terminal states 3. set of legal moves can make 4. utility function 5. initial state \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " Your summary here \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",
              "\n",
              "\n",
              "@ Search problem: 1 agent (game problems have more), deterministic actions, fully observable (perfect information), discrete state space (finite)  \n",
              "\n",
              "@ Two types of search problems: planning --> BFS, DFS, sequence is important, identification: variable assignment --> path doesnt matter, Constraints satisfaction problems \n",
              "\n",
              "@ Constraints satisfaction problem: represent constrainst in uniform declarative leanguage that the algorithm should work on all problems  \n",
              "\n",
              "@ CSP consists: 1. finite set of variables 2. set of possible values for each varaible 3. set of constraints ex: variable x1 != variable x2  \n",
              "\n",
              "@ CSP is done when all variables have a value, outcome should be compelete and consistent  \n",
              "\n",
              "@ CSP pros: generic, eliminate branch violate constraints, can tell which one violate constraint easily  \n",
              "\n",
              "@ Representation: graph, node --> variable, arc/edge --> constraints  \n",
              "\n",
              "@ Different kinds of CSP: discrete variables (finite domain and infinite domain) , continuous variables (time)  \n",
              "\n",
              "@ Different kinds of constraints: unary --> a!= pig, binary --> x1 != x2, higher-oder --> sudoku, preference/soft constraints --> a better than c, represent by cost  \n",
              "\n",
              "@   \n",
              "\n",
              "@ Solve CSP problem: 1. As search problem (DFS/ backtracking), 2. Improve on backtracking, choose assgined variable (a. most constrained b. most constraining c. least contraining d. forward checking)  3. inference \n",
              "\n",
              "@ Idea 1: search problem  (Backtracking/ Uninformed DFS) \n",
              "\n",
              "@ Each depth is a variable, width is number of values tried for this variable  \n",
              "\n",
              "@   \n",
              "\n",
              "@ Form problem: 1. init state, empty assignment 2. successor function: assgin values without conflict 3. if == goal, commplete 4. path cost: step cost  \n",
              "\n",
              "@ Solution always in depth n for n variable, ex: map problem, depth always = number of variables  \n",
              "\n",
              "@ n number variables, d = number domain of values, branching factor at root = n * d, next level = (n-1) * d , number of leaves n! * d^n  \n",
              "\n",
              "@ It's a tree search not a graph search, beacuse variable assignments are communtative, and the number of leaves can reduce to d^n because commutative  \n",
              "\n",
              "@ Back tracking means use DFS to assign one values for one variable at a time and return when no values to assign  \n",
              "\n",
              "@   \n",
              "\n",
              "@ Idea 2: improve backtracking (add Heuristic function)  \n",
              "\n",
              "@ Which variable assign first: a. most constrained variable (MRV, variable with fewer legal values) b. to break tie for a, most constraining variable (degree heuristic: variable that affets neighbors the most) \n",
              "\n",
              "@ How to try values:  least constraining values (value that reduce fewer options for neighbors) \n",
              "\n",
              "@ How to detect failure early: forward checking --> keep track remaining values for all variables, if a variable has no values left, it means failed, so break early  \n",
              "\n",
              "@ Drawck for forward checking: only consider empty variables, doesnt detect all failures such as (A and B are all red on the map)  \n",
              "\n",
              "@   \n",
              "\n",
              "@ To improve  \n",
              "\n",
              "@ Idea 3: Inference (Constraint propagation)  \n",
              "\n",
              "@ Steps now: 1. Search, assign value to a variable 2. Constraint propagation: eliminiate illegal values for all variables  \n",
              "\n",
              "@ Consistency: node --> unary constraint, arc --> binary cons  \n",
              "\n",
              "@ Arc cons: X to Y is consistent if and only every value x of X there is some allowed y  \n",
              "\n",
              "@ Waltz/Mackworth Algorithm:  \n",
              "\n",
              "    assign all variable a set of possible values,  for example: sudoku (1,1) {1,2,3,5} \n",
              "\n",
              "    while still changes in the matrix: \n",
              "\n",
              "      for each node i :  \n",
              "\n",
              "          for each of its neightbors j : \n",
              "\n",
              "            remove illegal values from i set based j set (set i - set j). \n",
              "\n",
              "@ Problems: inefficient, 1. no need to check all nodes, just check affected, only these neighbors of node i that have conflict with i (push neighbors into queue if conflict); 2. if x and y have conflict, push all neighbors of x, except y 3. Removing a value from Xi can only cause Yj to be inconsistent with regard to Xi. --> just ensure that (j,i) arc-consistent.   \n",
              "\n",
              "@   \n",
              "\n",
              "@ To improve: ---> AC-3  \n",
              "\n",
              "\n",
              "'''\n",
              "\n",
              "    def remove_inconsistent_values(self, cell1, cell2):\n",
              "        if (cell1,cell2) in self.ARCS:\n",
              "            if len(self.board[cell2]) == 1:\n",
              "                if self.board[cell2].issubset(self.board[cell1]):\n",
              "                    self.board[cell1] = self.board[cell1] - self.board[cell2]\n",
              "                    return True\n",
              "        return False\n",
              "\n",
              "\n",
              "    def infer_ac3(self):\n",
              "        q = Queue()\n",
              "        for arc in self.ARCS:\n",
              "            q.put(arc)\n",
              "        while q.empty() == False:\n",
              "            arc = q.get()\n",
              "            if self.remove_inconsistent_values(arc[0],arc[1]):\n",
              "                for other_arcs in self.ARCS:\n",
              "                    if arc[0] == other_arcs[1]:\n",
              "                        q.put(other_arcs)\n",
              "'''\n",
              "@   \n",
              "\n",
              "@ All nodes can connect to others, total number of arcs = 2*n*(n-1), O(n^2), n = number of variables  \n",
              "\n",
              "@ d values, check arc(i,j) takes O(d^2), each arc can be in queue d times  \n",
              "\n",
              "@ Worst complexity O(n^2 d^3), planar graphs, num arcs is linear, so complexity is O(nd^3)  \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@ Facts  \n",
              "\n",
              "@ CSP represent a state with a set of variable value pairs  \n",
              "\n",
              "@ CSPs represent the conditions for a solution with a set of constraints on the variables\n",
              "\n",
              "@ CSP vs search problem: serach problem states are unseen, need to move using transition model, but CSP we can see inside states  \n",
              "\n",
              "@ CSP has 2 ways ruling out variable assignment: 1. search: generate successors (like search problem) or 2: inference, constraints propagation \n",
              "\n",
              "@ The key idea behind inference in CSPs is enforcing k consistency  \n",
              "\n",
              "@ Node consistency is k-consistency for k = 1, arc consistency is k = 2, path is k = 3 \n",
              "\n",
              "@ AC-3 is algorithm for arc consistency, so it cant solve all CSP, only k = 2  \n",
              "\n",
              "@ Backtracking starts when no legal assignment found  \n",
              "\n",
              "@ Constraint learning records conflicts found in search to avoid later  \n",
              "\n",
              "@ Solve arbitray CSP --> exponential to the num of variables \n",
              "\n",
              "@ Tree CSP take linear time to num of variables, planar graphs as well \n",
              "\n",
              "@ Cutest conditioning used to reduce CSP to tree structure, but it only works if found small cutset, no always better  \n",
              "\n",
              "@ Tree decomposition --> CSP to tree of subproblems, only work if width of tree of contraint graph is small  \n",
              "\n",
              "@ Tree decomp time efficent than Cutset, but cutset better space efficient \n",
              "\n",
              "@ MAC --> maintain arc consistency  \n",
              "\n",
              "@ MAC vs AC-3: mac assign variable in backtracking search, not enqueue all arcs, only enqueue arc on assgineed variables (AC3 enqueue all arc at beginning) \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              "\n",
              "@  Knowledge based agent: reasoning over knowledge to act. Problem solving agent search over states to find plan and states are atomic \n",
              "\n",
              "@  Knowledge Base (representation language): Axioms --> given sentences, derived sentence --> inference from old sentences;  \n",
              "\n",
              "@  Logic defines semantic/ meaning of sentences, the semantics defines the truth of the world/model \n",
              "\n",
              "@  Models is fixed set of truth values for each sentences, M(a) means all the models that satisfies setence a \n",
              "\n",
              "@  Logical entailment \n",
              "\n",
              "@  a⊨β if and only if M(a) ⊆ M(β), a entails b --> a is specific/stronger than b, ex: b: he is a anima, a: he is a dog \n",
              "\n",
              "@  Possible worlds: find worlds that compatible with KB, M(KB) ⊆ M(a1 ) \n",
              "\n",
              "@  Logical inference: derive from logical entails, KB ⊢i a, a is derived from kb by i  \n",
              "\n",
              "@  Propostitional Logic: cheat sheet \n",
              "\n",
              "@  Truth Table \n",
              "\n",
              "@  Conjunction(and) TTT, TFF, FTF, FFF\n",
              "\n",
              "@  Disjunction(or) TTT, TFT, FTT, FFF \n",
              "\n",
              "@  Conditional / if⟹ TTT, TFF, FTT, FFT \n",
              "\n",
              "@  Biconditional/ iff <-> TTT, TFF FTF, FFT \n",
              "\n",
              "@  a⊨β if and only if M(a) ⊆ M(β), which means every model in b is true, a should also be true \n",
              "\n",
              "@  Inference algorithm: to emuerate the sentences by using entails and derive \n",
              "\n",
              "@  Evaluate inference algorithm: soundness (only derive entailed sentences) and completeness (derive all entailed sentences) \n",
              "\n",
              "@   \n",
              "\n",
              "@  Logical equaivalent: if a and b have same set of models, in other words a ≡ β iff a⊨β and b⊨a \n",
              "\n",
              "@  Rules: cheat sheet  \n",
              "\n",
              "@  Monotonicity: we can add sentences to KB without invalid anything we inferred, because we are adding restrictions and make the possible worlds smaller. if KB⊨a then KB ⋀ β ⊨a \n",
              "\n",
              "@  Proof search algorithm: 1. init knowledge base 2. apply inference rules to sentences 3. add new sentences to KB 4. if we find the goal sentence (1,1 is a pit) return True \n",
              "\n",
              "@  Search algorithm soundness? yes, because we only add sentences, complete? yes, proof by resolution \n",
              "\n",
              "@   \n",
              "\n",
              "@  Resolution --> guarrenteen complete inference algorithm \n",
              "\n",
              "@  Conjunctive Normal Form (CNF): all sentences in propositional logic can transform to conjunction of calusers  \n",
              "\n",
              "@  Resolution algorithm: 1. convert (KB and -a) into CNF, 2. apply resolution rule to result clauses 3. Resolve every pair that contains complementary literals to produce a new clause\n",
              "• If that new clause isn’t already present, then add it to the set.\n",
              "• Continue the process until one of two things happens:\n",
              "1. There are no new clauses that can be added. In this case, the KB does not entail \n",
              "2. Two clauses resolve to yield the empty clause, in which case the KB does entail  \n",
              "\n",
              "@  Definite clause: exactly one is positive -a or -b or c  \n",
              "\n",
              "@ Horn clauses: at most one disjunction is positive: -a or -b or c (include definite clauses)  \n",
              "\n",
              "@ Horn clauses are closed under resolution. apply resolution to a horn clause, return a horn clause.   \n",
              "\n",
              "@   \n",
              "\n",
              "@ Forward Chaining: data-driven reasoning An agent can begin with known data, adding premises as new percepts arrive, and then apply the forward chaining process progressively to generate new conclusions. It does not have to be motivated by a specific inquiry to do so.  \n",
              "\n",
              "@ Backward chaining work backwards from a query. query correct then, no effort is required. Otherwise, the algorithm searches the KB for implications based on the query's conclusions. If all of the premises of one of those can be demonstrated to be true (through backward chaining), the inquiry is true.  \n",
              "\n",
              "@   \n",
              "\n",
              "\n",
              "\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 69,
      "metadata": {
        "id": "UsPiGslOyPi8"
      },
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
