{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "344222ad-a216-45e3-9726-b566dead59fe"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ef81cd11-e574-43c8-fb57-4c2e2e3d803c"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"  Different people approach AI with different goals in mind. Two important questions to ask are: Are you concerned with thinking, or behavior? Do you want to model humans,\n",
        "or try to achieve the optimal results?\n",
        "According to what we have called the standard model, AI is concerned mainly with\n",
        "rational action. An ideal intelligent agent takes the best possible action in a situation.\n",
        "We study the problem of building agents that are intelligent in this sense.\n",
        "Two refinements to this simple idea are needed: first, the ability of any agent, human\n",
        "or otherwise, to choose rational actions is limited by the computational intractability of\n",
        "doing so; second, the concept of a machine that pursues a definite objective needs to be\n",
        "replaced with that of a machine pursuing objectives to benefit humans, but uncertain as\n",
        "to what those objectives are.\"\"\" \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 = \"\"\" Philosophers use the term weak AI for the hypothesis that machines could possibly\n",
        "behave intelligently, and strong AI for the hypothesis that such machines would count\n",
        "as having actual minds (as opposed to simulated minds) \"\"\"\n",
        "chapter27_2 = \"\"\"Alan Turing rejected the question “Can machines think?” and replaced it with a be\u0002havioral test. He anticipated many objections to the possibility of thinking machines.\n",
        "Few AI researchers pay attention to the Turing test, preferring to concentrate on their\n",
        "systems’ performance on practical tasks, rather than the ability to imitate humans.\n",
        "• Consciousness remains a mystery.\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" What is rational at any given time depends on four things:\n",
        "• The performance measure that defines the criterion of success.\n",
        "• The agent’s prior knowledge of the environment.\n",
        "• The actions that the agent can perform.\n",
        "• The agent’s percept sequence to date\n",
        "\n",
        "distinguish between rationality and omniscience. An omniscient\n",
        "agent knows the actual outcome of its actions and can act accordingly; but omniscience is\n",
        "impossible in reality. \n",
        "Rationality maximizes expected performance, while perfection maximizes actual performance.\n",
        "rational choice depends only on the percept sequence to date\n",
        "\n",
        "To the extent that an agent relies on the prior knowledge of its designer rather than on its\n",
        "Autonomy own percepts and learning processes, we say that the agent lacks autonomy. A rational agent\n",
        "should be autonomous—it should learn what it can to compensate for partial or incorrect\n",
        "prior knowledge.\"\"\"\n",
        "chapter2_3 = \"\"\" PEAS (Performance, Environment, Actuators, Sensors) description\n",
        "Fully observable vs. partially observable: If an agent’s sensors give it access to the Fully observable\n",
        "complete state of the environment at each point in time, then we say that the task environ- Partially observable\n",
        "ment is fully observable.\n",
        "An environment might be partially\n",
        "observable because of noisy and inaccurate sensors or because parts of the state are simply\n",
        "missing from the sensor data\n",
        "Deterministic vs. nondeterministic. If the next state of the environment is completely\n",
        "determined by the current state and the action executed by the agent(s), then we say the\n",
        "environment is deterministic; otherwise, it is nondeterministic.\n",
        "the word stochastic is used by some as a synonym for “nondeterministic,” Stochastic\n",
        "but we make a distinction between the two terms; we say that a model of the environment\n",
        "is stochastic if it explicitly deals with probabilities (e.g., “there’s a 25% chance of rain to\u0002morrow”) and “nondeterministic” if the possibilities are listed without being quantified (e.g.,\n",
        "“there’s a chance of rain tomorrow”)\n",
        "Static vs. dynamic: If the environment can change while an agent is deliberating, then\n",
        "we say the environment is dynamic for that agent; otherwise, it is static\n",
        "The distinction between known and unknown environments is not the same as the one\n",
        "between fully and partially observable environments.   \"\"\"\n",
        "chapter2_4 = \"\"\" simple reflex agent. \n",
        "These agents select actions on the basis Simple reflex agent of the current percept, ignoring the rest of the percept history\n",
        " Model-based reflex agents\n",
        " Simple reflex agents respond directly to percepts, whereas model-based reflex agents\n",
        "maintain internal state to track aspects of the world that are not evident in the current\n",
        "percept. Goal-based agents act to achieve their goals, and utility-based agents try to\n",
        "maximize their own expected “happiness.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \" content an agent’s sensors are perceiving\",\n",
        "\"percept sequence\" : \" complete history of everything the agent has ever perceived\",\n",
        "\"agent function\": \"maps any given percept sequence to an action.abstract mathematical description\",\n",
        "\"agent program\":\"a concrete implementation, running within some physical system\",\n",
        "\" rational agent\":\" one that does the right thing\",\n",
        "\" performance measure\":\"evaluates any Performance measure given sequence of environment states\"\n",
        "\"rational agent\":\" For each possible percept sequence, a rational agent should select an action that is ex\u0002pected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n",
        "\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "cellView": "form",
        "outputId": "10ce52d9-d4f9-4137-99ff-9578dcdade24"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \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 Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\" agent\" : \" anything that can be viewed as perceiving its environment through sensors and Sensor acting upon that environment through actuators.\",\n",
        "\"\":\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6c9789f4-242b-4b15-98f8-42d0e16986a9"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" search problem can be defined formally as follows:\n",
        "• A set of possible states that the environment can be in. We call this the state space.\n",
        "• The initial state that the agent starts in. For example: Arad.\n",
        " • A set of one or more goal states. Sometimes there is one goal state (e.g., Bucharest),\n",
        "Goal states sometimes there is a small set of alternative goal states, and sometimes the goal is\n",
        "defined by a property that applies to many states (potentially an infinite number). \n",
        "• The actions available to the agent. Given a state s, ACTIONS(s) returns a finite2\n",
        "set of Action\n",
        "actions that can be executed in s. We say that each of these actions is applicable in s. Applicable\n",
        "An example:\n",
        "ACTIONS(Arad) = {ToSibiu,ToTimisoara,ToZerind}.\n",
        "• A transition model, which describes what each action does. RESULT(s, a) returns the Transition model\n",
        "state that results from doing action a in state s. For example,\n",
        "RESULT(Arad, ToZerind) = Zerind .\n",
        "• An action cost function, \"\"\"\n",
        "chapter3_2 = \"\"\" A standardized problem\n",
        " A real-world problem, \"\"\"\n",
        "chapter3_3 = \"\"\"  distinction between the state space and the search tree.\n",
        "The state space describes the (possibly infinite) set of states in the world, and the actions\n",
        "that allow transitions from one state to another. The search tree describes paths between\n",
        "these states, reaching towards the goal.\n",
        "Best-first search\n",
        "choose a node, n, with minimum value of some Best-first search\n",
        "evaluation function, f(n). It is a  graph search algorithm\n",
        " We call a search algorithm a graph search if it checks for redundant\n",
        "paths and a tree-like search6 Tree-like search if it does not check.\n",
        " Measuring problem-solving performance\n",
        "  Completeness,Cost optimality, Time complexity,  Space complexity  \"\"\"\n",
        "chapter3_4 = \"\"\"Uninformed Search Strategies\n",
        "implement breadth-first search as a call to\n",
        "BEST-FIRST-SEARCH where the evaluation function f(n) is the depth of the node—that is,\n",
        "the number of actions it takes to reach the node.\n",
        "every state has b successors, o both time and space complexity are O(b^d).\n",
        "The memory requirements are a bigger problem for breadth-first search than the execution time\n",
        ". \n",
        "This is called Dijkstra’s algorithm by the theoretical computer science community, and uniform-cost search Uniform-cost search\n",
        "by the AI community\n",
        "Iterative deepening search: Like depth-first search, its memory requirements are modest: O(bd) when there is a\n",
        "solution, or O(bm) on finite state spaces with no solution. Like breadth-first search, iterative\n",
        "deepening is optimal for problems where all actions have the same cost, and is complete on\n",
        "finite acyclic state spaces, or on any finite state space when we check nodes for cycles all the\n",
        "way up the path.\n",
        "The time complexity is O(b^d) when there is a solution, or O(b^m) when there is none\n",
        "In general, iterative deepening is the preferred\n",
        "uninformed search method when the search state space is larger than can fit in memory and\n",
        "the depth of the solution is not known.\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
        "\" Uninformed search\":\" have access only to the problem definition. Algorithms build a search tree in an attempt to find a solution. Algorithms differ based on which node they expand first\",\n",
        "\"Best-first search\":\" selects nodes for expansion using to an evaluation function.\",\n",
        "\"Breadth-first search\": \"expands the shallowest nodes first; it is complete, optimal for unit action costs, but has exponential space complexity.\",\n",
        "\"Uniform-cost search\":\"expands the node with lowest path cost, g(n), and is optimal for general action costs.\",\n",
        "\"Depth-first search\":\"expands the deepest unexpanded node first. It is neither com\u0002plete nor optimal, but has linear space complexity. Depth-limited search adds a depth bound.\",\n",
        "\"Iterative deepening search\":\"calls depth-first search with increasing depth limits until a goal is found. It is complete when full cycle checking is done, optimal for unit action costs, has time complexity comparable to breadth-first search, and has linear space complexity.\",\n",
        "\"Bidirectional search\":\"expands two frontiers, one around the initial state and one around the goal, stopping when the two frontiers meet\"    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f8c6dc37-627d-494b-d493-ce53672224a4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Greedy best-first search: evaluation function f(n) = h(n)\n",
        "Greedy best-first graph search is complete in finite state spaces, but not in infinite ones.\n",
        "The worst-case time and space complexity is O(|V|). With a good heuristic function, however,\n",
        "the complexity can be reduced substantially, on certain problems reaching O(bm).\n",
        "A* search: evaluation function f(n) = g(n) +h(n)\n",
        "\n",
        "A∗ search is complete.11 Whether A∗ is cost-optimal depends on certain properties of\n",
        "Admissible heuristic. A key property is admissibility: an admissible heuristic is one that never\n",
        "overestimates the cost to reach a goal.The space complexity of A∗ is still an issue for many problems.\n",
        "A slightly stronger property is called consistency. A heuristic h(n) is consistent if, for\n",
        "every node n and every successor n\n",
        "′ of n generated by an action a, we have:\n",
        "h(n) ≤ c(n,a,n′) +h(n')\n",
        "Every consistent heuristic is admissible (but not vice versa), so with a consistent heuristic,\n",
        "A∗is cost-optimal. \n",
        "A* is efficient because it prunes away search tree nodes that are not necessary for finding\n",
        "an optimal solution.\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\" One way to characterize the quality of a heuristic is the effective branching factor b∗. A well-designed heuristic would have a value of b∗ close to 1.\n",
        "A better way to characterize the effect of A∗ pruning\n",
        "Effective depth with a given heuristic h is that it reduces the effective depth by a constant kh compared to\n",
        "the true depth. This means that the total search cost is O(b^(d−kh) ) compared to O(b^d) for an uninformed search\n",
        "the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem\n",
        "\n",
        "Admissible heuristics can also be derived from the solution cost of a subproblem of a given problem.\n",
        "The idea behind pattern databases is to store these exact solution costs for every possible Pattern database\n",
        "subproblem instance\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"h2 dominates h1\" : \"for any node n, h2(n) ≥ h1(n), A∗ using h2 will never expand more nodes than A∗ using h1\",\n",
        "\"Informed search methods\":\"have access to a heuristic function h(n) that estimates the cost of a solution from n. They may have access to additional information such as pattern databases with solution costs.\",\n",
        "\"Greedy best-first search\":\"expands nodes with minimal h(n). It is not optimal but is often efficient.\",\n",
        "\"Bidirectional A∗ search is sometimes more efficient than A∗ itself.\",\n",
        "\"IDA∗ (iterative deepening A∗search)\": \"is an iterative deepening version of A∗, and thus adresses the space complexity issue.\",\n",
        "\"RBFS (recursive best-first search) and SMA∗(simplified memory-bounded A∗)\":\"are robust, optimal search algorithms that use limited amounts of memory; given enough time, they can solve problems for which A∗ runs out of memory.\",\n",
        "\"Beam search\":\"puts a limit on the size of the frontier; that makes it incomplete and suboptimal, but it often finds reasonably good solutions and runs faster than complete searches.\",\n",
        "\"Weighted A∗search\" :\"focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "cellView": "form",
        "outputId": "6a33bad1-c16f-44e7-b70a-5755faa0ad38"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" . A game can be formally defined with the following elements:\n",
        "• S0: The initial state, which specifies how the game is set up at the start.\n",
        "• TO-MOVE(s): The player whose turn it is to move in state s.\n",
        "• ACTIONS(s): The set of legal moves in state s.\n",
        "• RESULT(s, a): The transition model, which defines the state resulting from taking action a in state s.\n",
        "• IS-TERMINAL(s): A terminal test, which is true when the game is over and false \n",
        "otherwise. States where the game has ended are called terminal states. \n",
        "• UTILITY(s, p): A utility function (also called an objective function or payoff function),\n",
        "which defines the final numeric value to player p when the game ends in terminal state s.\n",
        "In chess, the outcome is a win, loss, or draw, with values 1, 0, or 1/2.2 Some games\n",
        "have a wider range of possible outcomes—for example, the payoffs in backgammon\n",
        "range from 0 to 192. \n",
        "We define the complete game tree as a search tree that follows every sequence of moves all the way to a terminal state.\"\"\"\n",
        "chapter5_2 = \"\"\"The minimax algorithm performs a complete depth-first exploration of the game tree.\n",
        "If the maximum depth of the tree is m and there are b legal moves at each point, then the\n",
        "time complexity of the minimax algorithm is O(b^m). The space complexity is O(bm) for an\n",
        "algorithm that generates all actions at once, or O(m) for an algorithm that generates actions one at a time.\n",
        "The exponential complexity makes MINIMAX impractical for complex games.\n",
        "\n",
        "The effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined\n",
        "If this could be done perfectly, alpha–beta would need to examine only O(b^m/2) nodes to pick the best move, instead of O(b^m) for minimax. This means that the effective branching\n",
        "factor becomes √b instead of b—for chess, about 6 instead of 35. Put another way, alpha–beta with perfect move ordering can solve a tree roughly twice as deep as minimax in the\n",
        "same amount of time. With random move ordering, the total number of nodes examined will be roughly O(b^3m/4) for moderate b. \n",
        "Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the theoretical limit.\n",
        "In game tree search, repeated states can occur because of transpositions—different Transposition\n",
        "permutations of the move sequence that end up in the same position, and the problem can be\n",
        "addressed with a transposition table that caches the heuristic value of states.\n",
        "there are still too many states to explore in the time available, solution:\n",
        "Type A strategy(chess programs) considers all possible moves to a certain depth in the search tree, and then\n",
        "uses a heuristic evaluation function to estimate the utility of states at that depth. It explores\n",
        "a wide but shallow portion of the tree. A Type B strategy(Go programs) ignores moves that look bad, and\n",
        "follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree.\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"A heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state s to player p.\n",
        "For terminal states, it must be that EVAL(s, p)=UTILITY(s, p) and for nonterminal states, the evaluation must be somewhere between a loss and a win: UTILITY(loss, p) ≤\n",
        "EVAL(s, p) ≤ UTILITY(win, p).\n",
        "what makes for a good evaluation function?\n",
        "must not take too long! + the evaluation function should be strongly correlated with the actual chances of winning\n",
        "Most evaluation functions work by calculating various features of the state\n",
        "weighted linear function:\n",
        "in fact it involves a strong assumption: that the contribution of each feature is independent of the values of the other features.\n",
        "The most straightforward approach to controlling the amount of search is to\n",
        "set a fixed depth limit so that IS-CUTOFF(state, depth) returns true for all depth greater than\n",
        "some fixed depth d (as well as for all terminal states). The depth d is chosen so that a move\n",
        "is selected within the allocated time. A more robust approach is to apply iterative deepening.\n",
        "(See Chapter 3.) When time runs out, the program returns the move selected by the deepest\n",
        "completed search. As a bonus, if in each round of iterative deepening we keep entries in\n",
        "the transposition table, subsequent rounds will be faster, and we can use the evaluations to\n",
        "improve move ordering.\n",
        "The evaluation function should be applied only to positions that are quiescent—that is,\n",
        "positions in which there is no pending move (such as a capturing the queen) that would wildly\n",
        "swing the evaluation. For nonquiescent positions the IS-CUTOFF returns false, and the search\n",
        "Quiescence search continues until quiescent positions are reached. This extra quiescence search is sometimes\n",
        "restricted to consider only certain types of moves, such as capture moves, that will quickly\n",
        "resolve the uncertainties in the position.\n",
        "The horizon effect is more difficult to eliminate. It arises when the program is facing\n",
        "an opponent’s move that causes serious damage and is ultimately unavoidable, but can be\n",
        "temporarily avoided by the use of delaying tactics.\n",
        "Alpha–beta pruning prunes branches of the tree that can have no effect on the final evaluation,\n",
        "but forward pruning prunes moves that appear to be poor moves, but might possibly be good Forward pruning\n",
        "ones.\n",
        "One approach to forward pruning is beam search\n",
        "Another technique, late move reduction, works under the assumption that move ordering\n",
        "has been done well, and therefore moves that appear later in the list of possible moves are\n",
        "less likely to be good moves. But rather than pruning them away completely, we just reduce\n",
        "the depth to which we search these moves, thereby saving time. \"\"\"\n",
        "chapter5_5 = \"\"\" for stochastic games,chance nodes denoting the probabilities associated with each action as well as expecti-minimax values are included in the minimax tree\n",
        "Games of chance can be handled by expectiminimax, an extension to the minimax\n",
        "algorithm that evaluates a chance node by taking the average utility of all its children,\n",
        "weighted by the probability of each child.\n",
        "As with minimax, the obvious approximation to make with expectiminimax is to cut the\n",
        "search off at some point and apply an evaluation function to each leaf. One might think that\n",
        "evaluation functions for games such as backgammon should be just like evaluation functions\n",
        "for chess—they just need to give higher values to better positions. But in fact, the presence\n",
        "of chance nodes means that one has to be more careful about what the values mean.\n",
        "The program behaves totally differently if we make a change to some of the evaluation values,\n",
        "even if the preference order remains the same.\n",
        "It turns out that to avoid this problem, the evaluation function must return values that are\n",
        "a positive linear transformation of the probability of winning \n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"P(RESULT(a)=s′) = ∑_sP(s)P(s′|s,a). \n",
        "he agent’s preferences are captured by a utility function, U(s), which assigns a single number to express the Utility function\n",
        "desirability of a state. The expected utility of an action given the evidence, EU(a), is just the Expected utility\n",
        "average utility value of the outcomes, weighted by the probability that the outcome occurs:\n",
        "EU(a) = ∑s′P(RESULT(a)=s′)U(s′)\n",
        "\n",
        "The principle of maximum expected utility (MEU) says that a rational agent should choose\n",
        "the action that maximizes the agent’s expected utility:\n",
        "action = argmaxEU(a).\n",
        "In a sense, the MEU principle could be seen as a prescription for intelligent behavior. All an\n",
        "intelligent agent has to do is calculate the various quantities, maximize utility over its actions,\n",
        "and away it goes. But this does not mean that the AI problem is solved by the definition!\n",
        "The MEU principle formalizes the general notion that an intelligent agent should “do the\n",
        "right thing,” but does not operationalize that advice.\n",
        "The MEU principle formalizes the general notion that an intelligent agent should “do the\n",
        "right thing,” but does not operationalize that advice.\n",
        "\n",
        "central justification for the MEU principle:\n",
        "If an agent acts so as to maximize a utility function that correctly reflects the performance measure,\n",
        "then the agent will achieve the highest possible performance score (averaged over all the possible environments)\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "The primary issue for utility theory:\n",
        "to understand how preferences between complex lotteries are related to preferences between the underlying states in those lotteries.\n",
        "address this issue:\n",
        "we list six constraints that we require any reasonable preference relation to obey:\n",
        "orderability, transitivity, continuity, substitutability, monotonicity, and decomposability.\n",
        "\n",
        "once the probabilities and utilities of the possible outcome states are specified,\n",
        "the utility of a compound lottery involving those states is completely determined.\n",
        "he preceding theorems establish that (assuming the constraints on rational preferences)\n",
        "a utility function exists for any rational agent. The theorems do not establish that the utility function is unique.\n",
        "\n",
        "As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter.\n",
        "  \"\"\"\n",
        "chapter16_3 = \"\"\" We say that the agent exhibits a monotonic preference for more money. This does\n",
        "not mean that money behaves as a utility function, because it says nothing about preferences\n",
        "between lotteries involving money.\n",
        "The difference between the EMV of a lottery and its certainty equivalent is called the in\u0002surance premium. Risk aversion is the basis for the insurance industry, because it means that insurance premiums are positive.\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"Expectimax search: compute the average score under optimal play\n",
        "Max nodes as in minimax search\n",
        "Chance nodes are like min nodes but the outcome is uncertain\n",
        "Calculate their expected utilities I.e. take weighted average (expectation) of children\n",
        "Expectiminimax\n",
        "Environment is an extra “random agent” player that moves after each min/max agent\n",
        "Each node computes the appropriate combination of its children \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"beam search\" : \" on each ply, consider only a “beam” of the n best moves (according to the evaluation function) rather than consid\u0002ering all possible moves. Unfortunately, this approach is rather dangerous because there is no guarantee that the best move will not be pruned away.\", \n",
        "\"a value function or ordinal utility function\":\" a preference ranking on states\",\n",
        "\"preference elicitation\":\"Process that involves presenting choices to the human and using the Preference elicitation observed preferences to pin down the underlying utility function\",\n",
        "\"decision theory\":\" a normative theory: it describes how a rational agent should act.\",\n",
        "\"descriptive theory,\":\" describes how actual agents—for example, humans really do act\",\n",
        "\"ambiguity aversion\":\"people elect the known probability rather than the unknown unknowns\",\n",
        "\"framing effect\":\" the exact wording of a decision problem can have a big impact on the agent’s choices\",\n",
        "\"anchoring effect\":\"People feel more comfortable making relative utility judgments rather than absolute ones.\n",
        "\"  \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "39ec8635-89e2-4f2f-99f8-00aecd47f6ca"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \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* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"The best-known category of continuous-domain CSPs is that of linear programming problems。\n",
        "The simplest type is the unary constraint, which restricts the value of a single variable.\n",
        "binary constraint relates two variables. For example, SA = NSW is a binary constraint\n",
        "Preference constraints can often be encoded as costs on individual variable assignments—for example, assigning an afternoon slot for Prof. With this formulation, CSPs with preferences can be\n",
        "solved with optimization search methods, either path-based or local. We call such a problem\n",
        "a constrained optimization problem, or COP. \"\"\"\n",
        "chapter6_2 = \"\"\"  A single variable (corresponding to a node in the CSP graph) is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\n",
        "A variable in a CSP is arc-consistent1 Arc consistency if every value in its domain satisfies the variable’s binary constraints.\n",
        "The complexity of AC-3 can be analyzed as follows. Assume a CSP with n variables,\n",
        "each with domain size at most d, and with c binary constraints (arcs). Each arc (Xk,Xi) can\n",
        "be inserted in the queue only d times because Xi has at most d values to delete. Checking\n",
        "consistency of an arc can be done in O(d^2) time, so we get O(cd^3) total worst-case time.\n",
        "Path consistency tightens the binary constraints by using implicit constraints\n",
        "that are inferred by looking at triples of variables.\n",
        "Stronger forms of propagation can be defined with the notion of k-consistency. A CSP is k\u0002consistent if, for any set of k−1 variables and for any consistent assignment to those variables,\n",
        "a consistent value can always be assigned to any kth variable.\n",
        "A CSP is strongly k-consistent if it is k-consistent and is also (k−1)-consistent, (k−2)-consistent, ... all the way down to 1-consistent. The total run time is only O(n^2d).( CSP with n nodes)\n",
        "constraint satisfaction is NP-complete in general, and any algorithm for establishing n-consistency must take time exponential in n in the worst case.\n",
        "Worse, n-consistency also requires space that is exponential in n. In practice, determining the appropriate level of consistency checking is mostly an empirical science.\n",
        "Alldiff constraints works as follows:\n",
        "if m variables are involved in the constraint, and if they have n possible distinct values alto\u0002gether, and m > n, then the constraint cannot be satisfied\n",
        "\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" strategy for SELECT-UNASSIGNED-VARIABLE:\n",
        "This intuitive idea—choosing the variable with the fewest “legal” values—is called the minimum-remaining-values (MRV) heuristic.\n",
        "Degree heuristic. It attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables.\n",
        "The least-constraining-value heuristic is effective for this. It prefers Least-constraining\u0002value the value that rules out the fewest choices for the neighboring variables in the constraint graph.\n",
        "\n",
        "forward checking. \n",
        "Whenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each unas\u0002signed variable Y that is connected to X by a constraint, delete from Y’s domain any value\n",
        "that is inconsistent with the value chosen for X.\n",
        "\n",
        "The algorithm called MAC (for Maintaining Arc Consistency) detects inconsistencies Maintaining Arc Consistency\n",
        "like this. After a variable Xi is assigned a value, the INFERENCE procedure calls AC-3, but instead of a queue of all arcs in the CSP, we start with only the arcs (Xj,Xi) for all Xj that are unassigned variables that are neighbors of Xi\n",
        ".\n",
        "conflict-directed backjumping.\n",
        "Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem.\n",
        "No-good This set of variables, along with their corresponding values, is called a no-good. We then record the no-good, either by adding a new constraint to the CSP to forbid this combination\n",
        "of assignments or by keeping a separate cache of no-goods\n",
        "\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" the run time of min-conflicts is roughly independent of problem size.\n",
        "constraint weighting \n",
        "aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step\n",
        "of the search, the algorithm chooses a variable/value pair to change that will result in the\n",
        "lowest total weight of all violated constraints. The weights are then adjusted by incrementing\n",
        "the weight of each constraint that is violated by the current assignment. This has two benefits:\n",
        "it adds topography to plateaus, making sure that it is possible to improve from the current\n",
        "state, and it also adds learning: over time the difficult constraints are assigned higher weights. \"\"\"\n",
        "chapter6_5 = \"\"\" The complexity of solving a CSP is strongly related to the structure of its constraint\n",
        "graph. Tree-structured problems can be solved in linear time. Cutset conditioning can\n",
        "reduce a general CSP to a tree-structured one and is quite efficient (requiring only lin\u0002ear memory) if a small cutset can be found. Tree decomposition techniques transform\n",
        "the CSP into a tree of subproblems and are efficient if the tree width of the constraint\n",
        "graph is small; however they need memory exponential in the tree width of the con\u0002straint graph. Combining cutset conditioning with tree decomposition can allow a better\n",
        "tradeoff of memory versus time. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\" global constraint\" : \"one involving an arbitrary number of variables (but not necessarily all variables)\",\n",
        "\"resource constraint(the Atmost constrain)\":\" detect an inconsistency simply by checking the sum of the minimum values of the current domains\" ,\n",
        "\"bounds-consistent\":\"if for every variable X, and for both the lower-bound Bounds-consistent and upper-bound values of X, there exists some value of Y that satisfies the constraint between and Y for every variable Y.\"   \n",
        ",\n",
        "\"the min-conflicts heuristic\":\"select the value that results in the minimum number of conflicts with other variables\"}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5f3d2500-dfb2-42e4-9373-fb3bec356333"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \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* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" A logic must also define the semantics, or meaning, of sentences. The semantics defines\n",
        "Truth the truth of each sentence with respect to each possible world. \"\"\"\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",
        "\"axiom\" : \"When the sentence is taken as being given without being derived from other sentences\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2fc31cf5-b9c0-41b0-9a0e-5f7744a61e68"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n 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": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "T3cm1WV542_a",
        "outputId": "1e35f8dc-8712-4aad-fced-e8d79768a61b"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \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 Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \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* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \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* **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": {}
        }
      ]
    }
  ]
}