{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "“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": "90858213-e352-43cd-e297-46a2baf175f0"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0fba2813-5f70-45b4-a740-0e496effad3c"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "computer need capabilities: natural language processing,knowledge representation,automated reasoning,machine learning,computer vision,robotics\\\n",
        "hm thoughts: introspection,psychological experiments,brain imaging\\\n",
        " AI:study and construction of agents that do right thing\\\n",
        "A rational agent is one that acts so as to achieve the best outcome or,\\\n",
        " when there is uncertainty, the best expected outcome\n",
        "\n",
        " \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" qualification problem:difficult to capture every contingency of appropriate behavior in a\n",
        "set of necessary and sufficient logical rules;\n",
        "The embodied cognition approach:it makes no sense to consider the brain\n",
        "separately: cognition takes place within a body, which is embedded in an environment.\n",
        "Turing test:The test requires a\n",
        "program to have a conversation with an interrogator for five minutes.\n",
        "The interrogator then has to guess if the conversation is with a program or a person;\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" Running through all the debates about strong AI is the issue of consciousness: awareness of\n",
        "the outside world, and of the self, and the subjective experience of living. The technical term\n",
        "for the intrinsic nature of experiences is qualia\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"the agent function for an artificial agent will be\n",
        "implemented by an agent program;The\n",
        "agent function is an abstract mathematical description; the agent program is a concrete\n",
        "implementation, running within some physical system.\"\"\"\n",
        "chapter2_2 = \"\"\" Omniscience(no):An omniscient\n",
        "agent knows the actual outcome of its actions and can act accordingly; learning(not only gather), and autonomy:it should learn what it can to compensate for partial or\n",
        "incorrect prior knowledge;\n",
        "definition of a rational agent:\n",
        "For each possible percept sequence, a rational agent should select an action that is expected to\n",
        "maximize its performance measure, given the evidence provided by the percept sequence and\n",
        "whatever built-in knowledge the agent has.\n",
        " \"\"\"\n",
        "chapter2_3 = \"\"\" group task environment: PEAS (Performance, Environment, Actuators, Sensors)\\\n",
        "Properties of task environments: FULLY OBSERVABLE /PARTIALLY OBSERVABLE \\\n",
        "detect all aspects that are relevant to the choice of action\\\n",
        "SINGLE-AGENT VS. MULTIAGENT\\\n",
        "Deterministic vs. nondeterministic.\\\n",
        "EPISODIC VS. SEQUENTIAL\\\n",
        "STATIC VS. DYNAMIC\\\n",
        "DISCRETE VS. CONTINUOUS\\\n",
        "\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" agent = architecture + program \\n\n",
        "agent program take the current percept as input from the sensors, return action to the actuators. \\n\n",
        "agent function, which may depend on the entire percept history. \\n\n",
        "four basic kinds of agent programs:\\n\n",
        "Simple reflex agents;(current percept, ignoring percept history.) \\n\n",
        "Model-based reflex agents(maintain some internal state depends on history; \n",
        "transition model:This knowledge about “how the world works-simple Boolean circuits/in complete scientific theories \\n\n",
        "sensor model:how world state reflect in percepts.);\\n\n",
        "Goal-based agents(Search and planning are the subfields of AI finding action sequences that achieve goals.); \\n\n",
        "Utility-based agents(utility:the quality of being useful;  expected utility:utility the agent expects to derive,given the probabilities and utilities of each\n",
        "outcome. utility function:internalization of the performance measure, chooses actions to maximize its utility by external performance measure.).\\n\n",
        "not all utility-based agents are model-based\\n\n",
        "Any type of agent (model-based, goal-based, utility-based, etc.) can as learning agent (or not).\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "Agents include humans, robots, softbots, thermostats, ...\\n\n",
        "It is better to design performance measures according to what you want to be achieved in the environment, rather than how you think the agent should behave.\\n\n",
        "How do we know if an agent is acting rationally? do the right thing in all circumstances.\n",
        "How do we know if it’s doing the right thing?\n",
        "We define a performance measure: An objective criterion for success of an agent's behavior/given the evidence provided by the percept sequence.\n",
        "The hardest case isContinuous Partially Observable Stochastic Multiagent\\n\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"content agent’s sensors perceive\",\n",
        "\"agent function\" : \"maps any given percept sequence to an action/abstract mathematical description\",\n",
        "\"agent program\": \"concrete implementation, running within some physical system.\",\n",
        "\"rational agent\": \" select an action maximize maximizes expected performance\",\n",
        " \"task environments\":\"rational agents are the “solutions\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1341
        },
        "outputId": "143b737d-db08-4cf2-fec4-c314c2daa593"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\ncomputer need capabilities: natural language processing,knowledge representation,automated reasoning,machine learning,computer vision,roboticshm thoughts: introspection,psychological experiments,brain imaging AI:study and construction of agents that do right thingA rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n qualification problem:difficult to capture every contingency of appropriate behavior in a\nset of necessary and sufficient logical rules;\nThe embodied cognition approach:it makes no sense to consider the brain\nseparately: cognition takes place within a body, which is embedded in an environment.\nTuring test:The test requires a\nprogram to have a conversation with an interrogator for five minutes.\nThe interrogator then has to guess if the conversation is with a program or a person;\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Running through all the debates about strong AI is the issue of consciousness: awareness of\nthe outside world, and of the self, and the subjective experience of living. The technical term\nfor the intrinsic nature of experiences is qualia\n\n## AIMA 2.1 Agents and Environments\nthe agent function for an artificial agent will be\nimplemented by an agent program;The\nagent function is an abstract mathematical description; the agent program is a concrete\nimplementation, running within some physical system.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Omniscience(no):An omniscient\nagent knows the actual outcome of its actions and can act accordingly; learning(not only gather), and autonomy:it should learn what it can to compensate for partial or\nincorrect prior knowledge;\ndefinition of a rational agent:\nFor each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has.\n \n\n## AIMA 2.3 The Nature of Environments\n group task environment: PEAS (Performance, Environment, Actuators, Sensors)Properties of task environments: FULLY OBSERVABLE /PARTIALLY OBSERVABLE detect all aspects that are relevant to the choice of actionSINGLE-AGENT VS. MULTIAGENTDeterministic vs. nondeterministic.EPISODIC VS. SEQUENTIALSTATIC VS. DYNAMICDISCRETE VS. CONTINUOUS\n\n\n## AIMA 2.4 The Structure of Agents\n agent = architecture + program \n\nagent program take the current percept as input from the sensors, return action to the actuators. \n\nagent function, which may depend on the entire percept history. \n\nfour basic kinds of agent programs:\n\nSimple reflex agents;(current percept, ignoring percept history.) \n\nModel-based reflex agents(maintain some internal state depends on history; \ntransition model:This knowledge about “how the world works-simple Boolean circuits/in complete scientific theories \n\nsensor model:how world state reflect in percepts.);\n\nGoal-based agents(Search and planning are the subfields of AI finding action sequences that achieve goals.); \n\nUtility-based agents(utility:the quality of being useful;  expected utility:utility the agent expects to derive,given the probabilities and utilities of each\noutcome. utility function:internalization of the performance measure, chooses actions to maximize its utility by external performance measure.).\n\nnot all utility-based agents are model-based\n\nAny type of agent (model-based, goal-based, utility-based, etc.) can as learning agent (or not).\n\n\n\n## Module 1 Lecture Notes\n \nAgents include humans, robots, softbots, thermostats, ...\n\nIt is better to design performance measures according to what you want to be achieved in the environment, rather than how you think the agent should behave.\n\nHow do we know if an agent is acting rationally? do the right thing in all circumstances.\nHow do we know if it’s doing the right thing?\nWe define a performance measure: An objective criterion for success of an agent's behavior/given the evidence provided by the percept sequence.\nThe hardest case isContinuous Partially Observable Stochastic Multiagent\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content agent’s sensors perceive\n* **Agent function** - maps any given percept sequence to an action/abstract mathematical description\n* **Agent program** - concrete implementation, running within some physical system.\n* **Rational agent** -  select an action maximize maximizes expected performance\n* **Task environments** - rational agents are the “solutions\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 = \"\"\" All data treated as objects:An object is deleted (by garbage collection) once unreachable.\\n\n",
        "Strong Typing:Every object has a fixed type, interpreter doesn’t allow things incompatible with that type (eg. “foo” + 2)\\n\n",
        "Python: dynamic typing: If assigned again, type(var) is updated;Drawback: type errors are only caught at runtime\\n\n",
        "Strings: Prefixing with r means raw:No need to escape special characters: r’\\n’;\n",
        "String formatting: Special use of ‘%’ (as in printf in C) print(\"%s can speak %d languages\" % (\"C3PO\", 6000000));Immutable\\n\n",
        "\n",
        "Sequence Types: 1.Tuple: A simple immutable ordered sequence of items Immutable: a tuple cannot be modified once created Items can be of mixed types, including collection types\\n\n",
        "2.Strings Immutable:Regular strings are Unicode and use 2-byte characters (Regular strings in Python 2 use 8-bit characters)\n",
        "3.List:Mutable ordered sequence of items of mixed types\n",
        "li.reverse()reverse the list *in place* (modify)\\n\n",
        "li.sort() sort the list *in place*; sorted(li) #return a *copy* sorted\\n\n",
        "Dictionaries:keys must be immutable;d.items():List of item tuples.from collections import defaultdict,Counter d = defaultdict(str)/ d = Counter()\\n\n",
        "function Multiple Return Values:tuple; No Function Overloading;operator overloading (overloading +,-) is possible using methods in a class; Non-default argument should always precede default arguments; otherwise, it reports SyntaxError;Functions can be called with arguments out of order\\n \n",
        "accept a variable number of non-keyword arguments to function:\n",
        ">>> def myfun(b, c=3, d=\"hello\"):\\n\n",
        "return b + c\\n\n",
        "\n",
        ">>> myfun(5,3,\"bob\")\\n\n",
        ">>> myfun(5,3)\\n\n",
        "\n",
        "Keyword arguments can be used after all other arguments:like:\n",
        ">>> def myfun(a, b, c):\\n\n",
        "     return a – b\\n\n",
        ">>> myfun(c=43, b=1, a=2)\\n\n",
        ">>> myfun(2, c=43, b=1)\\n\n",
        ">>> myfun(a=2, b=3, 5)(error)\\n\n",
        "eg.\n",
        "def print_everything(*args):args is a tuple of arguments passed to the fn. print(args)\\n\n",
        "print_everything('a', 'b', 'c’)->('a', 'b', 'c’);lst = ['a', 'b', 'c’]print_everything(*lst)->('a', 'b', 'c')\\n\n",
        "Suppose you want to accept a variable number of keyword arguments to your function. def print_keyword_args(**kwargs):# kwargs is a dict of the keyword args passed to the fn. print(kwargs)\\n\n",
        "print_keyword_args(first_name=\"John\", last_name=\"Doe\")-> {'first_name': 'John', 'last_name': 'Doe’}; my_dict = {'first_name': 'Wei', 'last_name': 'Xu’} print_keyword_args(**my_dict)->{'first_name': 'Wei', 'last_name': 'Xu'}\n",
        "Subclasses:eg.class AI_Student(Student)\n",
        "\n",
        "\n",
        "Generators:Good for aggregating (summing, counting) items. One pass. Crucial for infinite sequences;Bad if you need to inspect the individual values\n",
        "   def merge(l, r):\n",
        "      llen = len(l)\n",
        "      rlen = len(r)\n",
        "      i=0\n",
        "      j=0\n",
        "      while i < llen or j < rlen:\\n\n",
        "                if j == rlen or (i < llen and l[i] < r[j]):\\n\n",
        "                    yield l[i]\n",
        "                    i += 1\n",
        "                else:\\n\n",
        "                    yield r[j]\n",
        "                    j += 1\n",
        "                  \\n\n",
        "[x for x in merge([1,3,5],[2,4])]\n",
        "\"First class object\" : \"can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in the programming language have\"\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "C4naMWQP72v2"
      },
      "source": [
        "a=tuple('sw')\n",
        "a=a+({1},{2})\n",
        "a"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1142
        },
        "outputId": "13c1d26f-8c74-40f1-fc8c-3b8ca63118d3"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n All data treated as objects:An object is deleted (by garbage collection) once unreachable.\n\nStrong Typing:Every object has a fixed type, interpreter doesn’t allow things incompatible with that type (eg. “foo” + 2)\n\nPython: dynamic typing: If assigned again, type(var) is updated;Drawback: type errors are only caught at runtime\n\nStrings: Prefixing with r means raw:No need to escape special characters: r’\n’;\nString formatting: Special use of ‘%’ (as in printf in C) print(\"%s can speak %d languages\" % (\"C3PO\", 6000000));Immutable\n\n\nSequence Types: 1.Tuple: A simple immutable ordered sequence of items Immutable: a tuple cannot be modified once created Items can be of mixed types, including collection types\n\n2.Strings Immutable:Regular strings are Unicode and use 2-byte characters (Regular strings in Python 2 use 8-bit characters)\n3.List:Mutable ordered sequence of items of mixed types\nli.reverse()reverse the list *in place* (modify)\n\nli.sort() sort the list *in place*; sorted(li) #return a *copy* sorted\n\nDictionaries:keys must be immutable;d.items():List of item tuples.from collections import defaultdict,Counter d = defaultdict(str)/ d = Counter()\n\nfunction Multiple Return Values:tuple; No Function Overloading;operator overloading (overloading +,-) is possible using methods in a class; Non-default argument should always precede default arguments; otherwise, it reports SyntaxError;Functions can be called with arguments out of order\n \naccept a variable number of non-keyword arguments to function:\n>>> def myfun(b, c=3, d=\"hello\"):\n\nreturn b + c\n\n\n>>> myfun(5,3,\"bob\")\n\n>>> myfun(5,3)\n\n\nKeyword arguments can be used after all other arguments:like:\n>>> def myfun(a, b, c):\n\n     return a – b\n\n>>> myfun(c=43, b=1, a=2)\n\n>>> myfun(2, c=43, b=1)\n\n>>> myfun(a=2, b=3, 5)(error)\n\neg.\ndef print_everything(*args):args is a tuple of arguments passed to the fn. print(args)\n\nprint_everything('a', 'b', 'c’)->('a', 'b', 'c’);lst = ['a', 'b', 'c’]print_everything(*lst)->('a', 'b', 'c')\n\nSuppose you want to accept a variable number of keyword arguments to your function. def print_keyword_args(**kwargs):# kwargs is a dict of the keyword args passed to the fn. print(kwargs)\n\nprint_keyword_args(first_name=\"John\", last_name=\"Doe\")-> {'first_name': 'John', 'last_name': 'Doe’}; my_dict = {'first_name': 'Wei', 'last_name': 'Xu’} print_keyword_args(**my_dict)->{'first_name': 'Wei', 'last_name': 'Xu'}\nSubclasses:eg.class AI_Student(Student)\n\n\nGenerators:Good for aggregating (summing, counting) items. One pass. Crucial for infinite sequences;Bad if you need to inspect the individual values\n   def merge(l, r):\n      llen = len(l)\n      rlen = len(r)\n      i=0\n      j=0\n      while i < llen or j < rlen:\n\n                if j == rlen or (i < llen and l[i] < r[j]):\n\n                    yield l[i]\n                    i += 1\n                else:\n\n                    yield r[j]\n                    j += 1\n                  \n\n[x for x in merge([1,3,5],[2,4])]\n\"First class object\" : \"can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in the programming language have\"\n\n\n## Module 2 Definitions\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5Ra-egFdZmD6",
        "outputId": "6d7b88fd-3d7f-4893-e745-d1addf658b27"
      },
      "source": [
        "l=[7,1,4,6]\n",
        "l.sort()\n",
        "l"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 4, 6, 7]"
            ]
          },
          "metadata": {},
          "execution_count": 20
        }
      ]
    },
    {
      "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 = \"\"\"  problem-solving process:\\n\n",
        "GOAL FORMULATION,PROBLEM FORMULATION,SEARCH,SEARCH,EXECUTION\\n\n",
        "search problem:  state space, initial state, goal states, actions, transition model, action cost function\\n\n",
        " Infinite state spaces in tasks involving mathematical expressions generation, circuits, proofs, programs, and other recursively defined objects.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" traveling salesperson problem (TSP) is a touring problem in which every\n",
        "city on a map must be visited. \n",
        " The layout problem comes after the logical design phase and is usually\n",
        "split into two parts: cell layout and channel routing.\n",
        "Automatic assembly sequencing: first find a feasible assembly\n",
        "sequence and then work to optimize the process.\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\" cycle -redundant path, three approaches to this issue:1.remember all previously reached states \n",
        "2.not reach the same state. call a search algorithm a graph search if it checks for\n",
        "redundant paths and a tree-like search if it does not check.\\n\n",
        "remove references to reached=tree-like search:uses less memory but examine redundant paths to the same state and run slower.\\n\n",
        "3. follow up the chain of parents to see if the state at the end of the path has appeared earlier in the path.\\n\n",
        "denotes:\\n\n",
        "d: depth or number of actions in an optimal solution\\n\n",
        "m: the maximum number of actions in any path\\n\n",
        "b:the branching factor or number of successors of a node that need to be considered.\\n\n",
        "\n",
        " best-first search: in which we choose a node, with minimum value of some evaluation function f(n),\n",
        "\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"  Uninformed Search Strategies: Breadth-first search:\\n\n",
        "early goal test, checking whether a node is a solution when generated, rather than late that best-first search uses, waiting until a node is popped off the queue.\\n\n",
        " space complexity:O($b^d$)\\n\n",
        " uniform-cost/Dijkstra’s algorithm：actions have different costs：BEST-FIRST- SEARCH with PATH-COST(root to the current)\\n\n",
        " complete and is cost-optimal.\\n\n",
        " Depth-first search:\\n\n",
        " A variant of depth-first search called backtracking search uses even less memory.\\n\n",
        "  In backtracking, only one successor is generated at a time\n",
        "rather than all successors; each partially expanded node remembers which successor to\n",
        "generate next. In addition, successors are generated by modifying the current state\n",
        "description directly rather than allocating memory for a brand-new state. reduces the\n",
        "memory requirements to O(m) just one state description and a path of actions;check for a cyclic path in time O(1)rather than O(m)\\n\n",
        " space complexity:O($bd$)\\n\n",
        " \n",
        " iterative deepening:\\n\n",
        "space complexity:O($bd$),O($bm$)no solution \\n\n",
        "iterative deepening is optimal (actions same cost),\n",
        "and is complete on finite acyclic state spaces, or on any finite state space when we check\n",
        "The time complexity O($b^d$)have solution, or O($b^m$) when none.\\n\n",
        "Bidirectional search\\n\n",
        "The time complexity O($b^{d/2}+b^{d/2}$)\n",
        "\n",
        "  \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"Graph search :Search Tree ->Simple Mod from tree search: Check to see if a node has been visited before adding to search queue\n",
        "must keep track of all possible states(cause a lot of memory)\\n\n",
        "Criterion Breadth- Depth- Depth-limited Iterative deepening \\n\n",
        "Complete?YES NO NO YES\\n\n",
        "Time $b^d$ $b^m$ $b^l$ $b^d$\\n\n",
        "Space $b^d$ $bm$ $bl$ $bd$\\n\n",
        "Optimal?YES NO NO YES\n",
        "\n",
        "  \n",
        " \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"can formulate a plan via search\",    \n",
        "\"search\" : \" a sequence of actions that form a path to a goal state\", \n",
        "\n",
        "\"informed algorithms\" :\"can estimate how far it is from the goal\",\n",
        "\"Uninformed search\": \"All non-goal nodes in frontier look equally\",\n",
        "\"Informed search\": \"Some non-goal nodes can be ranked above others.\"\n",
        "# open-loop system: ignoring the percepts breaks the loop between agent and environment.\n",
        "# uninformed search algorithm:no clue about how close a state is to the goal(s).\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1383
        },
        "outputId": "4615417e-00b3-4d64-d3da-18057faa73d2"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n  problem-solving process:\n\nGOAL FORMULATION,PROBLEM FORMULATION,SEARCH,SEARCH,EXECUTION\n\nsearch problem:  state space, initial state, goal states, actions, transition model, action cost function\n\n Infinite state spaces in tasks involving mathematical expressions generation, circuits, proofs, programs, and other recursively defined objects.\n\n\n## AIMA Chapter 3.2 Example Problems\n traveling salesperson problem (TSP) is a touring problem in which every\ncity on a map must be visited. \n The layout problem comes after the logical design phase and is usually\nsplit into two parts: cell layout and channel routing.\nAutomatic assembly sequencing: first find a feasible assembly\nsequence and then work to optimize the process.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n cycle -redundant path, three approaches to this issue:1.remember all previously reached states \n2.not reach the same state. call a search algorithm a graph search if it checks for\nredundant paths and a tree-like search if it does not check.\n\nremove references to reached=tree-like search:uses less memory but examine redundant paths to the same state and run slower.\n\n3. follow up the chain of parents to see if the state at the end of the path has appeared earlier in the path.\n\ndenotes:\n\nd: depth or number of actions in an optimal solution\n\nm: the maximum number of actions in any path\n\nb:the branching factor or number of successors of a node that need to be considered.\n\n\n best-first search: in which we choose a node, with minimum value of some evaluation function f(n),\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n  Uninformed Search Strategies: Breadth-first search:\n\nearly goal test, checking whether a node is a solution when generated, rather than late that best-first search uses, waiting until a node is popped off the queue.\n\n space complexity:O($b^d$)\n\n uniform-cost/Dijkstra’s algorithm：actions have different costs：BEST-FIRST- SEARCH with PATH-COST(root to the current)\n\n complete and is cost-optimal.\n\n Depth-first search:\n\n A variant of depth-first search called backtracking search uses even less memory.\n\n  In backtracking, only one successor is generated at a time\nrather than all successors; each partially expanded node remembers which successor to\ngenerate next. In addition, successors are generated by modifying the current state\ndescription directly rather than allocating memory for a brand-new state. reduces the\nmemory requirements to O(m) just one state description and a path of actions;check for a cyclic path in time O(1)rather than O(m)\n\n space complexity:O($bd$)\n\n \n iterative deepening:\n\nspace complexity:O($bd$),O($bm$)no solution \n\niterative deepening is optimal (actions same cost),\nand is complete on finite acyclic state spaces, or on any finite state space when we check\nThe time complexity O($b^d$)have solution, or O($b^m$) when none.\n\nBidirectional search\n\nThe time complexity O($b^{d/2}+b^{d/2}$)\n\n  \n\n## Module 3 Lecture Notes\nGraph search :Search Tree ->Simple Mod from tree search: Check to see if a node has been visited before adding to search queue\nmust keep track of all possible states(cause a lot of memory)\n\nCriterion Breadth- Depth- Depth-limited Iterative deepening \n\nComplete?YES NO NO YES\n\nTime $b^d$ $b^m$ $b^l$ $b^d$\n\nSpace $b^d$ $bm$ $bl$ $bd$\n\nOptimal?YES NO NO YES\n\n  \n \n\n## Module 3 Definitions\n* **Problem-solving agent** - can formulate a plan via search\n* **Search** -  a sequence of actions that form a path to a goal state\n* **Informed algorithms** - can estimate how far it is from the goal\n* **Uninformed search** - All non-goal nodes in frontier look equally\n* **Informed search** - Some non-goal nodes can be ranked above others.\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 = \"\"\" Informed (Heuristic) Search Strategies:\\n\n",
        "Greedy best-first search:(f(n) = h(n))\\n\n",
        "straight-line distance heuristic  complete in finite state spaces\\n\n",
        "space complexity is (V)->(bm)\n",
        " A* search:best-first search with f(n)=g(n)+h(n)\\n\n",
        "cost-optimal: 1.admissible heuristic is one that never overestimates the cost to reach a goal. 2. consistency.Every consistent heuristic is admissible (but not vice versa)\n",
        "\n",
        " In fact, the term “monotonic heuristic” is a synonym for “consistent heuristic.” The two ideas were developed independently, and\n",
        "then it was proved that they are equivalent\n",
        "\n",
        "A* is efficient because it prunes away search tree nodes that are not necessary for finding\n",
        "an optimal solution.\n",
        "\n",
        "That A* search is complete, cost-optimal, and optimally efficient among all such algorithms\n",
        "is rather satisfying.\\n\n",
        "\n",
        "A* search has many good qualities, but it expands a lot of nodes. We can explore fewer\n",
        "nodes (taking less time and space) if we are willing to accept solutions that are suboptimal,\n",
        "but are “good enough”—what we call satisficing solutions.\n",
        "\n",
        "consider new algorithms that are designed to conserve memory usage.\n",
        "Beam search limits the size of the frontier.->incomplete and suboptimal,good near-optimal solutions\n",
        "Iterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth\u0002first.\n",
        "RBFS resembles a recursive depth\u0002first search, but rather than continuing indefinitely down the current path, it uses the _limit\n",
        "variable to keep track of the -value of the best alternative path available from any ancestor\n",
        "of the current node.\n",
        "RBFS is somewhat more efficient than IDA*, but still suffers from excessive node regeneration.\n",
        "SMA* always drops the worst leaf node—the one with the highest -value.\n",
        "\n",
        "Some bidirectional heuristic search algorithms \n",
        "manage a queue of pairs, but we will stick with bidirectional best-first search (Figure\n",
        "3.14 ), which has two frontier priority queues, and give it an evaluation function that\n",
        "mimics the criteria:f2(n) = max(2g(n), g(n) + h(n))\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" the distance is the sum of the horizontal and vertical distances - city-block distance or Manhattan distance. the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\\n\n",
        "$b^*$ close to 1, allowing fairly large problems to be solved at reasonable computational cost.\\n\n",
        "h2(n) ≥ h1(n).$h^2$ dominates $h^1$-efficiency \n",
        "\n",
        "the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n",
        "\n",
        "h(n) = max{h1(n),… , hk(n)}.This composite heuristic picks whichever function is most accurate on the node in question.\n",
        "\n",
        "The idea behind pattern databases is to store these exact solution costs for every possible\n",
        "subproblem instance\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" A* search: g(n) + h(n) (W = 1) Uniform-cost search: g(n) (W = 0) Greedy best-first search: h(n) (W = ∞)\n",
        "A* search(complete):The algorithm doesn’t end until we “expand” the goal node – it has to be at the top of the Frontier queue.\n",
        "Uninformed search methods have access only to the problem definition. Algorithms\n",
        "build a search tree in an attempt to find a solution. Algorithms differ based on which\n",
        "node they expand first:\n",
        "– BEST-FIRST SEARCH selects nodes for expansion using to an evaluation function.\n",
        "– BREADTH-FIRST SEARCH expands the shallowest nodes first; it is complete,\n",
        "optimal for unit action costs, but has exponential space complexity.\\n\n",
        "– UNIFORM-COST SEARCH expands the node with lowest path cost, and is\n",
        "optimal for general action costs.\\n\n",
        "– DEPTH-FIRST SEARCH expands the deepest unexpanded node first. It is neither\n",
        "complete nor optimal, but has linear space complexity. Depth-limited search adds a\n",
        "depth bound.\\n\n",
        "– ITERATIVE DEEPENING SEARCH calls depth-first search with increasing depth\n",
        "limits until a goal is found. It is complete when full cycle checking is done, optimal for\n",
        "unit action costs, has time complexity comparable to breadth-first search, and has linear\n",
        "space complexity.g(n)\\n\n",
        "– BIDIRECTIONAL SEARCH expands two frontiers, one around the initial state and\n",
        "one around the goal, stopping when the two frontiers meet.\\n\n",
        "Informed search methods have access to a heuristic function that estimates the\n",
        "cost of a solution from They may have access to additional information such as\n",
        "pattern databases with solution costs.\\n\n",
        "– GREEDY BEST-FIRST SEARCH expands nodes with minimal It is not optimal\n",
        "but is often efficient.\\n\n",
        "– A* SEARCH expands nodes with minimal A* is complete and\n",
        "optimal, provided that is admissible. The space complexity of A* is still an issue for\n",
        "many problems.\\n\n",
        "– BIDIRECTIONAL A* SEARCH is sometimes more efficient than A* itself.\\n\n",
        "– IDA* (iterative deepening A* search) is an iterative deepening version of A*, and\n",
        "thus adresses the space complexity issue.\\n\n",
        "– RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are\n",
        "robust, optimal search algorithms that use limited amounts of memory; given enough\n",
        "time, they can solve problems for which A* runs out of memory.\\n\n",
        "– BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and\n",
        "suboptimal, but it often finds reasonably good solutions and runs faster than complete\n",
        "searches.\\n\n",
        "– WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but\n",
        "sacrificing optimality.\n",
        "The performance of heuristic search algorithms depends on the quality of the heuristic\n",
        "function. One can sometimes construct good heuristics by relaxing the problem\n",
        "definition, by storing precomputed solution costs for subproblems in a pattern database,\n",
        "by defining landmarks, or by learning from experience with the problem class.\n",
        "\n",
        "  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"h(n)\" : \"estimated cost of the cheapest path from the state at node n to a goal state.\",    \n",
        "\"g(n)\" :\"path cost from the initial state to node\",\n",
        "\"effective branching factor$b^{*}$\":\"$N + 1 = 1 + b^∗ + (b^∗)^2 + ⋯ + (b^∗)^d$\"\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1382
        },
        "outputId": "6b15981e-a2e9-4c70-8d51-aca555be90eb"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed (Heuristic) Search Strategies:\n\nGreedy best-first search:(f(n) = h(n))\n\nstraight-line distance heuristic  complete in finite state spaces\n\nspace complexity is (V)->(bm)\n A* search:best-first search with f(n)=g(n)+h(n)\n\ncost-optimal: 1.admissible heuristic is one that never overestimates the cost to reach a goal. 2. consistency.Every consistent heuristic is admissible (but not vice versa)\n\n In fact, the term “monotonic heuristic” is a synonym for “consistent heuristic.” The two ideas were developed independently, and\nthen it was proved that they are equivalent\n\nA* is efficient because it prunes away search tree nodes that are not necessary for finding\nan optimal solution.\n\nThat A* search is complete, cost-optimal, and optimally efficient among all such algorithms\nis rather satisfying.\n\n\nA* search has many good qualities, but it expands a lot of nodes. We can explore fewer\nnodes (taking less time and space) if we are willing to accept solutions that are suboptimal,\nbut are “good enough”—what we call satisficing solutions.\n\nconsider new algorithms that are designed to conserve memory usage.\nBeam search limits the size of the frontier.->incomplete and suboptimal,good near-optimal solutions\nIterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth\u0002first.\nRBFS resembles a recursive depth\u0002first search, but rather than continuing indefinitely down the current path, it uses the _limit\nvariable to keep track of the -value of the best alternative path available from any ancestor\nof the current node.\nRBFS is somewhat more efficient than IDA*, but still suffers from excessive node regeneration.\nSMA* always drops the worst leaf node—the one with the highest -value.\n\nSome bidirectional heuristic search algorithms \nmanage a queue of pairs, but we will stick with bidirectional best-first search (Figure\n3.14 ), which has two frontier priority queues, and give it an evaluation function that\nmimics the criteria:f2(n) = max(2g(n), g(n) + h(n))\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n the distance is the sum of the horizontal and vertical distances - city-block distance or Manhattan distance. the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\n$b^*$ close to 1, allowing fairly large problems to be solved at reasonable computational cost.\n\nh2(n) ≥ h1(n).$h^2$ dominates $h^1$-efficiency \n\nthe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\nh(n) = max{h1(n),… , hk(n)}.This composite heuristic picks whichever function is most accurate on the node in question.\n\nThe idea behind pattern databases is to store these exact solution costs for every possible\nsubproblem instance\n\n\n\n## Module 4 Lecture Notes\n A* search: g(n) + h(n) (W = 1) Uniform-cost search: g(n) (W = 0) Greedy best-first search: h(n) (W = ∞)\nA* search(complete):The algorithm doesn’t end until we “expand” the goal node – it has to be at the top of the Frontier queue.\nUninformed search methods have access only to the problem definition. Algorithms\nbuild a search tree in an attempt to find a solution. Algorithms differ based on which\nnode they expand first:\n– BEST-FIRST SEARCH selects nodes for expansion using to an evaluation function.\n– BREADTH-FIRST SEARCH expands the shallowest nodes first; it is complete,\noptimal for unit action costs, but has exponential space complexity.\n\n– UNIFORM-COST SEARCH expands the node with lowest path cost, and is\noptimal for general action costs.\n\n– DEPTH-FIRST SEARCH expands the deepest unexpanded node first. It is neither\ncomplete nor optimal, but has linear space complexity. Depth-limited search adds a\ndepth bound.\n\n– ITERATIVE DEEPENING SEARCH calls depth-first search with increasing depth\nlimits until a goal is found. It is complete when full cycle checking is done, optimal for\nunit action costs, has time complexity comparable to breadth-first search, and has linear\nspace complexity.g(n)\n\n– BIDIRECTIONAL SEARCH expands two frontiers, one around the initial state and\none around the goal, stopping when the two frontiers meet.\n\nInformed search methods have access to a heuristic function that estimates the\ncost of a solution from They may have access to additional information such as\npattern databases with solution costs.\n\n– GREEDY BEST-FIRST SEARCH expands nodes with minimal It is not optimal\nbut is often efficient.\n\n– A* SEARCH expands nodes with minimal A* is complete and\noptimal, provided that is admissible. The space complexity of A* is still an issue for\nmany problems.\n\n– BIDIRECTIONAL A* SEARCH is sometimes more efficient than A* itself.\n\n– IDA* (iterative deepening A* search) is an iterative deepening version of A*, and\nthus adresses the space complexity issue.\n\n– RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are\nrobust, optimal search algorithms that use limited amounts of memory; given enough\ntime, they can solve problems for which A* runs out of memory.\n\n– BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and\nsuboptimal, but it often finds reasonably good solutions and runs faster than complete\nsearches.\n\n– WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but\nsacrificing optimality.\nThe performance of heuristic search algorithms depends on the quality of the heuristic\nfunction. One can sometimes construct good heuristics by relaxing the problem\ndefinition, by storing precomputed solution costs for subproblems in a pattern database,\nby defining landmarks, or by learning from experience with the problem class.\n\n  \n\n## Module 4 Definitions\n* **H(n)** - estimated cost of the cheapest path from the state at node n to a goal state.\n* **G(n)** - path cost from the initial state to node\n* **Effective branching factor$b^{*}$** - $N + 1 = 1 + b^∗ + (b^∗)^2 + ⋯ + (b^∗)^d$\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 = \"\"\" multi-agent environments:consider them in the aggregate as an economy/consider adversarial agents as part of the environment/ explicitly model the adversarial agents with the techniques of\n",
        "adversarial game-tree search.(important)\n",
        "game theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games.\n",
        "“Perfect information” is a synonym for fully observable,\\n\n",
        "\n",
        "A game can be defined by the initial state (how the board is set up), the legal actions in\n",
        "each state, the result of each action, a terminal test (which says when the game is over),\n",
        "and a utility function that applies to terminal states to say who won and what the final\n",
        "score is.\n",
        "\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\" the definition of a winning strategy for the game is identical to the\n",
        "definition of a solution for a nondeterministic planning problem: in both cases the desirable\n",
        "outcome must be guaranteed no matter what the “other side” does. For games with multiple\n",
        "outcome scores, we need a slightly more general algorithm called minimax search. \\n\n",
        "A heuristic evaluation function returns an estimate of the expected utility of state \n",
        "to player , just as the heuristic functions return an estimate of the distance to\n",
        "the goal.\\n\n",
        "The evaluation function does not know which states are which, but it can return a single\n",
        "value that estimates the proportion of states with each outcome.Then a\n",
        "reasonable evaluation for states in the category is the expected value.\\n\n",
        "this kind of evaluation function is called a weighted linear function\n",
        "because it can be expressed as\\n\n",
        "EVAL(s) = w1f1(s) + w2f2(s) + ⋯ + wnfn(s)\\n\n",
        "where each is a feature of the position (such as “number of white bishops”) and each is\n",
        "a weight (saying how important that feature is).\\n\n",
        "\n",
        "The effectiveness of alpha–beta pruning is highly dependent on the order in which the\n",
        "states are examined.\n",
        " In game tree search, repeated states can occur because of transpositions—different permutations of the move sequence that end up in the same position.\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "To make use of our limited computation time, we can cut off the search early and apply a\n",
        "heuristic evaluation function to states, effectively treating nonterminal nodes as if they were\n",
        "terminal. In other words, we replace the UTILITY function with EVAL, which estimates a state’s\n",
        "utility. We also replace the terminal test by a cutoff test, which must return true for terminal\n",
        "states, but is otherwise free to decide when to cut off the search, based on the search depth\n",
        "and any property of the state that it chooses to consider.\n",
        "apply evaluation function to states ->estimates a state’s utility\n",
        "Alpha–beta pruning prunes branches of the tree that can have no effect on the final\n",
        "evaluation, but forward pruning prunes moves that appear to be poor moves, but might\n",
        "possibly be good ones.\n",
        "\n",
        "\n",
        "Alpha–beta pruning prunes branches of the tree that can have no effect on the final\n",
        "evaluation, but forward pruning prunes moves that appear to be poor moves, but might\n",
        "possibly be good ones. Thus, the strategy saves computation time at the risk of making an\n",
        "error. In Shannon’s terms, this is a Type B strategy. Clearly, most human chess players do\n",
        "this, considering only a few moves from each position (at least consciously).\\n\n",
        "One approach to forward pruning is beam search (see page 115): on each ply, consider only\n",
        "a “beam” of the best moves (according to the evaluation function) rather than considering\n",
        "all possible moves. Unfortunately, this approach is rather dangerous because there is no\n",
        "guarantee that the best move will not be pruned away.\\n\n",
        "\n",
        "The PROBCUT, or probabilistic cut, algorithm (Buro, 1995) is a forward-pruning version of\n",
        "alpha–beta search that uses statistics gained from prior experience to lessen the chance that\n",
        "the best move will be pruned. Alpha–beta search prunes any node that is provably outside\n",
        "the current window. PROBCUT also prunes nodes that are probably outside the window.\\n\n",
        "\n",
        "Another technique, late move reduction, works under the assumption that move ordering\n",
        "has been done well, and therefore moves that appear later in the list of possible moves are\n",
        "less likely to be good moves.\\n\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic games bring us a little closer to the unpredictability of real life by including a\n",
        "random element, such as the throwing of dice.\\n\n",
        " expectiminimax value: For chance nodes compute the expected value, which is the sum of the value over all outcomes, weighted by \n",
        "the probability of each chance action\\n\n",
        "expected value of a position: the average over all possible outcomes of the chance nodes.\\n\n",
        "This leads us to the expectiminimax value for games with chance nodes, a generalization of\n",
        "the minimax value for deterministic games. Terminal nodes and MAX and MIN nodes work\n",
        "exactly the same way as before (with the caveat that the legal moves for MAX and MIN will\n",
        "depend on the outcome of the dice roll in the previous chance node). For chance nodes we\n",
        "compute the expected value, which is the sum of the value over all outcomes, weighted by\n",
        "the probability of each chance action\\n\n",
        " But if we put bounds on the possible values of the utility function, then we can\n",
        "arrive at bounds for the average without looking at every number. For example, say that all\n",
        "utility values are between and ; then the value of leaf nodes is bounded, and in turn\n",
        "we can place an upper bound on the value of a chance node without looking at all its\n",
        "children.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\n",
        "the agent will achieve the highest possible performance score (averaged over all the possible environments). \"\"\"\n",
        "chapter16_2 = \"\"\" six constraints that we require any reasonable preference relation to obey:Orderability,Transitivity, Continuity,Substitutability,Monotonicity,Decomposability;These constraints are known as the axioms of utility theory.\n",
        "EXISTENCE OF UTILITY FUNCTION: there exists a function such that$U(A)>U(B)$ if and only if is preferred a to b.\n",
        "EXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n",
        "As in game-playing, in a deterministic environment an agent needs only a preference\n",
        "ranking on states—the numbers don’t matter. This is called a value function or ordinalutility function.\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\" preference elicitation, involves presenting choices to the human and\n",
        "using the observed preferences to pin down the underlying utility function.\n",
        "agent exhibits a monotonic preference for more money.\\n\n",
        "risk-averse: they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\\n\n",
        "in the “desperate” region at large negative wealth in Figure 16.2(b) , the behavior is risk-seeking.\n",
        "An agent that has a linear curve is said to be risk-neutral.\\n\n",
        "One explanation for the apparently irrational preferences is the certainty effect: people are strongly attracted to gains that are certain. There are several\n",
        "reasons why this may be so.\n",
        "Decision theory is a normative theory: it describes how a rational agent should act. A\n",
        "descriptive theory, describes how actual agents—for example, humans—\n",
        "really do act.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" stop evaluating a branch whenever: \n",
        "When MAX node: 𝑣 ≥ 𝛽 is backed-up->MIN will never select that MAX node\\n\n",
        "When MIN node: 𝑣 ≤ 𝛼 is found->MAX will never select that MIN node \n",
        "def max-value(state,alpha,beta):\\n\n",
        "   if the state is a terminal state:\\n\n",
        "        return the state’s utility\\n\n",
        "   initialize v = -∞\\n\n",
        "   for each successor of state:\\n\n",
        "    v = max(v, min-value(successor))\\n\n",
        "    alpha=max(alpha,v)\n",
        "    if v>=beta:\n",
        "      return v\\n\n",
        "\n",
        "def min-value(state,alpha,beta):\\n\n",
        "   if the state is a terminal state:\\n\n",
        "        return the state’s utility\\n\n",
        "   initialize v = +∞\\n\n",
        "   for each successor of state:\\n\n",
        "    v = max(v, max-value(successor))\\n\n",
        "    beta=min(beta,v)\n",
        "    if v<=alpha:\n",
        "      return v\\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"utility function\":\"the final numeric value to player when the game ends in terminal state\",\n",
        " \"Evaluation function\":\"returns an estimate of the expected utility of state to player ,return an estimate of the distance to the goal\",\n",
        "\"α\": \"MAX’s current lower bound on MAX’s outcome\",\n",
        "\"β: \" : \"MIN’s current upper bound on MIN’s outcome\"   ,\n",
        "\"expected value\" : \"the average over all possible outcomes of the chance nodes.\",\n",
        "\"utility function\":\"assigns a single number to express the desirability of a state.\",\n",
        "\"expected utility\":\" the average utility value of the outcomes, weighted by the probability that the outcome occurs\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2201
        },
        "outputId": "337be32a-a282-42d0-9255-d1e32fb912f5"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n multi-agent environments:consider them in the aggregate as an economy/consider adversarial agents as part of the environment/ explicitly model the adversarial agents with the techniques of\nadversarial game-tree search.(important)\ngame theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games.\n“Perfect information” is a synonym for fully observable,\n\n\nA game can be defined by the initial state (how the board is set up), the legal actions in\neach state, the result of each action, a terminal test (which says when the game is over),\nand a utility function that applies to terminal states to say who won and what the final\nscore is.\n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n the definition of a winning strategy for the game is identical to the\ndefinition of a solution for a nondeterministic planning problem: in both cases the desirable\noutcome must be guaranteed no matter what the “other side” does. For games with multiple\noutcome scores, we need a slightly more general algorithm called minimax search. \n\nA heuristic evaluation function returns an estimate of the expected utility of state \nto player , just as the heuristic functions return an estimate of the distance to\nthe goal.\n\nThe evaluation function does not know which states are which, but it can return a single\nvalue that estimates the proportion of states with each outcome.Then a\nreasonable evaluation for states in the category is the expected value.\n\nthis kind of evaluation function is called a weighted linear function\nbecause it can be expressed as\n\nEVAL(s) = w1f1(s) + w2f2(s) + ⋯ + wnfn(s)\n\nwhere each is a feature of the position (such as “number of white bishops”) and each is\na weight (saying how important that feature is).\n\n\nThe effectiveness of alpha–beta pruning is highly dependent on the order in which the\nstates are examined.\n In game tree search, repeated states can occur because of transpositions—different permutations of the move sequence that end up in the same position.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nTo make use of our limited computation time, we can cut off the search early and apply a\nheuristic evaluation function to states, effectively treating nonterminal nodes as if they were\nterminal. In other words, we replace the UTILITY function with EVAL, which estimates a state’s\nutility. We also replace the terminal test by a cutoff test, which must return true for terminal\nstates, but is otherwise free to decide when to cut off the search, based on the search depth\nand any property of the state that it chooses to consider.\napply evaluation function to states ->estimates a state’s utility\nAlpha–beta pruning prunes branches of the tree that can have no effect on the final\nevaluation, but forward pruning prunes moves that appear to be poor moves, but might\npossibly be good ones.\n\n\nAlpha–beta pruning prunes branches of the tree that can have no effect on the final\nevaluation, but forward pruning prunes moves that appear to be poor moves, but might\npossibly be good ones. Thus, the strategy saves computation time at the risk of making an\nerror. In Shannon’s terms, this is a Type B strategy. Clearly, most human chess players do\nthis, considering only a few moves from each position (at least consciously).\n\nOne approach to forward pruning is beam search (see page 115): on each ply, consider only\na “beam” of the best moves (according to the evaluation function) rather than considering\nall possible moves. Unfortunately, this approach is rather dangerous because there is no\nguarantee that the best move will not be pruned away.\n\n\nThe PROBCUT, or probabilistic cut, algorithm (Buro, 1995) is a forward-pruning version of\nalpha–beta search that uses statistics gained from prior experience to lessen the chance that\nthe best move will be pruned. Alpha–beta search prunes any node that is provably outside\nthe current window. PROBCUT also prunes nodes that are probably outside the window.\n\n\nAnother technique, late move reduction, works under the assumption that move ordering\nhas been done well, and therefore moves that appear later in the list of possible moves are\nless likely to be good moves.\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games bring us a little closer to the unpredictability of real life by including a\nrandom element, such as the throwing of dice.\n\n expectiminimax value: For chance nodes compute the expected value, which is the sum of the value over all outcomes, weighted by \nthe probability of each chance action\n\nexpected value of a position: the average over all possible outcomes of the chance nodes.\n\nThis leads us to the expectiminimax value for games with chance nodes, a generalization of\nthe minimax value for deterministic games. Terminal nodes and MAX and MIN nodes work\nexactly the same way as before (with the caveat that the legal moves for MAX and MIN will\ndepend on the outcome of the dice roll in the previous chance node). For chance nodes we\ncompute the expected value, which is the sum of the value over all outcomes, weighted by\nthe probability of each chance action\n\n But if we put bounds on the possible values of the utility function, then we can\narrive at bounds for the average without looking at every number. For example, say that all\nutility values are between and ; then the value of leaf nodes is bounded, and in turn\nwe can place an upper bound on the value of a chance node without looking at all its\nchildren.\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\nthe agent will achieve the highest possible performance score (averaged over all the possible environments). \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n six constraints that we require any reasonable preference relation to obey:Orderability,Transitivity, Continuity,Substitutability,Monotonicity,Decomposability;These constraints are known as the axioms of utility theory.\nEXISTENCE OF UTILITY FUNCTION: there exists a function such that$U(A)>U(B)$ if and only if is preferred a to b.\nEXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\nAs in game-playing, in a deterministic environment an agent needs only a preference\nranking on states—the numbers don’t matter. This is called a value function or ordinalutility function.\n\n\n## AIMA Chapter 16.3 Utility Functions\n preference elicitation, involves presenting choices to the human and\nusing the observed preferences to pin down the underlying utility function.\nagent exhibits a monotonic preference for more money.\n\nrisk-averse: they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\n\nin the “desperate” region at large negative wealth in Figure 16.2(b) , the behavior is risk-seeking.\nAn agent that has a linear curve is said to be risk-neutral.\n\nOne explanation for the apparently irrational preferences is the certainty effect: people are strongly attracted to gains that are certain. There are several\nreasons why this may be so.\nDecision theory is a normative theory: it describes how a rational agent should act. A\ndescriptive theory, describes how actual agents—for example, humans—\nreally do act.\n\n\n## Module 5 Lecture Notes\n stop evaluating a branch whenever: \nWhen MAX node: 𝑣 ≥ 𝛽 is backed-up->MIN will never select that MAX node\n\nWhen MIN node: 𝑣 ≤ 𝛼 is found->MAX will never select that MIN node \ndef max-value(state,alpha,beta):\n\n   if the state is a terminal state:\n\n        return the state’s utility\n\n   initialize v = -∞\n\n   for each successor of state:\n\n    v = max(v, min-value(successor))\n\n    alpha=max(alpha,v)\n    if v>=beta:\n      return v\n\n\ndef min-value(state,alpha,beta):\n\n   if the state is a terminal state:\n\n        return the state’s utility\n\n   initialize v = +∞\n\n   for each successor of state:\n\n    v = max(v, max-value(successor))\n\n    beta=min(beta,v)\n    if v<=alpha:\n      return v\n\n\n\n\n## Module 5 Definitions\n* **Utility function** - assigns a single number to express the desirability of a state.\n* **Evaluation function** - returns an estimate of the expected utility of state to player ,return an estimate of the distance to the goal\n* **Α** - MAX’s current lower bound on MAX’s outcome\n* **Β: ** - MIN’s current upper bound on MIN’s outcome\n* **Expected value** - the average over all possible outcomes of the chance nodes.\n* **Expected utility** -  the average utility value of the outcomes, weighted by the probability that the outcome occurs\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 constraint satisfaction problem consists of three components, X(variables) D(domains) C( constraints)\n",
        " Special solution algorithms exist for linear constraints on integer variables\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" constraint propagation: using the constraints to reduce the number of legal values for a\n",
        "variable, which in turn can reduce the legal values for another variable, and so on. \n",
        " A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those\n",
        "variables, a consistent value can always be assigned to any kth variable.\n",
        "is strongly k-consistent if it is k-consistent and is also k-1-consistent, k-2-consistent, all the way down to 1-consistent.\n",
        "global constraint is one involving an arbitrary number of variables (butnot necessarily all variables\n",
        " domains are represented by upper and lower bounds and are managed by bounds propagation.\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        " AC-3 can reduce the domains of variables before we begin the search. But\n",
        "inference can be even more powerful during the course of a search;\n",
        "One of the simplest forms of inference is called forward checking.\n",
        "\n",
        " MAC (for Maintaining Arc Consistency) detects inconsistencies like\n",
        "this. After a variable is assigned a value, the INFERENCE procedure calls AC-3, but instead\n",
        "of a queue of all arcs in the CSP,start with only the arcs $(X_i,X_j)$ for all $X_j$ that are\n",
        "unassigned variables that are neighbors of $X_i$.\n",
        "\n",
        "\n",
        "but unlike MAC, forward checking does not\n",
        "recursively propagate constraints when changes are made to the domains of variables.\n",
        "\n",
        "chronological backtracking :the most recent decision point is revisited.\n",
        "The backjumping method backtracks to the most recent assignment in the conflict set.\n",
        "backjumping is redundant in a forward-checking search\n",
        "A backjumping algorithm that uses conflict sets\n",
        "defined in this way is called conflict-directed backjumping:$conf(X_i)$ <- $conf(X_i)+ conf(X_j)-\\{X_i\\}$\n",
        "Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem.\n",
        "This set of variables, along with their corresponding values, is called a no-good.\n",
        "No-goods can be effectively used by forward checking or by backjumping.\n",
        "Constraint learning is one of the most important techniques used by modern CSP solvers to achieve efficiency on complex problems.\n",
        "\"\"\" \n",
        "\n",
        "chapter6_4 = \"\"\" the most obvious approach is to select the value that results in the\n",
        "minimum number of conflicts with other variables—the min-conflicts heuristic.\n",
        "Another technique called constraint weighting aims to concentrate the search on the\n",
        "important constraints. Each constraint is given a numeric weight, initially all 1. At each step\n",
        "of the search, the algorithm chooses a variable/value pair to change that will result in the\n",
        "lowest total weight of all violated constraints. The weights are then adjusted by\n",
        "incrementing the weight of each constraint that is violated by the current assignment.\n",
        "\n",
        "Conflict-directed backjumping backtracks directly to the source of the problem.\n",
        "Constraint learning records the conflicts as they are encountered during search in order\n",
        "to avoid the same conflict later in the search.\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\" a constraint graph is a tree when any two variables are connected by only one path.We will show that any tree-structured CSP can be solved in time linear in the number of variables. The key is a new notion of consistency,\n",
        "called directional arc consistency or DAC. A CSP is defined to be directional arc-consistent under an ordering of variables $X_1,X_2,X_3,………$ if and only if every $X_i$is arc-consistent with\n",
        "each $X_j$ for j>i.\\n\n",
        "To solve a tree-structured CSP, first pick any variable to be the root of the tree, and choose\n",
        "an ordering of the variables such that each variable appears after its parent in the tree. Such\n",
        "an ordering is called a topological sort.\\n\n",
        "The complexity of solving a CSP is strongly related to the structure of its constraint\n",
        "graph. Tree-structured problems can be solved in linear time. Cutset conditioning can\n",
        "reduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\n",
        "memory) if a small cutset can be found. Tree decomposition techniques transform the\n",
        "CSP into a tree of subproblems and are efficient if the tree width of the constraint graph\n",
        "is small; however they need memory exponential in the tree width of the constraint\n",
        "graph. Combining cutset conditioning with tree decomposition can allow a better\n",
        "tradeoff of memory versus time.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" CSP:Finite set of variables/Nonempty domain of possible values/Finite set of constraints.\n",
        "A solution to a CSP is a complete, consistent assignment.\n",
        "Clean specification of many problems, generic goal, successor function & heuristics\n",
        "CSP “knows” which variables violate a constraint\n",
        "CSPs: Automatically prune off all branches that violate constraints\n",
        "A CSP can easily be expressed as a search problem:\\n\n",
        "CSPs: Automatically prune off all branches that violate constraints\\n\n",
        "Initial State: the empty assignment {};Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict;Goal test: the current assignment is complete ;Path cost: a constant cost for every step.\\n\n",
        "Solution is always found at depth n, for n variables Hence Depth First Search can be used\\n\n",
        "Depth-first search for CSPs with single-variable assignments is called backtracking search\n",
        "Backtracking search is the basic uninformed algorithm for CSPs\n",
        "Improving backtracking efficiency\n",
        "General-purpose methods & general-purpose heuristics can give huge gains in speed\n",
        "Heuristics:variable should be assigned next: Most constrained variable/(if ties:) Most constraining variable\\n\n",
        "variable’s values be tried in  Least constraining value order\\n\n",
        "detect inevitable failure early:Forward checking\\n\n",
        "1.Choose a variable with the fewest legal values 2.Choose the variable with the most constraints on remaining variables \n",
        "3.Given a variable, choose the least constraining value: the one that rules out the fewest values in the remaining variables\n",
        "4.Keep track of remaining legal values for unassigned variables;Terminate search when any unassigned variable has no remaining legal values\n",
        "Forward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures\n",
        "Constraint propagation goes beyond forward checking & repeatedly enforces constraints locally\n",
        "X->Y is consistent iff for every value x of X there is some allowed y\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"alldiff\" : \"One of the most common global constraints,all of the variables involved in the constraint must have different values\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1434
        },
        "outputId": "314f291c-4f2f-4153-974d-19413a814a12"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n A constraint satisfaction problem consists of three components, X(variables) D(domains) C( constraints)\n Special solution algorithms exist for linear constraints on integer variables\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n constraint propagation: using the constraints to reduce the number of legal values for a\nvariable, which in turn can reduce the legal values for another variable, and so on. \n A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those\nvariables, a consistent value can always be assigned to any kth variable.\nis strongly k-consistent if it is k-consistent and is also k-1-consistent, k-2-consistent, all the way down to 1-consistent.\nglobal constraint is one involving an arbitrary number of variables (butnot necessarily all variables\n domains are represented by upper and lower bounds and are managed by bounds propagation.\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n AC-3 can reduce the domains of variables before we begin the search. But\ninference can be even more powerful during the course of a search;\nOne of the simplest forms of inference is called forward checking.\n\n MAC (for Maintaining Arc Consistency) detects inconsistencies like\nthis. After a variable is assigned a value, the INFERENCE procedure calls AC-3, but instead\nof a queue of all arcs in the CSP,start with only the arcs $(X_i,X_j)$ for all $X_j$ that are\nunassigned variables that are neighbors of $X_i$.\n\n\nbut unlike MAC, forward checking does not\nrecursively propagate constraints when changes are made to the domains of variables.\n\nchronological backtracking :the most recent decision point is revisited.\nThe backjumping method backtracks to the most recent assignment in the conflict set.\nbackjumping is redundant in a forward-checking search\nA backjumping algorithm that uses conflict sets\ndefined in this way is called conflict-directed backjumping:$conf(X_i)$ <- $conf(X_i)+ conf(X_j)-\\{X_i\\}$\nConstraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem.\nThis set of variables, along with their corresponding values, is called a no-good.\nNo-goods can be effectively used by forward checking or by backjumping.\nConstraint learning is one of the most important techniques used by modern CSP solvers to achieve efficiency on complex problems.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n the most obvious approach is to select the value that results in the\nminimum number of conflicts with other variables—the min-conflicts heuristic.\nAnother technique called constraint weighting aims to concentrate the search on the\nimportant constraints. Each constraint is given a numeric weight, initially all 1. At each step\nof the search, the algorithm chooses a variable/value pair to change that will result in the\nlowest total weight of all violated constraints. The weights are then adjusted by\nincrementing the weight of each constraint that is violated by the current assignment.\n\nConflict-directed backjumping backtracks directly to the source of the problem.\nConstraint learning records the conflicts as they are encountered during search in order\nto avoid the same conflict later in the search.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n a constraint graph is a tree when any two variables are connected by only one path.We will show that any tree-structured CSP can be solved in time linear in the number of variables. The key is a new notion of consistency,\ncalled directional arc consistency or DAC. A CSP is defined to be directional arc-consistent under an ordering of variables $X_1,X_2,X_3,………$ if and only if every $X_i$is arc-consistent with\neach $X_j$ for j>i.\n\nTo solve a tree-structured CSP, first pick any variable to be the root of the tree, and choose\nan ordering of the variables such that each variable appears after its parent in the tree. Such\nan ordering is called a topological sort.\n\nThe complexity of solving a CSP is strongly related to the structure of its constraint\ngraph. Tree-structured problems can be solved in linear time. Cutset conditioning can\nreduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\nmemory) if a small cutset can be found. Tree decomposition techniques transform the\nCSP into a tree of subproblems and are efficient if the tree width of the constraint graph\nis small; however they need memory exponential in the tree width of the constraint\ngraph. Combining cutset conditioning with tree decomposition can allow a better\ntradeoff of memory versus time.\n\n\n## Module 6 Lecture Notes\n CSP:Finite set of variables/Nonempty domain of possible values/Finite set of constraints.\nA solution to a CSP is a complete, consistent assignment.\nClean specification of many problems, generic goal, successor function & heuristics\nCSP “knows” which variables violate a constraint\nCSPs: Automatically prune off all branches that violate constraints\nA CSP can easily be expressed as a search problem:\n\nCSPs: Automatically prune off all branches that violate constraints\n\nInitial State: the empty assignment {};Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict;Goal test: the current assignment is complete ;Path cost: a constant cost for every step.\n\nSolution is always found at depth n, for n variables Hence Depth First Search can be used\n\nDepth-first search for CSPs with single-variable assignments is called backtracking search\nBacktracking search is the basic uninformed algorithm for CSPs\nImproving backtracking efficiency\nGeneral-purpose methods & general-purpose heuristics can give huge gains in speed\nHeuristics:variable should be assigned next: Most constrained variable/(if ties:) Most constraining variable\n\nvariable’s values be tried in  Least constraining value order\n\ndetect inevitable failure early:Forward checking\n\n1.Choose a variable with the fewest legal values 2.Choose the variable with the most constraints on remaining variables \n3.Given a variable, choose the least constraining value: the one that rules out the fewest values in the remaining variables\n4.Keep track of remaining legal values for unassigned variables;Terminate search when any unassigned variable has no remaining legal values\nForward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures\nConstraint propagation goes beyond forward checking & repeatedly enforces constraints locally\nX->Y is consistent iff for every value x of X there is some allowed y\n\n\n## Module 6 Definitions\n* **Alldiff** - One of the most common global constraints,all of the variables involved in the constraint must have different values\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 = \"\"\"When the sentence is taken as being given\n",
        "without being derived from other sentences, we call it an axiom.\n",
        "A generic knowledge-based agent. Given a percept, the agent adds the percept to its knowledge base,\n",
        "asks the knowledge base for the best action, and tells the knowledge base that it has in fact taken that\n",
        "action.\n",
        "Each time the agent program is called, it does three things. First, it TELLs the knowledge base\n",
        "what it perceives. Second, it ASKs the knowledge base what action it should perform. In the\n",
        "process of answering this query, extensive reasoning may be done about the current state of\n",
        "the world, about the outcomes of possible action sequences, and so on. Third, the agent\n",
        "program TELLs the knowledge base which action was chosen, and returns the action so that\n",
        "it can be executed.\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Wumpus world: it is deterministic, discrete, static, and single-agent, sequential, partially observable\n",
        "\n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\"knowledge bases consist of sentences. These sentences are\n",
        "expressed according to the syntax of the representation language, which specifies all the\n",
        "sentences that are well formed.A logic must also define the semantics, or meaning, of sentences. The final issue to consider is grounding—the connection between logical reasoning\n",
        "processes and the real environment in which the agent exists. \"\"\"\n",
        "chapter7_4 = \"\"\"We now present propositional logic. We describe its syntax (the structure of sentences) and\n",
        "its semantics (the way in which the truth of sentences is determined).\n",
        "  ⋀: conjunction; ∨:disjunction;⇔:biconditional.\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" theorem-proving algorithms:The first concept is logical equivalence;The second concept we will need is validity.;\n",
        "every sentence of propositional logic is logically equivalent to a conjunction of clauses.\n",
        "knowledge bases satisfy certain restrictions on the form of sentences they contain enables them to use a more restricted and efficient inference algorithm:One is the definite clause;Slightly more general is the Horn clause; Horn clauses are closed under resolution: if you resolve two\n",
        "Horn clauses, you get back a Horn clause.\n",
        "In Horn form, the premise is body\n",
        "and the conclusion is head. A sentence consisting of a single positive\n",
        "literal, such as , is called a fact.\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" A logic defines the semantics of the sentences, which is their meaning;\n",
        "The semantics defines the truth of each sentence with respect to a possible world, which we will often call a model;\n",
        "sentence 𝛂 entails sentence β:This means that 𝛂 is more specific, or stronger than, β\n",
        "Sound – the inference algorithm should only derive entailed sentences.\n",
        "Complete – an inference algorithm is complete if it can derive all sentences that are entailed\n",
        "\n",
        "Commutativity/Associativity/Double-negation elimination\n",
        "(𝛂⟹β) eq (¬β ⟹ ¬𝛂)Contraposition\\n\n",
        "(𝛂⟹β) eq (¬𝛂⋁β) Implication elimination\\n\n",
        "(𝛂⇔β) eq ((𝛂⟹β)⋀(β⟹𝛂)) Biconditional elimination\\n\n",
        "¬(𝛂⋀β) eq (¬𝛂 ⋁ ¬β)De Morgan\\n \n",
        "((𝛂⋀β)⋁ɣ) eq ((𝛂⋀β)⋁(𝛂⋀ɣ))) Distributivity of ⋀ over ⋁\\n\n",
        "Inference Rules can be used to derive proofs:\n",
        "Modus Ponens:(𝛂⟹β, 𝛂)/β\n",
        "Elimination:𝛂⋀β/𝛂\\n\n",
        "Monotonicity: if KB⊨𝛂 then KB ⋀ β ⊨𝛂,We can safely add to the KB, without 1 invalidating anything else that we inferred\n",
        " There is a single inference rule, resolution, which yields a complete inference algorithm when coupled with any complete search algorithm.\n",
        "\n",
        "CNF:\n",
        "1. Eliminate⇔byreplacing𝛂⇔βwith(𝛂⟹β)⋀(β⟹𝛂)\n",
        "2. Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β\n",
        "3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n",
        "4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\n",
        "\n",
        "To show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable.\n",
        "\n",
        " \n",
        " backward chaining:If all the premises of one of those can be proved to be true , then the query is true.\n",
        " Forward Chaining :is a kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"factoring\" : \"removal of multiple copies of literals\",    \n",
        "\"Horn clauses\":\"a disjunction of literals of which at most one is positive,includes definite clauses And clauses with no positive literals\",\n",
        "\"definite clause\":\"a disjunction of literals of which exactly one is positive.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1218
        },
        "outputId": "e5f89c67-6851-4958-f208-ec05be58a05a"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nWhen the sentence is taken as being given\nwithout being derived from other sentences, we call it an axiom.\nA generic knowledge-based agent. Given a percept, the agent adds the percept to its knowledge base,\nasks the knowledge base for the best action, and tells the knowledge base that it has in fact taken that\naction.\nEach time the agent program is called, it does three things. First, it TELLs the knowledge base\nwhat it perceives. Second, it ASKs the knowledge base what action it should perform. In the\nprocess of answering this query, extensive reasoning may be done about the current state of\nthe world, about the outcomes of possible action sequences, and so on. Third, the agent\nprogram TELLs the knowledge base which action was chosen, and returns the action so that\nit can be executed.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpus world: it is deterministic, discrete, static, and single-agent, sequential, partially observable\n\n \n\n## AIMA Chapter 7.3 Logic\nknowledge bases consist of sentences. These sentences are\nexpressed according to the syntax of the representation language, which specifies all the\nsentences that are well formed.A logic must also define the semantics, or meaning, of sentences. The final issue to consider is grounding—the connection between logical reasoning\nprocesses and the real environment in which the agent exists. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nWe now present propositional logic. We describe its syntax (the structure of sentences) and\nits semantics (the way in which the truth of sentences is determined).\n  ⋀: conjunction; ∨:disjunction;⇔:biconditional.\n \n\n## AIMA 7.5 Propositional Theorem Proving\n theorem-proving algorithms:The first concept is logical equivalence;The second concept we will need is validity.;\nevery sentence of propositional logic is logically equivalent to a conjunction of clauses.\nknowledge bases satisfy certain restrictions on the form of sentences they contain enables them to use a more restricted and efficient inference algorithm:One is the definite clause;Slightly more general is the Horn clause; Horn clauses are closed under resolution: if you resolve two\nHorn clauses, you get back a Horn clause.\nIn Horn form, the premise is body\nand the conclusion is head. A sentence consisting of a single positive\nliteral, such as , is called a fact.\n \n\n## Module 7 Lecture Notes\n A logic defines the semantics of the sentences, which is their meaning;\nThe semantics defines the truth of each sentence with respect to a possible world, which we will often call a model;\nsentence 𝛂 entails sentence β:This means that 𝛂 is more specific, or stronger than, β\nSound – the inference algorithm should only derive entailed sentences.\nComplete – an inference algorithm is complete if it can derive all sentences that are entailed\n\nCommutativity/Associativity/Double-negation elimination\n(𝛂⟹β) eq (¬β ⟹ ¬𝛂)Contraposition\n\n(𝛂⟹β) eq (¬𝛂⋁β) Implication elimination\n\n(𝛂⇔β) eq ((𝛂⟹β)⋀(β⟹𝛂)) Biconditional elimination\n\n¬(𝛂⋀β) eq (¬𝛂 ⋁ ¬β)De Morgan\n \n((𝛂⋀β)⋁ɣ) eq ((𝛂⋀β)⋁(𝛂⋀ɣ))) Distributivity of ⋀ over ⋁\n\nInference Rules can be used to derive proofs:\nModus Ponens:(𝛂⟹β, 𝛂)/β\nElimination:𝛂⋀β/𝛂\n\nMonotonicity: if KB⊨𝛂 then KB ⋀ β ⊨𝛂,We can safely add to the KB, without 1 invalidating anything else that we inferred\n There is a single inference rule, resolution, which yields a complete inference algorithm when coupled with any complete search algorithm.\n\nCNF:\n1. Eliminate⇔byreplacing𝛂⇔βwith(𝛂⟹β)⋀(β⟹𝛂)\n2. Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β\n3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\n\nTo show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable.\n\n \n backward chaining:If all the premises of one of those can be proved to be true , then the query is true.\n Forward Chaining :is a kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions.\n \n\n## Module 7 Definitions\n* **Factoring** - removal of multiple copies of literals\n* **Horn clauses** - a disjunction of literals of which at most one is positive,includes definite clauses And clauses with no positive literals\n* **Definite clause** - a disjunction of literals of which exactly one is positive.\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": 9964
        },
        "id": "T3cm1WV542_a",
        "outputId": "85ac3874-c2ab-4791-a977-3302d2e17e39"
      },
      "source": [
        "#@title 默认标题文本\n",
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\ncomputer need capabilities: natural language processing,knowledge representation,automated reasoning,machine learning,computer vision,roboticshm thoughts: introspection,psychological experiments,brain imaging AI:study and construction of agents that do right thingA rational agent is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome\n\n \n\n## AIMA Chapter 27.1 The Limits of AI\n qualification problem:difficult to capture every contingency of appropriate behavior in a\nset of necessary and sufficient logical rules;\nThe embodied cognition approach:it makes no sense to consider the brain\nseparately: cognition takes place within a body, which is embedded in an environment.\nTuring test:The test requires a\nprogram to have a conversation with an interrogator for five minutes.\nThe interrogator then has to guess if the conversation is with a program or a person;\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Running through all the debates about strong AI is the issue of consciousness: awareness of\nthe outside world, and of the self, and the subjective experience of living. The technical term\nfor the intrinsic nature of experiences is qualia\n\n## AIMA 2.1 Agents and Environments\nthe agent function for an artificial agent will be\nimplemented by an agent program;The\nagent function is an abstract mathematical description; the agent program is a concrete\nimplementation, running within some physical system.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Omniscience(no):An omniscient\nagent knows the actual outcome of its actions and can act accordingly; learning(not only gather), and autonomy:it should learn what it can to compensate for partial or\nincorrect prior knowledge;\ndefinition of a rational agent:\nFor each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure, given the evidence provided by the percept sequence and\nwhatever built-in knowledge the agent has.\n \n\n## AIMA 2.3 The Nature of Environments\n group task environment: PEAS (Performance, Environment, Actuators, Sensors)Properties of task environments: FULLY OBSERVABLE /PARTIALLY OBSERVABLE detect all aspects that are relevant to the choice of actionSINGLE-AGENT VS. MULTIAGENTDeterministic vs. nondeterministic.EPISODIC VS. SEQUENTIALSTATIC VS. DYNAMICDISCRETE VS. CONTINUOUS\n\n\n## AIMA 2.4 The Structure of Agents\n agent = architecture + program \n\nagent program take the current percept as input from the sensors, return action to the actuators. \n\nagent function, which may depend on the entire percept history. \n\nfour basic kinds of agent programs:\n\nSimple reflex agents;(current percept, ignoring percept history.) \n\nModel-based reflex agents(maintain some internal state depends on history; \ntransition model:This knowledge about “how the world works-simple Boolean circuits/in complete scientific theories \n\nsensor model:how world state reflect in percepts.);\n\nGoal-based agents(Search and planning are the subfields of AI finding action sequences that achieve goals.); \n\nUtility-based agents(utility:the quality of being useful;  expected utility:utility the agent expects to derive,given the probabilities and utilities of each\noutcome. utility function:internalization of the performance measure, chooses actions to maximize its utility by external performance measure.).\n\nnot all utility-based agents are model-based\n\nAny type of agent (model-based, goal-based, utility-based, etc.) can as learning agent (or not).\n\n\n\n## Module 1 Lecture Notes\n \nAgents include humans, robots, softbots, thermostats, ...\n\nIt is better to design performance measures according to what you want to be achieved in the environment, rather than how you think the agent should behave.\n\nHow do we know if an agent is acting rationally? do the right thing in all circumstances.\nHow do we know if it’s doing the right thing?\nWe define a performance measure: An objective criterion for success of an agent's behavior/given the evidence provided by the percept sequence.\nThe hardest case isContinuous Partially Observable Stochastic Multiagent\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - content agent’s sensors perceive\n* **Agent function** - maps any given percept sequence to an action/abstract mathematical description\n* **Agent program** - concrete implementation, running within some physical system.\n* **Rational agent** -  select an action maximize maximizes expected performance\n* **Task environments** - rational agents are the “solutions\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n All data treated as objects:An object is deleted (by garbage collection) once unreachable.\n\nStrong Typing:Every object has a fixed type, interpreter doesn’t allow things incompatible with that type (eg. “foo” + 2)\n\nPython: dynamic typing: If assigned again, type(var) is updated;Drawback: type errors are only caught at runtime\n\nStrings: Prefixing with r means raw:No need to escape special characters: r’\n’;\nString formatting: Special use of ‘%’ (as in printf in C) print(\"%s can speak %d languages\" % (\"C3PO\", 6000000));Immutable\n\n\nSequence Types: 1.Tuple: A simple immutable ordered sequence of items Immutable: a tuple cannot be modified once created Items can be of mixed types, including collection types\n\n2.Strings Immutable:Regular strings are Unicode and use 2-byte characters (Regular strings in Python 2 use 8-bit characters)\n3.List:Mutable ordered sequence of items of mixed types\nli.reverse()reverse the list *in place* (modify)\n\nli.sort() sort the list *in place*; sorted(li) #return a *copy* sorted\n\nDictionaries:keys must be immutable;d.items():List of item tuples.from collections import defaultdict,Counter d = defaultdict(str)/ d = Counter()\n\nfunction Multiple Return Values:tuple; No Function Overloading;operator overloading (overloading +,-) is possible using methods in a class; Non-default argument should always precede default arguments; otherwise, it reports SyntaxError;Functions can be called with arguments out of order\n \naccept a variable number of non-keyword arguments to function:\n>>> def myfun(b, c=3, d=\"hello\"):\n\nreturn b + c\n\n\n>>> myfun(5,3,\"bob\")\n\n>>> myfun(5,3)\n\n\nKeyword arguments can be used after all other arguments:like:\n>>> def myfun(a, b, c):\n\n     return a – b\n\n>>> myfun(c=43, b=1, a=2)\n\n>>> myfun(2, c=43, b=1)\n\n>>> myfun(a=2, b=3, 5)(error)\n\neg.\ndef print_everything(*args):args is a tuple of arguments passed to the fn. print(args)\n\nprint_everything('a', 'b', 'c’)->('a', 'b', 'c’);lst = ['a', 'b', 'c’]print_everything(*lst)->('a', 'b', 'c')\n\nSuppose you want to accept a variable number of keyword arguments to your function. def print_keyword_args(**kwargs):# kwargs is a dict of the keyword args passed to the fn. print(kwargs)\n\nprint_keyword_args(first_name=\"John\", last_name=\"Doe\")-> {'first_name': 'John', 'last_name': 'Doe’}; my_dict = {'first_name': 'Wei', 'last_name': 'Xu’} print_keyword_args(**my_dict)->{'first_name': 'Wei', 'last_name': 'Xu'}\nSubclasses:eg.class AI_Student(Student)\n\n\nGenerators:Good for aggregating (summing, counting) items. One pass. Crucial for infinite sequences;Bad if you need to inspect the individual values\n   def merge(l, r):\n      llen = len(l)\n      rlen = len(r)\n      i=0\n      j=0\n      while i < llen or j < rlen:\n\n                if j == rlen or (i < llen and l[i] < r[j]):\n\n                    yield l[i]\n                    i += 1\n                else:\n\n                    yield r[j]\n                    j += 1\n                  \n\n[x for x in merge([1,3,5],[2,4])]\n\"First class object\" : \"can be dynamically created, destroyed, passed to a function, returned as a value, and have all the rights as other variables in the programming language have\"\n\n\n## Module 2 Definitions\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n  problem-solving process:\n\nGOAL FORMULATION,PROBLEM FORMULATION,SEARCH,SEARCH,EXECUTION\n\nsearch problem:  state space, initial state, goal states, actions, transition model, action cost function\n\n Infinite state spaces in tasks involving mathematical expressions generation, circuits, proofs, programs, and other recursively defined objects.\n\n\n## AIMA Chapter 3.2 Example Problems\n traveling salesperson problem (TSP) is a touring problem in which every\ncity on a map must be visited. \n The layout problem comes after the logical design phase and is usually\nsplit into two parts: cell layout and channel routing.\nAutomatic assembly sequencing: first find a feasible assembly\nsequence and then work to optimize the process.\n\n\n## AIMA Chapter 3.3 Search Algorithms\n cycle -redundant path, three approaches to this issue:1.remember all previously reached states \n2.not reach the same state. call a search algorithm a graph search if it checks for\nredundant paths and a tree-like search if it does not check.\n\nremove references to reached=tree-like search:uses less memory but examine redundant paths to the same state and run slower.\n\n3. follow up the chain of parents to see if the state at the end of the path has appeared earlier in the path.\n\ndenotes:\n\nd: depth or number of actions in an optimal solution\n\nm: the maximum number of actions in any path\n\nb:the branching factor or number of successors of a node that need to be considered.\n\n\n best-first search: in which we choose a node, with minimum value of some evaluation function f(n),\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n  Uninformed Search Strategies: Breadth-first search:\n\nearly goal test, checking whether a node is a solution when generated, rather than late that best-first search uses, waiting until a node is popped off the queue.\n\n space complexity:O($b^d$)\n\n uniform-cost/Dijkstra’s algorithm：actions have different costs：BEST-FIRST- SEARCH with PATH-COST(root to the current)\n\n complete and is cost-optimal.\n\n Depth-first search:\n\n A variant of depth-first search called backtracking search uses even less memory.\n\n  In backtracking, only one successor is generated at a time\nrather than all successors; each partially expanded node remembers which successor to\ngenerate next. In addition, successors are generated by modifying the current state\ndescription directly rather than allocating memory for a brand-new state. reduces the\nmemory requirements to O(m) just one state description and a path of actions;check for a cyclic path in time O(1)rather than O(m)\n\n space complexity:O($bd$)\n\n \n iterative deepening:\n\nspace complexity:O($bd$),O($bm$)no solution \n\niterative deepening is optimal (actions same cost),\nand is complete on finite acyclic state spaces, or on any finite state space when we check\nThe time complexity O($b^d$)have solution, or O($b^m$) when none.\n\nBidirectional search\n\nThe time complexity O($b^{d/2}+b^{d/2}$)\n\n  \n\n## Module 3 Lecture Notes\nGraph search :Search Tree ->Simple Mod from tree search: Check to see if a node has been visited before adding to search queue\nmust keep track of all possible states(cause a lot of memory)\n\nCriterion Breadth- Depth- Depth-limited Iterative deepening \n\nComplete?YES NO NO YES\n\nTime $b^d$ $b^m$ $b^l$ $b^d$\n\nSpace $b^d$ $bm$ $bl$ $bd$\n\nOptimal?YES NO NO YES\n\n  \n \n\n## Module 3 Definitions\n* **Problem-solving agent** - can formulate a plan via search\n* **Search** -  a sequence of actions that form a path to a goal state\n* **Informed algorithms** - can estimate how far it is from the goal\n* **Uninformed search** - All non-goal nodes in frontier look equally\n* **Informed search** - Some non-goal nodes can be ranked above others.\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Informed (Heuristic) Search Strategies:\n\nGreedy best-first search:(f(n) = h(n))\n\nstraight-line distance heuristic  complete in finite state spaces\n\nspace complexity is (V)->(bm)\n A* search:best-first search with f(n)=g(n)+h(n)\n\ncost-optimal: 1.admissible heuristic is one that never overestimates the cost to reach a goal. 2. consistency.Every consistent heuristic is admissible (but not vice versa)\n\n In fact, the term “monotonic heuristic” is a synonym for “consistent heuristic.” The two ideas were developed independently, and\nthen it was proved that they are equivalent\n\nA* is efficient because it prunes away search tree nodes that are not necessary for finding\nan optimal solution.\n\nThat A* search is complete, cost-optimal, and optimally efficient among all such algorithms\nis rather satisfying.\n\n\nA* search has many good qualities, but it expands a lot of nodes. We can explore fewer\nnodes (taking less time and space) if we are willing to accept solutions that are suboptimal,\nbut are “good enough”—what we call satisficing solutions.\n\nconsider new algorithms that are designed to conserve memory usage.\nBeam search limits the size of the frontier.->incomplete and suboptimal,good near-optimal solutions\nIterative-deepening A* search (IDA*) is to A* what iterative-deepening search is to depth\u0002first.\nRBFS resembles a recursive depth\u0002first search, but rather than continuing indefinitely down the current path, it uses the _limit\nvariable to keep track of the -value of the best alternative path available from any ancestor\nof the current node.\nRBFS is somewhat more efficient than IDA*, but still suffers from excessive node regeneration.\nSMA* always drops the worst leaf node—the one with the highest -value.\n\nSome bidirectional heuristic search algorithms \nmanage a queue of pairs, but we will stick with bidirectional best-first search (Figure\n3.14 ), which has two frontier priority queues, and give it an evaluation function that\nmimics the criteria:f2(n) = max(2g(n), g(n) + h(n))\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n the distance is the sum of the horizontal and vertical distances - city-block distance or Manhattan distance. the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\n$b^*$ close to 1, allowing fairly large problems to be solved at reasonable computational cost.\n\nh2(n) ≥ h1(n).$h^2$ dominates $h^1$-efficiency \n\nthe cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n\nh(n) = max{h1(n),… , hk(n)}.This composite heuristic picks whichever function is most accurate on the node in question.\n\nThe idea behind pattern databases is to store these exact solution costs for every possible\nsubproblem instance\n\n\n\n## Module 4 Lecture Notes\n A* search: g(n) + h(n) (W = 1) Uniform-cost search: g(n) (W = 0) Greedy best-first search: h(n) (W = ∞)\nA* search(complete):The algorithm doesn’t end until we “expand” the goal node – it has to be at the top of the Frontier queue.\nUninformed search methods have access only to the problem definition. Algorithms\nbuild a search tree in an attempt to find a solution. Algorithms differ based on which\nnode they expand first:\n– BEST-FIRST SEARCH selects nodes for expansion using to an evaluation function.\n– BREADTH-FIRST SEARCH expands the shallowest nodes first; it is complete,\noptimal for unit action costs, but has exponential space complexity.\n\n– UNIFORM-COST SEARCH expands the node with lowest path cost, and is\noptimal for general action costs.\n\n– DEPTH-FIRST SEARCH expands the deepest unexpanded node first. It is neither\ncomplete nor optimal, but has linear space complexity. Depth-limited search adds a\ndepth bound.\n\n– ITERATIVE DEEPENING SEARCH calls depth-first search with increasing depth\nlimits until a goal is found. It is complete when full cycle checking is done, optimal for\nunit action costs, has time complexity comparable to breadth-first search, and has linear\nspace complexity.g(n)\n\n– BIDIRECTIONAL SEARCH expands two frontiers, one around the initial state and\none around the goal, stopping when the two frontiers meet.\n\nInformed search methods have access to a heuristic function that estimates the\ncost of a solution from They may have access to additional information such as\npattern databases with solution costs.\n\n– GREEDY BEST-FIRST SEARCH expands nodes with minimal It is not optimal\nbut is often efficient.\n\n– A* SEARCH expands nodes with minimal A* is complete and\noptimal, provided that is admissible. The space complexity of A* is still an issue for\nmany problems.\n\n– BIDIRECTIONAL A* SEARCH is sometimes more efficient than A* itself.\n\n– IDA* (iterative deepening A* search) is an iterative deepening version of A*, and\nthus adresses the space complexity issue.\n\n– RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*) are\nrobust, optimal search algorithms that use limited amounts of memory; given enough\ntime, they can solve problems for which A* runs out of memory.\n\n– BEAM SEARCH puts a limit on the size of the frontier; that makes it incomplete and\nsuboptimal, but it often finds reasonably good solutions and runs faster than complete\nsearches.\n\n– WEIGHTED A* search focuses the search towards a goal, expanding fewer nodes, but\nsacrificing optimality.\nThe performance of heuristic search algorithms depends on the quality of the heuristic\nfunction. One can sometimes construct good heuristics by relaxing the problem\ndefinition, by storing precomputed solution costs for subproblems in a pattern database,\nby defining landmarks, or by learning from experience with the problem class.\n\n  \n\n## Module 4 Definitions\n* **H(n)** - estimated cost of the cheapest path from the state at node n to a goal state.\n* **G(n)** - path cost from the initial state to node\n* **Effective branching factor$b^{*}$** - $N + 1 = 1 + b^∗ + (b^∗)^2 + ⋯ + (b^∗)^d$\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n multi-agent environments:consider them in the aggregate as an economy/consider adversarial agents as part of the environment/ explicitly model the adversarial agents with the techniques of\nadversarial game-tree search.(important)\ngame theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games.\n“Perfect information” is a synonym for fully observable,\n\n\nA game can be defined by the initial state (how the board is set up), the legal actions in\neach state, the result of each action, a terminal test (which says when the game is over),\nand a utility function that applies to terminal states to say who won and what the final\nscore is.\n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n the definition of a winning strategy for the game is identical to the\ndefinition of a solution for a nondeterministic planning problem: in both cases the desirable\noutcome must be guaranteed no matter what the “other side” does. For games with multiple\noutcome scores, we need a slightly more general algorithm called minimax search. \n\nA heuristic evaluation function returns an estimate of the expected utility of state \nto player , just as the heuristic functions return an estimate of the distance to\nthe goal.\n\nThe evaluation function does not know which states are which, but it can return a single\nvalue that estimates the proportion of states with each outcome.Then a\nreasonable evaluation for states in the category is the expected value.\n\nthis kind of evaluation function is called a weighted linear function\nbecause it can be expressed as\n\nEVAL(s) = w1f1(s) + w2f2(s) + ⋯ + wnfn(s)\n\nwhere each is a feature of the position (such as “number of white bishops”) and each is\na weight (saying how important that feature is).\n\n\nThe effectiveness of alpha–beta pruning is highly dependent on the order in which the\nstates are examined.\n In game tree search, repeated states can occur because of transpositions—different permutations of the move sequence that end up in the same position.\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nTo make use of our limited computation time, we can cut off the search early and apply a\nheuristic evaluation function to states, effectively treating nonterminal nodes as if they were\nterminal. In other words, we replace the UTILITY function with EVAL, which estimates a state’s\nutility. We also replace the terminal test by a cutoff test, which must return true for terminal\nstates, but is otherwise free to decide when to cut off the search, based on the search depth\nand any property of the state that it chooses to consider.\napply evaluation function to states ->estimates a state’s utility\nAlpha–beta pruning prunes branches of the tree that can have no effect on the final\nevaluation, but forward pruning prunes moves that appear to be poor moves, but might\npossibly be good ones.\n\n\nAlpha–beta pruning prunes branches of the tree that can have no effect on the final\nevaluation, but forward pruning prunes moves that appear to be poor moves, but might\npossibly be good ones. Thus, the strategy saves computation time at the risk of making an\nerror. In Shannon’s terms, this is a Type B strategy. Clearly, most human chess players do\nthis, considering only a few moves from each position (at least consciously).\n\nOne approach to forward pruning is beam search (see page 115): on each ply, consider only\na “beam” of the best moves (according to the evaluation function) rather than considering\nall possible moves. Unfortunately, this approach is rather dangerous because there is no\nguarantee that the best move will not be pruned away.\n\n\nThe PROBCUT, or probabilistic cut, algorithm (Buro, 1995) is a forward-pruning version of\nalpha–beta search that uses statistics gained from prior experience to lessen the chance that\nthe best move will be pruned. Alpha–beta search prunes any node that is provably outside\nthe current window. PROBCUT also prunes nodes that are probably outside the window.\n\n\nAnother technique, late move reduction, works under the assumption that move ordering\nhas been done well, and therefore moves that appear later in the list of possible moves are\nless likely to be good moves.\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games bring us a little closer to the unpredictability of real life by including a\nrandom element, such as the throwing of dice.\n\n expectiminimax value: For chance nodes compute the expected value, which is the sum of the value over all outcomes, weighted by \nthe probability of each chance action\n\nexpected value of a position: the average over all possible outcomes of the chance nodes.\n\nThis leads us to the expectiminimax value for games with chance nodes, a generalization of\nthe minimax value for deterministic games. Terminal nodes and MAX and MIN nodes work\nexactly the same way as before (with the caveat that the legal moves for MAX and MIN will\ndepend on the outcome of the dice roll in the previous chance node). For chance nodes we\ncompute the expected value, which is the sum of the value over all outcomes, weighted by\nthe probability of each chance action\n\n But if we put bounds on the possible values of the utility function, then we can\narrive at bounds for the average without looking at every number. For example, say that all\nutility values are between and ; then the value of leaf nodes is bounded, and in turn\nwe can place an upper bound on the value of a chance node without looking at all its\nchildren.\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nIf an agent acts so as to maximize a utility function that correctly reflects the performance measure, then\nthe agent will achieve the highest possible performance score (averaged over all the possible environments). \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n six constraints that we require any reasonable preference relation to obey:Orderability,Transitivity, Continuity,Substitutability,Monotonicity,Decomposability;These constraints are known as the axioms of utility theory.\nEXISTENCE OF UTILITY FUNCTION: there exists a function such that$U(A)>U(B)$ if and only if is preferred a to b.\nEXPECTED UTILITY OF A LOTTERY: The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\nAs in game-playing, in a deterministic environment an agent needs only a preference\nranking on states—the numbers don’t matter. This is called a value function or ordinalutility function.\n\n\n## AIMA Chapter 16.3 Utility Functions\n preference elicitation, involves presenting choices to the human and\nusing the observed preferences to pin down the underlying utility function.\nagent exhibits a monotonic preference for more money.\n\nrisk-averse: they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\n\nin the “desperate” region at large negative wealth in Figure 16.2(b) , the behavior is risk-seeking.\nAn agent that has a linear curve is said to be risk-neutral.\n\nOne explanation for the apparently irrational preferences is the certainty effect: people are strongly attracted to gains that are certain. There are several\nreasons why this may be so.\nDecision theory is a normative theory: it describes how a rational agent should act. A\ndescriptive theory, describes how actual agents—for example, humans—\nreally do act.\n\n\n## Module 5 Lecture Notes\n stop evaluating a branch whenever: \nWhen MAX node: 𝑣 ≥ 𝛽 is backed-up->MIN will never select that MAX node\n\nWhen MIN node: 𝑣 ≤ 𝛼 is found->MAX will never select that MIN node \ndef max-value(state,alpha,beta):\n\n   if the state is a terminal state:\n\n        return the state’s utility\n\n   initialize v = -∞\n\n   for each successor of state:\n\n    v = max(v, min-value(successor))\n\n    alpha=max(alpha,v)\n    if v>=beta:\n      return v\n\n\ndef min-value(state,alpha,beta):\n\n   if the state is a terminal state:\n\n        return the state’s utility\n\n   initialize v = +∞\n\n   for each successor of state:\n\n    v = max(v, max-value(successor))\n\n    beta=min(beta,v)\n    if v<=alpha:\n      return v\n\n\n\n\n## Module 5 Definitions\n* **Utility function** - assigns a single number to express the desirability of a state.\n* **Evaluation function** - returns an estimate of the expected utility of state to player ,return an estimate of the distance to the goal\n* **Α** - MAX’s current lower bound on MAX’s outcome\n* **Β: ** - MIN’s current upper bound on MIN’s outcome\n* **Expected value** - the average over all possible outcomes of the chance nodes.\n* **Expected utility** -  the average utility value of the outcomes, weighted by the probability that the outcome occurs\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n A constraint satisfaction problem consists of three components, X(variables) D(domains) C( constraints)\n Special solution algorithms exist for linear constraints on integer variables\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n constraint propagation: using the constraints to reduce the number of legal values for a\nvariable, which in turn can reduce the legal values for another variable, and so on. \n A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those\nvariables, a consistent value can always be assigned to any kth variable.\nis strongly k-consistent if it is k-consistent and is also k-1-consistent, k-2-consistent, all the way down to 1-consistent.\nglobal constraint is one involving an arbitrary number of variables (butnot necessarily all variables\n domains are represented by upper and lower bounds and are managed by bounds propagation.\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n AC-3 can reduce the domains of variables before we begin the search. But\ninference can be even more powerful during the course of a search;\nOne of the simplest forms of inference is called forward checking.\n\n MAC (for Maintaining Arc Consistency) detects inconsistencies like\nthis. After a variable is assigned a value, the INFERENCE procedure calls AC-3, but instead\nof a queue of all arcs in the CSP,start with only the arcs $(X_i,X_j)$ for all $X_j$ that are\nunassigned variables that are neighbors of $X_i$.\n\n\nbut unlike MAC, forward checking does not\nrecursively propagate constraints when changes are made to the domains of variables.\n\nchronological backtracking :the most recent decision point is revisited.\nThe backjumping method backtracks to the most recent assignment in the conflict set.\nbackjumping is redundant in a forward-checking search\nA backjumping algorithm that uses conflict sets\ndefined in this way is called conflict-directed backjumping:$conf(X_i)$ <- $conf(X_i)+ conf(X_j)-\\{X_i\\}$\nConstraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem.\nThis set of variables, along with their corresponding values, is called a no-good.\nNo-goods can be effectively used by forward checking or by backjumping.\nConstraint learning is one of the most important techniques used by modern CSP solvers to achieve efficiency on complex problems.\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n the most obvious approach is to select the value that results in the\nminimum number of conflicts with other variables—the min-conflicts heuristic.\nAnother technique called constraint weighting aims to concentrate the search on the\nimportant constraints. Each constraint is given a numeric weight, initially all 1. At each step\nof the search, the algorithm chooses a variable/value pair to change that will result in the\nlowest total weight of all violated constraints. The weights are then adjusted by\nincrementing the weight of each constraint that is violated by the current assignment.\n\nConflict-directed backjumping backtracks directly to the source of the problem.\nConstraint learning records the conflicts as they are encountered during search in order\nto avoid the same conflict later in the search.\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n a constraint graph is a tree when any two variables are connected by only one path.We will show that any tree-structured CSP can be solved in time linear in the number of variables. The key is a new notion of consistency,\ncalled directional arc consistency or DAC. A CSP is defined to be directional arc-consistent under an ordering of variables $X_1,X_2,X_3,………$ if and only if every $X_i$is arc-consistent with\neach $X_j$ for j>i.\n\nTo solve a tree-structured CSP, first pick any variable to be the root of the tree, and choose\nan ordering of the variables such that each variable appears after its parent in the tree. Such\nan ordering is called a topological sort.\n\nThe complexity of solving a CSP is strongly related to the structure of its constraint\ngraph. Tree-structured problems can be solved in linear time. Cutset conditioning can\nreduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\nmemory) if a small cutset can be found. Tree decomposition techniques transform the\nCSP into a tree of subproblems and are efficient if the tree width of the constraint graph\nis small; however they need memory exponential in the tree width of the constraint\ngraph. Combining cutset conditioning with tree decomposition can allow a better\ntradeoff of memory versus time.\n\n\n## Module 6 Lecture Notes\n CSP:Finite set of variables/Nonempty domain of possible values/Finite set of constraints.\nA solution to a CSP is a complete, consistent assignment.\nClean specification of many problems, generic goal, successor function & heuristics\nCSP “knows” which variables violate a constraint\nCSPs: Automatically prune off all branches that violate constraints\nA CSP can easily be expressed as a search problem:\n\nCSPs: Automatically prune off all branches that violate constraints\n\nInitial State: the empty assignment {};Successor function: Assign value to any unassigned variable provided that there is not a constraint conflict;Goal test: the current assignment is complete ;Path cost: a constant cost for every step.\n\nSolution is always found at depth n, for n variables Hence Depth First Search can be used\n\nDepth-first search for CSPs with single-variable assignments is called backtracking search\nBacktracking search is the basic uninformed algorithm for CSPs\nImproving backtracking efficiency\nGeneral-purpose methods & general-purpose heuristics can give huge gains in speed\nHeuristics:variable should be assigned next: Most constrained variable/(if ties:) Most constraining variable\n\nvariable’s values be tried in  Least constraining value order\n\ndetect inevitable failure early:Forward checking\n\n1.Choose a variable with the fewest legal values 2.Choose the variable with the most constraints on remaining variables \n3.Given a variable, choose the least constraining value: the one that rules out the fewest values in the remaining variables\n4.Keep track of remaining legal values for unassigned variables;Terminate search when any unassigned variable has no remaining legal values\nForward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures\nConstraint propagation goes beyond forward checking & repeatedly enforces constraints locally\nX->Y is consistent iff for every value x of X there is some allowed y\n\n\n## Module 6 Definitions\n* **Alldiff** - One of the most common global constraints,all of the variables involved in the constraint must have different values\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nWhen the sentence is taken as being given\nwithout being derived from other sentences, we call it an axiom.\nA generic knowledge-based agent. Given a percept, the agent adds the percept to its knowledge base,\nasks the knowledge base for the best action, and tells the knowledge base that it has in fact taken that\naction.\nEach time the agent program is called, it does three things. First, it TELLs the knowledge base\nwhat it perceives. Second, it ASKs the knowledge base what action it should perform. In the\nprocess of answering this query, extensive reasoning may be done about the current state of\nthe world, about the outcomes of possible action sequences, and so on. Third, the agent\nprogram TELLs the knowledge base which action was chosen, and returns the action so that\nit can be executed.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Wumpus world: it is deterministic, discrete, static, and single-agent, sequential, partially observable\n\n \n\n## AIMA Chapter 7.3 Logic\nknowledge bases consist of sentences. These sentences are\nexpressed according to the syntax of the representation language, which specifies all the\nsentences that are well formed.A logic must also define the semantics, or meaning, of sentences. The final issue to consider is grounding—the connection between logical reasoning\nprocesses and the real environment in which the agent exists. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nWe now present propositional logic. We describe its syntax (the structure of sentences) and\nits semantics (the way in which the truth of sentences is determined).\n  ⋀: conjunction; ∨:disjunction;⇔:biconditional.\n \n\n## AIMA 7.5 Propositional Theorem Proving\n theorem-proving algorithms:The first concept is logical equivalence;The second concept we will need is validity.;\nevery sentence of propositional logic is logically equivalent to a conjunction of clauses.\nknowledge bases satisfy certain restrictions on the form of sentences they contain enables them to use a more restricted and efficient inference algorithm:One is the definite clause;Slightly more general is the Horn clause; Horn clauses are closed under resolution: if you resolve two\nHorn clauses, you get back a Horn clause.\nIn Horn form, the premise is body\nand the conclusion is head. A sentence consisting of a single positive\nliteral, such as , is called a fact.\n \n\n## Module 7 Lecture Notes\n A logic defines the semantics of the sentences, which is their meaning;\nThe semantics defines the truth of each sentence with respect to a possible world, which we will often call a model;\nsentence 𝛂 entails sentence β:This means that 𝛂 is more specific, or stronger than, β\nSound – the inference algorithm should only derive entailed sentences.\nComplete – an inference algorithm is complete if it can derive all sentences that are entailed\n\nCommutativity/Associativity/Double-negation elimination\n(𝛂⟹β) eq (¬β ⟹ ¬𝛂)Contraposition\n\n(𝛂⟹β) eq (¬𝛂⋁β) Implication elimination\n\n(𝛂⇔β) eq ((𝛂⟹β)⋀(β⟹𝛂)) Biconditional elimination\n\n¬(𝛂⋀β) eq (¬𝛂 ⋁ ¬β)De Morgan\n \n((𝛂⋀β)⋁ɣ) eq ((𝛂⋀β)⋁(𝛂⋀ɣ))) Distributivity of ⋀ over ⋁\n\nInference Rules can be used to derive proofs:\nModus Ponens:(𝛂⟹β, 𝛂)/β\nElimination:𝛂⋀β/𝛂\n\nMonotonicity: if KB⊨𝛂 then KB ⋀ β ⊨𝛂,We can safely add to the KB, without 1 invalidating anything else that we inferred\n There is a single inference rule, resolution, which yields a complete inference algorithm when coupled with any complete search algorithm.\n\nCNF:\n1. Eliminate⇔byreplacing𝛂⇔βwith(𝛂⟹β)⋀(β⟹𝛂)\n2. Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β\n3. Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n4. Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\n\nTo show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable.\n\n \n backward chaining:If all the premises of one of those can be proved to be true , then the query is true.\n Forward Chaining :is a kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions.\n \n\n## Module 7 Definitions\n* **Factoring** - removal of multiple copies of literals\n* **Horn clauses** - a disjunction of literals of which at most one is positive,includes definite clauses And clauses with no positive literals\n* **Definite clause** - a disjunction of literals of which exactly one is positive.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}