{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "beeaebe2-cb5d-4a18-ecb5-e143ba620820"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0451f03e-791c-4a42-b02c-c5761bdddae1"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" \n",
        "Some prefer to define AI as rationality/right thing, or human vs rational. This study invloves math, engineerm statm and economics.\\\n",
        "Some define AI as fidelity of human performance, or thought vs behavior.This study invloves psychological observation and hypothesis on human behavior and thought process.\\ \n",
        "Turing test approach to test robot acticing humanly: can a robot think and pass the test of a human interrogator. \\\n",
        "Robot needs NLP, knowdledge representation, automated reasoning, ML.\\\n",
        "Real Turing test: require interaction with objects and people, robot needs CV and robotics. \\\n",
        "Cognitive modeling approach to test thinking humanly: learn human though through introspection, psychological experiments, brain imaging. See if a program input out put behavior matches human.\\\n",
        "Laws of thought approach tests thinking rationally through verifying correct logical inferences \\\n",
        "Rational agent approach tests acting rationally. This test is more general than the laws of thoughts\\\n",
        "It is also more amenable to scientific development. Rationality is math defined. Perfect rationality is not feasible when computational demand is high.\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" \n",
        "Turing's \"argument from informality of behavior\" says human behavior is too complex to be captured. Good old-Fashioned AI (GOFAI) is the simplest logical agent that cannot capture every rule.\\\n",
        "The argument from disbility claims a machine can never do X. Computers outperform human in some tasks and lag for the others, but it cannot be exactly human.\\\n",
        "The mathematical objection proves that some math questions are not answerable by formal systems. JR Lucas thinks machines are limited by this, so they are inferior to human\\\n",
        "Measuring AI by performance on some behaviorial task is the key point of his test.\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\"\n",
        "Philosophers claim machines are not actually thinking but simulating thinking. Turing notes there is no direct evidence about human mental states. \\\n",
        "So we should say everyone thinks including intelligent machines.\\\n",
        "John Searle rejects the polite convention through Chinese room argument, computers generate no understanding. \\\n",
        "All debates focuses on consciousness/qualia which is the awareness of outself word, self, and living. Turing thinks making machine human like concious is not the focus.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "This section talks about agent and environment. \\\n",
        "Human agents has eyes, hands, etc. A robotic agent has camera or motors for actuators. Software agent receives files, input. Environment is what agent perceives and affected by agent actions.\n",
        "The agent action depends on its built in knowledge and percept sequence from past to date, not on anything it has not perceived future percept. \n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "This section talks about rationality. Human evaluate agents by it's performance consequence from human's point of view. \\\n",
        "Rationality depends on the performance meaure that definesthe criterion of success, the agent's prior knowledge of the environment, the agent actions, and percept sequence.\\\n",
        "The difference between omniscience and rational is that an omniscient agent knows the actual outcome of its actions and maximize actual performance\\\n",
        "whereas rationality maximize expected outcome. We don't expect rational agent to be omniscient, but it should do information gathering, doing actions to modify future percepts\\\n",
        "and even be automomy and learn from its percepts.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "This section talks about task environment which is described by PEAS(Performance measure, Environment, Actuators, Sensors) and needs to be specified first when designing an agent\\\n",
        "Task environment is fully observable if the sensors have accoess to the complete state of the environment.\\\n",
        "Multi agent game can be either competitive or cooperative.\\\n",
        "If the next state of the enironment is fully depends on the current state and agent's action, the environment is determinstic.\n",
        "An example of non-determinstic environment is taxi driving because traffic is random. \\\n",
        "Stochastic is different because it's not 100% random, it deals with probabilities.\\\n",
        "In sequential environment, the current decision could affect future decisions, but in episodic task environment it would not.\\\n",
        "In dynamic environment, it can change when agent is making decision, static environment will not.\n",
        "In known enviroument, the agent will know the outcome of all its actions.\n",
        "\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" \n",
        "This section talks about the structure of agents. The job of AI is to design an agent program that implements the agent function. agent = architecture+program\\\n",
        "The agent programs in this class all take the current percept as input from sensors and return an action to actuators. The agent function may depend on the entire percept history.\\\n",
        "The challenge of AI is to produce rational behavior from a small program rather than a big table.\\\n",
        "There are 4 integlligent systems:\\\n",
        "Simple reflex agents: select actions based on current percept, not from history, only works in fully observable environment\\\n",
        "Model-based reflex agents: handle partial observable environment and keeps track of the part of world where it cannot see. Need to track transition model and sersor model\\\n",
        "Goal-based agents:needs a particular goal or destination\\\n",
        "Utility-based agebts: can assign a utility function to agent's performance measure, the agent will act to maximize its expected utility\\\n",
        "\\\n",
        "This section then discusses learning agent which can be divided into four components: \\\n",
        "learning element which makes improvement\\\n",
        "performance elememnt which select external actions\\\n",
        "critic which measures performance standard and tells learning element how well the agent is doing\\\n",
        "problem generator which suggestion actions that will lead to new and infromative experience.\\\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "There are four views of defining AI: thinking humanly, acting humanly, thinking rationally, acting rationally (rational agents). \\\n",
        "agent is composed of architecture and program. To make sure agent acts rationally we define performance measure for them.\\\n",
        "When designing performance measure we should keep it to what we want to be achieved, not we think how agent should behave.\\\n",
        "Rational agent will only select an optioan 'a' for each option 'p' to maximize expected value of performance measure, but not actual performance.\\\n",
        "To desgin a rational agentm we need to specify task environment and construct agent function that maximize the expected value of the performance\\\n",
        "and design an agent program that implements the agent function.\\\n",
        "There are also different type of agents. Reflex agent only selects action based on current percept, but problem solving agent will plan ahead and search for actions from path to goal state.\\\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",
        "\"introspection\": \"record personal thoughts\",\n",
        "\"psychological experiements\": \"observe people's actions\",\n",
        "\"brain imaging\": \"observe brain's actions\",\n",
        "\"agent\" : \"anything that can perceive and act in an environment through sensors and actuators\",\n",
        "\"rational agent\":\"agent who acts to achieve the optimal/best outcome and maximize expected performance measure\",\n",
        "\"weak AI\": \"machine can act as if it is intelligent\",\n",
        "\"string AI\":\"machine is thinking\",\n",
        "\"percept\" : \"stuff received by sensors\",\n",
        "\"percept sequence\":\"all historical percept\",\n",
        "\"agent function\": \"percept sequence -> action, or f:p->a in math\",\n",
        "\"agemnt program\":\"implements agent function\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "631b435f-e61f-42ff-f058-244f76006a21"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nSome prefer to define AI as rationality/right thing, or human vs rational. This study invloves math, engineerm statm and economics.Some define AI as fidelity of human performance, or thought vs behavior.This study invloves psychological observation and hypothesis on human behavior and thought process.\\ \nTuring test approach to test robot acticing humanly: can a robot think and pass the test of a human interrogator. Robot needs NLP, knowdledge representation, automated reasoning, ML.Real Turing test: require interaction with objects and people, robot needs CV and robotics. Cognitive modeling approach to test thinking humanly: learn human though through introspection, psychological experiments, brain imaging. See if a program input out put behavior matches human.Laws of thought approach tests thinking rationally through verifying correct logical inferences Rational agent approach tests acting rationally. This test is more general than the laws of thoughtsIt is also more amenable to scientific development. Rationality is math defined. Perfect rationality is not feasible when computational demand is high.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n \nTuring's \"argument from informality of behavior\" says human behavior is too complex to be captured. Good old-Fashioned AI (GOFAI) is the simplest logical agent that cannot capture every rule.The argument from disbility claims a machine can never do X. Computers outperform human in some tasks and lag for the others, but it cannot be exactly human.The mathematical objection proves that some math questions are not answerable by formal systems. JR Lucas thinks machines are limited by this, so they are inferior to humanMeasuring AI by performance on some behaviorial task is the key point of his test.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nPhilosophers claim machines are not actually thinking but simulating thinking. Turing notes there is no direct evidence about human mental states. So we should say everyone thinks including intelligent machines.John Searle rejects the polite convention through Chinese room argument, computers generate no understanding. All debates focuses on consciousness/qualia which is the awareness of outself word, self, and living. Turing thinks making machine human like concious is not the focus.\n\n\n\n## AIMA 2.1 Agents and Environments\n\nThis section talks about agent and environment. Human agents has eyes, hands, etc. A robotic agent has camera or motors for actuators. Software agent receives files, input. Environment is what agent perceives and affected by agent actions.\nThe agent action depends on its built in knowledge and percept sequence from past to date, not on anything it has not perceived future percept. \n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nThis section talks about rationality. Human evaluate agents by it's performance consequence from human's point of view. Rationality depends on the performance meaure that definesthe criterion of success, the agent's prior knowledge of the environment, the agent actions, and percept sequence.The difference between omniscience and rational is that an omniscient agent knows the actual outcome of its actions and maximize actual performancewhereas rationality maximize expected outcome. We don't expect rational agent to be omniscient, but it should do information gathering, doing actions to modify future perceptsand even be automomy and learn from its percepts.\n\n\n## AIMA 2.3 The Nature of Environments\n \nThis section talks about task environment which is described by PEAS(Performance measure, Environment, Actuators, Sensors) and needs to be specified first when designing an agentTask environment is fully observable if the sensors have accoess to the complete state of the environment.Multi agent game can be either competitive or cooperative.If the next state of the enironment is fully depends on the current state and agent's action, the environment is determinstic.\nAn example of non-determinstic environment is taxi driving because traffic is random. Stochastic is different because it's not 100% random, it deals with probabilities.In sequential environment, the current decision could affect future decisions, but in episodic task environment it would not.In dynamic environment, it can change when agent is making decision, static environment will not.\nIn known enviroument, the agent will know the outcome of all its actions.\n\n\n\n## AIMA 2.4 The Structure of Agents\n \nThis section talks about the structure of agents. The job of AI is to design an agent program that implements the agent function. agent = architecture+programThe agent programs in this class all take the current percept as input from sensors and return an action to actuators. The agent function may depend on the entire percept history.The challenge of AI is to produce rational behavior from a small program rather than a big table.There are 4 integlligent systems:Simple reflex agents: select actions based on current percept, not from history, only works in fully observable environmentModel-based reflex agents: handle partial observable environment and keeps track of the part of world where it cannot see. Need to track transition model and sersor modelGoal-based agents:needs a particular goal or destinationUtility-based agebts: can assign a utility function to agent's performance measure, the agent will act to maximize its expected utilityThis section then discusses learning agent which can be divided into four components: learning element which makes improvementperformance elememnt which select external actionscritic which measures performance standard and tells learning element how well the agent is doingproblem generator which suggestion actions that will lead to new and infromative experience.\n\n\n## Module 1 Lecture Notes\n\nThere are four views of defining AI: thinking humanly, acting humanly, thinking rationally, acting rationally (rational agents). agent is composed of architecture and program. To make sure agent acts rationally we define performance measure for them.When designing performance measure we should keep it to what we want to be achieved, not we think how agent should behave.Rational agent will only select an optioan 'a' for each option 'p' to maximize expected value of performance measure, but not actual performance.To desgin a rational agentm we need to specify task environment and construct agent function that maximize the expected value of the performanceand design an agent program that implements the agent function.There are also different type of agents. Reflex agent only selects action based on current percept, but problem solving agent will plan ahead and search for actions from path to goal state. \n\n## Module 1 Definitions\n* **Introspection** - record personal thoughts\n* **Psychological experiements** - observe people's actions\n* **Brain imaging** - observe brain's actions\n* **Agent** - anything that can perceive and act in an environment through sensors and actuators\n* **Rational agent** - agent who acts to achieve the optimal/best outcome and maximize expected performance measure\n* **Weak ai** - machine can act as if it is intelligent\n* **String ai** - machine is thinking\n* **Percept** - stuff received by sensors\n* **Percept sequence** - all historical percept\n* **Agent function** - percept sequence -> action, or f:p->a in math\n* **Agemnt program** - implements agent function\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "Python has advantages like fast development, portable, many built-in types, and large supported libraries.\\\n",
        "All data are objects and will be deleted once unreachable. Each object has a fixed typem which can be checked by either type(object) or isinstance(object,type)\\\n",
        "Different from Java which supports static typing, python supports dynamic typing.\\\n",
        "String is immutable and has below key operations:\\\n",
        "can be concatenated using +\\\n",
        "r prefix means the string is raw type, so no escape is needed like r'\\ n' \\\n",
        "Java can return only 1 value, but python can return a tuple as multiple value.\\\n",
        "Python does not allow method overloading like java, but allows operator overloading.\\\n",
        "You can provide default values for function's arguments, but non-default argument should alwasy precede default argument.\\\n",
        "*args allows you to pass in non-keyword argument to function\\\n",
        "**kwargs allow you to pass in a variable number of keyword arguments.\\\n",
        "Functions are first class objects that can be created, passed to a function, return as a value and etc.\\\n",
        "There is no extend in python, just put the parent class name in () for subclass. To redefine a mthod of parent class, just define a new one using the same name\\\n",
        "Magic method includes str for print, len for len, copy for copy, cmp for ==, add for +, neg for negation\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"tuple\" : \"a ordered sequence of items that is not mutable and can be mixed types\",\n",
        "\"list\": \"a ordered sequence of items that is mutable and can be mixed types\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 345
        },
        "outputId": "66180d81-6f40-408e-cc79-2306349d445d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\nPython has advantages like fast development, portable, many built-in types, and large supported libraries.All data are objects and will be deleted once unreachable. Each object has a fixed typem which can be checked by either type(object) or isinstance(object,type)Different from Java which supports static typing, python supports dynamic typing.String is immutable and has below key operations:can be concatenated using +r prefix means the string is raw type, so no escape is needed like r'\\ n' Java can return only 1 value, but python can return a tuple as multiple value.Python does not allow method overloading like java, but allows operator overloading.You can provide default values for function's arguments, but non-default argument should alwasy precede default argument.*args allows you to pass in non-keyword argument to function**kwargs allow you to pass in a variable number of keyword arguments.Functions are first class objects that can be created, passed to a function, return as a value and etc.There is no extend in python, just put the parent class name in () for subclass. To redefine a mthod of parent class, just define a new one using the same nameMagic method includes str for print, len for len, copy for copy, cmp for ==, add for +, neg for negation\n \n\n## Module 2 Definitions\n* **Tuple** - a ordered sequence of items that is not mutable and can be mixed types\n* **List** - a ordered sequence of items that is mutable and can be mixed types\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" \n",
        "The problem solving agent needs to form the goal, form the problem, search for solution, and execute the solution.\\\n",
        "A search problem needs state space, initial state, goal state, actions, transition model, and action cost function. \n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" \n",
        "This section talks about example problems. A standardized problem is intended to illustrate or exercise various problem-solving methods.\\\n",
        "Some examples include grid word problem, which is a 2D array which agent can move from cell to cell. \\\n",
        "A real-word problem is problem which solution is actully used by people.\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" \n",
        "A search algorithm takes a search problem as input and returns either solutin or failure as the result.\\\n",
        "The state space describes set of states which can be infinite, and actions that transite one state to another state.\\\n",
        "The search tree describes paths between these states which can have multiple path to a state. But each node of a tree only has 1 path back to root.\\\n",
        "An algorithm is a graph search if it checks for redundant path, otherwise its a tree search. Best first search is a graph search.\\\n",
        "To measure the search performance, we check completeness, cost optimality, time complexity, and space complexity. \\\n",
        "When representing complexity, b represents maximum branching factor, d represent depth of the closest/shallowest goal, m represent max length of any path.\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "Uninformed search gives the agent no clue how close it is to the goal \\\n",
        "Best first search selects which node to expand using a evaluation function \\\n",
        "Breadth first search expands to the nearest/most shallow node. In general, exponential complex search problem cannot be solved by uninformed search. This is complete and optimal.\\\n",
        "Another search strategy is Dijkstra or uninform-cost search which cost similar to bfs. It expands node to the lowest path cost. This is also complete and optimal.\\\n",
        "DFS expands to the deepest unexpanded node and has space complexity of O(bm) where m is the maximum depth of the tree. DFS is not complete. A variation is depth limited search whose time complexity is O(b^l) and space complexity is O(bl) where l is the depth limit, but it can also be incomplete. \\\n",
        "Depth limited Search added a depth bound for DFS.\\\n",
        "Iterative deeping search call dfs with increasing depth limits. It solves the problem of incompleteness, but its time complexity takes O(b^d) when there is a solution and O(b^m) when there is not. \\\n",
        "The bidirectional search searches from the initial state forwardly and goal state backwardly. It expands two frontiers and stop when frontiers meet.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "Reflex agent makes decition based on current percept, not on history. A problem solving agent plans ahead and find a solution to goal state.\\\n",
        "Uninformed search is when each edge cost is the same.\\\n",
        "BFS expands to the shallowest unvisited node and its frontier is FIFO, whereas DFS expand to the deepest unvisited node and its frontier is LIFO.\\\n",
        " \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "\"search\": \"an agent check the future and find actions to achieve goals\",\n",
        "\"path\": \"a sequence of actions\",\n",
        "\"solution\":\"path from initial state to goal state\",\n",
        "\"optimal solution\": \"solution with lowest path cost\",\n",
        "\"abstraction\":\"deleting details from representations\",\n",
        "\"depth\":\"count of actions in optimal solution\",\n",
        "\"branching factor\":\"count of a node's successors\",\n",
        "\"state space\":\"states that can be reached from initial state after some actions\",\n",
        "\"search tree\":\"a format to represent that paths explored\",\n",
        "\"frontier\":\"states waiting to be explored\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 899
        },
        "outputId": "67ffb65d-b0bc-494e-9dd4-a6eebf135bd3"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nThe problem solving agent needs to form the goal, form the problem, search for solution, and execute the solution.A search problem needs state space, initial state, goal state, actions, transition model, and action cost function. \n\n\n## AIMA Chapter 3.2 Example Problems\n \nThis section talks about example problems. A standardized problem is intended to illustrate or exercise various problem-solving methods.Some examples include grid word problem, which is a 2D array which agent can move from cell to cell. A real-word problem is problem which solution is actully used by people.\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \nA search algorithm takes a search problem as input and returns either solutin or failure as the result.The state space describes set of states which can be infinite, and actions that transite one state to another state.The search tree describes paths between these states which can have multiple path to a state. But each node of a tree only has 1 path back to root.An algorithm is a graph search if it checks for redundant path, otherwise its a tree search. Best first search is a graph search.To measure the search performance, we check completeness, cost optimality, time complexity, and space complexity. When representing complexity, b represents maximum branching factor, d represent depth of the closest/shallowest goal, m represent max length of any path.\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nUninformed search gives the agent no clue how close it is to the goal Best first search selects which node to expand using a evaluation function Breadth first search expands to the nearest/most shallow node. In general, exponential complex search problem cannot be solved by uninformed search. This is complete and optimal.Another search strategy is Dijkstra or uninform-cost search which cost similar to bfs. It expands node to the lowest path cost. This is also complete and optimal.DFS expands to the deepest unexpanded node and has space complexity of O(bm) where m is the maximum depth of the tree. DFS is not complete. A variation is depth limited search whose time complexity is O(b^l) and space complexity is O(bl) where l is the depth limit, but it can also be incomplete. Depth limited Search added a depth bound for DFS.Iterative deeping search call dfs with increasing depth limits. It solves the problem of incompleteness, but its time complexity takes O(b^d) when there is a solution and O(b^m) when there is not. The bidirectional search searches from the initial state forwardly and goal state backwardly. It expands two frontiers and stop when frontiers meet.\n\n\n## Module 3 Lecture Notes\n \nReflex agent makes decition based on current percept, not on history. A problem solving agent plans ahead and find a solution to goal state.Uninformed search is when each edge cost is the same.BFS expands to the shallowest unvisited node and its frontier is FIFO, whereas DFS expand to the deepest unvisited node and its frontier is LIFO. \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Search** - an agent check the future and find actions to achieve goals\n* **Path** - a sequence of actions\n* **Solution** - path from initial state to goal state\n* **Optimal solution** - solution with lowest path cost\n* **Abstraction** - deleting details from representations\n* **Depth** - count of actions in optimal solution\n* **Branching factor** - count of a node's successors\n* **State space** - states that can be reached from initial state after some actions\n* **Search tree** - a format to represent that paths explored\n* **Frontier** - states waiting to be explored\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "This section discusses different search method which has heuristic function information. \\\n",
        "Greedy bfs use the evaluation f(n)=h(n). Space costs O(V) and time cost O(bm) It is not optimal, but very efficient.\\\n",
        "A * search use f(n)=g(n)+h(n)\\\n",
        "A* is complete but whether it is optimal depends on whether the heuristic is optimal. Every consistent heuristic is admissble, but not the other way around.\n",
        "A* is efficient because it prunes away searh tree nodes that not necessary to find optimal solution. If the heuristic function is inadmissible, we could get not optimal solution,\n",
        "but expand less nodes. \\\n",
        "Bidirectional heuristic search is not guaranteed to be optimal.\\\n",
        "Iterative deepening A* search addresses the space complexity issue.\\\n",
        "Recursive best first search and simplified memory-bound A* are optimal and use limited memory.\\\n",
        "Beam search limits the size of frontier, but is incomplete and not optmal. It's able to find fairly good solutions.\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "When comparing different heuristic functions if h2(n)>=h1(n) then h2 dominates h1, which means h2 expands less nodes than h1.\\\n",
        "We can also change the problem to a relaxed one because the cost of an optional solution to a relaxed problem is also heuristic to the origional one.\\\n",
        "Heuristics can also be derived form the subproblem of a given problem\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "The best heuristics is the true distance from current node to goal. The worst heuristics is 0.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"heuristic function\" : \"estimated cost from current state to goal state\",    \n",
        "\"relaxed problem\":\"lift some restrictions of the problem\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 477
        },
        "cellView": "form",
        "outputId": "6c5c23fd-7aef-41ca-a5f9-76ba214a7c24"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nThis section discusses different search method which has heuristic function information. Greedy bfs use the evaluation f(n)=h(n). Space costs O(V) and time cost O(bm) It is not optimal, but very efficient.A * search use f(n)=g(n)+h(n)A* is complete but whether it is optimal depends on whether the heuristic is optimal. Every consistent heuristic is admissble, but not the other way around.\nA* is efficient because it prunes away searh tree nodes that not necessary to find optimal solution. If the heuristic function is inadmissible, we could get not optimal solution,\nbut expand less nodes. Bidirectional heuristic search is not guaranteed to be optimal.Iterative deepening A* search addresses the space complexity issue.Recursive best first search and simplified memory-bound A* are optimal and use limited memory.Beam search limits the size of frontier, but is incomplete and not optmal. It's able to find fairly good solutions.\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n\nWhen comparing different heuristic functions if h2(n)>=h1(n) then h2 dominates h1, which means h2 expands less nodes than h1.We can also change the problem to a relaxed one because the cost of an optional solution to a relaxed problem is also heuristic to the origional one.Heuristics can also be derived form the subproblem of a given problem\n\n\n## Module 4 Lecture Notes\n \nThe best heuristics is the true distance from current node to goal. The worst heuristics is 0.\n\n\n## Module 4 Definitions\n* **Heuristic function** - estimated cost from current state to goal state\n* **Relaxed problem** - lift some restrictions of the problem\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "This section discusses how to solve perfect information and zero-sum games. This game is composed of the initial state, current state(who to move next), actions(legal moves),\n",
        "the result of current state(the transition model), the terminal state, and the utility function(payoff function).\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "The minmax value of a terminal state is its untility. For non-terminal state, max moves to a state of maximum value, min move to minimum value.\\\n",
        "The minmax algo performs a complete dfs of the whole game tree so its runtime is O(b^m) and space complexity is O(bm)\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "We need to use a heuristic evaluation function that estimate the utility of a state to cut off search at some point to not search through the whole tree\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "In stochastic games, we have to use expected minmax, which evalues a chance node by taking the average utility of all its children, weighted by probability.\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "The principle of maximum expected utility defines that a rational agent should act to maximize the expected utility.\n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\"  \"\"\"\n",
        "chapter16_3 = \"\"\"  \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "A simple game environment is multi agent, static, discrete, fully observable, and strategic. \\\n",
        "Some examples are chess, Go, Tic-Tac-Toe, card games and etc. \\\n",
        "A game is formed by initial state, successor function, terminal test, and utility function.\\\n",
        "An evaluation function evaluates how good a board position is based on static features. If the function is greater than 0, the max is winning.\\\n",
        "The minmax procedure works like this, we start the current position as a MAX node, then expand the game tree for a fixed number of play, apply the evaluation function to current leaf,\n",
        "calculate back and assign the max move at the root, then min responds.\\\n",
        "If min does not play optimally, max will have a even better result.\\\n",
        "As for ab pruning, alpha is max's current lower bound and beta is min's current upper bound. Max will not allow a move that's smaller than alpha, and Min will not all a move that's greater than beta.\\\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Probability theory\" : \"what agent should believe\",    \n",
        "\"utility theory\":\"what agent wants\",\n",
        "\"decision theory\":\"combine two\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 781
        },
        "outputId": "2d8ceb92-8a73-4135-9c25-26f8dc320b1d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nThis section discusses how to solve perfect information and zero-sum games. This game is composed of the initial state, current state(who to move next), actions(legal moves),\nthe result of current state(the transition model), the terminal state, and the utility function(payoff function).\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nThe minmax value of a terminal state is its untility. For non-terminal state, max moves to a state of maximum value, min move to minimum value.The minmax algo performs a complete dfs of the whole game tree so its runtime is O(b^m) and space complexity is O(bm)\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nWe need to use a heuristic evaluation function that estimate the utility of a state to cut off search at some point to not search through the whole tree\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nIn stochastic games, we have to use expected minmax, which evalues a chance node by taking the average utility of all its children, weighted by probability.\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe principle of maximum expected utility defines that a rational agent should act to maximize the expected utility.\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n  \n\n## AIMA Chapter 16.3 Utility Functions\n  \n\n## Module 5 Lecture Notes\n \nA simple game environment is multi agent, static, discrete, fully observable, and strategic. Some examples are chess, Go, Tic-Tac-Toe, card games and etc. A game is formed by initial state, successor function, terminal test, and utility function.An evaluation function evaluates how good a board position is based on static features. If the function is greater than 0, the max is winning.The minmax procedure works like this, we start the current position as a MAX node, then expand the game tree for a fixed number of play, apply the evaluation function to current leaf,\ncalculate back and assign the max move at the root, then min responds.If min does not play optimally, max will have a even better result.As for ab pruning, alpha is max's current lower bound and beta is min's current upper bound. Max will not allow a move that's smaller than alpha, and Min will not all a move that's greater than beta. \n\n## Module 5 Definitions\n* **Probability theory** - what agent should believe\n* **Utility theory** - what agent wants\n* **Decision theory** - combine two\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "There are three components for CSP: X is the variables, D is a set of domains, one for each variable, and C is a set of constraints that describe allowed value combinations.\\\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "An state-space search algorithm only has one way to move to the next state which is expanding to a node of successors.\\\n",
        "A CSP can either choose a new variable assignment or use the constraints to propagate and reduce the legal move or a variable and reduce legal moves for other variables as well. \n",
        "Some time this propagation can solve the whole problem before search\\\n",
        "The idea is to enforce local consistancy and there are different type of local consistencies. \\\n",
        "Node consistent refers to a single variable and all values in nodes' domain satisfies constraints. \\\n",
        "Arc consistent refers to when every value in a domain statisfies its binary constraints. \\\n",
        "Path consistency referes to enforcing triplets.\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "There are times when we finish constraint propagation but still have variables with multiple values, and we will need to search for a solution. \\\n",
        "We should choose fail first variable and fail last value. Fail first variable can prune the tree fast. Value select needs to choose the value that \\\n",
        "When choosing variable, we can use minimum remaining values (MRV) where one can choose the most constrained variable to pruning the search tree. \\\n",
        "When selection value, we can use least constraining value which prues the fewest choice for its neighbors inorder to leave maximum flexibility for following variable selections. \\\n",
        "Another strategy we can use is forward checking, when we assign a variable we can propagate forward to establish arc consistency for its neighbors \n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "Local search for CSP uses min conflict techniques.\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "Cutset conditioning can reduce a CSP to a tree.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "The assignment to a CSP is complete when every variable has a value, the assignment needs to be complete and consistent. \\\n",
        "CSP includes many general problems, prune off branches that violate the search.\\\n",
        "AC3 solves CSP through search and inference.\\\n",
        "AC3 runs O(n^2d^3) in worst case.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"CSP\" : \"a state with a set of value pairs and search fro solution through constraints\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 711
        },
        "outputId": "419bd0a6-6270-4d5d-b993-00495a7d52f4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nThere are three components for CSP: X is the variables, D is a set of domains, one for each variable, and C is a set of constraints that describe allowed value combinations. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nAn state-space search algorithm only has one way to move to the next state which is expanding to a node of successors.A CSP can either choose a new variable assignment or use the constraints to propagate and reduce the legal move or a variable and reduce legal moves for other variables as well. \nSome time this propagation can solve the whole problem before searchThe idea is to enforce local consistancy and there are different type of local consistencies. Node consistent refers to a single variable and all values in nodes' domain satisfies constraints. Arc consistent refers to when every value in a domain statisfies its binary constraints. Path consistency referes to enforcing triplets.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nThere are times when we finish constraint propagation but still have variables with multiple values, and we will need to search for a solution. We should choose fail first variable and fail last value. Fail first variable can prune the tree fast. Value select needs to choose the value that When choosing variable, we can use minimum remaining values (MRV) where one can choose the most constrained variable to pruning the search tree. When selection value, we can use least constraining value which prues the fewest choice for its neighbors inorder to leave maximum flexibility for following variable selections. Another strategy we can use is forward checking, when we assign a variable we can propagate forward to establish arc consistency for its neighbors \n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nLocal search for CSP uses min conflict techniques.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nCutset conditioning can reduce a CSP to a tree.\n \n\n## Module 6 Lecture Notes\n \nThe assignment to a CSP is complete when every variable has a value, the assignment needs to be complete and consistent. CSP includes many general problems, prune off branches that violate the search.AC3 solves CSP through search and inference.AC3 runs O(n^2d^3) in worst case.\n \n\n## Module 6 Definitions\n* **Csp** - a state with a set of value pairs and search fro solution through constraints\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "Every time an agent needs to make a decision, it save percept to KB, then get action from KB, then tell KB what action it took and took the action. \\\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "a |= b means sentence a entails sentence b, or sentence b logically follows sentence a \\\n",
        "\n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "The Wampa word is seqential biscrete, static, but partially observable\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "Sound inference derive only sentences entailed, but complete derives all sentence s entailed.\n",
        "A and B are logically equivalent iff A entails B and B entails A\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "By using forward chaining algo, an agent can start with known kb and derive new sentences as new sentences comein. \\\n",
        "Backward chaining is like a goal-directed reasoning and works backward.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge base\" : \"sentences\",   \n",
        "\"axiom\":\"raw or underived sentences\" \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 552
        },
        "outputId": "bf547de4-23d6-4a84-c0c7-5c06f268668e"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nEvery time an agent needs to make a decision, it save percept to KB, then get action from KB, then tell KB what action it took and took the action.  \n\n## AIMA Chapter 7.2 The Wumpus World\n \na |= b means sentence a entails sentence b, or sentence b logically follows sentence a \n \n\n## AIMA Chapter 7.3 Logic\n \nThe Wampa word is seqential biscrete, static, but partially observable\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n \n\n## AIMA 7.5 Propositional Theorem Proving\n \nSound inference derive only sentences entailed, but complete derives all sentence s entailed.\nA and B are logically equivalent iff A entails B and B entails A\n \n\n## Module 7 Lecture Notes\n \nBy using forward chaining algo, an agent can start with known kb and derive new sentences as new sentences comein. Backward chaining is like a goal-directed reasoning and works backward.\n \n\n## Module 7 Definitions\n* **Knowledge base** - sentences\n* **Axiom** - raw or underived sentences\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "bb87950e-c2ec-4616-d7ff-73a5569a7466"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n \nSome prefer to define AI as rationality/right thing, or human vs rational. This study invloves math, engineerm statm and economics.Some define AI as fidelity of human performance, or thought vs behavior.This study invloves psychological observation and hypothesis on human behavior and thought process.\\ \nTuring test approach to test robot acticing humanly: can a robot think and pass the test of a human interrogator. Robot needs NLP, knowdledge representation, automated reasoning, ML.Real Turing test: require interaction with objects and people, robot needs CV and robotics. Cognitive modeling approach to test thinking humanly: learn human though through introspection, psychological experiments, brain imaging. See if a program input out put behavior matches human.Laws of thought approach tests thinking rationally through verifying correct logical inferences Rational agent approach tests acting rationally. This test is more general than the laws of thoughtsIt is also more amenable to scientific development. Rationality is math defined. Perfect rationality is not feasible when computational demand is high.\n\n\n## AIMA Chapter 27.1 The Limits of AI\n \nTuring's \"argument from informality of behavior\" says human behavior is too complex to be captured. Good old-Fashioned AI (GOFAI) is the simplest logical agent that cannot capture every rule.The argument from disbility claims a machine can never do X. Computers outperform human in some tasks and lag for the others, but it cannot be exactly human.The mathematical objection proves that some math questions are not answerable by formal systems. JR Lucas thinks machines are limited by this, so they are inferior to humanMeasuring AI by performance on some behaviorial task is the key point of his test.\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\nPhilosophers claim machines are not actually thinking but simulating thinking. Turing notes there is no direct evidence about human mental states. So we should say everyone thinks including intelligent machines.John Searle rejects the polite convention through Chinese room argument, computers generate no understanding. All debates focuses on consciousness/qualia which is the awareness of outself word, self, and living. Turing thinks making machine human like concious is not the focus.\n\n\n\n## AIMA 2.1 Agents and Environments\n\nThis section talks about agent and environment. Human agents has eyes, hands, etc. A robotic agent has camera or motors for actuators. Software agent receives files, input. Environment is what agent perceives and affected by agent actions.\nThe agent action depends on its built in knowledge and percept sequence from past to date, not on anything it has not perceived future percept. \n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nThis section talks about rationality. Human evaluate agents by it's performance consequence from human's point of view. Rationality depends on the performance meaure that definesthe criterion of success, the agent's prior knowledge of the environment, the agent actions, and percept sequence.The difference between omniscience and rational is that an omniscient agent knows the actual outcome of its actions and maximize actual performancewhereas rationality maximize expected outcome. We don't expect rational agent to be omniscient, but it should do information gathering, doing actions to modify future perceptsand even be automomy and learn from its percepts.\n\n\n## AIMA 2.3 The Nature of Environments\n \nThis section talks about task environment which is described by PEAS(Performance measure, Environment, Actuators, Sensors) and needs to be specified first when designing an agentTask environment is fully observable if the sensors have accoess to the complete state of the environment.Multi agent game can be either competitive or cooperative.If the next state of the enironment is fully depends on the current state and agent's action, the environment is determinstic.\nAn example of non-determinstic environment is taxi driving because traffic is random. Stochastic is different because it's not 100% random, it deals with probabilities.In sequential environment, the current decision could affect future decisions, but in episodic task environment it would not.In dynamic environment, it can change when agent is making decision, static environment will not.\nIn known enviroument, the agent will know the outcome of all its actions.\n\n\n\n## AIMA 2.4 The Structure of Agents\n \nThis section talks about the structure of agents. The job of AI is to design an agent program that implements the agent function. agent = architecture+programThe agent programs in this class all take the current percept as input from sensors and return an action to actuators. The agent function may depend on the entire percept history.The challenge of AI is to produce rational behavior from a small program rather than a big table.There are 4 integlligent systems:Simple reflex agents: select actions based on current percept, not from history, only works in fully observable environmentModel-based reflex agents: handle partial observable environment and keeps track of the part of world where it cannot see. Need to track transition model and sersor modelGoal-based agents:needs a particular goal or destinationUtility-based agebts: can assign a utility function to agent's performance measure, the agent will act to maximize its expected utilityThis section then discusses learning agent which can be divided into four components: learning element which makes improvementperformance elememnt which select external actionscritic which measures performance standard and tells learning element how well the agent is doingproblem generator which suggestion actions that will lead to new and infromative experience.\n\n\n## Module 1 Lecture Notes\n\nThere are four views of defining AI: thinking humanly, acting humanly, thinking rationally, acting rationally (rational agents). agent is composed of architecture and program. To make sure agent acts rationally we define performance measure for them.When designing performance measure we should keep it to what we want to be achieved, not we think how agent should behave.Rational agent will only select an optioan 'a' for each option 'p' to maximize expected value of performance measure, but not actual performance.To desgin a rational agentm we need to specify task environment and construct agent function that maximize the expected value of the performanceand design an agent program that implements the agent function.There are also different type of agents. Reflex agent only selects action based on current percept, but problem solving agent will plan ahead and search for actions from path to goal state. \n\n## Module 1 Definitions\n* **Introspection** - record personal thoughts\n* **Psychological experiements** - observe people's actions\n* **Brain imaging** - observe brain's actions\n* **Agent** - anything that can perceive and act in an environment through sensors and actuators\n* **Rational agent** - agent who acts to achieve the optimal/best outcome and maximize expected performance measure\n* **Weak ai** - machine can act as if it is intelligent\n* **String ai** - machine is thinking\n* **Percept** - stuff received by sensors\n* **Percept sequence** - all historical percept\n* **Agent function** - percept sequence -> action, or f:p->a in math\n* **Agemnt program** - implements agent function\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\nPython has advantages like fast development, portable, many built-in types, and large supported libraries.All data are objects and will be deleted once unreachable. Each object has a fixed typem which can be checked by either type(object) or isinstance(object,type)Different from Java which supports static typing, python supports dynamic typing.String is immutable and has below key operations:can be concatenated using +r prefix means the string is raw type, so no escape is needed like r'\\ n' Java can return only 1 value, but python can return a tuple as multiple value.Python does not allow method overloading like java, but allows operator overloading.You can provide default values for function's arguments, but non-default argument should alwasy precede default argument.*args allows you to pass in non-keyword argument to function**kwargs allow you to pass in a variable number of keyword arguments.Functions are first class objects that can be created, passed to a function, return as a value and etc.There is no extend in python, just put the parent class name in () for subclass. To redefine a mthod of parent class, just define a new one using the same nameMagic method includes str for print, len for len, copy for copy, cmp for ==, add for +, neg for negation\n \n\n## Module 2 Definitions\n* **Tuple** - a ordered sequence of items that is not mutable and can be mixed types\n* **List** - a ordered sequence of items that is mutable and can be mixed types\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nThe problem solving agent needs to form the goal, form the problem, search for solution, and execute the solution.A search problem needs state space, initial state, goal state, actions, transition model, and action cost function. \n\n\n## AIMA Chapter 3.2 Example Problems\n \nThis section talks about example problems. A standardized problem is intended to illustrate or exercise various problem-solving methods.Some examples include grid word problem, which is a 2D array which agent can move from cell to cell. A real-word problem is problem which solution is actully used by people.\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \nA search algorithm takes a search problem as input and returns either solutin or failure as the result.The state space describes set of states which can be infinite, and actions that transite one state to another state.The search tree describes paths between these states which can have multiple path to a state. But each node of a tree only has 1 path back to root.An algorithm is a graph search if it checks for redundant path, otherwise its a tree search. Best first search is a graph search.To measure the search performance, we check completeness, cost optimality, time complexity, and space complexity. When representing complexity, b represents maximum branching factor, d represent depth of the closest/shallowest goal, m represent max length of any path.\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nUninformed search gives the agent no clue how close it is to the goal Best first search selects which node to expand using a evaluation function Breadth first search expands to the nearest/most shallow node. In general, exponential complex search problem cannot be solved by uninformed search. This is complete and optimal.Another search strategy is Dijkstra or uninform-cost search which cost similar to bfs. It expands node to the lowest path cost. This is also complete and optimal.DFS expands to the deepest unexpanded node and has space complexity of O(bm) where m is the maximum depth of the tree. DFS is not complete. A variation is depth limited search whose time complexity is O(b^l) and space complexity is O(bl) where l is the depth limit, but it can also be incomplete. Depth limited Search added a depth bound for DFS.Iterative deeping search call dfs with increasing depth limits. It solves the problem of incompleteness, but its time complexity takes O(b^d) when there is a solution and O(b^m) when there is not. The bidirectional search searches from the initial state forwardly and goal state backwardly. It expands two frontiers and stop when frontiers meet.\n\n\n## Module 3 Lecture Notes\n \nReflex agent makes decition based on current percept, not on history. A problem solving agent plans ahead and find a solution to goal state.Uninformed search is when each edge cost is the same.BFS expands to the shallowest unvisited node and its frontier is FIFO, whereas DFS expand to the deepest unvisited node and its frontier is LIFO. \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Search** - an agent check the future and find actions to achieve goals\n* **Path** - a sequence of actions\n* **Solution** - path from initial state to goal state\n* **Optimal solution** - solution with lowest path cost\n* **Abstraction** - deleting details from representations\n* **Depth** - count of actions in optimal solution\n* **Branching factor** - count of a node's successors\n* **State space** - states that can be reached from initial state after some actions\n* **Search tree** - a format to represent that paths explored\n* **Frontier** - states waiting to be explored\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nThis section discusses different search method which has heuristic function information. Greedy bfs use the evaluation f(n)=h(n). Space costs O(V) and time cost O(bm) It is not optimal, but very efficient.A * search use f(n)=g(n)+h(n)A* is complete but whether it is optimal depends on whether the heuristic is optimal. Every consistent heuristic is admissble, but not the other way around.\nA* is efficient because it prunes away searh tree nodes that not necessary to find optimal solution. If the heuristic function is inadmissible, we could get not optimal solution,\nbut expand less nodes. Bidirectional heuristic search is not guaranteed to be optimal.Iterative deepening A* search addresses the space complexity issue.Recursive best first search and simplified memory-bound A* are optimal and use limited memory.Beam search limits the size of frontier, but is incomplete and not optmal. It's able to find fairly good solutions.\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n\nWhen comparing different heuristic functions if h2(n)>=h1(n) then h2 dominates h1, which means h2 expands less nodes than h1.We can also change the problem to a relaxed one because the cost of an optional solution to a relaxed problem is also heuristic to the origional one.Heuristics can also be derived form the subproblem of a given problem\n\n\n## Module 4 Lecture Notes\n \nThe best heuristics is the true distance from current node to goal. The worst heuristics is 0.\n\n\n## Module 4 Definitions\n* **Heuristic function** - estimated cost from current state to goal state\n* **Relaxed problem** - lift some restrictions of the problem\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nThis section discusses how to solve perfect information and zero-sum games. This game is composed of the initial state, current state(who to move next), actions(legal moves),\nthe result of current state(the transition model), the terminal state, and the utility function(payoff function).\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \nThe minmax value of a terminal state is its untility. For non-terminal state, max moves to a state of maximum value, min move to minimum value.The minmax algo performs a complete dfs of the whole game tree so its runtime is O(b^m) and space complexity is O(bm)\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nWe need to use a heuristic evaluation function that estimate the utility of a state to cut off search at some point to not search through the whole tree\n\n\n## AIMA Chapter 5.5 Stochastic Games\n \nIn stochastic games, we have to use expected minmax, which evalues a chance node by taking the average utility of all its children, weighted by probability.\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nThe principle of maximum expected utility defines that a rational agent should act to maximize the expected utility.\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n  \n\n## AIMA Chapter 16.3 Utility Functions\n  \n\n## Module 5 Lecture Notes\n \nA simple game environment is multi agent, static, discrete, fully observable, and strategic. Some examples are chess, Go, Tic-Tac-Toe, card games and etc. A game is formed by initial state, successor function, terminal test, and utility function.An evaluation function evaluates how good a board position is based on static features. If the function is greater than 0, the max is winning.The minmax procedure works like this, we start the current position as a MAX node, then expand the game tree for a fixed number of play, apply the evaluation function to current leaf,\ncalculate back and assign the max move at the root, then min responds.If min does not play optimally, max will have a even better result.As for ab pruning, alpha is max's current lower bound and beta is min's current upper bound. Max will not allow a move that's smaller than alpha, and Min will not all a move that's greater than beta. \n\n## Module 5 Definitions\n* **Probability theory** - what agent should believe\n* **Utility theory** - what agent wants\n* **Decision theory** - combine two\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nThere are three components for CSP: X is the variables, D is a set of domains, one for each variable, and C is a set of constraints that describe allowed value combinations. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nAn state-space search algorithm only has one way to move to the next state which is expanding to a node of successors.A CSP can either choose a new variable assignment or use the constraints to propagate and reduce the legal move or a variable and reduce legal moves for other variables as well. \nSome time this propagation can solve the whole problem before searchThe idea is to enforce local consistancy and there are different type of local consistencies. Node consistent refers to a single variable and all values in nodes' domain satisfies constraints. Arc consistent refers to when every value in a domain statisfies its binary constraints. Path consistency referes to enforcing triplets.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nThere are times when we finish constraint propagation but still have variables with multiple values, and we will need to search for a solution. We should choose fail first variable and fail last value. Fail first variable can prune the tree fast. Value select needs to choose the value that When choosing variable, we can use minimum remaining values (MRV) where one can choose the most constrained variable to pruning the search tree. When selection value, we can use least constraining value which prues the fewest choice for its neighbors inorder to leave maximum flexibility for following variable selections. Another strategy we can use is forward checking, when we assign a variable we can propagate forward to establish arc consistency for its neighbors \n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nLocal search for CSP uses min conflict techniques.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nCutset conditioning can reduce a CSP to a tree.\n \n\n## Module 6 Lecture Notes\n \nThe assignment to a CSP is complete when every variable has a value, the assignment needs to be complete and consistent. CSP includes many general problems, prune off branches that violate the search.AC3 solves CSP through search and inference.AC3 runs O(n^2d^3) in worst case.\n \n\n## Module 6 Definitions\n* **Csp** - a state with a set of value pairs and search fro solution through constraints\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nEvery time an agent needs to make a decision, it save percept to KB, then get action from KB, then tell KB what action it took and took the action.  \n\n## AIMA Chapter 7.2 The Wumpus World\n \na |= b means sentence a entails sentence b, or sentence b logically follows sentence a \n \n\n## AIMA Chapter 7.3 Logic\n \nThe Wampa word is seqential biscrete, static, but partially observable\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \n \n\n## AIMA 7.5 Propositional Theorem Proving\n \nSound inference derive only sentences entailed, but complete derives all sentence s entailed.\nA and B are logically equivalent iff A entails B and B entails A\n \n\n## Module 7 Lecture Notes\n \nBy using forward chaining algo, an agent can start with known kb and derive new sentences as new sentences comein. Backward chaining is like a goal-directed reasoning and works backward.\n \n\n## Module 7 Definitions\n* **Knowledge base** - sentences\n* **Axiom** - raw or underived sentences\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}