{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "7fa5f0df-260f-4a0b-e3a9-156ffbb02257"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "d43e4b77-294c-4975-85a9-d1eb4e21e25a"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ],
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 =\"\"\"\n",
        "Acting and behaving humanly and rationally: 4 possible combinations. Acting humanly: Six disciplines of AI: NLP, knowledge representation, automated reasoning, machine learning,\\\n",
        "computer vision, robotics. Rational agent approach (standard model) has prevailed in AI, requires a fully specified objective.\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 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"An agent's decision on action at a point in time depends on built-in knowledge and percept history but not anything not observed.\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"Performance measures should focus on desired results rather than agent behavior.\"\"\"\n",
        "chapter2_3 = \"\"\" Agents can be physical or virtual/software.\"\"\"\n",
        "chapter2_4 = \"\"\"Distinction between agent program and agent function: program maps single percept to action; function can consider entire percept history; program implements function\\\n",
        "Four types of agents: simple reflex agent, model-based reflex agent, goal-based agent and utility-based agent. Goal-based agent uses information about goal(s) along with model-information\\\n",
        "to decide next action. Search and Planning are used by agent to achieve objective to reaching goal. Learning agent has four conceptual components: Learning element, Performance element,\\\n",
        "Critic and Problem Generator. The Performance element selects external actions to be taken. Critic provides feedback on how the agent is doing to the Learning element which decides how\\\n",
        "the Performance element should be modified to perform better. The last component is the Problem Generator which suggests actionsleading to new experiences that can add more information\\\n",
        "In such a model, the external performance standard extracts a reward or penalty from the incoming percept which provides feedback on the agent's behavior. Environment representations \\\n",
        "lie on a continuum of complexity and expressive power: Atomic, Factored and Structured. Atomic implies indivisibility of each state of the world. Factored representation divides each state\\\n",
        " into variables or attributes each having a value.  Structured representation adds on relationships between variables. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"rationality\" : \"doing the correct thing\",\n",
        "\"natural language processing\" : \"to communicate effectively in a human language\",\n",
        "\"knowledge representation\" : \"entering in storage given and acquired knowledge\",\n",
        "\"automated reasoning\" : \"to respond to questions and draw new inferences\",\n",
        "\"value alignment process\" : \"process of agreeing our true preferences with objective given to machine\",\n",
        "\"agent\" : \"perceives its environment through sensors, acts independently through actuators, adjust to change in an environment, goal orientation\",\n",
        "\"rational agent\" : \"agent acts to maximize its performance measure and under uncertainity, best expected outcome; given built-in knowledge, to date percept sequence\",\n",
        "\"environment\" : \"that part of the universe that is relevant for the specific agent\",\n",
        "\"percept\" : \"input received from sensors\",\n",
        "\"percept sequence\" : \"entire history of percepts\",\n",
        "\"agent function\" : \"how agent behaves with regard to a specific percept sequence, an abstract mathematical description\",\n",
        "\"agent program\": \"internally concretely implements an agent's function, within a physical system \",\n",
        "\"agent architecture\": \"generally computing platform coupled with physical actuators and sensors\",\n",
        "\"agent\": \"architecture plus program\",\n",
        "\"consequentialism\": \"judging agent's behavior by how it modifies it's environment\",\n",
        "\"performance measure\": \"evaluates any specific ordering of environment states; there are explicit and implicit performance measures\",\n",
        "\"information gathering\": \"actions taken by agents to change future percepts\",\n",
        "\"learning\": \"extracting information from what agent perceives\",\n",
        "\"autonomy\": \"implies agent can learn from percepts and learning processes rather than relying entirely on prior knowledge\",\n",
        "\"task environment\": \"problems that agent is built to solve,OR combination of Performance measure, Environment, agent's Actuator and Sensors (PEAS)\",\n",
        "\"Fully vs Partially observable task environment\": \"where agent's sensors provide information on the complete (relevant) environment state at each point in time, is fully observable\",\n",
        "\"Single-agent vs Multi-agent task environment\": \"distinction between competitive (chess-player) vs. cooperative multi-agent (taxi-driver and other drivers)\",\n",
        "\"Deterministic vs Non-deterministic task environment\": \"determininistic if next environment state is determined solely by current state plus agent(s) action\",\n",
        "\"Stocastic vs Non-deterministic task environment\": \"first explicitly has quantified probabilities, second has unquantified uncertainty \",\n",
        "\"Episodic vs Sequential task environment\": \"first has atomic episodes not depending on previous episodes; second has current actions effecting future states\",\n",
        "\"Static vs Dynamic task environment\": \"if when the agent is thinking/deciding, environment can change, is dynamic; else static\",\n",
        "\"Discrete vs Continuous task environment\": \"Former has discrete environment state, time handling and percepts and actions by agent\",\n",
        "\"Known vs Unknown task environment\": \"In former, outcomes or outcome probabilities for all actions are known; solitare known but partially observable; new game observable unknown\",\n",
        "\"Simple reflex agent\": \"acts based on current percept, ignoring past percept sequence\",\n",
        "\"Condition-action rule\": \"Simple reflex agent uses this rule, otherwise stated as 'if....-then....'\",\n",
        "\"Model-based agent\": \"uses models such as transition model and sensor model\",\n",
        "\"Transition model\": \"Contains information on how world evolves and how agent's actions change world\",\n",
        "\"Sensor model\": \"Contains information on how the state of the world is captured in the agent's percepts\",\n",
        "\"Goal-based agent\": \"Agent uses information on goal along with model information to decide actions\",\n",
        "\"Utility-based agent\": \"The agent acts based on a utility (or expected utility) function which should reflect the agent's performance measure\",\n",
        "\"Learning agent\": \"Could be agent of any of the other types but with additional ability to learn\",\n",
        "\"Localist representation\": \"has a one-to-one mapping between concepts and memory locations.\",\n",
        "\"Distributed representation\": \"implies a concept can be represented across many memory locations and each memory location can represent multiple different concepts.\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\"\n",
        "\n",
        "}\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "gYYeNcdM_maE",
        "outputId": "46beafd4-08f5-44f4-dec4-1824ab9f81fc"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              "\n",
              "Acting and behaving humanly and rationally: 4 possible combinations. Acting humanly: Six disciplines of AI: NLP, knowledge representation, automated reasoning, machine learning,computer vision, robotics. Rational agent approach (standard model) has prevailed in AI, requires a fully specified objective.\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              "An agent's decision on action at a point in time depends on built-in knowledge and percept history but not anything not observed.\n",
              "\n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              "Performance measures should focus on desired results rather than agent behavior.\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Agents can be physical or virtual/software.\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              "Distinction between agent program and agent function: program maps single percept to action; function can consider entire percept history; program implements functionFour types of agents: simple reflex agent, model-based reflex agent, goal-based agent and utility-based agent. Goal-based agent uses information about goal(s) along with model-informationto decide next action. Search and Planning are used by agent to achieve objective to reaching goal. Learning agent has four conceptual components: Learning element, Performance element,Critic and Problem Generator. The Performance element selects external actions to be taken. Critic provides feedback on how the agent is doing to the Learning element which decides howthe Performance element should be modified to perform better. The last component is the Problem Generator which suggests actionsleading to new experiences that can add more informationIn such a model, the external performance standard extracts a reward or penalty from the incoming percept which provides feedback on the agent's behavior. Environment representations lie on a continuum of complexity and expressive power: Atomic, Factored and Structured. Atomic implies indivisibility of each state of the world. Factored representation divides each state into variables or attributes each having a value.  Structured representation adds on relationships between variables. \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Rationality** - doing the correct thing\n",
              "* **Natural language processing** - to communicate effectively in a human language\n",
              "* **Knowledge representation** - entering in storage given and acquired knowledge\n",
              "* **Automated reasoning** - to respond to questions and draw new inferences\n",
              "* **Value alignment process** - process of agreeing our true preferences with objective given to machine\n",
              "* **Agent** - architecture plus program\n",
              "* **Rational agent** - agent acts to maximize its performance measure and under uncertainity, best expected outcome; given built-in knowledge, to date percept sequence\n",
              "* **Environment** - that part of the universe that is relevant for the specific agent\n",
              "* **Percept** - input received from sensors\n",
              "* **Percept sequence** - entire history of percepts\n",
              "* **Agent function** - how agent behaves with regard to a specific percept sequence, an abstract mathematical description\n",
              "* **Agent program** - internally concretely implements an agent's function, within a physical system \n",
              "* **Agent architecture** - generally computing platform coupled with physical actuators and sensors\n",
              "* **Consequentialism** - judging agent's behavior by how it modifies it's environment\n",
              "* **Performance measure** - evaluates any specific ordering of environment states; there are explicit and implicit performance measures\n",
              "* **Information gathering** - actions taken by agents to change future percepts\n",
              "* **Learning** - extracting information from what agent perceives\n",
              "* **Autonomy** - implies agent can learn from percepts and learning processes rather than relying entirely on prior knowledge\n",
              "* **Task environment** - problems that agent is built to solve,OR combination of Performance measure, Environment, agent's Actuator and Sensors (PEAS)\n",
              "* **Fully vs partially observable task environment** - where agent's sensors provide information on the complete (relevant) environment state at each point in time, is fully observable\n",
              "* **Single-agent vs multi-agent task environment** - distinction between competitive (chess-player) vs. cooperative multi-agent (taxi-driver and other drivers)\n",
              "* **Deterministic vs non-deterministic task environment** - determininistic if next environment state is determined solely by current state plus agent(s) action\n",
              "* **Stocastic vs non-deterministic task environment** - first explicitly has quantified probabilities, second has unquantified uncertainty \n",
              "* **Episodic vs sequential task environment** - first has atomic episodes not depending on previous episodes; second has current actions effecting future states\n",
              "* **Static vs dynamic task environment** - if when the agent is thinking/deciding, environment can change, is dynamic; else static\n",
              "* **Discrete vs continuous task environment** - Former has discrete environment state, time handling and percepts and actions by agent\n",
              "* **Known vs unknown task environment** - In former, outcomes or outcome probabilities for all actions are known; solitare known but partially observable; new game observable unknown\n",
              "* **Simple reflex agent** - acts based on current percept, ignoring past percept sequence\n",
              "* **Condition-action rule** - Simple reflex agent uses this rule, otherwise stated as 'if....-then....'\n",
              "* **Model-based agent** - uses models such as transition model and sensor model\n",
              "* **Transition model** - Contains information on how world evolves and how agent's actions change world\n",
              "* **Sensor model** - Contains information on how the state of the world is captured in the agent's percepts\n",
              "* **Goal-based agent** - Agent uses information on goal along with model information to decide actions\n",
              "* **Utility-based agent** - The agent acts based on a utility (or expected utility) function which should reflect the agent's performance measure\n",
              "* **Learning agent** - Could be agent of any of the other types but with additional ability to learn\n",
              "* **Localist representation** - has a one-to-one mapping between concepts and memory locations.\n",
              "* **Distributed representation** - implies a concept can be represented across many memory locations and each memory location can represent multiple different concepts.\n",
              "* **Other concept** - your definitions here\n",
              "* **Etc.** - your definitions here\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 38,
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "outputs": [],
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"List operations: list.append(item); list.insert(index, item); list.sort(key(optional), reverse = False/True) -- sort in place; list.reverse() -- in place;\\\n",
        "sorted(list) -- copy sorted; list.index(item) -- index of first occurrence; list.count(item) --number of occurrences; list.remove(item) -- remove first occurrence; list(zip(a, b))\\\n",
        "[(1, 'a'), (2, 'b'), (3, 'c')] -- makes tuples with elements of both lists; list(zip(\"foo\", \"bar\")) ---results-- [('f', 'b'), ('o', 'a'), ('o', 'r')]\\\n",
        "String operations: \"filler(eg white space, comma, #, etc)\".join(list of strings); text.split(\" ,-\") to remove white spaces, comma, hyphen, etc;\\\n",
        "Array operations: number of rows = len(array); number of columns = len(array[0])\\\n",
        "\n",
        "Slice operations on sequences (could be strings, sets, lists, etc) a[start:end:step]:\\\n",
        "copy(seqs): return(:);\\\n",
        "text.lower(), text.split(' '), text.capitalize(),\\\n",
        "dictionary operations: key in dict.keys(); dict.items(); dict.values(); dict = {'a' : 'fruit', 'b' : 'vegetables'}; defaultdict automatically initializes nonexistent dictionary values\\\n",
        "from collections import defaultdict; d = defaultdict(str); from collections import Counter; d = Counter(); d['dog'] 0\\\n",
        "matrix_flat = matrix.flatten()\\\n",
        "print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\\\n",
        "== checks if points to objects of same value; is checks if two variables point to the same object\\\n",
        "y = x[:] creates a shallow copy, i.e. a new object with the same value\\\n",
        "def myfun(b, c=3, d=\"hello\"): -- default arguments in functions, Non-default argument should always precede default arguments\\\n",
        "Keyword Arguments: Functions can be called with arguments out of order. These arguments are specified in the call. Keyword arguments can be used after all other arguments.\\\n",
        "\n",
        "Suppose you want to accept a variable number of non-keyword arguments to your function.\\\n",
        "\n",
        "def print_everything(*args):\\\n",
        "\n",
        "     args is a tuple of arguments passed to the fn.  \\\n",
        "Suppose you want to accept a variable number of keyword arguments to your function.\\\n",
        "def print_keyword_args(**kwargs):\\\n",
        "   kwargs is a dict of the keyword args passed to the fn. \\\n",
        "You can combine positional, args and kwargs as def myfun(positional, *args, **kwargs):\\\n",
        "[int(i) for i in ['1', '2’]] \\\n",
        "\n",
        "list(map(int, ['1', '2'])) #equivalent to above \\\n",
        "\n",
        "def is_even(x):\\\n",
        "\n",
        " return x % 2 == 0\\\n",
        "\n",
        "[i for i in [1, 2, 3, 4, 5] if is_even(i)] \\\n",
        " \n",
        "list(filter(is_even, [1, 2, 3, 4, 5])) #equivalent \\\n",
        "\n",
        "list(filter(lambda x: x%2==0, [1, 2, 3, 4, 5])) #also equivalent \\\n",
        "\n",
        "Dictionary/set comprehension: lst1 = [('a', 1), ('b', 2), ('c', 'hi’)]; lst2 = ['x', 'a', 6];  d = { k: v for k,v in lst1 }; s = { x for x in lst2}\\\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "Review pg42 on\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 39,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 410
        },
        "id": "ydOK__lwWgdp",
        "outputId": "e46a873b-3bd2-4421-d5d4-30a9da0608a2"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "List operations: list.append(item); list.insert(index, item); list.sort(key(optional), reverse = False/True) -- sort in place; list.reverse() -- in place;sorted(list) -- copy sorted; list.index(item) -- index of first occurrence; list.count(item) --number of occurrences; list.remove(item) -- remove first occurrence; list(zip(a, b))[(1, 'a'), (2, 'b'), (3, 'c')] -- makes tuples with elements of both lists; list(zip(\"foo\", \"bar\")) ---results-- [('f', 'b'), ('o', 'a'), ('o', 'r')]String operations: \"filler(eg white space, comma, #, etc)\".join(list of strings); text.split(\" ,-\") to remove white spaces, comma, hyphen, etc;Array operations: number of rows = len(array); number of columns = len(array[0])Slice operations on sequences (could be strings, sets, lists, etc) a[start:end:step]:copy(seqs): return(:);text.lower(), text.split(' '), text.capitalize(),dictionary operations: key in dict.keys(); dict.items(); dict.values(); dict = {'a' : 'fruit', 'b' : 'vegetables'}; defaultdict automatically initializes nonexistent dictionary valuesfrom collections import defaultdict; d = defaultdict(str); from collections import Counter; d = Counter(); d['dog'] 0matrix_flat = matrix.flatten()print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))== checks if points to objects of same value; is checks if two variables point to the same objecty = x[:] creates a shallow copy, i.e. a new object with the same valuedef myfun(b, c=3, d=\"hello\"): -- default arguments in functions, Non-default argument should always precede default argumentsKeyword Arguments: Functions can be called with arguments out of order. These arguments are specified in the call. Keyword arguments can be used after all other arguments.\n",
              "Suppose you want to accept a variable number of non-keyword arguments to your function.\n",
              "def print_everything(*args):\n",
              "     args is a tuple of arguments passed to the fn.  Suppose you want to accept a variable number of keyword arguments to your function.def print_keyword_args(**kwargs):   kwargs is a dict of the keyword args passed to the fn. You can combine positional, args and kwargs as def myfun(positional, *args, **kwargs):\n",
              "Review pg42 on\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 46,
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Considering only the simplest environments in this chapter: episodic, single agent, fully observable, deterministic, static, discrete, and known. Informed(where\\\n",
        "agent can estimate how far the goal is) and Uninformed(no such information available).\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\"Search algorithms use data structure to keep track of search tree. Each node has state, parent, action(applied to parent to get node), path-cost (cost of path from\\\n",
        "initial state to node). Following parent nodes back from goal to initial state gives solution. Three types of queues are used in search algorithms. Graph search and tree-like search\\\n",
        "deal differently with redundant paths. Searches are evaluated on four criteria: Completeness, Cost Optimality, Time Complexity, and Space Complexity. Complexity can be measured by \\\n",
        "|V| + |E| or by depth, d, or number of actions in an optimal solution; m, the maximum number of actions in any path; and b, branching factor or number of successors of a node that\\\n",
        "to be considered. Tree search, unlike graph search, treats different paths to the same node as distinct. Hence it runs into the problem of failure to detect repeated states,\\\n",
        "which can turn a linear problem into an exponential one.\"\"\"\n",
        "chapter3_4 = \"\"\"Uninformed search strategies don't have information about distance from a state to the goal. Breadth-first search can be used if all actions have same cost. This is\\\n",
        "systematic, complete strategy and uses FIFO queue. Can do an early goal test, rather than late goal test. Has O(b^(d)) time and space complexity, where d is cost of least-cost solution.\\\n",
        "Exponential-complexity search problems can be solved by uninformed search only for small instances. Dijkstra's or uniform-cost algorithm spreads out in waves of uniform path-cost and\\\n",
        "does a late goal test. It returns the cheapest path. Depth-first search operates by expanding the deepest node first, has O(bm) space requirement where m is maximum depth of tree.\\\n",
        "It uses a tree-like search and does not maintain a table of reached nodes and is not complete. It returns\\\n",
        "the first solution found, not necessarily the cheapest. It may explore the same spaces many times over different paths but in acyclic spaces will eventually cover all spaces. A variant of DFS\\\n",
        "called back-tracking search generates only one successor at a time and has a path of O(m) where m is maximum depth. Used for tasks with large state descriptions. Iterative deepening \\\n",
        " search has O(bd) space requirement where d is the depth of the shortest solution. In best-first \\\n",
        "bidirectional search, node to be expanded is one with minimum evaluation function, across either frontier.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\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 using Atomic representations\",\n",
        "\"search\" : \"evaluating a series of actions that lead to a goal state\",\n",
        "\"solution\" : \"a series of actions that lead to a goal state\",\n",
        "\"goal formulation\" : \"determining what is the goal\",\n",
        "\"problem formulation\" : \"Agent decides on a description of states and actions necessary to arrive at goal; abstraction of relevant part of environment\",\n",
        "\"search\" : \"process of determining a sequence of actions (solution) to arrive at the goal; sometimes no solution may exist\",\n",
        "\"open-loop system\": \"where environment is fully observable, deterministic, known; agent can ignore percepts; known as open-loop system\",\n",
        "\"closed-loop system\" : \"agent monitors percepts\",\n",
        "\"problem\" : \"search problem has state space, initial state, goal states, available actions applicable in a state; transition model; action cost function\",\n",
        "\"state space\" : \"a set of possible states for environment\",\n",
        "\"initial state\" : \"where agent starts from\",\n",
        "\"goal states\" : \"one or more environment states to be achieved by agent\",\n",
        "\"action\" : \"action available to agent in a specific state s, this is applicable in state s\",\n",
        "\"transition model\" : \"describes the new state resulting from an action in state s\",\n",
        "\"action cost function\" : \"provides cost of action a in state s to reach state a, based on agent's performance measure\",\n",
        "\"path\" : \"a series of actions; cost of path = sum of costs of actions in path\",\n",
        "\"optimal solution\" : \"has minimum cost among all solutions\",\n",
        "\"graph\" : \"can represent states as vertices and actions as directed edges between them\",\n",
        "\"standardized problem\" : \"objective is to describe or exercise various problem-solving methods e.g. grid, sokoban, sliding-tile puzzle problems\",\n",
        "\"real-world problem\" : \"route-finding, touring, VLSI layout, robot navigation, automatic assembly sequencing, protein design\",\n",
        "\"search algorithm\" : \"input is search problem and output is solution or lack of solution\",\n",
        "\"node\" : \"in search tree is a state and edge is an action\",\n",
        "\"expand\" : \"node means to find child or successor nodes from the resulting states of actions applicable to the node\",\n",
        "\"frontier\" :\"set of unexpanded nodes, normally use a queue data structure\",\n",
        "\"reached\" : \"set of visited nodes, can be stored in a hash table with key as state and value as node for state\",\n",
        "\"best-first search\" : \"choose node to minimize evaluation function, f(n)\",\n",
        "\"priority-queue\" : \"pops node with minimum evaluation function value from frontier, used in best-first search\",\n",
        "\"FIFO queue\" : \"pops first node added to queue, used in breadth-first search (BFS)\",\n",
        "\"LIFO queue\" : \"also known as Stack, pops last node added to queue, used in depth-first search (DFS)\",\n",
        "\"graph search\" : \"checks for redundant paths (e.g. best-first search\",\n",
        "\"tree-like search\" : \"does not check for redundant paths because of nature of problem, e.g. assembly\",\n",
        "\"Completeness\" : \"Will the algorithm find a solution if there is any, or report lack of solution, if none? Needs be systematic.\",\n",
        "\"Cost optimality\" : \"Will the algorithm find lowest path cost solution?\",\n",
        "\"Time complexity\" : \"Time in seconds or abstractly by number of states and actions evaluated\",\n",
        "\"Space complexity\" : \"Amount of memory utilized by algorithm\",\n",
        "\"depth-limited search\": \"searches only upto depth limit l.\",\n",
        "\"iterative deepening search\" : \"uses depth-limiting search with increasing values of l, generally used  when search space larger than memory and depth not known.\",\n",
        "\"bidirectional search\" : \"simultaneously searches forward from initial state and backwards from goal\"\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 47,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "38e19414-1f29-4835-ecef-816cf799821f"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "## WARNING: Your definition of 'reached' is too long!\n",
              "WARNING: Your definition of 'iterative deepening search' is too long!\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " Considering only the simplest environments in this chapter: episodic, single agent, fully observable, deterministic, static, discrete, and known. Informed(whereagent can estimate how far the goal is) and Uninformed(no such information available).\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "Search algorithms use data structure to keep track of search tree. Each node has state, parent, action(applied to parent to get node), path-cost (cost of path frominitial state to node). Following parent nodes back from goal to initial state gives solution. Three types of queues are used in search algorithms. Graph search and tree-like searchdeal differently with redundant paths. Searches are evaluated on four criteria: Completeness, Cost Optimality, Time Complexity, and Space Complexity. Complexity can be measured by |V| + |E| or by depth, d, or number of actions in an optimal solution; m, the maximum number of actions in any path; and b, branching factor or number of successors of a node thatto be considered. Tree search, unlike graph search, treats different paths to the same node as distinct. Hence it runs into the problem of failure to detect repeated states,which can turn a linear problem into an exponential one.\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "Uninformed search strategies don't have information about distance from a state to the goal. Breadth-first search can be used if all actions have same cost. This issystematic, complete strategy and uses FIFO queue. Can do an early goal test, rather than late goal test. Has O(b^(d)) time and space complexity, where d is cost of least-cost solution.Exponential-complexity search problems can be solved by uninformed search only for small instances. Dijkstra's or uniform-cost algorithm spreads out in waves of uniform path-cost anddoes a late goal test. It returns the cheapest path. Depth-first search operates by expanding the deepest node first, has O(bm) space requirement where m is maximum depth of tree.It uses a tree-like search and does not maintain a table of reached nodes and is not complete. It returnsthe first solution found, not necessarily the cheapest. It may explore the same spaces many times over different paths but in acyclic spaces will eventually cover all spaces. A variant of DFScalled back-tracking search generates only one successor at a time and has a path of O(m) where m is maximum depth. Used for tasks with large state descriptions. Iterative deepening  search has O(bd) space requirement where d is the depth of the shortest solution. In best-first bidirectional search, node to be expanded is one with minimum evaluation function, across either frontier.\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search using Atomic representations\n",
              "* **Search** - process of determining a sequence of actions (solution) to arrive at the goal; sometimes no solution may exist\n",
              "* **Solution** - a series of actions that lead to a goal state\n",
              "* **Goal formulation** - determining what is the goal\n",
              "* **Problem formulation** - Agent decides on a description of states and actions necessary to arrive at goal; abstraction of relevant part of environment\n",
              "* **Open-loop system** - where environment is fully observable, deterministic, known; agent can ignore percepts; known as open-loop system\n",
              "* **Closed-loop system** - agent monitors percepts\n",
              "* **Problem** - search problem has state space, initial state, goal states, available actions applicable in a state; transition model; action cost function\n",
              "* **State space** - a set of possible states for environment\n",
              "* **Initial state** - where agent starts from\n",
              "* **Goal states** - one or more environment states to be achieved by agent\n",
              "* **Action** - action available to agent in a specific state s, this is applicable in state s\n",
              "* **Transition model** - describes the new state resulting from an action in state s\n",
              "* **Action cost function** - provides cost of action a in state s to reach state a, based on agent's performance measure\n",
              "* **Path** - a series of actions; cost of path = sum of costs of actions in path\n",
              "* **Optimal solution** - has minimum cost among all solutions\n",
              "* **Graph** - can represent states as vertices and actions as directed edges between them\n",
              "* **Standardized problem** - objective is to describe or exercise various problem-solving methods e.g. grid, sokoban, sliding-tile puzzle problems\n",
              "* **Real-world problem** - route-finding, touring, VLSI layout, robot navigation, automatic assembly sequencing, protein design\n",
              "* **Search algorithm** - input is search problem and output is solution or lack of solution\n",
              "* **Node** - in search tree is a state and edge is an action\n",
              "* **Expand** - node means to find child or successor nodes from the resulting states of actions applicable to the node\n",
              "* **Frontier** - set of unexpanded nodes, normally use a queue data structure\n",
              "* **Reached** - set of visited nodes, can be stored in a hash table with key as state and value as node for state\n",
              "* **Best-first search** - choose node to minimize evaluation function, f(n)\n",
              "* **Priority-queue** - pops node with minimum evaluation function value from frontier, used in best-first search\n",
              "* **Fifo queue** - pops first node added to queue, used in breadth-first search (BFS)\n",
              "* **Lifo queue** - also known as Stack, pops last node added to queue, used in depth-first search (DFS)\n",
              "* **Graph search** - checks for redundant paths (e.g. best-first search\n",
              "* **Tree-like search** - does not check for redundant paths because of nature of problem, e.g. assembly\n",
              "* **Completeness** - Will the algorithm find a solution if there is any, or report lack of solution, if none? Needs be systematic.\n",
              "* **Cost optimality** - Will the algorithm find lowest path cost solution?\n",
              "* **Time complexity** - Time in seconds or abstractly by number of states and actions evaluated\n",
              "* **Space complexity** - Amount of memory utilized by algorithm\n",
              "* **Depth-limited search** - searches only upto depth limit l.\n",
              "* **Iterative deepening search** - uses depth-limiting search with increasing values of l, generally used  when search space larger than memory and depth not known.\n",
              "* **Bidirectional search** - simultaneously searches forward from initial state and backwards from goal\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 40,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"Greedy best-first search may not find the cheapest path, is complete in finite state spaces but not in infinite state spaces. Maximum possible time and space\\\n",
        "complexity is O(|V|), but a good heuristic function can enable O(bm). A* search is complete and cost-optimal, with an admissible heuristic. A consistent heuristic must be \\\n",
        "admissible though reverse not true. With inadmissible heuristic, A*'s cost-optimality is uncertain, A* is O(b^(d)). If there is at least one cost-optimal path where h(n) is admissible \\\n",
        "for all path nodes, then that path will be found. Also, if optimal solution has cost C* and second-best has cost C and if h(n) overestimates some costs but by not\\\n",
        "more than C - C*, then A* will find cost-optimal solutions. A* has contours that each have the same f(n) values, with increasing value in outer contours, stretching\\\n",
        "towards the goal. A* can solve soduku problems in O(n^n+1). Uniform-cost search has circular contours with no elongation towards the goal. Memory optimization during search could be by i) not maintaining a reached set,\\\n",
        "ii) remove states from reached depending on the algorithm or by maintaining reference counts, iii) using beam, IDA*, RBFS, MA*, SMA*. Bidirectional heuristic search has a lower bound\\\n",
        "as lb(m,n) = max(gf(m) + gb(n), ff(m), fb(n)) and a f function, f2(n) = max(2g(n), g(n)+h(n)). No node with g(n) > C*/2 will be expanded.\"\"\"\n",
        "chapter3_6 = \"\"\"Heuristics for the 8-tile puzzle include i) the number of misplaced tiles, and ii) city-block or Manhattan distance or sum of horizontal and vertical distances of node\\\n",
        "from goal. A measure of quality of a heuristic is the effective branching factor b*. One method of identifying heuristics is by relaxing some of the restrictions on the original problem|\n",
        "This creates a supergraph of the original state space with additional edges arising from such relaxations. if there are multiple admissible heuristics, then h(n)=max{h1(n),....,hk(n)}|\\\n",
        "Admissible heuristics can also be developed from subproblems of the problem. Algorithms use metalevel state space consisting of nodes holding internal computational state of a search\\\n",
        " program in an ordinary state space. Metalevel learning programs can improve their search  based on their experience.  Machine learning and reinforcement learning techniques can also\\\n",
        " be used improve search algorithms from their experience in earlier searches. Different heuristcs can be combined by these techniques to get an improved heuristic.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search\" : \"uses information on position of goals to discover solutions more efficiently\",\n",
        "\"heuristic function\" : \"h(n), approximated cost of least expensive path to state node n to goal state\",\n",
        "\"greedy best-first search\" : \"type of best-first search selecting node for expansion based on lowest h(n) value; f(n) = h(n)\",\n",
        "\"A* search\" : \"best-first search using evaluation function f(n) = g(n) + h(n), where g(n) = cost from initial state to node\",\n",
        "\"admissible heuristic\" : \"one that never exceeds actual cost from node to goal\",\n",
        "\"consistency\" : \"heuristic is consistent if h(n) <= c(n,a,n') + h(n'), where n' is successor node to n, type of triangle inequality\",\n",
        "\"contours\" : \"shapes that are equidistant from the initial node based on the relevant evaluation function\",\n",
        "\"monotonic\" : \"path costs always increase along a path since action costs are never negative\",\n",
        "\"surely expanded nodes\" : \"are nodes expanded by A* reachable from the initial state on path on which every node has f(n) < C*\",\n",
        "\"optimally efficient\" : \"what A* with a consistent heuristic is because any algorithm using same heuristic would expand same surely expanded nodes\",\n",
        "\"satisficing\" : \"solutions are those good enough but may be suboptimal due to using inadmissible heuristic (which may overestimate cost)\",\n",
        "\"detour index\" : \"multiplier applied to straight-line distance to adjust for curvature of roads\",\n",
        "\"weighted A* search\" : \"uses heuristic with greater weight assigned to it; f(n) = g(n) + W x h(n), with W > 1\",\n",
        "\"bounded suboptimal search\" : \"provides a solution with cost within W times the optimal cost\",\n",
        "\"bounded cost search\" : \"provides a solution with cost less than a constant C\",\n",
        "\"unbounded cost search\" : \"provides a solution without cap on the cost, but does so quickly, e.g. speedy search\",\n",
        "\"speedy search\" : \"type of greedy best-first search using as heuristic estimated number of actions to reach goal, disregarding cost\",\n",
        "\"reference count\" : \"how many times a state has been visited\",\n",
        "\"beam search\" : \"limits size of frontier by only retaining k nodes with highest f-scores or with f-scores not much below best f-score\",\n",
        "\"iterative deepening A* search (IDA*)\" : \"uses cutoff as smallest f-value higher than cutoff in prior iteration to progressively expand search\",\n",
        "\"recursive best-first search (RBFS)\" : \"uses linear space, stores best f-score (backed-up value) of subtree and can recurse back based on this value in future\",\n",
        "\"SMA*\" : \"simplified memory-bounded A* drops node with worst f-score (backing its value to parent) when memory is full before adding node\",\n",
        "\"effective branching factor\" : \"solution to N+1 = 1+b*+(b*)^2+(b*)^3+....+(b*)^d, where N is total nodes generated by A*, d = depth\",\n",
        "\"effective depth\" : \"depth resulting from reduction from original depth by a constant factor kh due to A* pruning\",\n",
        "\"relaxed problem\" : \"developed from original problem by  relaxing some of the restrictions\",\n",
        "\"pattern database\" : \"holds the costs for every subproblem for reuse over time\",\n",
        "\"disjoint pattern databases\" : \"databases holding non-overlapping subproblems\",\n",
        "\"differential heuristic\" : \"hDH(n) = max(over all landmarks) of |C*(n,L) - C*(goal, L)|\",\n",
        "\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 41,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "f1ff8d9f-6580-4b00-f4f5-2a02ebccf496"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "Greedy best-first search may not find the cheapest path, is complete in finite state spaces but not in infinite state spaces. Maximum possible time and spacecomplexity is O(|V|), but a good heuristic function can enable O(bm). A* search is complete and cost-optimal, with an admissible heuristic. A consistent heuristic must be admissible though reverse not true. With inadmissible heuristic, A*'s cost-optimality is uncertain, A* is O(b^(d)). If there is at least one cost-optimal path where h(n) is admissible for all path nodes, then that path will be found. Also, if optimal solution has cost C* and second-best has cost C and if h(n) overestimates some costs but by notmore than C - C*, then A* will find cost-optimal solutions. A* has contours that each have the same f(n) values, with increasing value in outer contours, stretchingtowards the goal. A* can solve soduku problems in O(n^n+1). Uniform-cost search has circular contours with no elongation towards the goal. Memory optimization during search could be by i) not maintaining a reached set,ii) remove states from reached depending on the algorithm or by maintaining reference counts, iii) using beam, IDA*, RBFS, MA*, SMA*. Bidirectional heuristic search has a lower boundas lb(m,n) = max(gf(m) + gb(n), ff(m), fb(n)) and a f function, f2(n) = max(2g(n), g(n)+h(n)). No node with g(n) > C*/2 will be expanded.\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "Heuristics for the 8-tile puzzle include i) the number of misplaced tiles, and ii) city-block or Manhattan distance or sum of horizontal and vertical distances of nodefrom goal. A measure of quality of a heuristic is the effective branching factor b*. One method of identifying heuristics is by relaxing some of the restrictions on the original problem|\n",
              "This creates a supergraph of the original state space with additional edges arising from such relaxations. if there are multiple admissible heuristics, then h(n)=max{h1(n),....,hk(n)}|Admissible heuristics can also be developed from subproblems of the problem. Algorithms use metalevel state space consisting of nodes holding internal computational state of a search program in an ordinary state space. Metalevel learning programs can improve their search  based on their experience.  Machine learning and reinforcement learning techniques can also be used improve search algorithms from their experience in earlier searches. Different heuristcs can be combined by these techniques to get an improved heuristic.\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Informed search** - uses information on position of goals to discover solutions more efficiently\n",
              "* **Heuristic function** - h(n), approximated cost of least expensive path to state node n to goal state\n",
              "* **Greedy best-first search** - type of best-first search selecting node for expansion based on lowest h(n) value; f(n) = h(n)\n",
              "* **A* search** - best-first search using evaluation function f(n) = g(n) + h(n), where g(n) = cost from initial state to node\n",
              "* **Admissible heuristic** - one that never exceeds actual cost from node to goal\n",
              "* **Consistency** - heuristic is consistent if h(n) <= c(n,a,n') + h(n'), where n' is successor node to n, type of triangle inequality\n",
              "* **Contours** - shapes that are equidistant from the initial node based on the relevant evaluation function\n",
              "* **Monotonic** - path costs always increase along a path since action costs are never negative\n",
              "* **Surely expanded nodes** - are nodes expanded by A* reachable from the initial state on path on which every node has f(n) < C*\n",
              "* **Optimally efficient** - what A* with a consistent heuristic is because any algorithm using same heuristic would expand same surely expanded nodes\n",
              "* **Satisficing** - solutions are those good enough but may be suboptimal due to using inadmissible heuristic (which may overestimate cost)\n",
              "* **Detour index** - multiplier applied to straight-line distance to adjust for curvature of roads\n",
              "* **Weighted a* search** - uses heuristic with greater weight assigned to it; f(n) = g(n) + W x h(n), with W > 1\n",
              "* **Bounded suboptimal search** - provides a solution with cost within W times the optimal cost\n",
              "* **Bounded cost search** - provides a solution with cost less than a constant C\n",
              "* **Unbounded cost search** - provides a solution without cap on the cost, but does so quickly, e.g. speedy search\n",
              "* **Speedy search** - type of greedy best-first search using as heuristic estimated number of actions to reach goal, disregarding cost\n",
              "* **Reference count** - how many times a state has been visited\n",
              "* **Beam search** - limits size of frontier by only retaining k nodes with highest f-scores or with f-scores not much below best f-score\n",
              "* **Iterative deepening a* search (ida*)** - uses cutoff as smallest f-value higher than cutoff in prior iteration to progressively expand search\n",
              "* **Recursive best-first search (rbfs)** - uses linear space, stores best f-score (backed-up value) of subtree and can recurse back based on this value in future\n",
              "* **Sma*** - simplified memory-bounded A* drops node with worst f-score (backing its value to parent) when memory is full before adding node\n",
              "* **Effective branching factor** - solution to N+1 = 1+b*+(b*)^2+(b*)^3+....+(b*)^d, where N is total nodes generated by A*, d = depth\n",
              "* **Effective depth** - depth resulting from reduction from original depth by a constant factor kh due to A* pruning\n",
              "* **Relaxed problem** - developed from original problem by  relaxing some of the restrictions\n",
              "* **Pattern database** - holds the costs for every subproblem for reuse over time\n",
              "* **Disjoint pattern databases** - databases holding non-overlapping subproblems\n",
              "* **Differential heuristic** - hDH(n) = max(over all landmarks) of |C*(n,L) - C*(goal, L)|\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"Adversarial search problems exist in competitive environments where multiple agents have conflicting goals. Three approaches can be taken in regard to such\\\n",
        "environments: i) treat them as an economy, ii) treat the agents as adding randomness, but this ignores the adversarial aspect, and iii) explicitly model the behavior. Winner\\\n",
        "at each stage can be determined either by a heuristic evaluation function or averaging results from several fast simulations going from current state to goal. Games\\\n",
        " considered are deterministic, two-player, turn-taking, perfect information, zero-sum games.\"\"\"\n",
        "chapter5_2 = \"\"\"Minimax search is a recursive algorithm does a depth-first search to the leaves of a tree and then return minimax values up to the root. If m is tree's\\\n",
        "maximum depth and b is branching factor, then time complexity is O(b^(m)) and space complexity is O(bm) if all actions generated at the same time or O(m) if generated\\\n",
        "one at a time.  In multiplayer game, the value at each node is a vector of values, with terminal nodes having vector of utility values for each player. For intermediate\\\n",
        "node n, the backedup vector is that of successor state with highest value for player choosing at n. Alpha-beta pruning works by evaluating if for every node n that a player\\\n",
        "can move to, there is a better choice either at the same level or at any point higher in the tree. If so, player never chooses n. Hence, it can be pruned. Alpha-beta pruning\\\n",
        "works depending on order in which states are examined. Alpha-beta has time complexity of O(b^(m)), but can be improved to O(b^(m/2)), so that that effective branching factor\\\n",
        "becomes sqrt(b) with perfect move ordering or but could get to 2*O(b^(m/2)) with some heuristics on move ordering.  Improvements could be by iterative deepening, killer move\\\n",
        "heuristic, transposition table to store states.\"\"\"\n",
        "chapter5_3 = \"\"\"Can cut off search for alpha-beta pruning by setting a depth limit and an evaluation function, which should only be applied to quiescent positions, where no\\\n",
        "major changes will occur shortly. The quiescence search will consider only certain types of moves.  A better approach is to use iterative deepening. There is also a horizon\\\n",
        " effect, due to moves beyond the horizon, which could be mitigated by singular extensions to the depth limit for clearly better moves. Forward pruning is a Type B Strategy \\\n",
        "where future moves that don't look good are pruned. Beam search is not a good forwarding pruning method. ProbCut or probabilitic cut algorithm uses shallow search combined\\\n",
        "with past experience to that estimate a value v at depth d would be outside of alpha and beta.  Combining a number of these techniques gets the best result. Another option\\\n",
        "to improve alpha-beta search is to create large lookup tables for the moves from the intial state and around the goal state.   \"\"\"\n",
        "chapter5_5 = \"\"\"Stochastic games include a probability element.  Hence there are chance nodes in addition to MAX and MIN nodes.  It is only possible to calculate the expected\\\n",
        "value of a node, which is the average over all outcomes of the chance nodes. There is also an expectiminimax value as average of chance node outcomes.  While pruning nodes,\\\n",
        "not only their values but their probabilities need to be considered. Complexity of expectiminimax is O(b^(m) x n^(m)). Alternative to using an evaluation function is using\\\n",
        "a Monte Carlo tree search instead. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"Uncertainty about possible current states, P(s), and about action outcomes with transition probability P(s'|s,a). The two are related as under:\\\n",
        "$$P(RESULT(a)=s') = sigma(over s)P(s)P(s'|s, a)$$\\\n",
        "The environment is assumed to be episodic and agent's preferences are reflected by a utility function, which gives each state a number. The expected utility of an action is the\\\n",
        "probability-weighted average utility of its outcomes. Maximum expected utility (MEU) means that a rational agent should select actions to maximize expected utility.\"\"\"\n",
        "chapter16_2 = \"\"\"Constraints on rational preferences are: Orderability, Transitivity, Continuity, Substitutability, Monotonicity and Decomposability. In a deterministic environment,\\\n",
        "needs only an ordinal (ranking) function or value function. \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"pruning\" : \"ignores parts of search tree that have no effect on optimal move significantly improving the search\",\n",
        "\"evaluation function\" : \"heuristic calculation to decide the winner based on specifics of the state\",\n",
        "\"perfect information\" : \"= fully observable\",\n",
        "\"zero-sum games\" : \"games where outcomes for the two players are equal in absolute terms but with opposite signs\",\n",
        "\"move\" : \"= action\",\n",
        "\"position\" : \"= state\",\n",
        "\"initial state\" : \"describes how the game looks like at the beginning\",\n",
        "\"transition model\" : \"specifies the state coming as a result of action a on state s\",\n",
        "'terminal test' : \"boolean which is true if game has ended and false if not\",\n",
        "\"terminal states\" : \"states where game is over\",\n",
        "\"utility function\" : \"provides value to a player when game ends, also known as objective or payoff function\",\n",
        "\"state space graph\" : \"defined by initial state, ACTIONS/RESULTS functions; where vertices = states, edges = moves, state can be reached by multiple paths\",\n",
        "\"game tree\" : \"theoretical search tree tracing every path to a terminal state\",\n",
        "\"ply\" : \"denotes one move by one player increasing depth by one\",\n",
        "\"Minimax value\" : \"utility for MAX in a state, assuming both players play optimally to the end\",\n",
        "\"minimax search\" : \"MAX moves to state with max value, MIN moves to state with min value\",\n",
        "\"alpha-beta pruning\" : \"is so named due to alpha/beta, values of the best (highest-value for MAX and lowest-value for MIN, respectively, on path)\",\n",
        "\"Type A strategy\" : \"for Alpha-Beta, considers a wide but shallow  part of tree and uses heuristic evaluation of nodes at that level\",\n",
        "\"Type B strategy\" : \"more popular, considers deep but narrow part of tree, avoids moves that appear expensive, follows optimal-looking paths to extent possible\",\n",
        "\"Evaluation function\" : \"calculates values for intermediate nodes using estimated material values for features, combining them in linear or non-linear fashion\",\n",
        "\"features\" : \"characteristics of a state\",\n",
        "\"unbiased\" : \"estimates for which the expected value of the difference between estimate and actual value is zero\",\n",
        "\"optimizer's curse\" : \"likelihood of the estimated expected utility of best choice to be too optimistic\",\n",
        "\"certainty effect\"  : \"strong preference of people towards certain positive outcomes as against uncertain outcomes\",\n",
        "\"ambiguity aversion\" :\"people giving lower preference to outcomes that are ambiguous\",\n",
        "\"framing effect\" : \"the way a situation or question is worded can have huge effect on people's decisions\",\n",
        "\"anchoring effect\" : \"people use as benchmark a number or fact that is given to them, and evaluate other outcomes with reference to this\",\n",
        "\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 13,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "305781ea-39ec-4647-8e1f-8f7d0ed7e8be"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "## WARNING: Your definition of 'anchoring effect' is too long!\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "Adversarial search problems exist in competitive environments where multiple agents have conflicting goals. Three approaches can be taken in regard to suchenvironments: i) treat them as an economy, ii) treat the agents as adding randomness, but this ignores the adversarial aspect, and iii) explicitly model the behavior. Winnerat each stage can be determined either by a heuristic evaluation function or averaging results from several fast simulations going from current state to goal. Games considered are deterministic, two-player, turn-taking, perfect information, zero-sum games.\n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "Minimax search is a recursive algorithm does a depth-first search to the leaves of a tree and then return minimax values up to the root. If m is tree'smaximum depth and b is branching factor, then time complexity is O(b^(m)) and space complexity is O(bm) if all actions generated at the same time or O(m) if generatedone at a time.  In multiplayer game, the value at each node is a vector of values, with terminal nodes having vector of utility values for each player. For intermediatenode n, the backedup vector is that of successor state with highest value for player choosing at n. Alpha-beta pruning works by evaluating if for every node n that a playercan move to, there is a better choice either at the same level or at any point higher in the tree. If so, player never chooses n. Hence, it can be pruned. Alpha-beta pruningworks depending on order in which states are examined. Alpha-beta has time complexity of O(b^(m)), but can be improved to O(b^(m/2)), so that that effective branching factorbecomes sqrt(b) with perfect move ordering or but could get to 2*O(b^(m/2)) with some heuristics on move ordering.  Improvements could be by iterative deepening, killer moveheuristic, transposition table to store states.\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "Can cut off search for alpha-beta pruning by setting a depth limit and an evaluation function, which should only be applied to quiescent positions, where nomajor changes will occur shortly. The quiescence search will consider only certain types of moves.  A better approach is to use iterative deepening. There is also a horizon effect, due to moves beyond the horizon, which could be mitigated by singular extensions to the depth limit for clearly better moves. Forward pruning is a Type B Strategy where future moves that don't look good are pruned. Beam search is not a good forwarding pruning method. ProbCut or probabilitic cut algorithm uses shallow search combinedwith past experience to that estimate a value v at depth d would be outside of alpha and beta.  Combining a number of these techniques gets the best result. Another optionto improve alpha-beta search is to create large lookup tables for the moves from the intial state and around the goal state.   \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "Stochastic games include a probability element.  Hence there are chance nodes in addition to MAX and MIN nodes.  It is only possible to calculate the expectedvalue of a node, which is the average over all outcomes of the chance nodes. There is also an expectiminimax value as average of chance node outcomes.  While pruning nodes,not only their values but their probabilities need to be considered. Complexity of expectiminimax is O(b^(m) x n^(m)). Alternative to using an evaluation function is usinga Monte Carlo tree search instead. \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "Uncertainty about possible current states, P(s), and about action outcomes with transition probability P(s'|s,a). The two are related as under:$$P(RESULT(a)=s') = sigma(over s)P(s)P(s'|s, a)$$The environment is assumed to be episodic and agent's preferences are reflected by a utility function, which gives each state a number. The expected utility of an action is theprobability-weighted average utility of its outcomes. Maximum expected utility (MEU) means that a rational agent should select actions to maximize expected utility.\n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "Constraints on rational preferences are: Orderability, Transitivity, Continuity, Substitutability, Monotonicity and Decomposability. In a deterministic environment,needs only an ordinal (ranking) function or value function. \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Pruning** - ignores parts of search tree that have no effect on optimal move significantly improving the search\n",
              "* **Evaluation function** - heuristic calculation to decide the winner based on specifics of the state\n",
              "* **Perfect information** - = fully observable\n",
              "* **Zero-sum games** - games where outcomes for the two players are equal in absolute terms but with opposite signs\n",
              "* **Move** - = action\n",
              "* **Position** - = state\n",
              "* **Initial state** - describes how the game looks like at the beginning\n",
              "* **Transition model** - specifies the state coming as a result of action a on state s\n",
              "* **Terminal test** - boolean which is true if game has ended and false if not\n",
              "* **Terminal states** - states where game is over\n",
              "* **Utility function** - provides value to a player when game ends, also known as objective or payoff function\n",
              "* **State space graph** - defined by initial state, ACTIONS/RESULTS functions; where vertices = states, edges = moves, state can be reached by multiple paths\n",
              "* **Game tree** - theoretical search tree tracing every path to a terminal state\n",
              "* **Ply** - denotes one move by one player increasing depth by one\n",
              "* **Minimax value** - utility for MAX in a state, assuming both players play optimally to the end\n",
              "* **Minimax search** - MAX moves to state with max value, MIN moves to state with min value\n",
              "* **Alpha-beta pruning** - is so named due to alpha/beta, values of the best (highest-value for MAX and lowest-value for MIN, respectively, on path)\n",
              "* **Type a strategy** - for Alpha-Beta, considers a wide but shallow  part of tree and uses heuristic evaluation of nodes at that level\n",
              "* **Type b strategy** - more popular, considers deep but narrow part of tree, avoids moves that appear expensive, follows optimal-looking paths to extent possible\n",
              "* **Evaluation function** - calculates values for intermediate nodes using estimated material values for features, combining them in linear or non-linear fashion\n",
              "* **Features** - characteristics of a state\n",
              "* **Unbiased** - estimates for which the expected value of the difference between estimate and actual value is zero\n",
              "* **Optimizer's curse** - likelihood of the estimated expected utility of best choice to be too optimistic\n",
              "* **Certainty effect** - strong preference of people towards certain positive outcomes as against uncertain outcomes\n",
              "* **Ambiguity aversion** - people giving lower preference to outcomes that are ambiguous\n",
              "* **Framing effect** - the way a situation or question is worded can have huge effect on people's decisions\n",
              "* **Anchoring effect** - people use as benchmark a number or fact that is given to them, and evaluate other outcomes with reference to this\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"Start using Factored Representation for each state comprising a set of variables, each having a value.  CSP search algorithms use structure of states and apply\\\n",
        "general rather than domain-specific heuristics to solve complicated problems.  It seeks to eliminate much of the search space by finding variable/value combinations that do not\\\n",
        "satisfy the constraints. A CSP has three components: X, a set of variable; D, a set of domains, one for each variable; and C, a set of constraints defining permissible value\\\n",
        "combinations. A constraint Ci consists of a pair (scope, rel), where 'scope' consists of tuple of variables affected by the constraint and 'rel' defines valid values for the\\\n",
        "variables.  The relation can be defined either explicitly as a set of all value tuples that satisfy the constraint or a function that can calculate whether a tuple is valid\\\n",
        "based on the relation.  A CSP is NP-complete in general. CSP can be used for map-coloring and job-shop scheduling.\"\"\"\n",
        "chapter6_2 = \"\"\"Constraint propagation can be combined with search or used as preprocessing and may even result in a solution. AC-3 maintains a queue of arcs to be examined\\\n",
        ", initially all arcs. As each arc comes off of the queue, it is examined for arc-consistency and if the domain of the first node in the arc is changed, then arcs with all\\\n",
        "neighbors of the node are added to the queue.  If any domain comes down to nothing, then there is no consistent CSP solution. If not, the CSP  will be equivalent to the original\\\n",
        "CSP but will be faster. Complexity of AC-3 is O(cd^3) where d is maximum domain size, c is number of binary constraints (arcs).\"\"\"\n",
        "chapter6_3 = \"\"\"Backtracking search for CSPs uses domain-independent heuristics to select which variable and values in the variable domain should be tried, what inferences\\\n",
        "can be made at each step, how far back to backtrack, and is it possible to save and reuse partial solutions.\"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"constraint satisfaction problem\" : \"CSP's solution has a value assigned to each variable, satisfying all constraints on the variable\",\n",
        "\"consistent\" : \"assignment of values to a variables not violating any constraints are considered consistent or legal\",\n",
        "\"complete\" : \"if every variable is assigned a value, the assignment is complete\",\n",
        "\"solution\" : \"a consistent, complete assignment of values to the variables in a problem is a solution\",\n",
        "\"partial assignment\" : \"if some variables do not have values assigned to them, the assignment is partial\",\n",
        "\"partial solution\" : \"a partial assignment that is consistent is a partial solution\",\n",
        "\"constraint graph\" : \"representation of a CSP, where nodes are variables of problem, and edges connect two variables having a constraint between them\",\n",
        "\"precedence constraint\" : \"defines ordering of tasks and when one task can begin with respect to earlier tasks\",\n",
        "\"disjunctive constraint\" : \"implies two tasks cannot overlap in time\",\n",
        "\"unary constraint\" : \"applies to value of one variable\",\n",
        "\"binary constraint\" : \"applies to values of two variables\",\n",
        "\"binary CSP\" : \"is one with only unary and binary constraints; can be represented by a constraint graph\",\n",
        "\"global constraint\" : \"restricts arbitrary (not necessarily all) number of variables, e.g. Alldiff, where all variables have to have different values\",\n",
        "\"constraint hypergraph\" : \"has ordinary nodes (circles) for variables and hypernodes (squares) for n-ary constraints effecting n variables\",\n",
        "'preference constraints' : \"show which solutions are preferred and can be encoded as costs ( vs. absolute constraints which if violated eliminate solutions)\",\n",
        "\"constrained optimization problem\" : \"or COP are CSPs with preference constraints, solvable with optimization search algorithms, e.g. linear programs\",\n",
        "\"constraint propagation\" : \"where constraints are used to reduce number of legal values for a variable, and same for another variable and contiues\",\n",
        "\"local consistency\" : \"each node as variable and each edge as binary constraint can be examined eliminating inconsistent values everywhere in the graph\",\n",
        "\"node-consistency\" : \"ensures all values in variable domain meet variables unary constraints\",\n",
        "\"arc-consistency\" : \"ensures every value in a variable's domain meets variable's binary constraints\",\n",
        "\"path-consistency\" : \"(Xi,Xj) is path-consistent with variable Xm, if every consistent assignments to Xi,Xj has a consistent assignment to (Xi,Xm) and (Xm,Xj)\",\n",
        "\"k-consistency\" : \"CSP is k-consistent if for a consistent assignment to any k-1 variables, the kth variable can have a consistent assignment\",\n",
        "\"strongly k-consistent\" : \"if k-consistent, k-1 consistent....1-consistent\",\n",
        "\"resource constraint\" : \"expressed as Atmost(10, P1, P2,...), resources need to sum to 10\",\n",
        "\"bounds propagation\" : \"domains represented by upper and lower bounds\",\n",
        "\"bounds-consistent\" : \"if, for both upper/lower bound values of each variable X, some Y value satisfies constraint between X and Y\",\n",
        "\"commutativity\" : \"In such problems, the order of actions is irrelevant; CSPs are commutative\",\n",
        "\"minimum-remaining-values (MRV) heuristic\" : \"selects the variable with the least 'legal' values\",\n",
        "\"degree heuristic\" : \"it selects variable that forms arcs (has constraints) with largest number of other unassigned variables, reducing branching factor\",\n",
        "\"least-constraining-value heuristic\" : \"After variable is picked, this heuristic chooses value eliminating least number of choices for neighboring variables\",\n",
        "\"forward-checking\" : \"process that establishes arc-consistency for every variable which is assigned by deleting any inconsistent value from all neighbors' domains\",\n",
        "\"Maintaining Arc Consistency (MAC)\" : \"combines forward checking starting with neighbors of assigned variable with AC-3, to reconfirm consistency across CSP\",\n",
        "\"conflict set\" : \"set of assignments to other variables that conflict with some value in variable; could also consider variable-set, not single variable\",\n",
        "\"backjumping\" : \"method for backtracking to the most recent assignment in the conflict set\",\n",
        "\"conflicted-directed backjumping\" : \"uses conflict sets conflicting with a set of variables to decide backjumping\",\n",
        "\"constraint learning\" : \"searches for minimum set of variables (called 'no-good', consists of variables and their values)from conflict set creating problems\",\n",
        "\"mini-conflicts heuristic\" : \"selects value that has least number of conflicts with other variables\",\n",
        "'constraint weighting' : \"concentrates search on important constraints\",\n",
        "'independent subproblems' : \"can be solved separately; these can be found by identifying connected components\",\n",
        "'directional arc consistency' : 'when in any ordering of variables, every Xi is arc-consistent with every Xj, where j>i',\n",
        "'cycle cutset' : \"a subset of CSP's variables, S, removal of which makes constraint graph a tree\",\n",
        "\"cutset conditioning\" : \"implies for every consistent assignment to variables in S, removing from domains of remaining variables values inconsistent with assignment\",\n",
        "\"tree decomposition\" : \"another method of converting a CSP graph to a tree\",\n",
        "\"value symmetry\" : \"several ways of making assignments which are symmetric and hence only one needs to be selected\",\n",
        "\"symmetry-breaking constraint\" : \"adding a symmetry breaking constraint (e.g. arbitrary ordering constraint) to reduce the number of assignments\",\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "025dd6ac-c8a6-401b-e844-5a343dd96fed"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "Start using Factored Representation for each state comprising a set of variables, each having a value.  CSP search algorithms use structure of states and applygeneral rather than domain-specific heuristics to solve complicated problems.  It seeks to eliminate much of the search space by finding variable/value combinations that do notsatisfy the constraints. A CSP has three components: X, a set of variable; D, a set of domains, one for each variable; and C, a set of constraints defining permissible valuecombinations. A constraint Ci consists of a pair (scope, rel), where 'scope' consists of tuple of variables affected by the constraint and 'rel' defines valid values for thevariables.  The relation can be defined either explicitly as a set of all value tuples that satisfy the constraint or a function that can calculate whether a tuple is validbased on the relation.  A CSP is NP-complete in general. CSP can be used for map-coloring and job-shop scheduling.\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "Constraint propagation can be combined with search or used as preprocessing and may even result in a solution. AC-3 maintains a queue of arcs to be examined, initially all arcs. As each arc comes off of the queue, it is examined for arc-consistency and if the domain of the first node in the arc is changed, then arcs with allneighbors of the node are added to the queue.  If any domain comes down to nothing, then there is no consistent CSP solution. If not, the CSP  will be equivalent to the originalCSP but will be faster. Complexity of AC-3 is O(cd^3) where d is maximum domain size, c is number of binary constraints (arcs).\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              "Backtracking search for CSPs uses domain-independent heuristics to select which variable and values in the variable domain should be tried, what inferencescan be made at each step, how far back to backtrack, and is it possible to save and reuse partial solutions.\n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Constraint satisfaction problem** - CSP's solution has a value assigned to each variable, satisfying all constraints on the variable\n",
              "* **Consistent** - assignment of values to a variables not violating any constraints are considered consistent or legal\n",
              "* **Complete** - if every variable is assigned a value, the assignment is complete\n",
              "* **Solution** - a consistent, complete assignment of values to the variables in a problem is a solution\n",
              "* **Partial assignment** - if some variables do not have values assigned to them, the assignment is partial\n",
              "* **Partial solution** - a partial assignment that is consistent is a partial solution\n",
              "* **Constraint graph** - representation of a CSP, where nodes are variables of problem, and edges connect two variables having a constraint between them\n",
              "* **Precedence constraint** - defines ordering of tasks and when one task can begin with respect to earlier tasks\n",
              "* **Disjunctive constraint** - implies two tasks cannot overlap in time\n",
              "* **Unary constraint** - applies to value of one variable\n",
              "* **Binary constraint** - applies to values of two variables\n",
              "* **Binary csp** - is one with only unary and binary constraints; can be represented by a constraint graph\n",
              "* **Global constraint** - restricts arbitrary (not necessarily all) number of variables, e.g. Alldiff, where all variables have to have different values\n",
              "* **Constraint hypergraph** - has ordinary nodes (circles) for variables and hypernodes (squares) for n-ary constraints effecting n variables\n",
              "* **Preference constraints** - show which solutions are preferred and can be encoded as costs ( vs. absolute constraints which if violated eliminate solutions)\n",
              "* **Constrained optimization problem** - or COP are CSPs with preference constraints, solvable with optimization search algorithms, e.g. linear programs\n",
              "* **Constraint propagation** - where constraints are used to reduce number of legal values for a variable, and same for another variable and contiues\n",
              "* **Local consistency** - each node as variable and each edge as binary constraint can be examined eliminating inconsistent values everywhere in the graph\n",
              "* **Node-consistency** - ensures all values in variable domain meet variables unary constraints\n",
              "* **Arc-consistency** - ensures every value in a variable's domain meets variable's binary constraints\n",
              "* **Path-consistency** - (Xi,Xj) is path-consistent with variable Xm, if every consistent assignments to Xi,Xj has a consistent assignment to (Xi,Xm) and (Xm,Xj)\n",
              "* **K-consistency** - CSP is k-consistent if for a consistent assignment to any k-1 variables, the kth variable can have a consistent assignment\n",
              "* **Strongly k-consistent** - if k-consistent, k-1 consistent....1-consistent\n",
              "* **Resource constraint** - expressed as Atmost(10, P1, P2,...), resources need to sum to 10\n",
              "* **Bounds propagation** - domains represented by upper and lower bounds\n",
              "* **Bounds-consistent** - if, for both upper/lower bound values of each variable X, some Y value satisfies constraint between X and Y\n",
              "* **Commutativity** - In such problems, the order of actions is irrelevant; CSPs are commutative\n",
              "* **Minimum-remaining-values (mrv) heuristic** - selects the variable with the least 'legal' values\n",
              "* **Degree heuristic** - it selects variable that forms arcs (has constraints) with largest number of other unassigned variables, reducing branching factor\n",
              "* **Least-constraining-value heuristic** - After variable is picked, this heuristic chooses value eliminating least number of choices for neighboring variables\n",
              "* **Forward-checking** - process that establishes arc-consistency for every variable which is assigned by deleting any inconsistent value from all neighbors' domains\n",
              "* **Maintaining arc consistency (mac)** - combines forward checking starting with neighbors of assigned variable with AC-3, to reconfirm consistency across CSP\n",
              "* **Conflict set** - set of assignments to other variables that conflict with some value in variable; could also consider variable-set, not single variable\n",
              "* **Backjumping** - method for backtracking to the most recent assignment in the conflict set\n",
              "* **Conflicted-directed backjumping** - uses conflict sets conflicting with a set of variables to decide backjumping\n",
              "* **Constraint learning** - searches for minimum set of variables (called 'no-good', consists of variables and their values)from conflict set creating problems\n",
              "* **Mini-conflicts heuristic** - selects value that has least number of conflicts with other variables\n",
              "* **Constraint weighting** - concentrates search on important constraints\n",
              "* **Independent subproblems** - can be solved separately; these can be found by identifying connected components\n",
              "* **Directional arc consistency** - when in any ordering of variables, every Xi is arc-consistent with every Xj, where j>i\n",
              "* **Cycle cutset** - a subset of CSP's variables, S, removal of which makes constraint graph a tree\n",
              "* **Cutset conditioning** - implies for every consistent assignment to variables in S, removing from domains of remaining variables values inconsistent with assignment\n",
              "* **Tree decomposition** - another method of converting a CSP graph to a tree\n",
              "* **Value symmetry** - several ways of making assignments which are symmetric and hence only one needs to be selected\n",
              "* **Symmetry-breaking constraint** - adding a symmetry breaking constraint (e.g. arbitrary ordering constraint) to reduce the number of assignments\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 16,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 17,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 537
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "2694ee5d-5668-49bc-dc6d-16d681c3be85"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 18,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "2864ce03-446f-4034-9cb2-7203ce8014d0"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              "\n",
              "Acting and behaving humanly and rationally: 4 possible combinations. Acting humanly: Six disciplines of AI: NLP, knowledge representation, automated reasoning, machine learning,computer vision, robotics. Rational agent approach (standard model) has prevailed in AI, requires a fully specified objective.\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Your summary here \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              "An agent's decision on action at a point in time depends on built-in knowledge and percept history but not anything not observed.\n",
              "\n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              "Performance measures should focus on desired results rather than agent behavior.\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Agents can be physical or virtual/software.\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              "Distinction between agent program and agent function: program maps single percept to action; function can consider entire percept history; program implements functionFour types of agents: simple reflex agent, model-based reflex agent, goal-based agent and utility-based agent. Goal-based agent uses information about goal(s) along with model-informationto decide next action. Search and Planning are used by agent to achieve objective to reaching goal. Learning agent has four conceptual components: Learning element, Performance element,Critic and Problem Generator. The Performance element selects external actions to be taken. Critic provides feedback on how the agent is doing to the Learning element which decides howthe Performance element should be modified to perform better. The last component is the Problem Generator which suggests actionsleading to new experiences that can add more informationIn such a model, the external performance standard extracts a reward or penalty from the incoming percept which provides feedback on the agent's behavior. Environment representations lie on a continuum of complexity and expressive power: Atomic, Factored and Structured. Atomic implies indivisibility of each state of the world. Factored representation divides each state into variables or attributes each having a value.  Structured representation adds on relationships between variables. \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Rationality** - doing the correct thing\n",
              "* **Natural language processing** - to communicate effectively in a human language\n",
              "* **Knowledge representation** - entering in storage given and acquired knowledge\n",
              "* **Automated reasoning** - to respond to questions and draw new inferences\n",
              "* **Value alignment process** - process of agreeing our true preferences with objective given to machine\n",
              "* **Agent** - architecture plus program\n",
              "* **Rational agent** - agent acts to maximize its performance measure and under uncertainity, best expected outcome; given built-in knowledge, to date percept sequence\n",
              "* **Environment** - that part of the universe that is relevant for the specific agent\n",
              "* **Percept** - input received from sensors\n",
              "* **Percept sequence** - entire history of percepts\n",
              "* **Agent function** - how agent behaves with regard to a specific percept sequence, an abstract mathematical description\n",
              "* **Agent program** - internally concretely implements an agent's function, within a physical system \n",
              "* **Agent architecture** - generally computing platform coupled with physical actuators and sensors\n",
              "* **Consequentialism** - judging agent's behavior by how it modifies it's environment\n",
              "* **Performance measure** - evaluates any specific ordering of environment states; there are explicit and implicit performance measures\n",
              "* **Information gathering** - actions taken by agents to change future percepts\n",
              "* **Learning** - extracting information from what agent perceives\n",
              "* **Autonomy** - implies agent can learn from percepts and learning processes rather than relying entirely on prior knowledge\n",
              "* **Task environment** - problems that agent is built to solve,OR combination of Performance measure, Environment, agent's Actuator and Sensors (PEAS)\n",
              "* **Fully vs partially observable task environment** - where agent's sensors provide information on the complete (relevant) environment state at each point in time, is fully observable\n",
              "* **Single-agent vs multi-agent task environment** - distinction between competitive (chess-player) vs. cooperative multi-agent (taxi-driver and other drivers)\n",
              "* **Deterministic vs non-deterministic task environment** - determininistic if next environment state is determined solely by current state plus agent(s) action\n",
              "* **Stocastic vs non-deterministic task environment** - first explicitly has quantified probabilities, second has unquantified uncertainty \n",
              "* **Episodic vs sequential task environment** - first has atomic episodes not depending on previous episodes; second has current actions effecting future states\n",
              "* **Static vs dynamic task environment** - if when the agent is thinking/deciding, environment can change, is dynamic; else static\n",
              "* **Discrete vs continuous task environment** - Former has discrete environment state, time handling and percepts and actions by agent\n",
              "* **Known vs unknown task environment** - In former, outcomes or outcome probabilities for all actions are known; solitare known but partially observable; new game observable unknown\n",
              "* **Simple reflex agent** - acts based on current percept, ignoring past percept sequence\n",
              "* **Condition-action rule** - Simple reflex agent uses this rule, otherwise stated as 'if....-then....'\n",
              "* **Model-based agent** - uses models such as transition model and sensor model\n",
              "* **Transition model** - Contains information on how world evolves and how agent's actions change world\n",
              "* **Sensor model** - Contains information on how the state of the world is captured in the agent's percepts\n",
              "* **Goal-based agent** - Agent uses information on goal along with model information to decide actions\n",
              "* **Utility-based agent** - The agent acts based on a utility (or expected utility) function which should reflect the agent's performance measure\n",
              "* **Learning agent** - Could be agent of any of the other types but with additional ability to learn\n",
              "* **Localist representation** - has a one-to-one mapping between concepts and memory locations.\n",
              "* **Distributed representation** - implies a concept can be represented across many memory locations and each memory location can represent multiple different concepts.\n",
              "* **Other concept** - your definitions here\n",
              "* **Etc.** - your definitions here\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "List operations: list.append(item); list.insert(index, item); list.sort(key(optional), reverse = False/True) -- sort in place; list.reverse() -- in place;sorted(list) -- copy sorted; list.index(item) -- index of first occurrence; list.count(item) --number of occurrences; list.remove(item) -- remove first occurrence; list(zip(a, b))[(1, 'a'), (2, 'b'), (3, 'c')] -- makes tuples with elements of both lists; list(zip(\"foo\", \"bar\")) ---results-- [('f', 'b'), ('o', 'a'), ('o', 'r')]String operations: \"filler(eg white space, comma, #, etc)\".join(list of strings); text.split(\" ,-\") to remove white spaces, comma, hyphen, etc;Array operations: number of rows = len(array); number of columns = len(array[0])Slice operations on sequences (could be strings, sets, lists, etc) a[start:end:step]:copy(seqs): return(:);text.lower(), text.split(' '), text.capitalize(),dictionary operations: key in dict.keys(); dict.items(); dict.values(); dict = {'a' : 'fruit', 'b' : 'vegetables'}; defaultdict automatically initializes nonexistent dictionary valuesfrom collections import defaultdict; d = defaultdict(str); from collections import Counter; d = Counter(); d['dog'] 0matrix_flat = matrix.flatten()print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))== checks if points to objects of same value; is checks if two variables point to the same objecty = x[:] creates a shallow copy, i.e. a new object with the same valuedef myfun(b, c=3, d=\"hello\"): -- default arguments in functions, Non-default argument should always precede default arguments\n",
              "\n",
              "Review pg42 on\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - your definition here\n",
              "\n",
              "\n",
              "## WARNING: Your definition of 'reached' is too long!\n",
              "WARNING: Your definition of 'iterative deepening search' is too long!\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " Considering only the simplest environments in this chapter: episodic, single agent, fully observable, deterministic, static, discrete, and known. Informed(whereagent can estimate how far the goal is) and Uninformed(no such information available).\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "Search algorithms use data structure to keep track of search tree. Each node has state, parent, action(applied to parent to get node), path-cost (cost of path frominitial state to node). Following parent nodes back from goal to initial state gives solution. Three types of queues are used in search algorithms. Graph search and tree-like searchdeal differently with redundant paths. Searches are evaluated on four criteria: Completeness, Cost Optimality, Time Complexity, and Space Complexity. Complexity can be measured by |V| + |E| or by depth, d, or number of actions in an optimal solution; m, the maximum number of actions in any path; and b, branching factor or number of successors of a node thatto be considered.\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "Uninformed search strategies don't have information about distance from a state to the goal. Breadth-first search can be used if all actions have same cost. This issystematic, complete strategy and uses FIFO queue. Can do an early goal test, rather than late goal test. Has O(b^(d)) time and space complexity. Exponential-complexity search problemscan be solved by uninformed search only for small instances. Dijkstra's or uniform-cost algorithm spreads out in waves of uniform path-cost and does a late goal test. It returns thecheapest path. Depth-first search operates by expanding the deepest node first. It uses a tree-like search and does not maintain a table of reached nodes and is not complete. It returnsthe first solution found, not necessarily the cheapest. It may explore the same spaces many times over different paths but in acyclic spaces will eventually cover all spaces. A variant of DFScalled back-tracking search generates only one successor at a time and has a path of O(m) where m is maximum depth. Used for talks with large state descriptions. In best-fisrtbidirectional search, node to be expanded is one with minimum evaluation function, across either frontier.\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search using Atomic representations\n",
              "* **Search** - process of determining a sequence of actions (solution) to arrive at the goal; sometimes no solution may exist\n",
              "* **Solution** - a series of actions that lead to a goal state\n",
              "* **Goal formulation** - determining what is the goal\n",
              "* **Problem formulation** - Agent decides on a description of states and actions necessary to arrive at goal; abstraction of relevant part of environment\n",
              "* **Open-loop system** - where environment is fully observable, deterministic, known; agent can ignore percepts; known as open-loop system\n",
              "* **Closed-loop system** - agent monitors percepts\n",
              "* **Problem** - search problem has state space, initial state, goal states, available actions applicable in a state; transition model; action cost function\n",
              "* **State space** - a set of possible states for environment\n",
              "* **Initial state** - where agent starts from\n",
              "* **Goal states** - one or more environment states to be achieved by agent\n",
              "* **Action** - action available to agent in a specific state s, this is applicable in state s\n",
              "* **Transition model** - describes the new state resulting from an action in state s\n",
              "* **Action cost function** - provides cost of action a in state s to reach state a, based on agent's performance measure\n",
              "* **Path** - a series of actions; cost of path = sum of costs of actions in path\n",
              "* **Optimal solution** - has minimum cost among all solutions\n",
              "* **Graph** - can represent states as vertices and actions as directed edges between them\n",
              "* **Standardized problem** - objective is to describe or exercise various problem-solving methods e.g. grid, sokoban, sliding-tile puzzle problems\n",
              "* **Real-world problem** - route-finding, touring, VLSI layout, robot navigation, automatic assembly sequencing, protein design\n",
              "* **Search algorithm** - input is search problem and output is solution or lack of solution\n",
              "* **Node** - in search tree is a state and edge is an action\n",
              "* **Expand** - node means to find child or successor nodes from the resulting states of actions applicable to the node\n",
              "* **Frontier** - set of unexpanded nodes, normally use a queue data structure\n",
              "* **Reached** - set of visited nodes, can be stored in a hash table with key as state and value as node for state\n",
              "* **Best-first search** - choose node to minimize evaluation function, f(n)\n",
              "* **Priority-queue** - pops node with minimum evaluation function value from frontier, used in best-first search\n",
              "* **Fifo queue** - pops first node added to queue, used in breadth-first search (BFS)\n",
              "* **Lifo queue** - also known as Stack, pops last node added to queue, used in depth-first search (DFS)\n",
              "* **Graph search** - checks for redundant paths (e.g. best-first search\n",
              "* **Tree-like search** - does not check for redundant paths because of nature of problem, e.g. assembly\n",
              "* **Completeness** - Will the algorithm find a solution if there is any, or report lack of solution, if none? Needs be systematic.\n",
              "* **Cost optimality** - Will the algorithm find lowest path cost solution?\n",
              "* **Time complexity** - Time in seconds or abstractly by number of states and actions evaluated\n",
              "* **Space complexity** - Amount of memory utilized by algorithm\n",
              "* **Depth-limited search** - searches only upto depth limit l.\n",
              "* **Iterative deepening search** - uses depth-limiting search with increasing values of l, generally used  when search space larger than memory and depth not known.\n",
              "* **Bidirectional search** - simultaneously searches forward from initial state and backwards from goal\n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "Greedy best-first search may not find the cheapest path, is complete in finite state spaces but not in infinite state spaces. Maximum possible time and spacecomplexity is O(|V|), but a good heuristic function can enable O(bm). A* search is complete and cost-optimal, with an admissible heuristic. A consistent heuristic must be admissible though reverse not true. With inadmissible heuristic, A*'s cost-optimality is uncertain, A* is O(b^(d)). If there is at least one cost-optimal path where h(n) is admissible for all path nodes, then that path will be found. Also, if optimal solution has cost C* and second-best has cost C and if h(n) overestimates some costs but by notmore than C - C*, then A* will find cost-optimal solutions. A* has contours that each have the same f(n) values, with increasing value in outer contours, stretchingtowards the goal. Uniform-cost search has circular contours with no elongation towards the goal. Memory optimization during search could be by i) not maintaining a reached set,ii) remove states from reached depending on the algorithm or by maintaining reference counts, iii) using beam, IDA*, RBFS, MA*, SMA*. Bidirectional heuristic search has a lower boundas lb(m,n) = max(gf(m) + gb(n), ff(m), fb(n)) and a f function, f2(n) = max(2g(n), g(n)+h(n)). No node with g(n) > C*/2 will be expanded.\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "Heuristics for the 8-tile puzzle include i) the number of misplaced tiles, and ii) city-block or Manhattan distance or sum of horizontal and vertical distances of nodefrom goal. A measure of quality of a heuristic is the effective branching factor b*. One method of identifying heuristics is by relaxing some of the restrictions on the original problem|\n",
              "This creates a supergraph of the original state space with additional edges arising from such relaxations. if there are multiple admissible heuristics, then h(n)=max{h1(n),....,hk(n)}|Admissible heuristics can also be developed from subproblems of the problem. Algorithms use metalevel state space consisting of nodes holding internal computational state of a search program in an ordinary state space. Metalevel learning programs can improve their search  based on their experience.  Machine learning and reinforcement learning techniques can also be used improve search algorithms from their experience in earlier searches. Different heuristcs can be combined by these techniques to get an improved heuristic.\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Informed search** - uses information on position of goals to discover solutions more efficiently\n",
              "* **Heuristic function** - h(n), approximated cost of least expensive path to state node n to goal state\n",
              "* **Greedy best-first search** - type of best-first search selecting node for expansion based on lowest h(n) value; f(n) = h(n)\n",
              "* **A* search** - best-first search using evaluation function f(n) = g(n) + h(n), where g(n) = cost from initial state to node\n",
              "* **Admissible heuristic** - one that never exceeds actual cost from node to goal\n",
              "* **Consistency** - heuristic is consistent if h(n) <= c(n,a,n') + h(n'), where n' is successor node to n, type of triangle inequality\n",
              "* **Contours** - shapes that are equidistant from the initial node based on the relevant evaluation function\n",
              "* **Monotonic** - path costs always increase along a path since action costs are never negative\n",
              "* **Surely expanded nodes** - are nodes expanded by A* reachable from the initial state on path on which every node has f(n) < C*\n",
              "* **Optimally efficient** - what A* with a consistent heuristic is because any algorithm using same heuristic would expand same surely expanded nodes\n",
              "* **Satisficing** - solutions are those good enough but may be suboptimal due to using inadmissible heuristic (which may overestimate cost)\n",
              "* **Detour index** - multiplier applied to straight-line distance to adjust for curvature of roads\n",
              "* **Weighted a* search** - uses heuristic with greater weight assigned to it; f(n) = g(n) + W x h(n), with W > 1\n",
              "* **Bounded suboptimal search** - provides a solution with cost within W times the optimal cost\n",
              "* **Bounded cost search** - provides a solution with cost less than a constant C\n",
              "* **Unbounded cost search** - provides a solution without cap on the cost, but does so quickly, e.g. speedy search\n",
              "* **Speedy search** - type of greedy best-first search using as heuristic estimated number of actions to reach goal, disregarding cost\n",
              "* **Reference count** - how many times a state has been visited\n",
              "* **Beam search** - limits size of frontier by only retaining k nodes with highest f-scores or with f-scores not much below best f-score\n",
              "* **Iterative deepening a* search (ida*)** - uses cutoff as smallest f-value higher than cutoff in prior iteration to progressively expand search\n",
              "* **Recursive best-first search (rbfs)** - uses linear space, stores best f-score (backed-up value) of subtree and can recurse back based on this value in future\n",
              "* **Sma*** - simplified memory-bounded A* drops node with worst f-score (backing its value to parent) when memory is full before adding node\n",
              "* **Effective branching factor** - solution to N+1 = 1+b*+(b*)^2+(b*)^3+....+(b*)^d, where N is total nodes generated by A*, d = depth\n",
              "* **Effective depth** - depth resulting from reduction from original depth by a constant factor kh due to A* pruning\n",
              "* **Relaxed problem** - developed from original problem by  relaxing some of the restrictions\n",
              "* **Pattern database** - holds the costs for every subproblem for reuse over time\n",
              "* **Disjoint pattern databases** - databases holding non-overlapping subproblems\n",
              "* **Differential heuristic** - hDH(n) = max(over all landmarks) of |C*(n,L) - C*(goal, L)|\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "## WARNING: Your definition of 'anchoring effect' is too long!\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "Adversarial search problems exist in competitive environments where multiple agents have conflicting goals. Three approaches can be taken in regard to suchenvironments: i) treat them as an economy, ii) treat the agents as adding randomness, but this ignores the adversarial aspect, and iii) explicitly model the behavior. Winnerat each stage can be determined either by a heuristic evaluation function or averaging results from several fast simulations going from current state to goal. Games considered are deterministic, two-player, turn-taking, perfect information, zero-sum games.\n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "Minimax search is a recursive algorithm does a depth-first search to the leaves of a tree and then return minimax values up to the root. If m is tree'smaximum depth and b is branching factor, then time complexity is O(b^(m)) and space complexity is O(bm) if all actions generated at the same time or O(m) if generatedone at a time.  In multiplayer game, the value at each node is a vector of values, with terminal nodes having vector of utility values for each player. For intermediatenode n, the backedup vector is that of successor state with highest value for player choosing at n. Alpha-beta pruning works by evaluating if for every node n that a playercan move to, there is a better choice either at the same level or at any point higher in the tree. If so, player never chooses n. Hence, it can be pruned. Alpha-beta pruningworks depending on order in which states are examined. Alpha-beta has time complexity of O(b^(m)), but can be improved to O(b^(m/2)), so that that effective branching factorbecomes sqrt(b) with perfect move ordering or but could get to 2*O(b^(m/2)) with some heuristics on move ordering.  Improvements could be by iterative deepening, killer moveheuristic, transposition table to store states.\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "Can cut off search for alpha-beta pruning by setting a depth limit and an evaluation function, which should only be applied to quiescent positions, where nomajor changes will occur shortly. The quiescence search will consider only certain types of moves.  A better approach is to use iterative deepening. There is also a horizon effect, due to moves beyond the horizon, which could be mitigated by singular extensions to the depth limit for clearly better moves. Forward pruning is a Type B Strategy where future moves that don't look good are pruned. Beam search is not a good forwarding pruning method. ProbCut or probabilitic cut algorithm uses shallow search combinedwith past experience to that estimate a value v at depth d would be outside of alpha and beta.  Combining a number of these techniques gets the best result. Another optionto improve alpha-beta search is to create large lookup tables for the moves from the intial state and around the goal state.   \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "Stochastic games include a probability element.  Hence there are chance nodes in addition to MAX and MIN nodes.  It is only possible to calculate the expectedvalue of a node, which is the average over all outcomes of the chance nodes. There is also an expectiminimax value as average of chance node outcomes.  While pruning nodes,not only their values but their probabilities need to be considered. Complexity of expectiminimax is O(b^(m) x n^(m)). Alternative to using an evaluation function is usinga Monte Carlo tree search instead. \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "Uncertainty about possible current states, P(s), and about action outcomes with transition probability P(s'|s,a). The two are related as under:$$P(RESULT(a)=s') = sigma(over s)P(s)P(s'|s, a)$$The environment is assumed to be episodic and agent's preferences are reflected by a utility function, which gives each state a number. The expected utility of an action is theprobability-weighted average utility of its outcomes. Maximum expected utility (MEU) means that a rational agent should select actions to maximize expected utility.\n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "Constraints on rational preferences are: Orderability, Transitivity, Continuity, Substitutability, Monotonicity and Decomposability. In a deterministic environment,needs only an ordinal (ranking) function or value function. \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Pruning** - ignores parts of search tree that have no effect on optimal move significantly improving the search\n",
              "* **Evaluation function** - heuristic calculation to decide the winner based on specifics of the state\n",
              "* **Perfect information** - = fully observable\n",
              "* **Zero-sum games** - games where outcomes for the two players are equal in absolute terms but with opposite signs\n",
              "* **Move** - = action\n",
              "* **Position** - = state\n",
              "* **Initial state** - describes how the game looks like at the beginning\n",
              "* **Transition model** - specifies the state coming as a result of action a on state s\n",
              "* **Terminal test** - boolean which is true if game has ended and false if not\n",
              "* **Terminal states** - states where game is over\n",
              "* **Utility function** - provides value to a player when game ends, also known as objective or payoff function\n",
              "* **State space graph** - defined by initial state, ACTIONS/RESULTS functions; where vertices = states, edges = moves, state can be reached by multiple paths\n",
              "* **Game tree** - theoretical search tree tracing every path to a terminal state\n",
              "* **Ply** - denotes one move by one player increasing depth by one\n",
              "* **Minimax value** - utility for MAX in a state, assuming both players play optimally to the end\n",
              "* **Minimax search** - MAX moves to state with max value, MIN moves to state with min value\n",
              "* **Alpha-beta pruning** - is so named due to alpha/beta, values of the best (highest-value for MAX and lowest-value for MIN, respectively, on path)\n",
              "* **Type a strategy** - for Alpha-Beta, considers a wide but shallow  part of tree and uses heuristic evaluation of nodes at that level\n",
              "* **Type b strategy** - more popular, considers deep but narrow part of tree, avoids moves that appear expensive, follows optimal-looking paths to extent possible\n",
              "* **Evaluation function** - calculates values for intermediate nodes using estimated material values for features, combining them in linear or non-linear fashion\n",
              "* **Features** - characteristics of a state\n",
              "* **Unbiased** - estimates for which the expected value of the difference between estimate and actual value is zero\n",
              "* **Optimizer's curse** - likelihood of the estimated expected utility of best choice to be too optimistic\n",
              "* **Certainty effect** - strong preference of people towards certain positive outcomes as against uncertain outcomes\n",
              "* **Ambiguity aversion** - people giving lower preference to outcomes that are ambiguous\n",
              "* **Framing effect** - the way a situation or question is worded can have huge effect on people's decisions\n",
              "* **Anchoring effect** - people use as benchmark a number or fact that is given to them, and evaluate other outcomes with reference to this\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "Start using Factored Representation for each state comprising a set of variables, each having a value.  CSP search algorithms use structure of states and applygeneral rather than domain-specific heuristics to solve complicated problems.  It seeks to eliminate much of the search space by finding variable/value combinations that do notsatisfy the constraints. A CSP has three components: X, a set of variable; D, a set of domains, one for each variable; and C, a set of constraints defining permissible valuecombinations. A constraint Ci consists of a pair (scope, rel), where 'scope' consists of tuple of variables affected by the constraint and 'rel' defines valid values for thevariables.  The relation can be defined either explicitly as a set of all value tuples that satisfy the constraint or a function that can calculate whether a tuple is validbased on the relation.  A CSP is NP-complete in general. CSP can be used for map-coloring and job-shop scheduling.\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "Constraint propagation can be combined with search or used as preprocessing and may even result in a solution. AC-3 maintains a queue of arcs to be examined, initially all arcs. As each arc comes off of the queue, it is examined for arc-consistency and if the domain of the first node in the arc is changed, then arcs with allneighbors of the node are added to the queue.  If any domain comes down to nothing, then there is no consistent CSP solution. If not, the CSP  will be equivalent to the originalCSP but will be faster. Complexity of AC-3 is O(cd^3) where d is maximum domain size, c is number of binary constraints (arcs).\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              "Backtracking search for CSPs uses domain-independent heuristics to select which variable and values in the variable domain should be tried, what inferencescan be made at each step, how far back to backtrack, and is it possible to save and reuse partial solutions.\n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Constraint satisfaction problem** - CSP's solution has a value assigned to each variable, satisfying all constraints on the variable\n",
              "* **Consistent** - assignment of values to a variables not violating any constraints are considered consistent or legal\n",
              "* **Complete** - if every variable is assigned a value, the assignment is complete\n",
              "* **Solution** - a consistent, complete assignment of values to the variables in a problem is a solution\n",
              "* **Partial assignment** - if some variables do not have values assigned to them, the assignment is partial\n",
              "* **Partial solution** - a partial assignment that is consistent is a partial solution\n",
              "* **Constraint graph** - representation of a CSP, where nodes are variables of problem, and edges connect two variables having a constraint between them\n",
              "* **Precedence constraint** - defines ordering of tasks and when one task can begin with respect to earlier tasks\n",
              "* **Disjunctive constraint** - implies two tasks cannot overlap in time\n",
              "* **Unary constraint** - applies to value of one variable\n",
              "* **Binary constraint** - applies to values of two variables\n",
              "* **Binary csp** - is one with only unary and binary constraints; can be represented by a constraint graph\n",
              "* **Global constraint** - restricts arbitrary (not necessarily all) number of variables, e.g. Alldiff, where all variables have to have different values\n",
              "* **Constraint hypergraph** - has ordinary nodes (circles) for variables and hypernodes (squares) for n-ary constraints effecting n variables\n",
              "* **Preference constraints** - show which solutions are preferred and can be encoded as costs ( vs. absolute constraints which if violated eliminate solutions)\n",
              "* **Constrained optimization problem** - or COP are CSPs with preference constraints, solvable with optimization search algorithms, e.g. linear programs\n",
              "* **Constraint propagation** - where constraints are used to reduce number of legal values for a variable, and same for another variable and contiues\n",
              "* **Local consistency** - each node as variable and each edge as binary constraint can be examined eliminating inconsistent values everywhere in the graph\n",
              "* **Node-consistency** - ensures all values in variable domain meet variables unary constraints\n",
              "* **Arc-consistency** - ensures every value in a variable's domain meets variable's binary constraints\n",
              "* **Path-consistency** - (Xi,Xj) is path-consistent with variable Xm, if every consistent assignments to Xi,Xj has a consistent assignment to (Xi,Xm) and (Xm,Xj)\n",
              "* **K-consistency** - CSP is k-consistent if for a consistent assignment to any k-1 variables, the kth variable can have a consistent assignment\n",
              "* **Strongly k-consistent** - if k-consistent, k-1 consistent....1-consistent\n",
              "* **Resource constraint** - expressed as Atmost(10, P1, P2,...), resources need to sum to 10\n",
              "* **Bounds propagation** - domains represented by upper and lower bounds\n",
              "* **Bounds-consistent** - if, for both upper/lower bound values of each variable X, some Y value satisfies constraint between X and Y\n",
              "* **Commutativity** - In such problems, the order of actions is irrelevant; CSPs are commutative\n",
              "* **Minimum-remaining-values (mrv) heuristic** - selects the variable with the least 'legal' values\n",
              "* **Degree heuristic** - it selects variable that forms arcs (has constraints) with largest number of other unassigned variables, reducing branching factor\n",
              "* **Least-constraining-value heuristic** - After variable is picked, this heuristic chooses value eliminating least number of choices for neighboring variables\n",
              "* **Forward-checking** - process that establishes arc-consistency for every variable which is assigned by deleting any inconsistent value from all neighbors' domains\n",
              "* **Maintaining arc consistency (mac)** - combines forward checking starting with neighbors of assigned variable with AC-3, to reconfirm consistency across CSP\n",
              "* **Conflict set** - set of assignments to other variables that conflict with some value in variable; could also consider variable-set, not single variable\n",
              "* **Backjumping** - method for backtracking to the most recent assignment in the conflict set\n",
              "* **Conflicted-directed backjumping** - uses conflict sets conflicting with a set of variables to decide backjumping\n",
              "* **Constraint learning** - searches for minimum set of variables (called 'no-good', consists of variables and their values)from conflict set creating problems\n",
              "* **Mini-conflicts heuristic** - selects value that has least number of conflicts with other variables\n",
              "* **Constraint weighting** - concentrates search on important constraints\n",
              "* **Independent subproblems** - can be solved separately; these can be found by identifying connected components\n",
              "* **Directional arc consistency** - when in any ordering of variables, every Xi is arc-consistent with every Xj, where j>i\n",
              "* **Cycle cutset** - a subset of CSP's variables, S, removal of which makes constraint graph a tree\n",
              "* **Cutset conditioning** - implies for every consistent assignment to variables in S, removing from domains of remaining variables values inconsistent with assignment\n",
              "* **Tree decomposition** - another method of converting a CSP graph to a tree\n",
              "* **Value symmetry** - several ways of making assignments which are symmetric and hence only one needs to be selected\n",
              "* **Symmetry-breaking constraint** - adding a symmetry breaking constraint (e.g. arbitrary ordering constraint) to reduce the number of assignments\n",
              "* **Concept** - definition\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              " Your summary here \n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              " Your summary here \n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Concept** - definition\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
