{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0b384b9b-b2a5-435a-e15f-a7580338b0b0"
      },
      "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": 1,
      "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": "b5a24db7-214c-46db-df86-987469a5d448"
      },
      "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": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"Passing the Turing test: NLP+knowledge rep+automated testing+ML. (+robotics + CV) total Turing test.\\n\n",
        "Learn human thoughts: introspection+psychological experiments+brain imaging.\\n\n",
        "Agents: act autonomously, perceive environment, persist over time, adaptive to changes, goal-oriented.\\n\n",
        "Rational agents: always acting optimally.\\n\n",
        "limited rationality: not enough time for computation.\\n\n",
        "value alignment problem: goals for the machines should align with the human's original thought (transfer well).\\n\n",
        "\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 = \"\"\" weak AI: act as thinking (simulating); strong AI: actually thinking. \\n\n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\" Chinese room, biological naturalism, consciousness, qualia \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" \n",
        "Agents: anything that perceive environment via sensors and act via actuators. \\n\n",
        "Percept sequence: the complete history of what the agent has perceived before. \\n\n",
        "Choice of actions only depends on its knowledge and the up-to-date percept sequence, not on any future stuff. \\n\n",
        "Agent function: describe agent's behavior and maps percept sequence to actions. \\n\n",
        "Agent program implements agent function. agent funcion is abstract maths descriptions, agent program is implementation. \\n\n",
        "\n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\" \n",
        "Performance measure: evaluates sequence of envirnment states. \\n\n",
        "design the performance measures based on what one wants to achieve instead of how we think the agt should behave. \\n\n",
        "Rational agents: choose the optimal action (maxmise the expected value) based on the percept seq and built-in knowledge. expected value here\n",
        "coz the agent doesn't know what the actual outcome is since limited computation resources\\n\n",
        "Rational agents should do Information gathering: act to modify future percepts; explore the env. \\n\n",
        "Rational agents should Learn as much as P from its perception.\\n\n",
        "Lack Autonomy: relies on the prior knowledge rather than percept and learn \\n\n",
        "autonomous -> finally independent of the prior knowledge\\n\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" \n",
        "The first step is to Specify the task environment as fully as we can: performance measure, env, actuators, sensors (PEAS) \\n\n",
        "single agents vs multi agent: whether B can be viewed as an agent depends on whether B's performance measure's value (have its own performance measure)\\\n",
        "needs to be maximise based on agent A's actions. \\n\n",
        "cooperative vs competitive multiagent env. \\n\n",
        "stochastic vs nondeterministic env: the former one deals with exact probabilities, the latter one list unquantified probability.\\n\n",
        "episodic vs sequential: whether the current decisions affect the future decisions (think ahead) \\n\n",
        "static vs dynamic: whether the env can change while agent is deliberating \\n\n",
        "discrete vs continuous \\n\n",
        "known vs unknown (not a property of the env): whether the agents know or don't know how to make good choices \\n\n",
        " \"\"\"\n",
        "chapter2_4 = \"\"\" \n",
        "agent = architecture + program \\n\n",
        "agent program takes in only current percept while agent function may base on the whole percept history \\n\n",
        "Search and planning - find action sequences which achieve the goals \\n\n",
        "model based reflex agents: transition model+ sensor model + state + action + percept \\n\n",
        "goal based agents: add goals to the above \\n\n",
        "utility-based rational agents: select the actions maximising the expected utility of the outcomes\n",
        "learning agents: learning elements + performance element + critic + problem generator \\n\n",
        "atomic vs factored vs structure representation \\n\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "performance measure: an objective criteria for how successful the agent's behavior is \\\n",
        "given the evidence by the percept seque \\n\n",
        "given PEAS task env, construct agent function maximising the expected value of the perform measure\\\n",
        "and then design the agent program implementing f on particular architecture (from abstract maths descrip to concrete implemtn) \\n \n",
        "problem solving agents must plan ahead (consider the sequence of act to the goal, called search).\\n\n",
        "problem formulation with prob-solving agents: formulate goal, search problem(states, actions, performance measure) then find solution \\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",
        "\"Softbot\": \"software agent\",\n",
        "\"fully observable environment\": \"sensors knows the complete state of the env \",\n",
        "\"effectively fully observable environment\":\"sensors detect all relevant things to the action choice\",\n",
        "\"partially observable environment\":\"probs with sensors/ parts of the state missing from the sensor data\",\n",
        "\"unobservable environment\":\"agents don't have any sensors\",\n",
        "\"deterministic environment\": \"the next state of the env is fully based on the current state and the executed action\",\n",
        "\"nondeterministic environment\":\"the contrary of the above\",\n",
        "\"semidynamic environment\":\"env doesn't change but the agent's performance score changes when considering the time passes\",\n",
        "\"agent architecture\":\"devices(sensors + actuators)\",\n",
        "\"simple reflex agent\": \"choose actions only on the current percept\",\n",
        "\"utility function\" : \"an internalisation of the performance measure\",\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "947ea758-3337-4d17-d4db-8bdad6774a33"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nPassing the Turing test: NLP+knowledge rep+automated testing+ML. (+robotics + CV) total Turing test.\n\nLearn human thoughts: introspection+psychological experiments+brain imaging.\n\nAgents: act autonomously, perceive environment, persist over time, adaptive to changes, goal-oriented.\n\nRational agents: always acting optimally.\n\nlimited rationality: not enough time for computation.\n\nvalue alignment problem: goals for the machines should align with the human's original thought (transfer well).\n\n\n\n  \n\n## AIMA Chapter 27.1 The Limits of AI\n weak AI: act as thinking (simulating); strong AI: actually thinking. \n\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Chinese room, biological naturalism, consciousness, qualia \n\n## AIMA 2.1 Agents and Environments\n \nAgents: anything that perceive environment via sensors and act via actuators. \n\nPercept sequence: the complete history of what the agent has perceived before. \n\nChoice of actions only depends on its knowledge and the up-to-date percept sequence, not on any future stuff. \n\nAgent function: describe agent's behavior and maps percept sequence to actions. \n\nAgent program implements agent function. agent funcion is abstract maths descriptions, agent program is implementation. \n\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nPerformance measure: evaluates sequence of envirnment states. \n\ndesign the performance measures based on what one wants to achieve instead of how we think the agt should behave. \n\nRational agents: choose the optimal action (maxmise the expected value) based on the percept seq and built-in knowledge. expected value here\ncoz the agent doesn't know what the actual outcome is since limited computation resources\n\nRational agents should do Information gathering: act to modify future percepts; explore the env. \n\nRational agents should Learn as much as P from its perception.\n\nLack Autonomy: relies on the prior knowledge rather than percept and learn \n\nautonomous -> finally independent of the prior knowledge\n\n\n\n## AIMA 2.3 The Nature of Environments\n \nThe first step is to Specify the task environment as fully as we can: performance measure, env, actuators, sensors (PEAS) \n\nsingle agents vs multi agent: whether B can be viewed as an agent depends on whether B's performance measure's value (have its own performance measure)needs to be maximise based on agent A's actions. \n\ncooperative vs competitive multiagent env. \n\nstochastic vs nondeterministic env: the former one deals with exact probabilities, the latter one list unquantified probability.\n\nepisodic vs sequential: whether the current decisions affect the future decisions (think ahead) \n\nstatic vs dynamic: whether the env can change while agent is deliberating \n\ndiscrete vs continuous \n\nknown vs unknown (not a property of the env): whether the agents know or don't know how to make good choices \n\n \n\n## AIMA 2.4 The Structure of Agents\n \nagent = architecture + program \n\nagent program takes in only current percept while agent function may base on the whole percept history \n\nSearch and planning - find action sequences which achieve the goals \n\nmodel based reflex agents: transition model+ sensor model + state + action + percept \n\ngoal based agents: add goals to the above \n\nutility-based rational agents: select the actions maximising the expected utility of the outcomes\nlearning agents: learning elements + performance element + critic + problem generator \n\natomic vs factored vs structure representation \n\n\n\n## Module 1 Lecture Notes\n \nperformance measure: an objective criteria for how successful the agent's behavior is given the evidence by the percept seque \n\ngiven PEAS task env, construct agent function maximising the expected value of the perform measureand then design the agent program implementing f on particular architecture (from abstract maths descrip to concrete implemtn) \n \nproblem solving agents must plan ahead (consider the sequence of act to the goal, called search).\n\nproblem formulation with prob-solving agents: formulate goal, search problem(states, actions, performance measure) then find solution \n\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Softbot** - software agent\n* **Fully observable environment** - sensors knows the complete state of the env \n* **Effectively fully observable environment** - sensors detect all relevant things to the action choice\n* **Partially observable environment** - probs with sensors/ parts of the state missing from the sensor data\n* **Unobservable environment** - agents don't have any sensors\n* **Deterministic environment** - the next state of the env is fully based on the current state and the executed action\n* **Nondeterministic environment** - the contrary of the above\n* **Semidynamic environment** - env doesn't change but the agent's performance score changes when considering the time passes\n* **Agent architecture** - devices(sensors + actuators)\n* **Simple reflex agent** - choose actions only on the current percept\n* **Utility function** - an internalisation of the performance measure\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" \n",
        "python features: \\n\n",
        "concise, whitespace delimited syntax, garbage collected, portable on major platforms without change on programs,\\\n",
        "abundant built-in types, suport libraries \\n\n",
        "whitespace is meaningful, adopt newline to end a line of code \\n\n",
        "use indentation for block struc \\n\n",
        "all data considered as objects; objects deleted automatically once unreachable  \\n\n",
        "strong and dynamically typed \\n\n",
        "None, generator, function is also a type \\n\n",
        "Python is strongly typed because each object has a fixed type.\\ \n",
        "The interpreter doesn't allow operations/actions which are not compatible \\\n",
        "with the type of the object. An example could be \"we\" + int(2). \\n \n",
        "\n",
        "Python is dynamically typed since a variable doesn't have a fixed type. \\\n",
        "Variables come into existence when first assigned. The type of the object is determined at runtime. \\\n",
        "It can be assigned again. Variables can be associated with different objects of different types.\\\n",
        "An example is that:\\\n",
        "x = 5 \\n \n",
        "x = \"222\"\\n\n",
        "type errors can only be found at runtime \\n\n",
        "\n",
        "Java is static typing: variables can only refer to objects which has a type declared;\\\n",
        "to enforce contracts, methods use type signatu: public static void main... \\n\n",
        "Python functions don't have type signatures; \\n\n",
        "\n",
        "python math basic: 2e9, True, False, **(power), %, +=, &=, but no ++/-- like c++ \\n\n",
        "\n",
        "strings: \\n\n",
        "can use single/double quotes to create; triple quotes for multiline or docstr;\\n\n",
        "use + to concentenate; \\n\n",
        "prefix with r = raw: r'\\n' means character slash and n, not special characters \\n\n",
        "formatting: use %, placeholder; print(\"%s can speak %d languages\" % (\"C\", 6)) \\n\n",
        "string and tuple is immutable, list is mutable, a=b[:] will get a shallow copy (a new object) \\n\n",
        "\n",
        "'==' checks whether variables are pointing to the objects with same value (can be different objects);\\n\n",
        "'is' checks whether variables are pointing to the same object \\n\n",
        "\n",
        "tuple: immutable, ordered sequence, items can have mixed types including collection types \\n\n",
        "strings: immutable, regularly unicode, 2-byte characters \\n\n",
        "list: mutable, ordered, mixed types item \\n\n",
        "\n",
        "dictionary: unordered, work by hashing, keys must be immutable; constant avg time add, lookup, update \\n\n",
        "keyerror if the specified key not found \\n\n",
        "defaultdict: automatically initialised nonexistent values for missing keys \\n\n",
        "counter \\n\n",
        "\n",
        "functions:\\n\n",
        "dont need to declare the types of arguments or result \\n\n",
        "support multiple return values (the return type is a tuple) while java need to use a object \\n\n",
        "no function overloading: \\n\n",
        "function specified by name alone, ignorant of types of argument, two functions can't \\\n",
        "have the same function name even if with different numbers, order, name of args \\n\n",
        "but allow operator (+, ==,...) overloading; \\n\n",
        "non-default argument of a function should lie in front of default arguments, otherwise will raise syntaxerror \\n\n",
        "\n",
        "functions can be called with arguments out of order; positional argument must be placed in front of all the\\\n",
        " keyword argument when calling the function, otherwise raise syntax error. \\n\n",
        "example: def myfun(a,b,c) myfun(a=2, b=3, 5) will have syntac error; myfun(2, a=3, c=5) will also error coz there will be multiple a \\n\n",
        "\n",
        "*args: accept a variable numver of non-keyword arguments (keyword arguments means when passing into a function: project = \"aa\", \\\n",
        "project is a keyword argument) \\n\n",
        "**kwargs: accept a variable of keyword arguments \\n\n",
        "\n",
        "python use dynamic scope: function only see the most current value of variables \\n\n",
        "default arguments & memorization \\n\n",
        "\n",
        "functions are first-class objects in python, \n",
        "can be passed to a function and returned as values, create and destroy,\n",
        "can assign functions to var/ store them in data struc\\n\n",
        "\n",
        "higher order functions: input has functions \\n\n",
        "class: \\n\n",
        "member method is inside a class \\n\n",
        "\n",
        "subclasses: extend a class (origin class: superclass, parent, ancestor);\\\n",
        "e.g. class AI_student(Student): (student is the superclass) \\n\n",
        "can do mutiple inheritance \\n\n",
        "\n",
        "redefine methods: call methods of ancestor in member method: parentclass.methodname(self,a,b,c) \\n\n",
        "\n",
        "magic methods \\n\n",
        "python doesn't have built-in main method \\n\n",
        "duck typing: build sutability of an object by determin presence of methods \\n\n",
        "\n",
        "list comprehension: [expression for name in list if filter] \\n\n",
        "dictionary, set comprehension \\n\n",
        "\n",
        "iterators have __iter__ (create iterator), __next__; can call next(i), i.__next__(), i.next(), can catch the stopiteration exception \\\n",
        "; no hasnext() method \\n\n",
        "to be iterable: has __iter__ method; to be iterator: has __next__method \\n\n",
        "iterators efficiently utilise memory \\n\n",
        "generator: is iterator; yield automatically return generator when called \\n\n",
        "each time calling __next__, method runs until encounters a yield statement, then stops and returns the yielded value; next time resume from where it stops \\n\n",
        "\n",
        "benefits of using generators: \\n\n",
        "values computed one at a time, save memory, especially for infinite sequences, bad if inspect individual values are needed \\n\n",
        "\n",
        "importlib: helpful using importlib.reload(), while reloading code from a file \\n\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"REPL\" : \"Read-Evaluate-Print Loop, convenient for testing\",\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ceb2b274-08b2-43a2-ce1a-072c85ab1221"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n \npython features: \n\nconcise, whitespace delimited syntax, garbage collected, portable on major platforms without change on programs,abundant built-in types, suport libraries \n\nwhitespace is meaningful, adopt newline to end a line of code \n\nuse indentation for block struc \n\nall data considered as objects; objects deleted automatically once unreachable  \n\nstrong and dynamically typed \n\nNone, generator, function is also a type \n\nPython is strongly typed because each object has a fixed type.\\ \nThe interpreter doesn't allow operations/actions which are not compatible with the type of the object. An example could be \"we\" + int(2). \n \n\nPython is dynamically typed since a variable doesn't have a fixed type. Variables come into existence when first assigned. The type of the object is determined at runtime. It can be assigned again. Variables can be associated with different objects of different types.An example is that:x = 5 \n \nx = \"222\"\n\ntype errors can only be found at runtime \n\n\nJava is static typing: variables can only refer to objects which has a type declared;to enforce contracts, methods use type signatu: public static void main... \n\nPython functions don't have type signatures; \n\n\npython math basic: 2e9, True, False, **(power), %, +=, &=, but no ++/-- like c++ \n\n\nstrings: \n\ncan use single/double quotes to create; triple quotes for multiline or docstr;\n\nuse + to concentenate; \n\nprefix with r = raw: r'\n' means character slash and n, not special characters \n\nformatting: use %, placeholder; print(\"%s can speak %d languages\" % (\"C\", 6)) \n\nstring and tuple is immutable, list is mutable, a=b[:] will get a shallow copy (a new object) \n\n\n'==' checks whether variables are pointing to the objects with same value (can be different objects);\n\n'is' checks whether variables are pointing to the same object \n\n\ntuple: immutable, ordered sequence, items can have mixed types including collection types \n\nstrings: immutable, regularly unicode, 2-byte characters \n\nlist: mutable, ordered, mixed types item \n\n\ndictionary: unordered, work by hashing, keys must be immutable; constant avg time add, lookup, update \n\nkeyerror if the specified key not found \n\ndefaultdict: automatically initialised nonexistent values for missing keys \n\ncounter \n\n\nfunctions:\n\ndont need to declare the types of arguments or result \n\nsupport multiple return values (the return type is a tuple) while java need to use a object \n\nno function overloading: \n\nfunction specified by name alone, ignorant of types of argument, two functions can't have the same function name even if with different numbers, order, name of args \n\nbut allow operator (+, ==,...) overloading; \n\nnon-default argument of a function should lie in front of default arguments, otherwise will raise syntaxerror \n\n\nfunctions can be called with arguments out of order; positional argument must be placed in front of all the keyword argument when calling the function, otherwise raise syntax error. \n\nexample: def myfun(a,b,c) myfun(a=2, b=3, 5) will have syntac error; myfun(2, a=3, c=5) will also error coz there will be multiple a \n\n\n*args: accept a variable numver of non-keyword arguments (keyword arguments means when passing into a function: project = \"aa\", project is a keyword argument) \n\n**kwargs: accept a variable of keyword arguments \n\n\npython use dynamic scope: function only see the most current value of variables \n\ndefault arguments & memorization \n\n\nfunctions are first-class objects in python, \ncan be passed to a function and returned as values, create and destroy,\ncan assign functions to var/ store them in data struc\n\n\nhigher order functions: input has functions \n\nclass: \n\nmember method is inside a class \n\n\nsubclasses: extend a class (origin class: superclass, parent, ancestor);e.g. class AI_student(Student): (student is the superclass) \n\ncan do mutiple inheritance \n\n\nredefine methods: call methods of ancestor in member method: parentclass.methodname(self,a,b,c) \n\n\nmagic methods \n\npython doesn't have built-in main method \n\nduck typing: build sutability of an object by determin presence of methods \n\n\nlist comprehension: [expression for name in list if filter] \n\ndictionary, set comprehension \n\n\niterators have __iter__ (create iterator), __next__; can call next(i), i.__next__(), i.next(), can catch the stopiteration exception ; no hasnext() method \n\nto be iterable: has __iter__ method; to be iterator: has __next__method \n\niterators efficiently utilise memory \n\ngenerator: is iterator; yield automatically return generator when called \n\neach time calling __next__, method runs until encounters a yield statement, then stops and returns the yielded value; next time resume from where it stops \n\n\nbenefits of using generators: \n\nvalues computed one at a time, save memory, especially for infinite sequences, bad if inspect individual values are needed \n\n\nimportlib: helpful using importlib.reload(), while reloading code from a file \n\n\n\n \n\n## Module 2 Definitions\n* **Repl** - Read-Evaluate-Print Loop, convenient for testing\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" \n",
        "goal formulation, problem formulation(describe the necessary states and actions to the goal, an abstract model), search, execution \\n\n",
        "solution: fixed sequence of actions in fully observable, deterministic, known env; branching strategy in partially observable/ nondeterministic env \\n\n",
        "transition model is used to explain what each action does \\n\n",
        "abstraction, level of abstraction, valid abstraction \\n\n",
        "search algorithm consider states and actions as atomic without internal struc\\n\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" \n",
        "standarised problem vs real-world prob \\n\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" \n",
        "Best-first search: graph search with evaluation function \\n\n",
        "frontier uses a queue, priority queue pops the node with the min value first \\n\n",
        "Redundant paths: \\n\n",
        "1) repeated state generates a cycle (loopy path), then the search tree is infinite \\n\n",
        "2) paths which need not to be considered (Arad-Zerind-Sibiu coz we have Arad-Sibiu) \\n\n",
        "remember all history states allows to check for redundant paths. \n",
        "Measure problem-solving performance: completeness, cost optimality, time complexity, space complexity \\n\n",
        "not complete: cycles, loops, not systematic on infinite state spaces \\n\n",
        "systematic search strategy affects completeness\n",
        " \"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "uninformed search: \\n\n",
        "breath-first search: \\n\n",
        "while all actions cost the same, systematic, complete on both finite and infinite state spaces, \\\n",
        "can do early goal test; always find a optimal solution when all actions have the same cost (not optimal if actions' cost vary); time and space complexity: O(b^d)\\n\n",
        "\\n\n",
        "Dijkstra (without a goal) or uniform search (has goal): spread out in uniform path cost; late goal test; complete, cost-optimal \\n\n",
        "Dfs: first choose the deepest node in the frontier to expand; \\\n",
        "tree-like search; not optimal; not systematic in infinite state spaces, stuck in infinite path (even if no cycles) thus incomplete (complete on finite state spaces if checks for repeated states, cycles);\n",
        "time complexity: proportional to the states number, is O(b^m), terrible if m is much larger than d; but if solution is dense, much faster than bfs)\\\n",
        "; space complexity O(bm), m is the maximum depth of the tree; backtracking search time: O(m)\\n\n",
        "Depth-limited search: no infinite-path problem; not always complete (incomplete when l<d); not optimal (e.g. when l>d); time complexity: O(b^l), space: O(b*l); choice of l determines completeness; diameter of the state-space graph -> good depth limit\\n\n",
        "Iterative deepening search: picking limit from 0 until a solution is found or report failure; goal can always be found at depth d; time and space compexity: O(b^d), O(bd) with a solution, O(b^m), O(bm) without a solution on finite state space;\\\n",
        "optimal while actions cost the same; complete on finite acyclic state spaces, or any finite state space if we check for cycles;\\\n",
        "saves memory at the cost of more time coz it does not keep the previous levels in memory and keeps repeating them  \\n\n",
        "Bidirectional search: for speedup; time and space complexity: O(b^(d/2)), O(b^(d/2)) \\n\n",
        "m is the maximum depth of search tree; d is the depth of the shallowest solution\n",
        "\n",
        "\n",
        "\n",
        " \n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "in partially observ or nondetem env, solution recommend future actions depend on the percepts; \\\n",
        "recommend in the form of branching strategy \\n\n",
        "search algorithm enumerate all poosible paths in certain orders from the inital state \\n\n",
        "tree search, node is generated through transition model; treats differnt paths to the same node as distinct \\n\n",
        "node is not state; node include state, parent-node, children, action, path-cost, depth\\n\n",
        "repeated states turn linear problem into exponential one \\n\n",
        "big O notation ignores constant multiplicative factors, if not constant, cannot be ignored; also ignore size of fixed data structure, only fixed! \\n\n",
        "use DFS if space is restricted; no infinite paths; many solutions are possibly long paths; wrong paths terminate quickly; search can be quickly fine-tuned \\n\n",
        "use BFS if has possible infinte paths; solutions have short paths; can quickly gives up unlikely branch and paths \\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search (use atomic representations)\",\n",
        "\"planning agents\": \"use factored or structured representations of states\",\n",
        "\"search\": \"find a sequence of actions to the goal\",\n",
        "\"open-loop\": \"ignore the percepts\",\n",
        "\"closed-loop\": \"monitor the percepts\",\n",
        "\"environment\":\"state space graph\",\n",
        "\"search problem\":\"state space (graph), initial state, goal states, actions, transition model, action cost function\",\n",
        "\"optimal solution\": \"lowest path cost among all solutions\",\n",
        "\"search algorithm\": \"input: search prob, output: solution / failure\",\n",
        "\"frontier\": \"reached but unexpanded nodes\",\n",
        "\"interior\": \"expanded nodes\",\n",
        "\"exterior\": \"nodes that have not been reached\",\n",
        "\"reached node\": \"has a node generated no matter whether they have been expanded or not\",\n",
        "\"Best-first search\": \"choose a node which is of min value of evaluation function f(n)\",\n",
        "\"graph search\":\"checks for redundant paths, costs more memory but faster\",\n",
        "\"tree-like search\":\"does not check for redundant paths, less memory but slower\",\n",
        "\"completeness\": \"the algorithm is guaranteed to find a solution if there is any, and can report failure\",\n",
        "\"cost optimality\": \"the algorithm can find the solution with lowest path cost\",\n",
        "\"time complexity\":\"number of nodes generated in worst case\",\n",
        "\"space complexity\":\"number of nodes simultaneously in memory in worst case\",\n",
        "\"uninformed search\": \"no idea how close the state to the goal\",\n",
        "\"bidirectional search\":\"search forward from the initial state and meanwhile backewards from the goal states, till two search meets (if they can)\",\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "f9acd233-7207-4f41-be11-f62c00ce23ea"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \ngoal formulation, problem formulation(describe the necessary states and actions to the goal, an abstract model), search, execution \n\nsolution: fixed sequence of actions in fully observable, deterministic, known env; branching strategy in partially observable/ nondeterministic env \n\ntransition model is used to explain what each action does \n\nabstraction, level of abstraction, valid abstraction \n\nsearch algorithm consider states and actions as atomic without internal struc\n\n\n\n## AIMA Chapter 3.2 Example Problems\n \nstandarised problem vs real-world prob \n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \nBest-first search: graph search with evaluation function \n\nfrontier uses a queue, priority queue pops the node with the min value first \n\nRedundant paths: \n\n1) repeated state generates a cycle (loopy path), then the search tree is infinite \n\n2) paths which need not to be considered (Arad-Zerind-Sibiu coz we have Arad-Sibiu) \n\nremember all history states allows to check for redundant paths. \nMeasure problem-solving performance: completeness, cost optimality, time complexity, space complexity \n\nnot complete: cycles, loops, not systematic on infinite state spaces \n\nsystematic search strategy affects completeness\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nuninformed search: \n\nbreath-first search: \n\nwhile all actions cost the same, systematic, complete on both finite and infinite state spaces, can do early goal test; always find a optimal solution when all actions have the same cost (not optimal if actions' cost vary); time and space complexity: O(b^d)\n\n\n\nDijkstra (without a goal) or uniform search (has goal): spread out in uniform path cost; late goal test; complete, cost-optimal \n\nDfs: first choose the deepest node in the frontier to expand; tree-like search; not optimal; not systematic in infinite state spaces, stuck in infinite path (even if no cycles) thus incomplete (complete on finite state spaces if checks for repeated states, cycles);\ntime complexity: proportional to the states number, is O(b^m), terrible if m is much larger than d; but if solution is dense, much faster than bfs); space complexity O(bm), m is the maximum depth of the tree; backtracking search time: O(m)\n\nDepth-limited search: no infinite-path problem; not always complete (incomplete when l<d); not optimal (e.g. when l>d); time complexity: O(b^l), space: O(b*l); choice of l determines completeness; diameter of the state-space graph -> good depth limit\n\nIterative deepening search: picking limit from 0 until a solution is found or report failure; goal can always be found at depth d; time and space compexity: O(b^d), O(bd) with a solution, O(b^m), O(bm) without a solution on finite state space;optimal while actions cost the same; complete on finite acyclic state spaces, or any finite state space if we check for cycles;saves memory at the cost of more time coz it does not keep the previous levels in memory and keeps repeating them  \n\nBidirectional search: for speedup; time and space complexity: O(b^(d/2)), O(b^(d/2)) \n\nm is the maximum depth of search tree; d is the depth of the shallowest solution\n\n\n\n \n \n\n## Module 3 Lecture Notes\n \nin partially observ or nondetem env, solution recommend future actions depend on the percepts; recommend in the form of branching strategy \n\nsearch algorithm enumerate all poosible paths in certain orders from the inital state \n\ntree search, node is generated through transition model; treats differnt paths to the same node as distinct \n\nnode is not state; node include state, parent-node, children, action, path-cost, depth\n\nrepeated states turn linear problem into exponential one \n\nbig O notation ignores constant multiplicative factors, if not constant, cannot be ignored; also ignore size of fixed data structure, only fixed! \n\nuse DFS if space is restricted; no infinite paths; many solutions are possibly long paths; wrong paths terminate quickly; search can be quickly fine-tuned \n\nuse BFS if has possible infinte paths; solutions have short paths; can quickly gives up unlikely branch and paths \n\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search (use atomic representations)\n* **Planning agents** - use factored or structured representations of states\n* **Search** - find a sequence of actions to the goal\n* **Open-loop** - ignore the percepts\n* **Closed-loop** - monitor the percepts\n* **Environment** - state space graph\n* **Search problem** - state space (graph), initial state, goal states, actions, transition model, action cost function\n* **Optimal solution** - lowest path cost among all solutions\n* **Search algorithm** - input: search prob, output: solution / failure\n* **Frontier** - reached but unexpanded nodes\n* **Interior** - expanded nodes\n* **Exterior** - nodes that have not been reached\n* **Reached node** - has a node generated no matter whether they have been expanded or not\n* **Best-first search** - choose a node which is of min value of evaluation function f(n)\n* **Graph search** - checks for redundant paths, costs more memory but faster\n* **Tree-like search** - does not check for redundant paths, less memory but slower\n* **Completeness** - the algorithm is guaranteed to find a solution if there is any, and can report failure\n* **Cost optimality** - the algorithm can find the solution with lowest path cost\n* **Time complexity** - number of nodes generated in worst case\n* **Space complexity** - number of nodes simultaneously in memory in worst case\n* **Uninformed search** - no idea how close the state to the goal\n* **Bidirectional search** - search forward from the initial state and meanwhile backewards from the goal states, till two search meets (if they can)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "Greedy best-first search: f(n) = h(n); not optimal, generally not complete (complete in finite SP with no loops but incomplete in infinite SP, or finite state space with loops);\\\n",
        "time, space complex: both O(|V|), with good h(n) can reduce to O(bm)\\n\n",
        "A* search: \\n\n",
        "f(n) = estimated cost of the lowest cost path continuing from n to the goal state; \\n\n",
        "complete; cost-optimal if h(n) is admissible (never overestimate the cost to the goal; optimistic); inadmissible h(n), may/ may not be cost optimal\\n\n",
        "consistent h(n) is admissible (not vice versa), and the first time the state has been reached and it will be on the optimal path;\\n\n",
        "Search contours: concentric (no line cross each other), spread out towards the goal states while uniform search spreads out equally in all directions;\\n\n",
        "A* with consistent h(n) is optimally efficient; A* is efficient coz it prunes search tree nodes not necessary for searching the optimal solution \\n\n",
        "speedy search: a kind of unbouded-cost search, f(n) = h(n) = # of actions needed to reach the goal ignorant of the action cost, no g(n) \\n\n",
        "address the memory prob of a* search: beam search, IDA*, Recursive best-first search (RBFS), \\n\n",
        "RBFS uses linear space, is optimal if h(n) is admissible, space complexity: linear in the depth of the deepest optimal solution; time complexity: hard to tell \\n\n",
        "RBFS and SMA* are optimal; having enough time they can solve problem which don't have enough memory to use A* \\n\n",
        "IDA* , RBFS , SMA* : optimal, all more space efficient than A* \\n\n",
        "Bidirectional heuristic search: evaluation function use f2(n) = max(2g(n), g(n)+h(n)); sometimes more efficient than unidir but sometimes not; optimal and complete\\\n",
        "if using the f2 evaluation and admissible h(n) \\n\n",
        "front-to-end search vs front to front search (estimate the distance to other frontier)\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "the effect of h(n) accuracy on performance: \\n\n",
        "effective braching factor b*: close to 1 if the h(n) is well-designed \\n\n",
        "effective depth: search cost from O(b^d) to O(b^(d-kh)), kh is a constant \\n\n",
        "h2 dominates h1 if for any node n, h2(n) >= h1(n), h2 expands nodes no more than h1 \\n\n",
        "general h(n) from Relaxed problem: derived h(n) from the actual cost of the relaxed prob is admisslb and consistent \\n\n",
        "generate h(n) from subproblem: store precomputed solution costs for subproblems in pattern database, disjoint pattern db, \\n\n",
        "generate h(n) from defining landmark(efficient but not admissible), differential heuristic (admissible and efficient) \\\n",
        "\\n\n",
        "Learning to search better:\\n\n",
        "metalevel state space vs object-level state space \\n\n",
        "metalevel learning: learn and avoid exploring unpromising subtrees; minimise the total cost of solving the prob, makeing tradeoff between computational cost and path cost \\n\n",
        "Learning h(n) from experience with the problem class: learn h(n) using features, e.g. h(n) = c1x1(n) + c2x2(n) \\n\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "uniform cost search: cost contours, favors the lower path cost \\n\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"problem definition + heuristic function\",\n",
        "\"heuristic function\": \"estimate the cost of the lowest cost path from state n to the goal state\",\n",
        "\"Greedy best-first search\":\"choose the node closest to the goal to expand first (minimal h(n))\",\n",
        "\"Satisficing solutions\": \"inadmissible h(n), reduce the number of nodes to expand\",\n",
        "\"weighted A* search\":\"f(n) = g(n) + W * h(n) , W>1, faster search time, fewer nodes expanded, focus on goal, suboptimal, complete\",\n",
        "\"bounded suboptimal search\": \"search for solution that is within W*optimal cost\",\n",
        "\"bounded-cost search\":\"search for solution costs < constant C\",\n",
        "\"unbouded-cost search\":\"no cost bound, find it quickly\",\n",
        "\"beam search\": \"limits frontier's size in k; may be incomplete and suboptimal, but faster, reasonably good solution\",\n",
        "\"Iteratively-deepening a* search (IDA*)\": \"limit is each f(n)\",\n",
        "\"Recursive Best-first Search\":\"record the second-best path, and backtrack\",\n",
        "\"simplified memory-bounded A* (SMA*)\": \"expand the newest best node until memory gets full, and drops the oldest node with highest f(n) and backup\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "0be9169e-a2f2-45cf-ff61-751db15410db"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nGreedy best-first search: f(n) = h(n); not optimal, generally not complete (complete in finite SP with no loops but incomplete in infinite SP, or finite state space with loops);time, space complex: both O(|V|), with good h(n) can reduce to O(bm)\n\nA* search: \n\nf(n) = estimated cost of the lowest cost path continuing from n to the goal state; \n\ncomplete; cost-optimal if h(n) is admissible (never overestimate the cost to the goal; optimistic); inadmissible h(n), may/ may not be cost optimal\n\nconsistent h(n) is admissible (not vice versa), and the first time the state has been reached and it will be on the optimal path;\n\nSearch contours: concentric (no line cross each other), spread out towards the goal states while uniform search spreads out equally in all directions;\n\nA* with consistent h(n) is optimally efficient; A* is efficient coz it prunes search tree nodes not necessary for searching the optimal solution \n\nspeedy search: a kind of unbouded-cost search, f(n) = h(n) = # of actions needed to reach the goal ignorant of the action cost, no g(n) \n\naddress the memory prob of a* search: beam search, IDA*, Recursive best-first search (RBFS), \n\nRBFS uses linear space, is optimal if h(n) is admissible, space complexity: linear in the depth of the deepest optimal solution; time complexity: hard to tell \n\nRBFS and SMA* are optimal; having enough time they can solve problem which don't have enough memory to use A* \n\nIDA* , RBFS , SMA* : optimal, all more space efficient than A* \n\nBidirectional heuristic search: evaluation function use f2(n) = max(2g(n), g(n)+h(n)); sometimes more efficient than unidir but sometimes not; optimal and completeif using the f2 evaluation and admissible h(n) \n\nfront-to-end search vs front to front search (estimate the distance to other frontier)\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \nthe effect of h(n) accuracy on performance: \n\neffective braching factor b*: close to 1 if the h(n) is well-designed \n\neffective depth: search cost from O(b^d) to O(b^(d-kh)), kh is a constant \n\nh2 dominates h1 if for any node n, h2(n) >= h1(n), h2 expands nodes no more than h1 \n\ngeneral h(n) from Relaxed problem: derived h(n) from the actual cost of the relaxed prob is admisslb and consistent \n\ngenerate h(n) from subproblem: store precomputed solution costs for subproblems in pattern database, disjoint pattern db, \n\ngenerate h(n) from defining landmark(efficient but not admissible), differential heuristic (admissible and efficient) \n\nLearning to search better:\n\nmetalevel state space vs object-level state space \n\nmetalevel learning: learn and avoid exploring unpromising subtrees; minimise the total cost of solving the prob, makeing tradeoff between computational cost and path cost \n\nLearning h(n) from experience with the problem class: learn h(n) using features, e.g. h(n) = c1x1(n) + c2x2(n) \n\n\n\n\n\n\n \n\n## Module 4 Lecture Notes\n \nuniform cost search: cost contours, favors the lower path cost \n\n \n\n## Module 4 Definitions\n* **Informed search** - problem definition + heuristic function\n* **Heuristic function** - estimate the cost of the lowest cost path from state n to the goal state\n* **Greedy best-first search** - choose the node closest to the goal to expand first (minimal h(n))\n* **Satisficing solutions** - inadmissible h(n), reduce the number of nodes to expand\n* **Weighted a* search** - f(n) = g(n) + W * h(n) , W>1, faster search time, fewer nodes expanded, focus on goal, suboptimal, complete\n* **Bounded suboptimal search** - search for solution that is within W*optimal cost\n* **Bounded-cost search** - search for solution costs < constant C\n* **Unbouded-cost search** - no cost bound, find it quickly\n* **Beam search** - limits frontier's size in k; may be incomplete and suboptimal, but faster, reasonably good solution\n* **Iteratively-deepening a* search (ida*)** - limit is each f(n)\n* **Recursive best-first search** - record the second-best path, and backtrack\n* **Simplified memory-bounded a* (sma*)** - expand the newest best node until memory gets full, and drops the oldest node with highest f(n) and backup\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "competitive environment, conflicting goals -> adversarial search prob \\n\n",
        "Two-player zero-sum games (no win-win), perfect information (fully observable) \\n\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "the optimal strategy in a game tree: to retrive the minimax value (the utility) of each state in the game tree, \\\n",
        "assume both players play optimally; \\n\n",
        "minimax decision \\n\n",
        "it's not always best to use the minimax strategy if the opponent is not playing optimally. \\n\n",
        "minimax algorithm: complete depth-first search; time complexity: O(b^m), impratical for complex game; space complexity: O(bm) (generate all legal moves at once)\\\n",
        " / O(m) (generates actions one at a time); \\n \n",
        "optimal decisions in multiplayer games: use vector to represent utility; \\n\n",
        "if not zero-sum, two players might collaborate\\n\n",
        "Alpha-beta pruning\\n\n",
        "Move ordering: the order to examine the states affect alpha beta pruning; \\n\n",
        "perfect move ordering: nodes to examine: O(b^(m/2)) while O(b^m) for minimax;\\\n",
        "branching factor reduced to sqrt(b) from b \\n\n",
        "killer moves: best moves, killer move h(n) \\n\n",
        "transpositions will cause repeated states then exponential increase in search cost; keep a transposition table which stores the h(n) of states \\n\n",
        "Shannon's Type A & Type B strategy: useful for games with large search space; make tradeoff about which part of the tree to search \\n\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "cutoff test at non-terminal & terminal states & heuristic evaluation function replace utility function \\n\n",
        "evaluation function: expected value, weighted linear function \\n\n",
        "cutting off search: iterative-deeping, when time runs out, returns the move chosen by the deepest completed search， might need to error if not quiesceent \\n\n",
        "the evaluation function should apply only to quiescent position where no pending moves can swing the evaluation wildly \\n\n",
        "horizon effect: difficult to prevent, opponent's move can cause serious damage but can be delayed temporarily; saying an agent attempt to erroneously delay the inevitable \\n\n",
        "mitigate the horizon effect: allow singular extensions which are moves obviously best among all other moves, search deeper than the cut-off place \\n\n",
        "Forward pruning: \\n\n",
        "prune moves which look bad, might have error; \\n\n",
        "beam search, most common forward pruning method, consider only the best n moves in a ply\\n\n",
        "PROBCUT/probabilistic cut: use history statistics to choose the move to prune; estimate the prob of v would be outside (alpha, beta) \\n\n",
        "late move reduction: assume perfect move ordering, late moves less likely to be good moves, reduce the depth searching these moves rather than pruning them; \\\n",
        "if comes up with a better alpha, rerun the full depth \\n\n",
        "\\n\n",
        "Search versus lookup: precompute best moves table of opening and endgame; instead of searching, solve the opening and endgame by lookup table constructed by retrograde minimax search \\n\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\" \n",
        "stochastic games: \\n\n",
        "have chance node: calculate the expected value (expectiminimax value) of the change node;\\n\n",
        "handle by expectiminimax O(b^m * n^m), n is the number of distinct rolls, m is the maximum depth of the game tree; \\n\n",
        "can do pruning if can find bound of the chance node \\n\n",
        "MCTS: Monte Carlo Tree search: select moves randomly and play the game to the end; eval an action: play the game from that state repeatedly, then average the results  \\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "utility funcion, expected utility\n",
        "if agent maximise the utility function correctly correspond to the performance measure, then agent will get the highest possible performance score averaged over all possb env\\n\n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "axioms of utility theory: constraints on rational preferences: orderability, transitivity, continuity\\\n",
        "substitutability, monotonicity, decomposability\\n\n",
        "violating those constraints will cause irrational action \\n\n",
        "Rational preference leads to utility: \\n\n",
        "a positive affine transformation of the utility function would not change the agent's behavior \\n\n",
        "value function/ordinal utility function: only needs preference ranking rather than numeric value \\n\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" \n",
        "Utility assesment and scales:\\n\n",
        "perference elicitation, normalised utilities, choose between S and standard lottery, /\n",
        "monotinic perference; unbiased; optimizer's curse; human judgment and irarationality \\n\n",
        "decision theory: normative theory descrbiing how a rational agent should act, while descriptive theory describes how actual agents really act \\n\n",
        "humans have predictable irrationality: certainty effect, ambiguity aversion, framing effect, anchoring effect \\n\n",
        "decision theory: what agent should do, combining probability theory (what agent should believe based on evidence) + utility theory (what agents want) \\n\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "static env: no change to env while agent is deliberating \\n\n",
        "strategic env: next state is determined by current state and action by the agent and the other agent \\n\n",
        "even levels for MAX, odd levels for MIN \\n\n",
        "evaluation function assign values to node based of static feature without reference to path\\n\n",
        "chess evaluation functions: weighted sum of positional features \\n\n",
        "minimax: \\n\n",
        "a state-space search tree \\n\n",
        "the backed-up val of each node is decided by values of its children \\n\n",
        "MAX never allows a move less than alpha for MAX; MIN never allows a move better than beta for MAX;\n",
        "stop evaluting a branch when evaluting a max node having a value v >= beta is backedup; when evaluting \\\n",
        "min node having a value v <= a is backed-up \\n\n",
        "a random variable = an event who has unknown outcome\\n\n",
        "a probability distribution = assignment of weights to outcomes \\n\n",
        "objectivist (frequentist answer): averages over repeated experiments empirically from historical observation; \\\n",
        "subjectivist (Bayesian anwser): belief on unobserved variables, e.g. belief that raining given the temperature \\n\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"pruning\" : \"improve efficiency by ignoring the part of the search tree which does not affect the optimal move\", \n",
        "\"game (definition)\" : \"initial state, to-move(the current player), legal action, result(transition model), terminal test, utility function\",\n",
        "\"utility function/objective function/payoff function\":\"the value achieved to player if the game ends in the terminal state s\",\n",
        "\"state space graph\": \"initial state, action function, result function\",\n",
        "\"game tree\": \"a search tree following all actions sequences to the terminal state (may be infinite)\",\n",
        "\"ply\":\"how many levels of the game tree regardless of the terminal states\",\n",
        "\"alpha\": \"lower bound on max's outcome; the highest value choice found so far at any choice point along the MAX path\",\n",
        "\"beta\":\"upper bound on min's outcome; the lowest value choice found so far at any choice point along the MIN path\",\n",
        "\"Type A strategy\": \"keeps all possible moves at a depth in mind, wide but shallow\",\n",
        "\"Type B strategy\":\"ignore some appearing bad and focus on the promising ones; deep but narrow\",\n",
        "\"heuristic evaluation function\": \"estimate the expected utility of the state for the player\",\n",
        "\"weighted linear funcion\":\"EVAL(s) = w1f1(s) + .. + wnfn(s), fi is the feature, wi is the weight\",\n",
        "\"utility function\":\"express how desirable is the state for the agent using a number\",\n",
        "\"principle of maximum expected utility (MEU)\":\"rational agents selects anctions maximising its expected utility\",\n",
        "\"orderability\": \" the rational agent must prefer one choice over the other, or consider them equal\",\n",
        "\"transitivity\":\"if prefer a to b, and prefer b to c, then prefer a to c\",\n",
        "\"continuity\":\"A>B>C, then under some probability, the rational agent indifferent between 100% B and lottery that is p,A; 1-p, C\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c4210fd7-a686-49be-ac41-c649f8240d3a"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \ncompetitive environment, conflicting goals -> adversarial search prob \n\nTwo-player zero-sum games (no win-win), perfect information (fully observable) \n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nthe optimal strategy in a game tree: to retrive the minimax value (the utility) of each state in the game tree, assume both players play optimally; \n\nminimax decision \n\nit's not always best to use the minimax strategy if the opponent is not playing optimally. \n\nminimax algorithm: complete depth-first search; time complexity: O(b^m), impratical for complex game; space complexity: O(bm) (generate all legal moves at once) / O(m) (generates actions one at a time); \n \noptimal decisions in multiplayer games: use vector to represent utility; \n\nif not zero-sum, two players might collaborate\n\nAlpha-beta pruning\n\nMove ordering: the order to examine the states affect alpha beta pruning; \n\nperfect move ordering: nodes to examine: O(b^(m/2)) while O(b^m) for minimax;branching factor reduced to sqrt(b) from b \n\nkiller moves: best moves, killer move h(n) \n\ntranspositions will cause repeated states then exponential increase in search cost; keep a transposition table which stores the h(n) of states \n\nShannon's Type A & Type B strategy: useful for games with large search space; make tradeoff about which part of the tree to search \n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \ncutoff test at non-terminal & terminal states & heuristic evaluation function replace utility function \n\nevaluation function: expected value, weighted linear function \n\ncutting off search: iterative-deeping, when time runs out, returns the move chosen by the deepest completed search， might need to error if not quiesceent \n\nthe evaluation function should apply only to quiescent position where no pending moves can swing the evaluation wildly \n\nhorizon effect: difficult to prevent, opponent's move can cause serious damage but can be delayed temporarily; saying an agent attempt to erroneously delay the inevitable \n\nmitigate the horizon effect: allow singular extensions which are moves obviously best among all other moves, search deeper than the cut-off place \n\nForward pruning: \n\nprune moves which look bad, might have error; \n\nbeam search, most common forward pruning method, consider only the best n moves in a ply\n\nPROBCUT/probabilistic cut: use history statistics to choose the move to prune; estimate the prob of v would be outside (alpha, beta) \n\nlate move reduction: assume perfect move ordering, late moves less likely to be good moves, reduce the depth searching these moves rather than pruning them; if comes up with a better alpha, rerun the full depth \n\n\n\nSearch versus lookup: precompute best moves table of opening and endgame; instead of searching, solve the opening and endgame by lookup table constructed by retrograde minimax search \n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \nstochastic games: \n\nhave chance node: calculate the expected value (expectiminimax value) of the change node;\n\nhandle by expectiminimax O(b^m * n^m), n is the number of distinct rolls, m is the maximum depth of the game tree; \n\ncan do pruning if can find bound of the chance node \n\nMCTS: Monte Carlo Tree search: select moves randomly and play the game to the end; eval an action: play the game from that state repeatedly, then average the results  \n\n\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nutility funcion, expected utility\nif agent maximise the utility function correctly correspond to the performance measure, then agent will get the highest possible performance score averaged over all possb env\n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \naxioms of utility theory: constraints on rational preferences: orderability, transitivity, continuitysubstitutability, monotonicity, decomposability\n\nviolating those constraints will cause irrational action \n\nRational preference leads to utility: \n\na positive affine transformation of the utility function would not change the agent's behavior \n\nvalue function/ordinal utility function: only needs preference ranking rather than numeric value \n\n \n\n## AIMA Chapter 16.3 Utility Functions\n \nUtility assesment and scales:\n\nperference elicitation, normalised utilities, choose between S and standard lottery, /\nmonotinic perference; unbiased; optimizer's curse; human judgment and irarationality \n\ndecision theory: normative theory descrbiing how a rational agent should act, while descriptive theory describes how actual agents really act \n\nhumans have predictable irrationality: certainty effect, ambiguity aversion, framing effect, anchoring effect \n\ndecision theory: what agent should do, combining probability theory (what agent should believe based on evidence) + utility theory (what agents want) \n\n\n\n\n## Module 5 Lecture Notes\n \nstatic env: no change to env while agent is deliberating \n\nstrategic env: next state is determined by current state and action by the agent and the other agent \n\neven levels for MAX, odd levels for MIN \n\nevaluation function assign values to node based of static feature without reference to path\n\nchess evaluation functions: weighted sum of positional features \n\nminimax: \n\na state-space search tree \n\nthe backed-up val of each node is decided by values of its children \n\nMAX never allows a move less than alpha for MAX; MIN never allows a move better than beta for MAX;\nstop evaluting a branch when evaluting a max node having a value v >= beta is backedup; when evaluting min node having a value v <= a is backed-up \n\na random variable = an event who has unknown outcome\n\na probability distribution = assignment of weights to outcomes \n\nobjectivist (frequentist answer): averages over repeated experiments empirically from historical observation; subjectivist (Bayesian anwser): belief on unobserved variables, e.g. belief that raining given the temperature \n\n\n \n\n## Module 5 Definitions\n* **Pruning** - improve efficiency by ignoring the part of the search tree which does not affect the optimal move\n* **Game (definition)** - initial state, to-move(the current player), legal action, result(transition model), terminal test, utility function\n* **Utility function/objective function/payoff function** - the value achieved to player if the game ends in the terminal state s\n* **State space graph** - initial state, action function, result function\n* **Game tree** - a search tree following all actions sequences to the terminal state (may be infinite)\n* **Ply** - how many levels of the game tree regardless of the terminal states\n* **Alpha** - lower bound on max's outcome; the highest value choice found so far at any choice point along the MAX path\n* **Beta** - upper bound on min's outcome; the lowest value choice found so far at any choice point along the MIN path\n* **Type a strategy** - keeps all possible moves at a depth in mind, wide but shallow\n* **Type b strategy** - ignore some appearing bad and focus on the promising ones; deep but narrow\n* **Heuristic evaluation function** - estimate the expected utility of the state for the player\n* **Weighted linear funcion** - EVAL(s) = w1f1(s) + .. + wnfn(s), fi is the feature, wi is the weight\n* **Utility function** - express how desirable is the state for the agent using a number\n* **Principle of maximum expected utility (meu)** - rational agents selects anctions maximising its expected utility\n* **Orderability** -  the rational agent must prefer one choice over the other, or consider them equal\n* **Transitivity** - if prefer a to b, and prefer b to c, then prefer a to c\n* **Continuity** - A>B>C, then under some probability, the rational agent indifferent between 100% B and lottery that is p,A; 1-p, C\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "CSP:\n",
        "represent a state with a set of var/value pairs and conditions for a solution by set of constraints on vars\\n\n",
        "assign values to variables satisfying constraints \\n\n",
        "solving CSP - NP-complete problem generally \\n\n",
        "use factored representation: a set of variables, each with value \\n\n",
        "Variables, domains, constratins \\n\n",
        "relation: <(X1,X2), X1>X2 > \\n\n",
        "constraint graph to visualise the CSP, constraint hypergraph \\n\n",
        "discrete, continuous (linear programming problem), finite, infinite domains \\n\n",
        "any CSP can be transformed into CSP with only binary constratins \\n\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "constraint propagation: inference, reduce the legal moves of variables using constraints\\\n",
        "can be done with search, or before the search \\n\n",
        "enforcing local consistency is used to do constraint propagation \\n\n",
        "local consistency type: \\n\n",
        "node consistency, \\n\n",
        "arc consistency: \\n\n",
        "a graph is arc-consistent if every var is arc-con with every other var; \\n\n",
        "AC-3 to enforce the arc consistency: time complexity O(cd^3) or O(n^2*d^3), coz c= 2*n*(n-1), c arcs, d domain size, n variables: \\n\n",
        "Place all the arcs in a queue. Pop arcs. \\\n",
        "For each arc Xi, Xj, remove inconsistent values from Xi. \\\n",
        "If we change the values of a node, add its arcs Xk, Xi to the queue (except Xj, Xi). \\\n",
        "Terminate when the queue is empty. \\n\n",
        "path consistency,\\n\n",
        "k-consistency: any set of k-1 variables with consistent assignment, the kth variable can be assigned a consistent value \\n\n",
        "strongly k-consistent: k-consistent, also k-1, k-2 ..., 1-consistent \\n\n",
        "solving strongly n-consistent prob with n nodes: time complexity O(n^2*d); first choose a consistent value for X1,\\\n",
        "then choose a value for X2 since graph is 2-consistent,..\\n\n",
        "establish n-consistency takes time and space exponential in n\\n\n",
        "global constraint, resource constraint (at most m resources, but need n>m at least, thus not consistent ) \\n\n",
        "CSP formalism is powerful coz for each new problem, once we define the problem in terms of constraints, then it can be solved by a general CSP solving mechanism \\n\n",
        "solving arbitrary csp costs exponential time in n, which is # of the variables.\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "constraint propogation left some variables with multiple choices -> use search \\n\n",
        "for csp, the search tree will end up with complete assignment at depth n (number of variables); n! * d^n leaves, only d^n possible complete assignments \\n\n",
        "CSP has property of commutativity, if using this property, the number of leaves is d^n \\n\n",
        "backtracking search algorithm in CSP; can use domain-independent h(n) to improve the search \\n\n",
        "1) Variable and value ordering: \\n\n",
        "select-unassigned-variable strategy: minimum-remaining-values (MRV) heuristic \\\n",
        "to choose the variable with the least possible values; more powerful, not fit for the beginning \\n\n",
        "degree heuristic: helps in the beginning; choose the variables invoving in the biggest # of constraints on other \\\n",
        "unassigned var; reduce branching factor; can be tie-breaker \\n\n",
        "least-constraining-value to select what order to examine the value in the domain: \\\n",
        "prefer value that rules out the fewest choices, allow maximum flexible choices for the neighbouring var;\\n\n",
        "2) Interleaving search and inference: \\n\n",
        "inference can be used during search, such as forward checking, userful in backtracking search\\\n",
        "but doesn't look ahead far enough so that cannot detect all inconsistency; \\n\n",
        "Maintaining Arc Consistency (MAC): recursive constratints propogation, more powerful than forward checking; \\n\n",
        "MAC and AC3:\n",
        "MAC interleaving search and inference, AC-3 is pure inference; MAC runs while assigning variables in backtracking search.\\\n",
        "MAC only queues arcs incident on the assigned variable, AC3 queue all arcs. Then MAC runs identically to AC-3. \n",
        "3) Intelligent backtracking: looking backward:\\n\n",
        "use backjumping: a cleverer way to back up, not waste time changing var which can't fix the prob  \\n\n",
        "forward checking can provide the conflict set without extra work \\n\n",
        "with forward checking or MAC, no need to do backjumping; they prune the same\\n\n",
        "conflict-directed backjumping: see the algorithm \\n\n",
        "4) Constraint learning: \\n\n",
        "prevent from running the same prob again\\n\n",
        "record and forbid the no-good by adding constraints to avoid and keeping seperate cache \\n\n",
        "no-goods are effective when using forward checking or backjumping \\n\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "local search: \n",
        "randomly place a complete assignment, randomly select one conflict member,\\\n",
        " use min-conflict heuristic to select the move which costs least conflicts, \\\n",
        " terminate until no conflict \\n\n",
        " runtime of min-conlict is independent of problem size \\n\n",
        "tabu search, constraint weighting \\n\n",
        "local search can be adaptive to the problem changes in an online setting \\n\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "complexity of solving CSP relates to the structure of the constraint graph\\n\n",
        "decompose into subprob; independent subprob; \n",
        "n/c subprob, each subprob has c var and needs d^c to solve, the total work is O(d^c * (n/c)), linear in n, while\\\n",
        " without the decoposition, the total work is O(d^n), exponential in n;\\n\n",
        "a constrain graph is a tree structure if any two vars are connected by only one path \\n\n",
        "tree-structured CSP can solve in time linear in n which is the # of varaibles due to directional arc consistency (DAC);\\\n",
        "contruct DAC time is O(n*d^2), linear in n; find solution in linear time; if no solution, it can\\\n",
        " detect contradition; no need to backtrack, simply march down \\n\n",
        "reduce graph to tree: by removing nodes or by collapsing nodes together \\n\n",
        "cutset conditioning: \\n\n",
        "reduce the general csp into a tree-structured csp \\n\n",
        "choose a subset S (cycle cutset) and assign values, then the remaining graph becomes a tree; \\\n",
        "remove the values to be consistent with S in other variables; join the two solutions, S and the tree \\n\n",
        "the total run time is O(d^c * (n-c)*d^2) \\n\n",
        "Tree decomposition: \\n\n",
        "transform the original graph into a tree of subprob if the prob satisfy three requirements \\n\n",
        "a domain is a set of tuples of values in the decomposed tree \\n\n",
        "tree-csp-solver: O(n*d^2) (not talking about tree decomposition), efficient as long as d is small \\n\n",
        "a graph can have many tree decompositions; select the one making the subproblem as small as possible \\n\n",
        "CSPs with constraint graphs of bounded tree width can be solved within polynomial time O(n*d^(w+1)), w is the tree width; tree width is the minimum width \\\n",
        "among all the tree decompositions of the graph \\n\n",
        "save search time: use tree decomposition if the tree width is small\\n\n",
        "save memory: use cutset conditioning which is linear memory if small cutset can be found, while tree decomp use memory exponential in w \\n\n",
        "Cutset conditioning is efficient if found a small cutset. But generally, no more efficient than solving a CSP directly. \\n\n",
        "value symmetry (d!), symmetry-breaking constraint\\n\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "planning vs identificaion: seq of actions vs varibles value assignment (path is the same depth, goal is important not the path) \\n\n",
        "csp solution should maximise the objective function \\n\n",
        "csp benefits: 1)formulate it and can be solved with a general solver; 2) knows which variable violates constraints and focus on\\\n",
        " search; 3) automatically prunes illgeal branches \\n\n",
        "continuous variables, linear constraints, solvable in polynomial time using linear programming \\n\n",
        "variable assign is commutative thus tree search not graph search;\\\n",
        "thus only need to consider assign a single variable at each node, then branching factor b=d, and now d^n leaves \\n\n",
        "backtracking in uninformed in csp if without using heuristic\\n\n",
        "four heuristic: mrv, degree heu, least constraining value, foward checking \\n\n",
        "dtect failure early: use forward checking(also a heuristic) \\n\n",
        "x->y is consistent iff every value of x assigned, still some allowed value for y \\n\n",
        "planar constraint graphs: each pair has only one arc, number of arcs linear in n, time complexity is O(n*d^3))\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"consistent assignment\" : \"does not violate any constraints; also called legal assignment\",\n",
        "\"complete assignment\":\"every variable has been assigned a value\",\n",
        "\"solution to CSP\":\"complete and consistent assignment\",\n",
        "\"partial solution\":\"consitent assignment but partial (not complete)\",\n",
        "\"unary constraint\" :\"limits on only one variable\",\n",
        "\"binary constraint\":\"limits on two variables\",\n",
        "\"binary CSP\": \"only with unary and binary constraint\",\n",
        "\"global constraint\":\"limit arbitrary # (no need to be all) of variables\",\n",
        "\"Alldiff\":\"all variables in the constraint should have distinct values\",\n",
        "\"absolution constraints vs preference constraints\":\"pref: tell which is the prefered solution; pref often encode as costs\",\n",
        "\"constrained optimization problem COP\": \"solve CSP with preference constraints\",\n",
        "\"node consistent\": \"for a single variable, all values in the domain satisfy the unary constraints of the variable\",\n",
        "\"arc consistent\":\"Xi is arc-consistent to Xj if for every value in Di, Dj exists value satisfy Xi Xj binary constraints \",\n",
        "\"path consistent\":\"two-variable set path-consistent to a third variable Xm; given {Xi, Xj} consistent, Xm can satisfy {Xi,Xm} and {Xm, Xj}\",\n",
        "\"bound consistent\":\"every variable X and its upper and lower bound, some value of Y can satisfy constraint X,Y for every Y\",\n",
        "\"forward checking\":\"when X is assigned, delete inconsistent value with X from unassigned Y which constraint connected to X\",\n",
        "\"chronological backtracking\":\"back to most recent decision point\",\n",
        "\"backjumping\": \"backtrack to the most recent assignment of variables in conflict set\",\n",
        "\"Constraint learning\":\"find a minimum set of var causing the contradition prob from the conflict set \",\n",
        "\"no-good\": \"the set of variable and their corresponding value assignment leading contradition/failure assignment\",\n",
        "\"tabu search\": \"keeping a tiny list of recently visited states and avoid to return to these states\",\n",
        "\"constraint weighting\": \"focus on searching on significant constraints\",\n",
        "\"directional arc-consistent DAC\":\"if and only if every Xi is arc-consitent with Xj for j>i (has ordering)\"\n",
        "}\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "bc207b96-fe83-41ba-9d53-82cbb8e1f72a"
      },
      "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": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSP:\nrepresent a state with a set of var/value pairs and conditions for a solution by set of constraints on vars\n\nassign values to variables satisfying constraints \n\nsolving CSP - NP-complete problem generally \n\nuse factored representation: a set of variables, each with value \n\nVariables, domains, constratins \n\nrelation: <(X1,X2), X1>X2 > \n\nconstraint graph to visualise the CSP, constraint hypergraph \n\ndiscrete, continuous (linear programming problem), finite, infinite domains \n\nany CSP can be transformed into CSP with only binary constratins \n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nconstraint propagation: inference, reduce the legal moves of variables using constraintscan be done with search, or before the search \n\nenforcing local consistency is used to do constraint propagation \n\nlocal consistency type: \n\nnode consistency, \n\narc consistency: \n\na graph is arc-consistent if every var is arc-con with every other var; \n\nAC-3 to enforce the arc consistency: time complexity O(cd^3) or O(n^2*d^3), coz c= 2*n*(n-1), c arcs, d domain size, n variables: \n\nPlace all the arcs in a queue. Pop arcs. For each arc Xi, Xj, remove inconsistent values from Xi. If we change the values of a node, add its arcs Xk, Xi to the queue (except Xj, Xi). Terminate when the queue is empty. \n\npath consistency,\n\nk-consistency: any set of k-1 variables with consistent assignment, the kth variable can be assigned a consistent value \n\nstrongly k-consistent: k-consistent, also k-1, k-2 ..., 1-consistent \n\nsolving strongly n-consistent prob with n nodes: time complexity O(n^2*d); first choose a consistent value for X1,then choose a value for X2 since graph is 2-consistent,..\n\nestablish n-consistency takes time and space exponential in n\n\nglobal constraint, resource constraint (at most m resources, but need n>m at least, thus not consistent ) \n\nCSP formalism is powerful coz for each new problem, once we define the problem in terms of constraints, then it can be solved by a general CSP solving mechanism \n\nsolving arbitrary csp costs exponential time in n, which is # of the variables.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nconstraint propogation left some variables with multiple choices -> use search \n\nfor csp, the search tree will end up with complete assignment at depth n (number of variables); n! * d^n leaves, only d^n possible complete assignments \n\nCSP has property of commutativity, if using this property, the number of leaves is d^n \n\nbacktracking search algorithm in CSP; can use domain-independent h(n) to improve the search \n\n1) Variable and value ordering: \n\nselect-unassigned-variable strategy: minimum-remaining-values (MRV) heuristic to choose the variable with the least possible values; more powerful, not fit for the beginning \n\ndegree heuristic: helps in the beginning; choose the variables invoving in the biggest # of constraints on other unassigned var; reduce branching factor; can be tie-breaker \n\nleast-constraining-value to select what order to examine the value in the domain: prefer value that rules out the fewest choices, allow maximum flexible choices for the neighbouring var;\n\n2) Interleaving search and inference: \n\ninference can be used during search, such as forward checking, userful in backtracking searchbut doesn't look ahead far enough so that cannot detect all inconsistency; \n\nMaintaining Arc Consistency (MAC): recursive constratints propogation, more powerful than forward checking; \n\nMAC and AC3:\nMAC interleaving search and inference, AC-3 is pure inference; MAC runs while assigning variables in backtracking search.MAC only queues arcs incident on the assigned variable, AC3 queue all arcs. Then MAC runs identically to AC-3. \n3) Intelligent backtracking: looking backward:\n\nuse backjumping: a cleverer way to back up, not waste time changing var which can't fix the prob  \n\nforward checking can provide the conflict set without extra work \n\nwith forward checking or MAC, no need to do backjumping; they prune the same\n\nconflict-directed backjumping: see the algorithm \n\n4) Constraint learning: \n\nprevent from running the same prob again\n\nrecord and forbid the no-good by adding constraints to avoid and keeping seperate cache \n\nno-goods are effective when using forward checking or backjumping \n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nlocal search: \nrandomly place a complete assignment, randomly select one conflict member, use min-conflict heuristic to select the move which costs least conflicts,  terminate until no conflict \n\n runtime of min-conlict is independent of problem size \n\ntabu search, constraint weighting \n\nlocal search can be adaptive to the problem changes in an online setting \n\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \ncomplexity of solving CSP relates to the structure of the constraint graph\n\ndecompose into subprob; independent subprob; \nn/c subprob, each subprob has c var and needs d^c to solve, the total work is O(d^c * (n/c)), linear in n, while without the decoposition, the total work is O(d^n), exponential in n;\n\na constrain graph is a tree structure if any two vars are connected by only one path \n\ntree-structured CSP can solve in time linear in n which is the # of varaibles due to directional arc consistency (DAC);contruct DAC time is O(n*d^2), linear in n; find solution in linear time; if no solution, it can detect contradition; no need to backtrack, simply march down \n\nreduce graph to tree: by removing nodes or by collapsing nodes together \n\ncutset conditioning: \n\nreduce the general csp into a tree-structured csp \n\nchoose a subset S (cycle cutset) and assign values, then the remaining graph becomes a tree; remove the values to be consistent with S in other variables; join the two solutions, S and the tree \n\nthe total run time is O(d^c * (n-c)*d^2) \n\nTree decomposition: \n\ntransform the original graph into a tree of subprob if the prob satisfy three requirements \n\na domain is a set of tuples of values in the decomposed tree \n\ntree-csp-solver: O(n*d^2) (not talking about tree decomposition), efficient as long as d is small \n\na graph can have many tree decompositions; select the one making the subproblem as small as possible \n\nCSPs with constraint graphs of bounded tree width can be solved within polynomial time O(n*d^(w+1)), w is the tree width; tree width is the minimum width among all the tree decompositions of the graph \n\nsave search time: use tree decomposition if the tree width is small\n\nsave memory: use cutset conditioning which is linear memory if small cutset can be found, while tree decomp use memory exponential in w \n\nCutset conditioning is efficient if found a small cutset. But generally, no more efficient than solving a CSP directly. \n\nvalue symmetry (d!), symmetry-breaking constraint\n\n \n\n## Module 6 Lecture Notes\n \nplanning vs identificaion: seq of actions vs varibles value assignment (path is the same depth, goal is important not the path) \n\ncsp solution should maximise the objective function \n\ncsp benefits: 1)formulate it and can be solved with a general solver; 2) knows which variable violates constraints and focus on search; 3) automatically prunes illgeal branches \n\ncontinuous variables, linear constraints, solvable in polynomial time using linear programming \n\nvariable assign is commutative thus tree search not graph search;thus only need to consider assign a single variable at each node, then branching factor b=d, and now d^n leaves \n\nbacktracking in uninformed in csp if without using heuristic\n\nfour heuristic: mrv, degree heu, least constraining value, foward checking \n\ndtect failure early: use forward checking(also a heuristic) \n\nx->y is consistent iff every value of x assigned, still some allowed value for y \n\nplanar constraint graphs: each pair has only one arc, number of arcs linear in n, time complexity is O(n*d^3))\n \n\n## Module 6 Definitions\n* **Consistent assignment** - does not violate any constraints; also called legal assignment\n* **Complete assignment** - every variable has been assigned a value\n* **Solution to csp** - complete and consistent assignment\n* **Partial solution** - consitent assignment but partial (not complete)\n* **Unary constraint** - limits on only one variable\n* **Binary constraint** - limits on two variables\n* **Binary csp** - only with unary and binary constraint\n* **Global constraint** - limit arbitrary # (no need to be all) of variables\n* **Alldiff** - all variables in the constraint should have distinct values\n* **Absolution constraints vs preference constraints** - pref: tell which is the prefered solution; pref often encode as costs\n* **Constrained optimization problem cop** - solve CSP with preference constraints\n* **Node consistent** - for a single variable, all values in the domain satisfy the unary constraints of the variable\n* **Arc consistent** - Xi is arc-consistent to Xj if for every value in Di, Dj exists value satisfy Xi Xj binary constraints \n* **Path consistent** - two-variable set path-consistent to a third variable Xm; given {Xi, Xj} consistent, Xm can satisfy {Xi,Xm} and {Xm, Xj}\n* **Bound consistent** - every variable X and its upper and lower bound, some value of Y can satisfy constraint X,Y for every Y\n* **Forward checking** - when X is assigned, delete inconsistent value with X from unassigned Y which constraint connected to X\n* **Chronological backtracking** - back to most recent decision point\n* **Backjumping** - backtrack to the most recent assignment of variables in conflict set\n* **Constraint learning** - find a minimum set of var causing the contradition prob from the conflict set \n* **No-good** - the set of variable and their corresponding value assignment leading contradition/failure assignment\n* **Tabu search** - keeping a tiny list of recently visited states and avoid to return to these states\n* **Constraint weighting** - focus on searching on significant constraints\n* **Directional arc-consistent dac** - if and only if every Xi is arc-consitent with Xj for j>i (has ordering)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "agent program does three things when called: tell the KB its percept; asks the KB what actions to do; \\\n",
        "tells the KB what action has been chosen and returned the action so that exectued \\n\n",
        "knowledge level, implementation level \\n\n",
        "declarative approach (tell the agents till it knows how to operate) vs \n",
        "procedural approach (encodes desired behaviors directly in the program code); often combine together now \\n\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "the conlution is guaranteed to be correct given correct available information \\n\n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "semantics must be defined by a logic, which are truth of each sentence in each model \\n\n",
        "if sentence a is true in model m (m is the possible world), m satisfy a, or m is a model of a, using M(a) \\n\n",
        "to refer to the set of all models of a \\n\n",
        "logical entailment: a entails b, if and only if in every model a is true, then b is also true. M(a) belongs to M(b) (subset)\\\n",
        "set a is smaller or equal to set b \\n\n",
        "one logical inference algorithm: model checking: enumerates all possible models\\\n",
        " to check that b is true in all models in which a is true, then a entails b (works for finite model space) \\n\n",
        "if an inference algo i can derive a from KB, a is derived from KB by i, sees the sign pic \\n\n",
        "desirable property of inference: \\n\n",
        "sound/truth preserving\\n\n",
        "completeness: algo can derive any sentence which is entailed \\n\n",
        "if KB is true in real world, all sentence derived from KB by sound inference is true in real world \\n\n",
        "grounding: connection between logical reasoning and real env agent in; grounding can be based on agent's sensors, connect KB to real world \\n\n",
        "learning can produce general rules in KB \\n\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "Syntax: \\n\n",
        "logical connectives: \\n\n",
        "not: literal: an atomic sentence (a positive literal)/ a negated atomic sent (a negative literal) \\n\n",
        "and: conjunction, its elements are conjuncts \\n\n",
        "or: disjunction, disjuncts \\n\n",
        "implies: implication (or called conditional); a->b, a is the premise/antecedent \\\n",
        "b is conclusion/consequent; implication also called rules/ if-then statements \\n\n",
        "if and only if: biconditional \\n\n",
        "not operator has the highest priority \\n\n",
        "Semantics: \\n\n",
        "semantics for propositional logic must specify  given a model, for any sentence, how to compute the truth value \\n\n",
        "P imples Q is true unless P is true and Q is false in model m \\n\n",
        "P biconditional implying Q iff P and Q are both T or both False in m\\n\n",
        "use truth table to compute (see notes) \\n\n",
        "infenrence algorithm to decide whether KB entails sentences a: TT-entails? recursively enumerate a finite space of assignments\\\n",
        " to symbols; this is a sound algorithm only entail, a complete algorithm always terminate \\\n",
        "time complextiy O(2^n), space complexity O(n)\\n\n",
        "every inference algo for propos logic worst case complexity: exponential in the size of the input \\n\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "entailment by theorem proving: applying rules of inference directly to the sentences in KB to prove the desired sentence;\\\n",
        "don't need to consult models in this case \\n\n",
        "table of logical equivalence (see notes) \\n\n",
        "validity: sentence is valid if true in all models, also called tautology e.g. p or not p \\n\n",
        "deduction theorem: for any sents a and b, a entails b iff the sentence a implies b is valid \\n\n",
        "valid implication sentence -> a legitimate inference \\n\n",
        "satisfiability: a sentence is satisfiable if it is true in/ satisfied by some model \\n\n",
        "a entails b iff a AND (not B) is unsatisfiable \\n\n",
        "inference rule (see notes) \\n\n",
        "searching for proofs using inference rule \\n\n",
        "finding a proof more efficient since proof dont care about irrelevant propositions, no need for exponential models checking \\n\n",
        "monotonicity of logical systems: if KB entails a, then KB AND b can still entail a; means\\\n",
        " can add in conlucions but not invalidate what we have before; implies soundness coz it will only derive entailed sentences \\n\n",
        "Proof by resolution: \\n\n",
        "resolution, a single inference rule, yielding complete inference algorithm when used with\\\n",
        " complete search algo \\n\n",
        "resolution inference rule (see the notes) \\n\n",
        "factoring: remove multiple copies of literals, e.g. A AND A reduced to A \\n\n",
        "a resolution-based theorem proveing can decide whether a entails b for any a,b in propositional logic \\n\n",
        "Conjuctive normal form CNF: \\n\n",
        "resolution rule applies only to disjunctive of literals (also called clauses), \\n\n",
        "every sent is logically equivalent to a conjunction of disjunctive of literals (see notes) \\n\n",
        "A resolution algorithm (PL-resolution): \\n\n",
        "to show KB entails a -> to show KB AND not a is unsatisfiable \\n\n",
        "convert KB AND not a into CNF, then run the algo (see notes) \\n\n",
        "PL-resolution is complete, always terminate \\n\n",
        "resolution closure RC(S): the set of all clauses derivable \\n\n",
        "every definite clause can be transalted into an implication: premise is conjunction of positive literals, conclusion is the single positive literal \\n\n",
        "inference with horn clause can use forward-chaining and backward-chaining \\n\n",
        "entailment with horn clause: time is linear in the size of the KB \\n\n",
        "foward chaining is sound and complete \\n\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "a KB has background information \\n\n",
        "KB agent can assert new knowledge into KB, and also query the KB and ask to derive new knowledge, so as to select actions \\n\n",
        "logic defines the semantics (meanings) of the sentenes in KB; semantics defines the truth of the sents in models \\n\n",
        "\n",
        "resolution algorithm specified here: \\n\n",
        "to show KB entails a, show KB AND not a is unsatisfiable. \\n\n",
        "1) first convert KB AND not a into CNF \\n\n",
        "2) apply the resolution rule to the clauses \\n\n",
        "3) resolve every pair having the complementary literals to get new clause \\n\n",
        "4) add the new clause to the set if it never been seen \\n\n",
        "5) continue until: no new cluase can be added (KB cannot entail a); two clause resolve to yield empty clause(KB entail a) \\\n",
        "e.g. arise of P and not p lead to empty clause \\n\n",
        "\n",
        "horn clauses are closed while resolution; apply resolution to horn clause get a horn clause \\n\n",
        "\n",
        "forward chaining: data driven reasoning, dont have specific query in mind;\\\n",
        "start with known data, add premise, apply forward chaining to derive conclusion\\n\n",
        "backward chaining: goal-directed reasoning; work backwards from query; if query true, no work to do; otherwise, finds implications in KB which can conclude to query;\\\n",
        "if all premises is true, query is true\\n\n",
        "forward and backward chianing both work in linear time with efficient implementation\\n\n",
        "  \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"use reasoning over the internal representation of knowledge to select actions\",\n",
        "\"knowledge base\":\"a set of sentences using knowledge representation language, represent opinions of the world\",\n",
        "\"axiom\":\"sentence being given rather than being derived\",\n",
        "\"inference\": \"derive new setences from the old ones\",\n",
        "\"logic\":\"a general class of representations\",\n",
        "\"sound/ truth-preseving\":\"inference algo only derives entailed sentences\",\n",
        "\"syntax\":\"structure of sentences, defines allowalbe sentences\",\n",
        "\"semantics\":\"the way how the truth of sentences are determined\",\n",
        "\"atomic sentences\":\"consist of only one propositional symboll which can be True or False\",\n",
        "\"complex sentences\":\"built from simpler sentences, using parentheses and logical connectives\",\n",
        "\"logical connectives\":\"five types, not (negation), and, or, implies ->, if and only if\",\n",
        "\"logical equivalence\":\"sentences a and b both true in same set of models/ iff a entails b and b entails a\",\n",
        "\"define a proof problem for searching\":\"initial state (initial KB), actions (top of inference rule), result (bottom of rule), goal (sent trying to prove)\",\n",
        "\"definite clause\":\"a disjunction of literals with only one is postive, not A OR not B or C\",\n",
        "\"horn clause\":\"disjunction of literals where at most one is positive\",\n",
        "\"goal clause\":\"clause with no positive literals\",\n",
        "\"k-CNF sentence\":\"CNF sent where at most k literals in each clause\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e45e1bfe-3314-4e33-e885-265d2fa2ef32"
      },
      "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": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nagent program does three things when called: tell the KB its percept; asks the KB what actions to do; tells the KB what action has been chosen and returned the action so that exectued \n\nknowledge level, implementation level \n\ndeclarative approach (tell the agents till it knows how to operate) vs \nprocedural approach (encodes desired behaviors directly in the program code); often combine together now \n\n \n\n## AIMA Chapter 7.2 The Wumpus World\n \nthe conlution is guaranteed to be correct given correct available information \n\n \n\n## AIMA Chapter 7.3 Logic\n \nsemantics must be defined by a logic, which are truth of each sentence in each model \n\nif sentence a is true in model m (m is the possible world), m satisfy a, or m is a model of a, using M(a) \n\nto refer to the set of all models of a \n\nlogical entailment: a entails b, if and only if in every model a is true, then b is also true. M(a) belongs to M(b) (subset)set a is smaller or equal to set b \n\none logical inference algorithm: model checking: enumerates all possible models to check that b is true in all models in which a is true, then a entails b (works for finite model space) \n\nif an inference algo i can derive a from KB, a is derived from KB by i, sees the sign pic \n\ndesirable property of inference: \n\nsound/truth preserving\n\ncompleteness: algo can derive any sentence which is entailed \n\nif KB is true in real world, all sentence derived from KB by sound inference is true in real world \n\ngrounding: connection between logical reasoning and real env agent in; grounding can be based on agent's sensors, connect KB to real world \n\nlearning can produce general rules in KB \n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nSyntax: \n\nlogical connectives: \n\nnot: literal: an atomic sentence (a positive literal)/ a negated atomic sent (a negative literal) \n\nand: conjunction, its elements are conjuncts \n\nor: disjunction, disjuncts \n\nimplies: implication (or called conditional); a->b, a is the premise/antecedent b is conclusion/consequent; implication also called rules/ if-then statements \n\nif and only if: biconditional \n\nnot operator has the highest priority \n\nSemantics: \n\nsemantics for propositional logic must specify  given a model, for any sentence, how to compute the truth value \n\nP imples Q is true unless P is true and Q is false in model m \n\nP biconditional implying Q iff P and Q are both T or both False in m\n\nuse truth table to compute (see notes) \n\ninfenrence algorithm to decide whether KB entails sentences a: TT-entails? recursively enumerate a finite space of assignments to symbols; this is a sound algorithm only entail, a complete algorithm always terminate time complextiy O(2^n), space complexity O(n)\n\nevery inference algo for propos logic worst case complexity: exponential in the size of the input \n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \nentailment by theorem proving: applying rules of inference directly to the sentences in KB to prove the desired sentence;don't need to consult models in this case \n\ntable of logical equivalence (see notes) \n\nvalidity: sentence is valid if true in all models, also called tautology e.g. p or not p \n\ndeduction theorem: for any sents a and b, a entails b iff the sentence a implies b is valid \n\nvalid implication sentence -> a legitimate inference \n\nsatisfiability: a sentence is satisfiable if it is true in/ satisfied by some model \n\na entails b iff a AND (not B) is unsatisfiable \n\ninference rule (see notes) \n\nsearching for proofs using inference rule \n\nfinding a proof more efficient since proof dont care about irrelevant propositions, no need for exponential models checking \n\nmonotonicity of logical systems: if KB entails a, then KB AND b can still entail a; means can add in conlucions but not invalidate what we have before; implies soundness coz it will only derive entailed sentences \n\nProof by resolution: \n\nresolution, a single inference rule, yielding complete inference algorithm when used with complete search algo \n\nresolution inference rule (see the notes) \n\nfactoring: remove multiple copies of literals, e.g. A AND A reduced to A \n\na resolution-based theorem proveing can decide whether a entails b for any a,b in propositional logic \n\nConjuctive normal form CNF: \n\nresolution rule applies only to disjunctive of literals (also called clauses), \n\nevery sent is logically equivalent to a conjunction of disjunctive of literals (see notes) \n\nA resolution algorithm (PL-resolution): \n\nto show KB entails a -> to show KB AND not a is unsatisfiable \n\nconvert KB AND not a into CNF, then run the algo (see notes) \n\nPL-resolution is complete, always terminate \n\nresolution closure RC(S): the set of all clauses derivable \n\nevery definite clause can be transalted into an implication: premise is conjunction of positive literals, conclusion is the single positive literal \n\ninference with horn clause can use forward-chaining and backward-chaining \n\nentailment with horn clause: time is linear in the size of the KB \n\nfoward chaining is sound and complete \n\n\n\n \n\n## Module 7 Lecture Notes\n \na KB has background information \n\nKB agent can assert new knowledge into KB, and also query the KB and ask to derive new knowledge, so as to select actions \n\nlogic defines the semantics (meanings) of the sentenes in KB; semantics defines the truth of the sents in models \n\n\nresolution algorithm specified here: \n\nto show KB entails a, show KB AND not a is unsatisfiable. \n\n1) first convert KB AND not a into CNF \n\n2) apply the resolution rule to the clauses \n\n3) resolve every pair having the complementary literals to get new clause \n\n4) add the new clause to the set if it never been seen \n\n5) continue until: no new cluase can be added (KB cannot entail a); two clause resolve to yield empty clause(KB entail a) e.g. arise of P and not p lead to empty clause \n\n\nhorn clauses are closed while resolution; apply resolution to horn clause get a horn clause \n\n\nforward chaining: data driven reasoning, dont have specific query in mind;start with known data, add premise, apply forward chaining to derive conclusion\n\nbackward chaining: goal-directed reasoning; work backwards from query; if query true, no work to do; otherwise, finds implications in KB which can conclude to query;if all premises is true, query is true\n\nforward and backward chianing both work in linear time with efficient implementation\n\n  \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning over the internal representation of knowledge to select actions\n* **Knowledge base** - a set of sentences using knowledge representation language, represent opinions of the world\n* **Axiom** - sentence being given rather than being derived\n* **Inference** - derive new setences from the old ones\n* **Logic** - a general class of representations\n* **Sound/ truth-preseving** - inference algo only derives entailed sentences\n* **Syntax** - structure of sentences, defines allowalbe sentences\n* **Semantics** - the way how the truth of sentences are determined\n* **Atomic sentences** - consist of only one propositional symboll which can be True or False\n* **Complex sentences** - built from simpler sentences, using parentheses and logical connectives\n* **Logical connectives** - five types, not (negation), and, or, implies ->, if and only if\n* **Logical equivalence** - sentences a and b both true in same set of models/ iff a entails b and b entails a\n* **Define a proof problem for searching** - initial state (initial KB), actions (top of inference rule), result (bottom of rule), goal (sent trying to prove)\n* **Definite clause** - a disjunction of literals with only one is postive, not A OR not B or C\n* **Horn clause** - disjunction of literals where at most one is positive\n* **Goal clause** - clause with no positive literals\n* **K-cnf sentence** - CNF sent where at most k literals in each clause\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "20c29a92-005f-4da6-f572-feba8559050c"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nPassing the Turing test: NLP+knowledge rep+automated testing+ML. (+robotics + CV) total Turing test.\n\nLearn human thoughts: introspection+psychological experiments+brain imaging.\n\nAgents: act autonomously, perceive environment, persist over time, adaptive to changes, goal-oriented.\n\nRational agents: always acting optimally.\n\nlimited rationality: not enough time for computation.\n\nvalue alignment problem: goals for the machines should align with the human's original thought (transfer well).\n\n\n\n  \n\n## AIMA Chapter 27.1 The Limits of AI\n weak AI: act as thinking (simulating); strong AI: actually thinking. \n\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Chinese room, biological naturalism, consciousness, qualia \n\n## AIMA 2.1 Agents and Environments\n \nAgents: anything that perceive environment via sensors and act via actuators. \n\nPercept sequence: the complete history of what the agent has perceived before. \n\nChoice of actions only depends on its knowledge and the up-to-date percept sequence, not on any future stuff. \n\nAgent function: describe agent's behavior and maps percept sequence to actions. \n\nAgent program implements agent function. agent funcion is abstract maths descriptions, agent program is implementation. \n\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nPerformance measure: evaluates sequence of envirnment states. \n\ndesign the performance measures based on what one wants to achieve instead of how we think the agt should behave. \n\nRational agents: choose the optimal action (maxmise the expected value) based on the percept seq and built-in knowledge. expected value here\ncoz the agent doesn't know what the actual outcome is since limited computation resources\n\nRational agents should do Information gathering: act to modify future percepts; explore the env. \n\nRational agents should Learn as much as P from its perception.\n\nLack Autonomy: relies on the prior knowledge rather than percept and learn \n\nautonomous -> finally independent of the prior knowledge\n\n\n\n## AIMA 2.3 The Nature of Environments\n \nThe first step is to Specify the task environment as fully as we can: performance measure, env, actuators, sensors (PEAS) \n\nsingle agents vs multi agent: whether B can be viewed as an agent depends on whether B's performance measure's value (have its own performance measure)needs to be maximise based on agent A's actions. \n\ncooperative vs competitive multiagent env. \n\nstochastic vs nondeterministic env: the former one deals with exact probabilities, the latter one list unquantified probability.\n\nepisodic vs sequential: whether the current decisions affect the future decisions (think ahead) \n\nstatic vs dynamic: whether the env can change while agent is deliberating \n\ndiscrete vs continuous \n\nknown vs unknown (not a property of the env): whether the agents know or don't know how to make good choices \n\n \n\n## AIMA 2.4 The Structure of Agents\n \nagent = architecture + program \n\nagent program takes in only current percept while agent function may base on the whole percept history \n\nSearch and planning - find action sequences which achieve the goals \n\nmodel based reflex agents: transition model+ sensor model + state + action + percept \n\ngoal based agents: add goals to the above \n\nutility-based rational agents: select the actions maximising the expected utility of the outcomes\nlearning agents: learning elements + performance element + critic + problem generator \n\natomic vs factored vs structure representation \n\n\n\n## Module 1 Lecture Notes\n \nperformance measure: an objective criteria for how successful the agent's behavior is given the evidence by the percept seque \n\ngiven PEAS task env, construct agent function maximising the expected value of the perform measureand then design the agent program implementing f on particular architecture (from abstract maths descrip to concrete implemtn) \n \nproblem solving agents must plan ahead (consider the sequence of act to the goal, called search).\n\nproblem formulation with prob-solving agents: formulate goal, search problem(states, actions, performance measure) then find solution \n\n \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Softbot** - software agent\n* **Fully observable environment** - sensors knows the complete state of the env \n* **Effectively fully observable environment** - sensors detect all relevant things to the action choice\n* **Partially observable environment** - probs with sensors/ parts of the state missing from the sensor data\n* **Unobservable environment** - agents don't have any sensors\n* **Deterministic environment** - the next state of the env is fully based on the current state and the executed action\n* **Nondeterministic environment** - the contrary of the above\n* **Semidynamic environment** - env doesn't change but the agent's performance score changes when considering the time passes\n* **Agent architecture** - devices(sensors + actuators)\n* **Simple reflex agent** - choose actions only on the current percept\n* **Utility function** - an internalisation of the performance measure\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n \npython features: \n\nconcise, whitespace delimited syntax, garbage collected, portable on major platforms without change on programs,abundant built-in types, suport libraries \n\nwhitespace is meaningful, adopt newline to end a line of code \n\nuse indentation for block struc \n\nall data considered as objects; objects deleted automatically once unreachable  \n\nstrong and dynamically typed \n\nNone, generator, function is also a type \n\nPython is strongly typed because each object has a fixed type.\\ \nThe interpreter doesn't allow operations/actions which are not compatible with the type of the object. An example could be \"we\" + int(2). \n \n\nPython is dynamically typed since a variable doesn't have a fixed type. Variables come into existence when first assigned. The type of the object is determined at runtime. It can be assigned again. Variables can be associated with different objects of different types.An example is that:x = 5 \n \nx = \"222\"\n\ntype errors can only be found at runtime \n\n\nJava is static typing: variables can only refer to objects which has a type declared;to enforce contracts, methods use type signatu: public static void main... \n\nPython functions don't have type signatures; \n\n\npython math basic: 2e9, True, False, **(power), %, +=, &=, but no ++/-- like c++ \n\n\nstrings: \n\ncan use single/double quotes to create; triple quotes for multiline or docstr;\n\nuse + to concentenate; \n\nprefix with r = raw: r'\n' means character slash and n, not special characters \n\nformatting: use %, placeholder; print(\"%s can speak %d languages\" % (\"C\", 6)) \n\nstring and tuple is immutable, list is mutable, a=b[:] will get a shallow copy (a new object) \n\n\n'==' checks whether variables are pointing to the objects with same value (can be different objects);\n\n'is' checks whether variables are pointing to the same object \n\n\ntuple: immutable, ordered sequence, items can have mixed types including collection types \n\nstrings: immutable, regularly unicode, 2-byte characters \n\nlist: mutable, ordered, mixed types item \n\n\ndictionary: unordered, work by hashing, keys must be immutable; constant avg time add, lookup, update \n\nkeyerror if the specified key not found \n\ndefaultdict: automatically initialised nonexistent values for missing keys \n\ncounter \n\n\nfunctions:\n\ndont need to declare the types of arguments or result \n\nsupport multiple return values (the return type is a tuple) while java need to use a object \n\nno function overloading: \n\nfunction specified by name alone, ignorant of types of argument, two functions can't have the same function name even if with different numbers, order, name of args \n\nbut allow operator (+, ==,...) overloading; \n\nnon-default argument of a function should lie in front of default arguments, otherwise will raise syntaxerror \n\n\nfunctions can be called with arguments out of order; positional argument must be placed in front of all the keyword argument when calling the function, otherwise raise syntax error. \n\nexample: def myfun(a,b,c) myfun(a=2, b=3, 5) will have syntac error; myfun(2, a=3, c=5) will also error coz there will be multiple a \n\n\n*args: accept a variable numver of non-keyword arguments (keyword arguments means when passing into a function: project = \"aa\", project is a keyword argument) \n\n**kwargs: accept a variable of keyword arguments \n\n\npython use dynamic scope: function only see the most current value of variables \n\ndefault arguments & memorization \n\n\nfunctions are first-class objects in python, \ncan be passed to a function and returned as values, create and destroy,\ncan assign functions to var/ store them in data struc\n\n\nhigher order functions: input has functions \n\nclass: \n\nmember method is inside a class \n\n\nsubclasses: extend a class (origin class: superclass, parent, ancestor);e.g. class AI_student(Student): (student is the superclass) \n\ncan do mutiple inheritance \n\n\nredefine methods: call methods of ancestor in member method: parentclass.methodname(self,a,b,c) \n\n\nmagic methods \n\npython doesn't have built-in main method \n\nduck typing: build sutability of an object by determin presence of methods \n\n\nlist comprehension: [expression for name in list if filter] \n\ndictionary, set comprehension \n\n\niterators have __iter__ (create iterator), __next__; can call next(i), i.__next__(), i.next(), can catch the stopiteration exception ; no hasnext() method \n\nto be iterable: has __iter__ method; to be iterator: has __next__method \n\niterators efficiently utilise memory \n\ngenerator: is iterator; yield automatically return generator when called \n\neach time calling __next__, method runs until encounters a yield statement, then stops and returns the yielded value; next time resume from where it stops \n\n\nbenefits of using generators: \n\nvalues computed one at a time, save memory, especially for infinite sequences, bad if inspect individual values are needed \n\n\nimportlib: helpful using importlib.reload(), while reloading code from a file \n\n\n\n \n\n## Module 2 Definitions\n* **Repl** - Read-Evaluate-Print Loop, convenient for testing\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \ngoal formulation, problem formulation(describe the necessary states and actions to the goal, an abstract model), search, execution \n\nsolution: fixed sequence of actions in fully observable, deterministic, known env; branching strategy in partially observable/ nondeterministic env \n\ntransition model is used to explain what each action does \n\nabstraction, level of abstraction, valid abstraction \n\nsearch algorithm consider states and actions as atomic without internal struc\n\n\n\n## AIMA Chapter 3.2 Example Problems\n \nstandarised problem vs real-world prob \n\n \n\n## AIMA Chapter 3.3 Search Algorithms\n \nBest-first search: graph search with evaluation function \n\nfrontier uses a queue, priority queue pops the node with the min value first \n\nRedundant paths: \n\n1) repeated state generates a cycle (loopy path), then the search tree is infinite \n\n2) paths which need not to be considered (Arad-Zerind-Sibiu coz we have Arad-Sibiu) \n\nremember all history states allows to check for redundant paths. \nMeasure problem-solving performance: completeness, cost optimality, time complexity, space complexity \n\nnot complete: cycles, loops, not systematic on infinite state spaces \n\nsystematic search strategy affects completeness\n \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \nuninformed search: \n\nbreath-first search: \n\nwhile all actions cost the same, systematic, complete on both finite and infinite state spaces, can do early goal test; always find a optimal solution when all actions have the same cost (not optimal if actions' cost vary); time and space complexity: O(b^d)\n\n\n\nDijkstra (without a goal) or uniform search (has goal): spread out in uniform path cost; late goal test; complete, cost-optimal \n\nDfs: first choose the deepest node in the frontier to expand; tree-like search; not optimal; not systematic in infinite state spaces, stuck in infinite path (even if no cycles) thus incomplete (complete on finite state spaces if checks for repeated states, cycles);\ntime complexity: proportional to the states number, is O(b^m), terrible if m is much larger than d; but if solution is dense, much faster than bfs); space complexity O(bm), m is the maximum depth of the tree; backtracking search time: O(m)\n\nDepth-limited search: no infinite-path problem; not always complete (incomplete when l<d); not optimal (e.g. when l>d); time complexity: O(b^l), space: O(b*l); choice of l determines completeness; diameter of the state-space graph -> good depth limit\n\nIterative deepening search: picking limit from 0 until a solution is found or report failure; goal can always be found at depth d; time and space compexity: O(b^d), O(bd) with a solution, O(b^m), O(bm) without a solution on finite state space;optimal while actions cost the same; complete on finite acyclic state spaces, or any finite state space if we check for cycles;saves memory at the cost of more time coz it does not keep the previous levels in memory and keeps repeating them  \n\nBidirectional search: for speedup; time and space complexity: O(b^(d/2)), O(b^(d/2)) \n\nm is the maximum depth of search tree; d is the depth of the shallowest solution\n\n\n\n \n \n\n## Module 3 Lecture Notes\n \nin partially observ or nondetem env, solution recommend future actions depend on the percepts; recommend in the form of branching strategy \n\nsearch algorithm enumerate all poosible paths in certain orders from the inital state \n\ntree search, node is generated through transition model; treats differnt paths to the same node as distinct \n\nnode is not state; node include state, parent-node, children, action, path-cost, depth\n\nrepeated states turn linear problem into exponential one \n\nbig O notation ignores constant multiplicative factors, if not constant, cannot be ignored; also ignore size of fixed data structure, only fixed! \n\nuse DFS if space is restricted; no infinite paths; many solutions are possibly long paths; wrong paths terminate quickly; search can be quickly fine-tuned \n\nuse BFS if has possible infinte paths; solutions have short paths; can quickly gives up unlikely branch and paths \n\n\n \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search (use atomic representations)\n* **Planning agents** - use factored or structured representations of states\n* **Search** - find a sequence of actions to the goal\n* **Open-loop** - ignore the percepts\n* **Closed-loop** - monitor the percepts\n* **Environment** - state space graph\n* **Search problem** - state space (graph), initial state, goal states, actions, transition model, action cost function\n* **Optimal solution** - lowest path cost among all solutions\n* **Search algorithm** - input: search prob, output: solution / failure\n* **Frontier** - reached but unexpanded nodes\n* **Interior** - expanded nodes\n* **Exterior** - nodes that have not been reached\n* **Reached node** - has a node generated no matter whether they have been expanded or not\n* **Best-first search** - choose a node which is of min value of evaluation function f(n)\n* **Graph search** - checks for redundant paths, costs more memory but faster\n* **Tree-like search** - does not check for redundant paths, less memory but slower\n* **Completeness** - the algorithm is guaranteed to find a solution if there is any, and can report failure\n* **Cost optimality** - the algorithm can find the solution with lowest path cost\n* **Time complexity** - number of nodes generated in worst case\n* **Space complexity** - number of nodes simultaneously in memory in worst case\n* **Uninformed search** - no idea how close the state to the goal\n* **Bidirectional search** - search forward from the initial state and meanwhile backewards from the goal states, till two search meets (if they can)\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \nGreedy best-first search: f(n) = h(n); not optimal, generally not complete (complete in finite SP with no loops but incomplete in infinite SP, or finite state space with loops);time, space complex: both O(|V|), with good h(n) can reduce to O(bm)\n\nA* search: \n\nf(n) = estimated cost of the lowest cost path continuing from n to the goal state; \n\ncomplete; cost-optimal if h(n) is admissible (never overestimate the cost to the goal; optimistic); inadmissible h(n), may/ may not be cost optimal\n\nconsistent h(n) is admissible (not vice versa), and the first time the state has been reached and it will be on the optimal path;\n\nSearch contours: concentric (no line cross each other), spread out towards the goal states while uniform search spreads out equally in all directions;\n\nA* with consistent h(n) is optimally efficient; A* is efficient coz it prunes search tree nodes not necessary for searching the optimal solution \n\nspeedy search: a kind of unbouded-cost search, f(n) = h(n) = # of actions needed to reach the goal ignorant of the action cost, no g(n) \n\naddress the memory prob of a* search: beam search, IDA*, Recursive best-first search (RBFS), \n\nRBFS uses linear space, is optimal if h(n) is admissible, space complexity: linear in the depth of the deepest optimal solution; time complexity: hard to tell \n\nRBFS and SMA* are optimal; having enough time they can solve problem which don't have enough memory to use A* \n\nIDA* , RBFS , SMA* : optimal, all more space efficient than A* \n\nBidirectional heuristic search: evaluation function use f2(n) = max(2g(n), g(n)+h(n)); sometimes more efficient than unidir but sometimes not; optimal and completeif using the f2 evaluation and admissible h(n) \n\nfront-to-end search vs front to front search (estimate the distance to other frontier)\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n \nthe effect of h(n) accuracy on performance: \n\neffective braching factor b*: close to 1 if the h(n) is well-designed \n\neffective depth: search cost from O(b^d) to O(b^(d-kh)), kh is a constant \n\nh2 dominates h1 if for any node n, h2(n) >= h1(n), h2 expands nodes no more than h1 \n\ngeneral h(n) from Relaxed problem: derived h(n) from the actual cost of the relaxed prob is admisslb and consistent \n\ngenerate h(n) from subproblem: store precomputed solution costs for subproblems in pattern database, disjoint pattern db, \n\ngenerate h(n) from defining landmark(efficient but not admissible), differential heuristic (admissible and efficient) \n\nLearning to search better:\n\nmetalevel state space vs object-level state space \n\nmetalevel learning: learn and avoid exploring unpromising subtrees; minimise the total cost of solving the prob, makeing tradeoff between computational cost and path cost \n\nLearning h(n) from experience with the problem class: learn h(n) using features, e.g. h(n) = c1x1(n) + c2x2(n) \n\n\n\n\n\n\n \n\n## Module 4 Lecture Notes\n \nuniform cost search: cost contours, favors the lower path cost \n\n \n\n## Module 4 Definitions\n* **Informed search** - problem definition + heuristic function\n* **Heuristic function** - estimate the cost of the lowest cost path from state n to the goal state\n* **Greedy best-first search** - choose the node closest to the goal to expand first (minimal h(n))\n* **Satisficing solutions** - inadmissible h(n), reduce the number of nodes to expand\n* **Weighted a* search** - f(n) = g(n) + W * h(n) , W>1, faster search time, fewer nodes expanded, focus on goal, suboptimal, complete\n* **Bounded suboptimal search** - search for solution that is within W*optimal cost\n* **Bounded-cost search** - search for solution costs < constant C\n* **Unbouded-cost search** - no cost bound, find it quickly\n* **Beam search** - limits frontier's size in k; may be incomplete and suboptimal, but faster, reasonably good solution\n* **Iteratively-deepening a* search (ida*)** - limit is each f(n)\n* **Recursive best-first search** - record the second-best path, and backtrack\n* **Simplified memory-bounded a* (sma*)** - expand the newest best node until memory gets full, and drops the oldest node with highest f(n) and backup\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \ncompetitive environment, conflicting goals -> adversarial search prob \n\nTwo-player zero-sum games (no win-win), perfect information (fully observable) \n\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\nthe optimal strategy in a game tree: to retrive the minimax value (the utility) of each state in the game tree, assume both players play optimally; \n\nminimax decision \n\nit's not always best to use the minimax strategy if the opponent is not playing optimally. \n\nminimax algorithm: complete depth-first search; time complexity: O(b^m), impratical for complex game; space complexity: O(bm) (generate all legal moves at once) / O(m) (generates actions one at a time); \n \noptimal decisions in multiplayer games: use vector to represent utility; \n\nif not zero-sum, two players might collaborate\n\nAlpha-beta pruning\n\nMove ordering: the order to examine the states affect alpha beta pruning; \n\nperfect move ordering: nodes to examine: O(b^(m/2)) while O(b^m) for minimax;branching factor reduced to sqrt(b) from b \n\nkiller moves: best moves, killer move h(n) \n\ntranspositions will cause repeated states then exponential increase in search cost; keep a transposition table which stores the h(n) of states \n\nShannon's Type A & Type B strategy: useful for games with large search space; make tradeoff about which part of the tree to search \n\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \ncutoff test at non-terminal & terminal states & heuristic evaluation function replace utility function \n\nevaluation function: expected value, weighted linear function \n\ncutting off search: iterative-deeping, when time runs out, returns the move chosen by the deepest completed search， might need to error if not quiesceent \n\nthe evaluation function should apply only to quiescent position where no pending moves can swing the evaluation wildly \n\nhorizon effect: difficult to prevent, opponent's move can cause serious damage but can be delayed temporarily; saying an agent attempt to erroneously delay the inevitable \n\nmitigate the horizon effect: allow singular extensions which are moves obviously best among all other moves, search deeper than the cut-off place \n\nForward pruning: \n\nprune moves which look bad, might have error; \n\nbeam search, most common forward pruning method, consider only the best n moves in a ply\n\nPROBCUT/probabilistic cut: use history statistics to choose the move to prune; estimate the prob of v would be outside (alpha, beta) \n\nlate move reduction: assume perfect move ordering, late moves less likely to be good moves, reduce the depth searching these moves rather than pruning them; if comes up with a better alpha, rerun the full depth \n\n\n\nSearch versus lookup: precompute best moves table of opening and endgame; instead of searching, solve the opening and endgame by lookup table constructed by retrograde minimax search \n\n \n\n## AIMA Chapter 5.5 Stochastic Games\n \nstochastic games: \n\nhave chance node: calculate the expected value (expectiminimax value) of the change node;\n\nhandle by expectiminimax O(b^m * n^m), n is the number of distinct rolls, m is the maximum depth of the game tree; \n\ncan do pruning if can find bound of the chance node \n\nMCTS: Monte Carlo Tree search: select moves randomly and play the game to the end; eval an action: play the game from that state repeatedly, then average the results  \n\n\n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nutility funcion, expected utility\nif agent maximise the utility function correctly correspond to the performance measure, then agent will get the highest possible performance score averaged over all possb env\n\n \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \naxioms of utility theory: constraints on rational preferences: orderability, transitivity, continuitysubstitutability, monotonicity, decomposability\n\nviolating those constraints will cause irrational action \n\nRational preference leads to utility: \n\na positive affine transformation of the utility function would not change the agent's behavior \n\nvalue function/ordinal utility function: only needs preference ranking rather than numeric value \n\n \n\n## AIMA Chapter 16.3 Utility Functions\n \nUtility assesment and scales:\n\nperference elicitation, normalised utilities, choose between S and standard lottery, /\nmonotinic perference; unbiased; optimizer's curse; human judgment and irarationality \n\ndecision theory: normative theory descrbiing how a rational agent should act, while descriptive theory describes how actual agents really act \n\nhumans have predictable irrationality: certainty effect, ambiguity aversion, framing effect, anchoring effect \n\ndecision theory: what agent should do, combining probability theory (what agent should believe based on evidence) + utility theory (what agents want) \n\n\n\n\n## Module 5 Lecture Notes\n \nstatic env: no change to env while agent is deliberating \n\nstrategic env: next state is determined by current state and action by the agent and the other agent \n\neven levels for MAX, odd levels for MIN \n\nevaluation function assign values to node based of static feature without reference to path\n\nchess evaluation functions: weighted sum of positional features \n\nminimax: \n\na state-space search tree \n\nthe backed-up val of each node is decided by values of its children \n\nMAX never allows a move less than alpha for MAX; MIN never allows a move better than beta for MAX;\nstop evaluting a branch when evaluting a max node having a value v >= beta is backedup; when evaluting min node having a value v <= a is backed-up \n\na random variable = an event who has unknown outcome\n\na probability distribution = assignment of weights to outcomes \n\nobjectivist (frequentist answer): averages over repeated experiments empirically from historical observation; subjectivist (Bayesian anwser): belief on unobserved variables, e.g. belief that raining given the temperature \n\n\n \n\n## Module 5 Definitions\n* **Pruning** - improve efficiency by ignoring the part of the search tree which does not affect the optimal move\n* **Game (definition)** - initial state, to-move(the current player), legal action, result(transition model), terminal test, utility function\n* **Utility function/objective function/payoff function** - the value achieved to player if the game ends in the terminal state s\n* **State space graph** - initial state, action function, result function\n* **Game tree** - a search tree following all actions sequences to the terminal state (may be infinite)\n* **Ply** - how many levels of the game tree regardless of the terminal states\n* **Alpha** - lower bound on max's outcome; the highest value choice found so far at any choice point along the MAX path\n* **Beta** - upper bound on min's outcome; the lowest value choice found so far at any choice point along the MIN path\n* **Type a strategy** - keeps all possible moves at a depth in mind, wide but shallow\n* **Type b strategy** - ignore some appearing bad and focus on the promising ones; deep but narrow\n* **Heuristic evaluation function** - estimate the expected utility of the state for the player\n* **Weighted linear funcion** - EVAL(s) = w1f1(s) + .. + wnfn(s), fi is the feature, wi is the weight\n* **Utility function** - express how desirable is the state for the agent using a number\n* **Principle of maximum expected utility (meu)** - rational agents selects anctions maximising its expected utility\n* **Orderability** -  the rational agent must prefer one choice over the other, or consider them equal\n* **Transitivity** - if prefer a to b, and prefer b to c, then prefer a to c\n* **Continuity** - A>B>C, then under some probability, the rational agent indifferent between 100% B and lottery that is p,A; 1-p, C\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCSP:\nrepresent a state with a set of var/value pairs and conditions for a solution by set of constraints on vars\n\nassign values to variables satisfying constraints \n\nsolving CSP - NP-complete problem generally \n\nuse factored representation: a set of variables, each with value \n\nVariables, domains, constratins \n\nrelation: <(X1,X2), X1>X2 > \n\nconstraint graph to visualise the CSP, constraint hypergraph \n\ndiscrete, continuous (linear programming problem), finite, infinite domains \n\nany CSP can be transformed into CSP with only binary constratins \n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nconstraint propagation: inference, reduce the legal moves of variables using constraintscan be done with search, or before the search \n\nenforcing local consistency is used to do constraint propagation \n\nlocal consistency type: \n\nnode consistency, \n\narc consistency: \n\na graph is arc-consistent if every var is arc-con with every other var; \n\nAC-3 to enforce the arc consistency: time complexity O(cd^3) or O(n^2*d^3), coz c= 2*n*(n-1), c arcs, d domain size, n variables: \n\nPlace all the arcs in a queue. Pop arcs. For each arc Xi, Xj, remove inconsistent values from Xi. If we change the values of a node, add its arcs Xk, Xi to the queue (except Xj, Xi). Terminate when the queue is empty. \n\npath consistency,\n\nk-consistency: any set of k-1 variables with consistent assignment, the kth variable can be assigned a consistent value \n\nstrongly k-consistent: k-consistent, also k-1, k-2 ..., 1-consistent \n\nsolving strongly n-consistent prob with n nodes: time complexity O(n^2*d); first choose a consistent value for X1,then choose a value for X2 since graph is 2-consistent,..\n\nestablish n-consistency takes time and space exponential in n\n\nglobal constraint, resource constraint (at most m resources, but need n>m at least, thus not consistent ) \n\nCSP formalism is powerful coz for each new problem, once we define the problem in terms of constraints, then it can be solved by a general CSP solving mechanism \n\nsolving arbitrary csp costs exponential time in n, which is # of the variables.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nconstraint propogation left some variables with multiple choices -> use search \n\nfor csp, the search tree will end up with complete assignment at depth n (number of variables); n! * d^n leaves, only d^n possible complete assignments \n\nCSP has property of commutativity, if using this property, the number of leaves is d^n \n\nbacktracking search algorithm in CSP; can use domain-independent h(n) to improve the search \n\n1) Variable and value ordering: \n\nselect-unassigned-variable strategy: minimum-remaining-values (MRV) heuristic to choose the variable with the least possible values; more powerful, not fit for the beginning \n\ndegree heuristic: helps in the beginning; choose the variables invoving in the biggest # of constraints on other unassigned var; reduce branching factor; can be tie-breaker \n\nleast-constraining-value to select what order to examine the value in the domain: prefer value that rules out the fewest choices, allow maximum flexible choices for the neighbouring var;\n\n2) Interleaving search and inference: \n\ninference can be used during search, such as forward checking, userful in backtracking searchbut doesn't look ahead far enough so that cannot detect all inconsistency; \n\nMaintaining Arc Consistency (MAC): recursive constratints propogation, more powerful than forward checking; \n\nMAC and AC3:\nMAC interleaving search and inference, AC-3 is pure inference; MAC runs while assigning variables in backtracking search.MAC only queues arcs incident on the assigned variable, AC3 queue all arcs. Then MAC runs identically to AC-3. \n3) Intelligent backtracking: looking backward:\n\nuse backjumping: a cleverer way to back up, not waste time changing var which can't fix the prob  \n\nforward checking can provide the conflict set without extra work \n\nwith forward checking or MAC, no need to do backjumping; they prune the same\n\nconflict-directed backjumping: see the algorithm \n\n4) Constraint learning: \n\nprevent from running the same prob again\n\nrecord and forbid the no-good by adding constraints to avoid and keeping seperate cache \n\nno-goods are effective when using forward checking or backjumping \n\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nlocal search: \nrandomly place a complete assignment, randomly select one conflict member, use min-conflict heuristic to select the move which costs least conflicts,  terminate until no conflict \n\n runtime of min-conlict is independent of problem size \n\ntabu search, constraint weighting \n\nlocal search can be adaptive to the problem changes in an online setting \n\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \ncomplexity of solving CSP relates to the structure of the constraint graph\n\ndecompose into subprob; independent subprob; \nn/c subprob, each subprob has c var and needs d^c to solve, the total work is O(d^c * (n/c)), linear in n, while without the decoposition, the total work is O(d^n), exponential in n;\n\na constrain graph is a tree structure if any two vars are connected by only one path \n\ntree-structured CSP can solve in time linear in n which is the # of varaibles due to directional arc consistency (DAC);contruct DAC time is O(n*d^2), linear in n; find solution in linear time; if no solution, it can detect contradition; no need to backtrack, simply march down \n\nreduce graph to tree: by removing nodes or by collapsing nodes together \n\ncutset conditioning: \n\nreduce the general csp into a tree-structured csp \n\nchoose a subset S (cycle cutset) and assign values, then the remaining graph becomes a tree; remove the values to be consistent with S in other variables; join the two solutions, S and the tree \n\nthe total run time is O(d^c * (n-c)*d^2) \n\nTree decomposition: \n\ntransform the original graph into a tree of subprob if the prob satisfy three requirements \n\na domain is a set of tuples of values in the decomposed tree \n\ntree-csp-solver: O(n*d^2) (not talking about tree decomposition), efficient as long as d is small \n\na graph can have many tree decompositions; select the one making the subproblem as small as possible \n\nCSPs with constraint graphs of bounded tree width can be solved within polynomial time O(n*d^(w+1)), w is the tree width; tree width is the minimum width among all the tree decompositions of the graph \n\nsave search time: use tree decomposition if the tree width is small\n\nsave memory: use cutset conditioning which is linear memory if small cutset can be found, while tree decomp use memory exponential in w \n\nCutset conditioning is efficient if found a small cutset. But generally, no more efficient than solving a CSP directly. \n\nvalue symmetry (d!), symmetry-breaking constraint\n\n \n\n## Module 6 Lecture Notes\n \nplanning vs identificaion: seq of actions vs varibles value assignment (path is the same depth, goal is important not the path) \n\ncsp solution should maximise the objective function \n\ncsp benefits: 1)formulate it and can be solved with a general solver; 2) knows which variable violates constraints and focus on search; 3) automatically prunes illgeal branches \n\ncontinuous variables, linear constraints, solvable in polynomial time using linear programming \n\nvariable assign is commutative thus tree search not graph search;thus only need to consider assign a single variable at each node, then branching factor b=d, and now d^n leaves \n\nbacktracking in uninformed in csp if without using heuristic\n\nfour heuristic: mrv, degree heu, least constraining value, foward checking \n\ndtect failure early: use forward checking(also a heuristic) \n\nx->y is consistent iff every value of x assigned, still some allowed value for y \n\nplanar constraint graphs: each pair has only one arc, number of arcs linear in n, time complexity is O(n*d^3))\n \n\n## Module 6 Definitions\n* **Consistent assignment** - does not violate any constraints; also called legal assignment\n* **Complete assignment** - every variable has been assigned a value\n* **Solution to csp** - complete and consistent assignment\n* **Partial solution** - consitent assignment but partial (not complete)\n* **Unary constraint** - limits on only one variable\n* **Binary constraint** - limits on two variables\n* **Binary csp** - only with unary and binary constraint\n* **Global constraint** - limit arbitrary # (no need to be all) of variables\n* **Alldiff** - all variables in the constraint should have distinct values\n* **Absolution constraints vs preference constraints** - pref: tell which is the prefered solution; pref often encode as costs\n* **Constrained optimization problem cop** - solve CSP with preference constraints\n* **Node consistent** - for a single variable, all values in the domain satisfy the unary constraints of the variable\n* **Arc consistent** - Xi is arc-consistent to Xj if for every value in Di, Dj exists value satisfy Xi Xj binary constraints \n* **Path consistent** - two-variable set path-consistent to a third variable Xm; given {Xi, Xj} consistent, Xm can satisfy {Xi,Xm} and {Xm, Xj}\n* **Bound consistent** - every variable X and its upper and lower bound, some value of Y can satisfy constraint X,Y for every Y\n* **Forward checking** - when X is assigned, delete inconsistent value with X from unassigned Y which constraint connected to X\n* **Chronological backtracking** - back to most recent decision point\n* **Backjumping** - backtrack to the most recent assignment of variables in conflict set\n* **Constraint learning** - find a minimum set of var causing the contradition prob from the conflict set \n* **No-good** - the set of variable and their corresponding value assignment leading contradition/failure assignment\n* **Tabu search** - keeping a tiny list of recently visited states and avoid to return to these states\n* **Constraint weighting** - focus on searching on significant constraints\n* **Directional arc-consistent dac** - if and only if every Xi is arc-consitent with Xj for j>i (has ordering)\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nagent program does three things when called: tell the KB its percept; asks the KB what actions to do; tells the KB what action has been chosen and returned the action so that exectued \n\nknowledge level, implementation level \n\ndeclarative approach (tell the agents till it knows how to operate) vs \nprocedural approach (encodes desired behaviors directly in the program code); often combine together now \n\n \n\n## AIMA Chapter 7.2 The Wumpus World\n \nthe conlution is guaranteed to be correct given correct available information \n\n \n\n## AIMA Chapter 7.3 Logic\n \nsemantics must be defined by a logic, which are truth of each sentence in each model \n\nif sentence a is true in model m (m is the possible world), m satisfy a, or m is a model of a, using M(a) \n\nto refer to the set of all models of a \n\nlogical entailment: a entails b, if and only if in every model a is true, then b is also true. M(a) belongs to M(b) (subset)set a is smaller or equal to set b \n\none logical inference algorithm: model checking: enumerates all possible models to check that b is true in all models in which a is true, then a entails b (works for finite model space) \n\nif an inference algo i can derive a from KB, a is derived from KB by i, sees the sign pic \n\ndesirable property of inference: \n\nsound/truth preserving\n\ncompleteness: algo can derive any sentence which is entailed \n\nif KB is true in real world, all sentence derived from KB by sound inference is true in real world \n\ngrounding: connection between logical reasoning and real env agent in; grounding can be based on agent's sensors, connect KB to real world \n\nlearning can produce general rules in KB \n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \nSyntax: \n\nlogical connectives: \n\nnot: literal: an atomic sentence (a positive literal)/ a negated atomic sent (a negative literal) \n\nand: conjunction, its elements are conjuncts \n\nor: disjunction, disjuncts \n\nimplies: implication (or called conditional); a->b, a is the premise/antecedent b is conclusion/consequent; implication also called rules/ if-then statements \n\nif and only if: biconditional \n\nnot operator has the highest priority \n\nSemantics: \n\nsemantics for propositional logic must specify  given a model, for any sentence, how to compute the truth value \n\nP imples Q is true unless P is true and Q is false in model m \n\nP biconditional implying Q iff P and Q are both T or both False in m\n\nuse truth table to compute (see notes) \n\ninfenrence algorithm to decide whether KB entails sentences a: TT-entails? recursively enumerate a finite space of assignments to symbols; this is a sound algorithm only entail, a complete algorithm always terminate time complextiy O(2^n), space complexity O(n)\n\nevery inference algo for propos logic worst case complexity: exponential in the size of the input \n\n \n\n## AIMA 7.5 Propositional Theorem Proving\n \nentailment by theorem proving: applying rules of inference directly to the sentences in KB to prove the desired sentence;don't need to consult models in this case \n\ntable of logical equivalence (see notes) \n\nvalidity: sentence is valid if true in all models, also called tautology e.g. p or not p \n\ndeduction theorem: for any sents a and b, a entails b iff the sentence a implies b is valid \n\nvalid implication sentence -> a legitimate inference \n\nsatisfiability: a sentence is satisfiable if it is true in/ satisfied by some model \n\na entails b iff a AND (not B) is unsatisfiable \n\ninference rule (see notes) \n\nsearching for proofs using inference rule \n\nfinding a proof more efficient since proof dont care about irrelevant propositions, no need for exponential models checking \n\nmonotonicity of logical systems: if KB entails a, then KB AND b can still entail a; means can add in conlucions but not invalidate what we have before; implies soundness coz it will only derive entailed sentences \n\nProof by resolution: \n\nresolution, a single inference rule, yielding complete inference algorithm when used with complete search algo \n\nresolution inference rule (see the notes) \n\nfactoring: remove multiple copies of literals, e.g. A AND A reduced to A \n\na resolution-based theorem proveing can decide whether a entails b for any a,b in propositional logic \n\nConjuctive normal form CNF: \n\nresolution rule applies only to disjunctive of literals (also called clauses), \n\nevery sent is logically equivalent to a conjunction of disjunctive of literals (see notes) \n\nA resolution algorithm (PL-resolution): \n\nto show KB entails a -> to show KB AND not a is unsatisfiable \n\nconvert KB AND not a into CNF, then run the algo (see notes) \n\nPL-resolution is complete, always terminate \n\nresolution closure RC(S): the set of all clauses derivable \n\nevery definite clause can be transalted into an implication: premise is conjunction of positive literals, conclusion is the single positive literal \n\ninference with horn clause can use forward-chaining and backward-chaining \n\nentailment with horn clause: time is linear in the size of the KB \n\nfoward chaining is sound and complete \n\n\n\n \n\n## Module 7 Lecture Notes\n \na KB has background information \n\nKB agent can assert new knowledge into KB, and also query the KB and ask to derive new knowledge, so as to select actions \n\nlogic defines the semantics (meanings) of the sentenes in KB; semantics defines the truth of the sents in models \n\n\nresolution algorithm specified here: \n\nto show KB entails a, show KB AND not a is unsatisfiable. \n\n1) first convert KB AND not a into CNF \n\n2) apply the resolution rule to the clauses \n\n3) resolve every pair having the complementary literals to get new clause \n\n4) add the new clause to the set if it never been seen \n\n5) continue until: no new cluase can be added (KB cannot entail a); two clause resolve to yield empty clause(KB entail a) e.g. arise of P and not p lead to empty clause \n\n\nhorn clauses are closed while resolution; apply resolution to horn clause get a horn clause \n\n\nforward chaining: data driven reasoning, dont have specific query in mind;start with known data, add premise, apply forward chaining to derive conclusion\n\nbackward chaining: goal-directed reasoning; work backwards from query; if query true, no work to do; otherwise, finds implications in KB which can conclude to query;if all premises is true, query is true\n\nforward and backward chianing both work in linear time with efficient implementation\n\n  \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use reasoning over the internal representation of knowledge to select actions\n* **Knowledge base** - a set of sentences using knowledge representation language, represent opinions of the world\n* **Axiom** - sentence being given rather than being derived\n* **Inference** - derive new setences from the old ones\n* **Logic** - a general class of representations\n* **Sound/ truth-preseving** - inference algo only derives entailed sentences\n* **Syntax** - structure of sentences, defines allowalbe sentences\n* **Semantics** - the way how the truth of sentences are determined\n* **Atomic sentences** - consist of only one propositional symboll which can be True or False\n* **Complex sentences** - built from simpler sentences, using parentheses and logical connectives\n* **Logical connectives** - five types, not (negation), and, or, implies ->, if and only if\n* **Logical equivalence** - sentences a and b both true in same set of models/ iff a entails b and b entails a\n* **Define a proof problem for searching** - initial state (initial KB), actions (top of inference rule), result (bottom of rule), goal (sent trying to prove)\n* **Definite clause** - a disjunction of literals with only one is postive, not A OR not B or C\n* **Horn clause** - disjunction of literals where at most one is positive\n* **Goal clause** - clause with no positive literals\n* **K-cnf sentence** - CNF sent where at most k literals in each clause\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}