{
  "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": "RrnIz1Oj30Ws"
      },
      "source": []
    },
    {
      "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",
      "execution_count": 129,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "lzaavW96tcxM",
        "outputId": "6e819284-f35a-4004-a8bb-4751fa544630"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ],
      "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)))"
      ]
    },
    {
      "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",
      "execution_count": 130,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "8DvZ57A-djo1",
        "outputId": "f7ee375b-aa3f-41db-d385-4fab312e89e3"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 131,
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "outputs": [],
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 132,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "Y2NfE1CKxzS-",
        "outputId": "8864726e-f3c0-4628-99f3-f4e9eebc14c6"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 139\n",
            "The length in characters is 907\n",
            "The length in words is 89\n",
            "The length in characters is 600\n",
            "The length in words is 54\n",
            "The length in characters is 384\n",
            "The length in words is 55\n",
            "The length in characters is 333\n",
            "The length in words is 92\n",
            "The length in characters is 613\n",
            "The length in words is 60\n",
            "The length in characters is 477\n",
            "The length in words is 162\n",
            "The length in characters is 1148\n"
          ]
        }
      ],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" Field of AI wants to both understand and build AI. Human vs. rational and though vs behavour \\\n",
        "combinations come into play. Turing test sums up if a computer can pass test of being a human. Total turing \\\n",
        "includes passing visual aspects as well. human-cognitive modeling approach looks at human way of thinking, \\\n",
        "introspection, psychological experimeents, brain imaging. Laws of though approach deals with Aristotle and his \\\n",
        "syllogisms to provide patterns for arguments, leading to logic. Probability allows rigorous reasing even when info is \\\n",
        "uncertain. Rational agent approach deals with allowing an agent to act rationally. Advantages over first two approaches are \\ \n",
        "more general than laws of thought and more amenable to science. Beneficial machines deals with value alignment problem \\\n",
        ", achieving agreement between our preferences and machines objectives. Want agents that are provably beneficial to humans. \"\"\" \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 = \"\"\" Distinction between weak AI and strong AI in definitions section. Informality argument states human behavour \\\n",
        "too complicated (Hubert Dreyfus). Good-Old_Fashioned AI - technology skeptics critisized, saying can't be done with computation. \\\n",
        "Embodied cognition says brain not separate from body. Argument from disability claims a machine can never to X. Mathematical objection \\\n",
        "argues some math like Godel's incompleteness theorem can't be solved by formal systems, but argument that computers are informal is made. \\\n",
        "Turing then comes up with Turing test to see whether machines can pass behavoural test. \"\"\"\n",
        "chapter27_2 = \"\"\" Problem of whether AI actually thinking or just looking like thinking. Turing introduces polite convention. \\\n",
        "Chinese room experiment refutes Turing. Searl proponent of biological naturalism, where mental states are high level emergent features. \\\n",
        "Strong theme of conciousness, awareness of world, and qualia, defined in definitions. Turing believes this question is largely irrevelent. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" An agent's choice of actions depends on the built-in knowledge as well as the entire \\\n",
        "percept sequence so far, but not on anything it hasn't percieved. Vacuum cleaner example to show agent and agent program \\\n",
        "Agent meant to be tool for analyzing, not an absolute characterization. Note, this section largely summarized in definitions. \"\"\"\n",
        "chapter2_2 = \"\"\" AI evaluated by consequentialism, the consequences of its actions. Better to design performance measures based \\\n",
        "on what someone actually is trying to achieve in an environment, rather than how we think the agent should act. \\\n",
        "What is rational, depends on performance measure, prior knowledge, actions, and percept sequence to date. Rationality is not omniscience, \\\n",
        "as omniscience knows actual outcome of actions - impossible in reality. Information gathering and exploration used to modify future \\\n",
        "percepts. With learning, an agent can become independent of prior knowledge, allowing it to succeed in many scenarios.\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" Task environment, PEAS defined in definitions section. Properties include: fully observable vs. partionally observable, \\\n",
        "single-agent vs. multi-agent, deterministic vs. nondeterministic, episodic vs. sequential, static vs. dynamic, discrete vs. continuous, \\\n",
        "known vs. unknown. All defined in definitions. Hardest case is partionally observable, multi-agent, non-deterministic, sequential, \\\n",
        "dynamic, continous, unknown. Note: known vs. unknown not a property of the environment. \\\n",
        " \"\"\"\n",
        "chapter2_4 = \"\"\" Job of AI is designing agent program to implement the agent function. Ideal to produce agent programs that cause \\\n",
        "rational behavour based off small program rather than a massive table. Simple reflex agent selects actions based on current percept. \\\n",
        "Randomized behavour can outperform non-randomized. Model-based reflex agents maintains an internal state of the world. Uses transition \\\n",
        "model. model-based agent = transition model + sensor model. Goal-based agents uses goal to decide desirable actions. Utility based agents \\\n",
        "maximize happiness, which is utility. Learning agents is reponsible for using learning element to make improvements. Components of agent \\\n",
        "programs can use atomic representation (indivisibl), or factored, which splits up state into fixed set of variables or attributes. \\\n",
        "Structured representation says that the various relationships between objects can be described explicitely. More expressive representation \\\n",
        "captures everything a less expressive one can capture, plus more. Localist repesentation is one-to-one mapping of concepts and memory \\\n",
        "locations. Distributed representation is if concept spread over many memory locations. \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" A rational agent selects an action that maximizes the expected value of its performance measure. \\\n",
        "Touchless faucets, thermostat, pet hamster can be viewed as agents. \\\n",
        "A rational agent is not guaranteed to find optimal solutions. \\\n",
        "To be rational, an agent must maximize its expected performance.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"rationality\" : \"doing the right thing\",\n",
        "\"Turing test\" : \"needs NLP, knowledge representation, automated reasoning, machine learning\",\n",
        "\"value alignment problem\" : \"values we put into machine must align with human\",\n",
        "\"percept\" : \"content an agent's sensors are percieving\",\n",
        "\"Weak AI\" : \"could act as if intelligent\",\n",
        "\"Strong AI\" : \"conciously thinking\",\n",
        "\"Embodied cognition\" : \"Doesn't make sense to consider brain separate from human\",\n",
        "\"Polite Convention\" : \"turing says extends to machines\",\n",
        "\"Chinese Room\" : \"John Searl rejects this, citing Chinese room thought experiment\",\n",
        "\"Qualia\" : \"technical term for intrinsic nature of experiences\",\n",
        "\"agent\" : \"anything that can perceive and act in an environment.\",\n",
        "\"rational agent\" : \"agent that acts to achieve the best outcome or expected outcome\",\n",
        "\"percept\" : \"content an agent's sensors are percieving\",\n",
        "\"percept sequence\" : \"complete history of everything an agent has perceived\",\n",
        "\"agent function\" : \"describes agent's behavour, maps a given percept sequence to an action\",\n",
        "\"agent program\" : \"internally, agent function implemented by agent program\",\n",
        "\"rational agent\" : \"an agent that does the right thing\",\n",
        "\"information gathering\" : \"doing actions to modify future percepts, like exploration\",\n",
        "\"Task environment\" : \"PEAS Performance, environment, actuators, sensors\",\n",
        "\"Fully observable\" : \"agents sensors give access to complete state of environment at all points in time\",\n",
        "\"Single agent\" : \"distinct from multi, depending on whether B's behavour maximizes performanc measure whose value depends on A behavour\",\n",
        "\"Deterministic\" : \"If next state completely determined by current state and agent's action\",\n",
        "\"Episodic\" : \"Agent's experiences divided into atomic episodes, as opposed to sequential, where current decision affects future (chess, taxi)\",\n",
        "\"Static vs. Dynamic\" : \"if environment can change while deliberating, then its dynamic\",\n",
        "\"discrete vs. Continuous\" : \"Chess is discrete, while taxi driving is continuous\",\n",
        "\"known vs. unknown\" : \": State of knowledge of agent’s knowledge about the “laws of physics” of the environment\",\n",
        "\"Agent\" : \"the architecture plus the program\",\n",
        "\"simple reflex agent\" : \"selects actions based on current percept, ignoring history\",\n",
        "\"goal-based agent\" : \"Needs a goal in order to choose actions that result in that goal\",\n",
        "\"utility-based agent\" : \"happy. Maximize expected utility while reaching goal\",\n",
        "\"learning agents\" : \"responsible for making improvements to the agent. Problem generator to explore actions\"\n",
        "\n",
        "\n",
        "}\n",
        "\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",
      "execution_count": 133,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1575
        },
        "id": "gYYeNcdM_maE",
        "outputId": "1c5d2672-47e4-4ea5-9fea-792d72c9219c"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Field of AI wants to both understand and build AI. Human vs. rational and though vs behavour combinations come into play. Turing test sums up if a computer can pass test of being a human. Total turing includes passing visual aspects as well. human-cognitive modeling approach looks at human way of thinking, introspection, psychological experimeents, brain imaging. Laws of though approach deals with Aristotle and his syllogisms to provide patterns for arguments, leading to logic. Probability allows rigorous reasing even when info is uncertain. Rational agent approach deals with allowing an agent to act rationally. Advantages over first two approaches are \\ \n",
              "more general than laws of thought and more amenable to science. Beneficial machines deals with value alignment problem , achieving agreement between our preferences and machines objectives. Want agents that are provably beneficial to humans. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Distinction between weak AI and strong AI in definitions section. Informality argument states human behavour too complicated (Hubert Dreyfus). Good-Old_Fashioned AI - technology skeptics critisized, saying can't be done with computation. Embodied cognition says brain not separate from body. Argument from disability claims a machine can never to X. Mathematical objection argues some math like Godel's incompleteness theorem can't be solved by formal systems, but argument that computers are informal is made. Turing then comes up with Turing test to see whether machines can pass behavoural test. \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Problem of whether AI actually thinking or just looking like thinking. Turing introduces polite convention. Chinese room experiment refutes Turing. Searl proponent of biological naturalism, where mental states are high level emergent features. Strong theme of conciousness, awareness of world, and qualia, defined in definitions. Turing believes this question is largely irrevelent. \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " An agent's choice of actions depends on the built-in knowledge as well as the entire percept sequence so far, but not on anything it hasn't percieved. Vacuum cleaner example to show agent and agent program Agent meant to be tool for analyzing, not an absolute characterization. Note, this section largely summarized in definitions. \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " AI evaluated by consequentialism, the consequences of its actions. Better to design performance measures based on what someone actually is trying to achieve in an environment, rather than how we think the agent should act. What is rational, depends on performance measure, prior knowledge, actions, and percept sequence to date. Rationality is not omniscience, as omniscience knows actual outcome of actions - impossible in reality. Information gathering and exploration used to modify future percepts. With learning, an agent can become independent of prior knowledge, allowing it to succeed in many scenarios.\n",
              "\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Task environment, PEAS defined in definitions section. Properties include: fully observable vs. partionally observable, single-agent vs. multi-agent, deterministic vs. nondeterministic, episodic vs. sequential, static vs. dynamic, discrete vs. continuous, known vs. unknown. All defined in definitions. Hardest case is partionally observable, multi-agent, non-deterministic, sequential, dynamic, continous, unknown. Note: known vs. unknown not a property of the environment.  \n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " Job of AI is designing agent program to implement the agent function. Ideal to produce agent programs that cause rational behavour based off small program rather than a massive table. Simple reflex agent selects actions based on current percept. Randomized behavour can outperform non-randomized. Model-based reflex agents maintains an internal state of the world. Uses transition model. model-based agent = transition model + sensor model. Goal-based agents uses goal to decide desirable actions. Utility based agents maximize happiness, which is utility. Learning agents is reponsible for using learning element to make improvements. Components of agent programs can use atomic representation (indivisibl), or factored, which splits up state into fixed set of variables or attributes. Structured representation says that the various relationships between objects can be described explicitely. More expressive representation captures everything a less expressive one can capture, plus more. Localist repesentation is one-to-one mapping of concepts and memory locations. Distributed representation is if concept spread over many memory locations. \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " A rational agent selects an action that maximizes the expected value of its performance measure. Touchless faucets, thermostat, pet hamster can be viewed as agents. A rational agent is not guaranteed to find optimal solutions. To be rational, an agent must maximize its expected performance.\n",
              " \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Rationality** - doing the right thing\n",
              "* **Turing test** - needs NLP, knowledge representation, automated reasoning, machine learning\n",
              "* **Value alignment problem** - values we put into machine must align with human\n",
              "* **Percept** - content an agent's sensors are percieving\n",
              "* **Weak ai** - could act as if intelligent\n",
              "* **Strong ai** - conciously thinking\n",
              "* **Embodied cognition** - Doesn't make sense to consider brain separate from human\n",
              "* **Polite convention** - turing says extends to machines\n",
              "* **Chinese room** - John Searl rejects this, citing Chinese room thought experiment\n",
              "* **Qualia** - technical term for intrinsic nature of experiences\n",
              "* **Agent** - anything that can perceive and act in an environment.\n",
              "* **Rational agent** - an agent that does the right thing\n",
              "* **Percept sequence** - complete history of everything an agent has perceived\n",
              "* **Agent function** - describes agent's behavour, maps a given percept sequence to an action\n",
              "* **Agent program** - internally, agent function implemented by agent program\n",
              "* **Information gathering** - doing actions to modify future percepts, like exploration\n",
              "* **Task environment** - PEAS Performance, environment, actuators, sensors\n",
              "* **Fully observable** - agents sensors give access to complete state of environment at all points in time\n",
              "* **Single agent** - distinct from multi, depending on whether B's behavour maximizes performanc measure whose value depends on A behavour\n",
              "* **Deterministic** - If next state completely determined by current state and agent's action\n",
              "* **Episodic** - Agent's experiences divided into atomic episodes, as opposed to sequential, where current decision affects future (chess, taxi)\n",
              "* **Static vs. dynamic** - if environment can change while deliberating, then its dynamic\n",
              "* **Discrete vs. continuous** - Chess is discrete, while taxi driving is continuous\n",
              "* **Known vs. unknown** - : State of knowledge of agent’s knowledge about the “laws of physics” of the environment\n",
              "* **Agent** - the architecture plus the program\n",
              "* **Simple reflex agent** - selects actions based on current percept, ignoring history\n",
              "* **Goal-based agent** - Needs a goal in order to choose actions that result in that goal\n",
              "* **Utility-based agent** - happy. Maximize expected utility while reaching goal\n",
              "* **Learning agents** - responsible for making improvements to the agent. Problem generator to explore actions\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 134,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "id": "DpBvu7EMx7sy",
        "outputId": "3036274b-dfb0-40c0-dced-a1626883d7f8"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The length in words is 518\n",
            "The length in characters is 3762\n"
          ]
        }
      ],
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" \n",
        "All data treated as objects\n",
        "\n",
        "Strong typing – every object has a fixed type\n",
        "\n",
        "Dynamic typing – don’t have to declare type of variable. Variables come into existence when first assigned. Drawback – type errors caught at runtime\n",
        "\n",
        "**Strings**\n",
        "\n",
        "Creation – cause use single our double quotes, triple for multiline string and docstring\n",
        "\n",
        "Concatenation – special use of +\n",
        "\n",
        "Prefixing with r means raw\n",
        "\n",
        "String formatting – print(“%s can speak %d languages” %(“C3PO”, 6000))\n",
        "\n",
        "Immutable\n",
        "\n",
        "*lists are mutable though, but can use y=x[:] to create a shallow copy of any sequence\n",
        "\n",
        "**Sequence Types: Tuples, Lists, and Strings**\n",
        "\n",
        "Tuple: tu = (23, ‘abc’, 4.56, (2,3), ‘def’) *immutable ordered sequence of items, can be mixed\n",
        "\n",
        "List: li = [‘abc’, 34, 4.34, 23] *mutable ordered sequence of items of mixed types\n",
        "\n",
        "Slicing: tu[1:4] = (‘abc’, 4.56, (2,3)). [a,b) format. Can do something like [1:-1]. \n",
        "\n",
        "Select every nth item is: t[1:-1:2]\n",
        "\n",
        "Tu[:2] copy from beginning\n",
        "\n",
        "Tu[2:] copy to very end\n",
        "\n",
        "List methods: append, index, count, remove, reverse, sort (reverse and sort both in-place)\n",
        "\n",
        "String methods: words.split(“ “) -> puts the words separated by space into list\n",
        "\n",
        "s.capitalize(), s.upper(), .strip(‘ –‘)\n",
        "\n",
        "Zip: a = [1, 2, 3]; b = [‘a’, ‘b’, ‘c’, ‘d’], list(zip(a, b))\n",
        "\n",
        "[(1, ‘a’), (2, ‘b’), (3, ‘c’)]\n",
        "\n",
        "List(zip(“foo”, “bar”))  -> [(‘f’, ‘b’), (‘o’, ‘a’), (‘o’, ‘r’))\n",
        "\n",
        "**Dictionaries**\n",
        "\n",
        "Unordered and work by hasing, so keys must be immutable\n",
        "\n",
        "D = {‘user’ : ‘R2D2’, ‘pswd’: 1234}\n",
        "\n",
        "D[‘user’] -> ‘R2D2’\n",
        "\n",
        "Assigning a value to an existing key replaces its value\n",
        "\n",
        "Methods: d.keys(), d.values(), d.items()\n",
        "\n",
        "**Functions**\n",
        "\n",
        "def get_final_answer(filename):\n",
        "\n",
        "\txxx\n",
        "\n",
        "\treturn total_counter\n",
        "\n",
        "can return multiple answers, return type is tuple\n",
        "\n",
        "Function overloading (add(int, int), add(int, int, int)), etc.) not allowed\n",
        "\n",
        "Operator overloading allowed with special methods\n",
        "\n",
        "Default values -> def myFun(b, c=3, d=”hello):\n",
        "\n",
        "***non-default argument should always precede default arguments, otherwise syntax error\n",
        "\n",
        "Can call arguments out of order if you specify which argument. myFun(c=43, b=1, a=2)\n",
        "\n",
        "‘*args’ accepts a variable number of non-keyword arguments. Def(print_everything(*args)\n",
        "\n",
        "‘**kwargs’ accept a variable number of keyword arguments\n",
        "\n",
        "Python is dynamic scope, sees most current value of the variables\n",
        "\n",
        "Functions are first-class objects: can by created, destroyed, passed to function, returned as a value, and have all other rights of a variable\n",
        "\n",
        "Map() and filter() useful higher order functions\n",
        "\n",
        "**Classes and Inheritance**\n",
        "\n",
        "class Student:\n",
        "\n",
        "\tuniv = “upenn” # class attribute\n",
        "\n",
        "\tdef __init__(self, name, dept)\n",
        "\n",
        "\t\tself.student_name= name\n",
        "\t\t…\n",
        "\n",
        "Subclass: can extend the definition of another class, but name of superclass in parentheses after subclasses name on first line of the definition\n",
        "-\tTo redefine a method of parent class, include new definition using same name\n",
        "\n",
        "**List comprehension**\n",
        "\n",
        "Squares = [x*x for x in nums]\n",
        "\n",
        "Filtered: [elem * 2 for elem in li if elem > 4]\n",
        "\n",
        "Extra for: acts just as a nested for loop\n",
        "\n",
        "Dictionary set comprehension: d = {k: v for k, v in lst1}\n",
        "\n",
        "Set comprehension: s = {x for x in lst2}\n",
        "\n",
        "**Iterators (they use memory efficiently)**\n",
        "\n",
        "K = [1,2,3]\n",
        "\n",
        "i = iter(k)\n",
        "\n",
        "next(i) -> 1\n",
        "\n",
        "next(i) -> 2\n",
        "\n",
        "**Generators**\n",
        "\n",
        "Each time __next__ is called for generator, method runs until it encounters yield, then stop and return the value that was yielded\n",
        "\n",
        "Benefits: less code, maintains local state automatically, values computed one at a time, avoid storing whole sequence in memory, good for aggregating, one pass, crucial for infinite sequences, bad if need to inspect individual values\n",
        "\n",
        "\n",
        "**Extra**\n",
        "\n",
        "Hash function defined as any function that can be used to map data of arbitrary size to a fixed size\n",
        "\n",
        "A python tuple can be created without using parentheses (returning multiple values)\n",
        " \"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(module2_lecture_notes.split(' ')))\n",
        "print(\"The length in characters is\", len(module2_lecture_notes))\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"Can't change inplace once created is immutable\",\n",
        "\"Strong typing\" : \"Every object has fixed type\",\n",
        "\"Dynamic typing\" : \"don't have to declary type of variable. come into existence when first assigned. Drawback: type errors caught at runtime\"\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 135,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1851
        },
        "id": "ydOK__lwWgdp",
        "outputId": "dc08a266-2ba2-4bfd-fa5c-25d9d5015530"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              " \n",
              "All data treated as objects\n",
              "\n",
              "Strong typing – every object has a fixed type\n",
              "\n",
              "Dynamic typing – don’t have to declare type of variable. Variables come into existence when first assigned. Drawback – type errors caught at runtime\n",
              "\n",
              "**Strings**\n",
              "\n",
              "Creation – cause use single our double quotes, triple for multiline string and docstring\n",
              "\n",
              "Concatenation – special use of +\n",
              "\n",
              "Prefixing with r means raw\n",
              "\n",
              "String formatting – print(“%s can speak %d languages” %(“C3PO”, 6000))\n",
              "\n",
              "Immutable\n",
              "\n",
              "*lists are mutable though, but can use y=x[:] to create a shallow copy of any sequence\n",
              "\n",
              "**Sequence Types: Tuples, Lists, and Strings**\n",
              "\n",
              "Tuple: tu = (23, ‘abc’, 4.56, (2,3), ‘def’) *immutable ordered sequence of items, can be mixed\n",
              "\n",
              "List: li = [‘abc’, 34, 4.34, 23] *mutable ordered sequence of items of mixed types\n",
              "\n",
              "Slicing: tu[1:4] = (‘abc’, 4.56, (2,3)). [a,b) format. Can do something like [1:-1]. \n",
              "\n",
              "Select every nth item is: t[1:-1:2]\n",
              "\n",
              "Tu[:2] copy from beginning\n",
              "\n",
              "Tu[2:] copy to very end\n",
              "\n",
              "List methods: append, index, count, remove, reverse, sort (reverse and sort both in-place)\n",
              "\n",
              "String methods: words.split(“ “) -> puts the words separated by space into list\n",
              "\n",
              "s.capitalize(), s.upper(), .strip(‘ –‘)\n",
              "\n",
              "Zip: a = [1, 2, 3]; b = [‘a’, ‘b’, ‘c’, ‘d’], list(zip(a, b))\n",
              "\n",
              "[(1, ‘a’), (2, ‘b’), (3, ‘c’)]\n",
              "\n",
              "List(zip(“foo”, “bar”))  -> [(‘f’, ‘b’), (‘o’, ‘a’), (‘o’, ‘r’))\n",
              "\n",
              "**Dictionaries**\n",
              "\n",
              "Unordered and work by hasing, so keys must be immutable\n",
              "\n",
              "D = {‘user’ : ‘R2D2’, ‘pswd’: 1234}\n",
              "\n",
              "D[‘user’] -> ‘R2D2’\n",
              "\n",
              "Assigning a value to an existing key replaces its value\n",
              "\n",
              "Methods: d.keys(), d.values(), d.items()\n",
              "\n",
              "**Functions**\n",
              "\n",
              "def get_final_answer(filename):\n",
              "\n",
              "\txxx\n",
              "\n",
              "\treturn total_counter\n",
              "\n",
              "can return multiple answers, return type is tuple\n",
              "\n",
              "Function overloading (add(int, int), add(int, int, int)), etc.) not allowed\n",
              "\n",
              "Operator overloading allowed with special methods\n",
              "\n",
              "Default values -> def myFun(b, c=3, d=”hello):\n",
              "\n",
              "***non-default argument should always precede default arguments, otherwise syntax error\n",
              "\n",
              "Can call arguments out of order if you specify which argument. myFun(c=43, b=1, a=2)\n",
              "\n",
              "‘*args’ accepts a variable number of non-keyword arguments. Def(print_everything(*args)\n",
              "\n",
              "‘**kwargs’ accept a variable number of keyword arguments\n",
              "\n",
              "Python is dynamic scope, sees most current value of the variables\n",
              "\n",
              "Functions are first-class objects: can by created, destroyed, passed to function, returned as a value, and have all other rights of a variable\n",
              "\n",
              "Map() and filter() useful higher order functions\n",
              "\n",
              "**Classes and Inheritance**\n",
              "\n",
              "class Student:\n",
              "\n",
              "\tuniv = “upenn” # class attribute\n",
              "\n",
              "\tdef __init__(self, name, dept)\n",
              "\n",
              "\t\tself.student_name= name\n",
              "\t\t…\n",
              "\n",
              "Subclass: can extend the definition of another class, but name of superclass in parentheses after subclasses name on first line of the definition\n",
              "-\tTo redefine a method of parent class, include new definition using same name\n",
              "\n",
              "**List comprehension**\n",
              "\n",
              "Squares = [x*x for x in nums]\n",
              "\n",
              "Filtered: [elem * 2 for elem in li if elem > 4]\n",
              "\n",
              "Extra for: acts just as a nested for loop\n",
              "\n",
              "Dictionary set comprehension: d = {k: v for k, v in lst1}\n",
              "\n",
              "Set comprehension: s = {x for x in lst2}\n",
              "\n",
              "**Iterators (they use memory efficiently)**\n",
              "\n",
              "K = [1,2,3]\n",
              "\n",
              "i = iter(k)\n",
              "\n",
              "next(i) -> 1\n",
              "\n",
              "next(i) -> 2\n",
              "\n",
              "**Generators**\n",
              "\n",
              "Each time __next__ is called for generator, method runs until it encounters yield, then stop and return the value that was yielded\n",
              "\n",
              "Benefits: less code, maintains local state automatically, values computed one at a time, avoid storing whole sequence in memory, good for aggregating, one pass, crucial for infinite sequences, bad if need to inspect individual values\n",
              "\n",
              "\n",
              "**Extra**\n",
              "\n",
              "Hash function defined as any function that can be used to map data of arbitrary size to a fixed size\n",
              "\n",
              "A python tuple can be created without using parentheses (returning multiple values)\n",
              " \n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - Can't change inplace once created is immutable\n",
              "* **Strong typing** - Every object has fixed type\n",
              "* **Dynamic typing** - don't have to declary type of variable. come into existence when first assigned. Drawback: type errors caught at runtime\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 136,
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Goal formulation -> problem formulation -> search -> execution. Abstraction is valid if can elaborate any abstract \\\n",
        "solution into a solution in more detailed world. Solution to any problem is a fixed sequence of actions. In partially observable \\\n",
        "solution would be different branching patterns. Optimal solution has the lowerst path cost. Process of removing detail is abstraction. \\\n",
        "Abstraction valid if we can elaborate any abstract solution into a solution in more detailed environment. \"\"\"\n",
        "chapter3_2 = \"\"\" Grid world and sokoban (8-tile) example problems. Real world route finding problem between cities. Touring problem \\\n",
        "is when a set of places must be visited. VLSI layout problem requires positioning of millions of components on chips, split into cell \\\n",
        "layout and channel routing. Robot navigation is generalization of route finding problem earlier. Automatic assembly sequencing of complex \\\n",
        "objects by robot has been standard practice since 1970's.  \"\"\"\n",
        "chapter3_3 = \"\"\" Search algorithms take a search problem as input and return solution or failure. Best-first search most general algorithm \\\n",
        "where you expand node with minimum value of an evaluation function. Data structures: tree with state, parent, action, path-cost. Priority, \\\n",
        "LIFO, FIFO queues all used. A cycle is a special case of a redundant path. Measuring performance is based on completeness, cost optimality, \\\n",
        " time complexity, and space complexity. To be complete, a search algorithm should be systematic.  \"\"\"\n",
        "chapter3_4 = \"\"\" \n",
        "**Breadth-first search** – complete even on infinite spaces. Cost-optimal. \\\n",
        "Memory requirements bigger problem than execution time, but time still important. COMPLETE, COST-OPTIMAL, T: O(b^d), S: O(b^d)\n",
        "\n",
        "**Dijkstra’s algorithm/uniform cost search** – Spreads out in waves of uniform cost function (implemented like best-first search \\\n",
        "with path-cost as evaluation function. Complete and cost-optimal. b^(d+1) space and time complexity when all actions costs equal. COMPLETE, COST-OPTIMAL, T: O(b^(1 + floor(C*/epsilon))), S: O(b^(1 + floor(C*/epsilon)))\n",
        "\n",
        "**Depth-first search** – always expands deepest node on the frontier. Is NOT cost-optimal, is incomplete in infinite state spaces. \\\n",
        "Smaller need for memory than breadth-first or uniform-cost.  O(bm) space. Backtracking version uses even less memory O(m). \\\n",
        "NOT COMPLETE, NOT COST-OPTIMAL, T: O(b^m), S: O(bm)\n",
        "\n",
        "**Depth-limited** – version of DFS where depth limit l is supplied. T: O(b^l), S: O(bl). Incomplete if poor choice of l. \\\n",
        "NOT COMPLETE, NOT COST-OPTIMAL, T: O(b^l), S: O(bl)\n",
        "\n",
        "**Iterative deepening search** – pick good value of l by trying all values first, 0, 1, 2… S: O(bd) when solution, \\\n",
        "or O(bm) on finite with no solution. Cost-optimal for problems where actions have the same cost, complete finite \\\n",
        "state spaces. T: O(b^d) when solution, O(b^m) when none. COMPLETE, COST-OPTIMAL, T: O(b^d), S: O(bd)\n",
        "\n",
        "**Bi-directional search** – searches forward from initial state and backward from goal state. COMPLETE, \\\n",
        "COST-OPTIMAL, <- (if both directions BFS or uniform-cost), T: O(b^(d/2)), S: O(b^(d/2))\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "Use DFS if: space restricted / there are many possible solutions with long paths and wrong paths are usually \\\n",
        "terminated quickly / search can be fine-tuned quickly\n",
        "\n",
        "Use BFS if: Possible infinite paths, some solutions have short paths, can quickly discard unlikely paths\n",
        "\n",
        "Graph search checks if a node has been visited before adding it to the search queue\n",
        "\n",
        "If a state is reached via multiple paths, tree search will create two separate nodes corresponding to each path \\\n",
        "(turns a linear problem into an exponential one potentially)\n",
        "\n",
        "BFS optimal for problems with unit costs all same / BFS complete for infinite-depth search space\n",
        " \"\"\"\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",
        "\"open-loop\" : \"agent ignores percepts once solution found and just goes along path\",\n",
        "\"closed-loop\" : \"agent safer monitering percepts even whle traveling solution path\",\n",
        "\"search problem\" : \"set of states, initial state, goal state(s), actions available, transition model, action cost function\",\n",
        "\"Best-first search\" : \"choose a node with minimum value of evaluation function to expand\",\n",
        "\"complete\" : \"guarenteed to find a solution when there is one and correctly report failure if not\",\n",
        "\"d\" : \"depth or number of actions in optimal solution\",\n",
        "\"m\" : \"maximum number of actions in any path\",\n",
        "\"b\" : \"branching factor or number of successors\",\n",
        "\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 137,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1089
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "645ae4c5-566e-4d61-ed12-6f845bf845ff"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " Goal formulation -> problem formulation -> search -> execution. Abstraction is valid if can elaborate any abstract solution into a solution in more detailed world. Solution to any problem is a fixed sequence of actions. In partially observable solution would be different branching patterns. Optimal solution has the lowerst path cost. Process of removing detail is abstraction. Abstraction valid if we can elaborate any abstract solution into a solution in more detailed environment. \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Grid world and sokoban (8-tile) example problems. Real world route finding problem between cities. Touring problem is when a set of places must be visited. VLSI layout problem requires positioning of millions of components on chips, split into cell layout and channel routing. Robot navigation is generalization of route finding problem earlier. Automatic assembly sequencing of complex objects by robot has been standard practice since 1970's.  \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " Search algorithms take a search problem as input and return solution or failure. Best-first search most general algorithm where you expand node with minimum value of an evaluation function. Data structures: tree with state, parent, action, path-cost. Priority, LIFO, FIFO queues all used. A cycle is a special case of a redundant path. Measuring performance is based on completeness, cost optimality,  time complexity, and space complexity. To be complete, a search algorithm should be systematic.  \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " \n",
              "**Breadth-first search** – complete even on infinite spaces. Cost-optimal. Memory requirements bigger problem than execution time, but time still important. COMPLETE, COST-OPTIMAL, T: O(b^d), S: O(b^d)\n",
              "\n",
              "**Dijkstra’s algorithm/uniform cost search** – Spreads out in waves of uniform cost function (implemented like best-first search with path-cost as evaluation function. Complete and cost-optimal. b^(d+1) space and time complexity when all actions costs equal. COMPLETE, COST-OPTIMAL, T: O(b^(1 + floor(C*/epsilon))), S: O(b^(1 + floor(C*/epsilon)))\n",
              "\n",
              "**Depth-first search** – always expands deepest node on the frontier. Is NOT cost-optimal, is incomplete in infinite state spaces. Smaller need for memory than breadth-first or uniform-cost.  O(bm) space. Backtracking version uses even less memory O(m). NOT COMPLETE, NOT COST-OPTIMAL, T: O(b^m), S: O(bm)\n",
              "\n",
              "**Depth-limited** – version of DFS where depth limit l is supplied. T: O(b^l), S: O(bl). Incomplete if poor choice of l. NOT COMPLETE, NOT COST-OPTIMAL, T: O(b^l), S: O(bl)\n",
              "\n",
              "**Iterative deepening search** – pick good value of l by trying all values first, 0, 1, 2… S: O(bd) when solution, or O(bm) on finite with no solution. Cost-optimal for problems where actions have the same cost, complete finite state spaces. T: O(b^d) when solution, O(b^m) when none. COMPLETE, COST-OPTIMAL, T: O(b^d), S: O(bd)\n",
              "\n",
              "**Bi-directional search** – searches forward from initial state and backward from goal state. COMPLETE, COST-OPTIMAL, <- (if both directions BFS or uniform-cost), T: O(b^(d/2)), S: O(b^(d/2))\n",
              " \n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "Use DFS if: space restricted / there are many possible solutions with long paths and wrong paths are usually terminated quickly / search can be fine-tuned quickly\n",
              "\n",
              "Use BFS if: Possible infinite paths, some solutions have short paths, can quickly discard unlikely paths\n",
              "\n",
              "Graph search checks if a node has been visited before adding it to the search queue\n",
              "\n",
              "If a state is reached via multiple paths, tree search will create two separate nodes corresponding to each path (turns a linear problem into an exponential one potentially)\n",
              "\n",
              "BFS optimal for problems with unit costs all same / BFS complete for infinite-depth search space\n",
              " \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **Open-loop** - agent ignores percepts once solution found and just goes along path\n",
              "* **Closed-loop** - agent safer monitering percepts even whle traveling solution path\n",
              "* **Search problem** - set of states, initial state, goal state(s), actions available, transition model, action cost function\n",
              "* **Best-first search** - choose a node with minimum value of evaluation function to expand\n",
              "* **Complete** - guarenteed to find a solution when there is one and correctly report failure if not\n",
              "* **D** - depth or number of actions in optimal solution\n",
              "* **M** - maximum number of actions in any path\n",
              "* **B** - branching factor or number of successors\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 138,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Greedy best-first search – expand first node with the lowest h(n) value. f(n) = h(n). \\\n",
        "Complete in finite spaces, but not infinite. O(|V|) in worst case for both T and S.  Can be reduced to O(bm) \\\n",
        "with a good heuristic function on certain problems.  In contrast, A\\* search – f(n) = g(n) + h(n), where g(n) \\\n",
        "is path cost from initial state to node n, and h(n) is the estimated cost of the shortest path from n to the goal state. \\\n",
        "A\\* is complete (if state space finite). A\\* being optimal depends on the heuristic. Ann admissible heuristic is one that never \\\n",
        "overestimates the cost to reach a goal (optimistic).  If h(n) is admissible, then A* is cost-optimal. if h(n) not admissible, \\\n",
        "A* may or may not be cost-optimal. Consistency is a stronger property. Consistent if, for every node n and every successor n’ of \\\n",
        "n generated by an action a, we have: h(n) <= c(n, a, n’) + h(n’). Every consistent heuristic is admissible (but not vice versa). \n",
        "\n",
        "Can use search contours to visualize expansion. Surely expanded nodes is when A* expands all nodes that can be reached from initial \\\n",
        "state on a path that has f(n) < C\\*. A\\* might then expand some nodes right on the goal contour (f(n) = C\\*). A\\* expands no nodes with \\\n",
        "f(n) > C\\* (C\\* is cost of optimal solution path). A\\* is complete, cost-optimal and optimally efficient. Only downside is the exponential \\\n",
        "nature of it. Satisficing solutions is similar to A\\*, but accepting sub-optimal solutions by either using inadmissible heuristic or \\\n",
        "weighted A\\*(which is a somewhat greedy A-star). Can also use bounded suboptimal search, bounded-cost search, and unbounded-cost search. Memory \\\n",
        "bounded search problems can be described here. Beam search limits the size of the frontier. Iterative deepening A\\* search . \\\n",
        "Recursive best-first search (RBFS), attempts to mimic standard best-first search but using only linear space using backed up \\\n",
        "values, somewhat more efficient than IDA\\*, but excessive node generation still. MA\\* and SMA\\* determine how much memory we \\\n",
        "have available and are allowed to use all of it, SMA complete for any reachable solution, optimal if optimal solution is \\\n",
        "reachable. Memory limitations can still make a problem intractable from the point of view of computation time (thrashing). \n",
        "\"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\" \n",
        "**Branching factor** b\\* example is if A* finds a solution at depth = 5 using 52 nodes, then effective branching factor is \\\n",
        "1.92. N + 1 = 1 + b\\* + (b\\*)^2 + … + (b\\*)^d. The **effective depth** characterizes effect of A\\* pruning as \\\n",
        "reducing the effective depth by a constant kh compared to the true depth. Thus making total search cost O(bd – kh) \\\n",
        "compared to O(bd) for a uniformed search. h2 dominates h1. Therefore, h2 always better. for any node, h2(n) >= h1(n). Domination \\\n",
        "translates directly to efficiency. A relaxed problem is a problem with few restrictions on the actions. Used to come \\\n",
        "up with a better heuristic. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. \\\n",
        "Admissible heuristics can also be generated from subproblems using pattern databases (store exact solutions for every possible subproblem \\\n",
        "of instance). Can generate heuristics with landmarks – use precomputation using a few chosen landmark points. Uses differential heuristic, \\\n",
        "goal on optimal path from n to the landmark to be useful. Can get better heuristic by learning to search better using metalevel state space, \\\n",
        "goal of learning is to minimize the total cost of problem solving, trading off computational expense and path cost. Can get better heuristic \\\n",
        "simply by using experience, like solving lots of 8-puzzles.\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "Priority queue used by A\\*, Greedy Best-first search, uniform cost search\n",
        "\n",
        "Quiz implies that “graph-search of A\\* is optimal as long as the heuristic is admissible” is FALSE\n",
        "\n",
        "H2(n) >= h1(n), then h2 is more accurate than h1\n",
        "\n",
        "A\\* uses heuristic to prune search space so that the use of space is effectively O(bd).\n",
        "\n",
        "If h1(d) < h2(d) for all d, then A\\* search using h2 will not expand more nodes than A\\* search using h1\n",
        "\n",
        "A well-designed heuristic will have a branching factor close to 1. (True, smaller is better/more efficient)\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Informed search\" : \"uses domain-specific hints in form of heuristic function to find solution more efficiently\",   \n",
        "\"Greedy best-first search\" : \"expand first node with the lowest h(n) value. f(n) = h(n). Complete in finite spaces, but not infinite.\",\n",
        "\"Admissibility\" : \"an admissible heuristic is one that never overestimates the cost to reach a goal (optimistic).\", \n",
        "\"Consistency\" : \"Consistent if we have: h(n) <= c(n, a, n’) + h(n’)\",\n",
        "\"Satisficing solution\" : \"A\\*, but accepting sub-optimal solutions by either using inadmissible heuristic or weighted A\\*\",\n",
        "\"Effective depth\" : \"Characterizes effect of A\\* pruning as reducing the effective depth by a constant kh  compared to the true depth.\",\n",
        "\"Relaxed Problem\" : \"a problem with few restrictions on the actions. Used to come up with a better heuristic. \"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 139,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 921
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "3bc16dbd-0079-4238-da00-c7046676ad4e"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " Greedy best-first search – expand first node with the lowest h(n) value. f(n) = h(n). Complete in finite spaces, but not infinite. O(|V|) in worst case for both T and S.  Can be reduced to O(bm) with a good heuristic function on certain problems.  In contrast, A\\* search – f(n) = g(n) + h(n), where g(n) is path cost from initial state to node n, and h(n) is the estimated cost of the shortest path from n to the goal state. A\\* is complete (if state space finite). A\\* being optimal depends on the heuristic. Ann admissible heuristic is one that never overestimates the cost to reach a goal (optimistic).  If h(n) is admissible, then A* is cost-optimal. if h(n) not admissible, A* may or may not be cost-optimal. Consistency is a stronger property. Consistent if, for every node n and every successor n’ of n generated by an action a, we have: h(n) <= c(n, a, n’) + h(n’). Every consistent heuristic is admissible (but not vice versa). \n",
              "\n",
              "Can use search contours to visualize expansion. Surely expanded nodes is when A* expands all nodes that can be reached from initial state on a path that has f(n) < C\\*. A\\* might then expand some nodes right on the goal contour (f(n) = C\\*). A\\* expands no nodes with f(n) > C\\* (C\\* is cost of optimal solution path). A\\* is complete, cost-optimal and optimally efficient. Only downside is the exponential nature of it. Satisficing solutions is similar to A\\*, but accepting sub-optimal solutions by either using inadmissible heuristic or weighted A\\*(which is a somewhat greedy A-star). Can also use bounded suboptimal search, bounded-cost search, and unbounded-cost search. Memory bounded search problems can be described here. Beam search limits the size of the frontier. Iterative deepening A\\* search . Recursive best-first search (RBFS), attempts to mimic standard best-first search but using only linear space using backed up values, somewhat more efficient than IDA\\*, but excessive node generation still. MA\\* and SMA\\* determine how much memory we have available and are allowed to use all of it, SMA complete for any reachable solution, optimal if optimal solution is reachable. Memory limitations can still make a problem intractable from the point of view of computation time (thrashing). \n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " \n",
              "**Branching factor** b\\* example is if A* finds a solution at depth = 5 using 52 nodes, then effective branching factor is 1.92. N + 1 = 1 + b\\* + (b\\*)^2 + … + (b\\*)^d. The **effective depth** characterizes effect of A\\* pruning as reducing the effective depth by a constant kh compared to the true depth. Thus making total search cost O(bd – kh) compared to O(bd) for a uniformed search. h2 dominates h1. Therefore, h2 always better. for any node, h2(n) >= h1(n). Domination translates directly to efficiency. A relaxed problem is a problem with few restrictions on the actions. Used to come up with a better heuristic. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. Admissible heuristics can also be generated from subproblems using pattern databases (store exact solutions for every possible subproblem of instance). Can generate heuristics with landmarks – use precomputation using a few chosen landmark points. Uses differential heuristic, goal on optimal path from n to the landmark to be useful. Can get better heuristic by learning to search better using metalevel state space, goal of learning is to minimize the total cost of problem solving, trading off computational expense and path cost. Can get better heuristic simply by using experience, like solving lots of 8-puzzles.\n",
              " \n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " \n",
              "Priority queue used by A\\*, Greedy Best-first search, uniform cost search\n",
              "\n",
              "Quiz implies that “graph-search of A\\* is optimal as long as the heuristic is admissible” is FALSE\n",
              "\n",
              "H2(n) >= h1(n), then h2 is more accurate than h1\n",
              "\n",
              "A\\* uses heuristic to prune search space so that the use of space is effectively O(bd).\n",
              "\n",
              "If h1(d) < h2(d) for all d, then A\\* search using h2 will not expand more nodes than A\\* search using h1\n",
              "\n",
              "A well-designed heuristic will have a branching factor close to 1. (True, smaller is better/more efficient)\n",
              " \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Informed search** - uses domain-specific hints in form of heuristic function to find solution more efficiently\n",
              "* **Greedy best-first search** - expand first node with the lowest h(n) value. f(n) = h(n). Complete in finite spaces, but not infinite.\n",
              "* **Admissibility** - an admissible heuristic is one that never overestimates the cost to reach a goal (optimistic).\n",
              "* **Consistency** - Consistent if we have: h(n) <= c(n, a, n’) + h(n’)\n",
              "* **Satisficing solution** - A\\*, but accepting sub-optimal solutions by either using inadmissible heuristic or weighted A\\*\n",
              "* **Effective depth** - Characterizes effect of A\\* pruning as reducing the effective depth by a constant kh  compared to the true depth.\n",
              "* **Relaxed problem** - a problem with few restrictions on the actions. Used to come up with a better heuristic. \n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 140,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" When large number of agents,consider considering in aggregate as an economy. \\\n",
        "Use pruning to make search space more efficient, and heuristic evaluatin function to estimate who is winning. \\\n",
        "Two-player zero sum games described as deterministic, two-player, turn-taking, perfect information, zero-sum games \\\n",
        "Game defined by: starting state, to-move(s), actions(s), result(s,a), is-terminal(s), utility(s, p). Game tree is a search tree \\\n",
        "that will follow paths till terminal state is reached.\n",
        " \"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "minimax search accounts for games where both players play optimally. It's a recursive algorithm down to leaves and then \\\n",
        "backs up minimax values through tree while unwinding. Technically performs complete depth-first search. b = legal moves, \\\n",
        "m = max depth of the tree. T: O(b^m), S: O(bm), or O(m) if actions generated one at a time. Multiplayer games involve alliances. \n",
        "\n",
        "Alpha-beta pruning allows for pruning without examining every state. alpha/beta definition below. Effectiveness dependent on the order \\\n",
        "in which the leaves are examined. If done perfectly, alpha-beta examines O(b^(m/2)), compared to O(b^m) for minimax. Makes it sqrt(b) \\\n",
        "branching factor instead of b. \n",
        "\n",
        "Type A and Type B strategies (defs below) popular opposite strategies. \n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "Can apply heuristic evaluation function to states to cut off search early. replace terminal test with cutoff test. Good eval \\\n",
        "function = between loss and win, fast computation, correlated with chance of winning. Works by calculating various features of state. \\\n",
        "Weighted linear function like in chess, where piece number, type, position computed based on utility. Eval function should only be applied \\\n",
        "to quiescent position (def below). Can mitigate horizen effect using singular extensions (def below)\n",
        "\n",
        "Forward pruning saves computation time, but risks an error. Beam search decent approach to this. Another possibility is the late \\\n",
        "move reduction strategy, which assumes the move ordering has been done well, and therefore much later moves in the list are less \\\n",
        "likely to be good. Games like chess can use a policy to map certain moves, such as at the beginning or the end of the game, to make \\\n",
        "computation much less complex.\n",
        " \"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "Stochastic games include unpredictability. Use expected value instead. For minmax type games, called expectiminimax value. \\\n",
        "Chance games must use evaluation function that returns a positive linear transformation of the probability of winning. Expectimax \\\n",
        "will take O(b^m*n^m) time cause it must consider all dice rolls. \n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "agents preference captured by utility function. Try to maximize the expected utility. If an agent acts to maximize this \\\n",
        "then agent will achieve highest possible performance when averaged. Constraints on rational preferences are: orderability, \\\n",
        "transitivity, continuity, substitutability, monotonicity, and decomposability. In deterministic environments, agent only needs \\\n",
        "preference on states, this is the value function (ordinal utility function). \n",
        " \"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "Constraints on rational preferences are: orderability, \\\n",
        "transitivity, continuity, substitutability, monotonicity, and decomposability. In deterministic environments, agent only needs \\\n",
        "preference on states, this is the value function (ordinal utility function). \n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" Utility function maps from lotteries to real numbers. Preference elicitation gives choices to humans and then pins down \\\n",
        "utility function from that.  S-curve shape when agents are risk-averse. Agent with linear curve is risk neutral. Real outcome from an \\\n",
        "agent will be significantly worse, even when unbiased, due to optimizers curse. \n",
        "\n",
        "Decision theory is normative, describes how agent should act. Descricptive would describe how an agent actually acts. certainty effect, \\\n",
        "framing effect, and anchoring effect all describe reasons why humans may act irrationally. \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "Zero-sum assumption lets us use one function to describe goodness of both players. f(n) > = if MAX in winning position n. \\\n",
        "f(n) < 0 if MIN is winning in position n. \n",
        "\n",
        "Random variable represents an event whose outcome is unknown. Probability distribution is assignment of weights to outcomes.\n",
        "\n",
        "Objectivist / Frequentists average over repeated experiments\n",
        "\n",
        "Subjectivists / Bayseian answer has degrees of belief about unobserved variables based on other condtions / states\n",
        "\n",
        "If opponent is using a minmax result 80% of the time and moving randomly otherwise, use Expecimax tree search\n",
        "\n",
        "As depth increases in probabilistic search trees, usefulness of search is diminished, meaning limiting depth is less damaging, but \\\n",
        "pruning is trickier. \n",
        "\n",
        "MAX can't just search for his solution at start of game because: best possible move depends on min's decision\n",
        "\n",
        "Evaluation function returns estimate of the expected utility of game from a given position\n",
        "\n",
        "Minimax algorithm with pruning will take about same time as without if search space is small\n",
        "\n",
        "alpha-beta limitation: assumes leaf evaluations randomly distributed\n",
        "\n",
        "If outcome deterministic, minimax and expectiminimax will give same solutions\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"pruning\" : \"ignoring portions of the search tree\",\n",
        "\"evaluation function\" : \"heuristic to estimate who is winning based on features or averageing simulations\",\n",
        "\"terminal test\" : \"true when game is over and false otherwise\",\n",
        "\"game tree\" : \"search tree that follows every sequence until terminal state\",\n",
        "\"ply\" : \"one move by one player, therefore one level deeper in game tree\",\n",
        "\"minimax search\" : \"full DFS. T: O(b^m), S: O(bm), or O(m) if actions generated one at a time\",\n",
        "\"alpha\" : \"highest-value choice for MAX so far at any choice point along the path (at least)\",\n",
        "\"beta\" : \"lowest-value choice for MIN so far at any choice point along the path. (at most)\",\n",
        "\"killer moves\" : \"best moves, tried first - killer move heuristic\",\n",
        "\"transposition table\" : \"catches repreated sequences\",\n",
        "\"Type A strategy\" : \"considers all moves to certain depth, then heuristic eval to get utility of states at that depth\",\n",
        "\"Type B strategy\" : \"ignores moves that look bad, follows promising paths far as possible\",\n",
        "\"quiescent\" : \"position where no pending move would wildly swing evaluation\",\n",
        "\"horizon effect\" : \"when program facing enemy move that would end game, but it takes delaying moves\",\n",
        "\"singular extension\" : \"moves that are way better than all other moves\",\n",
        "\"forward pruning\" : \"prunes moves that seem poor, but could be good\",\n",
        "\"beam search\" : \"consider beam of 'n' best moves rather than all possible\",\n",
        "\"stochastic game\" : \"game with unpredictable elements\",\n",
        "\"expected value\" : \"average over all possible outcomes of chance nodes\",\n",
        "\"utility function\" : \"assigns a single number to express desirability of the state\",\n",
        "\"principle of maximum expected utility\" : \"ration agent should maximize expected utility\",\n",
        "\"lottery\" : \"set of outcomes for each action, each action like a ticket\",\n",
        "\"micromort\" : \"one in a million chance of death, used in medical community\",\n",
        "\"certainty effect\" : \"people are attracted to certain gains\",\n",
        "\"framing effect\" : \"exact wording can have influence on decision\",\n",
        "\"anchoring effect\" : \"200 dollar wine makes 55 dollar wine seem cheap!\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 141,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1693
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "2c944786-e35c-4425-95b3-eb50483b08fc"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " When large number of agents,consider considering in aggregate as an economy. Use pruning to make search space more efficient, and heuristic evaluatin function to estimate who is winning. Two-player zero sum games described as deterministic, two-player, turn-taking, perfect information, zero-sum games Game defined by: starting state, to-move(s), actions(s), result(s,a), is-terminal(s), utility(s, p). Game tree is a search tree that will follow paths till terminal state is reached.\n",
              " \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " \n",
              "minimax search accounts for games where both players play optimally. It's a recursive algorithm down to leaves and then backs up minimax values through tree while unwinding. Technically performs complete depth-first search. b = legal moves, m = max depth of the tree. T: O(b^m), S: O(bm), or O(m) if actions generated one at a time. Multiplayer games involve alliances. \n",
              "\n",
              "Alpha-beta pruning allows for pruning without examining every state. alpha/beta definition below. Effectiveness dependent on the order in which the leaves are examined. If done perfectly, alpha-beta examines O(b^(m/2)), compared to O(b^m) for minimax. Makes it sqrt(b) branching factor instead of b. \n",
              "\n",
              "Type A and Type B strategies (defs below) popular opposite strategies. \n",
              " \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "\n",
              "Can apply heuristic evaluation function to states to cut off search early. replace terminal test with cutoff test. Good eval function = between loss and win, fast computation, correlated with chance of winning. Works by calculating various features of state. Weighted linear function like in chess, where piece number, type, position computed based on utility. Eval function should only be applied to quiescent position (def below). Can mitigate horizen effect using singular extensions (def below)\n",
              "\n",
              "Forward pruning saves computation time, but risks an error. Beam search decent approach to this. Another possibility is the late move reduction strategy, which assumes the move ordering has been done well, and therefore much later moves in the list are less likely to be good. Games like chess can use a policy to map certain moves, such as at the beginning or the end of the game, to make computation much less complex.\n",
              " \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "Stochastic games include unpredictability. Use expected value instead. For minmax type games, called expectiminimax value. Chance games must use evaluation function that returns a positive linear transformation of the probability of winning. Expectimax will take O(b^m*n^m) time cause it must consider all dice rolls. \n",
              " \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " \n",
              "agents preference captured by utility function. Try to maximize the expected utility. If an agent acts to maximize this then agent will achieve highest possible performance when averaged. Constraints on rational preferences are: orderability, transitivity, continuity, substitutability, monotonicity, and decomposability. In deterministic environments, agent only needs preference on states, this is the value function (ordinal utility function). \n",
              " \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "\n",
              "Constraints on rational preferences are: orderability, transitivity, continuity, substitutability, monotonicity, and decomposability. In deterministic environments, agent only needs preference on states, this is the value function (ordinal utility function). \n",
              " \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Utility function maps from lotteries to real numbers. Preference elicitation gives choices to humans and then pins down utility function from that.  S-curve shape when agents are risk-averse. Agent with linear curve is risk neutral. Real outcome from an agent will be significantly worse, even when unbiased, due to optimizers curse. \n",
              "\n",
              "Decision theory is normative, describes how agent should act. Descricptive would describe how an agent actually acts. certainty effect, framing effect, and anchoring effect all describe reasons why humans may act irrationally. \n",
              "\n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " \n",
              "Zero-sum assumption lets us use one function to describe goodness of both players. f(n) > = if MAX in winning position n. f(n) < 0 if MIN is winning in position n. \n",
              "\n",
              "Random variable represents an event whose outcome is unknown. Probability distribution is assignment of weights to outcomes.\n",
              "\n",
              "Objectivist / Frequentists average over repeated experiments\n",
              "\n",
              "Subjectivists / Bayseian answer has degrees of belief about unobserved variables based on other condtions / states\n",
              "\n",
              "If opponent is using a minmax result 80% of the time and moving randomly otherwise, use Expecimax tree search\n",
              "\n",
              "As depth increases in probabilistic search trees, usefulness of search is diminished, meaning limiting depth is less damaging, but pruning is trickier. \n",
              "\n",
              "MAX can't just search for his solution at start of game because: best possible move depends on min's decision\n",
              "\n",
              "Evaluation function returns estimate of the expected utility of game from a given position\n",
              "\n",
              "Minimax algorithm with pruning will take about same time as without if search space is small\n",
              "\n",
              "alpha-beta limitation: assumes leaf evaluations randomly distributed\n",
              "\n",
              "If outcome deterministic, minimax and expectiminimax will give same solutions\n",
              "\n",
              "\n",
              "\n",
              " \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Pruning** - ignoring portions of the search tree\n",
              "* **Evaluation function** - heuristic to estimate who is winning based on features or averageing simulations\n",
              "* **Terminal test** - true when game is over and false otherwise\n",
              "* **Game tree** - search tree that follows every sequence until terminal state\n",
              "* **Ply** - one move by one player, therefore one level deeper in game tree\n",
              "* **Minimax search** - full DFS. T: O(b^m), S: O(bm), or O(m) if actions generated one at a time\n",
              "* **Alpha** - highest-value choice for MAX so far at any choice point along the path (at least)\n",
              "* **Beta** - lowest-value choice for MAX so far at any choice point along the path. (at most)\n",
              "* **Killer moves** - best moves, tried first - killer move heuristic\n",
              "* **Transposition table** - catches repreated sequences\n",
              "* **Type a strategy** - considers all moves to certain depth, then heuristic eval to get utility of states at that depth\n",
              "* **Type b strategy** - ignores moves that look bad, follows promising paths far as possible\n",
              "* **Quiescent** - position where no pending move would wildly swing evaluation\n",
              "* **Horizon effect** - when program facing enemy move that would end game, but it takes delaying moves\n",
              "* **Singular extension** - moves that are way better than all other moves\n",
              "* **Forward pruning** - prunes moves that seem poor, but could be good\n",
              "* **Beam search** - consider beam of 'n' best moves rather than all possible\n",
              "* **Stochastic game** - game with unpredictable elements\n",
              "* **Expected value** - average over all possible outcomes of chance nodes\n",
              "* **Utility function** - assigns a single number to express desirability of the state\n",
              "* **Principle of maximum expected utility** - ration agent should maximize expected utility\n",
              "* **Lottery** - set of outcomes for each action, each action like a ticket\n",
              "* **Micromort** - one in a million chance of death, used in medical community\n",
              "* **Certainty effect** - people are attracted to certain gains\n",
              "* **Framing effect** - exact wording can have influence on decision\n",
              "* **Anchoring effect** - 200 dollar wine makes 55 dollar wine seem cheap!\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 142,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "A constraint satisfaction problem is one in which a factored representation is used for each state, which is a set of variables, \\\n",
        "each of which has a value. If every variable has a value that satisfies the constraints, then it is considered solved. Map coloring \\\n",
        "is an example problem that is a CSP. Job-shop scheduling can be another CSP problem using precedence constraints. A discrete domain can \\\n",
        "be infinite (integers, strings). Common real world CSP problems have continous domains, generally considered linear programming problems. \\\n",
        "Several types of constraints, such as unary, binary, global, and preference. Can represent restraints using constraint hypergraph. \n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "CSP can either generate a new variable assignment, or perform constraint propagation. Local consistency shows that enforcing constraints on \\\n",
        "one part of the graph will lead to narrowing options further along in the graph. Types of consistency are node consistency, arc consistency, \\\n",
        "path consistency, K-consistency, and global constraints (all defined below). CSP is NP-complete in general, leading to exponential time to \\\n",
        "establish n-consistency, and also exponential space with regards to n. Sudoku example given.\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "Commutativity allows to reduce search space by realizing that order of application doesn't matter, making number of leaves d^n as hoped. \\\n",
        "Use minimum remainging heuristic (or degree heuristic if tie) to choose a varialbe, and then use least-constraining-value on that variable to \\\n",
        "choose which value to select (i.e., the one that leaves neighbors with the most choices). Forward checking says that when \\\n",
        "a variable X is assigned, for all Y's connected to X, deleted non-consistent values for those Y's. MAC (Maintaining Arc Consistency) \\\n",
        "algorithm is similar, it just progogates through entire graph, rather than stopping after one variable. Chronological backtracking \\\n",
        "allows most recent decision point to be revisited. Backjumping will backtrack to the most recent assignment in the conflict set. \\\n",
        "Constraint learning can be used to achieve much better efficiency on complex CSP problems by not running into the same problems (called \\\n",
        "no-good problems) again.\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "Local-search algorithms are effective for CSP. Min-conflicts heuristic to select value that has least conflicts. Constraint weighting is \\\n",
        "another way to do this, such as difficult constraints being assigned higher weights over time, allowing for faster solutions on future \\\n",
        "algorithm runs. \n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "Independence found by finding connected components of the constraint graph for a CSP problem. Directional arc consistency means that \\\n",
        "under ording of variables, X1, X2... Xn, if and only if each Xi arc-consistent with each Xj (j > i). Solve problems like these using \\\n",
        "topoligical sort. Algorithm using cycle cutsets (Defined below) can be used to find an answer to CSP's. Can also do tree decomposition in \\\n",
        "order to reduce a constraint graph to a tree. 3 conditions: every variable must appear in at least one of tree nodes, if 2 variables \\\n",
        "conntected, must appear connected in at least one tree node, and if variable appears in two nodes in the tree, it must appear in every node \\\n",
        "along the path connecting those nodes. NOTE: CSP's with constraint graphs of bounded tree width are solvable in polynomial time. Noted at \\\n",
        "end of chapter that you can use value symmetry such as on map problem by imposing arbitrary order (NT < SA < WA alphabetically), so that \\\n",
        "only one of d! solutions is possible (simimlar to idea covered earlier in chapter). \n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "Advantage to CSP's is they can be solved with general purpose algorithms. Also CPS knows which variables violate constraint, \\\n",
        "and can thus focus the search. Also CPS's automatically prune off all branches that violate constraints. \n",
        "\n",
        "Which variable to assign next? 1. Most constrained (if tied, most constraining). \n",
        "\n",
        "What order should variables values be tried? Least constraining value\n",
        "\n",
        "Detect inevitable failure by forward checking\n",
        "\n",
        "If d values, checking arc(i,j) takes O(d^2) time\n",
        "\n",
        "AC-3: at each iteration, 1. only need to examine Xi where at lesat one neighbor of Xi has lost a value. 2. if Xi loses a value \\\n",
        "only due to arc inconsistencies with Yj, don't need to check Yj. 3. Removing a value Xi can only make Yj arc-inconsistent with \\\n",
        "respect to Xi itself. Thus, only need to check that (j,i) is stil arc-consistent. \n",
        "\n",
        "AC-3 Complexity Anaylisis: total number of arcs = O(n^2). each arc can be inserted into the queue d times. Worse case complexity: O(n^2 x d^3). \\\n",
        "For planar consistent graphs, number of arcs is linear in N and time complexity is only O(n x d^3). Processes binary constraints\n",
        "\n",
        "Crucial principle: if a value is removed from a node Xi, then the values on all of Xi's neighbors must be reexamined. \n",
        "\n",
        "Constraint satisfaction problems cannot be solved in polynomial time on certain domains according to current theory.\n",
        "\n",
        "Assembly manufacturing problem good to use CPS strategies\n",
        "\n",
        "If problem has costs, the CSP will simply return a valid solution that satisfies the constraints and is arbitrary-cost. Won't mim/max. \n",
        "\n",
        "AC-3 can solve all sudoku puzzles in O(n^n+1) time\n",
        "\n",
        "CSP's generally use declarative programming\n",
        "\n",
        "To make X (tail) arc-consistent with Y (head), must check all values in X, and remove values from X that are present in Y. \\\n",
        "Note: always check all values on tail, but can stop checking head values once you see a value that allows the value you're checking \\\n",
        "on the tail.\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"consistent\" : \"An assignment that does not vialoate a constraint\", \n",
        "\"complete\" : \"every variable assigned a value, and all consistent\",\n",
        "\"precedence constraint\" : \"If a task must occur before another task\",\n",
        "\"unary constrain\" : \"restricts value of a single variable\",\n",
        "\"binary constraint\" : \"relates 2 variables, like two countries that can't have same color\",\n",
        "\"Binary CPS\" : \"only unary and binary constraints\",\n",
        "\"global constraint\" : \"arbitrary number of variables, such as all-diff in Sudoku\",\n",
        "\"preference constraints\" : \"indicate which solution is preferred, called constrained optimization problem\",\n",
        "\"Constraint propogation\" : \"using constraints to reduce number of legal values\",\n",
        "\"Node consistency\" : \"all values in single variables domain satisfy the unary constraints (1-consistent)\",\n",
        "\"Arc consistency\" : \"Every value in single variables domain satisfies the binary constraints (2-consistent)\",\n",
        "\"Path consistency\" : \"tightens binary constraints by looking at triples of variables and ensuring binary constraints hold (3-consistent)\",\n",
        "\"K-consistency\" : \"k-consistent if for any set of k-1 variables, and consistent values assigned, then k can be assigned\",\n",
        "\"strongly k-consistent\" : \"k-consistent and also (k-1) consistent, (k-2) consistent... etc.\",\n",
        "\"resource constraint\" : \"higher-order constraint, like at-most\",\n",
        "\"minimum remaining values heuristic\" : \"choose variable with fewest legal values\",\n",
        "\"degree heuristic\" : \"select variable involved in largest number of constraints with other variables. Less strong than minimum, but good as tie\",\n",
        "\"least-constraining-value heuristic\" : \"done once variable selected already. Choose variable that rules out fewest choices for neighboring values\",\n",
        "\"Forward checking\" : \"when a variable X is assigned, for all Y's connected to X, deleted non-consistent values for those Y's\",\n",
        "\"MAC\" : \"progogates forward checking through entire graph, rather than stopping after one variable\",\n",
        "\"conflict-directed backjumping\" : \"depper notion of conflict backjumping. set of preceding variables and subsequent that have no solution\",\n",
        "\"Cycle cutset\" : \"Choose subset of CSP's variables so that constraint graph becomes tree after S removed. S is the cycle cutset\",\n",
        "\"inference\" : \"using problem constraints to reduce the number of legal values on a variable\"\n",
        "\n",
        "\n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 143,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1605
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "fe7ea82a-40f7-47e1-db90-231337f57bbf"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " \n",
              "A constraint satisfaction problem is one in which a factored representation is used for each state, which is a set of variables, each of which has a value. If every variable has a value that satisfies the constraints, then it is considered solved. Map coloring is an example problem that is a CSP. Job-shop scheduling can be another CSP problem using precedence constraints. A discrete domain can be infinite (integers, strings). Common real world CSP problems have continous domains, generally considered linear programming problems. Several types of constraints, such as unary, binary, global, and preference. Can represent restraints using constraint hypergraph. \n",
              " \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " \n",
              "CSP can either generate a new variable assignment, or perform constraint propagation. Local consistency shows that enforcing constraints on one part of the graph will lead to narrowing options further along in the graph. Types of consistency are node consistency, arc consistency, path consistency, K-consistency, and global constraints (all defined below). CSP is NP-complete in general, leading to exponential time to establish n-consistency, and also exponential space with regards to n. Sudoku example given.\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " \n",
              "Commutativity allows to reduce search space by realizing that order of application doesn't matter, making number of leaves d^n as hoped. Use minimum remainging heuristic (or degree heuristic if tie) to choose a varialbe, and then use least-constraining-value on that variable to choose which value to select (i.e., the one that leaves neighbors with the most choices). Forward checking says that when a variable X is assigned, for all Y's connected to X, deleted non-consistent values for those Y's. MAC (Maintaining Arc Consistency) algorithm is similar, it just progogates through entire graph, rather than stopping after one variable. Chronological backtracking allows most recent decision point to be revisited. Backjumping will backtrack to the most recent assignment in the conflict set. Constraint learning can be used to achieve much better efficiency on complex CSP problems by not running into the same problems (called no-good problems) again.\n",
              " \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " \n",
              "Local-search algorithms are effective for CSP. Min-conflicts heuristic to select value that has least conflicts. Constraint weighting is another way to do this, such as difficult constraints being assigned higher weights over time, allowing for faster solutions on future algorithm runs. \n",
              " \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " \n",
              "Independence found by finding connected components of the constraint graph for a CSP problem. Directional arc consistency means that under ording of variables, X1, X2... Xn, if and only if each Xi arc-consistent with each Xj (j > i). Solve problems like these using topoligical sort. Algorithm using cycle cutsets (Defined below) can be used to find an answer to CSP's. Can also do tree decomposition in order to reduce a constraint graph to a tree. 3 conditions: every variable must appear in at least one of tree nodes, if 2 variables conntected, must appear connected in at least one tree node, and if variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. NOTE: CSP's with constraint graphs of bounded tree width are solvable in polynomial time. Noted at end of chapter that you can use value symmetry such as on map problem by imposing arbitrary order (NT < SA < WA alphabetically), so that only one of d! solutions is possible (simimlar to idea covered earlier in chapter). \n",
              " \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              "\n",
              "Advantage to CSP's is they can be solved with general purpose algorithms. Also CPS knows which variables violate constraint, and can thus focus the search. Also CPS's automatically prune off all branches that violate constraints. \n",
              "\n",
              "Which variable to assign next? 1. Most constrained (if tied, most constraining). \n",
              "\n",
              "What order should variables values be tried? Least constraining value\n",
              "\n",
              "Detect inevitable failure by forward checking\n",
              "\n",
              "If d values, checking arc(i,j) takes O(d^2) time\n",
              "\n",
              "AC-3: at each iteration, 1. only need to examine Xi where at lesat one neighbor of Xi has lost a value. 2. if Xi loses a value only due to arc inconsistencies with Yj, don't need to check Yj. 3. Removing a value Xi can only make Yj arc-inconsistent with respect to Xi itself. Thus, only need to check that (j,i) is stil arc-consistent. \n",
              "\n",
              "AC-3 Complexity Anaylisis: total number of arcs = O(n^2). each arc can be inserted into the queue d times. Worse case complexity: O(n^2 x d^3). For planar consistent graphs, number of arcs is linear in N and time complexity is only O(n x d^3). Processes binary constraints\n",
              "\n",
              "Crucial principle: if a value is removed from a node Xi, then the values on all of Xi's neighbors must be reexamined. \n",
              "\n",
              "Constraint satisfaction problems cannot be solved in polynomial time on certain domains according to current theory.\n",
              "\n",
              "Assembly manufacturing problem good to use CPS strategies\n",
              "\n",
              "If problem has costs, the CSP will simply return a valid solution that satisfies the constraints and is arbitrary-cost. Won't mim/max. \n",
              "\n",
              "AC-3 can solve all sudoku puzzles in O(n^n+1) time\n",
              "\n",
              "CSP's generally use declarative programming\n",
              "\n",
              "To make X (tail) arc-consistent with Y (head), must check all values in X, and remove values from X that are present in Y. Note: always check all values on tail, but can stop checking head values once you see a value that allows the value you're checking on the tail.\n",
              " \n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Consistent** - An assignment that does not vialoate a constraint\n",
              "* **Complete** - every variable assigned a value, and all consistent\n",
              "* **Precedence constraint** - If a task must occur before another task\n",
              "* **Unary constrain** - restricts value of a single variable\n",
              "* **Binary constraint** - relates 2 variables, like two countries that can't have same color\n",
              "* **Binary cps** - only unary and binary constraints\n",
              "* **Global constraint** - arbitrary number of variables, such as all-diff in Sudoku\n",
              "* **Preference constraints** - indicate which solution is preferred, called constrained optimization problem\n",
              "* **Constraint propogation** - using constraints to reduce number of legal values\n",
              "* **Node consistency** - all values in single variables domain satisfy the unary constraints (1-consistent)\n",
              "* **Arc consistency** - Every value in single variables domain satisfies the binary constraints (2-consistent)\n",
              "* **Path consistency** - tightens binary constraints by looking at triples of variables and ensuring binary constraints hold (3-consistent)\n",
              "* **K-consistency** - k-consistent if for any set of k-1 variables, and consistent values assigned, then k can be assigned\n",
              "* **Strongly k-consistent** - k-consistent and also (k-1) consistent, (k-2) consistent... etc.\n",
              "* **Resource constraint** - higher-order constraint, like at-most\n",
              "* **Minimum remaining values heuristic** - choose variable with fewest legal values\n",
              "* **Degree heuristic** - select variable involved in largest number of constraints with other variables. Less strong than minimum, but good as tie\n",
              "* **Least-constraining-value heuristic** - done once variable selected already. Choose variable that rules out fewest choices for neighboring values\n",
              "* **Forward checking** - when a variable X is assigned, for all Y's connected to X, deleted non-consistent values for those Y's\n",
              "* **Mac** - progogates forward checking through entire graph, rather than stopping after one variable\n",
              "* **Conflict-directed backjumping** - depper notion of conflict backjumping. set of preceding variables and subsequent that have no solution\n",
              "* **Cycle cutset** - Choose subset of CSP's variables so that constraint graph becomes tree after S removed. S is the cycle cutset\n",
              "* **Inference** - using problem constraints to reduce the number of legal values on a variable\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 144,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" \n",
        "Knowledge-based agent uses a knowledge base (set of sentences) that reflect the world. Can use inferences to extend knowledge base. \\\n",
        "Declarative language used to tell agent what it needs to know in order to perform its tasks. \n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "Wumpus world, agent has 5 sensors [stench, breeze, glitter, bump, scream]. For an agent in an environment, main challenge is its initial \\\n",
        "ignorance. Overcome with logical reasoning. Fundamental property, conclusion is guarenteed correct if available information is correct. \\\n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "knowledge base of sentences that follow a syntax. semantics (meaning) of sentences define the truth of each sentence for each world.  \\\n",
        "If sentence 'a' is true in model 'm', then 'm' satisfies 'a', also 'm' is a model of 'a'. m(a) is the set of all models 'a'. \n",
        "\n",
        "For entailment, alpha entails Beta iff in every model in which alpha is true, Beta is also true. \n",
        "\n",
        "KB |-i alpha is written in English as 'alpha is derived from KB by i' or 'i derives alpha from KB'. Desirable to have a sound/truth perserving \\\n",
        "inference algorithm, as well as completeness.\n",
        "\n",
        "If KB is true in real world, then any sentence derived from KB by a sound inference procedure is also tru ein the real world. If KB not true \\\n",
        "in real world, still room for some optimism by using technique of learning\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "Semantics for propositional logic must specify how to compute the truth value of any sentence, given a model. Truth table (just as \\\n",
        "truth table in logic design, easy). Can use a truth-table enumeration algorithm to for deciding propositional entailment in an \\\n",
        "environment. If a KB and alpha contain n symbols in all, then there are 2^n models. T: O(2^n). S: O(n) cause enumeration is depth first. \\\n",
        "Propositional entailment is co-NP complete (probably no easier than NP-complete). NOTE: every known inference algorithm for propositional \\\n",
        "logic has a worst-case complexity that is exponnential in the size of the input. \n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"\n",
        "Propositional theory proving based on several definitions described below, starting with theorm proving. SAT is NP-complete. \\\n",
        "'a' is valid iff 'not-a' is unsatisfiable. 'a' is satisfiable iff 'not-a' is not valid. Result: 'a' => 'b' iff the sentece \\\n",
        "(a ^ not-b) is unsatisfiable. \n",
        "\n",
        "Finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how many there are\n",
        "\n",
        "A single inference rule, resolution, allows a complete inference algorithm when coupled with a complete search algorithm. \\\n",
        "Removal of multiple copies of literals called factoring. A resolution-based theormem prover can, for any setnences a and B in \\\n",
        "propositional logic, decide whether a |= B using resolution. Every sentence of propositional logic is logically equivalent to a conjunction \\\n",
        "of clauses. Ground resolution instrumental for completeness of resolution, defined below. \n",
        "\n",
        "Can be made into definite clauses and horn clauses for simpler processing. Inference with horn clause done through forward-chaining and \\\n",
        "backward-chaining algorithms. Forward chaining is sound, every inference basically a Modus Ponens. Forward chaining is complete, \\\n",
        "every entailed atomic sentence will be derived. Forward chaining example of data-driven resasoning - focus of attention starts with known \\\n",
        "data. Backward chaining works backwards from query. Also known as goal-directed reasoning, like Where are my keys and What shall I do now?. \\\n",
        "Often, cost of backward chaning much less tha nlinear in size of KB, cause process touches just relevant facts. \n",
        "\n",
        "NOTE: standard logical equivalences on study sheet.\n",
        " \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "If a |= B, that means 'a' is more specific, or stronger than B. B could be agent is robot. A would be agent is astromech.\n",
        "\n",
        "To get conjuctive normal form:\n",
        "\n",
        "1. Eliminate <=> by replacing a <=> B with (a => B) ^ (b => B)\n",
        "\n",
        "2. Eliminate => by replacing a => B with (not-a V B)\n",
        "\n",
        "3. Move (not) inwards (eliminate double negation, apply De Morgan's rules)\n",
        "\n",
        "4. Sentence now has nested ^ and V operators applied to literals. Apply distributivity law to distribute V over ^ wherever possible. \n",
        "\n",
        "Sentence now CNF\n",
        "\n",
        "Resolution algorithm: To show KB |= a, then show that KB ^ (not-a) is unsatisfiable by:\n",
        "\n",
        "1. convert (KB ^ not-a) into CNF\n",
        "\n",
        "2. Apply resolution rule to resulting clauses\n",
        "\n",
        "3. Resolve every pair that contains complementary literals to produce a new clause\n",
        "\n",
        "4. If new clause not present, add to set\n",
        "\n",
        "5. Continue until either 1. no new clauses can be added, and thus KB does not entail 'a', or 2. Two clauses resolve to yield empty clause \\\n",
        "in which case KDB does entail 'a'.\n",
        "\n",
        "Horn clauses closed under resolution. If apply resolution to horn clause, you get back a horn clause.\n",
        "\n",
        "Deciding entailment with horn clauses can be done in linar tmie with respect to size of KB\n",
        "\n",
        "Agent needs to tell program what it percieves at beginning of call\n",
        "\n",
        "Good properties of inference algorithm are soundness and completeness, discussed above\n",
        "\n",
        "The CNF can be exponentially longer than the simplest representatin of a logical formula\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge base\" : \"set of sentences represting assertions about the world\",\n",
        "\"axiom\" : \"when sentence is taken as a given without being derived\",\n",
        "\"inference\" : \"deriving new senteces from old ones\",\n",
        "\"knowledge level\" : \"need only specify what agent knows and its goals to determine behavour (implementation level doesn't matter\",\n",
        "\"declarative approach\" : \"tell the agent what it needs to know (not procedural, where behavour encoded directly)\",\n",
        "\"syntax\" : \"dictates the sentences are well formed.\",\n",
        "\"model\" : \"a possible world\",\n",
        "\"entailment\" : \"a sentence follows logically from another sentece. a |= B (iff in every model that 'a' true, 'B' also true.\",\n",
        "\"model checking\" : \"enumerates all possible models to check that alpha is true in al models in which KB is true.\",\n",
        "\"sounds/truth perserving\" : \"inference algorithm that derives only entailed sentences\",\n",
        "\"completeness\" : \"can derive any sentence that is entailed.\",\n",
        "\"grounding\" : \"connection between logical reasoning processes and real environment\",\n",
        "\"atomic sentences\" : \"consist of a single propositinal symbol\",\n",
        "\"complex sentences\" : \"constructed from simple sentences uses logical connectives\",\n",
        "\"theorem proving\" : \"applying rules of inference directly to the sentences in knowledge base to make proof without constructing models\",\n",
        "\"logical equivalence\" : \"two sentences a and b are equivalent if they are true in same set of models\",\n",
        "\"validity\" : \"sentence true if it is true in all models\",\n",
        "\"tautology\" : \"valid sentences are known as tautalogies - necesarily true\",\n",
        "\"deduction theorem\" : \"for any sentence a and b, a |= b iff the sentence (a => b) is valid\",\n",
        "\"satisfiability\" : \"sentence satisfiable if it is true in some model\",\n",
        "\"Modus Ponens\" : \" ((a => B),a)/B  means sentence of form a=>B and 'a' given, then B can be inferred.\",\n",
        "\"And-Elimination\" : \"(a ^ B) / a    means from a conjunction, any of the conjucts can be inferred\",\n",
        "\"monotonicity\" : \"set of entailed sentences can only increase as info added to KB\",\n",
        "\"full resolution rule\" : \"(l1v..vlk,m1v..vmn)/(l1v..vli-1vli+1v..vlkvm1v..vmj-1vmj+1v..vmn)\",\n",
        "\"Conjuctive normal form (CNF)\" : \"a sentence expressed as a conjunction of clauses (clauses with AND between. think within clause OR's\",\n",
        "\"ground resolution theorem\" : \"If a set of clauses is unsatisfiable, then resolution closure of those clauses contains empty clause\",\n",
        "\"definite clause\" : \"disjuction of literals of which EXACTLY ONE is positive. (not-L V not-breeze V B) is a definite clause\",\n",
        "\"Horn clause\" : \"Disjunction of literals of which AT MOST ONE is positive. All definite clauses are Horn clauses.\",\n",
        "\"goal clause\": \"clauses with no positive literals\"\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 145,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1873
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "d148fbf8-21a5-42bb-8f42-2a37ef9c778b"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " \n",
              "Knowledge-based agent uses a knowledge base (set of sentences) that reflect the world. Can use inferences to extend knowledge base. Declarative language used to tell agent what it needs to know in order to perform its tasks. \n",
              " \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " \n",
              "Wumpus world, agent has 5 sensors [stench, breeze, glitter, bump, scream]. For an agent in an environment, main challenge is its initial ignorance. Overcome with logical reasoning. Fundamental property, conclusion is guarenteed correct if available information is correct.  \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " \n",
              "knowledge base of sentences that follow a syntax. semantics (meaning) of sentences define the truth of each sentence for each world.  If sentence 'a' is true in model 'm', then 'm' satisfies 'a', also 'm' is a model of 'a'. m(a) is the set of all models 'a'. \n",
              "\n",
              "For entailment, alpha entails Beta iff in every model in which alpha is true, Beta is also true. \n",
              "\n",
              "KB |-i alpha is written in English as 'alpha is derived from KB by i' or 'i derives alpha from KB'. Desirable to have a sound/truth perserving inference algorithm, as well as completeness.\n",
              "\n",
              "If KB is true in real world, then any sentence derived from KB by a sound inference procedure is also tru ein the real world. If KB not true in real world, still room for some optimism by using technique of learning\n",
              " \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "\n",
              "Semantics for propositional logic must specify how to compute the truth value of any sentence, given a model. Truth table (just as truth table in logic design, easy). Can use a truth-table enumeration algorithm to for deciding propositional entailment in an environment. If a KB and alpha contain n symbols in all, then there are 2^n models. T: O(2^n). S: O(n) cause enumeration is depth first. Propositional entailment is co-NP complete (probably no easier than NP-complete). NOTE: every known inference algorithm for propositional logic has a worst-case complexity that is exponnential in the size of the input. \n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "\n",
              "Propositional theory proving based on several definitions described below, starting with theorm proving. SAT is NP-complete. 'a' is valid iff 'not-a' is unsatisfiable. 'a' is satisfiable iff 'not-a' is not valid. Result: 'a' => 'b' iff the sentece (a ^ not-b) is unsatisfiable. \n",
              "\n",
              "Finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how many there are\n",
              "\n",
              "A single inference rule, resolution, allows a complete inference algorithm when coupled with a complete search algorithm. Removal of multiple copies of literals called factoring. A resolution-based theormem prover can, for any setnences a and B in propositional logic, decide whether a |= B using resolution. Every sentence of propositional logic is logically equivalent to a conjunction of clauses. Ground resolution instrumental for completeness of resolution, defined below. \n",
              "\n",
              "Can be made into definite clauses and horn clauses for simpler processing. Inference with horn clause done through forward-chaining and backward-chaining algorithms. Forward chaining is sound, every inference basically a Modus Ponens. Forward chaining is complete, every entailed atomic sentence will be derived. Forward chaining example of data-driven resasoning - focus of attention starts with known data. Backward chaining works backwards from query. Also known as goal-directed reasoning, like Where are my keys and What shall I do now?. Often, cost of backward chaning much less tha nlinear in size of KB, cause process touches just relevant facts. \n",
              "\n",
              "NOTE: standard logical equivalences on study sheet.\n",
              " \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              "\n",
              "If a |= B, that means 'a' is more specific, or stronger than B. B could be agent is robot. A would be agent is astromech.\n",
              "\n",
              "To get conjuctive normal form:\n",
              "\n",
              "1. Eliminate <=> by replacing a <=> B with (a => B) ^ (b => B)\n",
              "\n",
              "2. Eliminate => by replacing a => B with (not-a V B)\n",
              "\n",
              "3. Move (not) inwards (eliminate double negation, apply De Morgan's rules)\n",
              "\n",
              "4. Sentence now has nested ^ and V operators applied to literals. Apply distributivity law to distribute V over ^ wherever possible. \n",
              "\n",
              "Sentence now CNF\n",
              "\n",
              "Resolution algorithm: To show KB |= a, then show that KB ^ (not-a) is unsatisfiable by:\n",
              "\n",
              "1. convert (KB ^ not-a) into CNF\n",
              "\n",
              "2. Apply resolution rule to resulting clauses\n",
              "\n",
              "3. Resolve every pair that contains complementary literals to produce a new clause\n",
              "\n",
              "4. If new clause not present, add to set\n",
              "\n",
              "5. Continue until either 1. no new clauses can be added, and thus KB does not entail 'a', or 2. Two clauses resolve to yield empty clause in which case KDB does entail 'a'.\n",
              "\n",
              "Horn clauses closed under resolution. If apply resolution to horn clause, you get back a horn clause.\n",
              "\n",
              "Deciding entailment with horn clauses can be done in linar tmie with respect to size of KB\n",
              "\n",
              "Agent needs to tell program what it percieves at beginning of call\n",
              "\n",
              "Good properties of inference algorithm are soundness and completeness, discussed above\n",
              "\n",
              "The CNF can be exponentially longer than the simplest representatin of a logical formula\n",
              "\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Knowledge base** - set of sentences represting assertions about the world\n",
              "* **Axiom** - when sentence is taken as a given without being derived\n",
              "* **Inference** - deriving new senteces from old ones\n",
              "* **Knowledge level** - need only specify what agent knows and its goals to determine behavour (implementation level doesn't matter\n",
              "* **Declarative approach** - tell the agent what it needs to know (not procedural, where behavour encoded directly)\n",
              "* **Syntax** - dictates the sentences are well formed.\n",
              "* **Model** - a possible world\n",
              "* **Entailment** - a sentence follows logically from another sentece. a |= B (iff in every model that 'a' true, 'B' also true.\n",
              "* **Model checking** - enumerates all possible models to check that alpha is true in al models in which KB is true.\n",
              "* **Sounds/truth perserving** - inference algorithm that derives only entailed sentences\n",
              "* **Completeness** - can derive any sentence that is entailed.\n",
              "* **Grounding** - connection between logical reasoning processes and real environment\n",
              "* **Atomic sentences** - consist of a single propositinal symbol\n",
              "* **Complex sentences** - constructed from simple sentences uses logical connectives\n",
              "* **Theorem proving** - applying rules of inference directly to the sentences in knowledge base to make proof without constructing models\n",
              "* **Logical equivalence** - two sentences a and b are equivalent if they are true in same set of models\n",
              "* **Validity** - sentence true if it is true in all models\n",
              "* **Tautology** - valid sentences are known as tautalogies - necesarily true\n",
              "* **Deduction theorem** - for any sentence a and b, a |= b iff the sentence (a => b) is valid\n",
              "* **Satisfiability** - sentence satisfiable if it is true in some model\n",
              "* **Modus ponens** -  ((a => B),a)/B  means sentence of form a=>B and 'a' given, then B can be inferred.\n",
              "* **And-elimination** - (a ^ B) / a    means from a conjunction, any of the conjucts can be inferred\n",
              "* **Monotonicity** - set of entailed sentences can only increase as info added to KB\n",
              "* **Full resolution rule** - (l1v..vlk,m1v..vmn)/(l1v..vli-1vli+1v..vlkvm1v..vmj-1vmj+1v..vmn)\n",
              "* **Conjuctive normal form (cnf)** - a sentence expressed as a conjunction of clauses (clauses with AND between. think within clause OR's\n",
              "* **Ground resolution theorem** - If a set of clauses is unsatisfiable, then resolution closure of those clauses contains empty clause\n",
              "* **Definite clause** - disjuction of literals of which EXACTLY ONE is positive. (not-L V not-breeze V B) is a definite clause\n",
              "* **Horn clause** - Disjunction of literals of which AT MOST ONE is positive. All definite clauses are Horn clauses.\n",
              "* **Goal clause** - clauses with no positive literals\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    },
    {
      "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",
      "execution_count": 146,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 10468
        },
        "id": "T3cm1WV542_a",
        "outputId": "46981120-fc03-4276-dfb5-d3a238c008d4"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              " Field of AI wants to both understand and build AI. Human vs. rational and though vs behavour combinations come into play. Turing test sums up if a computer can pass test of being a human. Total turing includes passing visual aspects as well. human-cognitive modeling approach looks at human way of thinking, introspection, psychological experimeents, brain imaging. Laws of though approach deals with Aristotle and his syllogisms to provide patterns for arguments, leading to logic. Probability allows rigorous reasing even when info is uncertain. Rational agent approach deals with allowing an agent to act rationally. Advantages over first two approaches are \\ \n",
              "more general than laws of thought and more amenable to science. Beneficial machines deals with value alignment problem , achieving agreement between our preferences and machines objectives. Want agents that are provably beneficial to humans. \n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              " Distinction between weak AI and strong AI in definitions section. Informality argument states human behavour too complicated (Hubert Dreyfus). Good-Old_Fashioned AI - technology skeptics critisized, saying can't be done with computation. Embodied cognition says brain not separate from body. Argument from disability claims a machine can never to X. Mathematical objection argues some math like Godel's incompleteness theorem can't be solved by formal systems, but argument that computers are informal is made. Turing then comes up with Turing test to see whether machines can pass behavoural test. \n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " Problem of whether AI actually thinking or just looking like thinking. Turing introduces polite convention. Chinese room experiment refutes Turing. Searl proponent of biological naturalism, where mental states are high level emergent features. Strong theme of conciousness, awareness of world, and qualia, defined in definitions. Turing believes this question is largely irrevelent. \n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              " An agent's choice of actions depends on the built-in knowledge as well as the entire percept sequence so far, but not on anything it hasn't percieved. Vacuum cleaner example to show agent and agent program Agent meant to be tool for analyzing, not an absolute characterization. Note, this section largely summarized in definitions. \n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              " AI evaluated by consequentialism, the consequences of its actions. Better to design performance measures based on what someone actually is trying to achieve in an environment, rather than how we think the agent should act. What is rational, depends on performance measure, prior knowledge, actions, and percept sequence to date. Rationality is not omniscience, as omniscience knows actual outcome of actions - impossible in reality. Information gathering and exploration used to modify future percepts. With learning, an agent can become independent of prior knowledge, allowing it to succeed in many scenarios.\n",
              "\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              " Task environment, PEAS defined in definitions section. Properties include: fully observable vs. partionally observable, single-agent vs. multi-agent, deterministic vs. nondeterministic, episodic vs. sequential, static vs. dynamic, discrete vs. continuous, known vs. unknown. All defined in definitions. Hardest case is partionally observable, multi-agent, non-deterministic, sequential, dynamic, continous, unknown. Note: known vs. unknown not a property of the environment.  \n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              " Job of AI is designing agent program to implement the agent function. Ideal to produce agent programs that cause rational behavour based off small program rather than a massive table. Simple reflex agent selects actions based on current percept. Randomized behavour can outperform non-randomized. Model-based reflex agents maintains an internal state of the world. Uses transition model. model-based agent = transition model + sensor model. Goal-based agents uses goal to decide desirable actions. Utility based agents maximize happiness, which is utility. Learning agents is reponsible for using learning element to make improvements. Components of agent programs can use atomic representation (indivisibl), or factored, which splits up state into fixed set of variables or attributes. Structured representation says that the various relationships between objects can be described explicitely. More expressive representation captures everything a less expressive one can capture, plus more. Localist repesentation is one-to-one mapping of concepts and memory locations. Distributed representation is if concept spread over many memory locations. \n",
              "\n",
              "## Module 1 Lecture Notes\n",
              " A rational agent selects an action that maximizes the expected value of its performance measure. Touchless faucets, thermostat, pet hamster can be viewed as agents. A rational agent is not guaranteed to find optimal solutions. To be rational, an agent must maximize its expected performance.\n",
              " \n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Rationality** - doing the right thing\n",
              "* **Turing test** - needs NLP, knowledge representation, automated reasoning, machine learning\n",
              "* **Value alignment problem** - values we put into machine must align with human\n",
              "* **Percept** - content an agent's sensors are percieving\n",
              "* **Weak ai** - could act as if intelligent\n",
              "* **Strong ai** - conciously thinking\n",
              "* **Embodied cognition** - Doesn't make sense to consider brain separate from human\n",
              "* **Polite convention** - turing says extends to machines\n",
              "* **Chinese room** - John Searl rejects this, citing Chinese room thought experiment\n",
              "* **Qualia** - technical term for intrinsic nature of experiences\n",
              "* **Agent** - anything that can perceive and act in an environment.\n",
              "* **Rational agent** - an agent that does the right thing\n",
              "* **Percept sequence** - complete history of everything an agent has perceived\n",
              "* **Agent function** - describes agent's behavour, maps a given percept sequence to an action\n",
              "* **Agent program** - internally, agent function implemented by agent program\n",
              "* **Information gathering** - doing actions to modify future percepts, like exploration\n",
              "* **Task environment** - PEAS Performance, environment, actuators, sensors\n",
              "* **Fully observable** - agents sensors give access to complete state of environment at all points in time\n",
              "* **Single agent** - distinct from multi, depending on whether B's behavour maximizes performanc measure whose value depends on A behavour\n",
              "* **Deterministic** - If next state completely determined by current state and agent's action\n",
              "* **Episodic** - Agent's experiences divided into atomic episodes, as opposed to sequential, where current decision affects future (chess, taxi)\n",
              "* **Static vs. dynamic** - if environment can change while deliberating, then its dynamic\n",
              "* **Discrete vs. continuous** - Chess is discrete, while taxi driving is continuous\n",
              "* **Known vs. unknown** - : State of knowledge of agent’s knowledge about the “laws of physics” of the environment\n",
              "* **Agent** - the architecture plus the program\n",
              "* **Simple reflex agent** - selects actions based on current percept, ignoring history\n",
              "* **Goal-based agent** - Needs a goal in order to choose actions that result in that goal\n",
              "* **Utility-based agent** - happy. Maximize expected utility while reaching goal\n",
              "* **Learning agents** - responsible for making improvements to the agent. Problem generator to explore actions\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              " \n",
              "All data treated as objects\n",
              "\n",
              "Strong typing – every object has a fixed type\n",
              "\n",
              "Dynamic typing – don’t have to declare type of variable. Variables come into existence when first assigned. Drawback – type errors caught at runtime\n",
              "\n",
              "**Strings**\n",
              "\n",
              "Creation – cause use single our double quotes, triple for multiline string and docstring\n",
              "\n",
              "Concatenation – special use of +\n",
              "\n",
              "Prefixing with r means raw\n",
              "\n",
              "String formatting – print(“%s can speak %d languages” %(“C3PO”, 6000))\n",
              "\n",
              "Immutable\n",
              "\n",
              "*lists are mutable though, but can use y=x[:] to create a shallow copy of any sequence\n",
              "\n",
              "**Sequence Types: Tuples, Lists, and Strings**\n",
              "\n",
              "Tuple: tu = (23, ‘abc’, 4.56, (2,3), ‘def’) *immutable ordered sequence of items, can be mixed\n",
              "\n",
              "List: li = [‘abc’, 34, 4.34, 23] *mutable ordered sequence of items of mixed types\n",
              "\n",
              "Slicing: tu[1:4] = (‘abc’, 4.56, (2,3)). [a,b) format. Can do something like [1:-1]. \n",
              "\n",
              "Select every nth item is: t[1:-1:2]\n",
              "\n",
              "Tu[:2] copy from beginning\n",
              "\n",
              "Tu[2:] copy to very end\n",
              "\n",
              "List methods: append, index, count, remove, reverse, sort (reverse and sort both in-place)\n",
              "\n",
              "String methods: words.split(“ “) -> puts the words separated by space into list\n",
              "\n",
              "s.capitalize(), s.upper(), .strip(‘ –‘)\n",
              "\n",
              "Zip: a = [1, 2, 3]; b = [‘a’, ‘b’, ‘c’, ‘d’], list(zip(a, b))\n",
              "\n",
              "[(1, ‘a’), (2, ‘b’), (3, ‘c’)]\n",
              "\n",
              "List(zip(“foo”, “bar”))  -> [(‘f’, ‘b’), (‘o’, ‘a’), (‘o’, ‘r’))\n",
              "\n",
              "**Dictionaries**\n",
              "\n",
              "Unordered and work by hasing, so keys must be immutable\n",
              "\n",
              "D = {‘user’ : ‘R2D2’, ‘pswd’: 1234}\n",
              "\n",
              "D[‘user’] -> ‘R2D2’\n",
              "\n",
              "Assigning a value to an existing key replaces its value\n",
              "\n",
              "Methods: d.keys(), d.values(), d.items()\n",
              "\n",
              "**Functions**\n",
              "\n",
              "def get_final_answer(filename):\n",
              "\n",
              "\txxx\n",
              "\n",
              "\treturn total_counter\n",
              "\n",
              "can return multiple answers, return type is tuple\n",
              "\n",
              "Function overloading (add(int, int), add(int, int, int)), etc.) not allowed\n",
              "\n",
              "Operator overloading allowed with special methods\n",
              "\n",
              "Default values -> def myFun(b, c=3, d=”hello):\n",
              "\n",
              "***non-default argument should always precede default arguments, otherwise syntax error\n",
              "\n",
              "Can call arguments out of order if you specify which argument. myFun(c=43, b=1, a=2)\n",
              "\n",
              "‘*args’ accepts a variable number of non-keyword arguments. Def(print_everything(*args)\n",
              "\n",
              "‘**kwargs’ accept a variable number of keyword arguments\n",
              "\n",
              "Python is dynamic scope, sees most current value of the variables\n",
              "\n",
              "Functions are first-class objects: can by created, destroyed, passed to function, returned as a value, and have all other rights of a variable\n",
              "\n",
              "Map() and filter() useful higher order functions\n",
              "\n",
              "**Classes and Inheritance**\n",
              "\n",
              "class Student:\n",
              "\n",
              "\tuniv = “upenn” # class attribute\n",
              "\n",
              "\tdef __init__(self, name, dept)\n",
              "\n",
              "\t\tself.student_name= name\n",
              "\t\t…\n",
              "\n",
              "Subclass: can extend the definition of another class, but name of superclass in parentheses after subclasses name on first line of the definition\n",
              "-\tTo redefine a method of parent class, include new definition using same name\n",
              "\n",
              "**List comprehension**\n",
              "\n",
              "Squares = [x*x for x in nums]\n",
              "\n",
              "Filtered: [elem * 2 for elem in li if elem > 4]\n",
              "\n",
              "Extra for: acts just as a nested for loop\n",
              "\n",
              "Dictionary set comprehension: d = {k: v for k, v in lst1}\n",
              "\n",
              "Set comprehension: s = {x for x in lst2}\n",
              "\n",
              "**Iterators (they use memory efficiently)**\n",
              "\n",
              "K = [1,2,3]\n",
              "\n",
              "i = iter(k)\n",
              "\n",
              "next(i) -> 1\n",
              "\n",
              "next(i) -> 2\n",
              "\n",
              "**Generators**\n",
              "\n",
              "Each time __next__ is called for generator, method runs until it encounters yield, then stop and return the value that was yielded\n",
              "\n",
              "Benefits: less code, maintains local state automatically, values computed one at a time, avoid storing whole sequence in memory, good for aggregating, one pass, crucial for infinite sequences, bad if need to inspect individual values\n",
              "\n",
              "\n",
              "**Extra**\n",
              "\n",
              "Hash function defined as any function that can be used to map data of arbitrary size to a fixed size\n",
              "\n",
              "A python tuple can be created without using parentheses (returning multiple values)\n",
              " \n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Mutability** - Can't change inplace once created is immutable\n",
              "* **Strong typing** - Every object has fixed type\n",
              "* **Dynamic typing** - don't have to declary type of variable. come into existence when first assigned. Drawback: type errors caught at runtime\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              " Goal formulation -> problem formulation -> search -> execution. Abstraction is valid if can elaborate any abstract solution into a solution in more detailed world. Solution to any problem is a fixed sequence of actions. In partially observable solution would be different branching patterns. Optimal solution has the lowerst path cost. Process of removing detail is abstraction. Abstraction valid if we can elaborate any abstract solution into a solution in more detailed environment. \n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              " Grid world and sokoban (8-tile) example problems. Real world route finding problem between cities. Touring problem is when a set of places must be visited. VLSI layout problem requires positioning of millions of components on chips, split into cell layout and channel routing. Robot navigation is generalization of route finding problem earlier. Automatic assembly sequencing of complex objects by robot has been standard practice since 1970's.  \n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              " Search algorithms take a search problem as input and return solution or failure. Best-first search most general algorithm where you expand node with minimum value of an evaluation function. Data structures: tree with state, parent, action, path-cost. Priority, LIFO, FIFO queues all used. A cycle is a special case of a redundant path. Measuring performance is based on completeness, cost optimality,  time complexity, and space complexity. To be complete, a search algorithm should be systematic.  \n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              " \n",
              "**Breadth-first search** – complete even on infinite spaces. Cost-optimal. Memory requirements bigger problem than execution time, but time still important. COMPLETE, COST-OPTIMAL, T: O(b^d), S: O(b^d)\n",
              "\n",
              "**Dijkstra’s algorithm/uniform cost search** – Spreads out in waves of uniform cost function (implemented like best-first search with path-cost as evaluation function. Complete and cost-optimal. b^(d+1) space and time complexity when all actions costs equal. COMPLETE, COST-OPTIMAL, T: O(b^(1 + floor(C*/epsilon))), S: O(b^(1 + floor(C*/epsilon)))\n",
              "\n",
              "**Depth-first search** – always expands deepest node on the frontier. Is NOT cost-optimal, is incomplete in infinite state spaces. Smaller need for memory than breadth-first or uniform-cost.  O(bm) space. Backtracking version uses even less memory O(m). NOT COMPLETE, NOT COST-OPTIMAL, T: O(b^m), S: O(bm)\n",
              "\n",
              "**Depth-limited** – version of DFS where depth limit l is supplied. T: O(b^l), S: O(bl). Incomplete if poor choice of l. NOT COMPLETE, NOT COST-OPTIMAL, T: O(b^l), S: O(bl)\n",
              "\n",
              "**Iterative deepening search** – pick good value of l by trying all values first, 0, 1, 2… S: O(bd) when solution, or O(bm) on finite with no solution. Cost-optimal for problems where actions have the same cost, complete finite state spaces. T: O(b^d) when solution, O(b^m) when none. COMPLETE, COST-OPTIMAL, T: O(b^d), S: O(bd)\n",
              "\n",
              "**Bi-directional search** – searches forward from initial state and backward from goal state. COMPLETE, COST-OPTIMAL, <- (if both directions BFS or uniform-cost), T: O(b^(d/2)), S: O(b^(d/2))\n",
              " \n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "Use DFS if: space restricted / there are many possible solutions with long paths and wrong paths are usually terminated quickly / search can be fine-tuned quickly\n",
              "\n",
              "Use BFS if: Possible infinite paths, some solutions have short paths, can quickly discard unlikely paths\n",
              "\n",
              "Graph search checks if a node has been visited before adding it to the search queue\n",
              "\n",
              "If a state is reached via multiple paths, tree search will create two separate nodes corresponding to each path (turns a linear problem into an exponential one potentially)\n",
              "\n",
              "BFS optimal for problems with unit costs all same / BFS complete for infinite-depth search space\n",
              " \n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **Open-loop** - agent ignores percepts once solution found and just goes along path\n",
              "* **Closed-loop** - agent safer monitering percepts even whle traveling solution path\n",
              "* **Search problem** - set of states, initial state, goal state(s), actions available, transition model, action cost function\n",
              "* **Best-first search** - choose a node with minimum value of evaluation function to expand\n",
              "* **Complete** - guarenteed to find a solution when there is one and correctly report failure if not\n",
              "* **D** - depth or number of actions in optimal solution\n",
              "* **M** - maximum number of actions in any path\n",
              "* **B** - branching factor or number of successors\n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              " Greedy best-first search – expand first node with the lowest h(n) value. f(n) = h(n). Complete in finite spaces, but not infinite. O(|V|) in worst case for both T and S.  Can be reduced to O(bm) with a good heuristic function on certain problems.  In contrast, A\\* search – f(n) = g(n) + h(n), where g(n) is path cost from initial state to node n, and h(n) is the estimated cost of the shortest path from n to the goal state. A\\* is complete (if state space finite). A\\* being optimal depends on the heuristic. Ann admissible heuristic is one that never overestimates the cost to reach a goal (optimistic).  If h(n) is admissible, then A* is cost-optimal. if h(n) not admissible, A* may or may not be cost-optimal. Consistency is a stronger property. Consistent if, for every node n and every successor n’ of n generated by an action a, we have: h(n) <= c(n, a, n’) + h(n’). Every consistent heuristic is admissible (but not vice versa). \n",
              "\n",
              "Can use search contours to visualize expansion. Surely expanded nodes is when A* expands all nodes that can be reached from initial state on a path that has f(n) < C\\*. A\\* might then expand some nodes right on the goal contour (f(n) = C\\*). A\\* expands no nodes with f(n) > C\\* (C\\* is cost of optimal solution path). A\\* is complete, cost-optimal and optimally efficient. Only downside is the exponential nature of it. Satisficing solutions is similar to A\\*, but accepting sub-optimal solutions by either using inadmissible heuristic or weighted A\\*(which is a somewhat greedy A-star). Can also use bounded suboptimal search, bounded-cost search, and unbounded-cost search. Memory bounded search problems can be described here. Beam search limits the size of the frontier. Iterative deepening A\\* search . Recursive best-first search (RBFS), attempts to mimic standard best-first search but using only linear space using backed up values, somewhat more efficient than IDA\\*, but excessive node generation still. MA\\* and SMA\\* determine how much memory we have available and are allowed to use all of it, SMA complete for any reachable solution, optimal if optimal solution is reachable. Memory limitations can still make a problem intractable from the point of view of computation time (thrashing). \n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              " \n",
              "**Branching factor** b\\* example is if A* finds a solution at depth = 5 using 52 nodes, then effective branching factor is 1.92. N + 1 = 1 + b\\* + (b\\*)^2 + … + (b\\*)^d. The **effective depth** characterizes effect of A\\* pruning as reducing the effective depth by a constant kh compared to the true depth. Thus making total search cost O(bd – kh) compared to O(bd) for a uniformed search. h2 dominates h1. Therefore, h2 always better. for any node, h2(n) >= h1(n). Domination translates directly to efficiency. A relaxed problem is a problem with few restrictions on the actions. Used to come up with a better heuristic. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. Admissible heuristics can also be generated from subproblems using pattern databases (store exact solutions for every possible subproblem of instance). Can generate heuristics with landmarks – use precomputation using a few chosen landmark points. Uses differential heuristic, goal on optimal path from n to the landmark to be useful. Can get better heuristic by learning to search better using metalevel state space, goal of learning is to minimize the total cost of problem solving, trading off computational expense and path cost. Can get better heuristic simply by using experience, like solving lots of 8-puzzles.\n",
              " \n",
              "\n",
              "## Module 4 Lecture Notes\n",
              " \n",
              "Priority queue used by A\\*, Greedy Best-first search, uniform cost search\n",
              "\n",
              "Quiz implies that “graph-search of A\\* is optimal as long as the heuristic is admissible” is FALSE\n",
              "\n",
              "H2(n) >= h1(n), then h2 is more accurate than h1\n",
              "\n",
              "A\\* uses heuristic to prune search space so that the use of space is effectively O(bd).\n",
              "\n",
              "If h1(d) < h2(d) for all d, then A\\* search using h2 will not expand more nodes than A\\* search using h1\n",
              "\n",
              "A well-designed heuristic will have a branching factor close to 1. (True, smaller is better/more efficient)\n",
              " \n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Informed search** - uses domain-specific hints in form of heuristic function to find solution more efficiently\n",
              "* **Greedy best-first search** - expand first node with the lowest h(n) value. f(n) = h(n). Complete in finite spaces, but not infinite.\n",
              "* **Admissibility** - an admissible heuristic is one that never overestimates the cost to reach a goal (optimistic).\n",
              "* **Consistency** - Consistent if we have: h(n) <= c(n, a, n’) + h(n’)\n",
              "* **Satisficing solution** - A\\*, but accepting sub-optimal solutions by either using inadmissible heuristic or weighted A\\*\n",
              "* **Effective depth** - Characterizes effect of A\\* pruning as reducing the effective depth by a constant kh  compared to the true depth.\n",
              "* **Relaxed problem** - a problem with few restrictions on the actions. Used to come up with a better heuristic. \n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              " When large number of agents,consider considering in aggregate as an economy. Use pruning to make search space more efficient, and heuristic evaluatin function to estimate who is winning. Two-player zero sum games described as deterministic, two-player, turn-taking, perfect information, zero-sum games Game defined by: starting state, to-move(s), actions(s), result(s,a), is-terminal(s), utility(s, p). Game tree is a search tree that will follow paths till terminal state is reached.\n",
              " \n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              " \n",
              "minimax search accounts for games where both players play optimally. It's a recursive algorithm down to leaves and then backs up minimax values through tree while unwinding. Technically performs complete depth-first search. b = legal moves, m = max depth of the tree. T: O(b^m), S: O(bm), or O(m) if actions generated one at a time. Multiplayer games involve alliances. \n",
              "\n",
              "Alpha-beta pruning allows for pruning without examining every state. alpha/beta definition below. Effectiveness dependent on the order in which the leaves are examined. If done perfectly, alpha-beta examines O(b^(m/2)), compared to O(b^m) for minimax. Makes it sqrt(b) branching factor instead of b. \n",
              "\n",
              "Type A and Type B strategies (defs below) popular opposite strategies. \n",
              " \n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "\n",
              "Can apply heuristic evaluation function to states to cut off search early. replace terminal test with cutoff test. Good eval function = between loss and win, fast computation, correlated with chance of winning. Works by calculating various features of state. Weighted linear function like in chess, where piece number, type, position computed based on utility. Eval function should only be applied to quiescent position (def below). Can mitigate horizen effect using singular extensions (def below)\n",
              "\n",
              "Forward pruning saves computation time, but risks an error. Beam search decent approach to this. Another possibility is the late move reduction strategy, which assumes the move ordering has been done well, and therefore much later moves in the list are less likely to be good. Games like chess can use a policy to map certain moves, such as at the beginning or the end of the game, to make computation much less complex.\n",
              " \n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "Stochastic games include unpredictability. Use expected value instead. For minmax type games, called expectiminimax value. Chance games must use evaluation function that returns a positive linear transformation of the probability of winning. Expectimax will take O(b^m*n^m) time cause it must consider all dice rolls. \n",
              " \n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              " \n",
              "agents preference captured by utility function. Try to maximize the expected utility. If an agent acts to maximize this then agent will achieve highest possible performance when averaged. Constraints on rational preferences are: orderability, transitivity, continuity, substitutability, monotonicity, and decomposability. In deterministic environments, agent only needs preference on states, this is the value function (ordinal utility function). \n",
              " \n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "\n",
              "Constraints on rational preferences are: orderability, transitivity, continuity, substitutability, monotonicity, and decomposability. In deterministic environments, agent only needs preference on states, this is the value function (ordinal utility function). \n",
              " \n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              " Utility function maps from lotteries to real numbers. Preference elicitation gives choices to humans and then pins down utility function from that.  S-curve shape when agents are risk-averse. Agent with linear curve is risk neutral. Real outcome from an agent will be significantly worse, even when unbiased, due to optimizers curse. \n",
              "\n",
              "Decision theory is normative, describes how agent should act. Descricptive would describe how an agent actually acts. certainty effect, framing effect, and anchoring effect all describe reasons why humans may act irrationally. \n",
              "\n",
              "\n",
              "## Module 5 Lecture Notes\n",
              " \n",
              "Zero-sum assumption lets us use one function to describe goodness of both players. f(n) > = if MAX in winning position n. f(n) < 0 if MIN is winning in position n. \n",
              "\n",
              "Random variable represents an event whose outcome is unknown. Probability distribution is assignment of weights to outcomes.\n",
              "\n",
              "Objectivist / Frequentists average over repeated experiments\n",
              "\n",
              "Subjectivists / Bayseian answer has degrees of belief about unobserved variables based on other condtions / states\n",
              "\n",
              "If opponent is using a minmax result 80% of the time and moving randomly otherwise, use Expecimax tree search\n",
              "\n",
              "As depth increases in probabilistic search trees, usefulness of search is diminished, meaning limiting depth is less damaging, but pruning is trickier. \n",
              "\n",
              "MAX can't just search for his solution at start of game because: best possible move depends on min's decision\n",
              "\n",
              "Evaluation function returns estimate of the expected utility of game from a given position\n",
              "\n",
              "Minimax algorithm with pruning will take about same time as without if search space is small\n",
              "\n",
              "alpha-beta limitation: assumes leaf evaluations randomly distributed\n",
              "\n",
              "If outcome deterministic, minimax and expectiminimax will give same solutions\n",
              "\n",
              "\n",
              "\n",
              " \n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Pruning** - ignoring portions of the search tree\n",
              "* **Evaluation function** - heuristic to estimate who is winning based on features or averageing simulations\n",
              "* **Terminal test** - true when game is over and false otherwise\n",
              "* **Game tree** - search tree that follows every sequence until terminal state\n",
              "* **Ply** - one move by one player, therefore one level deeper in game tree\n",
              "* **Minimax search** - full DFS. T: O(b^m), S: O(bm), or O(m) if actions generated one at a time\n",
              "* **Alpha** - highest-value choice for MAX so far at any choice point along the path (at least)\n",
              "* **Beta** - lowest-value choice for MAX so far at any choice point along the path. (at most)\n",
              "* **Killer moves** - best moves, tried first - killer move heuristic\n",
              "* **Transposition table** - catches repreated sequences\n",
              "* **Type a strategy** - considers all moves to certain depth, then heuristic eval to get utility of states at that depth\n",
              "* **Type b strategy** - ignores moves that look bad, follows promising paths far as possible\n",
              "* **Quiescent** - position where no pending move would wildly swing evaluation\n",
              "* **Horizon effect** - when program facing enemy move that would end game, but it takes delaying moves\n",
              "* **Singular extension** - moves that are way better than all other moves\n",
              "* **Forward pruning** - prunes moves that seem poor, but could be good\n",
              "* **Beam search** - consider beam of 'n' best moves rather than all possible\n",
              "* **Stochastic game** - game with unpredictable elements\n",
              "* **Expected value** - average over all possible outcomes of chance nodes\n",
              "* **Utility function** - assigns a single number to express desirability of the state\n",
              "* **Principle of maximum expected utility** - ration agent should maximize expected utility\n",
              "* **Lottery** - set of outcomes for each action, each action like a ticket\n",
              "* **Micromort** - one in a million chance of death, used in medical community\n",
              "* **Certainty effect** - people are attracted to certain gains\n",
              "* **Framing effect** - exact wording can have influence on decision\n",
              "* **Anchoring effect** - 200 dollar wine makes 55 dollar wine seem cheap!\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              " \n",
              "A constraint satisfaction problem is one in which a factored representation is used for each state, which is a set of variables, each of which has a value. If every variable has a value that satisfies the constraints, then it is considered solved. Map coloring is an example problem that is a CSP. Job-shop scheduling can be another CSP problem using precedence constraints. A discrete domain can be infinite (integers, strings). Common real world CSP problems have continous domains, generally considered linear programming problems. Several types of constraints, such as unary, binary, global, and preference. Can represent restraints using constraint hypergraph. \n",
              " \n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              " \n",
              "CSP can either generate a new variable assignment, or perform constraint propagation. Local consistency shows that enforcing constraints on one part of the graph will lead to narrowing options further along in the graph. Types of consistency are node consistency, arc consistency, path consistency, K-consistency, and global constraints (all defined below). CSP is NP-complete in general, leading to exponential time to establish n-consistency, and also exponential space with regards to n. Sudoku example given.\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              " \n",
              "Commutativity allows to reduce search space by realizing that order of application doesn't matter, making number of leaves d^n as hoped. Use minimum remainging heuristic (or degree heuristic if tie) to choose a varialbe, and then use least-constraining-value on that variable to choose which value to select (i.e., the one that leaves neighbors with the most choices). Forward checking says that when a variable X is assigned, for all Y's connected to X, deleted non-consistent values for those Y's. MAC (Maintaining Arc Consistency) algorithm is similar, it just progogates through entire graph, rather than stopping after one variable. Chronological backtracking allows most recent decision point to be revisited. Backjumping will backtrack to the most recent assignment in the conflict set. Constraint learning can be used to achieve much better efficiency on complex CSP problems by not running into the same problems (called no-good problems) again.\n",
              " \n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              " \n",
              "Local-search algorithms are effective for CSP. Min-conflicts heuristic to select value that has least conflicts. Constraint weighting is another way to do this, such as difficult constraints being assigned higher weights over time, allowing for faster solutions on future algorithm runs. \n",
              " \n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              " \n",
              "Independence found by finding connected components of the constraint graph for a CSP problem. Directional arc consistency means that under ording of variables, X1, X2... Xn, if and only if each Xi arc-consistent with each Xj (j > i). Solve problems like these using topoligical sort. Algorithm using cycle cutsets (Defined below) can be used to find an answer to CSP's. Can also do tree decomposition in order to reduce a constraint graph to a tree. 3 conditions: every variable must appear in at least one of tree nodes, if 2 variables conntected, must appear connected in at least one tree node, and if variable appears in two nodes in the tree, it must appear in every node along the path connecting those nodes. NOTE: CSP's with constraint graphs of bounded tree width are solvable in polynomial time. Noted at end of chapter that you can use value symmetry such as on map problem by imposing arbitrary order (NT < SA < WA alphabetically), so that only one of d! solutions is possible (simimlar to idea covered earlier in chapter). \n",
              " \n",
              "\n",
              "## Module 6 Lecture Notes\n",
              "\n",
              "Advantage to CSP's is they can be solved with general purpose algorithms. Also CPS knows which variables violate constraint, and can thus focus the search. Also CPS's automatically prune off all branches that violate constraints. \n",
              "\n",
              "Which variable to assign next? 1. Most constrained (if tied, most constraining). \n",
              "\n",
              "What order should variables values be tried? Least constraining value\n",
              "\n",
              "Detect inevitable failure by forward checking\n",
              "\n",
              "If d values, checking arc(i,j) takes O(d^2) time\n",
              "\n",
              "AC-3: at each iteration, 1. only need to examine Xi where at lesat one neighbor of Xi has lost a value. 2. if Xi loses a value only due to arc inconsistencies with Yj, don't need to check Yj. 3. Removing a value Xi can only make Yj arc-inconsistent with respect to Xi itself. Thus, only need to check that (j,i) is stil arc-consistent. \n",
              "\n",
              "AC-3 Complexity Anaylisis: total number of arcs = O(n^2). each arc can be inserted into the queue d times. Worse case complexity: O(n^2 x d^3). For planar consistent graphs, number of arcs is linear in N and time complexity is only O(n x d^3). Processes binary constraints\n",
              "\n",
              "Crucial principle: if a value is removed from a node Xi, then the values on all of Xi's neighbors must be reexamined. \n",
              "\n",
              "Constraint satisfaction problems cannot be solved in polynomial time on certain domains according to current theory.\n",
              "\n",
              "Assembly manufacturing problem good to use CPS strategies\n",
              "\n",
              "If problem has costs, the CSP will simply return a valid solution that satisfies the constraints and is arbitrary-cost. Won't mim/max. \n",
              "\n",
              "AC-3 can solve all sudoku puzzles in O(n^n+1) time\n",
              "\n",
              "CSP's generally use declarative programming\n",
              "\n",
              "To make X (tail) arc-consistent with Y (head), must check all values in X, and remove values from X that are present in Y. Note: always check all values on tail, but can stop checking head values once you see a value that allows the value you're checking on the tail.\n",
              " \n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Consistent** - An assignment that does not vialoate a constraint\n",
              "* **Complete** - every variable assigned a value, and all consistent\n",
              "* **Precedence constraint** - If a task must occur before another task\n",
              "* **Unary constrain** - restricts value of a single variable\n",
              "* **Binary constraint** - relates 2 variables, like two countries that can't have same color\n",
              "* **Binary cps** - only unary and binary constraints\n",
              "* **Global constraint** - arbitrary number of variables, such as all-diff in Sudoku\n",
              "* **Preference constraints** - indicate which solution is preferred, called constrained optimization problem\n",
              "* **Constraint propogation** - using constraints to reduce number of legal values\n",
              "* **Node consistency** - all values in single variables domain satisfy the unary constraints (1-consistent)\n",
              "* **Arc consistency** - Every value in single variables domain satisfies the binary constraints (2-consistent)\n",
              "* **Path consistency** - tightens binary constraints by looking at triples of variables and ensuring binary constraints hold (3-consistent)\n",
              "* **K-consistency** - k-consistent if for any set of k-1 variables, and consistent values assigned, then k can be assigned\n",
              "* **Strongly k-consistent** - k-consistent and also (k-1) consistent, (k-2) consistent... etc.\n",
              "* **Resource constraint** - higher-order constraint, like at-most\n",
              "* **Minimum remaining values heuristic** - choose variable with fewest legal values\n",
              "* **Degree heuristic** - select variable involved in largest number of constraints with other variables. Less strong than minimum, but good as tie\n",
              "* **Least-constraining-value heuristic** - done once variable selected already. Choose variable that rules out fewest choices for neighboring values\n",
              "* **Forward checking** - when a variable X is assigned, for all Y's connected to X, deleted non-consistent values for those Y's\n",
              "* **Mac** - progogates forward checking through entire graph, rather than stopping after one variable\n",
              "* **Conflict-directed backjumping** - depper notion of conflict backjumping. set of preceding variables and subsequent that have no solution\n",
              "* **Cycle cutset** - Choose subset of CSP's variables so that constraint graph becomes tree after S removed. S is the cycle cutset\n",
              "* **Inference** - using problem constraints to reduce the number of legal values on a variable\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              " \n",
              "Knowledge-based agent uses a knowledge base (set of sentences) that reflect the world. Can use inferences to extend knowledge base. Declarative language used to tell agent what it needs to know in order to perform its tasks. \n",
              " \n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              " \n",
              "Wumpus world, agent has 5 sensors [stench, breeze, glitter, bump, scream]. For an agent in an environment, main challenge is its initial ignorance. Overcome with logical reasoning. Fundamental property, conclusion is guarenteed correct if available information is correct.  \n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              " \n",
              "knowledge base of sentences that follow a syntax. semantics (meaning) of sentences define the truth of each sentence for each world.  If sentence 'a' is true in model 'm', then 'm' satisfies 'a', also 'm' is a model of 'a'. m(a) is the set of all models 'a'. \n",
              "\n",
              "For entailment, alpha entails Beta iff in every model in which alpha is true, Beta is also true. \n",
              "\n",
              "KB |-i alpha is written in English as 'alpha is derived from KB by i' or 'i derives alpha from KB'. Desirable to have a sound/truth perserving inference algorithm, as well as completeness.\n",
              "\n",
              "If KB is true in real world, then any sentence derived from KB by a sound inference procedure is also tru ein the real world. If KB not true in real world, still room for some optimism by using technique of learning\n",
              " \n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "\n",
              "Semantics for propositional logic must specify how to compute the truth value of any sentence, given a model. Truth table (just as truth table in logic design, easy). Can use a truth-table enumeration algorithm to for deciding propositional entailment in an environment. If a KB and alpha contain n symbols in all, then there are 2^n models. T: O(2^n). S: O(n) cause enumeration is depth first. Propositional entailment is co-NP complete (probably no easier than NP-complete). NOTE: every known inference algorithm for propositional logic has a worst-case complexity that is exponnential in the size of the input. \n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "\n",
              "Propositional theory proving based on several definitions described below, starting with theorm proving. SAT is NP-complete. 'a' is valid iff 'not-a' is unsatisfiable. 'a' is satisfiable iff 'not-a' is not valid. Result: 'a' => 'b' iff the sentece (a ^ not-b) is unsatisfiable. \n",
              "\n",
              "Finding a proof can be more efficient because the proof can ignore irrelevant propositions, no matter how many there are\n",
              "\n",
              "A single inference rule, resolution, allows a complete inference algorithm when coupled with a complete search algorithm. Removal of multiple copies of literals called factoring. A resolution-based theormem prover can, for any setnences a and B in propositional logic, decide whether a |= B using resolution. Every sentence of propositional logic is logically equivalent to a conjunction of clauses. Ground resolution instrumental for completeness of resolution, defined below. \n",
              "\n",
              "Can be made into definite clauses and horn clauses for simpler processing. Inference with horn clause done through forward-chaining and backward-chaining algorithms. Forward chaining is sound, every inference basically a Modus Ponens. Forward chaining is complete, every entailed atomic sentence will be derived. Forward chaining example of data-driven resasoning - focus of attention starts with known data. Backward chaining works backwards from query. Also known as goal-directed reasoning, like Where are my keys and What shall I do now?. Often, cost of backward chaning much less tha nlinear in size of KB, cause process touches just relevant facts. \n",
              "\n",
              "NOTE: standard logical equivalences on study sheet.\n",
              " \n",
              "\n",
              "## Module 7 Lecture Notes\n",
              "\n",
              "If a |= B, that means 'a' is more specific, or stronger than B. B could be agent is robot. A would be agent is astromech.\n",
              "\n",
              "To get conjuctive normal form:\n",
              "\n",
              "1. Eliminate <=> by replacing a <=> B with (a => B) ^ (b => B)\n",
              "\n",
              "2. Eliminate => by replacing a => B with (not-a V B)\n",
              "\n",
              "3. Move (not) inwards (eliminate double negation, apply De Morgan's rules)\n",
              "\n",
              "4. Sentence now has nested ^ and V operators applied to literals. Apply distributivity law to distribute V over ^ wherever possible. \n",
              "\n",
              "Sentence now CNF\n",
              "\n",
              "Resolution algorithm: To show KB |= a, then show that KB ^ (not-a) is unsatisfiable by:\n",
              "\n",
              "1. convert (KB ^ not-a) into CNF\n",
              "\n",
              "2. Apply resolution rule to resulting clauses\n",
              "\n",
              "3. Resolve every pair that contains complementary literals to produce a new clause\n",
              "\n",
              "4. If new clause not present, add to set\n",
              "\n",
              "5. Continue until either 1. no new clauses can be added, and thus KB does not entail 'a', or 2. Two clauses resolve to yield empty clause in which case KDB does entail 'a'.\n",
              "\n",
              "Horn clauses closed under resolution. If apply resolution to horn clause, you get back a horn clause.\n",
              "\n",
              "Deciding entailment with horn clauses can be done in linar tmie with respect to size of KB\n",
              "\n",
              "Agent needs to tell program what it percieves at beginning of call\n",
              "\n",
              "Good properties of inference algorithm are soundness and completeness, discussed above\n",
              "\n",
              "The CNF can be exponentially longer than the simplest representatin of a logical formula\n",
              "\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Knowledge base** - set of sentences represting assertions about the world\n",
              "* **Axiom** - when sentence is taken as a given without being derived\n",
              "* **Inference** - deriving new senteces from old ones\n",
              "* **Knowledge level** - need only specify what agent knows and its goals to determine behavour (implementation level doesn't matter\n",
              "* **Declarative approach** - tell the agent what it needs to know (not procedural, where behavour encoded directly)\n",
              "* **Syntax** - dictates the sentences are well formed.\n",
              "* **Model** - a possible world\n",
              "* **Entailment** - a sentence follows logically from another sentece. a |= B (iff in every model that 'a' true, 'B' also true.\n",
              "* **Model checking** - enumerates all possible models to check that alpha is true in al models in which KB is true.\n",
              "* **Sounds/truth perserving** - inference algorithm that derives only entailed sentences\n",
              "* **Completeness** - can derive any sentence that is entailed.\n",
              "* **Grounding** - connection between logical reasoning processes and real environment\n",
              "* **Atomic sentences** - consist of a single propositinal symbol\n",
              "* **Complex sentences** - constructed from simple sentences uses logical connectives\n",
              "* **Theorem proving** - applying rules of inference directly to the sentences in knowledge base to make proof without constructing models\n",
              "* **Logical equivalence** - two sentences a and b are equivalent if they are true in same set of models\n",
              "* **Validity** - sentence true if it is true in all models\n",
              "* **Tautology** - valid sentences are known as tautalogies - necesarily true\n",
              "* **Deduction theorem** - for any sentence a and b, a |= b iff the sentence (a => b) is valid\n",
              "* **Satisfiability** - sentence satisfiable if it is true in some model\n",
              "* **Modus ponens** -  ((a => B),a)/B  means sentence of form a=>B and 'a' given, then B can be inferred.\n",
              "* **And-elimination** - (a ^ B) / a    means from a conjunction, any of the conjucts can be inferred\n",
              "* **Monotonicity** - set of entailed sentences can only increase as info added to KB\n",
              "* **Full resolution rule** - (l1v..vlk,m1v..vmn)/(l1v..vli-1vli+1v..vlkvm1v..vmj-1vmj+1v..vmn)\n",
              "* **Conjuctive normal form (cnf)** - a sentence expressed as a conjunction of clauses (clauses with AND between. think within clause OR's\n",
              "* **Ground resolution theorem** - If a set of clauses is unsatisfiable, then resolution closure of those clauses contains empty clause\n",
              "* **Definite clause** - disjuction of literals of which EXACTLY ONE is positive. (not-L V not-breeze V B) is a definite clause\n",
              "* **Horn clause** - Disjunction of literals of which AT MOST ONE is positive. All definite clauses are Horn clauses.\n",
              "* **Goal clause** - clauses with no positive literals\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "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))"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
