{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of DRAFT 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": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 17,
      "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 = \"\"\" **rationality**— doing the “right thing.”<br>\n",
        "**natural language processing** -to communicate in a human language <br>\n",
        "**knowledge representation** -to store what it knows or hears <br>\n",
        "**automated reasoning** -to answer questions and draw new conclusions <br>\n",
        "**machine learning** -to adapt to new circumstances and detect and extrapolate patterns. <br>\n",
        "**total Turing test**- requires interaction with objects and people in the real world <br>\n",
        "**embodied cognition** - body and cognition are connected <br>\n",
        "**\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"**weak AI** -machines could act intellligent <br>\n",
        "**strong AI** -machines do think <br>\n",
        "Good Old-Fashioned AI (GOFAI) <br>\n",
        "**qualification problem** - difficult to capture behavior with list of logical rules <br>\n",
        " \"\"\"\n",
        "chapter27_2 = \"\"\"***conciousness: awereness of outside world and self <br>\n",
        "**qualia**- nature of experiences <br>\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"**agent** - anything that can perceive and act in an environment <br>\n",
        "**percept** - content an agent gets from senors <br>\n",
        "**percept sequence** - complete history of everything percieved <br>\n",
        "**agent function** - maps any given percept sequence to an action <br>\n",
        "**agent program** - physical implementation of agent function <br>\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"**rational agent** - anything that acts to achieve the best outcome <br>\n",
        "**consequentialism**- we evaluate an agent’s behavior by its consequences <br>\n",
        "**performance measure** - measures desireability <br>\n",
        "better to design performance measures according to what one actually wants \n",
        "to be achieved in the environment, rather than according to how one thinks the agent should behave <br>\n",
        "**Rationality depends of 4 things**: performance measure, agent's prior knowledge of environment,\n",
        "actions that the agent can perfrom, the agent's percept sequence to date <br>\n",
        "**information gathering** - doing actions in order to modify futrure precepts(exploration) <br>\n",
        "**autonomy** - relies on own percepts and learning prcoesses <br>\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" **task environments** - which are\n",
        "essentially the “problems” to which rational agents are the “solutions.” <br> \n",
        "**fully observable** - sensors give acess to complete state of enviorment <br>\n",
        "taxi driving is partically competative and cooperative <br>\n",
        "**deterministic** - next state is fully determined by current state and the next action <br>\n",
        "Most real situations are so complex that it is impossible to keep track of all the unobserved\n",
        "aspects; for practical purposes, they must be treated as nondeterministic <br>\n",
        "**stochastic** - nondeterministic but with probabilities\n",
        "**episodic** - agent preceives a precept then performs a single action. Does\n",
        "not depend on previous episode <br>\n",
        "**sequencial** - previous decisions affect next decision <br>\n",
        "**dynamic** - if the enviorment can change while agent is deliberating <br>\n",
        "**semidynamic** - if enviorment doesnt change but agents performance score does <br>\n",
        "discrete/continuous distinction applies to the state of\n",
        "the environment, to the way time is handled, and to the percepts and actions of the agent <br>\n",
        "**known** - does the agent know about the rules of the environment\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" behavior - action that is perfromed after any given seqeunce of percepts <br>\n",
        "agent = architechture + program <br>\n",
        "**simple reflex agent** - These agents select actions on the\n",
        "basis of the current percept, ignoring the rest of the percept history <br>\n",
        "**transiton model** - what each action does <br>\n",
        "**sensor model** - how the world is shown to the sensor <br>\n",
        "**model-based reflex agents** - maintain internal state to track aspects of the world that are not in the current\n",
        "percept <br>\n",
        "**model_based agent** - agent using sensor model annd transition model <br>\n",
        "Search and planning are for fuincding action sequences to achieve agent's goals <br>\n",
        "**goal based agents** - performs actions to get to goal <br>\n",
        "**utility** - the quality of being useful <br>\n",
        "**utility function** internalization of performance measure <br>\n",
        "**expected utility** - utility, on average, given the probabilities and utilities of each\n",
        "outcome (p(x)*x) <br>\n",
        "**model-free agent** - learns what action is best without learning exactly how that\n",
        "action changes the envionment <br>\n",
        "**localist representation** one-to-one mapping between concepts and memory locations\n",
        "Distributed representations are more robust against noise and\n",
        "information loss. <br>\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes\n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"rational agent\": \"anything that acts to achieve the best outcome\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "21d9be24-45f0-4702-94b9-d828afa7e99a"
      },
      "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",
        "    if \"lecture\" in section.lower() and  len(summary) > 12000:\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "    elif (len(summary) > 3000 or len(summary.split(' ')) > 500):\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": 19,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n **rationality**— doing the “right thing.”<br>\n**natural language processing** -to communicate in a human language <br>\n**knowledge representation** -to store what it knows or hears <br>\n**automated reasoning** -to answer questions and draw new conclusions <br>\n**machine learning** -to adapt to new circumstances and detect and extrapolate patterns. <br>\n**total Turing test**- requires interaction with objects and people in the real world <br>\n**embodied cognition** - body and cognition are connected <br>\n**\n\n\n## AIMA Chapter 27.1 The Limits of AI\n**weak AI** -machines could act intellligent <br>\n**strong AI** -machines do think <br>\nGood Old-Fashioned AI (GOFAI) <br>\n**qualification problem** - difficult to capture behavior with list of logical rules <br>\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n***conciousness: awereness of outside world and self <br>\n**qualia**- nature of experiences <br>\n\n## AIMA 2.1 Agents and Environments\n**agent** - anything that can perceive and act in an environment <br>\n**percept** - content an agent gets from senors <br>\n**percept sequence** - complete history of everything percieved <br>\n**agent function** - maps any given percept sequence to an action <br>\n**agent program** - physical implementation of agent function <br>\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n**rational agent** - anything that acts to achieve the best outcome <br>\n**consequentialism**- we evaluate an agent’s behavior by its consequences <br>\n**performance measure** - measures desireability <br>\nbetter to design performance measures according to what one actually wants \nto be achieved in the environment, rather than according to how one thinks the agent should behave <br>\n**Rationality depends of 4 things**: performance measure, agent's prior knowledge of environment,\nactions that the agent can perfrom, the agent's percept sequence to date <br>\n**information gathering** - doing actions in order to modify futrure precepts(exploration) <br>\n**autonomy** - relies on own percepts and learning prcoesses <br>\n\n\n## AIMA 2.3 The Nature of Environments\n **task environments** - which are\nessentially the “problems” to which rational agents are the “solutions.” <br> \n**fully observable** - sensors give acess to complete state of enviorment <br>\ntaxi driving is partically competative and cooperative <br>\n**deterministic** - next state is fully determined by current state and the next action <br>\nMost real situations are so complex that it is impossible to keep track of all the unobserved\naspects; for practical purposes, they must be treated as nondeterministic <br>\n**stochastic** - nondeterministic but with probabilities\n**episodic** - agent preceives a precept then performs a single action. Does\nnot depend on previous episode <br>\n**sequencial** - previous decisions affect next decision <br>\n**dynamic** - if the enviorment can change while agent is deliberating <br>\n**semidynamic** - if enviorment doesnt change but agents performance score does <br>\ndiscrete/continuous distinction applies to the state of\nthe environment, to the way time is handled, and to the percepts and actions of the agent <br>\n**known** - does the agent know about the rules of the environment\n\n\n## AIMA 2.4 The Structure of Agents\n behavior - action that is perfromed after any given seqeunce of percepts <br>\nagent = architechture + program <br>\n**simple reflex agent** - These agents select actions on the\nbasis of the current percept, ignoring the rest of the percept history <br>\n**transiton model** - what each action does <br>\n**sensor model** - how the world is shown to the sensor <br>\n**model-based reflex agents** - maintain internal state to track aspects of the world that are not in the current\npercept <br>\n**model_based agent** - agent using sensor model annd transition model <br>\nSearch and planning are for fuincding action sequences to achieve agent's goals <br>\n**goal based agents** - performs actions to get to goal <br>\n**utility** - the quality of being useful <br>\n**utility function** internalization of performance measure <br>\n**expected utility** - utility, on average, given the probabilities and utilities of each\noutcome (p(x)*x) <br>\n**model-free agent** - learns what action is best without learning exactly how that\naction changes the envionment <br>\n**localist representation** one-to-one mapping between concepts and memory locations\nDistributed representations are more robust against noise and\ninformation loss. <br>\n \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - anything that acts to achieve the best outcome\n* **Percept** - 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",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 208
        },
        "outputId": "499e64e0-85a5-4a80-aa5e-8a0b5bb39c99"
      },
      "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": 21,
      "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 = \"\"\" **Problem** - initial state, set of actions, transition model, <br>\n",
        "goal states, and action cost function <br>\n",
        "**state** - representation of physical configuration <br>\n",
        "**state space** - a set of possible states that the enviormenrt can be in <br>\n",
        "**state space graph** - grpah representing the enviroment of the problem <br>\n",
        "**Solution** - a path through statespace from initial to goal state <br>\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" **standardized problem** - can be given exact desciprtion (grids) <br>\n",
        "**real-world problem** - formulation is distinct (route finding problem) <br>\"\"\"\n",
        "chapter3_3 = \"\"\" **Seach algorithm** - A search algorithm takes a search problem as input and returns a solution, or an indication\n",
        "of failure <br>\n",
        "**tree search** - various paths from initla state that find path to reach goal state <br>\n",
        "**frontier** - boarder between expanded and unexpanded states <br>\n",
        "**reached** - all nodes, even if unexpanded <br>\n",
        "Search algorithms generally treat states and actions as atomic, without any internal\n",
        "structure <br>\n",
        "Search algorithms are judged on the basis of **completeness, cost optimality, time\n",
        "complexity, and space complexity** <br>\n",
        "**Frontier is represented using Queues** - \n",
        "IS-EMPTY(frontier) returns true only if there are no nodes in the frontier. <br>\n",
        "POP(frontier) removes the top node from the frontier and returns it. <br>\n",
        "TOP(frontier) returns (but does not remove) the top node of the frontier. <br>\n",
        "ADD(node, frontier) inserts node into its proper place in the queue. <br>\n",
        "**Priority queue** first pops the node with the minimum cost according to some\n",
        "evaluation function, It is used in best-first search <br>\n",
        "**FIFO queue or first-in-first-out queue** - first pops the node that was added to the queue\n",
        "first; we shall see it is used in breadth-first search. <br>\n",
        "**A LIFO queue or last-in-first-out queue (also known as a stack)** - pops first the most\n",
        "recently added node; we shall see it is used in depth-first search. <br>\n",
        "reached states can be stroed as hash table (lookup table/dict) <br>\n",
        "**repeated state**- can be caused by **cycle** aka **loopy path** <br>\n",
        "**graph search** - checks for redundant paths <br>\n",
        "<br>\n",
        "We can evaluate an algorithm’s performance in four ways:<br>\n",
        "Completeness: Is the algorithm guaranteed to find a solution when there is one? <br>\n",
        "Optimality: Does the strategy find the optimal solution? <br>\n",
        "Time complexity: How long does it take to find a solution? <br>\n",
        "Space complexity: How much memory is needed to perform the search? <br><br>\n",
        "**Complexity is expressed in terms of three quantities:** <br>\n",
        "b, the branching factor or maximum number of successors of any node <br>\n",
        "d, the depth of the shallowest goal node \n",
        "(i.e., the number of steps along the path from the root) <br>\n",
        "m, the maximum length of any path in the state space. <br><br>\n",
        "To be **complete**, a search algorithm must be systematic in the way it explores an infinite\n",
        "state space <br>\n",
        "**Time** is often measured in terms of the number of nodes generated during the \n",
        "search, and space in terms of the maximum number of nodes stored in memory. <br>\n",
        "\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\" **Uninformed search** methods have access only to the problem definition. Algorithms differ based on which\n",
        "node they expand first: <br> <br>\n",
        "**Breath-first search** (good when all actions have the same cost) <br>\n",
        "simple strategy where the root node is expanded first,\n",
        " then all the successors of the root node are expanded next, then their successors, and so on.\n",
        "\n",
        "In general, all the nodes are expanded at a given depth in the search tree before \n",
        "any nodes at the next level are expanded. <br> <br>\n",
        "Complete? Yes (if b is finite) <br>\n",
        "Time? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1) <br>\n",
        "Space? O(bd+1) (keeps every node in memory) <br>\n",
        "Optimal? Yes (if cost = 1 per step) <br> <br>\n",
        "Space is a bigger problem (more than time)<br><br>\n",
        "\n",
        "**Uniform-cost search** <br>\n",
        "Uniform-cost search expands the node n with the lowest \n",
        "path cost g(n). This is done by storing the frontier as a priority queue ordered by g: <br>\n",
        "Complete? Yes, if step cost ≥ ε <br>\n",
        "Time? O(b1+ceiling(C*/ ε)) where C* is the cost of the optimal solution <br>\n",
        "Space? O(b1+ceiling(C*/ ε)) <br>\n",
        "Optimal? Yes – nodes expanded in increasing order of g(n) <br><br>\n",
        "\n",
        "**Depth-first search** <br>\n",
        "Depth-first search always expands the deepest node in \n",
        "the current frontier of the search tree: <br>\n",
        "Complete? No: fails in infinite-depth spaces, spaces with loops <br>\n",
        "Modify to avoid repeated states along path <br>\n",
        "complete in finite spaces <br>\n",
        "Time? O(bm): terrible if m is much larger than d,\n",
        "but if solutions are dense, may be much faster than breadth-first <br>\n",
        "Space? O(bm), i.e., linear space! <br>\n",
        "Optimal? No <br> <br>\n",
        "\n",
        "**Depth-limited search** <br>\n",
        "The failure of depth-first search in infinite state spaces can be \n",
        "fixed by supplying depth-first search with a predetermined depth limit l. \n",
        "(i.e., nodes at depth l have no successors)\n",
        "*note: not complete if goal is below depth l <br> <br>\n",
        "\n",
        "**Iterative deepening depth-first search** <br>\n",
        "General strategy, often used in combination with depth-first tree search, \n",
        "that finds the best depth limit. It does this by gradually increasing the \n",
        "limit—first 0, then 1, then 2, and so on—until a goal is found <br>\n",
        "Complete? Yes <br>\n",
        "Time? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd) <br>\n",
        "Space? O(bd) <br>\n",
        "Optimal? Yes, if step cost = 1 <br>\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",
        "}\n",
        "\n"
      ],
      "execution_count": 22,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "0ec35672-244a-41e0-9892-b147da10f90b"
      },
      "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": 23,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n **Problem** - initial state, set of actions, transition model, <br>\ngoal states, and action cost function <br>\n**state** - representation of physical configuration <br>\n**state space** - a set of possible states that the enviormenrt can be in <br>\n**state space graph** - grpah representing the enviroment of the problem <br>\n**Solution** - a path through statespace from initial to goal state <br>\n\n\n## AIMA Chapter 3.2 Example Problems\n **standardized problem** - can be given exact desciprtion (grids) <br>\n**real-world problem** - formulation is distinct (route finding problem) <br>\n\n## AIMA Chapter 3.3 Search Algorithms\n **Seach algorithm** - A search algorithm takes a search problem as input and returns a solution, or an indication\nof failure <br>\n**tree search** - various paths from initla state that find path to reach goal state <br>\n**frontier** - boarder between expanded and unexpanded states <br>\n**reached** - all nodes, even if unexpanded <br>\nSearch algorithms generally treat states and actions as atomic, without any internal\nstructure <br>\nSearch algorithms are judged on the basis of **completeness, cost optimality, time\ncomplexity, and space complexity** <br>\n**Frontier is represented using Queues** - \nIS-EMPTY(frontier) returns true only if there are no nodes in the frontier. <br>\nPOP(frontier) removes the top node from the frontier and returns it. <br>\nTOP(frontier) returns (but does not remove) the top node of the frontier. <br>\nADD(node, frontier) inserts node into its proper place in the queue. <br>\n**Priority queue** first pops the node with the minimum cost according to some\nevaluation function, It is used in best-first search <br>\n**FIFO queue or first-in-first-out queue** - first pops the node that was added to the queue\nfirst; we shall see it is used in breadth-first search. <br>\n**A LIFO queue or last-in-first-out queue (also known as a stack)** - pops first the most\nrecently added node; we shall see it is used in depth-first search. <br>\nreached states can be stroed as hash table (lookup table/dict) <br>\n**repeated state**- can be caused by **cycle** aka **loopy path** <br>\n**graph search** - checks for redundant paths <br>\n<br>\nWe can evaluate an algorithm’s performance in four ways:<br>\nCompleteness: Is the algorithm guaranteed to find a solution when there is one? <br>\nOptimality: Does the strategy find the optimal solution? <br>\nTime complexity: How long does it take to find a solution? <br>\nSpace complexity: How much memory is needed to perform the search? <br><br>\n**Complexity is expressed in terms of three quantities:** <br>\nb, the branching factor or maximum number of successors of any node <br>\nd, the depth of the shallowest goal node \n(i.e., the number of steps along the path from the root) <br>\nm, the maximum length of any path in the state space. <br><br>\nTo be **complete**, a search algorithm must be systematic in the way it explores an infinite\nstate space <br>\n**Time** is often measured in terms of the number of nodes generated during the \nsearch, and space in terms of the maximum number of nodes stored in memory. <br>\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n **Uninformed search** methods have access only to the problem definition. Algorithms differ based on which\nnode they expand first: <br> <br>\n**Breath-first search** (good when all actions have the same cost) <br>\nsimple strategy where the root node is expanded first,\n then all the successors of the root node are expanded next, then their successors, and so on.\n\nIn general, all the nodes are expanded at a given depth in the search tree before \nany nodes at the next level are expanded. <br> <br>\nComplete? Yes (if b is finite) <br>\nTime? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1) <br>\nSpace? O(bd+1) (keeps every node in memory) <br>\nOptimal? Yes (if cost = 1 per step) <br> <br>\nSpace is a bigger problem (more than time)<br><br>\n\n**Uniform-cost search** <br>\nUniform-cost search expands the node n with the lowest \npath cost g(n). This is done by storing the frontier as a priority queue ordered by g: <br>\nComplete? Yes, if step cost ≥ ε <br>\nTime? O(b1+ceiling(C*/ ε)) where C* is the cost of the optimal solution <br>\nSpace? O(b1+ceiling(C*/ ε)) <br>\nOptimal? Yes – nodes expanded in increasing order of g(n) <br><br>\n\n**Depth-first search** <br>\nDepth-first search always expands the deepest node in \nthe current frontier of the search tree: <br>\nComplete? No: fails in infinite-depth spaces, spaces with loops <br>\nModify to avoid repeated states along path <br>\ncomplete in finite spaces <br>\nTime? O(bm): terrible if m is much larger than d,\nbut if solutions are dense, may be much faster than breadth-first <br>\nSpace? O(bm), i.e., linear space! <br>\nOptimal? No <br> <br>\n\n**Depth-limited search** <br>\nThe failure of depth-first search in infinite state spaces can be \nfixed by supplying depth-first search with a predetermined depth limit l. \n(i.e., nodes at depth l have no successors)\n*note: not complete if goal is below depth l <br> <br>\n\n**Iterative deepening depth-first search** <br>\nGeneral strategy, often used in combination with depth-first tree search, \nthat finds the best depth limit. It does this by gradually increasing the \nlimit—first 0, then 1, then 2, and so on—until a goal is found <br>\nComplete? Yes <br>\nTime? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd) <br>\nSpace? O(bd) <br>\nOptimal? Yes, if step cost = 1 <br>\n\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 = \"\"\"**Informed search** methods have access to a heuristic function that estimates the\n",
        "cost of a solution from They may have access to additional information such as\n",
        "pattern databases with solution costs <br><br>\n",
        "**greedy best-first search** <br>\n",
        "Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly <br>\n",
        "It evaluates nodes by using just the heuristic function; that is, f(n) = h(n) <br>\n",
        "Complete? No – can get stuck in loops\n",
        "Time? O(bm), but a good heuristic can give dramatic improvement\n",
        "Space? O(bm) -- keeps all nodes in memory\n",
        "Optimal? No <br><br>\n",
        "\n",
        "**A* search** (main issue is memory) <br>\n",
        "Evaluates nodes by combining g(n), the cost to reach the node, and h(n), \n",
        "the cost to get from the node to the goal: <br> <br>\n",
        "\n",
        "f(n) = g(n) + h(n) <br>\n",
        "If h(n) is admissible, A* using TREE-SEARCH is optimal <br>\n",
        "An admissible heuristic is one that never overestimates the cost to reach the goal <br>\n",
        "A heuristic is consistent if for every node n, every successor n' of n is generated by any action a <br>\n",
        "h(n) ≤ c(n,a,n') + h(n') <br>\n",
        "if h is consitent: <br>\n",
        "f(n') \t= g(n') + h(n') <br>\n",
        "      \t= g(n) + c(n,a,n') + h(n') <br>\n",
        "      \t≥ g(n) + h(n) <br>\n",
        "      \t= f(n) <br><br>\n",
        "Every consistent heuristic is admissible (but not vice versa) <br> <br>\n",
        "\n",
        "Complete? Yes (unless there are infinitely many nodes with f ≤ f(G)) <br>\n",
        "Time? Exponential <br>\n",
        "Space? Keeps all nodes in memory <br>\n",
        "Optimal? Yes if h is admissable <br><br>\n",
        "**BIDIRECTIONAL A* SEARCH** is sometimes more efficient than A* itself. <br>\n",
        "\n",
        "monotonic: the path cost always\n",
        "increases as you go along a path, because action costs are always positive. <br><br>\n",
        "\n",
        "**Memory bounded searches** <br>\n",
        "\n",
        "**Iterative-deepening A star** <br>\n",
        "The simplest way to reduce memory requirements for A* is to adapt the idea of \n",
        "iterative deepening to the heuristic search context, resulting in the\n",
        "iterative-deepening A* (IDA* ) algorithm. <br> <br>\n",
        "\n",
        "The main difference between IDA* and standard iterative deepening is that the \n",
        "cutoff used is the f -cost (g + h) rather than the depth; \n",
        "at each iteration, the cutoff value is the smallest f -cost of any node that \n",
        "exceeded the cutoff on the previous iteration. <br><br>\n",
        "\n",
        "**RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*)** are\n",
        "robust, optimal search algorithms that use limited amounts of memory; given enough\n",
        "time, they can solve problems for which A* runs out of memory <br><br>\n",
        "\n",
        "**beam search** - limits the size of the frontier. The easiest approach is to keep only the nodes\n",
        "with the best -scores, discarding any other expanded nodes. Incomplete and suboptimal <br><br>\n",
        "\n",
        "**WEIGHTED A star** search focuses the search towards a goal, expanding fewer nodes, but\n",
        "sacrificing optimality.<br>\n",
        "\n",
        " \"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "One way to characterize the quality of a heuristic is the effective branching factor b*. \n",
        "If the total number of nodes generated by A* for a particular problem is N and \n",
        "the solution depth is d, then b* is the branching factor that a uniform tree of \n",
        "depth d would have to have in order to contain N + 1 nodes. Thus, <br> <br>\n",
        "\n",
        "N + 1 = 1 + b* + (b*)2 + · · · + (b*)d <br><br>\n",
        "\n",
        "For example, if A* finds a solution at depth 5 using 52 nodes, then the \n",
        "effective branching factor is 1.92 <br> <br>\n",
        "\n",
        "To test the heuristic functions h1 and h2, we generated 1200 random problems \n",
        "with solution lengths from 2 to 24 (100 for each even number) and solved them \n",
        "with iterative deepening search and with A* tree search using both h1 and h2. \n",
        "The results suggest that h2 is better than h1, and is far better than using \n",
        "iterative deepening search. <br><br>\n",
        "\n",
        "One might ask whether h2 is always better than h1. The answer is “Essentially, yes.” \n",
        "We thus say that h2 dominates h1.<br><br>\n",
        "\n",
        "**Relaxed Problems**<br>\n",
        "A problem with fewer restrictions on the actions is called a **relaxed problem** <br>\n",
        "The cost of an optimal solution to a relaxed problem is an admissible heuristic \n",
        "for the original problem <br>\n",
        "If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, \n",
        "then h1(n) gives the shortest solution <br>\n",
        "If the rules are relaxed so that a tile can move to any adjacent square, then h2(n) \n",
        "gives the shortest solution <br><br>\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"shortcuts\":\"artificial edges in the graph that define an optimal multi-action path\",    \n",
        "\"pattern databases\": \"store these exact solution costs for every possible subproblem instance\",\n",
        "\"disjoint pattern databases\": \"combinging solution from subproblems that don't overlap\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "969a93ef-af4b-4fca-bd93-e162a98d1a20"
      },
      "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))"
      ],
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n**Informed search** methods have access to a heuristic function that estimates the\ncost of a solution from They may have access to additional information such as\npattern databases with solution costs <br><br>\n**greedy best-first search** <br>\nGreedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly <br>\nIt evaluates nodes by using just the heuristic function; that is, f(n) = h(n) <br>\nComplete? No – can get stuck in loops\nTime? O(bm), but a good heuristic can give dramatic improvement\nSpace? O(bm) -- keeps all nodes in memory\nOptimal? No <br><br>\n\n**A* search** (main issue is memory) <br>\nEvaluates nodes by combining g(n), the cost to reach the node, and h(n), \nthe cost to get from the node to the goal: <br> <br>\n\nf(n) = g(n) + h(n) <br>\nIf h(n) is admissible, A* using TREE-SEARCH is optimal <br>\nAn admissible heuristic is one that never overestimates the cost to reach the goal <br>\nA heuristic is consistent if for every node n, every successor n' of n is generated by any action a <br>\nh(n) ≤ c(n,a,n') + h(n') <br>\nif h is consitent: <br>\nf(n') \t= g(n') + h(n') <br>\n      \t= g(n) + c(n,a,n') + h(n') <br>\n      \t≥ g(n) + h(n) <br>\n      \t= f(n) <br><br>\nEvery consistent heuristic is admissible (but not vice versa) <br> <br>\n\nComplete? Yes (unless there are infinitely many nodes with f ≤ f(G)) <br>\nTime? Exponential <br>\nSpace? Keeps all nodes in memory <br>\nOptimal? Yes if h is admissable <br><br>\n**BIDIRECTIONAL A* SEARCH** is sometimes more efficient than A* itself. <br>\n\nmonotonic: the path cost always\nincreases as you go along a path, because action costs are always positive. <br><br>\n\n**Memory bounded searches** <br>\n\n**Iterative-deepening A star** <br>\nThe simplest way to reduce memory requirements for A* is to adapt the idea of \niterative deepening to the heuristic search context, resulting in the\niterative-deepening A* (IDA* ) algorithm. <br> <br>\n\nThe main difference between IDA* and standard iterative deepening is that the \ncutoff used is the f -cost (g + h) rather than the depth; \nat each iteration, the cutoff value is the smallest f -cost of any node that \nexceeded the cutoff on the previous iteration. <br><br>\n\n**RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*)** are\nrobust, optimal search algorithms that use limited amounts of memory; given enough\ntime, they can solve problems for which A* runs out of memory <br><br>\n\n**beam search** - limits the size of the frontier. The easiest approach is to keep only the nodes\nwith the best -scores, discarding any other expanded nodes. Incomplete and suboptimal <br><br>\n\n**WEIGHTED A star** search focuses the search towards a goal, expanding fewer nodes, but\nsacrificing optimality.<br>\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n\nOne way to characterize the quality of a heuristic is the effective branching factor b*. \nIf the total number of nodes generated by A* for a particular problem is N and \nthe solution depth is d, then b* is the branching factor that a uniform tree of \ndepth d would have to have in order to contain N + 1 nodes. Thus, <br> <br>\n\nN + 1 = 1 + b* + (b*)2 + · · · + (b*)d <br><br>\n\nFor example, if A* finds a solution at depth 5 using 52 nodes, then the \neffective branching factor is 1.92 <br> <br>\n\nTo test the heuristic functions h1 and h2, we generated 1200 random problems \nwith solution lengths from 2 to 24 (100 for each even number) and solved them \nwith iterative deepening search and with A* tree search using both h1 and h2. \nThe results suggest that h2 is better than h1, and is far better than using \niterative deepening search. <br><br>\n\nOne might ask whether h2 is always better than h1. The answer is “Essentially, yes.” \nWe thus say that h2 dominates h1.<br><br>\n\n**Relaxed Problems**<br>\nA problem with fewer restrictions on the actions is called a **relaxed problem** <br>\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic \nfor the original problem <br>\nIf the rules of the 8-puzzle are relaxed so that a tile can move anywhere, \nthen h1(n) gives the shortest solution <br>\nIf the rules are relaxed so that a tile can move to any adjacent square, then h2(n) \ngives the shortest solution <br><br>\n\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Shortcuts** - artificial edges in the graph that define an optimal multi-action path\n* **Pattern databases** - store these exact solution costs for every possible subproblem instance\n* **Disjoint pattern databases** - combinging solution from subproblems that don't overlap\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 = \"\"\" Minimax search: move to position with highest minimax value aka best achievable payoff against best play <br> \n",
        "The minimax algorithm performs a complete depth-first exploration of the game tree.<br><br>\n",
        "\n",
        "A reasonable opponent will always chose the the lowest score. Our agent will then \n",
        "choose the higest of those scores. The root then will reflect the highest possible \n",
        "score from the current depth. <br><br>\n",
        "\n",
        "Complete? Yes (if tree is finite) <br>\n",
        "Optimal? Yes (against an optimal opponent) <br>\n",
        "Time complexity? O(bm) <br>\n",
        "Space complexity? O(bm) (depth-first exploration) <br>\n",
        "For chess, b ≈ 35, m ≈ 100 for \"reasonable\" games <br><br>\n",
        "\n",
        "**Alpha-beta pruning** <br>\n",
        "The number of game states is exponential in the depth of the tree, pruning is to \n",
        "reduce the exponent in half<br>\n",
        "Pruning does not affect final result <br>\n",
        "Goods moves ordered first improves effectivlenss of pruning <br>\n",
        "Perfect ordering time complexity is O(b^m/2), doubles depth of search <br>\n",
        "alpha = \"at least\", beta = \"at most\" <br>\n",
        "The number of game states is exponential in the depth of the tree <br>\n",
        "If v is worse than α, max will avoid it prune that branch <br><br>\n",
        "\"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\" **Move ordering** <br>\n",
        " alpha–beta can solve a tree roughly twice as deep as minimax in the same amount of time <br>\n",
        " Adding dynamic move-ordering schemes, such as trying first the moves that were \n",
        " found to be best in the past, brings us quite close to the theoretical limit <br>\n",
        " The past could be the previous move—often the same threats remain—or it could come \n",
        " from previous exploration of the current move <br>\n",
        " One way to gain information from the current move is with iterative deepening search <br>\n",
        " Type A- wide but shallow, type B- ignores bad moves, deep but narrow <br>\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"An evaluation function returns an estimate of the expected utility \n",
        "of the game from a given position, just as the heuristic functions return an estimate of the distance to the goal<br><br>\n",
        "It should be clear that the performance of a game-playing program depends strongly on the quality of its evaluation function<br><br>\n",
        "In other words, we replace the UTILITY function with EVAL, which estimates a state’s\n",
        "utility. We also replace the terminal test by a **cutoff test**, which must return true for terminal\n",
        "states, but is otherwise free to decide when to cut off the search, based on the search depth\n",
        "and any property of the state that it chooses to consider <br><br>\n",
        "\n",
        "Good evaluation function:<br>\n",
        "1. should order terminal states in the same way as the utility function:states that \n",
        "are wins must evaluate better than draws, which in turn must be better than losses.<br>\n",
        "2. The computation must not take too long! <br>\n",
        "3. For nonterminal states, the evaluation function should be strongly correlated \n",
        "with the actual chances of winning <br>\n",
        "\n",
        "**cutting off search**<br>\n",
        "The next step is to modify A LPHA-BETA-SEARCH so that it will call the heuristic E VAL function when it is appropriate to cut off the search<br>\n",
        "MinimaxCutoff is identical to MinimaxValue except: <br>\n",
        "Terminal? is replaced by Cutoff? <br>\n",
        "Utility is replaced by Eval<br><br>\n",
        "For nonquiescent positions the IS-CUTOFF returns false, and the\n",
        "search continues until quiescent positions are reached <br><br>\n",
        "\n",
        "**forward pruning**<br>\n",
        "Forward pruning: Some moves at a given node are pruned immediately without further consideration<br>\n",
        "PROBCUT also prunes nodes that are probably outside the (alpha, beta) window based on experience <br><br>\n",
        "Computes probability by doing a shallow search to compute backed-up value v of a \n",
        "node, then using past experience to estimate how likely it is that a score of \n",
        "v at depth d in the tree would be outside (alpha, beta)<br><br>\n",
        "\n",
        "**search vs lookup**<br>\n",
        "Near the end of the game there are again fewer possible positions, and thus more \n",
        "chance to do lookup. But here it is the computer that has the expertise: \n",
        "computer analysis of endgames goes far beyond anything achieved by humans <br>\n",
        "\n",
        "A computer, can completely solve the endgame by producing a **policy**, which is \n",
        "a mapping from every possible state to the best move in that state. Then we can \n",
        "just look up the best move rather than recompute it again<br><br>\n",
        "\n",
        "The table is constructed by **retrograde** minimax search<br>\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"**Stochastic games** bring us closer to the unpredictability of \n",
        "real life by including a random element, such as the throwing of dice<br><br>\n",
        "must include change nodes (in circles) <br><br>\n",
        "\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<br><br>\n",
        "\n",
        "The evaluation function must return values that are a\n",
        "positive linear transformation of the probability of winning (or of the expected utility, for\n",
        "games that have outcomes other than win/lose) <br><br>\n",
        "\n",
        "It may have occurred to you that something like alpha–beta pruning could be applied to\n",
        "game trees with chance nodes. It turns out that it can<br>\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"zero-sum\": \"what is good for one player is just as bad for the other: there is no “win-win” outcome\",\n",
        "\"killer moves\" : \"best moves\",\n",
        "\"transpositions\":\"different permutations of the move sequence that end up in the same positions\",\n",
        "\"transposition table\": \"that caches the heuristic value of states\",\n",
        "\"weighted linear function\": \"feature times weight added for all features in state (0-1)\",\n",
        "\"quiescent\": \"that is, positions in which there is no pending move (such as a capturing the queen) that would wildly swing the evaluation\" ,\n",
        "\"horizon effect\":\"program is facing an opponent’s move that causes serious damage and is ultimately unavoidable, but can be delayed\",\n",
        " \"singular extensions\": \"moves that are “clearly better” than all other moves in a given position, used to mitigate horizontal effect\",\n",
        " \"late move reduction\": \"works under the assumption that move ordering has been done well\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6e1f761e-96c1-428f-ceb1-428d4d17538f"
      },
      "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": 27,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'quiescent' is too long!\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Minimax search: move to position with highest minimax value aka best achievable payoff against best play <br> \nThe minimax algorithm performs a complete depth-first exploration of the game tree.<br><br>\n\nA reasonable opponent will always chose the the lowest score. Our agent will then \nchoose the higest of those scores. The root then will reflect the highest possible \nscore from the current depth. <br><br>\n\nComplete? Yes (if tree is finite) <br>\nOptimal? Yes (against an optimal opponent) <br>\nTime complexity? O(bm) <br>\nSpace complexity? O(bm) (depth-first exploration) <br>\nFor chess, b ≈ 35, m ≈ 100 for \"reasonable\" games <br><br>\n\n**Alpha-beta pruning** <br>\nThe number of game states is exponential in the depth of the tree, pruning is to \nreduce the exponent in half<br>\nPruning does not affect final result <br>\nGoods moves ordered first improves effectivlenss of pruning <br>\nPerfect ordering time complexity is O(b^m/2), doubles depth of search <br>\nalpha = \"at least\", beta = \"at most\" <br>\nThe number of game states is exponential in the depth of the tree <br>\nIf v is worse than α, max will avoid it prune that branch <br><br>\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n **Move ordering** <br>\n alpha–beta can solve a tree roughly twice as deep as minimax in the same amount of time <br>\n Adding dynamic move-ordering schemes, such as trying first the moves that were \n found to be best in the past, brings us quite close to the theoretical limit <br>\n The past could be the previous move—often the same threats remain—or it could come \n from previous exploration of the current move <br>\n One way to gain information from the current move is with iterative deepening search <br>\n Type A- wide but shallow, type B- ignores bad moves, deep but narrow <br>\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nAn evaluation function returns an estimate of the expected utility \nof the game from a given position, just as the heuristic functions return an estimate of the distance to the goal<br><br>\nIt should be clear that the performance of a game-playing program depends strongly on the quality of its evaluation function<br><br>\nIn other words, we replace the UTILITY function with EVAL, which estimates a state’s\nutility. We also replace the terminal test by a **cutoff test**, which must return true for terminal\nstates, but is otherwise free to decide when to cut off the search, based on the search depth\nand any property of the state that it chooses to consider <br><br>\n\nGood evaluation function:<br>\n1. should order terminal states in the same way as the utility function:states that \nare wins must evaluate better than draws, which in turn must be better than losses.<br>\n2. The computation must not take too long! <br>\n3. For nonterminal states, the evaluation function should be strongly correlated \nwith the actual chances of winning <br>\n\n**cutting off search**<br>\nThe next step is to modify A LPHA-BETA-SEARCH so that it will call the heuristic E VAL function when it is appropriate to cut off the search<br>\nMinimaxCutoff is identical to MinimaxValue except: <br>\nTerminal? is replaced by Cutoff? <br>\nUtility is replaced by Eval<br><br>\nFor nonquiescent positions the IS-CUTOFF returns false, and the\nsearch continues until quiescent positions are reached <br><br>\n\n**forward pruning**<br>\nForward pruning: Some moves at a given node are pruned immediately without further consideration<br>\nPROBCUT also prunes nodes that are probably outside the (alpha, beta) window based on experience <br><br>\nComputes probability by doing a shallow search to compute backed-up value v of a \nnode, then using past experience to estimate how likely it is that a score of \nv at depth d in the tree would be outside (alpha, beta)<br><br>\n\n**search vs lookup**<br>\nNear the end of the game there are again fewer possible positions, and thus more \nchance to do lookup. But here it is the computer that has the expertise: \ncomputer analysis of endgames goes far beyond anything achieved by humans <br>\n\nA computer, can completely solve the endgame by producing a **policy**, which is \na mapping from every possible state to the best move in that state. Then we can \njust look up the best move rather than recompute it again<br><br>\n\nThe table is constructed by **retrograde** minimax search<br>\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n**Stochastic games** bring us closer to the unpredictability of \nreal life by including a random element, such as the throwing of dice<br><br>\nmust include change nodes (in circles) <br><br>\n\nGames of chance can be handled by expectiminimax, an extension to the minimax\nalgorithm that evaluates a chance node by taking the average utility of all its children,\nweighted by the probability of each child<br><br>\n\nThe evaluation function must return values that are a\npositive linear transformation of the probability of winning (or of the expected utility, for\ngames that have outcomes other than win/lose) <br><br>\n\nIt may have occurred to you that something like alpha–beta pruning could be applied to\ngame trees with chance nodes. It turns out that it can<br>\n\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* **Zero-sum** - what is good for one player is just as bad for the other: there is no “win-win” outcome\n* **Killer moves** - best moves\n* **Transpositions** - different permutations of the move sequence that end up in the same positions\n* **Transposition table** - that caches the heuristic value of states\n* **Weighted linear function** - feature times weight added for all features in state (0-1)\n* **Quiescent** - that is, positions in which there is no pending move (such as a capturing the queen) that would wildly swing the evaluation\n* **Horizon effect** - program is facing an opponent’s move that causes serious damage and is ultimately unavoidable, but can be delayed\n* **Singular extensions** - moves that are “clearly better” than all other moves in a given position, used to mitigate horizontal effect\n* **Late move reduction** - works under the assumption that move ordering has been done well\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 = \"\"\" CSPs deal with **assignments** of values to variables. An assignment\n",
        "that does not violate any constraints is called a **consistent** or legal assignment. A **complete\n",
        "assignment** is one in which every variable is assigned a value, and a **solution** to a CSP is a\n",
        "consistent, complete assignment. A **partial assignment** is one that leaves some variables\n",
        "unassigned, and a **partial solution** is a partial assignment that is consistent\n",
        "visualize a CSP as a constraint graph<br><br>\n",
        "\n",
        "The simplest kind of CSP involves variables that have discrete, finite domains<br>\n",
        "A discrete domain can be infinite, such as the set of integers or strings<br><br>\n",
        "\n",
        "It can be shown that no algorithm exists for solving general nonlinear \n",
        "constraints on integer variables—the problem is undecidable<br><br>\n",
        "\n",
        "Global constraint need not involve all the variables in a problem<br>\n",
        "\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\"The minimum-remaining-values and degree heuristics are domain-independent\n",
        "methods for deciding which variable to choose next in a backtracking search <br>\n",
        "The leastconstraining-value heuristic helps in deciding which value to try first for a given\n",
        "variable <br>\n",
        "Backtracking occurs when no legal assignment can be found for a variable.\n",
        "Conflict-directed backjumping backtracks directly to the source of the problem <br>\n",
        "Constraint learning records the conflicts as they are encountered during search in order\n",
        "to avoid the same conflict later in the search <br><br>\n",
        "Local search using the min-conflicts heuristic has also been applied to constraint\n",
        "satisfaction problems with great success<br>\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" Local search using the min-conflicts heuristic has also been applied to constraint\n",
        "satisfaction problems with great success <br> \"\"\"\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 linear\n",
        "memory) if a small cutset can be found. <br><br>\n",
        "Tree decomposition techniques transform the\n",
        "CSP into a tree of subproblems and are efficient if the tree width of the constraint graph\n",
        "is small, but they need memory exponential in the tree width of the constraint\n",
        "graph. Combining cutset conditioning with tree decomposition can allow a better\n",
        "tradeoff of memory versus time<br> \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\" binary constraint\": \"relates two variables\",    \n",
        "\" global constraint\": \"A constraint involving an arbitrary number of variables \"\n",
        "}\n"
      ],
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 891
        },
        "outputId": "e9636d6d-6fda-4a6a-9b5d-98594652d882"
      },
      "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": 29,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSPs deal with **assignments** of values to variables. An assignment\nthat does not violate any constraints is called a **consistent** or legal assignment. A **complete\nassignment** is one in which every variable is assigned a value, and a **solution** to a CSP is a\nconsistent, complete assignment. A **partial assignment** is one that leaves some variables\nunassigned, and a **partial solution** is a partial assignment that is consistent\nvisualize a CSP as a constraint graph<br><br>\n\nThe simplest kind of CSP involves variables that have discrete, finite domains<br>\nA discrete domain can be infinite, such as the set of integers or strings<br><br>\n\nIt can be shown that no algorithm exists for solving general nonlinear \nconstraints on integer variables—the problem is undecidable<br><br>\n\nGlobal constraint need not involve all the variables in a problem<br>\n\n\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\nThe minimum-remaining-values and degree heuristics are domain-independent\nmethods for deciding which variable to choose next in a backtracking search <br>\nThe leastconstraining-value heuristic helps in deciding which value to try first for a given\nvariable <br>\nBacktracking occurs when no legal assignment can be found for a variable.\nConflict-directed backjumping backtracks directly to the source of the problem <br>\nConstraint learning records the conflicts as they are encountered during search in order\nto avoid the same conflict later in the search <br><br>\nLocal search using the min-conflicts heuristic has also been applied to constraint\nsatisfaction problems with great success<br>\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search using the min-conflicts heuristic has also been applied to constraint\nsatisfaction problems with great success <br> \n\n## AIMA Chapter 6.5 The Structure of Problems\nThe complexity of solving a CSP is strongly related to the structure of its constraint\ngraph. Tree-structured problems can be solved in linear time. Cutset conditioning can\nreduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\nmemory) if a small cutset can be found. <br><br>\nTree decomposition techniques transform the\nCSP into a tree of subproblems and are efficient if the tree width of the constraint graph\nis small, but they need memory exponential in the tree width of the constraint\ngraph. Combining cutset conditioning with tree decomposition can allow a better\ntradeoff of memory versus time<br> \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* ** binary constraint** - relates two variables\n* ** global constraint** - A constraint involving an arbitrary number of variables \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 = \"\"\" Intelligent agents need knowledge about the world in order to reach good decisions <br>\n",
        "Knowledge is contained in agents in the form of **sentences** in a **knowledge\n",
        "representation language** that are stored in a **knowledge base** <br><br>\n",
        "\n",
        "A knowledge-based agent is composed of a knowledge base and an inference\n",
        "mechanism. It operates by storing sentences about the world in its knowledge base,\n",
        "using the inference mechanism to infer new sentences, and using these sentences to\n",
        "decide what action to take<br><br>\n",
        "\n",
        "A representation language is defined by its **syntax**, which specifies the structure of\n",
        "sentences, and its **semantics**, which defines the truth of each sentence in each possible\n",
        "world or model <br><br>\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" The relationship of **entailment** between sentences is crucial to our understanding of\n",
        "reasoning. A sentence alpha entails another sentence beta if beta is true in all worlds where alpha is\n",
        "true. Equivalent definitions include the **validity** of the sentence a -> b and the\n",
        "unsatisfiability of the sentence a^-|B\n",
        "\n",
        "**Inference** - process of deriving new sentences from old ones. Sound inference\n",
        "algorithms derive only sentences that are entailed; complete algorithms derive all\n",
        "sentences that are entailed <br><br>\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\" **Propositional logic**- simple language consisting of proposition symbols and logical\n",
        "connectives. It can handle propositions that are known to be true, known to be false, or\n",
        "completely unknown<br><br>\n",
        "\n",
        "**Inference rules** - patterns of sound inference that can be used to find proofs. The\n",
        "**resolution** rule yields a complete inference algorithm for knowledge bases that are\n",
        "expressed in **conjunctive normal form**. **Forward chaining** and **backward chaining** are\n",
        "very natural reasoning algorithms for knowledge bases in **Horn form**<br><br>\n",
        "\n",
        "**Local search** methods such as WALKSAT can be used to find solutions. Sound but not complete <br><br>\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\" Logical **state estimation** involves maintaining a logical sentence that describes the set of\n",
        "possible states consistent with the observation history. Each update step requires\n",
        "inference using the transition model of the environment, which is built from \n",
        "**successor state axioms** that specify how each **fluent** changes <br><br>\n",
        "\n",
        "Decisions within a logical agent can be made by SAT solving--finding possible models\n",
        "specifying future action sequences that reach the goal. Only works for\n",
        "fully observable or sensorless environments <br>\n",
        "\n",
        " \"\"\"\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"
      ],
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 959
        },
        "outputId": "ec46a016-8a56-434b-edea-590ed5a6b6dc"
      },
      "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": 31,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Intelligent agents need knowledge about the world in order to reach good decisions <br>\nKnowledge is contained in agents in the form of **sentences** in a **knowledge\nrepresentation language** that are stored in a **knowledge base** <br><br>\n\nA knowledge-based agent is composed of a knowledge base and an inference\nmechanism. It operates by storing sentences about the world in its knowledge base,\nusing the inference mechanism to infer new sentences, and using these sentences to\ndecide what action to take<br><br>\n\nA representation language is defined by its **syntax**, which specifies the structure of\nsentences, and its **semantics**, which defines the truth of each sentence in each possible\nworld or model <br><br>\n\n\n## AIMA Chapter 7.2 The Wumpus World\n The relationship of **entailment** between sentences is crucial to our understanding of\nreasoning. A sentence alpha entails another sentence beta if beta is true in all worlds where alpha is\ntrue. Equivalent definitions include the **validity** of the sentence a -> b and the\nunsatisfiability of the sentence a^-|B\n\n**Inference** - process of deriving new sentences from old ones. Sound inference\nalgorithms derive only sentences that are entailed; complete algorithms derive all\nsentences that are entailed <br><br>\n\n\n## AIMA Chapter 7.3 Logic\n **Propositional logic**- simple language consisting of proposition symbols and logical\nconnectives. It can handle propositions that are known to be true, known to be false, or\ncompletely unknown<br><br>\n\n**Inference rules** - patterns of sound inference that can be used to find proofs. The\n**resolution** rule yields a complete inference algorithm for knowledge bases that are\nexpressed in **conjunctive normal form**. **Forward chaining** and **backward chaining** are\nvery natural reasoning algorithms for knowledge bases in **Horn form**<br><br>\n\n**Local search** methods such as WALKSAT can be used to find solutions. Sound but not complete <br><br>\n\n\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Logical **state estimation** involves maintaining a logical sentence that describes the set of\npossible states consistent with the observation history. Each update step requires\ninference using the transition model of the environment, which is built from \n**successor state axioms** that specify how each **fluent** changes <br><br>\n\nDecisions within a logical agent can be made by SAT solving--finding possible models\nspecifying future action sequences that reach the goal. Only works for\nfully observable or sensorless environments <br>\n\n \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/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "c15951a5-0332-40db-e267-8924e198f35b"
      },
      "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": 32,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n **rationality**— doing the “right thing.”<br>\n**natural language processing** -to communicate in a human language <br>\n**knowledge representation** -to store what it knows or hears <br>\n**automated reasoning** -to answer questions and draw new conclusions <br>\n**machine learning** -to adapt to new circumstances and detect and extrapolate patterns. <br>\n**total Turing test**- requires interaction with objects and people in the real world <br>\n**embodied cognition** - body and cognition are connected <br>\n**\n\n\n## AIMA Chapter 27.1 The Limits of AI\n**weak AI** -machines could act intellligent <br>\n**strong AI** -machines do think <br>\nGood Old-Fashioned AI (GOFAI) <br>\n**qualification problem** - difficult to capture behavior with list of logical rules <br>\n \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n***conciousness: awereness of outside world and self <br>\n**qualia**- nature of experiences <br>\n\n## AIMA 2.1 Agents and Environments\n**agent** - anything that can perceive and act in an environment <br>\n**percept** - content an agent gets from senors <br>\n**percept sequence** - complete history of everything percieved <br>\n**agent function** - maps any given percept sequence to an action <br>\n**agent program** - physical implementation of agent function <br>\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n**rational agent** - anything that acts to achieve the best outcome <br>\n**consequentialism**- we evaluate an agent’s behavior by its consequences <br>\n**performance measure** - measures desireability <br>\nbetter to design performance measures according to what one actually wants \nto be achieved in the environment, rather than according to how one thinks the agent should behave <br>\n**Rationality depends of 4 things**: performance measure, agent's prior knowledge of environment,\nactions that the agent can perfrom, the agent's percept sequence to date <br>\n**information gathering** - doing actions in order to modify futrure precepts(exploration) <br>\n**autonomy** - relies on own percepts and learning prcoesses <br>\n\n\n## AIMA 2.3 The Nature of Environments\n **task environments** - which are\nessentially the “problems” to which rational agents are the “solutions.” <br> \n**fully observable** - sensors give acess to complete state of enviorment <br>\ntaxi driving is partically competative and cooperative <br>\n**deterministic** - next state is fully determined by current state and the next action <br>\nMost real situations are so complex that it is impossible to keep track of all the unobserved\naspects; for practical purposes, they must be treated as nondeterministic <br>\n**stochastic** - nondeterministic but with probabilities\n**episodic** - agent preceives a precept then performs a single action. Does\nnot depend on previous episode <br>\n**sequencial** - previous decisions affect next decision <br>\n**dynamic** - if the enviorment can change while agent is deliberating <br>\n**semidynamic** - if enviorment doesnt change but agents performance score does <br>\ndiscrete/continuous distinction applies to the state of\nthe environment, to the way time is handled, and to the percepts and actions of the agent <br>\n**known** - does the agent know about the rules of the environment\n\n\n## AIMA 2.4 The Structure of Agents\n behavior - action that is perfromed after any given seqeunce of percepts <br>\nagent = architechture + program <br>\n**simple reflex agent** - These agents select actions on the\nbasis of the current percept, ignoring the rest of the percept history <br>\n**transiton model** - what each action does <br>\n**sensor model** - how the world is shown to the sensor <br>\n**model-based reflex agents** - maintain internal state to track aspects of the world that are not in the current\npercept <br>\n**model_based agent** - agent using sensor model annd transition model <br>\nSearch and planning are for fuincding action sequences to achieve agent's goals <br>\n**goal based agents** - performs actions to get to goal <br>\n**utility** - the quality of being useful <br>\n**utility function** internalization of performance measure <br>\n**expected utility** - utility, on average, given the probabilities and utilities of each\noutcome (p(x)*x) <br>\n**model-free agent** - learns what action is best without learning exactly how that\naction changes the envionment <br>\n**localist representation** one-to-one mapping between concepts and memory locations\nDistributed representations are more robust against noise and\ninformation loss. <br>\n \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Rational agent** - anything that acts to achieve the best outcome\n* **Percept** - 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 **Problem** - initial state, set of actions, transition model, <br>\ngoal states, and action cost function <br>\n**state** - representation of physical configuration <br>\n**state space** - a set of possible states that the enviormenrt can be in <br>\n**state space graph** - grpah representing the enviroment of the problem <br>\n**Solution** - a path through statespace from initial to goal state <br>\n\n\n## AIMA Chapter 3.2 Example Problems\n **standardized problem** - can be given exact desciprtion (grids) <br>\n**real-world problem** - formulation is distinct (route finding problem) <br>\n\n## AIMA Chapter 3.3 Search Algorithms\n **Seach algorithm** - A search algorithm takes a search problem as input and returns a solution, or an indication\nof failure <br>\n**tree search** - various paths from initla state that find path to reach goal state <br>\n**frontier** - boarder between expanded and unexpanded states <br>\n**reached** - all nodes, even if unexpanded <br>\nSearch algorithms generally treat states and actions as atomic, without any internal\nstructure <br>\nSearch algorithms are judged on the basis of **completeness, cost optimality, time\ncomplexity, and space complexity** <br>\n**Frontier is represented using Queues** - \nIS-EMPTY(frontier) returns true only if there are no nodes in the frontier. <br>\nPOP(frontier) removes the top node from the frontier and returns it. <br>\nTOP(frontier) returns (but does not remove) the top node of the frontier. <br>\nADD(node, frontier) inserts node into its proper place in the queue. <br>\n**Priority queue** first pops the node with the minimum cost according to some\nevaluation function, It is used in best-first search <br>\n**FIFO queue or first-in-first-out queue** - first pops the node that was added to the queue\nfirst; we shall see it is used in breadth-first search. <br>\n**A LIFO queue or last-in-first-out queue (also known as a stack)** - pops first the most\nrecently added node; we shall see it is used in depth-first search. <br>\nreached states can be stroed as hash table (lookup table/dict) <br>\n**repeated state**- can be caused by **cycle** aka **loopy path** <br>\n**graph search** - checks for redundant paths <br>\n<br>\nWe can evaluate an algorithm’s performance in four ways:<br>\nCompleteness: Is the algorithm guaranteed to find a solution when there is one? <br>\nOptimality: Does the strategy find the optimal solution? <br>\nTime complexity: How long does it take to find a solution? <br>\nSpace complexity: How much memory is needed to perform the search? <br><br>\n**Complexity is expressed in terms of three quantities:** <br>\nb, the branching factor or maximum number of successors of any node <br>\nd, the depth of the shallowest goal node \n(i.e., the number of steps along the path from the root) <br>\nm, the maximum length of any path in the state space. <br><br>\nTo be **complete**, a search algorithm must be systematic in the way it explores an infinite\nstate space <br>\n**Time** is often measured in terms of the number of nodes generated during the \nsearch, and space in terms of the maximum number of nodes stored in memory. <br>\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n **Uninformed search** methods have access only to the problem definition. Algorithms differ based on which\nnode they expand first: <br> <br>\n**Breath-first search** (good when all actions have the same cost) <br>\nsimple strategy where the root node is expanded first,\n then all the successors of the root node are expanded next, then their successors, and so on.\n\nIn general, all the nodes are expanded at a given depth in the search tree before \nany nodes at the next level are expanded. <br> <br>\nComplete? Yes (if b is finite) <br>\nTime? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1) <br>\nSpace? O(bd+1) (keeps every node in memory) <br>\nOptimal? Yes (if cost = 1 per step) <br> <br>\nSpace is a bigger problem (more than time)<br><br>\n\n**Uniform-cost search** <br>\nUniform-cost search expands the node n with the lowest \npath cost g(n). This is done by storing the frontier as a priority queue ordered by g: <br>\nComplete? Yes, if step cost ≥ ε <br>\nTime? O(b1+ceiling(C*/ ε)) where C* is the cost of the optimal solution <br>\nSpace? O(b1+ceiling(C*/ ε)) <br>\nOptimal? Yes – nodes expanded in increasing order of g(n) <br><br>\n\n**Depth-first search** <br>\nDepth-first search always expands the deepest node in \nthe current frontier of the search tree: <br>\nComplete? No: fails in infinite-depth spaces, spaces with loops <br>\nModify to avoid repeated states along path <br>\ncomplete in finite spaces <br>\nTime? O(bm): terrible if m is much larger than d,\nbut if solutions are dense, may be much faster than breadth-first <br>\nSpace? O(bm), i.e., linear space! <br>\nOptimal? No <br> <br>\n\n**Depth-limited search** <br>\nThe failure of depth-first search in infinite state spaces can be \nfixed by supplying depth-first search with a predetermined depth limit l. \n(i.e., nodes at depth l have no successors)\n*note: not complete if goal is below depth l <br> <br>\n\n**Iterative deepening depth-first search** <br>\nGeneral strategy, often used in combination with depth-first tree search, \nthat finds the best depth limit. It does this by gradually increasing the \nlimit—first 0, then 1, then 2, and so on—until a goal is found <br>\nComplete? Yes <br>\nTime? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd) <br>\nSpace? O(bd) <br>\nOptimal? Yes, if step cost = 1 <br>\n\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**Informed search** methods have access to a heuristic function that estimates the\ncost of a solution from They may have access to additional information such as\npattern databases with solution costs <br><br>\n**greedy best-first search** <br>\nGreedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly <br>\nIt evaluates nodes by using just the heuristic function; that is, f(n) = h(n) <br>\nComplete? No – can get stuck in loops\nTime? O(bm), but a good heuristic can give dramatic improvement\nSpace? O(bm) -- keeps all nodes in memory\nOptimal? No <br><br>\n\n**A* search** (main issue is memory) <br>\nEvaluates nodes by combining g(n), the cost to reach the node, and h(n), \nthe cost to get from the node to the goal: <br> <br>\n\nf(n) = g(n) + h(n) <br>\nIf h(n) is admissible, A* using TREE-SEARCH is optimal <br>\nAn admissible heuristic is one that never overestimates the cost to reach the goal <br>\nA heuristic is consistent if for every node n, every successor n' of n is generated by any action a <br>\nh(n) ≤ c(n,a,n') + h(n') <br>\nif h is consitent: <br>\nf(n') \t= g(n') + h(n') <br>\n      \t= g(n) + c(n,a,n') + h(n') <br>\n      \t≥ g(n) + h(n) <br>\n      \t= f(n) <br><br>\nEvery consistent heuristic is admissible (but not vice versa) <br> <br>\n\nComplete? Yes (unless there are infinitely many nodes with f ≤ f(G)) <br>\nTime? Exponential <br>\nSpace? Keeps all nodes in memory <br>\nOptimal? Yes if h is admissable <br><br>\n**BIDIRECTIONAL A* SEARCH** is sometimes more efficient than A* itself. <br>\n\nmonotonic: the path cost always\nincreases as you go along a path, because action costs are always positive. <br><br>\n\n**Memory bounded searches** <br>\n\n**Iterative-deepening A star** <br>\nThe simplest way to reduce memory requirements for A* is to adapt the idea of \niterative deepening to the heuristic search context, resulting in the\niterative-deepening A* (IDA* ) algorithm. <br> <br>\n\nThe main difference between IDA* and standard iterative deepening is that the \ncutoff used is the f -cost (g + h) rather than the depth; \nat each iteration, the cutoff value is the smallest f -cost of any node that \nexceeded the cutoff on the previous iteration. <br><br>\n\n**RBFS (recursive best-first search) and SMA* (simplified memory-bounded A*)** are\nrobust, optimal search algorithms that use limited amounts of memory; given enough\ntime, they can solve problems for which A* runs out of memory <br><br>\n\n**beam search** - limits the size of the frontier. The easiest approach is to keep only the nodes\nwith the best -scores, discarding any other expanded nodes. Incomplete and suboptimal <br><br>\n\n**WEIGHTED A star** search focuses the search towards a goal, expanding fewer nodes, but\nsacrificing optimality.<br>\n\n \n\n## AIMA Chapter 3.6 Heuristic Functions\n\nOne way to characterize the quality of a heuristic is the effective branching factor b*. \nIf the total number of nodes generated by A* for a particular problem is N and \nthe solution depth is d, then b* is the branching factor that a uniform tree of \ndepth d would have to have in order to contain N + 1 nodes. Thus, <br> <br>\n\nN + 1 = 1 + b* + (b*)2 + · · · + (b*)d <br><br>\n\nFor example, if A* finds a solution at depth 5 using 52 nodes, then the \neffective branching factor is 1.92 <br> <br>\n\nTo test the heuristic functions h1 and h2, we generated 1200 random problems \nwith solution lengths from 2 to 24 (100 for each even number) and solved them \nwith iterative deepening search and with A* tree search using both h1 and h2. \nThe results suggest that h2 is better than h1, and is far better than using \niterative deepening search. <br><br>\n\nOne might ask whether h2 is always better than h1. The answer is “Essentially, yes.” \nWe thus say that h2 dominates h1.<br><br>\n\n**Relaxed Problems**<br>\nA problem with fewer restrictions on the actions is called a **relaxed problem** <br>\nThe cost of an optimal solution to a relaxed problem is an admissible heuristic \nfor the original problem <br>\nIf the rules of the 8-puzzle are relaxed so that a tile can move anywhere, \nthen h1(n) gives the shortest solution <br>\nIf the rules are relaxed so that a tile can move to any adjacent square, then h2(n) \ngives the shortest solution <br><br>\n\n\n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Shortcuts** - artificial edges in the graph that define an optimal multi-action path\n* **Pattern databases** - store these exact solution costs for every possible subproblem instance\n* **Disjoint pattern databases** - combinging solution from subproblems that don't overlap\n\n\n## WARNING: Your definition of 'quiescent' is too long!\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Minimax search: move to position with highest minimax value aka best achievable payoff against best play <br> \nThe minimax algorithm performs a complete depth-first exploration of the game tree.<br><br>\n\nA reasonable opponent will always chose the the lowest score. Our agent will then \nchoose the higest of those scores. The root then will reflect the highest possible \nscore from the current depth. <br><br>\n\nComplete? Yes (if tree is finite) <br>\nOptimal? Yes (against an optimal opponent) <br>\nTime complexity? O(bm) <br>\nSpace complexity? O(bm) (depth-first exploration) <br>\nFor chess, b ≈ 35, m ≈ 100 for \"reasonable\" games <br><br>\n\n**Alpha-beta pruning** <br>\nThe number of game states is exponential in the depth of the tree, pruning is to \nreduce the exponent in half<br>\nPruning does not affect final result <br>\nGoods moves ordered first improves effectivlenss of pruning <br>\nPerfect ordering time complexity is O(b^m/2), doubles depth of search <br>\nalpha = \"at least\", beta = \"at most\" <br>\nThe number of game states is exponential in the depth of the tree <br>\nIf v is worse than α, max will avoid it prune that branch <br><br>\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n **Move ordering** <br>\n alpha–beta can solve a tree roughly twice as deep as minimax in the same amount of time <br>\n Adding dynamic move-ordering schemes, such as trying first the moves that were \n found to be best in the past, brings us quite close to the theoretical limit <br>\n The past could be the previous move—often the same threats remain—or it could come \n from previous exploration of the current move <br>\n One way to gain information from the current move is with iterative deepening search <br>\n Type A- wide but shallow, type B- ignores bad moves, deep but narrow <br>\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nAn evaluation function returns an estimate of the expected utility \nof the game from a given position, just as the heuristic functions return an estimate of the distance to the goal<br><br>\nIt should be clear that the performance of a game-playing program depends strongly on the quality of its evaluation function<br><br>\nIn other words, we replace the UTILITY function with EVAL, which estimates a state’s\nutility. We also replace the terminal test by a **cutoff test**, which must return true for terminal\nstates, but is otherwise free to decide when to cut off the search, based on the search depth\nand any property of the state that it chooses to consider <br><br>\n\nGood evaluation function:<br>\n1. should order terminal states in the same way as the utility function:states that \nare wins must evaluate better than draws, which in turn must be better than losses.<br>\n2. The computation must not take too long! <br>\n3. For nonterminal states, the evaluation function should be strongly correlated \nwith the actual chances of winning <br>\n\n**cutting off search**<br>\nThe next step is to modify A LPHA-BETA-SEARCH so that it will call the heuristic E VAL function when it is appropriate to cut off the search<br>\nMinimaxCutoff is identical to MinimaxValue except: <br>\nTerminal? is replaced by Cutoff? <br>\nUtility is replaced by Eval<br><br>\nFor nonquiescent positions the IS-CUTOFF returns false, and the\nsearch continues until quiescent positions are reached <br><br>\n\n**forward pruning**<br>\nForward pruning: Some moves at a given node are pruned immediately without further consideration<br>\nPROBCUT also prunes nodes that are probably outside the (alpha, beta) window based on experience <br><br>\nComputes probability by doing a shallow search to compute backed-up value v of a \nnode, then using past experience to estimate how likely it is that a score of \nv at depth d in the tree would be outside (alpha, beta)<br><br>\n\n**search vs lookup**<br>\nNear the end of the game there are again fewer possible positions, and thus more \nchance to do lookup. But here it is the computer that has the expertise: \ncomputer analysis of endgames goes far beyond anything achieved by humans <br>\n\nA computer, can completely solve the endgame by producing a **policy**, which is \na mapping from every possible state to the best move in that state. Then we can \njust look up the best move rather than recompute it again<br><br>\n\nThe table is constructed by **retrograde** minimax search<br>\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n**Stochastic games** bring us closer to the unpredictability of \nreal life by including a random element, such as the throwing of dice<br><br>\nmust include change nodes (in circles) <br><br>\n\nGames of chance can be handled by expectiminimax, an extension to the minimax\nalgorithm that evaluates a chance node by taking the average utility of all its children,\nweighted by the probability of each child<br><br>\n\nThe evaluation function must return values that are a\npositive linear transformation of the probability of winning (or of the expected utility, for\ngames that have outcomes other than win/lose) <br><br>\n\nIt may have occurred to you that something like alpha–beta pruning could be applied to\ngame trees with chance nodes. It turns out that it can<br>\n\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* **Zero-sum** - what is good for one player is just as bad for the other: there is no “win-win” outcome\n* **Killer moves** - best moves\n* **Transpositions** - different permutations of the move sequence that end up in the same positions\n* **Transposition table** - that caches the heuristic value of states\n* **Weighted linear function** - feature times weight added for all features in state (0-1)\n* **Quiescent** - that is, positions in which there is no pending move (such as a capturing the queen) that would wildly swing the evaluation\n* **Horizon effect** - program is facing an opponent’s move that causes serious damage and is ultimately unavoidable, but can be delayed\n* **Singular extensions** - moves that are “clearly better” than all other moves in a given position, used to mitigate horizontal effect\n* **Late move reduction** - works under the assumption that move ordering has been done well\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n CSPs deal with **assignments** of values to variables. An assignment\nthat does not violate any constraints is called a **consistent** or legal assignment. A **complete\nassignment** is one in which every variable is assigned a value, and a **solution** to a CSP is a\nconsistent, complete assignment. A **partial assignment** is one that leaves some variables\nunassigned, and a **partial solution** is a partial assignment that is consistent\nvisualize a CSP as a constraint graph<br><br>\n\nThe simplest kind of CSP involves variables that have discrete, finite domains<br>\nA discrete domain can be infinite, such as the set of integers or strings<br><br>\n\nIt can be shown that no algorithm exists for solving general nonlinear \nconstraints on integer variables—the problem is undecidable<br><br>\n\nGlobal constraint need not involve all the variables in a problem<br>\n\n\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\nThe minimum-remaining-values and degree heuristics are domain-independent\nmethods for deciding which variable to choose next in a backtracking search <br>\nThe leastconstraining-value heuristic helps in deciding which value to try first for a given\nvariable <br>\nBacktracking occurs when no legal assignment can be found for a variable.\nConflict-directed backjumping backtracks directly to the source of the problem <br>\nConstraint learning records the conflicts as they are encountered during search in order\nto avoid the same conflict later in the search <br><br>\nLocal search using the min-conflicts heuristic has also been applied to constraint\nsatisfaction problems with great success<br>\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search using the min-conflicts heuristic has also been applied to constraint\nsatisfaction problems with great success <br> \n\n## AIMA Chapter 6.5 The Structure of Problems\nThe complexity of solving a CSP is strongly related to the structure of its constraint\ngraph. Tree-structured problems can be solved in linear time. Cutset conditioning can\nreduce a general CSP to a tree-structured one and is quite efficient (requiring only linear\nmemory) if a small cutset can be found. <br><br>\nTree decomposition techniques transform the\nCSP into a tree of subproblems and are efficient if the tree width of the constraint graph\nis small, but they need memory exponential in the tree width of the constraint\ngraph. Combining cutset conditioning with tree decomposition can allow a better\ntradeoff of memory versus time<br> \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* ** binary constraint** - relates two variables\n* ** global constraint** - A constraint involving an arbitrary number of variables \n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Intelligent agents need knowledge about the world in order to reach good decisions <br>\nKnowledge is contained in agents in the form of **sentences** in a **knowledge\nrepresentation language** that are stored in a **knowledge base** <br><br>\n\nA knowledge-based agent is composed of a knowledge base and an inference\nmechanism. It operates by storing sentences about the world in its knowledge base,\nusing the inference mechanism to infer new sentences, and using these sentences to\ndecide what action to take<br><br>\n\nA representation language is defined by its **syntax**, which specifies the structure of\nsentences, and its **semantics**, which defines the truth of each sentence in each possible\nworld or model <br><br>\n\n\n## AIMA Chapter 7.2 The Wumpus World\n The relationship of **entailment** between sentences is crucial to our understanding of\nreasoning. A sentence alpha entails another sentence beta if beta is true in all worlds where alpha is\ntrue. Equivalent definitions include the **validity** of the sentence a -> b and the\nunsatisfiability of the sentence a^-|B\n\n**Inference** - process of deriving new sentences from old ones. Sound inference\nalgorithms derive only sentences that are entailed; complete algorithms derive all\nsentences that are entailed <br><br>\n\n\n## AIMA Chapter 7.3 Logic\n **Propositional logic**- simple language consisting of proposition symbols and logical\nconnectives. It can handle propositions that are known to be true, known to be false, or\ncompletely unknown<br><br>\n\n**Inference rules** - patterns of sound inference that can be used to find proofs. The\n**resolution** rule yields a complete inference algorithm for knowledge bases that are\nexpressed in **conjunctive normal form**. **Forward chaining** and **backward chaining** are\nvery natural reasoning algorithms for knowledge bases in **Horn form**<br><br>\n\n**Local search** methods such as WALKSAT can be used to find solutions. Sound but not complete <br><br>\n\n\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Logical **state estimation** involves maintaining a logical sentence that describes the set of\npossible states consistent with the observation history. Each update step requires\ninference using the transition model of the environment, which is built from \n**successor state axioms** that specify how each **fluent** changes <br><br>\n\nDecisions within a logical agent can be made by SAT solving--finding possible models\nspecifying future action sequences that reach the goal. Only works for\nfully observable or sensorless environments <br>\n\n \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": {}
        }
      ]
    }
  ]
}