{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8ae001e9-f651-445d-ba2f-7527a0713a81"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "86c0a48c-ff3b-4980-ef8a-b724f43443d5"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"Intelligence can be defined in terms of both human peformance and ration performance, \\\n",
        "                and can also be identified as a property of internal though vs intelligent behavior. \\\n",
        "                The Turing Test requires NLP, knowledge representation, automated reasoning, and \\\n",
        "                meachine learning in order to be passed by a computer. Robots need computer vision \\\n",
        "                and the ability to manipulate objects and move. Human thought can be learned about \\\n",
        "                through introspection, psychological experiments, and brain imaging. Agents are \\\n",
        "                considerd rational if they act so as to achieve the best outcome (which can be \\\n",
        "                mathematically well defined. The value alignment problem is one in which we have \\\n",
        "                to find balance between our true perferences and the objective of the machine. \"\"\" \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 is the idea that machines could act as if they were intelligent, while \\\n",
        "                 strong AI (general AI) assets that machines actually are thinking. Turing argued \\\n",
        "                 that human behavior cannot fully be codified. They critized GOFAI and claimed that \\\n",
        "                 machines are limited by the incompleteness theorem, but humans also have sentences \\\n",
        "                 that cannot be logically consistent (paradoxes). In the Turing Test no well trained \\\n",
        "                 judge has been fooled.\"\"\"\n",
        "chapter27_2 = \"\"\"The Chinese room experiment is one that shows that a machine does not need to have \\\n",
        "                 understanding to solve a task. The inventor believes in biological naturalism which \\\n",
        "                 claims neurons have features transistors cannot match. Qualia is the intrinsic nature \\\n",
        "                 of experiences. Consciousness, however, remains hard to define, but it may not really \\\n",
        "                 matter, as we do not care if programs are intelligent, more that they behave intelligently.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"Agents perceive through sensors and act through actuators. Percept sequences are the history \\\n",
        "                of everything an agent has seen, and agent functions map percepts to actions, while agent \n",
        "                programs are concrete implementations of these functions.\"\"\"\n",
        "chapter2_2 = \"\"\"We evaluate a rational agents behavior through consequences. We design a performance measure to \\\n",
        "                evaluate the sequences of environment states. Rationality maximizes expected performance while \\\n",
        "                perfection maximizes actual performance. Agents gather into to modify future percepts and learn \\\n",
        "                from their percepts.\"\"\"\n",
        "chapter2_3 = \"\"\"The task environment is PEAS (performance, env, actuators, sensors). These can be fully or partially \\\n",
        "                observable, single-agent vs multi-agent, competitive vs cooperative, deterministic or nondeterministic \\\n",
        "                and it can be stoochastic (nondeterministic with listed probabilities). Additionally environments can \\\n",
        "                be episodic vs sequential and static vs dynamic, as well as discrete vs continuous. \"\"\"\n",
        "chapter2_4 = \"\"\"Agents have architectures and programs. Some exmaples of programs include table lookup and neural networks. \\\n",
        "                Simple reflex agents select actions based on the current percept. Infinite loops often happens, which can be \\\n",
        "                fixed with randomization. Model based reflex agents keep an internal state based on percept history. The \\\n",
        "                transitional model and sensor model together make a model-based agent. Goal based agents give goal info that \\\n",
        "                an agent must achieve. Search and planning are subfields that help with these. Utility based agents make the \\\n",
        "                move that optimizes expected utility. These can all be learning agents, which have a learning element to make \\\n",
        "                improvements and a performance element to select external actions. A problem generator suggests actions that \\\n",
        "                will allow the agent to learn. We can represent agent programs from an atomic (black box) structure, a factored \\\n",
        "                structure (variables that each have values), or structured representation (objects and relations are decribed \\\n",
        "                explicity). these have increasing expressiveness.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"Thinking vs acting humanly and thinking vs acting rationally are 4 views of AI. \\\n",
        "                           The hardest env is continuous, partially observable, stochastic, and multiagent.\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"the content an agents sensors interpret\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 997
        },
        "cellView": "form",
        "outputId": "84b8a7b2-21f4-49ea-99ba-a29b64cfdc58"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nIntelligence can be defined in terms of both human peformance and ration performance,                 and can also be identified as a property of internal though vs intelligent behavior.                 The Turing Test requires NLP, knowledge representation, automated reasoning, and                 meachine learning in order to be passed by a computer. Robots need computer vision                 and the ability to manipulate objects and move. Human thought can be learned about                 through introspection, psychological experiments, and brain imaging. Agents are                 considerd rational if they act so as to achieve the best outcome (which can be                 mathematically well defined. The value alignment problem is one in which we have                 to find balance between our true perferences and the objective of the machine. \n\n## AIMA Chapter 27.1 The Limits of AI\nWeak AI is the idea that machines could act as if they were intelligent, while                  strong AI (general AI) assets that machines actually are thinking. Turing argued                  that human behavior cannot fully be codified. They critized GOFAI and claimed that                  machines are limited by the incompleteness theorem, but humans also have sentences                  that cannot be logically consistent (paradoxes). In the Turing Test no well trained                  judge has been fooled.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nThe Chinese room experiment is one that shows that a machine does not need to have                  understanding to solve a task. The inventor believes in biological naturalism which                  claims neurons have features transistors cannot match. Qualia is the intrinsic nature                  of experiences. Consciousness, however, remains hard to define, but it may not really                  matter, as we do not care if programs are intelligent, more that they behave intelligently.\n\n## AIMA 2.1 Agents and Environments\nAgents perceive through sensors and act through actuators. Percept sequences are the history                 of everything an agent has seen, and agent functions map percepts to actions, while agent \n                programs are concrete implementations of these functions.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nWe evaluate a rational agents behavior through consequences. We design a performance measure to                 evaluate the sequences of environment states. Rationality maximizes expected performance while                 perfection maximizes actual performance. Agents gather into to modify future percepts and learn                 from their percepts.\n\n## AIMA 2.3 The Nature of Environments\nThe task environment is PEAS (performance, env, actuators, sensors). These can be fully or partially                 observable, single-agent vs multi-agent, competitive vs cooperative, deterministic or nondeterministic                 and it can be stoochastic (nondeterministic with listed probabilities). Additionally environments can                 be episodic vs sequential and static vs dynamic, as well as discrete vs continuous. \n\n## AIMA 2.4 The Structure of Agents\nAgents have architectures and programs. Some exmaples of programs include table lookup and neural networks.                 Simple reflex agents select actions based on the current percept. Infinite loops often happens, which can be                 fixed with randomization. Model based reflex agents keep an internal state based on percept history. The                 transitional model and sensor model together make a model-based agent. Goal based agents give goal info that                 an agent must achieve. Search and planning are subfields that help with these. Utility based agents make the                 move that optimizes expected utility. These can all be learning agents, which have a learning element to make                 improvements and a performance element to select external actions. A problem generator suggests actions that                 will allow the agent to learn. We can represent agent programs from an atomic (black box) structure, a factored                 structure (variables that each have values), or structured representation (objects and relations are decribed                 explicity). these have increasing expressiveness.\n\n## Module 1 Lecture Notes\nThinking vs acting humanly and thinking vs acting rationally are 4 views of AI.                            The hardest env is continuous, partially observable, stochastic, and multiagent.\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - the content an agents sensors interpret\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 = \"\"\"Python is strongly typed, with all data being treated as objects \\\n",
        "                           , but it has dynamic typing. String are immutable and can be made with \\\n",
        "                           single or double quotes. Multiline should have triple qoutes. Functions \\\n",
        "                           can return multiple values, functions cannot be overloaded. *args is a \\\n",
        "                           tuple of arguments passed to the function. **kwargs is a dict of keyword \\\n",
        "                           arguments passed to the function. Default parameters only evaluated when the \\\n",
        "                           function is first called, meaning not recursively. Functions can be used as \\\n",
        "                           variables. Magic methods like __len__, __init__, __copy__, allow classes \\\n",
        "                           to behave like built in types. Duck typing establishes suitability of objects \\\n",
        "                           by checking for presence of methods. Iterators are objects with an iter method. \\\n",
        "                           Generators are created using yield, they are just more memory efficient.\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"can be changed without creating new\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 277
        },
        "outputId": "e270b9d5-baf6-40e7-9832-b4e56033d170"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\nPython is strongly typed, with all data being treated as objects                            , but it has dynamic typing. String are immutable and can be made with                            single or double quotes. Multiline should have triple qoutes. Functions                            can return multiple values, functions cannot be overloaded. *args is a                            tuple of arguments passed to the function. **kwargs is a dict of keyword                            arguments passed to the function. Default parameters only evaluated when the                            function is first called, meaning not recursively. Functions can be used as                            variables. Magic methods like __len__, __init__, __copy__, allow classes                            to behave like built in types. Duck typing establishes suitability of objects                            by checking for presence of methods. Iterators are objects with an iter method.                            Generators are created using yield, they are just more memory efficient.\n\n## Module 2 Definitions\n* **Mutability** - can be changed without creating new\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 = \"\"\"In order to solve a problem, an agent can formulate a goal, devise a description \\\n",
        "                of states and actions to reach it, search the environment to find a solution \\\n",
        "                by simulating in its model, and then execute in the environment. Search problems \\\n",
        "                are formulated with goal states, intial states, transition models, action cost, \\\n",
        "                states, actions.\"\"\"\n",
        "chapter3_2 = \"\"\"The best known task environments are listed here - standardized problems. Grid world \\\n",
        "                is a 2D array of cells where an agent movees from cell to cell. Sokoban puzzle is one \\ \n",
        "                where an agent must push boxes to designated locations. Sliding tile is another. Route \\\n",
        "                finding are another class of common problems, as are touring problems where we must visit \\\n",
        "                every destination in a set.\"\"\"\n",
        "chapter3_3 = \"\"\"Search algorithms map from search problems to solutions or an indication of failure. We \\\n",
        "                can superimpose a search treee over the state-space graph. The root is the initial states \\\n",
        "                and each node corresponds to a state in the state space. The distinction between search algos \\\n",
        "                are which nodes to expand next. Best-first search expands the node with minimum value of \\\n",
        "                some evaluation function. Graph searches check for redunbdant paths while tree searches \\\n",
        "                do not. Algorithms can be complete, optimal, and have time and space complexity.\"\"\"\n",
        "chapter3_4 = \"\"\"When all actions have the same cost, we use BFS in which nodes are expanded based on distance \\\n",
        "                to the root, with the closest being expanded first. This is complete and can use a FIFO queue. \\\n",
        "                Early goal tests can be used meaning checking when a node is generated vs expanded. It is optimal \\\n",
        "                if all actions have the same cost, otherwisee not, but always complete. It has complexity $O(b^d)$. \\\n",
        "                Uniform cost search (or Dijktra's), uses path cost as an evaluation function for best-first search. \\\n",
        "                This is both complete and cost optimal (given cost > 0). DFS expands the deepest node first, so inverse BFS \\\n",
        "                where it is implented as tree instead of graph search. It is not cost optimal nor complete, but much more \\\n",
        "                memory efficient $O(bm)$. Backtracking search is DFS that only generates one successor at a time, giving it \\\n",
        "                $O(m)$ memory. Depth-limited is DFS with a depth limit to prevent infinite search. Iterative deepening \\\n",
        "                search increases the depth limit incrementallty. This has the same time complexity as BFS but better space. \\\n",
        "                Bidirectional search searches forward from initial and backwards from goal, and returns a solution when frontiers \\\n",
        "                collide.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"These are defined with S, A, f : S, A -> S, p : A -> C, Goal(s). \\\n",
        "                           Uninformed search means we only have access to the problem defintion, \\\n",
        "                           no external $h(n)$. Informed search gives domain specific info.\"\"\"\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": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 745
        },
        "outputId": "4010de8d-3048-48b6-8941-6d84feedf64d"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nIn order to solve a problem, an agent can formulate a goal, devise a description                 of states and actions to reach it, search the environment to find a solution                 by simulating in its model, and then execute in the environment. Search problems                 are formulated with goal states, intial states, transition models, action cost,                 states, actions.\n\n## AIMA Chapter 3.2 Example Problems\nThe best known task environments are listed here - standardized problems. Grid world                 is a 2D array of cells where an agent movees from cell to cell. Sokoban puzzle is one \\ \n                where an agent must push boxes to designated locations. Sliding tile is another. Route                 finding are another class of common problems, as are touring problems where we must visit                 every destination in a set.\n\n## AIMA Chapter 3.3 Search Algorithms\nSearch algorithms map from search problems to solutions or an indication of failure. We                 can superimpose a search treee over the state-space graph. The root is the initial states                 and each node corresponds to a state in the state space. The distinction between search algos                 are which nodes to expand next. Best-first search expands the node with minimum value of                 some evaluation function. Graph searches check for redunbdant paths while tree searches                 do not. Algorithms can be complete, optimal, and have time and space complexity.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nWhen all actions have the same cost, we use BFS in which nodes are expanded based on distance                 to the root, with the closest being expanded first. This is complete and can use a FIFO queue.                 Early goal tests can be used meaning checking when a node is generated vs expanded. It is optimal                 if all actions have the same cost, otherwisee not, but always complete. It has complexity $O(b^d)$.                 Uniform cost search (or Dijktra's), uses path cost as an evaluation function for best-first search.                 This is both complete and cost optimal (given cost > 0). DFS expands the deepest node first, so inverse BFS                 where it is implented as tree instead of graph search. It is not cost optimal nor complete, but much more                 memory efficient $O(bm)$. Backtracking search is DFS that only generates one successor at a time, giving it                 $O(m)$ memory. Depth-limited is DFS with a depth limit to prevent infinite search. Iterative deepening                 search increases the depth limit incrementallty. This has the same time complexity as BFS but better space.                 Bidirectional search searches forward from initial and backwards from goal, and returns a solution when frontiers                 collide.\n\n## Module 3 Lecture Notes\nThese are defined with S, A, f : S, A -> S, p : A -> C, Goal(s).                            Uninformed search means we only have access to the problem defintion,                            no external $h(n)$. Informed search gives domain specific info.\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 = \"\"\"Beam search limits the size of the frontier to the best k nodes, making it suboptimal but more \\\n",
        "                memory efficient. Iterative deepening A* (IDA*) is essentially A* with the cutoff being $f(n)$ \\\n",
        "                instead of depth. The next iteration has a cutoff of the lowest value which exceeded the cutoff \\\n",
        "                in the previous. Recursive best-first is essentially DFS but only traverses a path until it does \\\n",
        "                not exceed some $f_limit$. This is optimal given an admissible heuristic. However, they may explore \\\n",
        "                the same states over and over due to using too little memory.\\\n",
        "                \\\n",
        "                MA* and SMA* are memory bounded A* which expand until memory is full, at which point it drops the \\\n",
        "                worst leaf node and backs up the value to its parent. This is complete diven a reachable solution \\\n",
        "                in the memory size. This heuristic search can also be bidirectional. You can do front to end, which \\\n",
        "                gives a heuristic from the current to the end, or front-to-front where the heuristic is between frontiers.\"\"\"\n",
        "chapter3_6 = \"\"\"The quality of a heuristic can be characterized by the effective branching factor. Heuristics can \\\n",
        "                dominate another if it is always better at every state. In order to create heuristics we can relax \\\n",
        "                a problem, meaning to allow moves with fewer restrictions. This adds edges to the state-space graph. \\\n",
        "                We can also create an admissible heuristic by taking the maximum of a set of admissible heuristics. \\\n",
        "                We can also design heuristics from solution costs of subproblems. A perfect heuristic could be generated \\\n",
        "                by precomputing the cost of the optimal path between each pair of vertices. This can even be done for \\\n",
        "                some landmark points. Some route finding algorithms also add edges as shortcuts. Differential heuristics \\\n",
        "                subtract the exact distance from current to L beyond and the goal to L beyond to get current to goal. \\\n",
        "                Agents can also learn to search better through the metalevel state space. Also, heursitics can be \\\n",
        "                learned through experience, meaning we can use machine learning to predict $h(n)$ given a state.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"$h(n)$ is the estimated cost of the cheapest path from the current to the goal state. \\\n",
        "                Greedy best-first search expands the node with lowest $h(n)$ value. This is complete. \n",
        "                The most common informed search is A*, where we use evaluation function $g(n) + h(n)$, \\\n",
        "                where g(n) is the actual cost from the initial to current node. It is complete and optimal \\\n",
        "                given an admissible heuristic. If a heuristic is consistent the difference between h for \\\n",
        "                a node and its child is bounded by some function. Consistent heuristics mean we will only \\\n",
        "                reach a state on its optimal path. $f(n)$ monotonically increases if the heuristic is \\\n",
        "                consistent. Inadmisssible heuristics can give non-optimal but good enough solutions. Thus \\\n",
        "                weighted A* uses $f(n) = g(n) + W * h(n)$ for some $W > 1$. A* uses a lot of memory, and \\\n",
        "                we can fix this by removing states from reached when they cannot be reached anymore.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissible\" : \"heuristic underestimates actual distance to goal\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 629
        },
        "cellView": "form",
        "outputId": "9d94ba08-0b2a-40c4-e6d6-977ed3e4f6d1"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nBeam search limits the size of the frontier to the best k nodes, making it suboptimal but more                 memory efficient. Iterative deepening A* (IDA*) is essentially A* with the cutoff being $f(n)$                 instead of depth. The next iteration has a cutoff of the lowest value which exceeded the cutoff                 in the previous. Recursive best-first is essentially DFS but only traverses a path until it does                 not exceed some $f_limit$. This is optimal given an admissible heuristic. However, they may explore                 the same states over and over due to using too little memory.                                MA* and SMA* are memory bounded A* which expand until memory is full, at which point it drops the                 worst leaf node and backs up the value to its parent. This is complete diven a reachable solution                 in the memory size. This heuristic search can also be bidirectional. You can do front to end, which                 gives a heuristic from the current to the end, or front-to-front where the heuristic is between frontiers.\n\n## AIMA Chapter 3.6 Heuristic Functions\nThe quality of a heuristic can be characterized by the effective branching factor. Heuristics can                 dominate another if it is always better at every state. In order to create heuristics we can relax                 a problem, meaning to allow moves with fewer restrictions. This adds edges to the state-space graph.                 We can also create an admissible heuristic by taking the maximum of a set of admissible heuristics.                 We can also design heuristics from solution costs of subproblems. A perfect heuristic could be generated                 by precomputing the cost of the optimal path between each pair of vertices. This can even be done for                 some landmark points. Some route finding algorithms also add edges as shortcuts. Differential heuristics                 subtract the exact distance from current to L beyond and the goal to L beyond to get current to goal.                 Agents can also learn to search better through the metalevel state space. Also, heursitics can be                 learned through experience, meaning we can use machine learning to predict $h(n)$ given a state.\n\n## Module 4 Lecture Notes\n$h(n)$ is the estimated cost of the cheapest path from the current to the goal state.                 Greedy best-first search expands the node with lowest $h(n)$ value. This is complete. \n                The most common informed search is A*, where we use evaluation function $g(n) + h(n)$,                 where g(n) is the actual cost from the initial to current node. It is complete and optimal                 given an admissible heuristic. If a heuristic is consistent the difference between h for                 a node and its child is bounded by some function. Consistent heuristics mean we will only                 reach a state on its optimal path. $f(n)$ monotonically increases if the heuristic is                 consistent. Inadmisssible heuristics can give non-optimal but good enough solutions. Thus                 weighted A* uses $f(n) = g(n) + W * h(n)$ for some $W > 1$. A* uses a lot of memory, and                 we can fix this by removing states from reached when they cannot be reached anymore.\n\n## Module 4 Definitions\n* **Admissible** - heuristic underestimates actual distance to goal\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 = \"\"\"Most commonly studied games include deterministic, two-player, turn-taking \\\n",
        "                perfect information, zero-sum games. This mans that they are fully observable and \\\n",
        "                what is good for one player is bad for the other. The players are max and min, \\\n",
        "                with max moving first and then turns being taken. We can superimpose trees on \\\n",
        "                games as well.\"\"\"\n",
        "chapter5_2 = \"\"\"Given a game tree, we can find the minimax value of each state \\\n",
        "                which is the utility of the state for max. Thus, the minimax value is the optimal \\\n",
        "                value of its children depending on whos move it is. We can extend this algorithm \\\n",
        "                to multiplayer games. We can have a vector associated with each node for the number \\\n",
        "                of players and have players choose move which maximize their utility in the same \\\n",
        "                manner. Alpha-beta pruning has $\\alpha$ be at least where $\\beta$ is at most. \\\n",
        "                This means alpha is the best value for max and beta is the best value most min. \\\n",
        "                Alpha beta pruning depends heavily on the order in which the moves are examined. \\\n",
        "                Type A strategies explore all possible moves to a certain depth while Type B explore \\\n",
        "                promising lines as far as possible. \"\"\"\n",
        "chapter5_3 = \"\"\"Heuristic evaluation functions return an estimate of expected utility of a state \\\n",
        "                for a specific player. For nonterminal states this is between the utility of a loss \\\n",
        "                and a win. These functions are often calculated using a set of features and a weight \\\n",
        "                given to those features. An evaluation function should be strongly correlated with the \\\n",
        "                chance of winning. We then use this evaluation function with a cutoff to terminate early \\\n",
        "                if there are no quiescient moves. We must also eliminate the horizon effect where there is \\\n",
        "                an unavoidable move that will cause damage at some point in the future. We can mitigate \\\n",
        "                this by allowing singular extensions where we can make moves that are clearly better even \\\n",
        "                aftett the cutoff. Forward pruning prunes moves which appear to be poor. This is similar to \\\n",
        "                beam search, where you only consider the few best moves. Probabilistic cut prunes moves using \\\n",
        "                statistics from prior experience. For the opening and ending, many programs use table lookup \\\n",
        "                rather than search and rely mostly on the expertise of humans. \"\"\"\n",
        "chapter5_5 = \"\"\"Stochastic games include a random element. For these, game trees must include chance nodes \\\n",
        "                in addition to the min and max nodes. Instead of minimax, we can now calculate expected values \\\n",
        "                of positions. This gives the expectiminimax value of games with chance nodees. The eval function \\\n",
        "                must return values that are a positive linear transformation of the win probability. You can prune \\\n",
        "                chance nodes by bounding the value of its utility.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"The principle of maximum expected utility says that a rational agent should choose \\\n",
        "                 the action that maximizes its expected utility. However, in order to do this the agent \\\n",
        "                 must have a causal model of the world already.\"\"\"\n",
        "chapter16_2 = \"\"\"Given two lotteries (atomic states or another lottery), a rational agent must prefer one \\\n",
        "                 or be indifferent. They should be transitive, substitue indifferent loterries, monotonic, \\\n",
        "                 and continuous (as well as decompisble). If an agent's preferences satisfy all of these, \\\n",
        "                 there exists a utility function that satisfies these. \"\"\"\n",
        "chapter16_3 = \"\"\"Utility functions map lotteries to numbers. We can use preference elicitation for an agent \\\n",
        "                 to define its utility function. Utilities can be normalized to 0 and 1 to compare. Then, if \\\n",
        "                 you ask an agent to choose between S and a standard lottery $p*1 + (1-p)*0$, we adjust \\\n",
        "                 p until indifferent and the normalized utility of S is p. The value an agent will accept in \\\n",
        "                 lieue of a lottery is called the certainty equivalent of that lottery. Human agents have \\\n",
        "                 ambiguity aversion and also act irrationally due to emotion.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"alpha is max's current lower bound on their outcome, and \\\n",
        "                           beta is mins current upper bound on their outcome. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"quiescient move\" : \"a pending move that wildly swings the evaluation\", \n",
        "\"micromort\" : \"how much would one pay to avoid death\"   \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "99594c6b-ceb9-4136-f7ff-4dac3feb5014"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nMost commonly studied games include deterministic, two-player, turn-taking                 perfect information, zero-sum games. This mans that they are fully observable and                 what is good for one player is bad for the other. The players are max and min,                 with max moving first and then turns being taken. We can superimpose trees on                 games as well.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nGiven a game tree, we can find the minimax value of each state                 which is the utility of the state for max. Thus, the minimax value is the optimal                 value of its children depending on whos move it is. We can extend this algorithm                 to multiplayer games. We can have a vector associated with each node for the number                 of players and have players choose move which maximize their utility in the same                 manner. Alpha-beta pruning has $\u0007lpha$ be at least where $\beta$ is at most.                 This means alpha is the best value for max and beta is the best value most min.                 Alpha beta pruning depends heavily on the order in which the moves are examined.                 Type A strategies explore all possible moves to a certain depth while Type B explore                 promising lines as far as possible. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nHeuristic evaluation functions return an estimate of expected utility of a state                 for a specific player. For nonterminal states this is between the utility of a loss                 and a win. These functions are often calculated using a set of features and a weight                 given to those features. An evaluation function should be strongly correlated with the                 chance of winning. We then use this evaluation function with a cutoff to terminate early                 if there are no quiescient moves. We must also eliminate the horizon effect where there is                 an unavoidable move that will cause damage at some point in the future. We can mitigate                 this by allowing singular extensions where we can make moves that are clearly better even                 aftett the cutoff. Forward pruning prunes moves which appear to be poor. This is similar to                 beam search, where you only consider the few best moves. Probabilistic cut prunes moves using                 statistics from prior experience. For the opening and ending, many programs use table lookup                 rather than search and rely mostly on the expertise of humans. \n\n## AIMA Chapter 5.5 Stochastic Games\nStochastic games include a random element. For these, game trees must include chance nodes                 in addition to the min and max nodes. Instead of minimax, we can now calculate expected values                 of positions. This gives the expectiminimax value of games with chance nodees. The eval function                 must return values that are a positive linear transformation of the win probability. You can prune                 chance nodes by bounding the value of its utility.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nThe principle of maximum expected utility says that a rational agent should choose                  the action that maximizes its expected utility. However, in order to do this the agent                  must have a causal model of the world already.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nGiven two lotteries (atomic states or another lottery), a rational agent must prefer one                  or be indifferent. They should be transitive, substitue indifferent loterries, monotonic,                  and continuous (as well as decompisble). If an agent's preferences satisfy all of these,                  there exists a utility function that satisfies these. \n\n## AIMA Chapter 16.3 Utility Functions\nUtility functions map lotteries to numbers. We can use preference elicitation for an agent                  to define its utility function. Utilities can be normalized to 0 and 1 to compare. Then, if                  you ask an agent to choose between S and a standard lottery $p*1 + (1-p)*0$, we adjust                  p until indifferent and the normalized utility of S is p. The value an agent will accept in                  lieue of a lottery is called the certainty equivalent of that lottery. Human agents have                  ambiguity aversion and also act irrationally due to emotion.\n\n## Module 5 Lecture Notes\nalpha is max's current lower bound on their outcome, and                            beta is mins current upper bound on their outcome. \n\n## Module 5 Definitions\n* **Quiescient move** - a pending move that wildly swings the evaluation\n* **Micromort** - how much would one pay to avoid death\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 are problems where each state has a set of variables that have values. \\\n",
        "                An assignment that does not violate any constraints is called consistent. \\\n",
        "                A solution is a complete consistent assignment. Unary constraints restrict 1 \\\n",
        "                variable while binary constrains restrict 2 variables. Any CSP can be reduced \\\n",
        "                to a binary contrained CSP. \"\"\"\n",
        "chapter6_2 = \"\"\"Contraint propagation reduces the number of legal moves for a variable by \\\n",
        "                using the constraints. Node consistency is if it satisfied unary constrains. \\\n",
        "                Arc consistency is if every value in a variables domain satisfies its binary \\\n",
        "                contraints. AC3 enforces arc consistency with a queue of ARCs. Path consistency \\\n",
        "                is for 3 variable sets. A CSP is k-consistent if for every seet of k-1 variables \\\n",
        "                and a consistent assignment to those, a consistent value can always be assigned to \\\n",
        "                the kth variable. We can use bounds contraints as well as max and min to eliminate \\\n",
        "                some options from variable domains. \"\"\"\n",
        "chapter6_3 = \"\"\"Backtracking search for CSPs essentially guesses for a partial assignment, \\\n",
        "                then continues to infer, and if we cannot reach a solution it goes back and \\\n",
        "                changes the guess. We can choose variables to assign using the minimum remaining \\\n",
        "                value heuristic. It chooses the most constrained variable, or the one most \\\n",
        "                likely to cause a failure soon. The degree heuristic can also have the same \\\n",
        "                effect here. Then, once we choose a variable, we choose the value to assign \\\n",
        "                using the least constraining value heuristic. After searching, forward checking \\\n",
        "                establishes arc consistency for the new assigned variable by examining all \\\n",
        "                variables connected to it by an arc. Instead of backtracking to the variable \\\n",
        "                we assigned, we can also backtrack to the most recent assignment in the conflict set.\"\"\"\n",
        "chapter6_4 = \"\"\"For CSPs, local search algorithms can be very effective. When we have a conflicting \\\n",
        "                variable in a complete assignment, what we can do is change the value to the one that \\\n",
        "                results in the minimum number of conflicts. Constraint weighting also helps by giving \\\n",
        "                each constraint a specific weight and then changes variables that will result in the \\\n",
        "                lowest total weight of violated constraints.\"\"\"\n",
        "chapter6_5 = \"\"\"We can find independence by finding connected components of the constraint subgraph. \\\n",
        "                We can then solve the subproblems independently. Some CSPs can be tree structured, \\\n",
        "                meaning we can define directional arc consistency and topologically sort the \\\n",
        "                nodes, which then leads to linear time variable assignment. We can reduce regular \\\n",
        "                CSP graphs to trees using cutset conditioning. We can remove nodes by fixing values \\\n",
        "                and removing other inconsistent values. We can also construct a tree decomposition of \\\n",
        "                the constraint graph. We can create a tree where each node in the tree is a set of variables \\\n",
        "                such thaat each variable appears in at least 1 node, two vars connected by a constraint \\\n",
        "                must appear together in a node, and if a var appears in 2 nodes it must appear in \\\n",
        "                every node along the path connecting those nodes. Then, we assign sets of values to each \\\n",
        "                node in the tree and individually solve each subproblem. We try to minimize tree width. \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"soft constrains are preferences that can be represented as costs \\\n",
        "                           for certain variable assignments. \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 813
        },
        "outputId": "bd37969b-1036-4bab-cd30-d0cb12e7bb23"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nCSPs are problems where each state has a set of variables that have values.                 An assignment that does not violate any constraints is called consistent.                 A solution is a complete consistent assignment. Unary constraints restrict 1                 variable while binary constrains restrict 2 variables. Any CSP can be reduced                 to a binary contrained CSP. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nContraint propagation reduces the number of legal moves for a variable by                 using the constraints. Node consistency is if it satisfied unary constrains.                 Arc consistency is if every value in a variables domain satisfies its binary                 contraints. AC3 enforces arc consistency with a queue of ARCs. Path consistency                 is for 3 variable sets. A CSP is k-consistent if for every seet of k-1 variables                 and a consistent assignment to those, a consistent value can always be assigned to                 the kth variable. We can use bounds contraints as well as max and min to eliminate                 some options from variable domains. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nBacktracking search for CSPs essentially guesses for a partial assignment,                 then continues to infer, and if we cannot reach a solution it goes back and                 changes the guess. We can choose variables to assign using the minimum remaining                 value heuristic. It chooses the most constrained variable, or the one most                 likely to cause a failure soon. The degree heuristic can also have the same                 effect here. Then, once we choose a variable, we choose the value to assign                 using the least constraining value heuristic. After searching, forward checking                 establishes arc consistency for the new assigned variable by examining all                 variables connected to it by an arc. Instead of backtracking to the variable                 we assigned, we can also backtrack to the most recent assignment in the conflict set.\n\n## AIMA Chapter 6.4 Local Search for CSPs\nFor CSPs, local search algorithms can be very effective. When we have a conflicting                 variable in a complete assignment, what we can do is change the value to the one that                 results in the minimum number of conflicts. Constraint weighting also helps by giving                 each constraint a specific weight and then changes variables that will result in the                 lowest total weight of violated constraints.\n\n## AIMA Chapter 6.5 The Structure of Problems\nWe can find independence by finding connected components of the constraint subgraph.                 We can then solve the subproblems independently. Some CSPs can be tree structured,                 meaning we can define directional arc consistency and topologically sort the                 nodes, which then leads to linear time variable assignment. We can reduce regular                 CSP graphs to trees using cutset conditioning. We can remove nodes by fixing values                 and removing other inconsistent values. We can also construct a tree decomposition of                 the constraint graph. We can create a tree where each node in the tree is a set of variables                 such thaat each variable appears in at least 1 node, two vars connected by a constraint                 must appear together in a node, and if a var appears in 2 nodes it must appear in                 every node along the path connecting those nodes. Then, we assign sets of values to each                 node in the tree and individually solve each subproblem. We try to minimize tree width. \n\n## Module 6 Lecture Notes\nsoft constrains are preferences that can be represented as costs                            for certain variable assignments. \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 = \"\"\"Knowledge based agents have a set of 'sentences' where each represents \\\n",
        "                some assertion about the world. When it is given without being derived \\\n",
        "                it is an axiom. They have tell and ask functions which are used to \\\n",
        "                update the KB and return an action that should be taken.\"\"\"\n",
        "chapter7_2 = \"\"\"Wumpus World lecture\"\"\"\n",
        "chapter7_3 = \"\"\"If a sentence a is true in a model m, we say m satifies a or m is a \\\n",
        "                model of a. M(a) is the set of all models of a. a entails B means B \\\n",
        "                follows logically from a. Model checking means seeing if a is true in all \\\n",
        "                models where KB is true. An inference algorithms is called sound if \\\n",
        "                it derives only entailed sentences. An inference algorithm is complete \\\n",
        "                if it can derive any sentence that is entailed. \"\"\"\n",
        "chapter7_4 = \"\"\"Propositional logic considers each sentence to be a proposition. TT \\\n",
        "                entails is an algorithm that enumerates all assignments to symnols.\"\"\"\n",
        "chapter7_5 = \"\"\"A sentence is valid if it is true in all models. A sentence is \\\n",
        "                satisfiable if its is true in some model. Given inference rules \\\n",
        "                in the form (expressions) / (expressions) if the numerator is given \\\n",
        "                the denominator can be inferred. CNF form is a conjunction of clauses \\\n",
        "                where conjunction is ands and clauses are made of ors. The resolution \\\n",
        "                rule allows us to resolve sentences together to simplify them. PL-Resolution \\\n",
        "                is a resolution algorithm given CNF of KB implies a in which each pair of \\\n",
        "                clauses that contains complementary literals is combined to produce a new \\\n",
        "                clause which is added to the set. Then if no new clauses can be added for \\\n",
        "                the problem a is not entailed by KB otherwis if we get the empty clause \\\n",
        "                it is entailed. A defininte clause is a disjunction of literals where \\\n",
        "                exactly 1 is positive. The Horn clause is where at most 1 is positive. \\\n",
        "                These are closed under resolution, meaning if you resolve 2 you get a \\\n",
        "                Horn clause. Forward chaining determines if a query is entailed by KB \\\n",
        "                where we add q if we know p implies q and p and this continues until \\\n",
        "                we cannot add anything or the goal query is added. Backward chaining \\\n",
        "                does the reverse where it sees if p implies the query and checks if \\\n",
        "                we can prove p.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"If a entails B that means a is more specific, or stronger than B \\\n",
        "                           as the set of models that satisfy a are a subset of those that satisy B \\\n",
        "                           since a model that satisfied a necesarily satifies B.\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 728
        },
        "outputId": "948e6b1e-a860-4e0f-b80a-5da1dc0aafb4"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nKnowledge based agents have a set of 'sentences' where each represents                 some assertion about the world. When it is given without being derived                 it is an axiom. They have tell and ask functions which are used to                 update the KB and return an action that should be taken.\n\n## AIMA Chapter 7.2 The Wumpus World\nWumpus World lecture\n\n## AIMA Chapter 7.3 Logic\nIf a sentence a is true in a model m, we say m satifies a or m is a                 model of a. M(a) is the set of all models of a. a entails B means B                 follows logically from a. Model checking means seeing if a is true in all                 models where KB is true. An inference algorithms is called sound if                 it derives only entailed sentences. An inference algorithm is complete                 if it can derive any sentence that is entailed. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nPropositional logic considers each sentence to be a proposition. TT                 entails is an algorithm that enumerates all assignments to symnols.\n\n## AIMA 7.5 Propositional Theorem Proving\nA sentence is valid if it is true in all models. A sentence is                 satisfiable if its is true in some model. Given inference rules                 in the form (expressions) / (expressions) if the numerator is given                 the denominator can be inferred. CNF form is a conjunction of clauses                 where conjunction is ands and clauses are made of ors. The resolution                 rule allows us to resolve sentences together to simplify them. PL-Resolution                 is a resolution algorithm given CNF of KB implies a in which each pair of                 clauses that contains complementary literals is combined to produce a new                 clause which is added to the set. Then if no new clauses can be added for                 the problem a is not entailed by KB otherwis if we get the empty clause                 it is entailed. A defininte clause is a disjunction of literals where                 exactly 1 is positive. The Horn clause is where at most 1 is positive.                 These are closed under resolution, meaning if you resolve 2 you get a                 Horn clause. Forward chaining determines if a query is entailed by KB                 where we add q if we know p implies q and p and this continues until                 we cannot add anything or the goal query is added. Backward chaining                 does the reverse where it sees if p implies the query and checks if                 we can prove p.\n\n## Module 7 Lecture Notes\nIf a entails B that means a is more specific, or stronger than B                            as the set of models that satisfy a are a subset of those that satisy B                            since a model that satisfied a necesarily satifies B.\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": "d897fdef-46de-4892-de05-f29c9d06ca06"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nIntelligence can be defined in terms of both human peformance and ration performance,                 and can also be identified as a property of internal though vs intelligent behavior.                 The Turing Test requires NLP, knowledge representation, automated reasoning, and                 meachine learning in order to be passed by a computer. Robots need computer vision                 and the ability to manipulate objects and move. Human thought can be learned about                 through introspection, psychological experiments, and brain imaging. Agents are                 considerd rational if they act so as to achieve the best outcome (which can be                 mathematically well defined. The value alignment problem is one in which we have                 to find balance between our true perferences and the objective of the machine. \n\n## AIMA Chapter 27.1 The Limits of AI\nWeak AI is the idea that machines could act as if they were intelligent, while                  strong AI (general AI) assets that machines actually are thinking. Turing argued                  that human behavior cannot fully be codified. They critized GOFAI and claimed that                  machines are limited by the incompleteness theorem, but humans also have sentences                  that cannot be logically consistent (paradoxes). In the Turing Test no well trained                  judge has been fooled.\n\n## AIMA Chapter 27.1 Can Machines Really Think?\nThe Chinese room experiment is one that shows that a machine does not need to have                  understanding to solve a task. The inventor believes in biological naturalism which                  claims neurons have features transistors cannot match. Qualia is the intrinsic nature                  of experiences. Consciousness, however, remains hard to define, but it may not really                  matter, as we do not care if programs are intelligent, more that they behave intelligently.\n\n## AIMA 2.1 Agents and Environments\nAgents perceive through sensors and act through actuators. Percept sequences are the history                 of everything an agent has seen, and agent functions map percepts to actions, while agent \n                programs are concrete implementations of these functions.\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nWe evaluate a rational agents behavior through consequences. We design a performance measure to                 evaluate the sequences of environment states. Rationality maximizes expected performance while                 perfection maximizes actual performance. Agents gather into to modify future percepts and learn                 from their percepts.\n\n## AIMA 2.3 The Nature of Environments\nThe task environment is PEAS (performance, env, actuators, sensors). These can be fully or partially                 observable, single-agent vs multi-agent, competitive vs cooperative, deterministic or nondeterministic                 and it can be stoochastic (nondeterministic with listed probabilities). Additionally environments can                 be episodic vs sequential and static vs dynamic, as well as discrete vs continuous. \n\n## AIMA 2.4 The Structure of Agents\nAgents have architectures and programs. Some exmaples of programs include table lookup and neural networks.                 Simple reflex agents select actions based on the current percept. Infinite loops often happens, which can be                 fixed with randomization. Model based reflex agents keep an internal state based on percept history. The                 transitional model and sensor model together make a model-based agent. Goal based agents give goal info that                 an agent must achieve. Search and planning are subfields that help with these. Utility based agents make the                 move that optimizes expected utility. These can all be learning agents, which have a learning element to make                 improvements and a performance element to select external actions. A problem generator suggests actions that                 will allow the agent to learn. We can represent agent programs from an atomic (black box) structure, a factored                 structure (variables that each have values), or structured representation (objects and relations are decribed                 explicity). these have increasing expressiveness.\n\n## Module 1 Lecture Notes\nThinking vs acting humanly and thinking vs acting rationally are 4 views of AI.                            The hardest env is continuous, partially observable, stochastic, and multiagent.\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - the content an agents sensors interpret\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\nPython is strongly typed, with all data being treated as objects                            , but it has dynamic typing. String are immutable and can be made with                            single or double quotes. Multiline should have triple qoutes. Functions                            can return multiple values, functions cannot be overloaded. *args is a                            tuple of arguments passed to the function. **kwargs is a dict of keyword                            arguments passed to the function. Default parameters only evaluated when the                            function is first called, meaning not recursively. Functions can be used as                            variables. Magic methods like __len__, __init__, __copy__, allow classes                            to behave like built in types. Duck typing establishes suitability of objects                            by checking for presence of methods. Iterators are objects with an iter method.                            Generators are created using yield, they are just more memory efficient.\n\n## Module 2 Definitions\n* **Mutability** - can be changed without creating new\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nIn order to solve a problem, an agent can formulate a goal, devise a description                 of states and actions to reach it, search the environment to find a solution                 by simulating in its model, and then execute in the environment. Search problems                 are formulated with goal states, intial states, transition models, action cost,                 states, actions.\n\n## AIMA Chapter 3.2 Example Problems\nThe best known task environments are listed here - standardized problems. Grid world                 is a 2D array of cells where an agent movees from cell to cell. Sokoban puzzle is one \\ \n                where an agent must push boxes to designated locations. Sliding tile is another. Route                 finding are another class of common problems, as are touring problems where we must visit                 every destination in a set.\n\n## AIMA Chapter 3.3 Search Algorithms\nSearch algorithms map from search problems to solutions or an indication of failure. We                 can superimpose a search treee over the state-space graph. The root is the initial states                 and each node corresponds to a state in the state space. The distinction between search algos                 are which nodes to expand next. Best-first search expands the node with minimum value of                 some evaluation function. Graph searches check for redunbdant paths while tree searches                 do not. Algorithms can be complete, optimal, and have time and space complexity.\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\nWhen all actions have the same cost, we use BFS in which nodes are expanded based on distance                 to the root, with the closest being expanded first. This is complete and can use a FIFO queue.                 Early goal tests can be used meaning checking when a node is generated vs expanded. It is optimal                 if all actions have the same cost, otherwisee not, but always complete. It has complexity $O(b^d)$.                 Uniform cost search (or Dijktra's), uses path cost as an evaluation function for best-first search.                 This is both complete and cost optimal (given cost > 0). DFS expands the deepest node first, so inverse BFS                 where it is implented as tree instead of graph search. It is not cost optimal nor complete, but much more                 memory efficient $O(bm)$. Backtracking search is DFS that only generates one successor at a time, giving it                 $O(m)$ memory. Depth-limited is DFS with a depth limit to prevent infinite search. Iterative deepening                 search increases the depth limit incrementallty. This has the same time complexity as BFS but better space.                 Bidirectional search searches forward from initial and backwards from goal, and returns a solution when frontiers                 collide.\n\n## Module 3 Lecture Notes\nThese are defined with S, A, f : S, A -> S, p : A -> C, Goal(s).                            Uninformed search means we only have access to the problem defintion,                            no external $h(n)$. Informed search gives domain specific info.\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\nBeam search limits the size of the frontier to the best k nodes, making it suboptimal but more                 memory efficient. Iterative deepening A* (IDA*) is essentially A* with the cutoff being $f(n)$                 instead of depth. The next iteration has a cutoff of the lowest value which exceeded the cutoff                 in the previous. Recursive best-first is essentially DFS but only traverses a path until it does                 not exceed some $f_limit$. This is optimal given an admissible heuristic. However, they may explore                 the same states over and over due to using too little memory.                                MA* and SMA* are memory bounded A* which expand until memory is full, at which point it drops the                 worst leaf node and backs up the value to its parent. This is complete diven a reachable solution                 in the memory size. This heuristic search can also be bidirectional. You can do front to end, which                 gives a heuristic from the current to the end, or front-to-front where the heuristic is between frontiers.\n\n## AIMA Chapter 3.6 Heuristic Functions\nThe quality of a heuristic can be characterized by the effective branching factor. Heuristics can                 dominate another if it is always better at every state. In order to create heuristics we can relax                 a problem, meaning to allow moves with fewer restrictions. This adds edges to the state-space graph.                 We can also create an admissible heuristic by taking the maximum of a set of admissible heuristics.                 We can also design heuristics from solution costs of subproblems. A perfect heuristic could be generated                 by precomputing the cost of the optimal path between each pair of vertices. This can even be done for                 some landmark points. Some route finding algorithms also add edges as shortcuts. Differential heuristics                 subtract the exact distance from current to L beyond and the goal to L beyond to get current to goal.                 Agents can also learn to search better through the metalevel state space. Also, heursitics can be                 learned through experience, meaning we can use machine learning to predict $h(n)$ given a state.\n\n## Module 4 Lecture Notes\n$h(n)$ is the estimated cost of the cheapest path from the current to the goal state.                 Greedy best-first search expands the node with lowest $h(n)$ value. This is complete. \n                The most common informed search is A*, where we use evaluation function $g(n) + h(n)$,                 where g(n) is the actual cost from the initial to current node. It is complete and optimal                 given an admissible heuristic. If a heuristic is consistent the difference between h for                 a node and its child is bounded by some function. Consistent heuristics mean we will only                 reach a state on its optimal path. $f(n)$ monotonically increases if the heuristic is                 consistent. Inadmisssible heuristics can give non-optimal but good enough solutions. Thus                 weighted A* uses $f(n) = g(n) + W * h(n)$ for some $W > 1$. A* uses a lot of memory, and                 we can fix this by removing states from reached when they cannot be reached anymore.\n\n## Module 4 Definitions\n* **Admissible** - heuristic underestimates actual distance to goal\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nMost commonly studied games include deterministic, two-player, turn-taking                 perfect information, zero-sum games. This mans that they are fully observable and                 what is good for one player is bad for the other. The players are max and min,                 with max moving first and then turns being taken. We can superimpose trees on                 games as well.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nGiven a game tree, we can find the minimax value of each state                 which is the utility of the state for max. Thus, the minimax value is the optimal                 value of its children depending on whos move it is. We can extend this algorithm                 to multiplayer games. We can have a vector associated with each node for the number                 of players and have players choose move which maximize their utility in the same                 manner. Alpha-beta pruning has $\u0007lpha$ be at least where $\beta$ is at most.                 This means alpha is the best value for max and beta is the best value most min.                 Alpha beta pruning depends heavily on the order in which the moves are examined.                 Type A strategies explore all possible moves to a certain depth while Type B explore                 promising lines as far as possible. \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nHeuristic evaluation functions return an estimate of expected utility of a state                 for a specific player. For nonterminal states this is between the utility of a loss                 and a win. These functions are often calculated using a set of features and a weight                 given to those features. An evaluation function should be strongly correlated with the                 chance of winning. We then use this evaluation function with a cutoff to terminate early                 if there are no quiescient moves. We must also eliminate the horizon effect where there is                 an unavoidable move that will cause damage at some point in the future. We can mitigate                 this by allowing singular extensions where we can make moves that are clearly better even                 aftett the cutoff. Forward pruning prunes moves which appear to be poor. This is similar to                 beam search, where you only consider the few best moves. Probabilistic cut prunes moves using                 statistics from prior experience. For the opening and ending, many programs use table lookup                 rather than search and rely mostly on the expertise of humans. \n\n## AIMA Chapter 5.5 Stochastic Games\nStochastic games include a random element. For these, game trees must include chance nodes                 in addition to the min and max nodes. Instead of minimax, we can now calculate expected values                 of positions. This gives the expectiminimax value of games with chance nodees. The eval function                 must return values that are a positive linear transformation of the win probability. You can prune                 chance nodes by bounding the value of its utility.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nThe principle of maximum expected utility says that a rational agent should choose                  the action that maximizes its expected utility. However, in order to do this the agent                  must have a causal model of the world already.\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nGiven two lotteries (atomic states or another lottery), a rational agent must prefer one                  or be indifferent. They should be transitive, substitue indifferent loterries, monotonic,                  and continuous (as well as decompisble). If an agent's preferences satisfy all of these,                  there exists a utility function that satisfies these. \n\n## AIMA Chapter 16.3 Utility Functions\nUtility functions map lotteries to numbers. We can use preference elicitation for an agent                  to define its utility function. Utilities can be normalized to 0 and 1 to compare. Then, if                  you ask an agent to choose between S and a standard lottery $p*1 + (1-p)*0$, we adjust                  p until indifferent and the normalized utility of S is p. The value an agent will accept in                  lieue of a lottery is called the certainty equivalent of that lottery. Human agents have                  ambiguity aversion and also act irrationally due to emotion.\n\n## Module 5 Lecture Notes\nalpha is max's current lower bound on their outcome, and                            beta is mins current upper bound on their outcome. \n\n## Module 5 Definitions\n* **Quiescient move** - a pending move that wildly swings the evaluation\n* **Micromort** - how much would one pay to avoid death\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nCSPs are problems where each state has a set of variables that have values.                 An assignment that does not violate any constraints is called consistent.                 A solution is a complete consistent assignment. Unary constraints restrict 1                 variable while binary constrains restrict 2 variables. Any CSP can be reduced                 to a binary contrained CSP. \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nContraint propagation reduces the number of legal moves for a variable by                 using the constraints. Node consistency is if it satisfied unary constrains.                 Arc consistency is if every value in a variables domain satisfies its binary                 contraints. AC3 enforces arc consistency with a queue of ARCs. Path consistency                 is for 3 variable sets. A CSP is k-consistent if for every seet of k-1 variables                 and a consistent assignment to those, a consistent value can always be assigned to                 the kth variable. We can use bounds contraints as well as max and min to eliminate                 some options from variable domains. \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\nBacktracking search for CSPs essentially guesses for a partial assignment,                 then continues to infer, and if we cannot reach a solution it goes back and                 changes the guess. We can choose variables to assign using the minimum remaining                 value heuristic. It chooses the most constrained variable, or the one most                 likely to cause a failure soon. The degree heuristic can also have the same                 effect here. Then, once we choose a variable, we choose the value to assign                 using the least constraining value heuristic. After searching, forward checking                 establishes arc consistency for the new assigned variable by examining all                 variables connected to it by an arc. Instead of backtracking to the variable                 we assigned, we can also backtrack to the most recent assignment in the conflict set.\n\n## AIMA Chapter 6.4 Local Search for CSPs\nFor CSPs, local search algorithms can be very effective. When we have a conflicting                 variable in a complete assignment, what we can do is change the value to the one that                 results in the minimum number of conflicts. Constraint weighting also helps by giving                 each constraint a specific weight and then changes variables that will result in the                 lowest total weight of violated constraints.\n\n## AIMA Chapter 6.5 The Structure of Problems\nWe can find independence by finding connected components of the constraint subgraph.                 We can then solve the subproblems independently. Some CSPs can be tree structured,                 meaning we can define directional arc consistency and topologically sort the                 nodes, which then leads to linear time variable assignment. We can reduce regular                 CSP graphs to trees using cutset conditioning. We can remove nodes by fixing values                 and removing other inconsistent values. We can also construct a tree decomposition of                 the constraint graph. We can create a tree where each node in the tree is a set of variables                 such thaat each variable appears in at least 1 node, two vars connected by a constraint                 must appear together in a node, and if a var appears in 2 nodes it must appear in                 every node along the path connecting those nodes. Then, we assign sets of values to each                 node in the tree and individually solve each subproblem. We try to minimize tree width. \n\n## Module 6 Lecture Notes\nsoft constrains are preferences that can be represented as costs                            for certain variable assignments. \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nKnowledge based agents have a set of 'sentences' where each represents                 some assertion about the world. When it is given without being derived                 it is an axiom. They have tell and ask functions which are used to                 update the KB and return an action that should be taken.\n\n## AIMA Chapter 7.2 The Wumpus World\nWumpus World lecture\n\n## AIMA Chapter 7.3 Logic\nIf a sentence a is true in a model m, we say m satifies a or m is a                 model of a. M(a) is the set of all models of a. a entails B means B                 follows logically from a. Model checking means seeing if a is true in all                 models where KB is true. An inference algorithms is called sound if                 it derives only entailed sentences. An inference algorithm is complete                 if it can derive any sentence that is entailed. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\nPropositional logic considers each sentence to be a proposition. TT                 entails is an algorithm that enumerates all assignments to symnols.\n\n## AIMA 7.5 Propositional Theorem Proving\nA sentence is valid if it is true in all models. A sentence is                 satisfiable if its is true in some model. Given inference rules                 in the form (expressions) / (expressions) if the numerator is given                 the denominator can be inferred. CNF form is a conjunction of clauses                 where conjunction is ands and clauses are made of ors. The resolution                 rule allows us to resolve sentences together to simplify them. PL-Resolution                 is a resolution algorithm given CNF of KB implies a in which each pair of                 clauses that contains complementary literals is combined to produce a new                 clause which is added to the set. Then if no new clauses can be added for                 the problem a is not entailed by KB otherwis if we get the empty clause                 it is entailed. A defininte clause is a disjunction of literals where                 exactly 1 is positive. The Horn clause is where at most 1 is positive.                 These are closed under resolution, meaning if you resolve 2 you get a                 Horn clause. Forward chaining determines if a query is entailed by KB                 where we add q if we know p implies q and p and this continues until                 we cannot add anything or the goal query is added. Backward chaining                 does the reverse where it sees if p implies the query and checks if                 we can prove p.\n\n## Module 7 Lecture Notes\nIf a entails B that means a is more specific, or stronger than B                            as the set of models that satisfy a are a subset of those that satisy B                            since a model that satisfied a necesarily satifies B.\n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}