{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "REVATHI - FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8af7ecec-29ec-4da3-feab-95f1fe136f1b"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 81,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1cd67f17-bc7f-4338-e58e-07a69aedbd55"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 82,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 83,
      "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 = \"\"\" Chapter 1.1 summary. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Everything in the definition section.\"\"\"\n",
        "\n",
        "chapter2_2 = \"\"\" \n",
        "Depends on: \\n1. performance measure \\n2. agent's prior knowlegde of the environment \\n3. actions that the agent can perform \\n4. agent's percept sequence to date.\n",
        "\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" Lecture notes \"\"\"\n",
        "chapter2_4 = \"\"\" The job of AI is to design an agent program that implements the agent function—the mapping from percepts to actions. \n",
        "We assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture: agent = architecture + program \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" \n",
        "Task environment properties:\n",
        "\\n1. Fully observable, partially observable\n",
        "\\n2. Deterministic, Non-deterministic, stochastic\n",
        "\\n3. Episodic, sequential (dependency on previous actions)\n",
        "\\n4. Static, Dynamic\n",
        "\\n5. Discrete, continuous\n",
        "\\n6. Single, multiagent\n",
        "\\n\\nHardest environment: continuous, partially observable, stochastic, multiagent. \n",
        "\n",
        "Reflex agent vs problem solving - only current percent vs plan ahead.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive (sense) and act (actuate) in an environment\",\n",
        "\"percept\" : \"agent's perceptual inputs at any given instance\",\n",
        "\"percept sequence\": \"complete history of everything perceived by the agent\",\n",
        "\"agent function\": \"mapping of percept sequence to an action\",\n",
        "\"agent program\":\"agent function is implemented by an agent program\",\n",
        "\"rational agent\":\"does the right thing\",\n",
        "\"rational_agent\":\"\"\"For each possible percept sequence, a rational agent should select an action that is expected to\n",
        "maximize its performance measure\"\"\",\n",
        "\"task environment\":\"problems to which agents provide solutions (PEAS - performance, env, actuator, sensor)\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 84,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "ff1f5cb7-6156-4784-da8e-6917d859c876"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 85,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Everything in the definition section.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nDepends on: \n1. performance measure \n2. agent's prior knowlegde of the environment \n3. actions that the agent can perform \n4. agent's percept sequence to date.\n\n\n\n## AIMA 2.3 The Nature of Environments\n Lecture notes \n\n## AIMA 2.4 The Structure of Agents\n The job of AI is to design an agent program that implements the agent function—the mapping from percepts to actions. \nWe assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture: agent = architecture + program \n\n## Module 1 Lecture Notes\n \nTask environment properties:\n\n1. Fully observable, partially observable\n\n2. Deterministic, Non-deterministic, stochastic\n\n3. Episodic, sequential (dependency on previous actions)\n\n4. Static, Dynamic\n\n5. Discrete, continuous\n\n6. Single, multiagent\n\n\nHardest environment: continuous, partially observable, stochastic, multiagent. \n\nReflex agent vs problem solving - only current percent vs plan ahead.\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive (sense) and act (actuate) in an environment\n* **Percept** - agent's perceptual inputs at any given instance\n* **Percept sequence** - complete history of everything perceived by the agent\n* **Agent function** - mapping of percept sequence to an action\n* **Agent program** - agent function is implemented by an agent program\n* **Rational agent** - does the right thing\n* **Rational_agent** - For each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure\n* **Task environment** - problems to which agents provide solutions (PEAS - performance, env, actuator, sensor)\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": 86,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "ae729a10-3fe6-435a-c3cc-9932dd00f945"
      },
      "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": 87,
      "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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\"Best first search (graph algo): choose a node, with a minimum value of some eval function say f(n). If the node is the goal state, you return that solution, if not - you expand the current node. Redundant paths - include cycles (loopy path), checking a state again, etc. We call a search algo a graph search if it checks for redundant paths, and tree search if it does not.\n",
        "\\n Measuring problem solving performance: \\n1. Completeness: If there exists a solution, does the algo return it? If not does it report failure correctly? \\n2. Cost Optimality: Does it find the path with the least cost? \n",
        "\\n3. Time complexity \\n4. Space Complexity. \\n\\nSpace/time complexity is usually measured in terms of |V| and |E| of a graph, but other factors could be d: depth of a tree/graph, m: maximum moves to reach the goal state and b: branching factor.\"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\" \\n3.4.1 *Bread First Search*: (FIFO) This is appropriate when all actions have the same cost. Root is expanded, all successors of the root node are expanded, then their successors and so on. We can call BFS best first with f(n) to be depth of the node, i.e., the actions needed to reach the node. \n",
        "We use FIFO queue instead of priority queue for efficiency. We can use early-goal-test, rather than late goal test (wait until node is popped off from the Q) as in best first. This is checking if a node is goal node as soon as it is generated.  \n",
        "Performance: BFS is cost optimal for problems having same action cost. It is complete. Time and space complexity are both O(b^d), since all nodes remain in memory.\n",
        "\n",
        "\\n3.4.2 *Dijkstra/Uniform cost search*: When actions have diff costs, use best-first search with eval fn = cost of path from root to curr node. \n",
        "Complexity is given in terms of C*, cost of optimal solution. And epsilon (E), E>0, where E is the lower bound of each action cost. Worst case time and space complexity is:\n",
        " $$O(b^{1 + (C*/E)})$$ This can be worse than BFS. Uniform-cost search is complete and cost optimal. It never gets caught down a single path infinite path, always chooses paths systematically in terms of increasing costs.\n",
        " \n",
        "\\n3.4.3 *Depth first search*: (LIFO) Always expands the deepest node in the frontier first. It can be called bestFS with eval fn negative of the depth. This is a tree search where it does not keep track of reached states.\n",
        "DFS is not cost-optimal. It returns the solution it finds first, even if it is not lowest cost. For finite space it is complete. In cyclic state spaces it can get stuck in an infinite loop. In infinite state spaces, depth-first\n",
        "search is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus DFS is incomplete.\n",
        "Space complexity is $$O(bm)$$ Here, m is the maximum depth of the tree. We use DFS when you need a tree like search and memory efficiency. Variation of DFS is backtracking search, which uses even lesser memory, since it expands one node at a time. which is O(m).\n",
        "\n",
        "\\n3.4.4 *Depth limited & Iterative deepening search*: Set depth to l so that no problem of infite loop. Time: O(b^l), Space: O(bl). IMportant: choice of l. Iterative deepening is same as depth limited, except it tries all values of l: 0,1,...until a solution is found, or you surpass cutoff value.\n",
        "SpaceL O(bd) if there is a solution, O(bm) if no solution. Complete, cost optimal.\n",
        "\n",
        "\\n3.4.5 *Bidirectional search*: Search forward from initial and backwards from goal state; hope the two will meet. Motivation: b^(d/2) + b^(d/2) < b^d.\n",
        "Complete, cost optimal. Time, space both O(b^d/2)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" State vs Node: state is representation of a physical configuration, node is data structure - part of search tree. \n",
        "\n",
        "Graph search: simple modification to tree search, check if a node has been visited before.\n",
        "\n",
        "Uninformed search: all nodes have equal importance, informed search: some nodes are ranked higher than the others.\n",
        "\n",
        "Use DFS: \\n1. Space is restricted \\n2. There are many possible solutions with long paths and wrong paths are usually\n",
        "terminated quickly \\n3. Search can be fine-tuned quickly\n",
        "\n",
        "Use BFS: \\n1. Possible infinite paths \\n2. Some solutions have short paths \\n3. Can quickly discard unlikely paths\n",
        "\n",
        "Depth limited: \\n1. if l=d, optimal \\n2. l<d incomplete \\n3. l>d not optimal\n",
        "\n",
        "ID-DFS: \\n1. Complete, time O(b^d), space O(bd), optimal if step cost=1\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        "\"goal formulation\": \"goal state - organize the behavior by limiting objectives and hence actions\",\n",
        "\"problem formulation\": \"description of states and actions to reach the goal\",\n",
        "\"search\": \"agent simulates actions in its model, searching till it finds a solution that reaches the goal\",\n",
        "\"search problem\": \"states, state space, initial and goal state, actions, transition model, action cost function\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 88,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ff854181-6c3f-4268-c679-2a7401c07de7"
      },
      "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": 89,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\nBest first search (graph algo): choose a node, with a minimum value of some eval function say f(n). If the node is the goal state, you return that solution, if not - you expand the current node. Redundant paths - include cycles (loopy path), checking a state again, etc. We call a search algo a graph search if it checks for redundant paths, and tree search if it does not.\n\n Measuring problem solving performance: \n1. Completeness: If there exists a solution, does the algo return it? If not does it report failure correctly? \n2. Cost Optimality: Does it find the path with the least cost? \n\n3. Time complexity \n4. Space Complexity. \n\nSpace/time complexity is usually measured in terms of |V| and |E| of a graph, but other factors could be d: depth of a tree/graph, m: maximum moves to reach the goal state and b: branching factor.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n3.4.1 *Bread First Search*: (FIFO) This is appropriate when all actions have the same cost. Root is expanded, all successors of the root node are expanded, then their successors and so on. We can call BFS best first with f(n) to be depth of the node, i.e., the actions needed to reach the node. \nWe use FIFO queue instead of priority queue for efficiency. We can use early-goal-test, rather than late goal test (wait until node is popped off from the Q) as in best first. This is checking if a node is goal node as soon as it is generated.  \nPerformance: BFS is cost optimal for problems having same action cost. It is complete. Time and space complexity are both O(b^d), since all nodes remain in memory.\n\n\n3.4.2 *Dijkstra/Uniform cost search*: When actions have diff costs, use best-first search with eval fn = cost of path from root to curr node. \nComplexity is given in terms of C*, cost of optimal solution. And epsilon (E), E>0, where E is the lower bound of each action cost. Worst case time and space complexity is:\n $$O(b^{1 + (C*/E)})$$ This can be worse than BFS. Uniform-cost search is complete and cost optimal. It never gets caught down a single path infinite path, always chooses paths systematically in terms of increasing costs.\n \n\n3.4.3 *Depth first search*: (LIFO) Always expands the deepest node in the frontier first. It can be called bestFS with eval fn negative of the depth. This is a tree search where it does not keep track of reached states.\nDFS is not cost-optimal. It returns the solution it finds first, even if it is not lowest cost. For finite space it is complete. In cyclic state spaces it can get stuck in an infinite loop. In infinite state spaces, depth-first\nsearch is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus DFS is incomplete.\nSpace complexity is $$O(bm)$$ Here, m is the maximum depth of the tree. We use DFS when you need a tree like search and memory efficiency. Variation of DFS is backtracking search, which uses even lesser memory, since it expands one node at a time. which is O(m).\n\n\n3.4.4 *Depth limited & Iterative deepening search*: Set depth to l so that no problem of infite loop. Time: O(b^l), Space: O(bl). IMportant: choice of l. Iterative deepening is same as depth limited, except it tries all values of l: 0,1,...until a solution is found, or you surpass cutoff value.\nSpaceL O(bd) if there is a solution, O(bm) if no solution. Complete, cost optimal.\n\n\n3.4.5 *Bidirectional search*: Search forward from initial and backwards from goal state; hope the two will meet. Motivation: b^(d/2) + b^(d/2) < b^d.\nComplete, cost optimal. Time, space both O(b^d/2)\n\n\n\n## Module 3 Lecture Notes\n State vs Node: state is representation of a physical configuration, node is data structure - part of search tree. \n\nGraph search: simple modification to tree search, check if a node has been visited before.\n\nUninformed search: all nodes have equal importance, informed search: some nodes are ranked higher than the others.\n\nUse DFS: \n1. Space is restricted \n2. There are many possible solutions with long paths and wrong paths are usually\nterminated quickly \n3. Search can be fine-tuned quickly\n\nUse BFS: \n1. Possible infinite paths \n2. Some solutions have short paths \n3. Can quickly discard unlikely paths\n\nDepth limited: \n1. if l=d, optimal \n2. l<d incomplete \n3. l>d not optimal\n\nID-DFS: \n1. Complete, time O(b^d), space O(bd), optimal if step cost=1\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Goal formulation** - goal state - organize the behavior by limiting objectives and hence actions\n* **Problem formulation** - description of states and actions to reach the goal\n* **Search** - agent simulates actions in its model, searching till it finds a solution that reaches the goal\n* **Search problem** - states, state space, initial and goal state, actions, transition model, action cost function\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 = \"\"\"Hints from heuristic function and the domain. \n",
        "\\n3.5.1 *Greedy Best-first search*: expands nodes closest to the goal, f(n) = h(n). Complete in finite spaces, incomplete otherwise. Worst time and space complexity is O(|V|), this can be reduced to O(bm) with good heuristic.\n",
        "\\n3.5.2 *A * search*: f(n) = g(n) + h(n); g(n) is the path cost from the initial state to node and h(n) is the estimated cost of the shortest path from to a goal state, so f(n) is estimated cost of the best path that continues from n to a goal.\n",
        "A* is complete. Cost optimality depends on the chosen heuristic. Admissibility, Consistency - A heuristic is consistent if, for every node n and every successor n, of generated by an action we have h(n) <= c(n,a,n') + h(n'). Every consistent heuristic is admissible, not vice versa.\n",
        "A* is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.  If we allow A* search to use an\n",
        "inadmissible heuristic—one that may overestimate, then we may miss the optimal solution, but the heuristic can potentially be more accurate, thereby reducing the number of\n",
        "nodes expanded. Weighted A* search - g(n) + W*h(n). \n",
        "In bounded suboptimal search, we look for a solution that is guaranteed to be within a constant factor W of the optimal cost. Weighted A* provides this guarantee. \n",
        "In bounded-cost search, we look for a solution whose cost is less than some constant C. And in unbounded-cost search, we accept a solution of any cost,\n",
        "as long as we can find it quickly. \n",
        "\\n3.5.5 *Memory Bounded Search* - drawback of A*, use of space. Beam Search - reduces the size of the frontier. Keep best k-nodes with best f-scores. Incomplete and suboptimal.\n",
        "IDA* - e benefits of A* without the requirement to keep all reached states in memory, at a cost of visiting some states multiple times. Recursive Best First Search - rather than continuing indefinitely down the current path, it uses the f_limit\n",
        "variable to keep track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path.\n",
        "Bidirectional Heuristic Search - lb(m, n) = max(gF (m) + gB(n), fF (m), fB(n)).\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" \n",
        "Relaxed problems: The graph of the relaxed problem is a supergraph of the og state space. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\n",
        "If a collection of admissible heuristics {h1, h2..} is available, then h(n) which is composite heuristic picks the one that is most accurate on node n. h(n) is admissible and consistent, and dominates its subcomponents.\n",
        "Differential heuristic: hDH(n) = max(L∈Landmarks)|C ∗(n,L) − C∗(goal,L)|\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "Admissible heuristics: \n",
        "h(n) <= h*(n) where h*(n) is the true cost from n\n",
        "h(n) >= 0 so h(G)=0 for any goal G\n",
        "\n",
        "If h2(n) ≥ h1(n) for all n (both admissible), then h2 dominates h1; So h2 is optimistic, but more accurate than h1.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissible heuristic\" : \"a heuristic that never over-estimates the cost to reach the goal node, it is optimistic\",  \n",
        "\"relaxed problem\": \"A problem with fewer restrictions on the actions\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 90,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 688
        },
        "outputId": "4b0a5820-6a74-449e-e85e-45f2dadd3967"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 91,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nHints from heuristic function and the domain. \n\n3.5.1 *Greedy Best-first search*: expands nodes closest to the goal, f(n) = h(n). Complete in finite spaces, incomplete otherwise. Worst time and space complexity is O(|V|), this can be reduced to O(bm) with good heuristic.\n\n3.5.2 *A * search*: f(n) = g(n) + h(n); g(n) is the path cost from the initial state to node and h(n) is the estimated cost of the shortest path from to a goal state, so f(n) is estimated cost of the best path that continues from n to a goal.\nA* is complete. Cost optimality depends on the chosen heuristic. Admissibility, Consistency - A heuristic is consistent if, for every node n and every successor n, of generated by an action we have h(n) <= c(n,a,n') + h(n'). Every consistent heuristic is admissible, not vice versa.\nA* is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.  If we allow A* search to use an\ninadmissible heuristic—one that may overestimate, then we may miss the optimal solution, but the heuristic can potentially be more accurate, thereby reducing the number of\nnodes expanded. Weighted A* search - g(n) + W*h(n). \nIn bounded suboptimal search, we look for a solution that is guaranteed to be within a constant factor W of the optimal cost. Weighted A* provides this guarantee. \nIn bounded-cost search, we look for a solution whose cost is less than some constant C. And in unbounded-cost search, we accept a solution of any cost,\nas long as we can find it quickly. \n\n3.5.5 *Memory Bounded Search* - drawback of A*, use of space. Beam Search - reduces the size of the frontier. Keep best k-nodes with best f-scores. Incomplete and suboptimal.\nIDA* - e benefits of A* without the requirement to keep all reached states in memory, at a cost of visiting some states multiple times. Recursive Best First Search - rather than continuing indefinitely down the current path, it uses the f_limit\nvariable to keep track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path.\nBidirectional Heuristic Search - lb(m, n) = max(gF (m) + gB(n), fF (m), fB(n)).\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \nRelaxed problems: The graph of the relaxed problem is a supergraph of the og state space. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\nIf a collection of admissible heuristics {h1, h2..} is available, then h(n) which is composite heuristic picks the one that is most accurate on node n. h(n) is admissible and consistent, and dominates its subcomponents.\nDifferential heuristic: hDH(n) = max(L∈Landmarks)|C ∗(n,L) − C∗(goal,L)|\n\n\n## Module 4 Lecture Notes\n \nAdmissible heuristics: \nh(n) <= h*(n) where h*(n) is the true cost from n\nh(n) >= 0 so h(G)=0 for any goal G\n\nIf h2(n) ≥ h1(n) for all n (both admissible), then h2 dominates h1; So h2 is optimistic, but more accurate than h1.\n\n\n## Module 4 Definitions\n* **Admissible heuristic** - a heuristic that never over-estimates the cost to reach the goal node, it is optimistic\n* **Relaxed problem** - A problem with fewer restrictions on the actions\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",
        "\n",
        "chapter5_1 = \"\"\" \n",
        "Game theory: Most commonly studied games are deterministic, 2 player, turn-taking, perfect-info (fully observable), zero-sum games (what is good for one player is bad for another, no win-win situation).\n",
        "TWO players - MAX and MIN, max plays first move. Chess is a zero sum game.\n",
        " \"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\" \n",
        "5.2.1 Minimax Algorithm: It is a recursive algorithm that proceeds all the way down to the leaves of the tree and then backs up the minimax values through the tree as the recursion unwinds. \n",
        "\\n5.2.3 Alpha-beta pruning: Algo: \\n\\nSuppose, MINIMAX(root) = max(min(3,12,8), min(2,x,y), min(14,5,2)) = max(3,z,2) where z = min(2,x,y) ≤ 2 \\n\\n\n",
        "The value of the root and hence the minimax decision are independent of the values of the leaves x and y, and therefore they can be pruned.\n",
        "\\n5.2.4 Move ordering: The effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. \n",
        "If this could be done properly, alpha–beta will examine only O(b^m/2) nodes to pick the best move, instead of O(b^m) for minimax. Effective branching\n",
        "factor becomes sqrt(b) instead of b — and for chess, about 6 instead of 35. \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter5_3 = \"\"\" \n",
        "A heuristic evaluation function EVAL(S,P) returns an estimate of the expected utility of state s to player p.\n",
        "\"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\"Expectiminimax value for games with chance nodes - stochastic games, a generalization of the minimax value for deterministic games. \n",
        "Terminal, MAX and MIN nodes work exactly as before. \n",
        "For chance nodes we compute the expected value, which is the sum of the value over all outcomes, weighted by the probability of each chance action.\n",
        "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). \n",
        "Expectiminimax time: is also considering all the possible dice-roll sequences,\n",
        "it will take O(b^m * n^m), where n is the number of distinct rolls.\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 = \"\"\"\n",
        "Simplest game environment: multiagent, static, discrete, fully observable, strategic\n",
        "\n",
        "Expectimax search: compute the average score under optimal play, calculate the expected utility, so (replace min with expecti-basically)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"move\" : \"action\",    \n",
        "\"position\": \"state\",\n",
        "\"terminal State\": \"state where game has ended\",\n",
        "\"utility function (objective/payoff fn)\": \"defines the final numeric value to player p when the game ends in terminal state s\",\n",
        "\"killer moves\": \"best moves\",\n",
        "\"transposition\": \"different permutations of the move sequence that end up in the same position.\",\n",
        "\"stochastic game\": \"includes some randomness that mimics real life, e.g., backgammon or throwing of a dice\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 92,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ca0fcd95-96d6-402a-d697-7d60027f580b"
      },
      "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": 93,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nGame theory: Most commonly studied games are deterministic, 2 player, turn-taking, perfect-info (fully observable), zero-sum games (what is good for one player is bad for another, no win-win situation).\nTWO players - MAX and MIN, max plays first move. Chess is a zero sum game.\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n5.2.1 Minimax Algorithm: It is a recursive algorithm that proceeds all the way down to the leaves of the tree and then backs up the minimax values through the tree as the recursion unwinds. \n\n5.2.3 Alpha-beta pruning: Algo: \n\nSuppose, MINIMAX(root) = max(min(3,12,8), min(2,x,y), min(14,5,2)) = max(3,z,2) where z = min(2,x,y) ≤ 2 \n\n\nThe value of the root and hence the minimax decision are independent of the values of the leaves x and y, and therefore they can be pruned.\n\n5.2.4 Move ordering: The effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. \nIf this could be done properly, alpha–beta will examine only O(b^m/2) nodes to pick the best move, instead of O(b^m) for minimax. Effective branching\nfactor becomes sqrt(b) instead of b — and for chess, about 6 instead of 35. \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nA heuristic evaluation function EVAL(S,P) returns an estimate of the expected utility of state s to player p.\n\n\n## AIMA Chapter 5.5 Stochastic Games\nExpectiminimax value for games with chance nodes - stochastic games, a generalization of the minimax value for deterministic games. \nTerminal, MAX and MIN nodes work exactly as before. \nFor chance nodes we compute the expected value, which is the sum of the value over all outcomes, weighted by the probability of each chance action.\nEvaluation 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). \nExpectiminimax time: is also considering all the possible dice-roll sequences,\nit will take O(b^m * n^m), where n is the number of distinct rolls.\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\nSimplest game environment: multiagent, static, discrete, fully observable, strategic\n\nExpectimax search: compute the average score under optimal play, calculate the expected utility, so (replace min with expecti-basically)\n\n\n\n## Module 5 Definitions\n* **Move** - action\n* **Position** - state\n* **Terminal state** - state where game has ended\n* **Utility function (objective/payoff fn)** - defines the final numeric value to player p when the game ends in terminal state s\n* **Killer moves** - best moves\n* **Transposition** - different permutations of the move sequence that end up in the same position.\n* **Stochastic game** - includes some randomness that mimics real life, e.g., backgammon or throwing of a dice\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 = \"\"\"We use a factored representation for each\n",
        "state: a set of variables, each of which has a value. A problem is solved when each variable\n",
        "has a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem (CSP). CSP search algorithms take advantage of the structure of states and use general rather than domain-specific heuristics to enable the solution of complex problems. \n",
        "The main idea is to eliminate large portions of the search space all at once by identifying variable/value combinations that violate the constraints. An assignment that does not violate any constraints is called a consistent or legal assignment. A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a\n",
        "consistent, complete assignment. \n",
        "A partial assignment is one that leaves some variables unassigned, and a partial solution is a partial assignment that is consistent.\n",
        "\"\"\"\n",
        "\n",
        "chapter6_2 = \"\"\" \n",
        "\\n1.Node consistency: A single variable (corresponding to a node in the CSP graph) is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\n",
        "\\n2. Arc consistency: A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints.\n",
        "\\n\\tAC3 Algorithm:  CSP with n variables, each with domain size at most d, and with binary constraints c (arcs).  Each arc (Xk, Xi) can be\n",
        "inserted in the queue only d times because Xi has at most d values to delete. So the time is O(cd^3). (arc checking can be done in O(d^2)).\n",
        "\n",
        "\\n3.Path Consistency:  Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "\\n1. Consistent assignment: does not violate constraints\n",
        "\\n2. Complete assignment: every variable is assigned a value\n",
        "\\n3. Solution to CSP: Complete, consistent assignment\n",
        "\n",
        "Forward checking: removes some possibilities, but does not estimate failure. Terminate when any of the unassigned variables have no values to be assigned.\n",
        "\n",
        "AC3 Worst case: O(n2d3), for planar constraint graphs: O(nd3)\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 94,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 853
        },
        "outputId": "830daef1-78cc-4f26-d516-cc19e37ff8ab"
      },
      "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": 95,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nWe use a factored representation for each\nstate: a set of variables, each of which has a value. A problem is solved when each variable\nhas a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem (CSP). CSP search algorithms take advantage of the structure of states and use general rather than domain-specific heuristics to enable the solution of complex problems. \nThe main idea is to eliminate large portions of the search space all at once by identifying variable/value combinations that violate the constraints. An assignment that does not violate any constraints is called a consistent or legal assignment. A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a\nconsistent, complete assignment. \nA partial assignment is one that leaves some variables unassigned, and a partial solution is a partial assignment that is consistent.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n\n1.Node consistency: A single variable (corresponding to a node in the CSP graph) is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\n\n2. Arc consistency: A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints.\n\n\tAC3 Algorithm:  CSP with n variables, each with domain size at most d, and with binary constraints c (arcs).  Each arc (Xk, Xi) can be\ninserted in the queue only d times because Xi has at most d values to delete. So the time is O(cd^3). (arc checking can be done in O(d^2)).\n\n\n3.Path Consistency:  Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n \n\n1. Consistent assignment: does not violate constraints\n\n2. Complete assignment: every variable is assigned a value\n\n3. Solution to CSP: Complete, consistent assignment\n\nForward checking: removes some possibilities, but does not estimate failure. Terminate when any of the unassigned variables have no values to be assigned.\n\nAC3 Worst case: O(n2d3), for planar constraint graphs: O(nd3)\n\n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"  \n",
        "Knowledge Base (KB): set of sentences. Each sentence is represented as a knowledge repr language.  When the sentence is taken as being given\n",
        "without being derived from other sentences, we call it an axiom.\n",
        "\"\"\"\n",
        "\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"KB\" : \"set of sentences\",\n",
        "\"axiom\": \"sentence that is not derived from other sentences\",\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 96,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 552
        },
        "outputId": "2c92f8b2-8dd4-4d51-af27-eb3b42a5bdf0"
      },
      "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": 97,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n  \nKnowledge Base (KB): set of sentences. Each sentence is represented as a knowledge repr language.  When the sentence is taken as being given\nwithout being derived from other sentences, we call it an axiom.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n\n\n\n\n## Module 7 Definitions\n* **Kb** - set of sentences\n* **Axiom** - sentence that is not derived from other sentences\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": {
        "id": "T3cm1WV542_a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "ff7bd3e1-33b0-40d1-b656-e5d154313ab4"
      },
      "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": 98,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Everything in the definition section.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n \nDepends on: \n1. performance measure \n2. agent's prior knowlegde of the environment \n3. actions that the agent can perform \n4. agent's percept sequence to date.\n\n\n\n## AIMA 2.3 The Nature of Environments\n Lecture notes \n\n## AIMA 2.4 The Structure of Agents\n The job of AI is to design an agent program that implements the agent function—the mapping from percepts to actions. \nWe assume this program will run on some sort of computing device with physical sensors and actuators—we call this the agent architecture: agent = architecture + program \n\n## Module 1 Lecture Notes\n \nTask environment properties:\n\n1. Fully observable, partially observable\n\n2. Deterministic, Non-deterministic, stochastic\n\n3. Episodic, sequential (dependency on previous actions)\n\n4. Static, Dynamic\n\n5. Discrete, continuous\n\n6. Single, multiagent\n\n\nHardest environment: continuous, partially observable, stochastic, multiagent. \n\nReflex agent vs problem solving - only current percent vs plan ahead.\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive (sense) and act (actuate) in an environment\n* **Percept** - agent's perceptual inputs at any given instance\n* **Percept sequence** - complete history of everything perceived by the agent\n* **Agent function** - mapping of percept sequence to an action\n* **Agent program** - agent function is implemented by an agent program\n* **Rational agent** - does the right thing\n* **Rational_agent** - For each possible percept sequence, a rational agent should select an action that is expected to\nmaximize its performance measure\n* **Task environment** - problems to which agents provide solutions (PEAS - performance, env, actuator, sensor)\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\nBest first search (graph algo): choose a node, with a minimum value of some eval function say f(n). If the node is the goal state, you return that solution, if not - you expand the current node. Redundant paths - include cycles (loopy path), checking a state again, etc. We call a search algo a graph search if it checks for redundant paths, and tree search if it does not.\n\n Measuring problem solving performance: \n1. Completeness: If there exists a solution, does the algo return it? If not does it report failure correctly? \n2. Cost Optimality: Does it find the path with the least cost? \n\n3. Time complexity \n4. Space Complexity. \n\nSpace/time complexity is usually measured in terms of |V| and |E| of a graph, but other factors could be d: depth of a tree/graph, m: maximum moves to reach the goal state and b: branching factor.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n \n3.4.1 *Bread First Search*: (FIFO) This is appropriate when all actions have the same cost. Root is expanded, all successors of the root node are expanded, then their successors and so on. We can call BFS best first with f(n) to be depth of the node, i.e., the actions needed to reach the node. \nWe use FIFO queue instead of priority queue for efficiency. We can use early-goal-test, rather than late goal test (wait until node is popped off from the Q) as in best first. This is checking if a node is goal node as soon as it is generated.  \nPerformance: BFS is cost optimal for problems having same action cost. It is complete. Time and space complexity are both O(b^d), since all nodes remain in memory.\n\n\n3.4.2 *Dijkstra/Uniform cost search*: When actions have diff costs, use best-first search with eval fn = cost of path from root to curr node. \nComplexity is given in terms of C*, cost of optimal solution. And epsilon (E), E>0, where E is the lower bound of each action cost. Worst case time and space complexity is:\n $$O(b^{1 + (C*/E)})$$ This can be worse than BFS. Uniform-cost search is complete and cost optimal. It never gets caught down a single path infinite path, always chooses paths systematically in terms of increasing costs.\n \n\n3.4.3 *Depth first search*: (LIFO) Always expands the deepest node in the frontier first. It can be called bestFS with eval fn negative of the depth. This is a tree search where it does not keep track of reached states.\nDFS is not cost-optimal. It returns the solution it finds first, even if it is not lowest cost. For finite space it is complete. In cyclic state spaces it can get stuck in an infinite loop. In infinite state spaces, depth-first\nsearch is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus DFS is incomplete.\nSpace complexity is $$O(bm)$$ Here, m is the maximum depth of the tree. We use DFS when you need a tree like search and memory efficiency. Variation of DFS is backtracking search, which uses even lesser memory, since it expands one node at a time. which is O(m).\n\n\n3.4.4 *Depth limited & Iterative deepening search*: Set depth to l so that no problem of infite loop. Time: O(b^l), Space: O(bl). IMportant: choice of l. Iterative deepening is same as depth limited, except it tries all values of l: 0,1,...until a solution is found, or you surpass cutoff value.\nSpaceL O(bd) if there is a solution, O(bm) if no solution. Complete, cost optimal.\n\n\n3.4.5 *Bidirectional search*: Search forward from initial and backwards from goal state; hope the two will meet. Motivation: b^(d/2) + b^(d/2) < b^d.\nComplete, cost optimal. Time, space both O(b^d/2)\n\n\n\n## Module 3 Lecture Notes\n State vs Node: state is representation of a physical configuration, node is data structure - part of search tree. \n\nGraph search: simple modification to tree search, check if a node has been visited before.\n\nUninformed search: all nodes have equal importance, informed search: some nodes are ranked higher than the others.\n\nUse DFS: \n1. Space is restricted \n2. There are many possible solutions with long paths and wrong paths are usually\nterminated quickly \n3. Search can be fine-tuned quickly\n\nUse BFS: \n1. Possible infinite paths \n2. Some solutions have short paths \n3. Can quickly discard unlikely paths\n\nDepth limited: \n1. if l=d, optimal \n2. l<d incomplete \n3. l>d not optimal\n\nID-DFS: \n1. Complete, time O(b^d), space O(bd), optimal if step cost=1\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Goal formulation** - goal state - organize the behavior by limiting objectives and hence actions\n* **Problem formulation** - description of states and actions to reach the goal\n* **Search** - agent simulates actions in its model, searching till it finds a solution that reaches the goal\n* **Search problem** - states, state space, initial and goal state, actions, transition model, action cost function\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nHints from heuristic function and the domain. \n\n3.5.1 *Greedy Best-first search*: expands nodes closest to the goal, f(n) = h(n). Complete in finite spaces, incomplete otherwise. Worst time and space complexity is O(|V|), this can be reduced to O(bm) with good heuristic.\n\n3.5.2 *A * search*: f(n) = g(n) + h(n); g(n) is the path cost from the initial state to node and h(n) is the estimated cost of the shortest path from to a goal state, so f(n) is estimated cost of the best path that continues from n to a goal.\nA* is complete. Cost optimality depends on the chosen heuristic. Admissibility, Consistency - A heuristic is consistent if, for every node n and every successor n, of generated by an action we have h(n) <= c(n,a,n') + h(n'). Every consistent heuristic is admissible, not vice versa.\nA* is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.  If we allow A* search to use an\ninadmissible heuristic—one that may overestimate, then we may miss the optimal solution, but the heuristic can potentially be more accurate, thereby reducing the number of\nnodes expanded. Weighted A* search - g(n) + W*h(n). \nIn bounded suboptimal search, we look for a solution that is guaranteed to be within a constant factor W of the optimal cost. Weighted A* provides this guarantee. \nIn bounded-cost search, we look for a solution whose cost is less than some constant C. And in unbounded-cost search, we accept a solution of any cost,\nas long as we can find it quickly. \n\n3.5.5 *Memory Bounded Search* - drawback of A*, use of space. Beam Search - reduces the size of the frontier. Keep best k-nodes with best f-scores. Incomplete and suboptimal.\nIDA* - e benefits of A* without the requirement to keep all reached states in memory, at a cost of visiting some states multiple times. Recursive Best First Search - rather than continuing indefinitely down the current path, it uses the f_limit\nvariable to keep track of the f-value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path.\nBidirectional Heuristic Search - lb(m, n) = max(gF (m) + gB(n), fF (m), fB(n)).\n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n \nRelaxed problems: The graph of the relaxed problem is a supergraph of the og state space. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.\nIf a collection of admissible heuristics {h1, h2..} is available, then h(n) which is composite heuristic picks the one that is most accurate on node n. h(n) is admissible and consistent, and dominates its subcomponents.\nDifferential heuristic: hDH(n) = max(L∈Landmarks)|C ∗(n,L) − C∗(goal,L)|\n\n\n## Module 4 Lecture Notes\n \nAdmissible heuristics: \nh(n) <= h*(n) where h*(n) is the true cost from n\nh(n) >= 0 so h(G)=0 for any goal G\n\nIf h2(n) ≥ h1(n) for all n (both admissible), then h2 dominates h1; So h2 is optimistic, but more accurate than h1.\n\n\n## Module 4 Definitions\n* **Admissible heuristic** - a heuristic that never over-estimates the cost to reach the goal node, it is optimistic\n* **Relaxed problem** - A problem with fewer restrictions on the actions\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \nGame theory: Most commonly studied games are deterministic, 2 player, turn-taking, perfect-info (fully observable), zero-sum games (what is good for one player is bad for another, no win-win situation).\nTWO players - MAX and MIN, max plays first move. Chess is a zero sum game.\n \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n5.2.1 Minimax Algorithm: It is a recursive algorithm that proceeds all the way down to the leaves of the tree and then backs up the minimax values through the tree as the recursion unwinds. \n\n5.2.3 Alpha-beta pruning: Algo: \n\nSuppose, MINIMAX(root) = max(min(3,12,8), min(2,x,y), min(14,5,2)) = max(3,z,2) where z = min(2,x,y) ≤ 2 \n\n\nThe value of the root and hence the minimax decision are independent of the values of the leaves x and y, and therefore they can be pruned.\n\n5.2.4 Move ordering: The effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. \nIf this could be done properly, alpha–beta will examine only O(b^m/2) nodes to pick the best move, instead of O(b^m) for minimax. Effective branching\nfactor becomes sqrt(b) instead of b — and for chess, about 6 instead of 35. \n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nA heuristic evaluation function EVAL(S,P) returns an estimate of the expected utility of state s to player p.\n\n\n## AIMA Chapter 5.5 Stochastic Games\nExpectiminimax value for games with chance nodes - stochastic games, a generalization of the minimax value for deterministic games. \nTerminal, MAX and MIN nodes work exactly as before. \nFor chance nodes we compute the expected value, which is the sum of the value over all outcomes, weighted by the probability of each chance action.\nEvaluation 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). \nExpectiminimax time: is also considering all the possible dice-roll sequences,\nit will take O(b^m * n^m), where n is the number of distinct rolls.\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\nSimplest game environment: multiagent, static, discrete, fully observable, strategic\n\nExpectimax search: compute the average score under optimal play, calculate the expected utility, so (replace min with expecti-basically)\n\n\n\n## Module 5 Definitions\n* **Move** - action\n* **Position** - state\n* **Terminal state** - state where game has ended\n* **Utility function (objective/payoff fn)** - defines the final numeric value to player p when the game ends in terminal state s\n* **Killer moves** - best moves\n* **Transposition** - different permutations of the move sequence that end up in the same position.\n* **Stochastic game** - includes some randomness that mimics real life, e.g., backgammon or throwing of a dice\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nWe use a factored representation for each\nstate: a set of variables, each of which has a value. A problem is solved when each variable\nhas a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem (CSP). CSP search algorithms take advantage of the structure of states and use general rather than domain-specific heuristics to enable the solution of complex problems. \nThe main idea is to eliminate large portions of the search space all at once by identifying variable/value combinations that violate the constraints. An assignment that does not violate any constraints is called a consistent or legal assignment. A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a\nconsistent, complete assignment. \nA partial assignment is one that leaves some variables unassigned, and a partial solution is a partial assignment that is consistent.\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n\n1.Node consistency: A single variable (corresponding to a node in the CSP graph) is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.\n\n2. Arc consistency: A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints.\n\n\tAC3 Algorithm:  CSP with n variables, each with domain size at most d, and with binary constraints c (arcs).  Each arc (Xk, Xi) can be\ninserted in the queue only d times because Xi has at most d values to delete. So the time is O(cd^3). (arc checking can be done in O(d^2)).\n\n\n3.Path Consistency:  Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n \n\n1. Consistent assignment: does not violate constraints\n\n2. Complete assignment: every variable is assigned a value\n\n3. Solution to CSP: Complete, consistent assignment\n\nForward checking: removes some possibilities, but does not estimate failure. Terminate when any of the unassigned variables have no values to be assigned.\n\nAC3 Worst case: O(n2d3), for planar constraint graphs: O(nd3)\n\n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n  \nKnowledge Base (KB): set of sentences. Each sentence is represented as a knowledge repr language.  When the sentence is taken as being given\nwithout being derived from other sentences, we call it an axiom.\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n\n\n\n\n## Module 7 Definitions\n* **Kb** - set of sentences\n* **Axiom** - sentence that is not derived from other sentences\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}