{
  "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": "97097151-a300-483f-9d76-9d7fc253dcdb"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "deterministic, two-player, turn-taking, perfect information, zero-sum games.\\\n",
        "we often use the term move as a synonym for “action” and position as a synonym for “state.”\\\n",
        "Game can be defined using four elements:1.initial state2.TO-MOVE(s): The player whose turn it is to move in state .\n",
        "3.ACTIONS(s):The set of legal moves in state .\n",
        "4.RESULT(s,a):The transition model, which defines the state resulting from taking action a in state s\n",
        "5.IS-TERMINAL(s):A terminal test, which is true when the game is over and false otherwise.States where the game has ended are called terminal states.\n",
        "6.UTILITY(s,p):A utility function (also called an objective function or payoff function), which defines the final numeric value to player when the game ends in terminal state\\\n",
        "we can superimpose a search tree over part of that graph to determine what move to make.\\\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": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 126 words long, so you could write an additional 374 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": "ec00822d-9b33-4127-bb7f-0f241902f838"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 1\n",
            "The length in characters is 0\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 = False"
      ],
      "execution_count": 3,
      "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 = \"\"\" Tuning test contains natural language processing,knowledge representation,automated reasoning,machine learning. \\\n",
        "total Tuning test contains computer vision,robotics. \\\n",
        "Human thoughts contain introspection,psychological experiments,brain imaging. \\\n",
        "The rational-agent approach to AI has two advantages over the other approaches. First, it is more general than the “laws of thought” approach because correct inference is just one of several possible mechanisms for achieving rationality. Second, it is more amenable to scientific development. \\\n",
        "AI has focused on the study and construction of agents that do the right thing. \\\n",
        "It is impossible to anticipate all the ways in which a machine pursuing a fixed objective might misbehave. There is good reason, then, to think that the standard model is inadequate.\\\n",
        "We don’t want machines that are intelligent in the sense of pursuing their objectives; we want them to pursue our objectives. \\ \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.\\\n",
        "we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action.\\\n",
        "The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system.\\ \"\"\"\n",
        "chapter2_2 = \"\"\" but AI has generally stuck to one notion called consequentialism: we evaluate an agent’s behavior by\n",
        "its consequences. When an agent is plunked down in an environment, it generates a\n",
        "sequence of actions according to the percepts it receives. This sequence of actions causes\n",
        "the environment to go through a sequence of states.\\\n",
        "Humans have desires and preferences of their own,Machines, on the other hand, do not have desires and preferences of their own;\n",
        "What is rational at any given time depends on four things:The performance measure that defines the criterion of success.The agent’s prior knowledge of the environment.\n",
        "The actions that the agent can perform.The agent’s percept sequence to date.\\\n",
        "\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.(rational agent defination)\\\n",
        "hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\\\n",
        " \"\"\"\n",
        "chapter2_4 = \"\"\" The job of AI is to design an agent program that implements the agent function.\\\n",
        " We assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture: agent=architecture+program.\\\n",
        " The key challenge for AI is to find out how to write programs that, to the extent possible, produce rational behavior from a smallish program rather than from a vast table.\\\n",
        " four basic kinds of agent programs that embody the principles underlying almost all intelligent systems:\n",
        "Simple reflex agents; Model-based reflex agents; Goal-based agents; and Utility-based agents.\\\n",
        "a randomized simple reflex agent might outperform a deterministic simple reflex agent.\\\n",
        "The most effective way to handle partial observability is for the agent to keep track of the part of the world it can’t see now.That is, the agent should maintain some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved aspects of the current state. \\\n",
        "Any type of agent (model-based, goal-based, utility-based, etc.) can be built as a learning agent (or not) by using performance element, learning element and problem generator.\\\n",
        "All agents can improve their performance through learning.\\ \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "'rational agent': 'acts to achieve the best outcome',\n",
        "\"percept\" : \"content that agent detect\",\n",
        "'percept sequence':'history of content that agent detect',\n",
        "'value alignment problem':'the value of things to machine must matches with human\\'s thought about value of that thing',\n",
        "'agent function':'abstract concept of what agent is doing',\n",
        "'agent program':'concrete implementation, running within some physical program.',\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "'consequentialism':'only consequence of agent action matters',\n",
        "'information gathering':'doing to modify future percepts',\n",
        "'autonomy':'not rely on prior knowledge, but learn on its own percepts',\n",
        "'PEAS':'Performance(Goal), Environment(what agent is facing), Actuators(tool of agent to finish goal), Sensors(provide environment information)',\n",
        "'software agent(softbot)':'web site agent',\n",
        "'Fully observable':'all relevant information to the choice of action is avaliable',\n",
        "'Deterministic':'next state is determined by agent action(nonDeterministic vice versa),in practice nondeterministic is more frequent',\n",
        "'stochastic':'if uncertainty has probability, it is stochastic, otherwise it is nondeterministic',\n",
        "'episodic':'one action a time,next episode does not depend on current action',\n",
        "'sequential':'current action can affect future decisions',\n",
        "'static':'environment cannot change, while dynamic refers to changing environment',\n",
        "'semidynamic':'environment dont change but agent score change',\n",
        "'known':'agent knowledge, not environment, not like fully observable',\n",
        "'agent program':'agent=agent program(algorithm)+agent architecture(computer)',\n",
        "'simple reflex agent':'just correspond to current percept, ignore history',\n",
        "'transition model of the world':'knowledge of how the world works',\n",
        "'sensor model':'how the state of the world is reflected in the agent percepts',\n",
        "'model-based agent':'transition model + sensor model agent',\n",
        "'goal-based agent':'more flexible, adjusting goal can change agent behavior',\n",
        "'utility-based agent':'agent maximizing expected utility',\n",
        "'performance element':'takes percept and make decision(entire agent)',\n",
        "'learning element':'to make improvement for agent use feedback',\n",
        "'problem generator':'suggest action that lead to new information ',\n",
        "'atomic representation':'no internal structure',\n",
        "'factored representation':'splits up each state into a fixed set of variables or attributes,',\n",
        "'structured representation':'objects has inter related relation',\n",
        "'localist representation':'dictionary of concepts and memory location(one to one)',\n",
        "'distributed representation':'concepts and memory location are many to many(robust against information loss)',\n",
        "'Good Old-Fashioned AI (GOFAI)':'simplest logical agent ',\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "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": "b32a7739-2597-4f72-f8a8-35fa28b381d5"
      },
      "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": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Tuning test contains natural language processing,knowledge representation,automated reasoning,machine learning. total Tuning test contains computer vision,robotics. Human thoughts contain introspection,psychological experiments,brain imaging. The rational-agent approach to AI has two advantages over the other approaches. First, it is more general than the “laws of thought” approach because correct inference is just one of several possible mechanisms for achieving rationality. Second, it is more amenable to scientific development. AI has focused on the study and construction of agents that do the right thing. It is impossible to anticipate all the ways in which a machine pursuing a fixed objective might misbehave. There is good reason, then, to think that the standard model is inadequate.We don’t want machines that are intelligent in the sense of pursuing their objectives; we want them to pursue our objectives. \\ \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action.The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system.\\ \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n but AI has generally stuck to one notion called consequentialism: we evaluate an agent’s behavior by\nits consequences. When an agent is plunked down in an environment, it generates a\nsequence of actions according to the percepts it receives. This sequence of actions causes\nthe environment to go through a sequence of states.Humans have desires and preferences of their own,Machines, on the other hand, do not have desires and preferences of their own;\nWhat is rational at any given time depends on four things:The performance measure that defines the criterion of success.The agent’s prior knowledge of the environment.\nThe actions that the agent can perform.The agent’s percept sequence to date.\n \n\n## AIMA 2.3 The Nature of Environments\n For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.(rational agent defination)hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown. \n\n## AIMA 2.4 The Structure of Agents\n The job of AI is to design an agent program that implements the agent function. We assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture: agent=architecture+program. The key challenge for AI is to find out how to write programs that, to the extent possible, produce rational behavior from a smallish program rather than from a vast table. four basic kinds of agent programs that embody the principles underlying almost all intelligent systems:\nSimple reflex agents; Model-based reflex agents; Goal-based agents; and Utility-based agents.a randomized simple reflex agent might outperform a deterministic simple reflex agent.The most effective way to handle partial observability is for the agent to keep track of the part of the world it can’t see now.That is, the agent should maintain some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved aspects of the current state. Any type of agent (model-based, goal-based, utility-based, etc.) can be built as a learning agent (or not) by using performance element, learning element and problem generator.All agents can improve their performance through learning.\\ \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - acts to achieve the best outcome\n* **Percept** - content that agent detect\n* **Percept sequence** - history of content that agent detect\n* **Value alignment problem** - the value of things to machine must matches with human's thought about value of that thing\n* **Agent function** - abstract concept of what agent is doing\n* **Agent program** - agent=agent program(algorithm)+agent architecture(computer)\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n* **Consequentialism** - only consequence of agent action matters\n* **Information gathering** - doing to modify future percepts\n* **Autonomy** - not rely on prior knowledge, but learn on its own percepts\n* **Peas** - Performance(Goal), Environment(what agent is facing), Actuators(tool of agent to finish goal), Sensors(provide environment information)\n* **Software agent(softbot)** - web site agent\n* **Fully observable** - all relevant information to the choice of action is avaliable\n* **Deterministic** - next state is determined by agent action(nonDeterministic vice versa),in practice nondeterministic is more frequent\n* **Stochastic** - if uncertainty has probability, it is stochastic, otherwise it is nondeterministic\n* **Episodic** - one action a time,next episode does not depend on current action\n* **Sequential** - current action can affect future decisions\n* **Static** - environment cannot change, while dynamic refers to changing environment\n* **Semidynamic** - environment dont change but agent score change\n* **Known** - agent knowledge, not environment, not like fully observable\n* **Simple reflex agent** - just correspond to current percept, ignore history\n* **Transition model of the world** - knowledge of how the world works\n* **Sensor model** - how the state of the world is reflected in the agent percepts\n* **Model-based agent** - transition model + sensor model agent\n* **Goal-based agent** - more flexible, adjusting goal can change agent behavior\n* **Utility-based agent** - agent maximizing expected utility\n* **Performance element** - takes percept and make decision(entire agent)\n* **Learning element** - to make improvement for agent use feedback\n* **Problem generator** - suggest action that lead to new information \n* **Atomic representation** - no internal structure\n* **Factored representation** - splits up each state into a fixed set of variables or attributes,\n* **Structured representation** - objects has inter related relation\n* **Localist representation** - dictionary of concepts and memory location(one to one)\n* **Distributed representation** - concepts and memory location are many to many(robust against information loss)\n* **Good old-fashioned ai (gofai)** - simplest logical agent \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 = \"\"\" Counter = defaultdict(int). \\\n",
        "function uses the same default object each time(eg fib(n,fib={})).\\\n",
        "function is first class object.\\\n",
        "[expression for name in list if filter].\\\n",
        "[a for i in x for j in y] = for i in x: for j in y:\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"able to change its content after being defined\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 226
        },
        "outputId": "170df682-b0ee-49b8-9eae-77e6790aaa31"
      },
      "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": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Counter = defaultdict(int). function uses the same default object each time(eg fib(n,fib={})).function is first class object.[expression for name in list if filter].[a for i in x for j in y] = for i in x: for j in y:\n\n\n## Module 2 Definitions\n* **Mutability** - able to change its content after being defined\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 = \"\"\" four-pharse problem-solving: GOAL FORMULATION,PROBLEM FORMULATION,SEARCH,EXECUTION \\\n",
        "search problem defined by :A set of possible states(state space),initial state,goal states,actions available,transition model,action cost function \n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" A standardized problem is intended to illustrate or exercise various problem- solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms. A real-world problem, such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data.\n",
        " node of tree has four part:state,parent,action,pathcost.\\\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" Dijkstra’s algorithm or uniform-cost search is  breadth-first search spreads out in waves of uniform depth—first depth 1, then depth 2, and so on\\\n",
        "It expands node with least cost so far\\\n",
        "A variant of depth-first search called backtracking search uses even less memory.\\\n",
        "this reduces the memory requirements to just one state description and a path of actions; a significant savings over states for depth-first search.\\\n",
        "  \"\"\"\n",
        "chapter3_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",   \n",
        "'open-loop':'ignore percept that might cause error',\n",
        "'closed-loop':'monitors the percept' ,\n",
        "'frontier':'list of nodes waited to be expanded',\n",
        "'best first search':'expand node with lowest f(n) score',\n",
        "'graph search':'check redundant path',\n",
        "'tree search':'dont check redundant path',\n",
        "'completeness':'guarantee a solution',\n",
        "'early goal test':'checking whether a node is a solution as soon as it is generated',\n",
        "'late goal test':'waiting until a node is popped off the queue(bfs)',\n",
        "'BFS(FIFO)':'complete,optimal,Time:O(b^d),Space:O(b^d),b braching, d depth',\n",
        "'Uniform-Cost':'Complete,optimal,Time:O(b),Space:O(b)',\n",
        "'DFS(FILO)':'not complete,not optimal,Time:O(b^m),Space:O(bm),m depth of tree no solution',\n",
        "'Depth-Limited':'not complete,not optimal,Time:O(b^l),Space:O(bl)',\n",
        "'Iterative Deepening':'Complete,optimal,Time:O(b^d),Space:O(bd)',\n",
        "'Bidirectional':'complete,optimal,T,S same:O(b^(d/2))'\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 831
        },
        "outputId": "b2326805-2102-4b62-b696-03d812452135"
      },
      "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": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n four-pharse problem-solving: GOAL FORMULATION,PROBLEM FORMULATION,SEARCH,EXECUTION search problem defined by :A set of possible states(state space),initial state,goal states,actions available,transition model,action cost function \n\n\n## AIMA Chapter 3.2 Example Problems\n A standardized problem is intended to illustrate or exercise various problem- solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms. A real-world problem, such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data.\n node of tree has four part:state,parent,action,pathcost. \n\n## AIMA Chapter 3.3 Search Algorithms\n Dijkstra’s algorithm or uniform-cost search is  breadth-first search spreads out in waves of uniform depth—first depth 1, then depth 2, and so onIt expands node with least cost so farA variant of depth-first search called backtracking search uses even less memory.this reduces the memory requirements to just one state description and a path of actions; a significant savings over states for depth-first search.  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open-loop** - ignore percept that might cause error\n* **Closed-loop** - monitors the percept\n* **Frontier** - list of nodes waited to be expanded\n* **Best first search** - expand node with lowest f(n) score\n* **Graph search** - check redundant path\n* **Tree search** - dont check redundant path\n* **Completeness** - guarantee a solution\n* **Early goal test** - checking whether a node is a solution as soon as it is generated\n* **Late goal test** - waiting until a node is popped off the queue(bfs)\n* **Bfs(fifo)** - complete,optimal,Time:O(b^d),Space:O(b^d),b braching, d depth\n* **Uniform-cost** - Complete,optimal,Time:O(b),Space:O(b)\n* **Dfs(filo)** - not complete,not optimal,Time:O(b^m),Space:O(bm),m depth of tree no solution\n* **Depth-limited** - not complete,not optimal,Time:O(b^l),Space:O(bl)\n* **Iterative deepening** - Complete,optimal,Time:O(b^d),Space:O(bd)\n* **Bidirectional** - complete,optimal,T,S same:O(b^(d/2))\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 = \"\"\" Greedy best-first search worst-case time and space complexity is O(|V|),With a good heuristic function is O(bm)\\\n",
        "The most common informed search algorithm is A* search , uses f(n) = g(n) + h(n), g(n)is the path cost from the initial state to node, h(n)is the estimated cost to a goal state,\\\n",
        "Every consistent heuristic is admissible,\\\n",
        "If C is the cost of the optimal solution path,surely expanded nodes are   f(n)<C,\\\n",
        "That A* search is complete, cost-optimal, and optimally efficient among all such algorithms\\\n",
        "The main issue with A* is its use of memory,Memory is split between the frontier and the reached states.\\\n",
        "Beam search limits the size of the frontier\\\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "effective branching factor(b*) = If the total number of nodes generated by A*  is N and the solution depth is d, N+1=1+b*+(b*)^2..+(b*)^d\\\n",
        "well-designed heuristic have b* close to 1\\\n",
        "If a collection of admissible heuristics is available for a problem and none of them is clearly better than the others, which should we choose?,just take max of them\\\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" uninformed search use real path cost of cur node to next node, best-first search use estimated path cost to goal.\\\n",
        "the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\\\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "'heristic function':'estimated cost from current state to the goal',\n",
        "'Greedy best-first search':'expands first the node with the lowest h(n)value,complete in finite states, not in infinite',\n",
        "'A* search':'g(n)+h(n),complete,optimal or not depends on h(n),space O（b^(d-k))',\n",
        "'admissible heuristic':' never overestimates the cost to reach a goal',\n",
        "'consistency(stronger admissible) of h(n)':'h(n)<= c(n,n\\')+h(n\\') for successor of h(n),consistency->admissible,not vice versa',\n",
        "'optimally efficient':'A* expands necessary nodes compared with other algorithm',\n",
        "'satisficing solutions.':'suboptimal solution',\n",
        "'Manhattan distance(city-block distance)':'sum of the horizontal and vertical distances',\n",
        "'effective branching factor':' uniform tree of depth d would have to have in order to contain N nodes.',\n",
        "'dominates':'h1 dominates h2 if h1 uses less nodes to find solution,h2(n)>=h1(n)for all n',\n",
        "' relaxed problem.':'problem with fewer restrictions on the actions ',\n",
        "'WEIGHTED A*':'expanding fewer nodes, but sacrificing optimality.',\n",
        "'RBFS ':'robust, optimal search algorithms that use limited amounts of memory',\n",
        "'pattern databases':'store these exact solution costs for every possible subproblem instance',\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 664
        },
        "cellView": "form",
        "outputId": "0e049de8-b19f-46d4-909a-0202103c0f99"
      },
      "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": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy best-first search worst-case time and space complexity is O(|V|),With a good heuristic function is O(bm)The most common informed search algorithm is A* search , uses f(n) = g(n) + h(n), g(n)is the path cost from the initial state to node, h(n)is the estimated cost to a goal state,Every consistent heuristic is admissible,If C is the cost of the optimal solution path,surely expanded nodes are   f(n)<C,That A* search is complete, cost-optimal, and optimally efficient among all such algorithmsThe main issue with A* is its use of memory,Memory is split between the frontier and the reached states.Beam search limits the size of the frontier\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \neffective branching factor(b*) = If the total number of nodes generated by A*  is N and the solution depth is d, N+1=1+b*+(b*)^2..+(b*)^dwell-designed heuristic have b* close to 1If a collection of admissible heuristics is available for a problem and none of them is clearly better than the others, which should we choose?,just take max of them \n\n## Module 4 Lecture Notes\n uninformed search use real path cost of cur node to next node, best-first search use estimated path cost to goal.the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\n## Module 4 Definitions\n* **Heristic function** - estimated cost from current state to the goal\n* **Greedy best-first search** - expands first the node with the lowest h(n)value,complete in finite states, not in infinite\n* **A* search** - g(n)+h(n),complete,optimal or not depends on h(n),space O（b^(d-k))\n* **Admissible heuristic** -  never overestimates the cost to reach a goal\n* **Consistency(stronger admissible) of h(n)** - h(n)<= c(n,n')+h(n') for successor of h(n),consistency->admissible,not vice versa\n* **Optimally efficient** - A* expands necessary nodes compared with other algorithm\n* **Satisficing solutions.** - suboptimal solution\n* **Manhattan distance(city-block distance)** - sum of the horizontal and vertical distances\n* **Effective branching factor** -  uniform tree of depth d would have to have in order to contain N nodes.\n* **Dominates** - h1 dominates h2 if h1 uses less nodes to find solution,h2(n)>=h1(n)for all n\n* ** relaxed problem.** - problem with fewer restrictions on the actions \n* **Weighted a*** - expanding fewer nodes, but sacrificing optimality.\n* **Rbfs ** - robust, optimal search algorithms that use limited amounts of memory\n* **Pattern databases** - store these exact solution costs for every possible subproblem instance\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 = \"\"\" deterministic, two-player, turn-taking, perfect information, zero-sum games.\\\n",
        "we often use the term move as a synonym for “action” and position as a synonym for “state.”\\\n",
        "Game can be defined using four elements:1.initial state2.TO-MOVE(s): The player whose turn it is to move in state .\n",
        "3.ACTIONS(s):The set of legal moves in state .\n",
        "4.RESULT(s,a):The transition model, which defines the state resulting from taking action a in state s\n",
        "5.IS-TERMINAL(s):A terminal test, which is true when the game is over and false otherwise.States where the game has ended are called terminal states.\n",
        "6.UTILITY(s,p):A utility function (also called an objective function or payoff function), which defines the final numeric value to player when the game ends in terminal state\\\n",
        "we can superimpose a search tree over part of that graph to determine what move to make.\\ \"\"\"\n",
        "chapter5_2 = \"\"\"  For games with multiple outcome scores, we need a slightly more general algorithm called minimax search.\\\n",
        "Given a game tree, the optimal strategy can be determined by working out the minimax value of each state in the tree\\\n",
        " If the maximum depth of the tree is and there are legal moves at each point, Time:O(b^m),Space:O(bm)\\\n",
        " If this could be done perfectly, alpha–beta would need to examine only O(b^(m/2)),instead O(b^m)for minimax\\\n",
        " With random move ordering, the total number of nodes examined will be roughlyO(b^(3m/4))\\\n",
        " Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree. \\\n",
        " A Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion\\  \"\"\"\n",
        "chapter5_3 = \"\"\" Eval(s,p) returns an estimate of the expected utility of state s to player p,For terminal states, Eval(s,p)=Utility(s,p),for nonterminal, Utility(loss,p)<=Eval(s,p)<=Utility(win,p)\\\n",
        " Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good ones. \\\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" f the program knew in advance all the dice rolls that would occur for the rest of the game, solving a game with dice would be just like solving a game without dice, which minimax does in O(b^m) time, where is the branching factor and is the maximum depth of the game tree. Because expectiminimax is also considering all the possible dice-roll sequences, it will takeO(b^m n^m) , where is the number of distinct rolls. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" If an agent’s preferences obey the axioms of utility, then there exists a function such thatU(A)>U(B) if and only if is A preferred to B,\\\n",
        "As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function.\\\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" If we want to build a decision-theoretic system that helps a human make decisions or acts\n",
        "on his or her behalf, we must first work out what the human’s utility function is. This\n",
        "process, often called preference elicitation, involves presenting choices to the human and \n",
        "using the observed preferences to pin down the underlying utility function \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "'minimax':'time:O(b^m)space:O(bm)for generates all actions at once,O(m) for generates actions one at a time',\n",
        "'competitive environments':'more than one agents, compete for goal' ,\n",
        "'pruning':'igonre unnecessary nodes',\n",
        "'imperfect information':'not all information is visible to players',\n",
        "'perfect information':'synonym for fully obervable',\n",
        "'quiescent':'positions in which there is no pending move that changes evaluation too much',\n",
        "'quiescence search ':'consider only certain types of moves, such as capture moves',\n",
        "'horizon effect':'unavoidable damaging move',\n",
        "'singular extensions':'moves that are “clearly better”,delay horizon effect',\n",
        "'forward pruning':'runes moves that appear to be poor moves, but might be good',\n",
        "'ORDERABILITY':'one of A>B,A<B,A~B holds',\n",
        "'TRANSITIVITY':'A>B and B>C -> A>C',\n",
        "'CONTINUITY':'A>B>C-> [p,A,1-p,C]~B for some p',\n",
        "'SUBSTITUTABILITY:':'A~B->[p,A,1-p,C]~[p,B,1-p,C]',\n",
        "'MONOTONICITY':'A>B->(p>q<->[p,A,1-p,B]>[q,A,1-q,B])',\n",
        "'DECOMPOSABILITY':'[p,A;1-p,[q,B,1-q,C]]~[p,A;,(1-p)q,B;(1-p)(1-q),C]',\n",
        "'value function':'number of utility not matter, order matters',\n",
        "'Normalized utilities':'0<=u<=1',\n",
        "'certainty equivalent':'certain value of lottery',\n",
        "'framing effect':'people like positive describtion(90%survival rate > 10% death rate)',\n",
        "'anchoring effect':'people value stuff compared with other stuff'\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "f72a8901-4b28-4759-b0c9-871860736802"
      },
      "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": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n deterministic, two-player, turn-taking, perfect information, zero-sum games.we often use the term move as a synonym for “action” and position as a synonym for “state.”Game can be defined using four elements:1.initial state2.TO-MOVE(s): The player whose turn it is to move in state .\n3.ACTIONS(s):The set of legal moves in state .\n4.RESULT(s,a):The transition model, which defines the state resulting from taking action a in state s\n5.IS-TERMINAL(s):A terminal test, which is true when the game is over and false otherwise.States where the game has ended are called terminal states.\n6.UTILITY(s,p):A utility function (also called an objective function or payoff function), which defines the final numeric value to player when the game ends in terminal statewe can superimpose a search tree over part of that graph to determine what move to make.\\ \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n  For games with multiple outcome scores, we need a slightly more general algorithm called minimax search.Given a game tree, the optimal strategy can be determined by working out the minimax value of each state in the tree If the maximum depth of the tree is and there are legal moves at each point, Time:O(b^m),Space:O(bm) If this could be done perfectly, alpha–beta would need to examine only O(b^(m/2)),instead O(b^m)for minimax With random move ordering, the total number of nodes examined will be roughlyO(b^(3m/4)) Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree.  A Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion\\  \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Eval(s,p) returns an estimate of the expected utility of state s to player p,For terminal states, Eval(s,p)=Utility(s,p),for nonterminal, Utility(loss,p)<=Eval(s,p)<=Utility(win,p) Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good ones.  \n\n## AIMA Chapter 5.5 Stochastic Games\n f the program knew in advance all the dice rolls that would occur for the rest of the game, solving a game with dice would be just like solving a game without dice, which minimax does in O(b^m) time, where is the branching factor and is the maximum depth of the game tree. Because expectiminimax is also considering all the possible dice-roll sequences, it will takeO(b^m n^m) , where is the number of distinct rolls. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n If an agent’s preferences obey the axioms of utility, then there exists a function such thatU(A)>U(B) if and only if is A preferred to B,As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function. \n\n## AIMA Chapter 16.3 Utility Functions\n If we want to build a decision-theoretic system that helps a human make decisions or acts\non his or her behalf, we must first work out what the human’s utility function is. This\nprocess, often called preference elicitation, involves presenting choices to the human and \nusing the observed preferences to pin down the underlying utility function \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Minimax** - time:O(b^m)space:O(bm)for generates all actions at once,O(m) for generates actions one at a time\n* **Competitive environments** - more than one agents, compete for goal\n* **Pruning** - igonre unnecessary nodes\n* **Imperfect information** - not all information is visible to players\n* **Perfect information** - synonym for fully obervable\n* **Quiescent** - positions in which there is no pending move that changes evaluation too much\n* **Quiescence search ** - consider only certain types of moves, such as capture moves\n* **Horizon effect** - unavoidable damaging move\n* **Singular extensions** - moves that are “clearly better”,delay horizon effect\n* **Forward pruning** - runes moves that appear to be poor moves, but might be good\n* **Orderability** - one of A>B,A<B,A~B holds\n* **Transitivity** - A>B and B>C -> A>C\n* **Continuity** - A>B>C-> [p,A,1-p,C]~B for some p\n* **Substitutability:** - A~B->[p,A,1-p,C]~[p,B,1-p,C]\n* **Monotonicity** - A>B->(p>q<->[p,A,1-p,B]>[q,A,1-q,B])\n* **Decomposability** - [p,A;1-p,[q,B,1-q,C]]~[p,A;,(1-p)q,B;(1-p)(1-q),C]\n* **Value function** - number of utility not matter, order matters\n* **Normalized utilities** - 0<=u<=1\n* **Certainty equivalent** - certain value of lottery\n* **Framing effect** - people like positive describtion(90%survival rate > 10% death rate)\n* **Anchoring effect** - people value stuff compared with other stuff\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 = \"\"\" A problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem, or CSP.\\\n",
        " CSPs deal with assignments of values to variables,\\\n",
        " The best-known category of continuous-domain CSPs is that of linear programming problems, where constraints must be linear equalities or inequalities. Linear programming problems can be solved in time polynomial in the number of variables. \\\n",
        " CSPs with preferences can be solved with optimization search methods, either path-based or local. We call such a problem a constrained optimization problem, or COP. Linear programs are one class of COPs.\\\n",
        "Assume a CSP with n variables,domain size at most d and c binary constraints. Each arc can be inserted in the queue only d times.\\\n",
        "checking an arc O(d^2)time, total O(cd^3)time for planar constraint graphs,O(n^2d^3) in worst case.\\\n",
        "\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\\\n",
        "A CSP is k consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\n",
        "strongly k consistent timeO(n^2d)\\\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" The MRV heuristic usually performs better than a random or static ordering, sometimes by orders of magnitude, although the results vary depending on the problem.\\\n",
        "The MRV heuristic doesn’t help at all in choosing the first region to color in Australia,In this case, the degree heuristic is useful.\\\n",
        "  Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods.\\\n",
        "  \"\"\"\n",
        "chapter6_4 = \"\"\" We’d like to change the value to something that brings us closer to a solution; the most obvious approach is to select the value that results in the minimum number of conflicts with other variables—the min-conflicts heuristic.\n",
        "run time of min-conflicts is roughly independent of problem size\\\n",
        "Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment.\n",
        "\n",
        "\"\"\"\n",
        "chapter6_5='a constraint graph is a tree when any two variables are connected by only one path.\\\n",
        "an ordering of the variables such that each variable appears after its parent in the tree. Such an ordering is called a topological sort. \\\n",
        "We can solve any tree decomposition problem in O(nd^2) time\\\n",
        "if a graph has tree width w then the problem can be solved in O(nd^(w+1))\\\n",
        "This is called value symmetry. We would like to reduce the search space by a factor of d! by breaking the symmetry in assignments. We do this by introducing a symmetry-breaking constraint.'\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "' consistent':'CSP problem assignment that does not violate constraint',\n",
        "'complete':'every variable has assignment, solution to CSP is complete and consistent assignment',\n",
        "' unary constraint':'restrict only one variable',\n",
        "'binary constraint ':'rectricts are related with two varaible',\n",
        "'preference constraints':'prefer which solution',\n",
        "'constraint propagation':'using the constraints to reduce the number of legal values for variables',\n",
        "'node-consistent':'k=1(X)',\n",
        "'arc-consistent':'k=2(X,Y)',\n",
        "'AC-3':'enforcing arc consistency,',\n",
        "'minimum-remaining-values heuristic(MRV)':'choosing the variable with the fewest “legal” values',\n",
        "'degree heuristic':'choose variable that influences many other variables',\n",
        "'least-constraining-value heuristic':'prefers the value that rules out the fewest choices for the neighboring variables',\n",
        "' forward checking':'a type of inference, when X is updated, check neighbors of X',\n",
        "'Maintaining Arc Consistency(MAC)':'like AC3, but start with only arcs of (Xi,Xj),Xj neighbors of Xi,not all arcs',\n",
        "'chronological backtracking':'back to last variable just visited',\n",
        "'conflict set':'a set of assignments that are in conflict with some value of X',\n",
        "'backjumping ':'backtracks to the most recent assignment in the conflict set',\n",
        "'constraint weighting':'concentrate on important search'\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n"
      ],
      "execution_count": 29,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "a294dac4-218d-484e-83c1-9932528c7c35"
      },
      "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": 30,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n A problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem, or CSP. CSPs deal with assignments of values to variables, The best-known category of continuous-domain CSPs is that of linear programming problems, where constraints must be linear equalities or inequalities. Linear programming problems can be solved in time polynomial in the number of variables.  CSPs with preferences can be solved with optimization search methods, either path-based or local. We call such a problem a constrained optimization problem, or COP. Linear programs are one class of COPs.Assume a CSP with n variables,domain size at most d and c binary constraints. Each arc can be inserted in the queue only d times.checking an arc O(d^2)time, total O(cd^3)time for planar constraint graphs,O(n^2d^3) in worst case.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.A CSP is k consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\nstrongly k consistent timeO(n^2d) \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n The MRV heuristic usually performs better than a random or static ordering, sometimes by orders of magnitude, although the results vary depending on the problem.The MRV heuristic doesn’t help at all in choosing the first region to color in Australia,In this case, the degree heuristic is useful.  Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods.  \n\n## AIMA Chapter 6.4 Local Search for CSPs\n We’d like to change the value to something that brings us closer to a solution; the most obvious approach is to select the value that results in the minimum number of conflicts with other variables—the min-conflicts heuristic.\nrun time of min-conflicts is roughly independent of problem sizeEach constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment.\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\na constraint graph is a tree when any two variables are connected by only one path.an ordering of the variables such that each variable appears after its parent in the tree. Such an ordering is called a topological sort. We can solve any tree decomposition problem in O(nd^2) timeif a graph has tree width w then the problem can be solved in O(nd^(w+1))This is called value symmetry. We would like to reduce the search space by a factor of d! by breaking the symmetry in assignments. We do this by introducing a symmetry-breaking constraint.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n* ** consistent** - CSP problem assignment that does not violate constraint\n* **Complete** - every variable has assignment, solution to CSP is complete and consistent assignment\n* ** unary constraint** - restrict only one variable\n* **Binary constraint ** - rectricts are related with two varaible\n* **Preference constraints** - prefer which solution\n* **Constraint propagation** - using the constraints to reduce the number of legal values for variables\n* **Node-consistent** - k=1(X)\n* **Arc-consistent** - k=2(X,Y)\n* **Ac-3** - enforcing arc consistency,\n* **Minimum-remaining-values heuristic(mrv)** - choosing the variable with the fewest “legal” values\n* **Degree heuristic** - choose variable that influences many other variables\n* **Least-constraining-value heuristic** - prefers the value that rules out the fewest choices for the neighboring variables\n* ** forward checking** - a type of inference, when X is updated, check neighbors of X\n* **Maintaining arc consistency(mac)** - like AC3, but start with only arcs of (Xi,Xj),Xj neighbors of Xi,not all arcs\n* **Chronological backtracking** - back to last variable just visited\n* **Conflict set** - a set of assignments that are in conflict with some value of X\n* **Backjumping ** - backtracks to the most recent assignment in the conflict set\n* **Constraint weighting** - concentrate on important search\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 = \"\"\"  In AI, knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what actions to take.\\\n",
        "Each time the agent program is called, it does three things. First, it TELLs the knowledge base what it perceives. Second, it ASKs the knowledge base what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on. Third, the agent program TELLs the knowledge base which action was chosen, and returns the action so that it can be executed.\\\n",
        " Starting with an empty knowledge base, the agent designer can TELL sentences one by one until the agent knows how to operate in its environment. This is called the declarative approach to system building. In contrast, the procedural approach encodes desired behaviors directly as program code. \\\n",
        "\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" Note that in each case for which the agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct. This is a fundamental property of logical reasoning. In the rest of this chapter, we describe how to build logical agents that can represent information and draw conclusions such as those described in the preceding paragraphs.\\\n",
        "An inference algorithm that derives only entailed sentences is called sound or truth- preserving. Soundness is a highly desirable property.\\\n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\" If a sentence alpha is true in model m, we say that m satisfies alpha or sometimes m is a model of alpha We use the notation M(alpha) to mean the set of all models of alpha\\\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" implication (or conditional)A->B. Its premise or antecedent is A, and its conclusion or consequent is B\\\n",
        "not operator has highest priority\\\n",
        "Our first algorithm for inference is a model-checking approach that is a direct implementation of the definition of entailment: enumerate the models, and check that\n",
        "is true in every model in which is true.\\\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.\\\n",
        "One such restricted form is the definite clause, which is a disjunction of literals of which exactly one is positive.\\\n",
        "Slightly more general is the Horn clause, which is a disjunction of literals of which at most one is positive.\\\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "'logic':'class of representations to support knowledge-based agents.',\n",
        "'knowledge base':'sentences expressed in knowledge representation language and represent some information about environment',\n",
        "'axiom':'sentence not derived from other sentences',\n",
        "'knowledge level':'what agent knows and what its goals are',\n",
        "'declarative':'tell agent sentences one by one until it works',\n",
        "'procedural ':'contrast to  declarative,use program code to achieve goal',\n",
        "'wumpus world':'cave consisting of rooms connected by passageways',\n",
        "'syntax':'how sentences should be structured',\n",
        "'semantics':'truth of sentence',\n",
        "'model':'possible world',\n",
        "'entailment':'alpha is more specific than beta, if alhpa entails beta',\n",
        "'sound( truth- preserving)':'only derive entailed sentences',\n",
        "'completeness':'derive all entailed sentences',\n",
        "'grounding':'connection between real world and sentences',\n",
        "'atomic sentences':'only single propositional symbol',\n",
        "'literal':'a positive literal or negative literal',\n",
        "' conjunction':'connected by and',\n",
        "' disjunction':'connected by or',\n",
        "'biconditional.':'if and only if',\n",
        "'model checking':'time O(2^n),space O(n),deep-first',\n",
        "'validity(tautologies)':'sentence has validity if it is true in all model',\n",
        "'satisfiability':'a sentence is satisfiable if it is true in some model',\n",
        "' monotonicity':'entailed sentences can only increase as information increase',\n",
        "'CNF ':'sentence expressed in conjunction'\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "7315758f-1701-4976-9a1b-f4cb4cfdb7f8"
      },
      "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": 32,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n  In AI, knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what actions to take.Each time the agent program is called, it does three things. First, it TELLs the knowledge base what it perceives. Second, it ASKs the knowledge base what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on. Third, the agent program TELLs the knowledge base which action was chosen, and returns the action so that it can be executed. Starting with an empty knowledge base, the agent designer can TELL sentences one by one until the agent knows how to operate in its environment. This is called the declarative approach to system building. In contrast, the procedural approach encodes desired behaviors directly as program code. \n \n\n## AIMA Chapter 7.2 The Wumpus World\n Note that in each case for which the agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct. This is a fundamental property of logical reasoning. In the rest of this chapter, we describe how to build logical agents that can represent information and draw conclusions such as those described in the preceding paragraphs.An inference algorithm that derives only entailed sentences is called sound or truth- preserving. Soundness is a highly desirable property. \n\n## AIMA Chapter 7.3 Logic\n If a sentence alpha is true in model m, we say that m satisfies alpha or sometimes m is a model of alpha We use the notation M(alpha) to mean the set of all models of alpha\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n implication (or conditional)A->B. Its premise or antecedent is A, and its conclusion or consequent is Bnot operator has highest priorityOur first algorithm for inference is a model-checking approach that is a direct implementation of the definition of entailment: enumerate the models, and check that\nis true in every model in which is true. \n\n## AIMA 7.5 Propositional Theorem Proving\n If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.One such restricted form is the definite clause, which is a disjunction of literals of which exactly one is positive.Slightly more general is the Horn clause, which is a disjunction of literals of which at most one is positive. \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Logic** - class of representations to support knowledge-based agents.\n* **Knowledge base** - sentences expressed in knowledge representation language and represent some information about environment\n* **Axiom** - sentence not derived from other sentences\n* **Knowledge level** - what agent knows and what its goals are\n* **Declarative** - tell agent sentences one by one until it works\n* **Procedural ** - contrast to  declarative,use program code to achieve goal\n* **Wumpus world** - cave consisting of rooms connected by passageways\n* **Syntax** - how sentences should be structured\n* **Semantics** - truth of sentence\n* **Model** - possible world\n* **Entailment** - alpha is more specific than beta, if alhpa entails beta\n* **Sound( truth- preserving)** - only derive entailed sentences\n* **Completeness** - derive all entailed sentences\n* **Grounding** - connection between real world and sentences\n* **Atomic sentences** - only single propositional symbol\n* **Literal** - a positive literal or negative literal\n* ** conjunction** - connected by and\n* ** disjunction** - connected by or\n* **Biconditional.** - if and only if\n* **Model checking** - time O(2^n),space O(n),deep-first\n* **Validity(tautologies)** - sentence has validity if it is true in all model\n* **Satisfiability** - a sentence is satisfiable if it is true in some model\n* ** monotonicity** - entailed sentences can only increase as information increase\n* **Cnf ** - sentence expressed in conjunction\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": "6da0fd5d-36ab-41bc-ea9d-93a59d38ccd9"
      },
      "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": 33,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Tuning test contains natural language processing,knowledge representation,automated reasoning,machine learning. total Tuning test contains computer vision,robotics. Human thoughts contain introspection,psychological experiments,brain imaging. The rational-agent approach to AI has two advantages over the other approaches. First, it is more general than the “laws of thought” approach because correct inference is just one of several possible mechanisms for achieving rationality. Second, it is more amenable to scientific development. AI has focused on the study and construction of agents that do the right thing. It is impossible to anticipate all the ways in which a machine pursuing a fixed objective might misbehave. There is good reason, then, to think that the standard model is inadequate.We don’t want machines that are intelligent in the sense of pursuing their objectives; we want them to pursue our objectives. \\ \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.we say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action.The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system.\\ \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n but AI has generally stuck to one notion called consequentialism: we evaluate an agent’s behavior by\nits consequences. When an agent is plunked down in an environment, it generates a\nsequence of actions according to the percepts it receives. This sequence of actions causes\nthe environment to go through a sequence of states.Humans have desires and preferences of their own,Machines, on the other hand, do not have desires and preferences of their own;\nWhat is rational at any given time depends on four things:The performance measure that defines the criterion of success.The agent’s prior knowledge of the environment.\nThe actions that the agent can perform.The agent’s percept sequence to date.\n \n\n## AIMA 2.3 The Nature of Environments\n For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.(rational agent defination)hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown. \n\n## AIMA 2.4 The Structure of Agents\n The job of AI is to design an agent program that implements the agent function. We assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture: agent=architecture+program. The key challenge for AI is to find out how to write programs that, to the extent possible, produce rational behavior from a smallish program rather than from a vast table. four basic kinds of agent programs that embody the principles underlying almost all intelligent systems:\nSimple reflex agents; Model-based reflex agents; Goal-based agents; and Utility-based agents.a randomized simple reflex agent might outperform a deterministic simple reflex agent.The most effective way to handle partial observability is for the agent to keep track of the part of the world it can’t see now.That is, the agent should maintain some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved aspects of the current state. Any type of agent (model-based, goal-based, utility-based, etc.) can be built as a learning agent (or not) by using performance element, learning element and problem generator.All agents can improve their performance through learning.\\ \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - acts to achieve the best outcome\n* **Percept** - content that agent detect\n* **Percept sequence** - history of content that agent detect\n* **Value alignment problem** - the value of things to machine must matches with human's thought about value of that thing\n* **Agent function** - abstract concept of what agent is doing\n* **Agent program** - agent=agent program(algorithm)+agent architecture(computer)\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n* **Consequentialism** - only consequence of agent action matters\n* **Information gathering** - doing to modify future percepts\n* **Autonomy** - not rely on prior knowledge, but learn on its own percepts\n* **Peas** - Performance(Goal), Environment(what agent is facing), Actuators(tool of agent to finish goal), Sensors(provide environment information)\n* **Software agent(softbot)** - web site agent\n* **Fully observable** - all relevant information to the choice of action is avaliable\n* **Deterministic** - next state is determined by agent action(nonDeterministic vice versa),in practice nondeterministic is more frequent\n* **Stochastic** - if uncertainty has probability, it is stochastic, otherwise it is nondeterministic\n* **Episodic** - one action a time,next episode does not depend on current action\n* **Sequential** - current action can affect future decisions\n* **Static** - environment cannot change, while dynamic refers to changing environment\n* **Semidynamic** - environment dont change but agent score change\n* **Known** - agent knowledge, not environment, not like fully observable\n* **Simple reflex agent** - just correspond to current percept, ignore history\n* **Transition model of the world** - knowledge of how the world works\n* **Sensor model** - how the state of the world is reflected in the agent percepts\n* **Model-based agent** - transition model + sensor model agent\n* **Goal-based agent** - more flexible, adjusting goal can change agent behavior\n* **Utility-based agent** - agent maximizing expected utility\n* **Performance element** - takes percept and make decision(entire agent)\n* **Learning element** - to make improvement for agent use feedback\n* **Problem generator** - suggest action that lead to new information \n* **Atomic representation** - no internal structure\n* **Factored representation** - splits up each state into a fixed set of variables or attributes,\n* **Structured representation** - objects has inter related relation\n* **Localist representation** - dictionary of concepts and memory location(one to one)\n* **Distributed representation** - concepts and memory location are many to many(robust against information loss)\n* **Good old-fashioned ai (gofai)** - simplest logical agent \n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Counter = defaultdict(int). function uses the same default object each time(eg fib(n,fib={})).function is first class object.[expression for name in list if filter].[a for i in x for j in y] = for i in x: for j in y:\n\n\n## Module 2 Definitions\n* **Mutability** - able to change its content after being defined\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n four-pharse problem-solving: GOAL FORMULATION,PROBLEM FORMULATION,SEARCH,EXECUTION search problem defined by :A set of possible states(state space),initial state,goal states,actions available,transition model,action cost function \n\n\n## AIMA Chapter 3.2 Example Problems\n A standardized problem is intended to illustrate or exercise various problem- solving methods. It can be given a concise, exact description and hence is suitable as a benchmark for researchers to compare the performance of algorithms. A real-world problem, such as robot navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic, not standardized, because, for example, each robot has different sensors that produce different data.\n node of tree has four part:state,parent,action,pathcost. \n\n## AIMA Chapter 3.3 Search Algorithms\n Dijkstra’s algorithm or uniform-cost search is  breadth-first search spreads out in waves of uniform depth—first depth 1, then depth 2, and so onIt expands node with least cost so farA variant of depth-first search called backtracking search uses even less memory.this reduces the memory requirements to just one state description and a path of actions; a significant savings over states for depth-first search.  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Open-loop** - ignore percept that might cause error\n* **Closed-loop** - monitors the percept\n* **Frontier** - list of nodes waited to be expanded\n* **Best first search** - expand node with lowest f(n) score\n* **Graph search** - check redundant path\n* **Tree search** - dont check redundant path\n* **Completeness** - guarantee a solution\n* **Early goal test** - checking whether a node is a solution as soon as it is generated\n* **Late goal test** - waiting until a node is popped off the queue(bfs)\n* **Bfs(fifo)** - complete,optimal,Time:O(b^d),Space:O(b^d),b braching, d depth\n* **Uniform-cost** - Complete,optimal,Time:O(b),Space:O(b)\n* **Dfs(filo)** - not complete,not optimal,Time:O(b^m),Space:O(bm),m depth of tree no solution\n* **Depth-limited** - not complete,not optimal,Time:O(b^l),Space:O(bl)\n* **Iterative deepening** - Complete,optimal,Time:O(b^d),Space:O(bd)\n* **Bidirectional** - complete,optimal,T,S same:O(b^(d/2))\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Greedy best-first search worst-case time and space complexity is O(|V|),With a good heuristic function is O(bm)The most common informed search algorithm is A* search , uses f(n) = g(n) + h(n), g(n)is the path cost from the initial state to node, h(n)is the estimated cost to a goal state,Every consistent heuristic is admissible,If C is the cost of the optimal solution path,surely expanded nodes are   f(n)<C,That A* search is complete, cost-optimal, and optimally efficient among all such algorithmsThe main issue with A* is its use of memory,Memory is split between the frontier and the reached states.Beam search limits the size of the frontier\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \neffective branching factor(b*) = If the total number of nodes generated by A*  is N and the solution depth is d, N+1=1+b*+(b*)^2..+(b*)^dwell-designed heuristic have b* close to 1If a collection of admissible heuristics is available for a problem and none of them is clearly better than the others, which should we choose?,just take max of them \n\n## Module 4 Lecture Notes\n uninformed search use real path cost of cur node to next node, best-first search use estimated path cost to goal.the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\n## Module 4 Definitions\n* **Heristic function** - estimated cost from current state to the goal\n* **Greedy best-first search** - expands first the node with the lowest h(n)value,complete in finite states, not in infinite\n* **A* search** - g(n)+h(n),complete,optimal or not depends on h(n),space O（b^(d-k))\n* **Admissible heuristic** -  never overestimates the cost to reach a goal\n* **Consistency(stronger admissible) of h(n)** - h(n)<= c(n,n')+h(n') for successor of h(n),consistency->admissible,not vice versa\n* **Optimally efficient** - A* expands necessary nodes compared with other algorithm\n* **Satisficing solutions.** - suboptimal solution\n* **Manhattan distance(city-block distance)** - sum of the horizontal and vertical distances\n* **Effective branching factor** -  uniform tree of depth d would have to have in order to contain N nodes.\n* **Dominates** - h1 dominates h2 if h1 uses less nodes to find solution,h2(n)>=h1(n)for all n\n* ** relaxed problem.** - problem with fewer restrictions on the actions \n* **Weighted a*** - expanding fewer nodes, but sacrificing optimality.\n* **Rbfs ** - robust, optimal search algorithms that use limited amounts of memory\n* **Pattern databases** - store these exact solution costs for every possible subproblem instance\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n deterministic, two-player, turn-taking, perfect information, zero-sum games.we often use the term move as a synonym for “action” and position as a synonym for “state.”Game can be defined using four elements:1.initial state2.TO-MOVE(s): The player whose turn it is to move in state .\n3.ACTIONS(s):The set of legal moves in state .\n4.RESULT(s,a):The transition model, which defines the state resulting from taking action a in state s\n5.IS-TERMINAL(s):A terminal test, which is true when the game is over and false otherwise.States where the game has ended are called terminal states.\n6.UTILITY(s,p):A utility function (also called an objective function or payoff function), which defines the final numeric value to player when the game ends in terminal statewe can superimpose a search tree over part of that graph to determine what move to make.\\ \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n  For games with multiple outcome scores, we need a slightly more general algorithm called minimax search.Given a game tree, the optimal strategy can be determined by working out the minimax value of each state in the tree If the maximum depth of the tree is and there are legal moves at each point, Time:O(b^m),Space:O(bm) If this could be done perfectly, alpha–beta would need to examine only O(b^(m/2)),instead O(b^m)for minimax With random move ordering, the total number of nodes examined will be roughlyO(b^(3m/4)) Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth. It explores a wide but shallow portion of the tree.  A Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion\\  \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Eval(s,p) returns an estimate of the expected utility of state s to player p,For terminal states, Eval(s,p)=Utility(s,p),for nonterminal, Utility(loss,p)<=Eval(s,p)<=Utility(win,p) Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation, but forward pruning prunes moves that appear to be poor moves, but might possibly be good ones.  \n\n## AIMA Chapter 5.5 Stochastic Games\n f the program knew in advance all the dice rolls that would occur for the rest of the game, solving a game with dice would be just like solving a game without dice, which minimax does in O(b^m) time, where is the branching factor and is the maximum depth of the game tree. Because expectiminimax is also considering all the possible dice-roll sequences, it will takeO(b^m n^m) , where is the number of distinct rolls. \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n maximum expected utility (MEU) says that a rational agent should choose the action that maximizes the agent’s expected utility:\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n If an agent’s preferences obey the axioms of utility, then there exists a function such thatU(A)>U(B) if and only if is A preferred to B,As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal utility function. \n\n## AIMA Chapter 16.3 Utility Functions\n If we want to build a decision-theoretic system that helps a human make decisions or acts\non his or her behalf, we must first work out what the human’s utility function is. This\nprocess, often called preference elicitation, involves presenting choices to the human and \nusing the observed preferences to pin down the underlying utility function \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Minimax** - time:O(b^m)space:O(bm)for generates all actions at once,O(m) for generates actions one at a time\n* **Competitive environments** - more than one agents, compete for goal\n* **Pruning** - igonre unnecessary nodes\n* **Imperfect information** - not all information is visible to players\n* **Perfect information** - synonym for fully obervable\n* **Quiescent** - positions in which there is no pending move that changes evaluation too much\n* **Quiescence search ** - consider only certain types of moves, such as capture moves\n* **Horizon effect** - unavoidable damaging move\n* **Singular extensions** - moves that are “clearly better”,delay horizon effect\n* **Forward pruning** - runes moves that appear to be poor moves, but might be good\n* **Orderability** - one of A>B,A<B,A~B holds\n* **Transitivity** - A>B and B>C -> A>C\n* **Continuity** - A>B>C-> [p,A,1-p,C]~B for some p\n* **Substitutability:** - A~B->[p,A,1-p,C]~[p,B,1-p,C]\n* **Monotonicity** - A>B->(p>q<->[p,A,1-p,B]>[q,A,1-q,B])\n* **Decomposability** - [p,A;1-p,[q,B,1-q,C]]~[p,A;,(1-p)q,B;(1-p)(1-q),C]\n* **Value function** - number of utility not matter, order matters\n* **Normalized utilities** - 0<=u<=1\n* **Certainty equivalent** - certain value of lottery\n* **Framing effect** - people like positive describtion(90%survival rate > 10% death rate)\n* **Anchoring effect** - people value stuff compared with other stuff\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n A problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem, or CSP. CSPs deal with assignments of values to variables, The best-known category of continuous-domain CSPs is that of linear programming problems, where constraints must be linear equalities or inequalities. Linear programming problems can be solved in time polynomial in the number of variables.  CSPs with preferences can be solved with optimization search methods, either path-based or local. We call such a problem a constrained optimization problem, or COP. Linear programs are one class of COPs.Assume a CSP with n variables,domain size at most d and c binary constraints. Each arc can be inserted in the queue only d times.checking an arc O(d^2)time, total O(cd^3)time for planar constraint graphs,O(n^2d^3) in worst case.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.A CSP is k consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.\nstrongly k consistent timeO(n^2d) \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n The MRV heuristic usually performs better than a random or static ordering, sometimes by orders of magnitude, although the results vary depending on the problem.The MRV heuristic doesn’t help at all in choosing the first region to color in Australia,In this case, the degree heuristic is useful.  Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination of assignments or by keeping a separate cache of no-goods.  \n\n## AIMA Chapter 6.4 Local Search for CSPs\n We’d like to change the value to something that brings us closer to a solution; the most obvious approach is to select the value that results in the minimum number of conflicts with other variables—the min-conflicts heuristic.\nrun time of min-conflicts is roughly independent of problem sizeEach constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. The weights are then adjusted by incrementing the weight of each constraint that is violated by the current assignment.\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\na constraint graph is a tree when any two variables are connected by only one path.an ordering of the variables such that each variable appears after its parent in the tree. Such an ordering is called a topological sort. We can solve any tree decomposition problem in O(nd^2) timeif a graph has tree width w then the problem can be solved in O(nd^(w+1))This is called value symmetry. We would like to reduce the search space by a factor of d! by breaking the symmetry in assignments. We do this by introducing a symmetry-breaking constraint.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n* ** consistent** - CSP problem assignment that does not violate constraint\n* **Complete** - every variable has assignment, solution to CSP is complete and consistent assignment\n* ** unary constraint** - restrict only one variable\n* **Binary constraint ** - rectricts are related with two varaible\n* **Preference constraints** - prefer which solution\n* **Constraint propagation** - using the constraints to reduce the number of legal values for variables\n* **Node-consistent** - k=1(X)\n* **Arc-consistent** - k=2(X,Y)\n* **Ac-3** - enforcing arc consistency,\n* **Minimum-remaining-values heuristic(mrv)** - choosing the variable with the fewest “legal” values\n* **Degree heuristic** - choose variable that influences many other variables\n* **Least-constraining-value heuristic** - prefers the value that rules out the fewest choices for the neighboring variables\n* ** forward checking** - a type of inference, when X is updated, check neighbors of X\n* **Maintaining arc consistency(mac)** - like AC3, but start with only arcs of (Xi,Xj),Xj neighbors of Xi,not all arcs\n* **Chronological backtracking** - back to last variable just visited\n* **Conflict set** - a set of assignments that are in conflict with some value of X\n* **Backjumping ** - backtracks to the most recent assignment in the conflict set\n* **Constraint weighting** - concentrate on important search\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n  In AI, knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what actions to take.Each time the agent program is called, it does three things. First, it TELLs the knowledge base what it perceives. Second, it ASKs the knowledge base what action it should perform. In the process of answering this query, extensive reasoning may be done about the current state of the world, about the outcomes of possible action sequences, and so on. Third, the agent program TELLs the knowledge base which action was chosen, and returns the action so that it can be executed. Starting with an empty knowledge base, the agent designer can TELL sentences one by one until the agent knows how to operate in its environment. This is called the declarative approach to system building. In contrast, the procedural approach encodes desired behaviors directly as program code. \n \n\n## AIMA Chapter 7.2 The Wumpus World\n Note that in each case for which the agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct. This is a fundamental property of logical reasoning. In the rest of this chapter, we describe how to build logical agents that can represent information and draw conclusions such as those described in the preceding paragraphs.An inference algorithm that derives only entailed sentences is called sound or truth- preserving. Soundness is a highly desirable property. \n\n## AIMA Chapter 7.3 Logic\n If a sentence alpha is true in model m, we say that m satisfies alpha or sometimes m is a model of alpha We use the notation M(alpha) to mean the set of all models of alpha\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n implication (or conditional)A->B. Its premise or antecedent is A, and its conclusion or consequent is Bnot operator has highest priorityOur first algorithm for inference is a model-checking approach that is a direct implementation of the definition of entailment: enumerate the models, and check that\nis true in every model in which is true. \n\n## AIMA 7.5 Propositional Theorem Proving\n If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause.One such restricted form is the definite clause, which is a disjunction of literals of which exactly one is positive.Slightly more general is the Horn clause, which is a disjunction of literals of which at most one is positive. \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Logic** - class of representations to support knowledge-based agents.\n* **Knowledge base** - sentences expressed in knowledge representation language and represent some information about environment\n* **Axiom** - sentence not derived from other sentences\n* **Knowledge level** - what agent knows and what its goals are\n* **Declarative** - tell agent sentences one by one until it works\n* **Procedural ** - contrast to  declarative,use program code to achieve goal\n* **Wumpus world** - cave consisting of rooms connected by passageways\n* **Syntax** - how sentences should be structured\n* **Semantics** - truth of sentence\n* **Model** - possible world\n* **Entailment** - alpha is more specific than beta, if alhpa entails beta\n* **Sound( truth- preserving)** - only derive entailed sentences\n* **Completeness** - derive all entailed sentences\n* **Grounding** - connection between real world and sentences\n* **Atomic sentences** - only single propositional symbol\n* **Literal** - a positive literal or negative literal\n* ** conjunction** - connected by and\n* ** disjunction** - connected by or\n* **Biconditional.** - if and only if\n* **Model checking** - time O(2^n),space O(n),deep-first\n* **Validity(tautologies)** - sentence has validity if it is true in all model\n* **Satisfiability** - a sentence is satisfiable if it is true in some model\n* ** monotonicity** - entailed sentences can only increase as information increase\n* **Cnf ** - sentence expressed in conjunction\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dS90bdGVFK3T"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}