{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Haroun, 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": "d88a2f83-2a7d-4aa8-9c30-c1b0f2d6fd37"
      },
      "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": "8766d2f3-85b5-4c20-c75e-81660fca9ce5"
      },
      "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-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 130
        },
        "outputId": "268fcbad-5d63-48d6-f34d-addd7cb33da8"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" AI is the study of understanding and building intelligent entities \\\n",
        "                 Turing Test - computer will pass the test if a human interegator, after \\\n",
        "                               asking some questions, is unable to tell whether it is communicating \\\n",
        "                               with a machine or a human. \\\n",
        "                       -- Turing did not view physical simulation of machine as human as necessary for test \\\n",
        "                          though some propose it necessary now (requires computer vision and robotics) \\\n",
        "                 How can we study how humans think?\n",
        "                      introspection — trying to catch our own thoughts as they go by \\\n",
        "                      psychological experiments — observing a person in action \\\n",
        "                      brain imaging — observing the brain in action \\   \n",
        "                      \n",
        "                 1.4: Acting Rationally Vocabulary \\\n",
        "                      An agent is something that just acts, a rational agent acts to achieve best outcome or \\\n",
        "                      with uncertainty the best expected outcome. Rational agents should make the correct \\\n",
        "                      inferences. All the skills needed for turing test allow agent to act rationally.\n",
        "                      AI has focused on the study and construction of agents that 'do the right thing' \\\n",
        "                      What counts as the right thing is determined by the standard model\n",
        "                 1.5: Beneficial machines     \n",
        "                      Often times standard model doesn't hold up for all types of AI. There is no clear objective \\\n",
        "                      in designing a Autonomous Vehichle (trade off between risk of injury and speed with which we \\\n",
        "                      arrive at the destination, how do we express this?). The values or objectives of machine must be \\\n",
        "                      alligned with the humans goals (value allignment problem)        \"\"\" \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 = \"\"\" LIMITS OF AI \\\n",
        "                  Weak AI - the idea that machines could act as if they are thinking vs. Strong AI - the idea that the machine is actually \n",
        "                  assembling thoughts and thinking like a human. Early AI leaders thought it would be nearly impossible for AI to widely succesfull \\\n",
        "                  at acting like a human agent because human behavoir is far too complex to be defined by a set of rules. Machines are limited by the \\\n",
        "                  incompleteness thereom which basically says that machines are limited by the truth that encoded to evaluate, they cannot generate something \\\n",
        "                  \"new\". This thereom was ultimately written off - today most agree that it is impossible to answer if humans are smarter than computers.\n",
        "\n",
        "                  \"\"\"\n",
        "chapter27_2 = \"\"\" CAN MACHINES REALLY THINK \\\n",
        "                  Is an intelligent machine 'thinking' or simulating thinking? The field has decided that this question is not relevant. \\\n",
        "                  Airplanes can't flap their wings and fly in the typical sense but they still move across the sky. Searle rejects the fact that \\\n",
        "                  humans can really think in his Chinese Room example. He claims that a person who does not understand chinese in a room with a stack \\\n",
        "                  of text allowing him to translate the text is appearing as though he knows chinese but is not actually thinking. To summarize, conciousness \\\n",
        "                  is a tough thing to comprehend and define, it depends on how one views the world. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Agents and Environments \\\n",
        "                 Agent is anything that percieves its environment through sensors and acts upon it through actuators. Agents can be human, robotic, or software.\n",
        "                 The intention of agent in AI is not to set into category of IS or ISNT, calculator could technically be viewed as agent. Agents use precepts that \\\n",
        "                 they are given and an agent function to designate how to act under certain conditions. \"\"\"\n",
        "chapter2_2 = \"\"\" GOOD BEHAVOIR - CONCEPT OF RATIONALITY \\\n",
        "                 AI evaluates rationality through consequentialism, which measures rationality by the result of the actions of the AI. There is a performance measure \\\n",
        "                 at each action done by an AI that quantifies the benefit of the move made by the AI. Performance measures need to be carefully defined and in line with \\\n",
        "                 the intended goal that the human has for the machine. \"As a general rule, it is better to design performance measures according to what one actually \\ \n",
        "                 wants to be achieved in the environment, rather than according to how one thinks the agent should behave.\n",
        "                 \n",
        "                 Criterions for Rationality \\\n",
        "                   -- The performance measure that defines the criterion of success. \\\n",
        "                   -- The agent’s prior knowledge of the environment. \\\n",
        "                   -- The actions that the agent can perform. \\\n",
        "                   -- The agent’s percept sequence to date.\". \\\n",
        "\n",
        "                Rationality maximizes expected performance, while perfection maximizes actual performance. \\\n",
        "                Rational agents need to be autonomous, ones that operate on their own and are able to 'learn' from the space \\\n",
        "\n",
        "                  \"\"\"\n",
        "chapter2_3 = \"\"\" THE NATURE OF ENVIRONMENTS \n",
        "                 You must define your task environment prior to executing. PEAS - (Performance, Environment, Actuators, Sensors). \\\n",
        "                 Task environments are the problem that our rational agent will solve. Performance may be dificult to define among complex agents\n",
        "                 such as Autonomous Vehichles. Task environments can be physical or virtual.\n",
        "                 \n",
        "                 There are different kinds of environments: partially observable vs fully observable. In a fully observable environment sensors have \\\n",
        "                 access to the whole state of the problem. In a partially observable environment, sensors may not have access to the entire state of the world.\\\n",
        "                 \n",
        "                 Single-Agent vs. Multi-Agent - Single agent games have only one player (i.e. solving a crossword) whearas multi-agent have many. Multi-Agent\\\n",
        "                 games can be broken down to competitive and cooperative agents. Whereas chess is (competitive) other drivers interacting with an autonomous \\\n",
        "                 vehichle are (cooperative).\n",
        "                 \n",
        "                 Deterministic vs. nondeterministic. If the next state of the environment is completely determined by the current state and the action executed \\\n",
        "                 by the agent(s), then we say the environment is deterministic; otherwise, it is nondeterministic.\n",
        "\n",
        "                 The remaining definitions of task environments are listed in the definitions below\n",
        "\n",
        "                 games can be unknown and fully observable or known and partially observable\n",
        "                 \n",
        "                 The hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown.\n",
        "                  \n",
        "                  \"\"\"\n",
        "chapter2_4 = \"\"\"THE STRUCTURE OF AGENTS \\\n",
        "                AI's job is to design an agent program that allows the agent to map precepts to actions. Agent programs take percept as \\\n",
        "                input from the sensors and return an action to the actuators. Agent function may depend on entire percept history whearas agent \\\n",
        "                program depends solely on current percept.\n",
        "                The key challenge for AI is to find out how to write programs that, to the extent possible, produce rational behavior from a smallish \\\n",
        "                program rather than from a vast table. \\\n",
        "                \n",
        "                There are 4 major types of agents:\n",
        "                -- simple reflex agents\n",
        "                -- model based reflex agents\n",
        "                -- goal-based agents\n",
        "                -- utility based agents\n",
        "                \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        " \"rational agent\": \"is one that acts so as to achieve the best outcome or, when there is uncertainty, the best expected outcome.\"\n",
        " \"the value alignment problem\": \"the problem of achieving agreement between our true preferences and the objective we put into the machine\"\n",
        " \"weak AI\": \"the idea that machines could act as if they were intelligent\"\n",
        " \"strong AI\": \"the assertion that machines that do so are actually consciously thinking (not just simulating thinking)\"\n",
        " \"qualification problem\":  \"we saw there that it is indeed difficult to capture every contingency of appropriate behavior in a set of necessary and sufficient logical rules\"\n",
        "\"Chinese Room example\": \"he claims that a person who does not understand chinese in a room with a stack \\\n",
        "                  of text allowing him to translate the text is appearing as though he knows chinese but is not actually thinking.\"\n",
        "\"agent\": \"anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators\"\n",
        " \"percept\": \"the content an agent’s sensors are perceiving\"\n",
        " \"percept sequence\": \"complete history of everything the agent has ever perceived\"\n",
        " \"agent function\": \"maps any given percept sequence to an action.\"\n",
        " \"rational agent\":  \"For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. \"\n",
        " \"consequentialism\":  \"we evaluate an agent’s behavior by its consequences. \"\n",
        " \"omniscient agent\": \"knows the actual outcome of its actions and can act accordingly; but omniscience is impossible in reality\"\n",
        " \"task environments\" : \"the “problems” to which rational agents are the “solutions.” \"\n",
        " \"fully observable\": \"agent’s sensors give it access to the complete state of the environment at each point in time, then we say that the task environment\"\n",
        " \"episodic task environment\": \"the agent’s experience is divided into atomic episodes. In each episode the agent receives a percept and then performs a single action. Crucially, the next episode does not depend on the actions taken in previous episodes.\"\n",
        " \"sequential task environment\": \"the current decision could affect all future decisions (chess, crosswords)\"\n",
        " \"static/dynamic environment\":  \"If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent; otherwise, it is static. \"\n",
        " \"semidynamic environment\": \"If the environment itself does not change with the passage of time but the agent’s performance score does\"\n",
        " \"discrete environment\": \"one with defined finite and distinct states (chess)\"\n",
        " \"continous environment\" - \"one with infinite states (driving an AV)\"\n",
        " \"known environment\" - \"designer has knowledge of the possible outcome states of the game \"\n",
        " \"unknown environment\" - \"designer does not have knowledge of how the environment operates, the AI will have to learn the environment to work withint it (solitaire)\"\n",
        " \"agent program\" - \"implements the agent function, maps percepts to actions\"\n",
        " \"agent architecture\" - \"physical computing device and sensors and actuators that program runs on\"\n",
        " \"simple reflex agent\" - \"agents select actions on the basis of the current percept, ignoring the rest of the percept history\"\n",
        "\"model-based relex agent\" - \"keep track of the part of the world that you cant now see (past precept history) use transition model and sensor model to keep track of state of world and act on it\"\n",
        " \"goal-based agents\" - \"can combine goal with a model-based agent to introduce goal oriented behavoir (taxi deciding where to turn at intersection)\"\n",
        " \"utility-based agents\" - \"measure should allow a comparison of different world states according to exactly how happy they would make the agent, use utility function\"\n",
        " \"learning agents\" - \"build learning machines and then teach them, allows the agent to operate in initially unknown environments and to become more competent than its initial knowledge alone might allow, learning element can update knowledge components after exploration\"\n",
        " \"problem generator - part of the learning agent, respondible for suggesting actions that will lead to new informative experiences\n",
        " atomic representation - each state of the world is indivisible—it has no internal structure (driving from point A to B)\n",
        " factored representation - splits up each state into a fixed set of variables or attributes, each of which can have a value (driving from A to B, GPS coords, gas in tank, station on radio etc.)\n",
        " structured representation - allows us to handle unexpected edge cases (AV sees a cow in the road) more expressive then factored which is limited to acting upon its attributes\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "error",
          "ename": "SyntaxError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-9-6237ef303531>\"\u001b[0;36m, line \u001b[0;32m94\u001b[0m\n\u001b[0;31m    \"the value alignment problem\": \"the problem of achieving agreement between our true preferences and the objective we put into the machine\"\u001b[0m\n\u001b[0m                                 ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "cellView": "form",
        "outputId": "10ce52d9-d4f9-4137-99ff-9578dcdade24"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" All data are treated as objects, interpreter doesn't allow incompatible things with that type (i.e. \"foo\" + 2)\n",
        "                            Python (unlike java) is dynamicly typed - variables come into existence when first assigned x=\"foo\" newline x = 2 \\\n",
        "                            No ++ or -- is python \\\n",
        "                            Strings\n",
        "                               -- Creation: Can use either single or double quotes, Triple quote for multiline string and docstring\n",
        "                               -- immutable\n",
        "                               -- print(\"%s can speak %d languages\" % (\"C3PO\", 6000000))\n",
        "                            References and Mutability \\\n",
        "                              -- == checks for variables pointing to same value \\\n",
        "                              -- is checks for variables pointing ot the same object \\\n",
        "                              -- lists are mutable strings and tuples are immutable \\\n",
        "                              -- y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value \\\n",
        "                              -- tu[-3] negative lookup, lookup from end of array leftward \\\n",
        "                            Slicing \\\n",
        "                              -- t[1:-1:2] selection of every nth item\n",
        "                              -- t[:2]  copy from beginning of sequence\n",
        "                              -- > t[2:]  copy to the very end of the sequence\n",
        "                            List \\\n",
        "                               -- li.sort() and li.reverse() li.sort(function) #sort in place using user defined comparison\n",
        "                            Operations on Strings   \n",
        "                               -- \"_\".join(words) #join method of obj \"_\", where words is a list\n",
        "                               -- s.capitalize() #capitalizes first letter\n",
        "                               -- s.strip('-') #removes all occurences of -\n",
        "                               -- s.upper() #puts in upper case\n",
        "                            Dictionaries \\\n",
        "                               -- Dictionaries are unordered & work by hashing, so keys must be immutable\n",
        "                               -- Constant average time add, lookup, update   \n",
        "                               -- Can assign to existing key to replace value\n",
        "                               -- example dict d = {'user' : 'R2D2','pswd': 1234}\n",
        "                               -- d.keys() d.values() # list of values\n",
        "                               --  d.items() #list of item tuples\n",
        "                               -- d = defaultdict(str) # automatically initializes non existant values\n",
        "                            Functions\n",
        "                               -- can return multiple values (return mean, median, mode) # returns as tuple\n",
        "                               -- no overloading functions (cant have multiple with same name)\n",
        "                               -- can provide default values in function arguments, these args are optional \n",
        "                               -- def print_everything(*args): #takes variable number of arguments\n",
        "                               -- **kwargs \n",
        "                               -- python has dynamic scope (function sees most current value of vars)\n",
        "                               -- first class object\n",
        "                           Class\n",
        "                               -- __init__ #equivilant to constructor in java\n",
        "                           Magic Methods and Duck Typing\n",
        "                               -- magic methods allow user defined class to behave like built in types\n",
        "                               -- __init__ __len__ __copy__ __add__ ...\n",
        "                               -- duck typing #can call len() on any object that implements __len__\n",
        "                           Loops /\n",
        "                               -- [elem * 2 for elem in li if elem > 4]\n",
        "                           Iterators\n",
        "                               -- Iterable objects can be used in a for loop because they have an __iter__ magic method, which converts them to iterator objects:    \n",
        "                               -- i.next() #no hasNext() method\n",
        "                           Generators\n",
        "                               -- generators are iterators\n",
        "                               -- use yield to return\n",
        "                               -- def f(n): ... yield n ... yield n+1  \n",
        "                               --  [i for i in f(6)] --> [6,7]\n",
        "                               -- Each time we call the __next__ method of the generator, the method runs until it encounters a yield statement, and then it stops and returns the value that was yielded. Next time, it resumes where it left off.           \n",
        "                               \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"immutable\" : \"object whose state cannot be changed after it is created\",\n",
        "}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6c9789f4-242b-4b15-98f8-42d0e16986a9"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Problem solving agent undertakes a 'search'. They take on atomic representation. \\\n",
        "                 Precepts are not monitored in most search problems that we will look at because \n",
        "                 they are informed and fully observable. State space, initial state, set of possible actions, transition model \\\n",
        "                 action cost function, and goal states define a search problem. Optimal \\\n",
        "                 solution has lowest path cost among all solutions. State space can be \\\n",
        "                 represented as a graph where vertices are states and directed edges \\\n",
        "                 between are actions. \"\"\"\n",
        "chapter3_2 = \"\"\" Problems have states, initial state, actions, transition model, goal states, and action cost.\\\n",
        "                 There are many different types of problems - touring, robot navigation, etc. (Really not much \\\n",
        "                 actual content for this section) \\\n",
        " \"\"\"\n",
        "chapter3_3 = \"\"\" Search problem takes problem as an input and returns a solution or indication of failure. In order \\\n",
        "                 to complete search problems we superimpose a search tree over the state-space graph and form paths \\\n",
        "                 from the initial state. State space describes the possibly infinite set of states in the world and actions \\\n",
        "                 that allow transitions from one to another. The search tree may have multiple paths to any given node but each \\ \n",
        "                 node has unique path back to the top. Search data structures are typically trees where each node is an object \\\n",
        "                 with reference to a parent and a child. We store the frontier in a queue. \"\"\"\n",
        "chapter3_4 = \"\"\" Uninformed search algorithm is given no clue about how close a state is to the goal. There are different \\\n",
        "                 algorithms that we can employ to search an uniformed problem. BFS root node expanded first then their successors \\\n",
        "                 and so on. Works well when all have the same cost. BFS always finds a solution with minimal number of actions (optimal) \\\n",
        "                 Generates b^d nodes (where d is depth). Time and space complexity are both O(b^d).\n",
        "                 \n",
        "                 Dijkstras (uniform-cost-search) works well when edges are of different weights. Dijkstras has time and space \\\n",
        "                 complexity that is worse than BFS. It is complete and optimal.\n",
        "                 \n",
        "                 DFS is not optimal and it can get stuck going down cycles. It is often used because its space complexity is \\\n",
        "                 small. Complexity O(bm) m is depth and b is branching factor. \\\n",
        "                 \n",
        "                 Depth-limited search - like DFS but prevents it from going down infinite cycle, do not look given depth. \\\n",
        "                 Time complexity of O(b^l) and space complexity of O(bl) where l is depth. It is incomplete if we do not \\\n",
        "                 look at every level l\n",
        "                 \n",
        "                 Iterative deepening search performs Depth limited search for each value of l until it finds a a solution. has the same\n",
        "                 time complexity as BFS\n",
        "                 \n",
        "                 Bidirectional Search - simultaneously search forward from initial state and back from goal state and hope that you \\\n",
        "                 meet somewhere in the middle. Complete and Optimal and O(b^d/2) space and time complexity\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "\"state space\" : \"set of possible states the environment can be in\",    \n",
        "\"intial state\" : \"state the environment begins in\",    \n",
        "\"goal states\" : \"goal environments\",\n",
        "\"path\": \"a series of actions\",\n",
        "\"model\": \"abstract mathematical description\",\n",
        "\"standardized problem\": \"illustrate or exercise various problem-solving methods\",\n",
        "\"real world problem\": \"problem such as robot navigation that people actually use\",\n",
        "\"STATES\" : \"A state of the world says which objects are in which cells.\",\n",
        "\"touring problem\" : \"a set of locations that must be visited, rather than a single goal destination\"\n",
        "\"best-first search\": \"choose a node n with min value, at each iteration choose frontier node with min f(n)\"\n",
        "\"graph search\": \"algorithm that checks for redundant paths in search problem\"\n",
        "\"tree-like search\": \"does not check for redundant paths\"\n",
        "\"complete\": \"algorithm finds a solution if there is one\"\n",
        "\"optimal\": \"algorithm finds a solution of lowest path cost\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 215
        },
        "outputId": "302a0e08-cc1a-4607-c4f6-90dae7f455b9"
      },
      "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": "error",
          "ename": "NameError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-6-0a3759060351>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      9\u001b[0m ]\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 11\u001b[0;31m \u001b[0mmodule3_markdown\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mformat_module\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"Search Problems\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmodule3_sections\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmodule3_definitions\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     12\u001b[0m \u001b[0mdisplay\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mMarkdown\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmodule3_markdown\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mNameError\u001b[0m: name 'format_module' is not defined"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"Informed search strategy takes advantage of some heuristic function to find solutions more effeciently \\\n",
        "                Greedy Best First Search: expans the node with the lowest h(n) value, node that appears to be closest to \\\n",
        "                the goal state. It is complete in finite search spaces but not infinite and has a worse case complexity equal \\\n",
        "                to O(|V|). \n",
        "                A* Search: f(n) = g(n) + h(n). g(n) is path cost to the current node and h(n) is the estimated cost to goal state \\\n",
        "                It is complete and optimal when admissible (heuristic never overestimates the cost. If heuristic A* is not admissable \\\n",
        "                then it is not guarenteed to return cost optimal solutions. A* works well because it prunes away the search tree nodes \\\n",
        "                A* lacks in that it is an exponential time algorithm - often times need shorter. We can explore fewer nodes if we are \\\n",
        "                willing to accept slightly suboptimal solutions \\\n",
        "                \n",
        "                Weighted A* Search: We weight the heuristic value more heavily by some factor W. Iterative Deepening A* search also exists \\\n",
        "                \n",
        "                \"\"\"\n",
        "chapter3_6 = \"\"\" Will talk about heuristic function in context of sliding puzzle 8tile game. Manhattan distance vs. Misplaced tiles. \\\n",
        "                 Misplaced tiles worked better almost on every occasion. Computers can also generate heurstics from problem definitions \\\n",
        "                 provided to them. We use heuristics so that we can calculate utility at our current state instead of storing utility for \\\n",
        "                 all possible game states and moves. We can generate heuristics from relaxed versions of presented problem from which optimal \\\n",
        "                 solution can be found easily.\n",
        "                  \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"admissable\": \"never overestimates the cost to reach a goal\",\n",
        "\"monotonic\": \"path cost always increases as you go along\",\n",
        "\"unbounded-cost search\": \"we look for a solution whose cost is less than some constant C\",\n",
        "\"reference counts\": \"counts the number of times a state has been reached and remove when no more possible ways to meet\",\n",
        "\"Manhattan Distance\": \"distance from moving up and down but not diagonally, is admissable\",\n",
        "\"relaxed problem\": \"problem with fewer restrictions\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "cellView": "form",
        "outputId": "6a33bad1-c16f-44e7-b70a-5755faa0ad38"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" When there are a large amount of agents in the population \\\n",
        "we consider them to be an eeconomy. Adversarial agents are the part of the \\ \n",
        "environent that  make the game non-deterministic. Pruning makes a search more \\\n",
        "efficient by preventing exploration of unfit paths. A heuristic evaluation \\\n",
        "function is used to estimate who is winning. In this chapter, we we cover \\\n",
        "two-player, turn-taking, zero-sum, perfect information games. To evaluate these, \n",
        "we use the minimax algorithm. A completee game tree is a search tree that \\\n",
        " follows every sequeence of moves to a terminal state. \"\"\"\n",
        "chapter5_2 = \"\"\" Minimax search is a general zero-sum game solution algorithm \\\n",
        "that defines two players MAX who wants to maximize their outcome and MIN who \\\n",
        "whats to minimize MAXs outcome. MAXs strategy is a plan contingent on MINs \\\n",
        "responses. The more simplified version of the minimax algorithm for win-lose \\\n",
        "games is AND-OR search. Minimax is a complete depth-first exploration. \\ \n",
        "If the max depth of the tree is m and there are b legal moves at each level, \\\n",
        "the time complexity of the algorithm is $$O(b^m)$$. For games with more than \\\n",
        "two players. For multiplayer games, the single value can be replaced with \\\n",
        "a vector of values. In multiplayer games, alliances can be formed and can \\\n",
        "give a concrete indication of how outcomes will happen. Alpha beta pruning allows \\\n",
        "for the removal of paths that will not impact the outcome before exploring that \\ \n",
        "path. The order in which you explore edges changes the outcome of the aplha \\\n",
        "beta pruning. If done properly, the runtime can be reduced to $$O(b^{m/2})$$. \\\n",
        "Repeated states can be referred to as transpositions, which are shown in a \\\n",
        "transposition table. \"\"\"\n",
        "chapter5_3 = \"\"\"Using a heuristic evaluation function, we can treat non-terminal \\\n",
        "nodes as if they are terminal and ESTIMATE their utility. To use this, we replace \\\n",
        "the terminal test by a cutoff test. The value of the evaluation function must be \\\n",
        "within the value of win and loss. The evaluation function computes the expected \\\n",
        "value or material value of the outcome. You also must alter the minimax \\\n",
        "algorithm so that the is_terminal call is replaced by an is_cutoff call. \\\n",
        "Singular etensions are moves that are clearly better than all other moves in a \\\n",
        "given position. Forward pruning prunes moves that seem to be poor moves but actually\\\n",
        " may be helpful. This can be done using beam search (at each ply, consider only a \\\n",
        " \"beam of the moves\") or  through late move reduction ( assuming that move \\\n",
        " ordering is done well and moves that appear later in the list are done well). \\\n",
        " Many game playing programs use table lookup rather than search for the \\\n",
        " opening and ending of games. They produce a policy (mapping of every possible \\\n",
        "  move to the best state) and make a table by retrograde miniax search.\"\"\"\n",
        "chapter5_5 = \"\"\" Stochastic games incorporate a random element, using \\\n",
        "chance nodes in a tree in addition to min and maxnodes. Consider this in a \\\n",
        "game like backgammon, where a dice roll at every turn impacts outcome. These \\\n",
        "chance nodes use expected value of a position, and the expectiminimax algorithm \\\n",
        "is a generalization of minimax that can be used to solve these games. The \\\n",
        "evaluation function in these games use probability, and the search space is \n",
        "expanded by a multiple of the number of events of chance.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "###Games\n",
        "\n",
        " Games provide an interesting way of performing \\\n",
        "search algorithms to solve a problem. Deep blue : 1997 AI game beat Kasparov\\\n",
        "the world chess champion.  In 2016, AlphaGo (Go AI program by Google's DeepMind)\\\n",
        "beats the world champion.  \n",
        "\n",
        "#### Main properties of Games \n",
        "1. Two players alternate moves\n",
        "2. one player's loss is another player's gain\n",
        "3. there is a clear set of legal moves\n",
        "4. there is a clear set of outcomes \n",
        "\n",
        "Examples of deterministic games : Chess, checkers, go....\n",
        "Card games are usually not deterministic games, same with real time strategy games \\\n",
        "like continuous games\n",
        "\n",
        "#### Formalizing the Game\n",
        "\n",
        "two players : MAX and MIN, MAX goes first and they take turns for the whole game\n",
        "\n",
        "Games as search \n",
        "1. Initial state: particular configuration of the game borad \n",
        "2. Successor function: set of possible actions and the resulting states\n",
        "3. Terminal test : is the game over\n",
        "4. Utility function: numerical value of terminal states (+, -, or 0)\n",
        "5. MAX uses the search tree to consider all moves\n",
        "\n",
        "####General Scheme\n",
        "1. Consider all successors to the current position\n",
        "2. Evaluate the successors of each move\n",
        "3. Pick the move which puts you in the best position\n",
        "4. Repeat AFTER your opponent moves\n",
        "\n",
        "### Game Trees\n",
        "\n",
        "Example: Hexapawn (3 x 3 chess board with three pawns for each player)\\\n",
        "In the tree, nodes are board position and edges are moves from board to board\\\n",
        "Root node is the first position.\\\n",
        "\n",
        "#### MINIMAX Algorithm\n",
        "\n",
        "+ two players, max and min\n",
        "+ max tries to maximize the score, min tries to minimize maxs score\n",
        "+ we assume that max moves first\n",
        "+ all scores are computed from max's view point\n",
        "+ The root is level 0, all even turns are MAX, all odd levels are MIN, alternate/\n",
        "max and min labels at each ply of the tree\n",
        "\n",
        "Represent the game as a tree with nodes as board positions and edges as legal moves\n",
        "\n",
        "Evaluation function f assigns real numbr scores to board positions\n",
        "\n",
        "Terminal nodes are ways the game could end\n",
        "\n",
        "#### The evaluation function f(n)\n",
        "1. says \"how good\" a board position is \n",
        "2. based on static features alone\n",
        "3. if f(n) > 0 is a better position for MAX to be in, f(n) = 0 equally good, \\\n",
        "f(n) < 0 MIN is winning\n",
        "4. example f(n) for tic tac toe : f(n)= (# of lengths of 3 open for MAX) - \\\n",
        "(# of lengths of 3 for MIN) \n",
        "\n",
        "For more complicated games (like chess) where do we get f(n)? \n",
        "+ Turing's evaluation function f(n) = sum of A's vals - sum of B's vals\n",
        "+ more complex, weight positional features based on game pieces, add up each \\\n",
        "players weighted sums, and subtract your opponents weighted score from yours \n",
        "\n",
        "### The MiniMax Algorithm\n",
        "\"Don't play hope chess\"\n",
        "+ assume that min is alwaysgoingto reply with the best possible move for itself\n",
        "+ resursive process: search down the search tree to bottom or depth threshhold\n",
        "+ recursively back the values up the search tree based on who's turn it was at \\\n",
        "each ply\n",
        "+ for MAX, choose max value of all children, for MIN choose the min value of all\n",
        "children\n",
        "\n",
        "####Algorithm:\n",
        "Until the game is over:\n",
        " 1. Start with the currentpositionas MAX node\n",
        " 2. Expand the game tree bvy a fized number of ply\n",
        " 3. apply f(n) to each of the leaf nodes\n",
        " 4. \"back up\" the values in a bottom up fashion\n",
        " 5. pick the move assigned to max at the root\n",
        " 6. wait for min to respond\n",
        "\n",
        "Minimax search uses the above algorithm to pick moves \n",
        "```\n",
        "def max_value(state):\n",
        "  if terminal : return utility\n",
        "  else: \n",
        "    initialize v = - \\infty\n",
        "    for s in state.successors():\n",
        "      v = max(v, min_value(s))\n",
        "    return v\n",
        "\n",
        "def min_value(state):\n",
        "  if terminal : return utility\n",
        "  else: \n",
        "    initialize v = + \\infty\n",
        "    for s in state.successors():\n",
        "      v = min(v, max_value(s))\n",
        "    return v\n",
        "```\n",
        "\n",
        "### Alpha Beta Pruning\n",
        "\n",
        "\"Cutting off branches\" from our game tree \n",
        "+ alpha : MAXs current lower bound on outcome (I will score at least this) (init - \\infty)\n",
        "+ beta : MINs current upper bound on score (I will score at most this) (init  \\infty)\n",
        "+ aka the best already explored on the path to the root\n",
        "+ MAX will never allow a move that leads to a lower score than alpha, MIN will \\\n",
        "never allow a move that will lead to a higher score than beta\n",
        "+ This helps us decide when to stop evaluating a branch, \n",
        "+ Logic for alpha and beta, MAX will never choose something lower than alpha, we \n",
        "know that a node will never be better than beta \n",
        "+ if you are at a MIN node, check agains alpha, if you are at a MAX node, \\\n",
        "check against beta \n",
        "\n",
        "### Expectimax\n",
        "\n",
        "+ Games with uncertain outcomes, we don't actually know what is going to happen\n",
        "+ ie. rolling a dice\n",
        "+ Outcomes are controlled by chance\n",
        "+ we have max nodes and chance nodes \n",
        "+ Expectimax computes the score by calculating expected utilities \n",
        "+ useful with games of chance or not fully rational opponents\n",
        "+ Later will be formalized using Markov decision processes\n",
        "+ values in the chance nodes are averagee case outcomes \n",
        "\n",
        "Pseudocode: \n",
        "```\n",
        "\n",
        "def value(state): \n",
        "  if terminal: return utility\n",
        "  if state is a MAX : return max-value(state)\n",
        "  if state is an EXP : return exp-value(state)\n",
        "\n",
        "def max-value(state):\n",
        "  initialize v = - \\infty\n",
        "  for s in state.successors():\n",
        "    v = max(v, value(s))\n",
        "  return v\n",
        "\n",
        "def exp-value(state):\n",
        "  initialize v = 0\n",
        "  for s in state.successors():\n",
        "    p = probability(s)\n",
        "    v += p* value(s)\n",
        "  return v\n",
        "\n",
        "```\n",
        "\n",
        "We CANNOT do pruning easily with expectimax to trim out the search space, \\\n",
        "since the average can end up being greater\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"multiagent\" : \"more than one player in the search, differentaites it from a \\\n",
        "puzzle\",    \n",
        "\"static\" : \"agent can sit and think for as long as it needs, the game doesn't \\\n",
        "change during deliberation\",\n",
        "\"discrete\" : \"finite set of actions\",\n",
        "\"fully observable\" : \"you see the complete. configuration of the game at each \\\n",
        "point\",\n",
        "\"strategic\" : \"the next state is determined by the current state and what your \\\n",
        "opponent does\",  \n",
        "\"adversarial search\" : \"think about what your opponent is thinking about\" , \n",
        "\"ply\" : \"layer of a game tree\", \n",
        "\"expectation\" : \"weighted average of all of the possible outcomes\",\n",
        "\"perfect information\" : \"fully observable\", \n",
        "\"zero sum\" : \"there are no win-win outcomes, a gain for one player is a loss for \\\n",
        "another player\", \n",
        "\"transition model\" : \"defines the resulting state taking an action from a \\\n",
        " starting board\", \n",
        " \"terminal states\" :\"when the game is over\",\n",
        " \"utility function(s,p)\" : \"assigns a numerical value p when the game ends in \\\n",
        " state s\", \n",
        " \"minimax decision\" : \"minimax value at the root\", \n",
        " \"killer moves\" : \"moves that when explored first using pruning are most beneficial \\\n",
        " to the runtime\",\n",
        " \"Type A Strategy\" : \"wide but shallow, considers all possible moves to a \\\n",
        " certain depth in the search tree\", \n",
        " \"Type B Strategy\" : \"deep but narrow, uses pruning\", \n",
        " \"EVAL(s,p)\" :\"proposes an estimate for the utility of state s to player p\", \n",
        " \"quiescent\" : \"positions such that there is no move that would wildly \\\n",
        " way the outcome, ie capturing. the queen and ending the game \",\n",
        " \"horizon effect\" : \"when an opponents move causes serious damage and is not \\\n",
        " avoidable but delayable\"\n",
        " \n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "39ec8635-89e2-4f2f-99f8-00aecd47f6ca"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "### Introduction to CSPs\n",
        "What is search for? single or multiple agent/ dterministic actions, \\\n",
        "fully observed state, discrete state space. Goal is to formulate a plan \\\n",
        "(ie sequences if actions to navigate a map of cities, solve the 8-puzzle, etc.)\\\n",
        "\n",
        "Today, we want to identify a good assignment of variables to reach a goal state \\\n",
        "path length is equal for all solutions, we just care about the goal itself\n",
        "\n",
        "####  Big Idea\n",
        "+ Constrains are represented by uniform declarative language\n",
        "+ no built in transition functions or heuristic functions requirred\n",
        "+ devlop general purpose algorithms \n",
        "\n",
        "#### Definition of a CSP\n",
        "1. Set of variables (with a label for each) $$X_1 ..... X_n$$\n",
        "2. the domain of possoble values to assign to each variable \\\n",
        "$$D_1, D_2, ...D_n \\\\text{where } D_i = \\\\{v_1...v_k\\\\}$$ \n",
        "3. A finite set of constraints $$C_1 ..... C_k \\\\text{ where each } C_i \\\\text{ limits the values that two variables can take}$$\n",
        "4. A consistent assignment doesn't violate any constraint\n",
        "5. We will build a general purpose algorithm to solve these problems\n",
        "6. Solutions must be complete and consistent \n",
        "\n",
        "Example : Sudoku\n",
        "\n",
        "### Deeper in CSP\n",
        "\n",
        "#### Applications \n",
        "+ map coloring (we go into today)\n",
        "+ scheduling problems\n",
        "+ floor planning for very large scale integrated circuits\n",
        "+ sudoku\n",
        "\n",
        "#### Map Coloring \n",
        "+ Goal: to color a map such that no area is the samee color as its neighbors\n",
        "+ Variables : different states / regions\n",
        "+ Domains : the set of colors each area can take\n",
        "+ Constraints : adjacent areas must not have the same color\n",
        "\n",
        "\n",
        "#### CSP Benefits \n",
        "1. Generic way to handle a whole suite of complicated problems \\\n",
        "no need for speecific heuristics, successor functions, etc\n",
        "2. CSP \"knows\" which variables violate constraints, focus on the search \n",
        "3. CSPs automaticallu prune constraint violating branching so they massively \\\n",
        "reduce the search space\n",
        "\n",
        "#### CSP Graph Representation \n",
        "\n",
        "Develop a constraint graph, nodes are variable and arcs represent binary \\\n",
        "constraints between each pair of nodes. This simplifies search. It is also  \\\n",
        "possible to have disjoint subgraohs which allows you to divide the CSP into \\\n",
        "smaller independent CSP. We are focusing on discrete domain CSPs, but there can \\\n",
        "be both finite (ie n variables) and infinite domains (ie set of all integers). \\\n",
        "Continuous variable CSPs use Linear Programming. \n",
        "\n",
        "#### Varieties of Constraints \n",
        "+ Unary : involve a single variable ie Florida cannot be blue\n",
        "+ Binary: involve two variables ie Florida and alabama cannot be the same color\n",
        "+ Higher order : constraints that involve 3 or more variables\n",
        "+ Preference : aka soft constraints red is better than green, used in \\\n",
        "constrained optimization problems \n",
        "\n",
        "### CSP as a Search Problem\n",
        "\n",
        "Expressing CSP as a search problem \n",
        "+ Initial State : all variabvles with no assignment \n",
        "+ Successor function : take any unassigned variables and assign it a value\n",
        "+ Goal test : is the current state complete and consistent?\n",
        "+ Path cost : constant \n",
        "\n",
        "Solution will always be found at depth n.\n",
        "\n",
        "#### Search Tree and Branching Factor\n",
        "n variables of domain size d, branching factor is n*d, n*d-1, and so on. \\\n",
        "So, the tree has n!*d^n leaves. Variable assignments are commutative, order in \\\n",
        "which we assign them does not matter. Therefore, only a singke variable is  \\\n",
        "considered at each node, there are only d^n leaves.Redundant paths are checked, \\\n",
        "this is a tree search not a graph search. \n",
        "\n",
        "#### Search and Backtracking \n",
        "+ We know the depth of our tree, n, so we can use DFS because we know we have \\\n",
        "met the end \n",
        "+ Backtracking search uses values for one variable at a time and when it has \\\n",
        "reached a point of inconsistency it backtracks\n",
        "+ This is the most basic,  uninformed way to approach CSPs\n",
        "\n",
        "### Improving Efficiency of Backtracking \n",
        "\n",
        "Can we come up with general purpose heuristics to detect failure before \\\n",
        "a depth of n? Give us a gain in speed ON AVERAGE. \n",
        "\n",
        "#### Which Variavble should we assign a value to next?\n",
        "\n",
        "1. Pick the most constrained variable to assign first, called the minimum \\\n",
        " remaining values heuristic (MRV) (the one with the fewest available remaining \\\n",
        " values in its domain)\n",
        "2. With ties in MRV, pick the most constraining variable, the one that imposes the \\\n",
        "most constraints on others \n",
        "\n",
        "\n",
        "#### What order should that variables values be tried\n",
        "3. Choose the least constraining value (the one that rules out the fewest \\\n",
        "values in the remaining unassigned variables)\n",
        "\n",
        "#### Can we detect inevitable failure early? AKA Forward checking\n",
        "4. Inference, try to check the remaining unassigned variables , terminate \\\n",
        "the search when any unassigned variable has no remaining legal values (AC-3 \\\n",
        "towards arc consistency)\n",
        "\n",
        "Towards constraint propogation: forward checking allows us to propogate \\\n",
        "information from assigned variables to unassigned variables BUT doesnt \\\n",
        "provide early detection to all failures. Constraint propogation goes beyond \\\n",
        "forward checking \n",
        "\n",
        "### Arc Consistency and AC-3\n",
        "\n",
        "#### Big Idea : Inference \n",
        "+ CSPs alternate between search and inference \n",
        "+ Search : assign value to a variable \n",
        "+ Inference: propogates constraints to eliminate values \n",
        " \n",
        " #### Local Consistency\n",
        " 1. Node consistency satisfies unary constraints (easy) \n",
        " 2. Arc consistency satisfies binary constraints, if i and j havee an edge \\\n",
        "  between them for every value in the domain of i there is a value in domain  \\\n",
        "  of j that satisfies the constraint between i and j \n",
        "\n",
        "  #### Edges as Arcs\n",
        "  + a constraint is a pair of directed arcs, i to j and j to i\n",
        "  + the arc from x to y is consistent if for every value in x there is a some \\\n",
        "  allowed value in y. If not, we remove these valuyes from x because we know \\\n",
        "  they will lead to inconsistency\n",
        "  + an arc (i,j) is consistent iff eveery valuee in i is consistent with some \\\n",
        "  value in j if not we remove the value from i. Takes O(d^2) time \n",
        "\n",
        "Dave Waltz said that we can propogate arc consistency:\n",
        "+ assign every node a set of all  possible values, \n",
        "+ repeat until no change: for each node i and each neighboring node j, remove \\\n",
        "any value of i which is not consistent with j\n",
        "\n",
        "#### Towards AC-3: \n",
        "1. at each iteration we only need ti look at the Xi where at least one neighbor \\\n",
        "has lost a value\n",
        "2. if Xj loses a value because of arc inconsistencies of Yj, we dont need to \\\n",
        "check Xj in the next iteration\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"consistency\" : \"A consisent solution does not violate any constraints\",\n",
        "\"CSP\" : \"Constraint satisfaction problem\",\n",
        "\"Complete\" : \"every variable is assigned a value\" , \n",
        "\"Backtracking\" : \" An uninformed method of solving CSPs using DFS, arbitrarily \\\n",
        " assigning a value to one variable at a time, backtracking one we reach a point \\\n",
        " where a variable has no available values in its domain\"\n",
        "   \n",
        "}\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5f3d2500-dfb2-42e4-9373-fb3bec356333"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5) \n",
        "chapter7_1 = \"\"\"  \"\"\"\n",
        "chapter7_2 = \"\"\"  \"\"\"\n",
        "chapter7_3 = \"\"\" \"\"\"\n",
        "chapter7_4 = \"\"\" \"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "To prove theorems, we need logical equivalence (rules enumerated in lecture notes) \\\n",
        "and validity. A sentence is valid if it is true in all models. Valid \\\n",
        "sentences are also known as tatuologies. The Deduction Theorem is derived from \\\n",
        "entailment, we can derive if a entails b by checking if a implies b \\\n",
        "in every model Satisfiability is the last concept needed to formalize logical proofs: \\\n",
        "a sentence is satisfiable if it is possible for it to be true in some model. We\n",
        "can prove this through \"reductio ad absurdum\" aka proof by refutation or \\ \n",
        "contradiction.\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "\n",
        "### Knowledge Based Agents\n",
        "\n",
        "+ Knowledge based agents use processes of reasoning over an internal \\\n",
        "representation or knowledge about the world to make actions\n",
        "+ problem solving agents searched over a state of the world, an atomic state \\\n",
        "representation (no additional information about the world )\n",
        "\n",
        "+ a Knowledge Base (KB) contains a set of sentences written in a knowledge \\\n",
        "representation language that contains facts about the world \n",
        "Example Sentences: \n",
        "+ hoth is a planet -> planeet(hoth)\n",
        "+ hoth is far from its sun -> far_from(hoth, sol)\n",
        "+ if a planeet is far from its sun then it is cold : planet(x) and sun(y) and \\\n",
        "far_from(x,y) -> cold(x)\n",
        "\n",
        "Knowledge based agents add inforrmation to add to its knowledge base by telling \\\n",
        "it can also ask the knowledge base for information by asking (query). \n",
        "\n",
        "#### Logic \n",
        "+ is a general class of representations to use for our language\n",
        "+ KB agents used logic to make inferences about the world\n",
        "+ KB is going to consist of a set of sentences in our rrepreseentation language\n",
        "+ the language has a specific syntax\n",
        "+ logic defines the semantics of the sentences (their meaning)\n",
        "+ The semantics define the truth of each sentence with respect to the \\\n",
        "possible world known as a model\n",
        "\n",
        "#### Possible worlds\n",
        "+ Every possible sentence has a fixed set of truth values (true or false)\n",
        "+ if a sentence A is true in a particular model M then M satisfies A or M is \\\n",
        "the model for A\n",
        "+ M(A) is the set of all models where A is true \n",
        "+ examples, if A is there is no pit in [2,2], the M(A) is the set of all possible \\\n",
        "worlds where there is no pit in [2,2]\n",
        "\n",
        "#### Logical Entaillment\n",
        "+ entailment means that a sentence logically follows from another one \n",
        "+ a entails b, $$a\\\\models b \\\\text { iff } M(a) \\\\subset M(b)$$. This means \\\n",
        "that a is more specific than b \n",
        "\n",
        "#### Knowledge Base\n",
        "+ a set of sentences\n",
        "+ the KB is false in models where the sentences contradict what the agent knows\n",
        "+ Model checking is eenumerating all possible models that are compatible with \\\n",
        "the KB (find all models where the knowledge base entails the facts that we know)\n",
        "\n",
        "#### Logical Inference\n",
        "+ deriving conslucions from a seet of existing logical sentences \n",
        "+ we can think of the consequences of a KB as the set of additional sentences that \\\n",
        "are entailed given the sentences in the KB\n",
        "+designing an inference algorithm will enumerate all of these consequences, \\\n",
        " $$ KB \\\\vdash_i a $$ a is derived from KB by i\n",
        "\n",
        "### Propositional Logic\n",
        " + atomic sentences are represented by propositional symbols, standing for a \\\n",
        " statement that can be either true or false\n",
        " + ie W_1,3 can stand for a boolean that represents the Wampa is at position \\\n",
        " [1,3]\n",
        " + Complex sentences are conjoined using logical connectives:\n",
        " $$ \\\\neg \\\\text{(not) is a negation, } \\\\wedge \\\\text{(and) is conjunction, } \\\\vee \\\\text{(or) is disjunction, } \n",
        " \\\\Rightarrow \\\\text{(implies) premise -> consequence (conclusion),} \\\\Leftrightarrow \\\\text{(iff) is a biconditional, } $$\n",
        "\n",
        "Implications are also known as if-then statements or rules\n",
        "\n",
        "#### Important Truth Table Values\n",
        "+ for and, both values must be true for true\n",
        "+ for or, only one value must be true\n",
        "+ for implies, all are T except T -> F because in this case you told a lie\n",
        "+ For biconditional, T<->T and F<->F are True, the others are false\n",
        "\n",
        "### Knowledge Base\n",
        "\n",
        "Constructed of sentences, rules are applied to derive new sentences\n",
        "1. Outline the atomic sentences for example:\n",
        "$$P_{x,y} \\\\text{ will be true if there is a pit at x,y}$$\n",
        "2. Construct a knowledge base: label each sentence with R, $$R1 = \\\\neg P_1 \\\\text{there is not a pit at 1,1}$$\n",
        "3. As the wampa moves, he learns and infers things about the different squares and \\\n",
        "can add different assertions about the world when the knowldge base entails a \\\n",
        "certain fact\n",
        "\n",
        "### Theorem Proving\n",
        "\n",
        "+ we have already covered propositional logic with both atomic and complex \\\n",
        "sentences \n",
        "+ we need a notion of logical equivalence \n",
        "\n",
        "Logical Equivalence : $$a \\\\equiv b \\\\text{ iff } a \\\\models b \\\\text{ and } b \\\\models a$$\n",
        "\n",
        "### Important Logical Equivalencies \n",
        "\n",
        "+ Commutivity of and $$(a \\\\wedge b) \\\\equiv (b \\\\wedge a)$$\n",
        "+ Commutivity of or $$(a \\\\vee b) \\\\equiv (b \\\\vee a)$$\n",
        "+ Associativity of and $$((a \\\\wedge b) \\\\wedge c) \\\\equiv (a \\\\wedge (b \\\\wedge c))$$\n",
        "+ Associativity of or $$((a \\\\vee b) \\\\vee c) \\\\equiv (a \\\\vee (b \\\\vee c))$$\n",
        "+ Double negation $$\\\\neg (\\\\neg a) \\\\equiv a$$\n",
        "+ Contraposition $$ (a \\\\Rightarrow b) \\\\equiv (\\\\neg a \\\\Rightarrow \\\\neg b)$$\n",
        "+ Implication elimination $$ (a \\\\Rightarrow b) \\\\equiv (\\\\neg a \\\\vee b)$$\n",
        "+ Biconditional Implication $$ (a \\\\Leftrightarrow b) \\\\equiv ((a \\\\Rightarrow b) \\\\wedge (b \\\\Rightarrow a))$$\n",
        "+ DeMorgan $$\\\\neg(a \\\\wedge b) \\\\equiv (\\\\neg a \\\\vee \\\\neg b)$$\n",
        "+ DeMorgan $$\\\\neg(a \\\\vee b) \\\\equiv (\\\\neg a \\\\wedge \\\\neg b)$$\n",
        "+ Distributivity of or over and $$((a \\\\vee b) \\\\wedge c) \\\\equiv ((a \\\\vee b) \\\\wedge (a \\\\vee c))$$\n",
        "+ Distributivity of and over or $$((a \\\\wedge b) \\\\vee c) \\\\equiv ((a \\\\wedge b) \\\\vee (a \\\\wedge c))$$\n",
        "\n",
        "\n",
        "### Theorem Proving\n",
        "\n",
        "#### Inference and Proofs\n",
        "\n",
        "+ a proof is a chain of conclusions that reaches a desired goal\n",
        "+ Modus Ponensis written $$ \\\\frac{a \\\\Rightarrow b, a}{b}$$. This means that \\\n",
        "whenever a -> b and a are given, b can be inferred.\n",
        "+ And- Elimination  $$ \\\\frac{a \\\\wedge b}{a}$$ This means that whenever \\ \n",
        "a and bis given, a can be inferred\n",
        "+ monotonicity states that the set of entailed sentences can only increase as \\\n",
        "the knowledge base expands\n",
        "\n",
        "#### Proof by Resolution\n",
        "\n",
        "+ resolution yields a complete inference algorithm when coupled with any complete \\\n",
        "search algorithm\n",
        "+ Basically, resolution allows you to simplify sentences that use logical \\\n",
        "equivalences using other sentences in the knowledge base that consist of a single \\\n",
        "literal, leaving a shortened sentence known as a resolvent. \n",
        "+ $$\\\\frac{l_1 \\\\vee ..... l_k, m}{l_1 \\\\vee......\\\\vee l_{i-1} \\\\vee l_{i+1} \\\\vee .... l_k}$$\n",
        "if li and m are complementary (opposite). Basically, a disjunction of literals\\\n",
        "is shortened\n",
        "+ a unit clause is a \"disjunction\" of a single literal\n",
        "+ the unit-resolution can be expanded to full resolution given a series of ms\n",
        "+ The conjunctive normal form, or CNF, is a sentence expressed as a conjunction \\\n",
        "of clauses, $$Clause_1 \\\\wedge ... \\\\wedge Clause_n$$\n",
        "+ resolution closure is the set of all clauses derivable by repeatedly applying \\\n",
        "the resolution rule\n",
        "\n",
        "#### Horn and Definite Clauses\n",
        "+ a definite clause is a disjunction of lierals where exactly one is positive\n",
        "+ a horn clause is a disjunction where at most one literal is positive\n",
        "+ KBs with only definite clauses are interesting because\n",
        "  1. every clause can be written as an implication whose premise (body) is a \\\n",
        "  conjunction of positive literals and whose conclusion (head) is one postive \\\n",
        "  literal\n",
        "  2. Inference with Horn clauses can be done through forward and backward chaining \\\n",
        "  which is the basis for logic programming \n",
        "  3. Deciding entailment in horn clauses can be done in linear time\n",
        "\n",
        "#### Forward and Backward Chaining\n",
        " + this algorithm is sound, complete, data driven, and goal-directed\n",
        "\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Knowledge Base\" : \"(KB) Sentences that contains assertions about the world\", \n",
        "\"axioms\" : \"a sentence that is given withiut being derived from other sentences\",\n",
        "\"derived sentences\" : \" a new sentence that is derived from old sentences in \\\n",
        "a process called inference\" , \n",
        "\"background knowledge\" : \"information initially given in the KB\", \n",
        "\"knowledge level\": \"what an agent knows and what its goals are\",\n",
        "\"declarative approach\" : \"KB built by an agent telling it what it needs to know\",\n",
        "\"procedural approach\" :\"encodes desired behaviors directly\", \n",
        "\"truth perserving\" : \" a knowledge base that only derives entailed sentences, \\\n",
        "also known as sound\", \n",
        "\"completeness\" : \"an inference algorithm is complete if it can derive any entailed \\\n",
        "sentence\", \n",
        "\"grounding\" : \"how do we connect the logical reasoning to the true world? the \\\n",
        "answer is through sensors\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "2fc31cf5-b9c0-41b0-9a0e-5f7744a61e68"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "T3cm1WV542_a",
        "outputId": "1e35f8dc-8712-4aad-fced-e8d79768a61b"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}