{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lzaavW96tcxM",
        "outputId": "d6ae6bff-bf94-4abb-896b-d6094015f222"
      },
      "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": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8DvZ57A-djo1",
        "outputId": "5153fcd5-7441-4860-c0cf-64e5ea7e9be5"
      },
      "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": null,
      "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": null,
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "* Generally want AI to do the right thing, defined as rationality\n",
        "* this intelligence can either thought processes and reasoning or actual intelligent behavior\n",
        "* computer would need natural language processing, knowledge representation, automated reasoning, and machine learning to pass the Turing test\n",
        "* Think of a human thought in terms of introspection (thinking about their thoughts), psychological experiments, and brain imaging\n",
        "* Aristotle tried to quantify what thinking was right meant, created syllogisms for patterns for arguments that gave correct conclusions when fed the right premise, initalized field of logic\n",
        "* Logicist tradition was the first forms of problems solved when a solvable problem was described in a certain way\n",
        "* probability is used to fill in the gaps of uncertainty when dealing with logical problems\n",
        "* all skills for the turing test allow rational agents to exist\n",
        "* early agents were built based on logical foundations, transitioned to be probability and machine learning to make the best decision possible in an environment\n",
        "* agents with incorrect objectives are more difficult to correct in modern design \n",
        "* not incorrect or unintelligent when it acts \"irrationally\", it is doing so to reach the objective\n",
        "* want to create agents that are provably beneficial to humans\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "* Searle defined weak AI vs. strong AI, strong AI shifted to human level AI\n",
        "* Turing claimed that human behavior was too complex to simulate with any sort of computer\n",
        "* Turing outlined all of the things computers could never do, some of which has already happened\n",
        "* Turing and Godel proved there existed questions that were not answerable by formal systems\n",
        "* thought that this proved machines were inferior to humans mentally\n",
        "* incompleteness theorem that Godel created applies more to mathematics than computers\n",
        "* only really applies to formal systems that can do arithmetic\n",
        "* Turing test tried to get a human to believe that a computer answering questions was also a human\n",
        "\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" \n",
        "* Is a machine that is intelligent actually thinking or only simulating it\n",
        "* Difficult to draw a line on consciousness, especially in computers\n",
        "* Turing believed this was a difficult but necessary problem to understand when dealing with AI\n",
        "* machines can't experience things the same way as humans but can still run code, is that really different\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "* An agents choice of action at any time can depend on its previous knowledge but nothing it hasn’t seen before\n",
        "* Agent function is a abstract definition while the agent program is the architecture implementation\n",
        "* Define agents to learn about the system, not every thing is an agent or a non agent\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "* We need to establish performance measures because the machines have no point of view\n",
        "* Want to design performance measures towards what we want to achieve in an environment, not how we think the agent should get there\n",
        "* Rationality depends on the performance measure, the prior knowledge of the system, the actions possible, and the percept sequence to that point\n",
        "* Agent chooses an action to maximize the performance measure that is expected\n",
        "* Agent has to explore an environment if they are unfamiliar with it\n",
        "* Rationality does not equal perfection\n",
        "* Want the agent to both gather information and learn from it\n",
        "* Agent lacks autonomy since it relies on the designer to tell it what to achieve\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "* Task environment defined by PEAS (performance, environment, actuators, sensors)\n",
        "* Tradeoffs often required in performance measures\n",
        "* The more restricted the environment, the design problem becomes easier\n",
        "* Virtual environments are just as complex as the real world, can have a software agent instead of a physical agent\n",
        "* Fully observable vs. partially observable - whether or not the sensors give the agent access to the entire environment at any given time\n",
        "* Also fully observable if the agent knows all things relevant to the action to be performed next\n",
        "* Unobservable environment created if the agent has no sensors to perceive the environment\n",
        "* Single agent vs. multiple agents important to keep in mind, can be competitive or cooperative\n",
        "* Deterministic vs. nondeterministic - whether or not the next state is determined entirely by the actions of the agent in the current state\n",
        "* Stochastic if it explicitly deals with probabilities versus nondeterministic \n",
        "* Episodic vs. sequential - whether or not it is divided into atomic episodes\n",
        "* Static vs. dynamic - whether or not the system can change while the agent makes a decision\n",
        "* If environment doesn’t change but performance score does, semidynamic\n",
        "* Discrete vs. continuous, does the state of the environment change when time is handled, does it affect the percepts or actions \n",
        "* Known vs. unknown - agents knowledge about physics of the environment, are the outcomes of the moves given for any action\n",
        "* Experiments carried out for many environments draw from an environment class\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "* Agent architecture combines the agent program and agent function, to make the agent the architecture + program\n",
        "* Architecture makes the percepts from the sensors, runs the programs, then presents choices to make\n",
        "* Take in a percept and return an action to the actuators\n",
        "* Agent program only takes the current percept, agent function has the entire percept history\n",
        "* Need to be able to write programs to be rational from small programs instead of huge lookup tables\n",
        "* Reflex behaviors still occur in complex environments\n",
        "* Condition action rules in reflex agents, if something happens then react quickly with something else\n",
        "* Limited intelligence and only correct if the environment is fully observable\n",
        "* Can get stuck in infinite loops, or randomize its actions to get out of them\n",
        "* Model based reflex agetnts try to keep track of the previous world percepts\n",
        "* Need to know how the world changes over time, and how that is reflected in the agents percepts\n",
        "* Agent needs goal information to figure out where to go next\n",
        "* Search and planning used to determine how the agent should get to the goal\n",
        "* Utility agents have to distinguish between which world states make them happier\n",
        "* Agent chooses to maximize this utility measure\n",
        "* Agent has to choose the action that will yield the highest expected utility given the probabilities since it likely cannot always know what it will be\n",
        "* A model free agent can learn what action is best without learning how the environment changes as a result of it\n",
        "* Learning agent has a learning element that makes improvements and a performance element that makes actions\n",
        "* Learning element has a critic that tells how the agent is doing and how the performance element should be altered\n",
        "* Can give an award or penalty based on what actions the agent is taking\n",
        "* More expressive representations capture everything a less expressive representation does, often more concise\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"AI is the science of making machines that think like people, act like people, think rationally, and act rationally.\n",
        "* Rene Descartes - Principle of dualism - the mind or thinking itself is essentially incorporeal or spirital and that a mind exists separately from the body.\n",
        "* Alan Turing - Turing test - an evaluator judges a text based conversation between a computer and a machine, If the evaluator cannot tell the difference between the two, the machine passes the test. Are there imaginable digital computers which would do well in the imitation game?\n",
        "* John Seale - Application of rules to input symbols is not true intelligence, the Chinese Room. Contrasts strong AI with weak AI, argues that biological brains cause minds.\n",
        "Strong AI says the computer is a mind and can literally understand and have cognitive states, whereas weak AI just simulates thought, and their understanding isn't real understanding.\n",
        "* Daniel Dennett - Brain in a Vat, what makes this different from a computer processing symbols?\n",
        "Actually thinking versus simulating thinking is the main distinction in AI philosophy.\n",
        "\n",
        "Rational Agents:\n",
        "* focus in on acting rationally, and creating effective techniques for designing rational agents\n",
        "* An agent is anything that cna perceive an environment through sensors, and can act on its environment with actuators\n",
        "* A percept is the agent's inputs in the form of perceptions at a given time point.\n",
        "\n",
        "An agent is specified by an agent function (a mathematical abstract description) that maps f: P -> a , a sequence of percept vectors P to an action a from set A.\n",
        "\n",
        "P = [p0, p1, ... pt]\n",
        "A = [a0, a1, .. at]\n",
        "* An agent has sensors that perceive inputs from the environment in the form of percepts, then uses its actuators to perform actions in the environment.\n",
        "* The agent program (conversely to the agent function) runs on the architecture to produce f\n",
        "* The agent altogether is the archtiecture and the program\n",
        "\n",
        "Agent is anything that can be viewed as perceiving its environment with sensors and acting in that same environment with some form of actuators.\n",
        "* humans, thermostats, animals, roombas, robots, etc.\n",
        "A rational agent is any agent attempting to behave rationally in an environment where it perceives information. Related to consequentialism, doing \"the right thing\".\n",
        "\n",
        "Define a performance measure to see if the agent is acting rationally in the environment.\n",
        "* performance measure is a defined objective criteria for success of the behaior of the agent given the percepts as input.\n",
        "* Generally, it is better to design performance measures towards what you want the agent to achieve in the environment instead of how you think they should behave at a given point in time.\n",
        "* choose an action a for each possible input percept sequence P to maximize the performance measure.\n",
        "* In reality, the agent is not omniscient in the environment so we want to maximize the expected value of the performance measure based on the context that we have.\n",
        "\n",
        "Task Environments\n",
        "* For a given rational agent, we need to specify a task environment for which it is to find a solution.\n",
        "* PEAS: Performance Measure, Environment, Actuators, Sensors\n",
        "* Taxi example: P - safe, legal, maximize profits. E: roads, drivers, customers. A: brake, accelerator, gear shift. S: speedometer, odometer, rear camera.\n",
        "\n",
        "For a rational agent, the goal should be - given an environment defined with PEAS:\n",
        "1. Construct an agent function f (as an abstract mathematical description) to maximize the expected value of the performance measure\n",
        "2. Design an agent program (a concrete architecture implementation) to implement f.\n",
        "\n",
        "Things to consider:\n",
        "* Fully observable vs. partially observable (backgammon board vs. driving)\n",
        "* Deterministic (moves on a board) vs. nondeterministic (different results each time) vs. Stochastic (rolling a die)\n",
        "* Episodic (independent steps) vs. sequenatial (dependent steps)\n",
        "* Static (unchanging) vs. Dynamic (changing)\n",
        "* Discrete (stagnant) vs. Continuous (moving pieces around you)\n",
        "* Single vs. Multiple Agents\n",
        "\n",
        "Hardest environments are continuous, partially observable, stochastic, multiagent. \n",
        "Easier environments are static, fully observable, deterministic, discrete.\n",
        "* Reflex agents - agents that only select actions based on the current perception of information and ignore the history of the percepts\n",
        "* Problem solving agent - agents that plan ahead, consider sequence of actions towards a goal, a search.\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",
        "\"standard model\": \"foundation of AI, trying to create agents that do the right thing\",\n",
        "\"limited rationality\": \"when an agent makes the best decision possible in a constrained time environment\",\n",
        "\"value alignment problem\": \"the objectives of the machine have to be in line with those of the human who designed it\",\n",
        "\"Turing test\" : \"A test to deem whether or not a machine could think, could it make indistiguishable responses\",\n",
        "\"Total Turing test\": \"Extension of a Turing test that requires computer vision and robotics to interact with the world\",\n",
        "\"Cognitive Science\": \"interdisciplinary field that combines computer models and psychology to create theories about the mind\",\n",
        "\"Weak AI\": \"machines only act as if they are intelligent but are not inherently\",\n",
        "\"Strong AI\": \"machines are actually thinking consciously and not just simulating it\",\n",
        "\"Good Old-Fashioned AI\": \"simple logical agents criticized in early AI, couldn't capture all behaviors - qualification problem\",\n",
        "\"embodied cognition\":  \"doesn't make sense to separate the brain from the body, study the entire system\",\n",
        "\"polite convention\": \"Turing's assertion that everyone thinks\",\n",
        "\"Chinese room\": \"Searle's thought experiment, no thinking being generated only transcription of symbols\",\n",
        "\"biological naturalism\": \"says that mental states are high level features resulting form low level processes in neurons, which themselves don't matter\",\n",
        "\"consciousness\": \"key point in AI, can the machine be aware of the world and experience living, do they have qualia\",\n",
        "\"agent\" : \"anything that can perceive and act in an environment with sensors, acts with actuators\",\n",
        "\"percept\": \"what the agent is presented to perceive\",\n",
        "\"percept sequence\": \"history of all of the percepts the agent has seen\",\n",
        "\"agent function\": \"maps a percept sequence fed to the agent to an action\",\n",
        "\"agent program\": \"the internal implementation of the agent function\",\n",
        "\"rational agent\" : \"any agent that acts to maximize the best outcome or best expected outcome if unsure\",\n",
        "\"consequentialism\": \"agents performance is measure but the consequences of its actions\",\n",
        "\"performance measure\": \"how we judge what the agent has done in an environment\",\n",
        "\"omniscience\": \"agent knows everything about the system and its outcomes, not possible to achieve\",\n",
        "\"information gathering\": \"collecting details about the environemtn to modify future percepts\",\n",
        "\"task environments\": \"the problem spaces where we place agents to find solutions\",\n",
        "\"simple reflex agent\": \"agents that select an action based only on the current percept\",\n",
        "\"transition model\": \"knows how the world works for model based reflex agents\",\n",
        "\"sensor model\": \"how the state is current expressed in the agents percepts\",\n",
        "\"utility function\": \"an internal representation of the agents performance measure\",\n",
        "\"problem generator\": \"suggests actions that leads to new environments that the agent can learn from\",\n",
        "\"atomic representation\": \"every state of the world has no internal structure\",\n",
        "\"factored representation\": \"splits a state up into variables and attributes with values\",\n",
        "\"structured representation\": \"objects and their various relationships are described explicitly\",\n",
        "\"localist representation\": \"concepts and memory locations have a one to one mapping\",\n",
        "\"distributed representation\": \"concept spread across memory locations, each of which can have multiple concepts\"\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": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "gYYeNcdM_maE",
        "outputId": "4dd8ef43-2220-4bea-d8a3-f5ff794a5e7d"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              "\n",
              "* Generally want AI to do the right thing, defined as rationality\n",
              "* this intelligence can either thought processes and reasoning or actual intelligent behavior\n",
              "* computer would need natural language processing, knowledge representation, automated reasoning, and machine learning to pass the Turing test\n",
              "* Think of a human thought in terms of introspection (thinking about their thoughts), psychological experiments, and brain imaging\n",
              "* Aristotle tried to quantify what thinking was right meant, created syllogisms for patterns for arguments that gave correct conclusions when fed the right premise, initalized field of logic\n",
              "* Logicist tradition was the first forms of problems solved when a solvable problem was described in a certain way\n",
              "* probability is used to fill in the gaps of uncertainty when dealing with logical problems\n",
              "* all skills for the turing test allow rational agents to exist\n",
              "* early agents were built based on logical foundations, transitioned to be probability and machine learning to make the best decision possible in an environment\n",
              "* agents with incorrect objectives are more difficult to correct in modern design \n",
              "* not incorrect or unintelligent when it acts \"irrationally\", it is doing so to reach the objective\n",
              "* want to create agents that are provably beneficial to humans\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              "\n",
              "* Searle defined weak AI vs. strong AI, strong AI shifted to human level AI\n",
              "* Turing claimed that human behavior was too complex to simulate with any sort of computer\n",
              "* Turing outlined all of the things computers could never do, some of which has already happened\n",
              "* Turing and Godel proved there existed questions that were not answerable by formal systems\n",
              "* thought that this proved machines were inferior to humans mentally\n",
              "* incompleteness theorem that Godel created applies more to mathematics than computers\n",
              "* only really applies to formal systems that can do arithmetic\n",
              "* Turing test tried to get a human to believe that a computer answering questions was also a human\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " \n",
              "* Is a machine that is intelligent actually thinking or only simulating it\n",
              "* Difficult to draw a line on consciousness, especially in computers\n",
              "* Turing believed this was a difficult but necessary problem to understand when dealing with AI\n",
              "* machines can't experience things the same way as humans but can still run code, is that really different\n",
              "\n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              "\n",
              "* An agents choice of action at any time can depend on its previous knowledge but nothing it hasn’t seen before\n",
              "* Agent function is a abstract definition while the agent program is the architecture implementation\n",
              "* Define agents to learn about the system, not every thing is an agent or a non agent\n",
              "\n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              "\n",
              "* We need to establish performance measures because the machines have no point of view\n",
              "* Want to design performance measures towards what we want to achieve in an environment, not how we think the agent should get there\n",
              "* Rationality depends on the performance measure, the prior knowledge of the system, the actions possible, and the percept sequence to that point\n",
              "* Agent chooses an action to maximize the performance measure that is expected\n",
              "* Agent has to explore an environment if they are unfamiliar with it\n",
              "* Rationality does not equal perfection\n",
              "* Want the agent to both gather information and learn from it\n",
              "* Agent lacks autonomy since it relies on the designer to tell it what to achieve\n",
              "\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              "\n",
              "* Task environment defined by PEAS (performance, environment, actuators, sensors)\n",
              "* Tradeoffs often required in performance measures\n",
              "* The more restricted the environment, the design problem becomes easier\n",
              "* Virtual environments are just as complex as the real world, can have a software agent instead of a physical agent\n",
              "* Fully observable vs. partially observable - whether or not the sensors give the agent access to the entire environment at any given time\n",
              "* Also fully observable if the agent knows all things relevant to the action to be performed next\n",
              "* Unobservable environment created if the agent has no sensors to perceive the environment\n",
              "* Single agent vs. multiple agents important to keep in mind, can be competitive or cooperative\n",
              "* Deterministic vs. nondeterministic - whether or not the next state is determined entirely by the actions of the agent in the current state\n",
              "* Stochastic if it explicitly deals with probabilities versus nondeterministic \n",
              "* Episodic vs. sequential - whether or not it is divided into atomic episodes\n",
              "* Static vs. dynamic - whether or not the system can change while the agent makes a decision\n",
              "* If environment doesn’t change but performance score does, semidynamic\n",
              "* Discrete vs. continuous, does the state of the environment change when time is handled, does it affect the percepts or actions \n",
              "* Known vs. unknown - agents knowledge about physics of the environment, are the outcomes of the moves given for any action\n",
              "* Experiments carried out for many environments draw from an environment class\n",
              "\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              "\n",
              "* Agent architecture combines the agent program and agent function, to make the agent the architecture + program\n",
              "* Architecture makes the percepts from the sensors, runs the programs, then presents choices to make\n",
              "* Take in a percept and return an action to the actuators\n",
              "* Agent program only takes the current percept, agent function has the entire percept history\n",
              "* Need to be able to write programs to be rational from small programs instead of huge lookup tables\n",
              "* Reflex behaviors still occur in complex environments\n",
              "* Condition action rules in reflex agents, if something happens then react quickly with something else\n",
              "* Limited intelligence and only correct if the environment is fully observable\n",
              "* Can get stuck in infinite loops, or randomize its actions to get out of them\n",
              "* Model based reflex agetnts try to keep track of the previous world percepts\n",
              "* Need to know how the world changes over time, and how that is reflected in the agents percepts\n",
              "* Agent needs goal information to figure out where to go next\n",
              "* Search and planning used to determine how the agent should get to the goal\n",
              "* Utility agents have to distinguish between which world states make them happier\n",
              "* Agent chooses to maximize this utility measure\n",
              "* Agent has to choose the action that will yield the highest expected utility given the probabilities since it likely cannot always know what it will be\n",
              "* A model free agent can learn what action is best without learning how the environment changes as a result of it\n",
              "* Learning agent has a learning element that makes improvements and a performance element that makes actions\n",
              "* Learning element has a critic that tells how the agent is doing and how the performance element should be altered\n",
              "* Can give an award or penalty based on what actions the agent is taking\n",
              "* More expressive representations capture everything a less expressive representation does, often more concise\n",
              "\n",
              "\n",
              "## Module 1 Lecture Notes\n",
              "AI is the science of making machines that think like people, act like people, think rationally, and act rationally.\n",
              "* Rene Descartes - Principle of dualism - the mind or thinking itself is essentially incorporeal or spirital and that a mind exists separately from the body.\n",
              "* Alan Turing - Turing test - an evaluator judges a text based conversation between a computer and a machine, If the evaluator cannot tell the difference between the two, the machine passes the test. Are there imaginable digital computers which would do well in the imitation game?\n",
              "* John Seale - Application of rules to input symbols is not true intelligence, the Chinese Room. Contrasts strong AI with weak AI, argues that biological brains cause minds.\n",
              "Strong AI says the computer is a mind and can literally understand and have cognitive states, whereas weak AI just simulates thought, and their understanding isn't real understanding.\n",
              "* Daniel Dennett - Brain in a Vat, what makes this different from a computer processing symbols?\n",
              "Actually thinking versus simulating thinking is the main distinction in AI philosophy.\n",
              "\n",
              "Rational Agents:\n",
              "* focus in on acting rationally, and creating effective techniques for designing rational agents\n",
              "* An agent is anything that cna perceive an environment through sensors, and can act on its environment with actuators\n",
              "* A percept is the agent's inputs in the form of perceptions at a given time point.\n",
              "\n",
              "An agent is specified by an agent function (a mathematical abstract description) that maps f: P -> a , a sequence of percept vectors P to an action a from set A.\n",
              "\n",
              "P = [p0, p1, ... pt]\n",
              "A = [a0, a1, .. at]\n",
              "* An agent has sensors that perceive inputs from the environment in the form of percepts, then uses its actuators to perform actions in the environment.\n",
              "* The agent program (conversely to the agent function) runs on the architecture to produce f\n",
              "* The agent altogether is the archtiecture and the program\n",
              "\n",
              "Agent is anything that can be viewed as perceiving its environment with sensors and acting in that same environment with some form of actuators.\n",
              "* humans, thermostats, animals, roombas, robots, etc.\n",
              "A rational agent is any agent attempting to behave rationally in an environment where it perceives information. Related to consequentialism, doing \"the right thing\".\n",
              "\n",
              "Define a performance measure to see if the agent is acting rationally in the environment.\n",
              "* performance measure is a defined objective criteria for success of the behaior of the agent given the percepts as input.\n",
              "* Generally, it is better to design performance measures towards what you want the agent to achieve in the environment instead of how you think they should behave at a given point in time.\n",
              "* choose an action a for each possible input percept sequence P to maximize the performance measure.\n",
              "* In reality, the agent is not omniscient in the environment so we want to maximize the expected value of the performance measure based on the context that we have.\n",
              "\n",
              "Task Environments\n",
              "* For a given rational agent, we need to specify a task environment for which it is to find a solution.\n",
              "* PEAS: Performance Measure, Environment, Actuators, Sensors\n",
              "* Taxi example: P - safe, legal, maximize profits. E: roads, drivers, customers. A: brake, accelerator, gear shift. S: speedometer, odometer, rear camera.\n",
              "\n",
              "For a rational agent, the goal should be - given an environment defined with PEAS:\n",
              "1. Construct an agent function f (as an abstract mathematical description) to maximize the expected value of the performance measure\n",
              "2. Design an agent program (a concrete architecture implementation) to implement f.\n",
              "\n",
              "Things to consider:\n",
              "* Fully observable vs. partially observable (backgammon board vs. driving)\n",
              "* Deterministic (moves on a board) vs. nondeterministic (different results each time) vs. Stochastic (rolling a die)\n",
              "* Episodic (independent steps) vs. sequenatial (dependent steps)\n",
              "* Static (unchanging) vs. Dynamic (changing)\n",
              "* Discrete (stagnant) vs. Continuous (moving pieces around you)\n",
              "* Single vs. Multiple Agents\n",
              "\n",
              "Hardest environments are continuous, partially observable, stochastic, multiagent. \n",
              "Easier environments are static, fully observable, deterministic, discrete.\n",
              "* Reflex agents - agents that only select actions based on the current perception of information and ignore the history of the percepts\n",
              "* Problem solving agent - agents that plan ahead, consider sequence of actions towards a goal, a search.\n",
              "\n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Standard model** - foundation of AI, trying to create agents that do the right thing\n",
              "* **Limited rationality** - when an agent makes the best decision possible in a constrained time environment\n",
              "* **Value alignment problem** - the objectives of the machine have to be in line with those of the human who designed it\n",
              "* **Turing test** - A test to deem whether or not a machine could think, could it make indistiguishable responses\n",
              "* **Total turing test** - Extension of a Turing test that requires computer vision and robotics to interact with the world\n",
              "* **Cognitive science** - interdisciplinary field that combines computer models and psychology to create theories about the mind\n",
              "* **Weak ai** - machines only act as if they are intelligent but are not inherently\n",
              "* **Strong ai** - machines are actually thinking consciously and not just simulating it\n",
              "* **Good old-fashioned ai** - simple logical agents criticized in early AI, couldn't capture all behaviors - qualification problem\n",
              "* **Embodied cognition** - doesn't make sense to separate the brain from the body, study the entire system\n",
              "* **Polite convention** - Turing's assertion that everyone thinks\n",
              "* **Chinese room** - Searle's thought experiment, no thinking being generated only transcription of symbols\n",
              "* **Biological naturalism** - says that mental states are high level features resulting form low level processes in neurons, which themselves don't matter\n",
              "* **Consciousness** - key point in AI, can the machine be aware of the world and experience living, do they have qualia\n",
              "* **Agent** - anything that can perceive and act in an environment with sensors, acts with actuators\n",
              "* **Percept** - what the agent is presented to perceive\n",
              "* **Percept sequence** - history of all of the percepts the agent has seen\n",
              "* **Agent function** - maps a percept sequence fed to the agent to an action\n",
              "* **Agent program** - the internal implementation of the agent function\n",
              "* **Rational agent** - any agent that acts to maximize the best outcome or best expected outcome if unsure\n",
              "* **Consequentialism** - agents performance is measure but the consequences of its actions\n",
              "* **Performance measure** - how we judge what the agent has done in an environment\n",
              "* **Omniscience** - agent knows everything about the system and its outcomes, not possible to achieve\n",
              "* **Information gathering** - collecting details about the environemtn to modify future percepts\n",
              "* **Task environments** - the problem spaces where we place agents to find solutions\n",
              "* **Simple reflex agent** - agents that select an action based only on the current percept\n",
              "* **Transition model** - knows how the world works for model based reflex agents\n",
              "* **Sensor model** - how the state is current expressed in the agents percepts\n",
              "* **Utility function** - an internal representation of the agents performance measure\n",
              "* **Problem generator** - suggests actions that leads to new environments that the agent can learn from\n",
              "* **Atomic representation** - every state of the world has no internal structure\n",
              "* **Factored representation** - splits a state up into variables and attributes with values\n",
              "* **Structured representation** - objects and their various relationships are described explicitly\n",
              "* **Localist representation** - concepts and memory locations have a one to one mapping\n",
              "* **Distributed representation** - concept spread across memory locations, each of which can have multiple concepts\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": null,
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "outputs": [],
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "Python Positive Features\n",
        "* Fast development, garbage collected with whitespace delimited syntax\n",
        "* Runs on major platforms without alterations\n",
        "* Built in types of lists, dicts, sets\n",
        "* Supported libraries of Numpy, Pandas, Sklearn, Pytorch, Tensorflow, etc. available for easy importing\n",
        "\n",
        "Simplest python program: print(\"Hello world\")\n",
        "\n",
        "Structure of a file:\n",
        "* Whitespace is meaningful, tab delimited or 4 spaces\n",
        "* Use a new line to end a line of code, or \\ to do so prematurely\n",
        "* Blocks are defined by the indendtation, colon appears at the end of a line starting a new block, subsequent blocks have more indentation if inside\n",
        "\n",
        "if expr: else:\n",
        "\n",
        "Objects\n",
        "* All data treated like an object, deleted once unreachable by garbage collection\n",
        "* Strong typing, interpreter doesn't allow incompatabilities with typings. Find out with type(object) and isinstance(object, type)\n",
        "* int, float, str, tuple, dict, list, bool, None, generator, function all first class objects\n",
        "\n",
        "Dynamic Typing  - variables aren't declared preemptively, come into existance when assigned, type determined and can be reassigned, fucntions have no signature. Typing errors have to be caught at runtime\n",
        "\n",
        "Math - Literals (integers, floats, booleans), operations (arithmetic, power (**), modulo (%), comparison, logic), assignment operators (+=, /=)\n",
        "\n",
        "Strings\n",
        "* single or double quote, can concatenate strings with +\n",
        "* can be prefixed with r to mean raw, and can print with % formatting e.g. print('%s can you count to %d' % (\"Sarah\", 1000))\n",
        "* IMMUTABLE\n",
        "* .split(), \"_\".join(words), .capitalize(), .upper(), .strip()\n",
        "\n",
        "Strings vs. Lists vs. Tuples:\n",
        "* Strings - immutable, == to check if they are the same, 'is' for if they are the same object, unicode or 2-byte chracters\n",
        "* Lists - mutable, y = x[:] to get shallow copy, deep copy also possible with import copy, can be mixed type objects\n",
        "* Tuples - immutable ordered sequence of items, can be of mixed type objects\n",
        "\n",
        "Slicing: t = ('a', 'b', 'c', 'd', 'e') [start:stop:step]\n",
        "* t[1:4] -> ('b', 'c', 'd')\n",
        "* t[1:-1] -> ('b', 'c', 'd')\n",
        "* t[1: -1: 2] -> ('b', 'd')\n",
        "* t[:2] -> ('a', 'b')\n",
        "* t[2:] -> ('c', 'd', 'e')\n",
        "\n",
        "List operations: a = [1, 2, 3, 4, 5]\n",
        "* a.append('b') -> [1, 2, 3, 4, 5, 'b']\n",
        "* a.insert(2, 'b') -> [1, 2, 'b', 3, 4, 5, 'b']\n",
        "* a.index(2) -> 1\n",
        "* a.count('b') -> 2\n",
        "* a.remove('b') -> [1, 2, 3, 4, 5, 'b']\n",
        "* a.sort(), a.reverse() operations in place, returns nothing\n",
        "\n",
        "Dictionaries - unordered hashes, keys must be immutable, constant average add, lookup, update\n",
        "* .keys(), .values(), .items() (item tuples)\n",
        "* A = {\"a\": '1', \"b\": 2}\n",
        "* d[\"a\"] -> 1\n",
        "* defaultdict automatically creates empty dictionary values\n",
        "\n",
        "Functions - beings with def, first line with less indentation outside function definition, return to send value back to caller\n",
        "* multiple return values allowed, not overloading allowed\n",
        "* default arguments allowed - def testfunc(a, b = 2, c = 'world'):\n",
        "* keyword arguments can be called out of order, but non-default arguments must come first otherwise syntaxerror\n",
        "* #args passes in variable number of non-keyword arguments\n",
        "* ##kwargs  passes in variable number of keyword arguments\n",
        "\n",
        "* Dynamic Scoping - function sees most current value of variables\n",
        "* Default parameter values only evaluated when def statement they belong to is first executed\n",
        "\n",
        "Class construction\n",
        "* Class Test - def __init__(self, name, input): ..., def func_2(self):\n",
        "* Subclasses - can extend the previous instantiation of another class, allows use of methods and attributes defined previous. class Test2(Test)\n",
        "* Can redefine a method of the parents class that will overwrite it, include the self argument\n",
        "\n",
        "Magic methods:\n",
        "* __init__: the constructor\n",
        "* __len__: how the len(obj) is defined\n",
        "* __copy__: how to copy a class\n",
        "* __cmp__: how == works\n",
        "* __add__: how + works for a class\n",
        "* __neg__: how unary negation works for class\n",
        "\n",
        "main function: if __name__ == '__main__': ...\n",
        "\n",
        "For loops:\n",
        "* For <item> in <collection>: <do statements>\n",
        "* can be tuples as well: for (x, y) in [(1, 2), (3, 4)]\n",
        "\n",
        "List Comprehension\n",
        "* list from 1 - 100: [x for x in range(1, 101)]\n",
        "* multiply by 2: [x * 2 for x in li]\n",
        "* Filtered divide: [x / 2 for x in li if x < 10]\n",
        "\n",
        "Iterators - iterable objects can be used in loops because they have __iter__ method\n",
        "* a = [1,2,3]\n",
        "* a.__iter__() produces iter object, iter(a) produces iter object\n",
        "* a.__next__() or a.next(), throws a stopiteration exception if it does not have a next element\n",
        "* Efficient in memory, do not return until called upon\n",
        "\n",
        "Generators - Iterators with __next__() method\n",
        "* use yield keyword to return a generator whenever they are called in a function\n",
        "* each time it is called, runs until it hits th enext yield statement, picks up next time where it left off\n",
        "* less code, local state maintained, computed as needed, doesn't store in memory, works for infinite sequences\n",
        "* if need to look at individual elements not as good.\n",
        "\n",
        "Imports - import packages using import <item>, from <item> import <function>, from <item> import *, import <item> as shorthand\n",
        "Pip - package installer for python, allows installation of external libraries\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"REPL\" : \"Read-Evaluate-Print Loop, type a sequence in and returns the evaluated expression\",\n",
        "\"Scripts\" : \"Created text files run with python3 script.py, not REPL so need to use print\",\n",
        "\"First Class Objects\": \"Entity that can be dynamically created, destroyed, passed to a function, returned as a value, all rights of variable\",\n",
        "\"Duck typing\": \"establishes suitability of an object by determining presence of previous methods defined\"\n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "ydOK__lwWgdp",
        "outputId": "8b04a6de-2cfe-47dd-ffd5-1d2095e8e47d"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "\n",
              "Python Positive Features\n",
              "* Fast development, garbage collected with whitespace delimited syntax\n",
              "* Runs on major platforms without alterations\n",
              "* Built in types of lists, dicts, sets\n",
              "* Supported libraries of Numpy, Pandas, Sklearn, Pytorch, Tensorflow, etc. available for easy importing\n",
              "\n",
              "Simplest python program: print(\"Hello world\")\n",
              "\n",
              "Structure of a file:\n",
              "* Whitespace is meaningful, tab delimited or 4 spaces\n",
              "* Use a new line to end a line of code, or \\ to do so prematurely\n",
              "* Blocks are defined by the indendtation, colon appears at the end of a line starting a new block, subsequent blocks have more indentation if inside\n",
              "\n",
              "if expr: else:\n",
              "\n",
              "Objects\n",
              "* All data treated like an object, deleted once unreachable by garbage collection\n",
              "* Strong typing, interpreter doesn't allow incompatabilities with typings. Find out with type(object) and isinstance(object, type)\n",
              "* int, float, str, tuple, dict, list, bool, None, generator, function all first class objects\n",
              "\n",
              "Dynamic Typing  - variables aren't declared preemptively, come into existance when assigned, type determined and can be reassigned, fucntions have no signature. Typing errors have to be caught at runtime\n",
              "\n",
              "Math - Literals (integers, floats, booleans), operations (arithmetic, power (**), modulo (%), comparison, logic), assignment operators (+=, /=)\n",
              "\n",
              "Strings\n",
              "* single or double quote, can concatenate strings with +\n",
              "* can be prefixed with r to mean raw, and can print with % formatting e.g. print('%s can you count to %d' % (\"Sarah\", 1000))\n",
              "* IMMUTABLE\n",
              "* .split(), \"_\".join(words), .capitalize(), .upper(), .strip()\n",
              "\n",
              "Strings vs. Lists vs. Tuples:\n",
              "* Strings - immutable, == to check if they are the same, 'is' for if they are the same object, unicode or 2-byte chracters\n",
              "* Lists - mutable, y = x[:] to get shallow copy, deep copy also possible with import copy, can be mixed type objects\n",
              "* Tuples - immutable ordered sequence of items, can be of mixed type objects\n",
              "\n",
              "Slicing: t = ('a', 'b', 'c', 'd', 'e') [start:stop:step]\n",
              "* t[1:4] -> ('b', 'c', 'd')\n",
              "* t[1:-1] -> ('b', 'c', 'd')\n",
              "* t[1: -1: 2] -> ('b', 'd')\n",
              "* t[:2] -> ('a', 'b')\n",
              "* t[2:] -> ('c', 'd', 'e')\n",
              "\n",
              "List operations: a = [1, 2, 3, 4, 5]\n",
              "* a.append('b') -> [1, 2, 3, 4, 5, 'b']\n",
              "* a.insert(2, 'b') -> [1, 2, 'b', 3, 4, 5, 'b']\n",
              "* a.index(2) -> 1\n",
              "* a.count('b') -> 2\n",
              "* a.remove('b') -> [1, 2, 3, 4, 5, 'b']\n",
              "* a.sort(), a.reverse() operations in place, returns nothing\n",
              "\n",
              "Dictionaries - unordered hashes, keys must be immutable, constant average add, lookup, update\n",
              "* .keys(), .values(), .items() (item tuples)\n",
              "* A = {\"a\": '1', \"b\": 2}\n",
              "* d[\"a\"] -> 1\n",
              "* defaultdict automatically creates empty dictionary values\n",
              "\n",
              "Functions - beings with def, first line with less indentation outside function definition, return to send value back to caller\n",
              "* multiple return values allowed, not overloading allowed\n",
              "* default arguments allowed - def testfunc(a, b = 2, c = 'world'):\n",
              "* keyword arguments can be called out of order, but non-default arguments must come first otherwise syntaxerror\n",
              "* #args passes in variable number of non-keyword arguments\n",
              "* ##kwargs  passes in variable number of keyword arguments\n",
              "\n",
              "* Dynamic Scoping - function sees most current value of variables\n",
              "* Default parameter values only evaluated when def statement they belong to is first executed\n",
              "\n",
              "Class construction\n",
              "* Class Test - def __init__(self, name, input): ..., def func_2(self):\n",
              "* Subclasses - can extend the previous instantiation of another class, allows use of methods and attributes defined previous. class Test2(Test)\n",
              "* Can redefine a method of the parents class that will overwrite it, include the self argument\n",
              "\n",
              "Magic methods:\n",
              "* __init__: the constructor\n",
              "* __len__: how the len(obj) is defined\n",
              "* __copy__: how to copy a class\n",
              "* __cmp__: how == works\n",
              "* __add__: how + works for a class\n",
              "* __neg__: how unary negation works for class\n",
              "\n",
              "main function: if __name__ == '__main__': ...\n",
              "\n",
              "For loops:\n",
              "* For <item> in <collection>: <do statements>\n",
              "* can be tuples as well: for (x, y) in [(1, 2), (3, 4)]\n",
              "\n",
              "List Comprehension\n",
              "* list from 1 - 100: [x for x in range(1, 101)]\n",
              "* multiply by 2: [x * 2 for x in li]\n",
              "* Filtered divide: [x / 2 for x in li if x < 10]\n",
              "\n",
              "Iterators - iterable objects can be used in loops because they have __iter__ method\n",
              "* a = [1,2,3]\n",
              "* a.__iter__() produces iter object, iter(a) produces iter object\n",
              "* a.__next__() or a.next(), throws a stopiteration exception if it does not have a next element\n",
              "* Efficient in memory, do not return until called upon\n",
              "\n",
              "Generators - Iterators with __next__() method\n",
              "* use yield keyword to return a generator whenever they are called in a function\n",
              "* each time it is called, runs until it hits th enext yield statement, picks up next time where it left off\n",
              "* less code, local state maintained, computed as needed, doesn't store in memory, works for infinite sequences\n",
              "* if need to look at individual elements not as good.\n",
              "\n",
              "Imports - import packages using import <item>, from <item> import <function>, from <item> import *, import <item> as shorthand\n",
              "Pip - package installer for python, allows installation of external libraries\n",
              "\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Repl** - Read-Evaluate-Print Loop, type a sequence in and returns the evaluated expression\n",
              "* **Scripts** - Created text files run with python3 script.py, not REPL so need to use print\n",
              "* **First class objects** - Entity that can be dynamically created, destroyed, passed to a function, returned as a value, all rights of variable\n",
              "* **Duck typing** - establishes suitability of an object by determining presence of previous methods defined\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": null,
      "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 = \"\"\"\n",
        "* Goal formation: the person wants to get to Bucharest, makes this their goal. This goal will limit their movements and actions\n",
        "* Problem formulation: the person creates an abstract model of the environment, in this case a map of Romania with all of the cities and their distances\n",
        "* Search: before actually moving, they simulate the steps to take until a solution is found, will likely have to iterate through a bunch of them\n",
        "* Execution: the agent has created the best path and now goes down it to get to Bucharest\n",
        "* For a fully observable, deterministic, known environment we will have a fixed sequence of actions from the start to goal node\n",
        "* A search problem as the following:\n",
        "* Set of states (state space) that the environment can be\n",
        "* Initial state where the agent starts\n",
        "* Set of 1+ goal states, goal can be defined to be many different things\n",
        "* Actions available to get to the goal, each one is applicable in s\n",
        "* Transition model that describes what an action does\n",
        "* Action cost function that calculates the cost to make some action in a current state\n",
        "* Path is a sequence of actions that gets to our solution, with the optimal solution being the lowest path cost\n",
        "* Can be seen as a graph with directed edges as actions and states as nodes\n",
        "* Have to determine a level of abstraction that is valid so we can arrive at a solution, useful if it is easier than the original problem\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "* Create a grid world of 2d space where the agents can move side to side and up and down\n",
        "* Vacuum world has the following setup\n",
        "* State: which objects are In each cell, agent and/or dirt\n",
        "* Initial state: any one can be chosen\n",
        "* Actions: suck, move left, or move right\n",
        "* Transition model: suck up dirt, move the agent forward for backward\n",
        "* Goal state: when everything is clean\n",
        "* Action cost: everything is 1\n",
        "* Sliding tile puzzle example:\n",
        "* states: any setup of the 1-8 tiles\n",
        "* Initial state: whichever setup of the tiles we pick to be the start\n",
        "* Actions: can slide up, down, left, right if possible\n",
        "* Transition model: if we move left, the tile in the position to move to the left actually goes there\n",
        "* Goal state: when the numbers are in order\n",
        "* Action cost: everything is 1\n",
        "* Touring problems are sets of places that have to be visited\n",
        "* VLSI layout optimal positioning is important with cell layouts and channel routings\n",
        "* Robot navigation, automatic assembly sequencing of complex objects, protein design all search problems\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "* Representing search state space graphs as search trees, with the root as the initial point and each node in the tree corresponding to a search tree, edges are the actions to get tho that state\n",
        "* State space is the set of states in the world and actions that allow transitions, whereas the tree just describes paths to get to these states\n",
        "* Expand a node and get its children (or successor) nodes, previous node becomes the parent\n",
        "* Frontier for prioritizing what to look at next, call a node reached if its been expanded\n",
        "* A node in the tree has a state corresponding to it, a parent node, an action that got it there, and a path cost to get there from the initial state\n",
        "* Types of queues we consider: priority queue (minimum cost popped off first), FIFO (first in first out) queue, LIFO (last in first out, or a stack) queue\n",
        "* Trees have repeated states, or a cycle, redundant paths\n",
        "* If we don’t remember the past we’ll run into the same states over and over\n",
        "* Graph search keep track of the previous states and checks for redundant paths, although not always necessary/important\n",
        "* More memory but less redundant paths\n",
        "* We can check for cycles in tree search but redundancy hard to look for\n",
        "* Search must be systematic in some way in order to be complete\n",
        "* Depth is the number of actions to get to the optimal solution, or depth of the tree, m is the maximum number of actions in any path, not necessarily the optimal path, and b is the branching factor that estimates the number of successors for each node to look into\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "* FIFO queue faster than priority queue in BFS\n",
        "* BFS cost optimal when all actions have the same cost, complete in both cases\n",
        "* O(b^d) nodes generated, time and space the same\n",
        "* Memory requirements much bigger worry than execution time, cannot be solved for except in smallest instances\n",
        "* Djikstras/Uniform cost search evaluates the path cost to the current node, UCS has a goal state\n",
        "* Can be inefficient if explores large area with lose costs away from the goal node, never gets caught in single infinite path\n",
        "* DFS backs up when a goal isn’t found recursively, not cost toptimal\n",
        "* Efficient and complete in finite state spaces, can hit loops\n",
        "* Much better for memory, no reached table needed at all, small frontier\n",
        "* O(bm) complexity, b is branching factor and m is max depth of the tree\n",
        "* For backtracking to work we ned a way of undoing our modifications to the state\n",
        "* If we pick a bad L in depth limited search we are going to be inefficient\n",
        "* Iterative deepening optimal for when all actions have the same cost, O(b^d) when a solution exists and O(b^m) when it doesn’t \n",
        "* Iterative deepening generally preferred when search state space is larger than can fit in memory and the depth is unknown\n",
        "* Bidirectional has two frontiers and two tables of reach states, need to be able to reason backwards\n",
        "* Pass in 2 versions of the program and evaluation function for forward and reverse direction\n",
        "* When the first solution is found, it is guaranteed to be optimal if the evaluation function is the path cos\n",
        "* Bidirectional is complete if b is finite and both directions are breadth first or uniform cost\n",
        "* Optimal cost when all action costs are identical and both directions are breadth first or uniform cost\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "Reflex agent vs. Problem Solving Agent\n",
        "* Reflex agent ignores the past percept histroay and only makes an action based on the current percept\n",
        "* Problem Solving Agents plan ahead and perform a search to reach the solution state, execute a sequence of actions\n",
        "\n",
        "Task environment effects\n",
        "* If environment is fully oberservable, deterministics, known it is a sequence of fixed actions that won't change\n",
        "* If either partially observerable or nondeterministic the agent must be flexible with the percepts it receives before making a decision, branching strategy\n",
        "\n",
        "Search Problem components:\n",
        "1. States: a set S of possible states, with an initial state (1a) si that exists in S\n",
        "2. Actions: a set A of all possible actions that can be executed in s and are applicable\n",
        "3. Transition Model: the set of all states and all actions that exist, and their resulting successor states, denotes as s_r. The state space is comprised of the initial state and all successors\n",
        "4. Path Cost function: the performance measure that we are using to calculate the step cost, assuming its at least 0. The cost it takes from state x to state y using an action a.\n",
        "5. Goal state: The goals, s is a goal state if Goal(s) is true, can also be implicit.\n",
        "\n",
        "Formulating a Search Problem - how this is done affects the search space and the speed of search\n",
        "* Decide which properties matter versus others and how to represent each state in the environment\n",
        "* Decide which actions are possible and how we represent them in actions and transition models\n",
        "* Decide which path is next using the cost function\n",
        "\n",
        "Selecting a state space:\n",
        "* State space must be abstracted from the real world since it is very complex. State generally is a set of real-world staates\n",
        "* Action is a class of cominations of real-world equivalent actions\n",
        "* both of these are abstractions, so they should in theory be easier to solve than the real-world problem.\n",
        "\n",
        "State space terminology:\n",
        "* State space - set of all states reachable by any sequence of actions, can expand very quickly depending on how it was constructed\n",
        "* Path - how to get from one state to another state, and what actions led you there\n",
        "* Solution - a complete path from the initial state to the goal state\n",
        "* Search Tree - way to representing the paths with the initial state at the root, checks redundant nodes\n",
        "* Frontier - queue of what is to be explored next, available actions we can look at next\n",
        "* Optimal solution - optimal path from start to goal state with no possible lower cost of getting there\n",
        "\n",
        "Tree Search:\n",
        "* Go through every possible path from the initial state in some order, with the root as the initial state and all other states as leaves\n",
        "* Each path to the same node is distinct, so we may be checking for redundant paths\n",
        "* This failure to check the states can make a linear search problem become exponential\n",
        "\n",
        "State vs. Node: States are representations of physical configurations (like the game board itself), whereas nodes are the data structure of the part of a search tree, including its parent, children, costs, etc.\n",
        "\n",
        "Graph Search:\n",
        "* Attempting to improve upon tree search by storing whether or not a node has been visited before adding it to the frontier\n",
        "* Memory cost is greater than that of tree search but can make the search linear which is ideal\n",
        "\n",
        "Uninformed Search strategy ranks all nodes as equally favorable to explore, whereas an informed search ranks nodes in some uniform way\n",
        "\n",
        "Criteria for search strategies:\n",
        "* Strategy - how the tree is expeanded (queue, priority, etc.)\n",
        "* Completeness - whether or not a solution can always be found\n",
        "* Optimality - when a solution is found, is it always the lowest cost solution?\n",
        "* Time Complexity - how many nodes are generated in the exploration\n",
        "* Space Complexity - how many nodes are stored in memory simultaneously during exploration\n",
        "* b = maximum branching factor, d = depth of shallowest goal node, m - maximum length of any pace in state space\n",
        "\n",
        "Breadth-First Search (BFS)\n",
        "* Expand the nearest node first, and create a FIFO queue, putting any discovered nodes at the end of the frontier\n",
        "* look at each layer individually before moving to the next one, repeat in the next layer\n",
        "* Complete if b is finite, optimal if cost = 1 per step (although generally no), O(b^d) time complexity, O(b^d) space complexity to store all nodes\n",
        "* Very bad in situations with exponential complexity \n",
        "* use over DFS if infinite paths are possible, some solutions are short and you can get rid of bad paths\n",
        "\n",
        "Depth-First Search (DFS)\n",
        "* Expand the deepest node first, and create a LIFO queue, where any discovered nodes are at the front of the frontier\n",
        "* look at one node and go all the way down before moving to the next one, repeat with next node\n",
        "* Not complete (infinite depth, loops), not optimal, O(b^m) time complexity (bad if m >> d), O(b* m) space which is biggest win\n",
        "* Use over BFS if space is an issue and search can be altered quicktly, wrong solutions quickly discarded\n",
        "\n",
        "Depth limited search\n",
        "* DFS with a depth limit l, set beforehand. if l is at a depth less than the goal node then it is incomplete and not found, if its greater than d its inefficient and not optimal\n",
        "* Time complextity of O(b^l), space complexity of O(b * l)\n",
        "\n",
        "Iterative Deepening Search \n",
        "* Use depth first search at a depth limit set to l in each iteration, then increase it by 1, repeat\n",
        "* Makes the algorithm complete and optimal, because we always find the solution at a depth of d, the current maximum depth node\n",
        "* Time complexity is O(b^d), space is O(b * d), but now it's complete and optimal\n",
        "\n",
        "Algorithm Summary:\n",
        "BFS: Complete, Optimal, b^d time, b^d space\n",
        "DFS: Not Complete, Not Optimal, b^m time, b*m space\n",
        "Depth-limited: Not Complete, Not Optimal, b^m time, b*l space\n",
        "Iterative Deepening: Complete, Optimal, b^d time, b*d space\n",
        "\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",
        "\"atomic representations\": \"states of the world in their entirety, no interal structures are visible\",\n",
        "\"unknown environment\": \"no additional information available to the agent besides their current state\",\n",
        "\"open-loop\": \"once a path is known the agent can ignore the percepts and execute the actions, breaks the agent-environment loop\",\n",
        "\"closed-loop\": \"monitors the percepts while executing the actions, if there's a chance a mistake is made\",\n",
        "\"model\": \"a mathematical description of the problem state, not the real world environment\",\n",
        "\"abstraction\": \"when we simplify a representation so it has the appropriate amount of detail\",\n",
        "\"standardized problem\": \"expresses problem-solving methods, a benchmark for algorithm research\",\n",
        "\"real-world problem\": \"a problem with solutions that are actually used and unique to each environment\",\n",
        "\"absolute movement actions\": \"up, down, left, or right\",\n",
        "\"egocentric actions\": \"movements relative to the agent, turn left, turn right, forward, backward\",\n",
        "\"Traveling salesperson problem\": \"every city on the map has to be visited optimally\",\n",
        "\"search algorithm\": \"looks at a search problem and returns a solution if one exists or a failure\",\n",
        "\"Best first search\": \"expand a node with the minimuum value for some evaluation function f(n)\",\n",
        "\"Completeness\": \"will we find a solution when it exists or correctly report a failure?\",\n",
        "\"Cost optimality\": \"will the solution we find be the lowest path cost?\",\n",
        "\"Time complexity\": \"Big O notation for how long it takes to reach a solution\",\n",
        "\"Space complexity\": \"Big O notation for how much memory is needed to find the solution\",\n",
        "\"Breadth first search\": \"root node expanded followed by all of its successors, and so on\",\n",
        "\"Early goal test\": \"in BFS, can check if a node is a solution when its generated\",\n",
        "\"late goal test\": \"check to check if a node is a solution until its popped off the queue\",\n",
        "\"Depth first search\": \"explores the deepest node in the frontier first\",\n",
        "\"backtracking search\": \"even less memory than DFS, one successor generated at a time, modifies current state instead of creating new ones\",\n",
        "\"depth limited search\": \"DFS but only explore to a maximum depth l, pretend they have no successors\",\n",
        "\"diameter\": \"the distance each node takes to reach any other node, good estimate for depth limited search\",\n",
        "\"Iterative Deepening Search\": \"depth limited by tries all values of L, combines DFS and BFS benefits\",\n",
        "\"bidirectional search\": \"simultaneously looks forwards and backwards from the goal state hoping they meet up\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lvtN3p7ET3Tx",
        "outputId": "b792b72f-c10a-47bd-9923-1953b395005c"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "\n",
              "* Goal formation: the person wants to get to Bucharest, makes this their goal. This goal will limit their movements and actions\n",
              "* Problem formulation: the person creates an abstract model of the environment, in this case a map of Romania with all of the cities and their distances\n",
              "* Search: before actually moving, they simulate the steps to take until a solution is found, will likely have to iterate through a bunch of them\n",
              "* Execution: the agent has created the best path and now goes down it to get to Bucharest\n",
              "* For a fully observable, deterministic, known environment we will have a fixed sequence of actions from the start to goal node\n",
              "* A search problem as the following:\n",
              "* Set of states (state space) that the environment can be\n",
              "* Initial state where the agent starts\n",
              "* Set of 1+ goal states, goal can be defined to be many different things\n",
              "* Actions available to get to the goal, each one is applicable in s\n",
              "* Transition model that describes what an action does\n",
              "* Action cost function that calculates the cost to make some action in a current state\n",
              "* Path is a sequence of actions that gets to our solution, with the optimal solution being the lowest path cost\n",
              "* Can be seen as a graph with directed edges as actions and states as nodes\n",
              "* Have to determine a level of abstraction that is valid so we can arrive at a solution, useful if it is easier than the original problem\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              "\n",
              "* Create a grid world of 2d space where the agents can move side to side and up and down\n",
              "* Vacuum world has the following setup\n",
              "* State: which objects are In each cell, agent and/or dirt\n",
              "* Initial state: any one can be chosen\n",
              "* Actions: suck, move left, or move right\n",
              "* Transition model: suck up dirt, move the agent forward for backward\n",
              "* Goal state: when everything is clean\n",
              "* Action cost: everything is 1\n",
              "* Sliding tile puzzle example:\n",
              "* states: any setup of the 1-8 tiles\n",
              "* Initial state: whichever setup of the tiles we pick to be the start\n",
              "* Actions: can slide up, down, left, right if possible\n",
              "* Transition model: if we move left, the tile in the position to move to the left actually goes there\n",
              "* Goal state: when the numbers are in order\n",
              "* Action cost: everything is 1\n",
              "* Touring problems are sets of places that have to be visited\n",
              "* VLSI layout optimal positioning is important with cell layouts and channel routings\n",
              "* Robot navigation, automatic assembly sequencing of complex objects, protein design all search problems\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "\n",
              "* Representing search state space graphs as search trees, with the root as the initial point and each node in the tree corresponding to a search tree, edges are the actions to get tho that state\n",
              "* State space is the set of states in the world and actions that allow transitions, whereas the tree just describes paths to get to these states\n",
              "* Expand a node and get its children (or successor) nodes, previous node becomes the parent\n",
              "* Frontier for prioritizing what to look at next, call a node reached if its been expanded\n",
              "* A node in the tree has a state corresponding to it, a parent node, an action that got it there, and a path cost to get there from the initial state\n",
              "* Types of queues we consider: priority queue (minimum cost popped off first), FIFO (first in first out) queue, LIFO (last in first out, or a stack) queue\n",
              "* Trees have repeated states, or a cycle, redundant paths\n",
              "* If we don’t remember the past we’ll run into the same states over and over\n",
              "* Graph search keep track of the previous states and checks for redundant paths, although not always necessary/important\n",
              "* More memory but less redundant paths\n",
              "* We can check for cycles in tree search but redundancy hard to look for\n",
              "* Search must be systematic in some way in order to be complete\n",
              "* Depth is the number of actions to get to the optimal solution, or depth of the tree, m is the maximum number of actions in any path, not necessarily the optimal path, and b is the branching factor that estimates the number of successors for each node to look into\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "* FIFO queue faster than priority queue in BFS\n",
              "* BFS cost optimal when all actions have the same cost, complete in both cases\n",
              "* O(b^d) nodes generated, time and space the same\n",
              "* Memory requirements much bigger worry than execution time, cannot be solved for except in smallest instances\n",
              "* Djikstras/Uniform cost search evaluates the path cost to the current node, UCS has a goal state\n",
              "* Can be inefficient if explores large area with lose costs away from the goal node, never gets caught in single infinite path\n",
              "* DFS backs up when a goal isn’t found recursively, not cost toptimal\n",
              "* Efficient and complete in finite state spaces, can hit loops\n",
              "* Much better for memory, no reached table needed at all, small frontier\n",
              "* O(bm) complexity, b is branching factor and m is max depth of the tree\n",
              "* For backtracking to work we ned a way of undoing our modifications to the state\n",
              "* If we pick a bad L in depth limited search we are going to be inefficient\n",
              "* Iterative deepening optimal for when all actions have the same cost, O(b^d) when a solution exists and O(b^m) when it doesn’t \n",
              "* Iterative deepening generally preferred when search state space is larger than can fit in memory and the depth is unknown\n",
              "* Bidirectional has two frontiers and two tables of reach states, need to be able to reason backwards\n",
              "* Pass in 2 versions of the program and evaluation function for forward and reverse direction\n",
              "* When the first solution is found, it is guaranteed to be optimal if the evaluation function is the path cos\n",
              "* Bidirectional is complete if b is finite and both directions are breadth first or uniform cost\n",
              "* Optimal cost when all action costs are identical and both directions are breadth first or uniform cost\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "Reflex agent vs. Problem Solving Agent\n",
              "* Reflex agent ignores the past percept histroay and only makes an action based on the current percept\n",
              "* Problem Solving Agents plan ahead and perform a search to reach the solution state, execute a sequence of actions\n",
              "\n",
              "Task environment effects\n",
              "* If environment is fully oberservable, deterministics, known it is a sequence of fixed actions that won't change\n",
              "* If either partially observerable or nondeterministic the agent must be flexible with the percepts it receives before making a decision, branching strategy\n",
              "\n",
              "Search Problem components:\n",
              "1. States: a set S of possible states, with an initial state (1a) si that exists in S\n",
              "2. Actions: a set A of all possible actions that can be executed in s and are applicable\n",
              "3. Transition Model: the set of all states and all actions that exist, and their resulting successor states, denotes as s_r. The state space is comprised of the initial state and all successors\n",
              "4. Path Cost function: the performance measure that we are using to calculate the step cost, assuming its at least 0. The cost it takes from state x to state y using an action a.\n",
              "5. Goal state: The goals, s is a goal state if Goal(s) is true, can also be implicit.\n",
              "\n",
              "Formulating a Search Problem - how this is done affects the search space and the speed of search\n",
              "* Decide which properties matter versus others and how to represent each state in the environment\n",
              "* Decide which actions are possible and how we represent them in actions and transition models\n",
              "* Decide which path is next using the cost function\n",
              "\n",
              "Selecting a state space:\n",
              "* State space must be abstracted from the real world since it is very complex. State generally is a set of real-world staates\n",
              "* Action is a class of cominations of real-world equivalent actions\n",
              "* both of these are abstractions, so they should in theory be easier to solve than the real-world problem.\n",
              "\n",
              "State space terminology:\n",
              "* State space - set of all states reachable by any sequence of actions, can expand very quickly depending on how it was constructed\n",
              "* Path - how to get from one state to another state, and what actions led you there\n",
              "* Solution - a complete path from the initial state to the goal state\n",
              "* Search Tree - way to representing the paths with the initial state at the root, checks redundant nodes\n",
              "* Frontier - queue of what is to be explored next, available actions we can look at next\n",
              "* Optimal solution - optimal path from start to goal state with no possible lower cost of getting there\n",
              "\n",
              "Tree Search:\n",
              "* Go through every possible path from the initial state in some order, with the root as the initial state and all other states as leaves\n",
              "* Each path to the same node is distinct, so we may be checking for redundant paths\n",
              "* This failure to check the states can make a linear search problem become exponential\n",
              "\n",
              "State vs. Node: States are representations of physical configurations (like the game board itself), whereas nodes are the data structure of the part of a search tree, including its parent, children, costs, etc.\n",
              "\n",
              "Graph Search:\n",
              "* Attempting to improve upon tree search by storing whether or not a node has been visited before adding it to the frontier\n",
              "* Memory cost is greater than that of tree search but can make the search linear which is ideal\n",
              "\n",
              "Uninformed Search strategy ranks all nodes as equally favorable to explore, whereas an informed search ranks nodes in some uniform way\n",
              "\n",
              "Criteria for search strategies:\n",
              "* Strategy - how the tree is expeanded (queue, priority, etc.)\n",
              "* Completeness - whether or not a solution can always be found\n",
              "* Optimality - when a solution is found, is it always the lowest cost solution?\n",
              "* Time Complexity - how many nodes are generated in the exploration\n",
              "* Space Complexity - how many nodes are stored in memory simultaneously during exploration\n",
              "* b = maximum branching factor, d = depth of shallowest goal node, m - maximum length of any pace in state space\n",
              "\n",
              "Breadth-First Search (BFS)\n",
              "* Expand the nearest node first, and create a FIFO queue, putting any discovered nodes at the end of the frontier\n",
              "* look at each layer individually before moving to the next one, repeat in the next layer\n",
              "* Complete if b is finite, optimal if cost = 1 per step (although generally no), O(b^d) time complexity, O(b^d) space complexity to store all nodes\n",
              "* Very bad in situations with exponential complexity \n",
              "* use over DFS if infinite paths are possible, some solutions are short and you can get rid of bad paths\n",
              "\n",
              "Depth-First Search (DFS)\n",
              "* Expand the deepest node first, and create a LIFO queue, where any discovered nodes are at the front of the frontier\n",
              "* look at one node and go all the way down before moving to the next one, repeat with next node\n",
              "* Not complete (infinite depth, loops), not optimal, O(b^m) time complexity (bad if m >> d), O(b* m) space which is biggest win\n",
              "* Use over BFS if space is an issue and search can be altered quicktly, wrong solutions quickly discarded\n",
              "\n",
              "Depth limited search\n",
              "* DFS with a depth limit l, set beforehand. if l is at a depth less than the goal node then it is incomplete and not found, if its greater than d its inefficient and not optimal\n",
              "* Time complextity of O(b^l), space complexity of O(b * l)\n",
              "\n",
              "Iterative Deepening Search \n",
              "* Use depth first search at a depth limit set to l in each iteration, then increase it by 1, repeat\n",
              "* Makes the algorithm complete and optimal, because we always find the solution at a depth of d, the current maximum depth node\n",
              "* Time complexity is O(b^d), space is O(b * d), but now it's complete and optimal\n",
              "\n",
              "Algorithm Summary:\n",
              "BFS: Complete, Optimal, b^d time, b^d space\n",
              "DFS: Not Complete, Not Optimal, b^m time, b*m space\n",
              "Depth-limited: Not Complete, Not Optimal, b^m time, b*l space\n",
              "Iterative Deepening: Complete, Optimal, b^d time, b*d space\n",
              "\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **Atomic representations** - states of the world in their entirety, no interal structures are visible\n",
              "* **Unknown environment** - no additional information available to the agent besides their current state\n",
              "* **Open-loop** - once a path is known the agent can ignore the percepts and execute the actions, breaks the agent-environment loop\n",
              "* **Closed-loop** - monitors the percepts while executing the actions, if there's a chance a mistake is made\n",
              "* **Model** - a mathematical description of the problem state, not the real world environment\n",
              "* **Abstraction** - when we simplify a representation so it has the appropriate amount of detail\n",
              "* **Standardized problem** - expresses problem-solving methods, a benchmark for algorithm research\n",
              "* **Real-world problem** - a problem with solutions that are actually used and unique to each environment\n",
              "* **Absolute movement actions** - up, down, left, or right\n",
              "* **Egocentric actions** - movements relative to the agent, turn left, turn right, forward, backward\n",
              "* **Traveling salesperson problem** - every city on the map has to be visited optimally\n",
              "* **Search algorithm** - looks at a search problem and returns a solution if one exists or a failure\n",
              "* **Best first search** - expand a node with the minimuum value for some evaluation function f(n)\n",
              "* **Completeness** - will we find a solution when it exists or correctly report a failure?\n",
              "* **Cost optimality** - will the solution we find be the lowest path cost?\n",
              "* **Time complexity** - Big O notation for how long it takes to reach a solution\n",
              "* **Space complexity** - Big O notation for how much memory is needed to find the solution\n",
              "* **Breadth first search** - root node expanded followed by all of its successors, and so on\n",
              "* **Early goal test** - in BFS, can check if a node is a solution when its generated\n",
              "* **Late goal test** - check to check if a node is a solution until its popped off the queue\n",
              "* **Depth first search** - explores the deepest node in the frontier first\n",
              "* **Backtracking search** - even less memory than DFS, one successor generated at a time, modifies current state instead of creating new ones\n",
              "* **Depth limited search** - DFS but only explore to a maximum depth l, pretend they have no successors\n",
              "* **Diameter** - the distance each node takes to reach any other node, good estimate for depth limited search\n",
              "* **Iterative deepening search** - depth limited by tries all values of L, combines DFS and BFS benefits\n",
              "* **Bidirectional search** - simultaneously looks forwards and backwards from the goal state hoping they meet up\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": null,
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"\n",
        "* Greedy best first search is not cost optimal, complete in finite spaces but not infinite\n",
        "* Worst case time and complexity is O(V), with good heuristics can be reduced to O(bm)\n",
        "* A star search has estimated cost of the best path to the goal as the cost so far and the heuristic to get to the goal state\n",
        "* A* is complete, cost optimal depends on whether or not the heuristic is admissible\n",
        "* Heuristic is consistent if it satisfies  a triangle inequality, heuristic less than the cost of a move and that next heuristic\n",
        "* Every consistent heuristic is admissible (so cost-optimal), but not the other way around\n",
        "* Inconsistent heuristics never have to re-add a state to the frontier\n",
        "* With an inadmissible heuristic A* may or may not be cost optimal\n",
        "* Contours in the state space illustrate the search process\n",
        "* A* expands all nodes reached form the initial state where f(n) < C*, surely expanded nodes\n",
        "* Optimally efficient with consistent heuristic since it explores all nodes surely\n",
        "* Prunes away tree nodes not involved in a solution\n",
        "* Number of nodes to expand can be exponential in length of the solution\n",
        "* Main issue with A* is memory concerns\n",
        "* Can seep reference counts for number of times a state has been reached\n",
        "* If a current node exceeds f_limit in RBFS, it backs up to the next path with the backed-up value\n",
        "* RBFS more efficient than IDA* slightly, but node regeneration still a problem\n",
        "* RBFS is optimal with admissible heuristic, space complexity linear in depth of optimal solution\n",
        "* IDA* and RBFS use too little memory\n",
        "* SMA* only regenerates subtree when all other paths are worse than the one its forgotten\n",
        "* Expands the newest best leaf and deletes oldest worst leaf in case of ties\n",
        "* Complete if there is a reachable solution, optimal if optimal solution is reachable otherwise returns best reachable ones\n",
        "* Useful on easy problems, struggles on more difficult ones, thrashes between candidates\n",
        "* In bidirectional heuristic search, need to look at pairs of nodes to be expanded, heuristics of forward and backward functions\n",
        "* Sometimes more efficient than unidirectional search, sometimes not\n",
        "* If we have a good enough heuristic, A* generally the best choice\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\"\n",
        "* For 8 tile puzzle, can use number of misplaces tiles or Manhattan distance as a heuristic\n",
        "* Better way may be to reduce effective depth by constant compared to the true depth\n",
        "* If one heuristic is always better than another, we say it dominates it, h2 dominates h1, h2 >= h1\n",
        "* A relaxed problem can be a good heuristic as well if we let some of the rules be ignored\n",
        "* Cost of the optimal solution to this relaxed problem is admissible for the original problem\n",
        "* If we have several heuristics, pick whichever one is more accurate on that exact node\n",
        "* Admissible heuristics can also be derived from solution costs of subproblems of a particular problem\n",
        "* Pattern databases store the solution costs for these subproblem instances \n",
        "* Sum of two costs is still a lower bound on the cost of solving the entire problem so its a disjoint pattern database\n",
        "* Precomputation of optimal path costs allows faster finding of optimal solutions\n",
        "* Alternatively choose a few landmark points then compute the optimal path cost from one to another\n",
        "* Will either be optimal if it goes through all landmarks or overestimate the cost, not admissible\n",
        "* Can also add shortcuts that cut though with artificial edges\n",
        "* Differential heuristics have subtraction in them, can be efficient and admissible\n",
        "* Spread the landmarks out to be more efficient \n",
        "* Metalevel learning algorithm learns from missteps to avoid exploring non promising subtrees in the future\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "From search, we have our root node = start node, expanded nodes, frontier of nodes to explore. We have to choose a leaf node from frontier to expand depending on the search stratetgy of the algorithm.\n",
        "\n",
        "Uniform Cost Search\n",
        "* a tree search algorithm (checks redundant paths) used for traversing weighed trees, structures, or graphs\n",
        "* Basically Djistra's algorithm but with a goal state\n",
        "* previously all of our search algorithms had a step cost of one, varying that here. g(N) previouslt was the depth of the search tree\n",
        "* g(N): path cost function, assigning some unique costs to each step in a path\n",
        "* C(i, j)- cost of going from node i to node j\n",
        "* Going from node 0 to node 2 - g(N2) = C(0, 1) + C(1, 2)\n",
        "* extends node with the lowest path cost ordered by g(N) in the frontier, similar to BFS\n",
        "* Tests whether or not a node is the goal state when it is popped off the queue for expansion, NOT when added to the frontier\n",
        "* A node is updated on the frontier if a better path to the same point is found\n",
        "* BFS explores equally in all directions with the FIFO queue, smooth contour search\n",
        "* UCS prioritizes which paths to explore, favors lower path costs and gives a priority queue, cost contour but still optimal\n",
        "* Can expand the wrong way away form our goal state, thus we want a node expansion based on estimate with distance to the goal\n",
        "\n",
        "Best first search\n",
        "* Node that is next for expansion selected based on an evaluation function f(n) that is the distance to the goal esimation\n",
        "* Sort the frontier by f(n), leads to greedy search and A* search.\n",
        "\n",
        "Heuristics:\n",
        "* An educated guess that limits the search for solutions in domains that are difficult to understand.\n",
        "* Useful but not necessarily corret, algorithsm provide heuristic knowledge to solve a problem\n",
        "* h(n) takes the current state n and returns an estaimte of the distance to the goal state, straight line distances are useful and simple\n",
        "\n",
        "Admissiblility:\n",
        "* A heuristic is admissible if it is optimistic and never overestimates the cost to reach the goal node\n",
        "* for all nodes n in a system, h(n) <= h*(n) where h*(n) is the true cost, and h(n) >= 0 \n",
        "* inadmissible heuristics violate optimality, good plans trapped on frontier\n",
        "* admissible heuristics slow down bad ideas, never outweigh good paths\n",
        "* a problem with fewer restrictions on the actions is called a relaxed problem\n",
        "* cost of optimal solution to a relaxed problem is an admissible heuristic for the original one\n",
        "* h(n) is the cost of an exact solution to a relaxed problem, allow some of the rules to be broken\n",
        "\n",
        "Dominance:\n",
        "* if h2(n) >= h1(n) for all nodes n, and both are admissible, then h2 dominates h1\n",
        "* h2 is therefore optimistic and more accurate than h1, so its better to use as a heuristic\n",
        "* h*(n) is the oracle heuristic, the true distance, this and the teleporting heuristic are both admissible\n",
        "* h*(n) dominates all other heuristics and h teleport is dominated by all other heuristics\n",
        "\n",
        "Greedy best-first search: set f(n) = h(n)\n",
        "* only expand the node that is estimated to be the closest to the goal and completely ignore g(n), the cost to get to that node\n",
        "* could be a straight line heuristic (L2 distance), manhatten distance in the grid world\n",
        "* Not optimal, can find shorter optimal paths\n",
        "* Not complete, can get stuck in loops if the heuristics are set a certain way\n",
        "\n",
        "A* search - f(n) = g(n) + h(n)\n",
        "* avoid extending paths that are already expensive while also expanding the most promising first, implement in frontier priority queue by increasing f(n)\n",
        "* g(n) is the actual cost so far to reach the current node\n",
        "* h(n) is the estimated cost to get from the current node to the goal\n",
        "* f(n) is the total cost of the path through n to the goal node\n",
        "* if h(n) is an admissible heuristic, this is optimal with tree search\n",
        "* 8 puzzle, set our heuristic to be the manhatten distance or the number of out of place tiles, the former gives a better estimate\n",
        "* will be faster in general than UCS\n",
        "* UCS expands equally in all directions, whereas A* will mainly expand towards the goal and hedges to make sure its still optimal\n",
        "* Applications in path finding, motion planning, games, etc.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"informed search strategy\" : \"a search strategy using domain speific hints and goal locations\",\n",
        "\"heuristic functions\": \"estimated cheapest path from a current node to the goal state\",\n",
        "\"Greedy best first search\": \"Best first search that expands only with the lowest h(n) value\",\n",
        "\"straight line distance\": \"a heuristic in path finding that is a straight line to the goal\",\n",
        "\"A* search\": \"Most common informed algorithm, f(n) = g(n) + h(n), path cost + heuristic\",\n",
        "\"Admissibility\": \"a heuristic that never overestimates the cost to reach the goal, optimistic\",\n",
        "\"consistency\": \"a heuristic is consisten if for every known\",\n",
        "\"Monotonic\": \"g costs always increase as you go along a path, cost is always positive\",\n",
        "\"satisficing solutions\": \"if we explore fewer nodes with an inadmissible heuristic and accept suboptimal solutions\",\n",
        "\"Weighted A* search\": \"weight the heuristic value more heavily, f(n) = g(n) + W * h(n)\",\n",
        "\"Bounded suboptimal search\": \"look for solutions guarenteed to be within a factor W of the optimal cost\",\n",
        "\"Boiunded cost search\": \"look for solutions with cost < come C\",\n",
        "\"Unbounded cost search\": \"accept any solution of any cost as long as we find it quickly\",\n",
        "\"Speedy search\": \"version of best first search that estimates the number of actions to reach a goal\",\n",
        "\"Beam search\": \"limits the size of the frontier, keep best socres and discard the others\",\n",
        "\"Iterative Deepening A* search\": \"cutoff is the g + h cost, smallest fcost in previous iteration is the cutoff value at each depth\",\n",
        "\"Recursive best-first search\": \"Like a recursive DFS, but uses f_limit to keep track of the f-value of best alternative path\",\n",
        "\"Simplified memory bounded A*\": \"proceeds like A* expanding best leaf until memory is full, drops worst leaf\",\n",
        "\"front to end search\": \"heuristic that estimates the distance to the goal and another that meausures distance to start\",\n",
        "\"front to front\": \"estimates the distance to the other frontier in bidirectional heuristic search\",\n",
        "\"Effective branching factor\": \"quality of a heuristic metric, branching factors that a uniform tree at depth d needs for N-1 nodes\",\n",
        "\"meta-level state space\": \"each state captures internal state of a program searching an ordinary search space\",\n",
        "\"object level state space\": \"each state looking at the ordinary state space itself, map of Romania e.g.\"\n",
        "}\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "vqtEs0gHs9sO",
        "outputId": "3d85588a-524e-448c-d7b4-f75444050249"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "\n",
              "* Greedy best first search is not cost optimal, complete in finite spaces but not infinite\n",
              "* Worst case time and complexity is O(V), with good heuristics can be reduced to O(bm)\n",
              "* A star search has estimated cost of the best path to the goal as the cost so far and the heuristic to get to the goal state\n",
              "* A* is complete, cost optimal depends on whether or not the heuristic is admissible\n",
              "* Heuristic is consistent if it satisfies  a triangle inequality, heuristic less than the cost of a move and that next heuristic\n",
              "* Every consistent heuristic is admissible (so cost-optimal), but not the other way around\n",
              "* Inconsistent heuristics never have to re-add a state to the frontier\n",
              "* With an inadmissible heuristic A* may or may not be cost optimal\n",
              "* Contours in the state space illustrate the search process\n",
              "* A* expands all nodes reached form the initial state where f(n) < C*, surely expanded nodes\n",
              "* Optimally efficient with consistent heuristic since it explores all nodes surely\n",
              "* Prunes away tree nodes not involved in a solution\n",
              "* Number of nodes to expand can be exponential in length of the solution\n",
              "* Main issue with A* is memory concerns\n",
              "* Can seep reference counts for number of times a state has been reached\n",
              "* If a current node exceeds f_limit in RBFS, it backs up to the next path with the backed-up value\n",
              "* RBFS more efficient than IDA* slightly, but node regeneration still a problem\n",
              "* RBFS is optimal with admissible heuristic, space complexity linear in depth of optimal solution\n",
              "* IDA* and RBFS use too little memory\n",
              "* SMA* only regenerates subtree when all other paths are worse than the one its forgotten\n",
              "* Expands the newest best leaf and deletes oldest worst leaf in case of ties\n",
              "* Complete if there is a reachable solution, optimal if optimal solution is reachable otherwise returns best reachable ones\n",
              "* Useful on easy problems, struggles on more difficult ones, thrashes between candidates\n",
              "* In bidirectional heuristic search, need to look at pairs of nodes to be expanded, heuristics of forward and backward functions\n",
              "* Sometimes more efficient than unidirectional search, sometimes not\n",
              "* If we have a good enough heuristic, A* generally the best choice\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "\n",
              "* For 8 tile puzzle, can use number of misplaces tiles or Manhattan distance as a heuristic\n",
              "* Better way may be to reduce effective depth by constant compared to the true depth\n",
              "* If one heuristic is always better than another, we say it dominates it, h2 dominates h1, h2 >= h1\n",
              "* A relaxed problem can be a good heuristic as well if we let some of the rules be ignored\n",
              "* Cost of the optimal solution to this relaxed problem is admissible for the original problem\n",
              "* If we have several heuristics, pick whichever one is more accurate on that exact node\n",
              "* Admissible heuristics can also be derived from solution costs of subproblems of a particular problem\n",
              "* Pattern databases store the solution costs for these subproblem instances \n",
              "* Sum of two costs is still a lower bound on the cost of solving the entire problem so its a disjoint pattern database\n",
              "* Precomputation of optimal path costs allows faster finding of optimal solutions\n",
              "* Alternatively choose a few landmark points then compute the optimal path cost from one to another\n",
              "* Will either be optimal if it goes through all landmarks or overestimate the cost, not admissible\n",
              "* Can also add shortcuts that cut though with artificial edges\n",
              "* Differential heuristics have subtraction in them, can be efficient and admissible\n",
              "* Spread the landmarks out to be more efficient \n",
              "* Metalevel learning algorithm learns from missteps to avoid exploring non promising subtrees in the future\n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              "\n",
              "From search, we have our root node = start node, expanded nodes, frontier of nodes to explore. We have to choose a leaf node from frontier to expand depending on the search stratetgy of the algorithm.\n",
              "\n",
              "Uniform Cost Search\n",
              "* a tree search algorithm (checks redundant paths) used for traversing weighed trees, structures, or graphs\n",
              "* Basically Djistra's algorithm but with a goal state\n",
              "* previously all of our search algorithms had a step cost of one, varying that here. g(N) previouslt was the depth of the search tree\n",
              "* g(N): path cost function, assigning some unique costs to each step in a path\n",
              "* C(i, j)- cost of going from node i to node j\n",
              "* Going from node 0 to node 2 - g(N2) = C(0, 1) + C(1, 2)\n",
              "* extends node with the lowest path cost ordered by g(N) in the frontier, similar to BFS\n",
              "* Tests whether or not a node is the goal state when it is popped off the queue for expansion, NOT when added to the frontier\n",
              "* A node is updated on the frontier if a better path to the same point is found\n",
              "* BFS explores equally in all directions with the FIFO queue, smooth contour search\n",
              "* UCS prioritizes which paths to explore, favors lower path costs and gives a priority queue, cost contour but still optimal\n",
              "* Can expand the wrong way away form our goal state, thus we want a node expansion based on estimate with distance to the goal\n",
              "\n",
              "Best first search\n",
              "* Node that is next for expansion selected based on an evaluation function f(n) that is the distance to the goal esimation\n",
              "* Sort the frontier by f(n), leads to greedy search and A* search.\n",
              "\n",
              "Heuristics:\n",
              "* An educated guess that limits the search for solutions in domains that are difficult to understand.\n",
              "* Useful but not necessarily corret, algorithsm provide heuristic knowledge to solve a problem\n",
              "* h(n) takes the current state n and returns an estaimte of the distance to the goal state, straight line distances are useful and simple\n",
              "\n",
              "Admissiblility:\n",
              "* A heuristic is admissible if it is optimistic and never overestimates the cost to reach the goal node\n",
              "* for all nodes n in a system, h(n) <= h*(n) where h*(n) is the true cost, and h(n) >= 0 \n",
              "* inadmissible heuristics violate optimality, good plans trapped on frontier\n",
              "* admissible heuristics slow down bad ideas, never outweigh good paths\n",
              "* a problem with fewer restrictions on the actions is called a relaxed problem\n",
              "* cost of optimal solution to a relaxed problem is an admissible heuristic for the original one\n",
              "* h(n) is the cost of an exact solution to a relaxed problem, allow some of the rules to be broken\n",
              "\n",
              "Dominance:\n",
              "* if h2(n) >= h1(n) for all nodes n, and both are admissible, then h2 dominates h1\n",
              "* h2 is therefore optimistic and more accurate than h1, so its better to use as a heuristic\n",
              "* h*(n) is the oracle heuristic, the true distance, this and the teleporting heuristic are both admissible\n",
              "* h*(n) dominates all other heuristics and h teleport is dominated by all other heuristics\n",
              "\n",
              "Greedy best-first search: set f(n) = h(n)\n",
              "* only expand the node that is estimated to be the closest to the goal and completely ignore g(n), the cost to get to that node\n",
              "* could be a straight line heuristic (L2 distance), manhatten distance in the grid world\n",
              "* Not optimal, can find shorter optimal paths\n",
              "* Not complete, can get stuck in loops if the heuristics are set a certain way\n",
              "\n",
              "A* search - f(n) = g(n) + h(n)\n",
              "* avoid extending paths that are already expensive while also expanding the most promising first, implement in frontier priority queue by increasing f(n)\n",
              "* g(n) is the actual cost so far to reach the current node\n",
              "* h(n) is the estimated cost to get from the current node to the goal\n",
              "* f(n) is the total cost of the path through n to the goal node\n",
              "* if h(n) is an admissible heuristic, this is optimal with tree search\n",
              "* 8 puzzle, set our heuristic to be the manhatten distance or the number of out of place tiles, the former gives a better estimate\n",
              "* will be faster in general than UCS\n",
              "* UCS expands equally in all directions, whereas A* will mainly expand towards the goal and hedges to make sure its still optimal\n",
              "* Applications in path finding, motion planning, games, etc.\n",
              "\n",
              "\n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Informed search strategy** - a search strategy using domain speific hints and goal locations\n",
              "* **Heuristic functions** - estimated cheapest path from a current node to the goal state\n",
              "* **Greedy best first search** - Best first search that expands only with the lowest h(n) value\n",
              "* **Straight line distance** - a heuristic in path finding that is a straight line to the goal\n",
              "* **A* search** - Most common informed algorithm, f(n) = g(n) + h(n), path cost + heuristic\n",
              "* **Admissibility** - a heuristic that never overestimates the cost to reach the goal, optimistic\n",
              "* **Consistency** - a heuristic is consisten if for every known\n",
              "* **Monotonic** - g costs always increase as you go along a path, cost is always positive\n",
              "* **Satisficing solutions** - if we explore fewer nodes with an inadmissible heuristic and accept suboptimal solutions\n",
              "* **Weighted a* search** - weight the heuristic value more heavily, f(n) = g(n) + W * h(n)\n",
              "* **Bounded suboptimal search** - look for solutions guarenteed to be within a factor W of the optimal cost\n",
              "* **Boiunded cost search** - look for solutions with cost < come C\n",
              "* **Unbounded cost search** - accept any solution of any cost as long as we find it quickly\n",
              "* **Speedy search** - version of best first search that estimates the number of actions to reach a goal\n",
              "* **Beam search** - limits the size of the frontier, keep best socres and discard the others\n",
              "* **Iterative deepening a* search** - cutoff is the g + h cost, smallest fcost in previous iteration is the cutoff value at each depth\n",
              "* **Recursive best-first search** - Like a recursive DFS, but uses f_limit to keep track of the f-value of best alternative path\n",
              "* **Simplified memory bounded a*** - proceeds like A* expanding best leaf until memory is full, drops worst leaf\n",
              "* **Front to end search** - heuristic that estimates the distance to the goal and another that meausures distance to start\n",
              "* **Front to front** - estimates the distance to the other frontier in bidirectional heuristic search\n",
              "* **Effective branching factor** - quality of a heuristic metric, branching factors that a uniform tree at depth d needs for N-1 nodes\n",
              "* **Meta-level state space** - each state captures internal state of a program searching an ordinary search space\n",
              "* **Object level state space** - each state looking at the ordinary state space itself, map of Romania e.g.\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": null,
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"\n",
        "* Pruning makes search more efficient by ignoring portions of the tree that don’t affect the result\n",
        "* Actions referred to as moves, positions for states\n",
        "* A game has an initial state (how the game is set up), who’s move it is, the list of legal moves for that person, the result of the move with a transition model that defines the state that results from the move, is-terminal with a terminal test to see whether or not the game is ended, and a utility defined by a utility function that gives values to players in each state or at the terminal state\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\"\n",
        "* Max wants to maximize their own score, min wants to minimize the score that max can achieve\n",
        "* Always assume the other player makes the optimal move in minimax\n",
        "* Recursive algorithm that goes down to the leaves then backs up the minimax values of the tree as the recursion returns\n",
        "* Run the utility on the leaf nodes to get the values to pass back up in recursion\n",
        "* Depth first search, time complexity of O(b^m), space complexity O(bm)\n",
        "* If more than two players, replace single value with vector of values for each utility\n",
        "* Alliances in multiplayer games affect which node is chosen in minimax\n",
        "* In alpha beta pruning, minimax decision is independent of the values of the leaves in some cases, pruned\n",
        "* If a player has a better choice at the same level or any point higher up in the tree, it doesn’t need to explore it, prune it there\n",
        "* Alpha is the value of the best choice we have found so far along the path for MAX, at least alpha\n",
        "* Beta is the value of the best choice we have found so far along the path for MIN, at most beta\n",
        "* Prunes as soon as it is worse than alpha or beta at any state, meaning different directions\n",
        "* If perfect, would only need to look at O(b^m/2) compared to O(b^m) for minimax, doesn’t happen every time but can get decently close\n",
        "* Can use iterative deepening with this search method to improve selection and reduce memory\n",
        "* Repeated states in game search trees recorded in a transposition table that looks at heuristic values of states\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\"\n",
        "* Can cut searches early and apply heuristic evaluation functions to states\n",
        "* Cutoff tests used for deciding when to stop looking at a certain branch of the tree\n",
        "* Can only get an estimate of the expected utility of a state to the player, just like in estimated distances in search trees\n",
        "* Most evaluation functions look at features of the state and weigh them to get some value that it can compare across states, also referred to as a weighted linear function, at each position we say how important a certain feature is and sum them up to get a value (in chess)\n",
        "* This assumes the contribution of each feature is independent of the values of others, not true in many games, need to use nonlinear combinations as well\n",
        "* Tell alpha beta pruning that if some evaluation function is true then stop looking at that branch\n",
        "* Evaluation function should only look at positions with no pending moves (quiescent) that would greatly affect the resulting value\n",
        "* Forward pruning is a type b strategy to save computation time\n",
        "* Use beam search to mitigate this, look only at one string of best moves instead of all of them\n",
        "* PROBcut prunes things that were probably prunable as opposed to provably prunable \n",
        "* Late move reduction says that moves that appear later are less likely to be good moves, reduce the depth that we look at these nodes instead of completely pruning them\n",
        "* If they come back promising we can always extend them and look further\n",
        "* Computer can completely solve some tasks with a policy that maps the best next state from a current state\n",
        "* Does so with retrograde minimax, look at all possible solutions then work backwards\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"\n",
        "* Stochastic games include a random element as well\n",
        "* Game trees in stochastic games need to include chance nodes in addition to MAX and MIN nodes\n",
        "* At best, can pick the highest expected value of a position, or the average of all possible outcomes\n",
        "* Compute the probability of the expected value as the sum of all values weighted by probability over the number of nodes\n",
        "* Evaluation function must return expected values that are the probability of winning, harder to prune\n",
        "* Takes O(b^m * n^m), where n is the number of distinct rolls of a dice and m is the max depth of a tree\n",
        "* If we bound the value of the children, we can get an idea of the average without looking at all of the children\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "* Agent has to make actions but is unsure of which one, so it assigns probabilities\n",
        "* Work to choose which action based on the desirability of their immediate outcomes, assuming an episodic environment\n",
        "* Captured by a utility function and want to maximize the expected utility\n",
        "* Maximum expected utility theory says a rational agent should pick the action that generates the highest expected utility\n",
        "* If an agent acts to maximize this utility function that is correctly calculated, it will achieve the highest possible score performance\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\"\n",
        "* Say that one agent either prefers A over B, indifferent between the two, or prefers or is indifferent between them\n",
        "* A and B could be states of the world, usually some uncertainty in there, think of each set of outcomes as a lottery\n",
        "* Six constants we require for a preference relation to obey\n",
        "* Orderability - given two choices, an agent must prefer one, the other, or equally preferable, cannot avoid making a decision\n",
        "* Transitivity - if an agent prefers A to B and prefers B to C, must prefer A to C\n",
        "* Continuity - if B is between a and c in preference, some probability where the agent is indifferent between getting B and the probability of getting A with probability p and c with 1 - p\n",
        "* Substitutability - if indifferent between A and B, need to be indifferent between more complex options that are the same except B is substituted for A somewhere\n",
        "* Monotonicity - If two lotteries have A and B outcomes and A is preferred, then agent must pick which one gives a higher probability to A\n",
        "* Decomposability - Compound lotteries can be reduced to more basic representations using probability\n",
        "* If these are violated, agent behaves strangely in some way\n",
        "* Existence of a utility function - if preferences are aligned then there’s some function U that gives a higher value to A over B if A is preferred to B, or makes them equal if they are indifferent\n",
        "* Expected utility of a lottery - utility of the lottery is the sum of the probability of the outcome * utility of the outcome\n",
        "* Agent only needs an ordinal utility function, or a ranking of the choices, doesn’t care about what the associated values are\n",
        "\"\"\"\n",
        "chapter16_3 = \"\"\"\n",
        "* Preference elicitation lets the human decide what the utility function should be by presenting a bunch of choices and observing what decisions are made\n",
        "* Normalized utilities use a scare of 0 to 1, with 0 being the worst possible thing and 1 being the best possible outcome\n",
        "* Give the agent the utility scale and say to choose between the utility of an object and the standard lottery, adjust it until the agent is indifferent between the two and you get the expected utility\n",
        "* Can look at tradeoffs and at some point a value is placed on decisions\n",
        "* Use micromorts in insurance, one in a million chance of death\n",
        "* QALY is quality adjusted life year for patients receiving treatment\n",
        "* Generally agents have a monotonic preference for more money\n",
        "* Expected monetary value is each outcome probability multiplied by the associated reward\n",
        "* Risk averse agents prefer a sure thing rather than a game\n",
        "* Risk-seeing agents large risks for monetary gain, usually have some amount of debt\n",
        "* Average an agent will accept instead of a chance event is the certainty equivalent \n",
        "* Difference between the EMV and certainty equivalent is called the insurance premium \n",
        "* Agents with linear curves in wealth relative to current wealth are risk neutral\n",
        "* Optimizers curve is the estimated expected utility of the best choice being too high \n",
        "* Normative theory says how a rational agent should act, describe theory is how actual agents really act, like humans\n",
        "* Certainty effect says people are strongly attached to certain gains\n",
        "* People go with certain probabilities rather than unknowns, ambiguity aversion\n",
        "* The way a decision problem is worded affects it as well, framing effect\n",
        "* People prefer relative utility judgments as well, anchoring effect\n",
        "* Evolutionary psychology investigates these irrationalities further\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Simplest game environment - Multiagent, static (no changes while deliberating), discrete (finite state of percepts/actions), fully observable (can see entire environment, perfect information), strategic (next state determined by current state and action of one agent then the other)\n",
        "\n",
        "Our games - two players alternate moves, zero-sum (one players loss it the others gains), set of moves, well defined win/loss/draw outcome\n",
        "\n",
        "Card games - stochastic, not deterministic, not fully observable\n",
        "\n",
        "Real time strategy - continous instead of discrete, no break between actions\n",
        "\n",
        "Game setup\n",
        "* Two players MAX and MIN, MAX goes first\n",
        "* MAX always tries to maximize their turn, MIN tries to minimize the turn of MAX\n",
        "* take turns until the game is over, winner get award, loser penalty\n",
        "* Initial state (board configuration), successor functions (legal move lists), terminal state, utility function (numerical value to terminal states), search tree to determine next move\n",
        "\n",
        "Making a move\n",
        "* Look at all legal moves (successors) to the current board position\n",
        "* Evaluate each successor board poision, pick the one that leads to the best ne, repeat after your opponent does the same thing\n",
        "\n",
        "Game Trees - represent game problem by a tree, nodes are board positions, edges are the moves that can be made, root is the first position to make a move, leaves are terminal states\n",
        "* Can try to assign evaluation function f to real number scores to current position without how it got there\n",
        "* Can give scores to the output boards depending on how desirable they are\n",
        "* f(n) evaluation function is static features of board alone\n",
        "* f(n) > 0 if MAX is winning, 0 if tied, < 0 if MIN is winning\n",
        "\n",
        "Max & Min\n",
        "* MAX is the perspective we look from, try to maximize their outcome\n",
        "* Min attempts to minimize MAX's outcome\n",
        "* root is level 0, max foes first, MAX has even levels, MIN has odd levels\n",
        "\n",
        "Minimax\n",
        "* make the best move for MAX assuming MIN always makes the best move for them\n",
        "* can recursively compute, the backed up value of node is the optimal value of its children\n",
        "* MAX this means backed up value is the max of its children, MIN is min of its children\n",
        "* until game terminates, start with MAX node, expand a given number of moves, apply evlaution function, calculate backed up values, pick the optimal move, let min respond\n",
        "* minimax value is the best achievable move against a rational opponent\n",
        "* Even if min doesnt play optimally, max plays even better then since it assumes the worst case scenario if they played correctly\n",
        "\n",
        "Alpha-Beta pruning\n",
        "* minimax but keep track of alpha and beta values\n",
        "* alpha is MAX's current lower bound on MAX's outcome, MAX will never allow a move that could lead to a worse move than alpha\n",
        "* beta is MIN's current upper bound on MINs outcome, MIN will never allow a move that could lead to a better move than beta\n",
        "* When evaluating a MAX node, a value is greater than beta, can stop because MIN will never select it\n",
        "* When evaluating a MIN node, a value less than alpha, can stop because MAX will never select it\n",
        "\n",
        "Expectimax - when we have to deal with uncertain outcomes with chance instead of just the opponent\n",
        "* Randomness either through explicitly random, an opponent who acts irradically, or an action that may fail\n",
        "* now instead want to calculate the average-case (expectimax) outcomes instead of the worst case (minimax) outcomes\n",
        "* Compute the average score under optimal play, MAX nodes are the same as before, chance nodes are like MIN but uncertain outcome so we calculate the expected utility\n",
        "* have some model of probabilities for how the opponent will move in a state, could be uniform distribution, complicated computation, chance nodes, traditional adversarial response\n",
        "* in our environments we have all probabilities with chance nodes that specify distribution\n",
        "* Objectivist (frequentist) - average over repeated experiments, assertsion how future iterations will go, new evidence changes the reference class, more in line with inherently random things\n",
        "* Subjectivist (Bayesian) - degrees of belief about unobserved variables exist, learn probabilities from the past experiences and new evidence updates the beliefs. Agent believes certain things based on the state or percepts\n",
        "\n",
        "Probability\n",
        "* Random variable, represents an event with an unknown outcome, probability distribution is an assignment of weights to the outcomes\n",
        "* always have non-negative probabilities, and always have to sum to one. May change as more information is gathered\n",
        "* Expected value of the random variable function is then the average weighed by the probability of the outcomes\n",
        "* can get slow quickly if need to calculate the opponent and then they have to calculate you back, minimax helps solve this a bit\n",
        "\n",
        "Expectiminimax - environment is extra random agent player that moves after each min/max move, results in nodes that compute the appropriate combination of the child values\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"evaluation function\" : \"some measure of who is winning, based on the features of the current state\", \n",
        "\"perfect information\": \"fully obserable environment\",\n",
        "\"zero sum games\": \"what is good for one player is bad for the other, no win win outcomes possible\",\n",
        "\"state space graph\": \"graph where states are vertices, moves are edges, different states can be reached with multiple paths\",\n",
        "\"Game tree\": \"a complete search tree that follows every possible sequence of moves to the terminal state\",\n",
        "\"ply\": \"one move by one of the players, not for both players\",\n",
        "\"minimax\": \"optimal strategy in a search tree given that both sides play optimally\",\n",
        "\"minimax decision\": \"what move is ultimately chosen at the root when we calculate all of the minimax values\",\n",
        "\"alpha-beta pruning\": \"look at values of alpha and beta and prune branches of the tree that won't contribute\",\n",
        "\"Type A strategy\": \"wide but shallow, looks at all moves to a certain depth in search game tree\",\n",
        "\"Type B strategy\": \"deep but narrow, ignore moves that look bad and following promising paths\",\n",
        "\"quiescence search\": \"only look at certain moves that won't greatly swing the evaluation function\",\n",
        "\"horizon effect\": \"when program is facing a bad move from the opponent and it ultimately inevitable but it tries to delay\",\n",
        "\"singular extensions\": \"mitigate horizon effect with clearly better moves than all others in a position even if cut off\",\n",
        "\"forward pruning\": \"prun moves that look bad but may be good ones, could be done in error\",\n",
        "\"expectiminimax\": \"minimax game trees with chance nodes, generalization for deterministic games\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "KUc_LgzDvWf-",
        "outputId": "d482d70c-363d-4b6f-b9b1-3ea50cb657cd"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "\n",
              "* Pruning makes search more efficient by ignoring portions of the tree that don’t affect the result\n",
              "* Actions referred to as moves, positions for states\n",
              "* A game has an initial state (how the game is set up), who’s move it is, the list of legal moves for that person, the result of the move with a transition model that defines the state that results from the move, is-terminal with a terminal test to see whether or not the game is ended, and a utility defined by a utility function that gives values to players in each state or at the terminal state\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "\n",
              "* Max wants to maximize their own score, min wants to minimize the score that max can achieve\n",
              "* Always assume the other player makes the optimal move in minimax\n",
              "* Recursive algorithm that goes down to the leaves then backs up the minimax values of the tree as the recursion returns\n",
              "* Run the utility on the leaf nodes to get the values to pass back up in recursion\n",
              "* Depth first search, time complexity of O(b^m), space complexity O(bm)\n",
              "* If more than two players, replace single value with vector of values for each utility\n",
              "* Alliances in multiplayer games affect which node is chosen in minimax\n",
              "* In alpha beta pruning, minimax decision is independent of the values of the leaves in some cases, pruned\n",
              "* If a player has a better choice at the same level or any point higher up in the tree, it doesn’t need to explore it, prune it there\n",
              "* Alpha is the value of the best choice we have found so far along the path for MAX, at least alpha\n",
              "* Beta is the value of the best choice we have found so far along the path for MIN, at most beta\n",
              "* Prunes as soon as it is worse than alpha or beta at any state, meaning different directions\n",
              "* If perfect, would only need to look at O(b^m/2) compared to O(b^m) for minimax, doesn’t happen every time but can get decently close\n",
              "* Can use iterative deepening with this search method to improve selection and reduce memory\n",
              "* Repeated states in game search trees recorded in a transposition table that looks at heuristic values of states\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "\n",
              "* Can cut searches early and apply heuristic evaluation functions to states\n",
              "* Cutoff tests used for deciding when to stop looking at a certain branch of the tree\n",
              "* Can only get an estimate of the expected utility of a state to the player, just like in estimated distances in search trees\n",
              "* Most evaluation functions look at features of the state and weigh them to get some value that it can compare across states, also referred to as a weighted linear function, at each position we say how important a certain feature is and sum them up to get a value (in chess)\n",
              "* This assumes the contribution of each feature is independent of the values of others, not true in many games, need to use nonlinear combinations as well\n",
              "* Tell alpha beta pruning that if some evaluation function is true then stop looking at that branch\n",
              "* Evaluation function should only look at positions with no pending moves (quiescent) that would greatly affect the resulting value\n",
              "* Forward pruning is a type b strategy to save computation time\n",
              "* Use beam search to mitigate this, look only at one string of best moves instead of all of them\n",
              "* PROBcut prunes things that were probably prunable as opposed to provably prunable \n",
              "* Late move reduction says that moves that appear later are less likely to be good moves, reduce the depth that we look at these nodes instead of completely pruning them\n",
              "* If they come back promising we can always extend them and look further\n",
              "* Computer can completely solve some tasks with a policy that maps the best next state from a current state\n",
              "* Does so with retrograde minimax, look at all possible solutions then work backwards\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "* Stochastic games include a random element as well\n",
              "* Game trees in stochastic games need to include chance nodes in addition to MAX and MIN nodes\n",
              "* At best, can pick the highest expected value of a position, or the average of all possible outcomes\n",
              "* Compute the probability of the expected value as the sum of all values weighted by probability over the number of nodes\n",
              "* Evaluation function must return expected values that are the probability of winning, harder to prune\n",
              "* Takes O(b^m * n^m), where n is the number of distinct rolls of a dice and m is the max depth of a tree\n",
              "* If we bound the value of the children, we can get an idea of the average without looking at all of the children\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "\n",
              "* Agent has to make actions but is unsure of which one, so it assigns probabilities\n",
              "* Work to choose which action based on the desirability of their immediate outcomes, assuming an episodic environment\n",
              "* Captured by a utility function and want to maximize the expected utility\n",
              "* Maximum expected utility theory says a rational agent should pick the action that generates the highest expected utility\n",
              "* If an agent acts to maximize this utility function that is correctly calculated, it will achieve the highest possible score performance\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "\n",
              "* Say that one agent either prefers A over B, indifferent between the two, or prefers or is indifferent between them\n",
              "* A and B could be states of the world, usually some uncertainty in there, think of each set of outcomes as a lottery\n",
              "* Six constants we require for a preference relation to obey\n",
              "* Orderability - given two choices, an agent must prefer one, the other, or equally preferable, cannot avoid making a decision\n",
              "* Transitivity - if an agent prefers A to B and prefers B to C, must prefer A to C\n",
              "* Continuity - if B is between a and c in preference, some probability where the agent is indifferent between getting B and the probability of getting A with probability p and c with 1 - p\n",
              "* Substitutability - if indifferent between A and B, need to be indifferent between more complex options that are the same except B is substituted for A somewhere\n",
              "* Monotonicity - If two lotteries have A and B outcomes and A is preferred, then agent must pick which one gives a higher probability to A\n",
              "* Decomposability - Compound lotteries can be reduced to more basic representations using probability\n",
              "* If these are violated, agent behaves strangely in some way\n",
              "* Existence of a utility function - if preferences are aligned then there’s some function U that gives a higher value to A over B if A is preferred to B, or makes them equal if they are indifferent\n",
              "* Expected utility of a lottery - utility of the lottery is the sum of the probability of the outcome * utility of the outcome\n",
              "* Agent only needs an ordinal utility function, or a ranking of the choices, doesn’t care about what the associated values are\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              "\n",
              "* Preference elicitation lets the human decide what the utility function should be by presenting a bunch of choices and observing what decisions are made\n",
              "* Normalized utilities use a scare of 0 to 1, with 0 being the worst possible thing and 1 being the best possible outcome\n",
              "* Give the agent the utility scale and say to choose between the utility of an object and the standard lottery, adjust it until the agent is indifferent between the two and you get the expected utility\n",
              "* Can look at tradeoffs and at some point a value is placed on decisions\n",
              "* Use micromorts in insurance, one in a million chance of death\n",
              "* QALY is quality adjusted life year for patients receiving treatment\n",
              "* Generally agents have a monotonic preference for more money\n",
              "* Expected monetary value is each outcome probability multiplied by the associated reward\n",
              "* Risk averse agents prefer a sure thing rather than a game\n",
              "* Risk-seeing agents large risks for monetary gain, usually have some amount of debt\n",
              "* Average an agent will accept instead of a chance event is the certainty equivalent \n",
              "* Difference between the EMV and certainty equivalent is called the insurance premium \n",
              "* Agents with linear curves in wealth relative to current wealth are risk neutral\n",
              "* Optimizers curve is the estimated expected utility of the best choice being too high \n",
              "* Normative theory says how a rational agent should act, describe theory is how actual agents really act, like humans\n",
              "* Certainty effect says people are strongly attached to certain gains\n",
              "* People go with certain probabilities rather than unknowns, ambiguity aversion\n",
              "* The way a decision problem is worded affects it as well, framing effect\n",
              "* People prefer relative utility judgments as well, anchoring effect\n",
              "* Evolutionary psychology investigates these irrationalities further\n",
              "\n",
              "\n",
              "## Module 5 Lecture Notes\n",
              "\n",
              "Simplest game environment - Multiagent, static (no changes while deliberating), discrete (finite state of percepts/actions), fully observable (can see entire environment, perfect information), strategic (next state determined by current state and action of one agent then the other)\n",
              "\n",
              "Our games - two players alternate moves, zero-sum (one players loss it the others gains), set of moves, well defined win/loss/draw outcome\n",
              "\n",
              "Card games - stochastic, not deterministic, not fully observable\n",
              "\n",
              "Real time strategy - continous instead of discrete, no break between actions\n",
              "\n",
              "Game setup\n",
              "* Two players MAX and MIN, MAX goes first\n",
              "* MAX always tries to maximize their turn, MIN tries to minimize the turn of MAX\n",
              "* take turns until the game is over, winner get award, loser penalty\n",
              "* Initial state (board configuration), successor functions (legal move lists), terminal state, utility function (numerical value to terminal states), search tree to determine next move\n",
              "\n",
              "Making a move\n",
              "* Look at all legal moves (successors) to the current board position\n",
              "* Evaluate each successor board poision, pick the one that leads to the best ne, repeat after your opponent does the same thing\n",
              "\n",
              "Game Trees - represent game problem by a tree, nodes are board positions, edges are the moves that can be made, root is the first position to make a move, leaves are terminal states\n",
              "* Can try to assign evaluation function f to real number scores to current position without how it got there\n",
              "* Can give scores to the output boards depending on how desirable they are\n",
              "* f(n) evaluation function is static features of board alone\n",
              "* f(n) > 0 if MAX is winning, 0 if tied, < 0 if MIN is winning\n",
              "\n",
              "Max & Min\n",
              "* MAX is the perspective we look from, try to maximize their outcome\n",
              "* Min attempts to minimize MAX's outcome\n",
              "* root is level 0, max foes first, MAX has even levels, MIN has odd levels\n",
              "\n",
              "Minimax\n",
              "* make the best move for MAX assuming MIN always makes the best move for them\n",
              "* can recursively compute, the backed up value of node is the optimal value of its children\n",
              "* MAX this means backed up value is the max of its children, MIN is min of its children\n",
              "* until game terminates, start with MAX node, expand a given number of moves, apply evlaution function, calculate backed up values, pick the optimal move, let min respond\n",
              "* minimax value is the best achievable move against a rational opponent\n",
              "* Even if min doesnt play optimally, max plays even better then since it assumes the worst case scenario if they played correctly\n",
              "\n",
              "Alpha-Beta pruning\n",
              "* minimax but keep track of alpha and beta values\n",
              "* alpha is MAX's current lower bound on MAX's outcome, MAX will never allow a move that could lead to a worse move than alpha\n",
              "* beta is MIN's current upper bound on MINs outcome, MIN will never allow a move that could lead to a better move than beta\n",
              "* When evaluating a MAX node, a value is greater than beta, can stop because MIN will never select it\n",
              "* When evaluating a MIN node, a value less than alpha, can stop because MAX will never select it\n",
              "\n",
              "Expectimax - when we have to deal with uncertain outcomes with chance instead of just the opponent\n",
              "* Randomness either through explicitly random, an opponent who acts irradically, or an action that may fail\n",
              "* now instead want to calculate the average-case (expectimax) outcomes instead of the worst case (minimax) outcomes\n",
              "* Compute the average score under optimal play, MAX nodes are the same as before, chance nodes are like MIN but uncertain outcome so we calculate the expected utility\n",
              "* have some model of probabilities for how the opponent will move in a state, could be uniform distribution, complicated computation, chance nodes, traditional adversarial response\n",
              "* in our environments we have all probabilities with chance nodes that specify distribution\n",
              "* Objectivist (frequentist) - average over repeated experiments, assertsion how future iterations will go, new evidence changes the reference class, more in line with inherently random things\n",
              "* Subjectivist (Bayesian) - degrees of belief about unobserved variables exist, learn probabilities from the past experiences and new evidence updates the beliefs. Agent believes certain things based on the state or percepts\n",
              "\n",
              "Probability\n",
              "* Random variable, represents an event with an unknown outcome, probability distribution is an assignment of weights to the outcomes\n",
              "* always have non-negative probabilities, and always have to sum to one. May change as more information is gathered\n",
              "* Expected value of the random variable function is then the average weighed by the probability of the outcomes\n",
              "* can get slow quickly if need to calculate the opponent and then they have to calculate you back, minimax helps solve this a bit\n",
              "\n",
              "Expectiminimax - environment is extra random agent player that moves after each min/max move, results in nodes that compute the appropriate combination of the child values\n",
              "\n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Evaluation function** - some measure of who is winning, based on the features of the current state\n",
              "* **Perfect information** - fully obserable environment\n",
              "* **Zero sum games** - what is good for one player is bad for the other, no win win outcomes possible\n",
              "* **State space graph** - graph where states are vertices, moves are edges, different states can be reached with multiple paths\n",
              "* **Game tree** - a complete search tree that follows every possible sequence of moves to the terminal state\n",
              "* **Ply** - one move by one of the players, not for both players\n",
              "* **Minimax** - optimal strategy in a search tree given that both sides play optimally\n",
              "* **Minimax decision** - what move is ultimately chosen at the root when we calculate all of the minimax values\n",
              "* **Alpha-beta pruning** - look at values of alpha and beta and prune branches of the tree that won't contribute\n",
              "* **Type a strategy** - wide but shallow, looks at all moves to a certain depth in search game tree\n",
              "* **Type b strategy** - deep but narrow, ignore moves that look bad and following promising paths\n",
              "* **Quiescence search** - only look at certain moves that won't greatly swing the evaluation function\n",
              "* **Horizon effect** - when program is facing a bad move from the opponent and it ultimately inevitable but it tries to delay\n",
              "* **Singular extensions** - mitigate horizon effect with clearly better moves than all others in a position even if cut off\n",
              "* **Forward pruning** - prun moves that look bad but may be good ones, could be done in error\n",
              "* **Expectiminimax** - minimax game trees with chance nodes, generalization for deterministic games\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": null,
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "* Constraint satisfaction consists of a set of variables X, a set of domains D for each variable, and a set of constraints C that allow a combination of values\n",
        "* Each domain allows a set of values for a given variable, relations define the constraints for each pair\n",
        "* Solution to a CSP has to be complete and consistent\n",
        "* Australia map coloring, have a set of variables X to be regions, domains are colors, constraints are no touching countries can be the same color\n",
        "* Constraint graphs help to visualize these relationships\n",
        "* Check on each assignment whether it is a goal or not\n",
        "* Discrete, finite domains make up the easiest CSPs\n",
        "* Discrete domain can still be infinite (numbers, strings)\n",
        "* Special solutions exists for linear constraints on integers, where each variable appears in linear form, but not for nonlinear constraints, undecidable\n",
        "* Continuous domains are common in the real world as well, linear programming, Hubble space telescope\n",
        "* Binary CSP only has unary and binary constraints, can be represented as a graph\n",
        "* Can convert an n-ary CSP to binary using dual graphs, creating a new graph for one variable for each constraint in the original graph and one binary constraint for each pair of constraints\n",
        "* Can apply costs to the assignments and turn them into constraint optimization problems\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"\n",
        "* Xi is arc consistent to Xj if every value in domain Di there’s some variable in Dj that satisfies the binary constraint on the arc.\n",
        "* Graph is arc consistent if every variable is arc consistent with each other\n",
        "* AC-3 maintains a queue of arcs to look through\n",
        "* Initially all arcs in the CSP, pops one off, makes it arc-consistent Xi with Xj. \n",
        "* If the domain is the same we move on, if the domain is smaller we put all arcs Xk Xi back in for all neighbors\n",
        "* If a domain goes to nothing, we have a failure and we need to return false\n",
        "* O(d^2) time to check an arc, and O(cd^3) total worse case where c is the number of arcs and d is the number of times an arc can be inserted into a queue\n",
        "* Path consistent Xi Xj with a third variable Xm if for every assignment consistent with Xi Xj there’s an assignment with Xm such that Xi Xm and Xm Xj are satisfied\n",
        "* A CSP is k-consistent if for any set of k - 1 variables with any consistent assignments, a consistent value can always be assigned to any 4th variable\n",
        "* CSP is strongly k-consistent if it is k consistent, k - 1 consistent, k - 2 consistent, … down to 1 consistent\n",
        "* Can’t represent all domains sometimes, so we do bounds propagation, set a min and max bound on the domains\n",
        "* Bounds consistent if for each variable X for lower and upper bounds there’s a value of y that satisfies the constrains between x and y\n",
        "* Sudoku is very popular CSP\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "* Often still have to perform a search after constraining with backtracking\n",
        "* CSPs are commutative which is key, doesn’t matter which order we assign things, so only need to look t one variable in each node \n",
        "* Number of leaves in depth limited search is now d^n\n",
        "* Backtracking can be improved with domain independent heuristics that take advantage of factored representation\n",
        "* Which variable should be assigned next, select unassigned variable default is just pick them in order, or randomly\n",
        "* MRV heuristic is most constrained variable, most likely to fail soonest \n",
        "* Degree heuristic reduced branching factor by selected variable involved in larger number of constraints on other variables, if the MRV is tied\n",
        "* Least constraining value good for which order to examine, prefers value that rules out the fewest choices for the neighbors\n",
        "* Forward checking - whenever a variable is assigned, forward checking establishes arc consistent for it\n",
        "* Get better results if we combine MRV with forward checking\n",
        "* MAC (maintaining arc consistency) detects consistencies early.\n",
        "* Assign a variable Xi a value, inference procedure calls AC-3 starting with the arcs Xj Xi for each unassigned neighbors of Xi, more powerful than forward checking\n",
        "* Forward checking doesn’t recursively propagate constraints like MAC\n",
        "* Keep track of assignments that conflict with some value, called the conflict set, then backup to the most recent assignment in the conflict set\n",
        "* Backjumping algorithm that uses conflict sets is called conflict-directs backjumping\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\"\n",
        "* Local search algorithms good in solving CSPs, N-Queens for example\n",
        "* Min conflicts heuristic is selecting a value that gives the minimum number of conflicts with other variable\n",
        "* Tabu search keeps a list of recently visited states handy and forbid the return to those states\n",
        "* Constraint weighing weights the variable/value pairs different so concentrate on the important bits of search\n",
        "* Local search all can be used in online setting when the problems change\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "* Decompose into simpler problems, if we have independent subproblems can solve those first\n",
        "* Independence found by identifying connected components of the constraint graph\n",
        "* Constraint graphs are trees when any two variables are connected by only one path, then can be solved in linear time with the number of variables\n",
        "* Directional arc consistency if we look at arc consistency in one direction\n",
        "* Topological sort used when we pick a variable to be the root of the tree and order the variables outside of that\n",
        "* Don’t need to backtrack then, just move through the variable orderings\n",
        "* Cutset conditioning algorithm: choose a subset of the variables so that the graph is a tree when S is removed, S is a cycle cutest\n",
        "* For each assignment to variables in S that satisfies all constraints, remove from the domains of remaining variables any inconsistent values, and if it has a solution return it with S assignment\n",
        "* Tree decomposition transforms the graph itnto a tree where each node consists of a set of variables\n",
        "* Decomposition must have every variable in at least one of the tree nodes, if two variables are connected in the original problem they must be in at least one of trees, and if a variable appears in two nodes in the tree it must be in every node along the path connecting the nodes\n",
        "* Tree width of the decomposition is one less than the size of the largest node\n",
        "* Tree width of graph is minimum width of tree decompositions\n",
        "* CPSs with bounded tree widths are solvable in polynomial time\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\"\n",
        "Purpose of search\n",
        "* Assume in our world we habe a single agent, deterministic actions, fully obseravle, discrete actions\n",
        "* planning involves creating a sequence of actions to get to the goal, with costs and depths, heuristics\n",
        "* identify assignments to variables, do not care how we reach the goal\n",
        "\n",
        "Constraint Satisfaction Problems\n",
        "* want to represent constraints that solutions have to satisfy in some language, make them general purpose search algorithms \n",
        "* if they are general purpose then we can specify a problem in some language and the algorithm still works\n",
        "* in a CSP we have finite set of variables X1, X2, ..., Xn, nonempty domain of values for each variable D1, D2, .. where Di = {v1, ..., vk}, finite set of constraints C1, ... Cm\n",
        "* a constraint limits the values that the varibales can take according to some rules, and a state is defined as the assignemtn of these values to the variables.\n",
        "* An assignment is consistent if it doesn't violate the constraints, sudoku, color mapping, scheduling problems\n",
        "* complete assignment is achieved when every variable is assigned a value\n",
        "* a solution has to be both complete and consistent, solutions. found using these general purpose algorithms, maximizes some objective function\n",
        "\n",
        "Map coloring example\n",
        "* have a map and can assign each country or area as a variable, domains initially are all possible colors, constraints are touching regions have to have different colors\n",
        "* how many colors are required to create a complete and consistent assignment (solution)\n",
        "\n",
        "Advantages\n",
        "* create a generic goal, successor function, and heuristics, and clean specifications can be created from them\n",
        "* the CSP can check when the variables violate a constraint with forward checking\n",
        "* prune off branches where constraints are violates as the variables are assigned values\n",
        "\n",
        "Representations\n",
        "* Graphs, where nodes are variables and the arcs are binary constraints\n",
        "* standard representation pattern which provides variables with values\n",
        "* Constraint graphs which can simiplify searches by creating independent subproblems, nodes are the variables and edges are the constraints\n",
        "* Binary CSPs where each constraint is related to two of the variables in the environment.\n",
        "* Discrete variables can have finite domains (n variables, domain size d leads to O(d^n) complete assignements, like Boolean CSPs), or infintie domains (strings, integers, start/end days for something, requires consistent language)\n",
        "* Continuous variables harder to define, start and end times for things that are constantly occurring.\n",
        "* Unary constraints involve a single variable, Binary is a pair of variables, Higher-order is 3 or more variables, can also have preferences (soft constraints) which can be enforced or not depending on rigidity of constraint.\n",
        "\n",
        "CSP as a search problem\n",
        "* if we express CSP as a search problem (initial state is empty assignment, sucessor function is next unassigned variables, goal test is when complete and consistent, path cost is the cost to assign a variable), then a solution is always found at depth n for n variables\n",
        "* Can try depth first search. If we try to expand one assignemnt per layer, we get n variables of domain size d, n*d branching at the root, n-1 * d branching at next level, n! * d^n leaves, becomes very expensive.\n",
        "* can take advantage of commutativity, the states can be assigned in any order, only need to then look at one assignment per node, so b = d with d^n leaves\n",
        "* DFS for the CPS refereed to as backtracking, when we cannot assign any legal moves we move back up the tree until we can again, continue until a complete consistent solution is reached\n",
        "* uninformed algorithm in backtracking, not assigning any costs associated with it.\n",
        "\n",
        "Backtracking performance\n",
        "* we want to create a general purpose method that has general purpose heuristic that can speed up the process and be applied to many contexts\n",
        "* to pick which variable is assigned next, want the most constrained variable first (i.e. fewest legal moves, minimum remaining values), if tied then most constraining variable (most constraints on the remaining variables in environment)\n",
        "* try the variables with the least constrining values first (rules out the fewest values for the rest of the states), and correct with forward checking\n",
        "\n",
        "Forward checking\n",
        "* we assign a variable to a domain, we want to keep a tally on the remaining legal values for the unassigned variables and go back when we have variables with no remaining values possible\n",
        "* if a failure is detected, then we use backtracking\n",
        "* cannot provide early detection for failures but moves the information forward from the assigned variable by removing the value from the neighbors\n",
        "* constraint propogation exists to repeatedly check the constraints locally instead of having to go iteratively through forward checking\n",
        "\n",
        "Inference\n",
        "* want to do this constraint propogation first to check local consistency to speed up the process of backtracking\n",
        "* local consistency can be done with node consistency (satisfies unary constraints) and arc consistancy (satisfies binary constraints)\n",
        "* if we have two nodes Xi and Xj connected by an edge, we want to represent this as a pair of directed edges or arcs from one to the other instead of an undirected edge\n",
        "\n",
        "Arc consistency\n",
        "* form of propogation to make each arc consistent, says that node 1 to node 2 is consistent iff for every value x in 1 there is some allowed y\n",
        "* if we lose a value in node 1, we recheck all of its neighbors to see that legal moves still remain \n",
        "* by doing this check on neighbors, we detect failures earlier and can do preprocessoring or check after assigning variables.\n",
        "* arc consistent iff every value on v on node 1 is consistent with some label on node 2\n",
        "* for each of these values, if there isn't a label in node 2 consistent with the value, then remove it from node 1\n",
        "* O(d^2) time to check the arcs with d values\n",
        "\n",
        "Waltz algorithm \n",
        "* iterating over the graph allows us to propagate the consistency constraints along arcs of the graph, use these constraints to add labels towards finding the solution\n",
        "* at the same time we can eliminate labels from the constraints to find all solutions\n",
        "* assign every node in the graph all possible values, then repear until there is no change in the set of values associated with any remaining nodes, for each node 1, if a neighbor has an inconsistent value with node 1, remove it from node 1\n",
        "\n",
        "AC-3 algorithm\n",
        "* only need to look at those nodes where at least one of the neighrbors has lost a value in the previous iteration to save on time\n",
        "* similarly, if node 1 loses a value because of node 2, we don't need to check node 2 in the next round, because removing a value of node 1 can only make node 2 inconsistent with node 1, no other nodes, so don't touch node 2\n",
        "* if we have all nodes connected to every other node, n nodes compared to n -1 nodes, 2 * n * (n-1) = O(n^2)\n",
        "* d values, checking an arc is O(d^2) time, each arc can be inserted back into the queue d times, giving worse case complexity of O(n^2 * d^3)\n",
        "* if we have a planar graph, arcs is only linear in N and time complexity reduced to O(n * d^3)\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"assignments\" : \"in CSPs when you give a value to a variable\",\n",
        "\"Consistency\": \"an assignment that doesn't violate any constraints, a legal move\",\n",
        "\"Complete\": \"every variable has a value\",\n",
        "\"partial assignment\": \"some of the variables are unassigned\",\n",
        "\"partial solution\": \"a consistent partial assignment\",\n",
        "\"precedence constraints\": \"the tasks/constraints have to occur in a certain order, one before another\",\n",
        "\"disjunctive constraints\": \"some events cannot happen at the same time, one first or the other\",\n",
        "\"unary constraint\": \"value of a single variable restricted\",\n",
        "\"binary constraint\": \"two variables involved in the constraint\",\n",
        "\"global constraint\": \"constraint involving any number of variables, not necessarily all of them\",\n",
        "\"preference constraints\": \"when certain solutions are preferred but not required\",\n",
        "\"constraint propagation\": \"use the constraints to remove the legal values for the variables, which can affect other variables\",\n",
        "\"local consistency\": \"treat each variable as a node in a graph and each constraint as an edge, propagate around\",\n",
        "\"node consistent\": \"one node if all values satisfy the unary constraints\",\n",
        "\"arc consisitent\": \"every value in the domain satisfies the binary constraints\",\n",
        "\"path consistent\": \"uses implicit constraints inferred by looking at triplets of variables\",\n",
        "\"resource constraint\": \"some limit ot the assignments, at most x people working at once\",\n",
        "\"minimum remaining values\": \"choose the variable with the fewest legal values next\",\n",
        "\"chronological backtracking\": \"when a branch fails, back up to the preceding node and try a different one\",\n",
        "\"constraint learning\": \"finding minimu set of variables from conlifct that cause the problem, called no-goods\",\n",
        "\"value symmetry\": \"different ways so assign the solutions that are all valid\",\n",
        "\"symmetry breaking constraint\": \"some way to break the tie and reduce the value symmetry search space\"\n",
        "}\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "kKWbCsbfxL3R",
        "outputId": "75c2f117-0341-44f2-e012-a716948f7ae4"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "\n",
              "* Constraint satisfaction consists of a set of variables X, a set of domains D for each variable, and a set of constraints C that allow a combination of values\n",
              "* Each domain allows a set of values for a given variable, relations define the constraints for each pair\n",
              "* Solution to a CSP has to be complete and consistent\n",
              "* Australia map coloring, have a set of variables X to be regions, domains are colors, constraints are no touching countries can be the same color\n",
              "* Constraint graphs help to visualize these relationships\n",
              "* Check on each assignment whether it is a goal or not\n",
              "* Discrete, finite domains make up the easiest CSPs\n",
              "* Discrete domain can still be infinite (numbers, strings)\n",
              "* Special solutions exists for linear constraints on integers, where each variable appears in linear form, but not for nonlinear constraints, undecidable\n",
              "* Continuous domains are common in the real world as well, linear programming, Hubble space telescope\n",
              "* Binary CSP only has unary and binary constraints, can be represented as a graph\n",
              "* Can convert an n-ary CSP to binary using dual graphs, creating a new graph for one variable for each constraint in the original graph and one binary constraint for each pair of constraints\n",
              "* Can apply costs to the assignments and turn them into constraint optimization problems\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "\n",
              "* Xi is arc consistent to Xj if every value in domain Di there’s some variable in Dj that satisfies the binary constraint on the arc.\n",
              "* Graph is arc consistent if every variable is arc consistent with each other\n",
              "* AC-3 maintains a queue of arcs to look through\n",
              "* Initially all arcs in the CSP, pops one off, makes it arc-consistent Xi with Xj. \n",
              "* If the domain is the same we move on, if the domain is smaller we put all arcs Xk Xi back in for all neighbors\n",
              "* If a domain goes to nothing, we have a failure and we need to return false\n",
              "* O(d^2) time to check an arc, and O(cd^3) total worse case where c is the number of arcs and d is the number of times an arc can be inserted into a queue\n",
              "* Path consistent Xi Xj with a third variable Xm if for every assignment consistent with Xi Xj there’s an assignment with Xm such that Xi Xm and Xm Xj are satisfied\n",
              "* A CSP is k-consistent if for any set of k - 1 variables with any consistent assignments, a consistent value can always be assigned to any 4th variable\n",
              "* CSP is strongly k-consistent if it is k consistent, k - 1 consistent, k - 2 consistent, … down to 1 consistent\n",
              "* Can’t represent all domains sometimes, so we do bounds propagation, set a min and max bound on the domains\n",
              "* Bounds consistent if for each variable X for lower and upper bounds there’s a value of y that satisfies the constrains between x and y\n",
              "* Sudoku is very popular CSP\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              "\n",
              "* Often still have to perform a search after constraining with backtracking\n",
              "* CSPs are commutative which is key, doesn’t matter which order we assign things, so only need to look t one variable in each node \n",
              "* Number of leaves in depth limited search is now d^n\n",
              "* Backtracking can be improved with domain independent heuristics that take advantage of factored representation\n",
              "* Which variable should be assigned next, select unassigned variable default is just pick them in order, or randomly\n",
              "* MRV heuristic is most constrained variable, most likely to fail soonest \n",
              "* Degree heuristic reduced branching factor by selected variable involved in larger number of constraints on other variables, if the MRV is tied\n",
              "* Least constraining value good for which order to examine, prefers value that rules out the fewest choices for the neighbors\n",
              "* Forward checking - whenever a variable is assigned, forward checking establishes arc consistent for it\n",
              "* Get better results if we combine MRV with forward checking\n",
              "* MAC (maintaining arc consistency) detects consistencies early.\n",
              "* Assign a variable Xi a value, inference procedure calls AC-3 starting with the arcs Xj Xi for each unassigned neighbors of Xi, more powerful than forward checking\n",
              "* Forward checking doesn’t recursively propagate constraints like MAC\n",
              "* Keep track of assignments that conflict with some value, called the conflict set, then backup to the most recent assignment in the conflict set\n",
              "* Backjumping algorithm that uses conflict sets is called conflict-directs backjumping\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              "\n",
              "* Local search algorithms good in solving CSPs, N-Queens for example\n",
              "* Min conflicts heuristic is selecting a value that gives the minimum number of conflicts with other variable\n",
              "* Tabu search keeps a list of recently visited states handy and forbid the return to those states\n",
              "* Constraint weighing weights the variable/value pairs different so concentrate on the important bits of search\n",
              "* Local search all can be used in online setting when the problems change\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              "\n",
              "* Decompose into simpler problems, if we have independent subproblems can solve those first\n",
              "* Independence found by identifying connected components of the constraint graph\n",
              "* Constraint graphs are trees when any two variables are connected by only one path, then can be solved in linear time with the number of variables\n",
              "* Directional arc consistency if we look at arc consistency in one direction\n",
              "* Topological sort used when we pick a variable to be the root of the tree and order the variables outside of that\n",
              "* Don’t need to backtrack then, just move through the variable orderings\n",
              "* Cutset conditioning algorithm: choose a subset of the variables so that the graph is a tree when S is removed, S is a cycle cutest\n",
              "* For each assignment to variables in S that satisfies all constraints, remove from the domains of remaining variables any inconsistent values, and if it has a solution return it with S assignment\n",
              "* Tree decomposition transforms the graph itnto a tree where each node consists of a set of variables\n",
              "* Decomposition must have every variable in at least one of the tree nodes, if two variables are connected in the original problem they must be in at least one of trees, and if a variable appears in two nodes in the tree it must be in every node along the path connecting the nodes\n",
              "* Tree width of the decomposition is one less than the size of the largest node\n",
              "* Tree width of graph is minimum width of tree decompositions\n",
              "* CPSs with bounded tree widths are solvable in polynomial time\n",
              "\n",
              "\n",
              "## Module 6 Lecture Notes\n",
              "\n",
              "Purpose of search\n",
              "* Assume in our world we habe a single agent, deterministic actions, fully obseravle, discrete actions\n",
              "* planning involves creating a sequence of actions to get to the goal, with costs and depths, heuristics\n",
              "* identify assignments to variables, do not care how we reach the goal\n",
              "\n",
              "Constraint Satisfaction Problems\n",
              "* want to represent constraints that solutions have to satisfy in some language, make them general purpose search algorithms \n",
              "* if they are general purpose then we can specify a problem in some language and the algorithm still works\n",
              "* in a CSP we have finite set of variables X1, X2, ..., Xn, nonempty domain of values for each variable D1, D2, .. where Di = {v1, ..., vk}, finite set of constraints C1, ... Cm\n",
              "* a constraint limits the values that the varibales can take according to some rules, and a state is defined as the assignemtn of these values to the variables.\n",
              "* An assignment is consistent if it doesn't violate the constraints, sudoku, color mapping, scheduling problems\n",
              "* complete assignment is achieved when every variable is assigned a value\n",
              "* a solution has to be both complete and consistent, solutions. found using these general purpose algorithms, maximizes some objective function\n",
              "\n",
              "Map coloring example\n",
              "* have a map and can assign each country or area as a variable, domains initially are all possible colors, constraints are touching regions have to have different colors\n",
              "* how many colors are required to create a complete and consistent assignment (solution)\n",
              "\n",
              "Advantages\n",
              "* create a generic goal, successor function, and heuristics, and clean specifications can be created from them\n",
              "* the CSP can check when the variables violate a constraint with forward checking\n",
              "* prune off branches where constraints are violates as the variables are assigned values\n",
              "\n",
              "Representations\n",
              "* Graphs, where nodes are variables and the arcs are binary constraints\n",
              "* standard representation pattern which provides variables with values\n",
              "* Constraint graphs which can simiplify searches by creating independent subproblems, nodes are the variables and edges are the constraints\n",
              "* Binary CSPs where each constraint is related to two of the variables in the environment.\n",
              "* Discrete variables can have finite domains (n variables, domain size d leads to O(d^n) complete assignements, like Boolean CSPs), or infintie domains (strings, integers, start/end days for something, requires consistent language)\n",
              "* Continuous variables harder to define, start and end times for things that are constantly occurring.\n",
              "* Unary constraints involve a single variable, Binary is a pair of variables, Higher-order is 3 or more variables, can also have preferences (soft constraints) which can be enforced or not depending on rigidity of constraint.\n",
              "\n",
              "CSP as a search problem\n",
              "* if we express CSP as a search problem (initial state is empty assignment, sucessor function is next unassigned variables, goal test is when complete and consistent, path cost is the cost to assign a variable), then a solution is always found at depth n for n variables\n",
              "* Can try depth first search. If we try to expand one assignemnt per layer, we get n variables of domain size d, n*d branching at the root, n-1 * d branching at next level, n! * d^n leaves, becomes very expensive.\n",
              "* can take advantage of commutativity, the states can be assigned in any order, only need to then look at one assignment per node, so b = d with d^n leaves\n",
              "* DFS for the CPS refereed to as backtracking, when we cannot assign any legal moves we move back up the tree until we can again, continue until a complete consistent solution is reached\n",
              "* uninformed algorithm in backtracking, not assigning any costs associated with it.\n",
              "\n",
              "Backtracking performance\n",
              "* we want to create a general purpose method that has general purpose heuristic that can speed up the process and be applied to many contexts\n",
              "* to pick which variable is assigned next, want the most constrained variable first (i.e. fewest legal moves, minimum remaining values), if tied then most constraining variable (most constraints on the remaining variables in environment)\n",
              "* try the variables with the least constrining values first (rules out the fewest values for the rest of the states), and correct with forward checking\n",
              "\n",
              "Forward checking\n",
              "* we assign a variable to a domain, we want to keep a tally on the remaining legal values for the unassigned variables and go back when we have variables with no remaining values possible\n",
              "* if a failure is detected, then we use backtracking\n",
              "* cannot provide early detection for failures but moves the information forward from the assigned variable by removing the value from the neighbors\n",
              "* constraint propogation exists to repeatedly check the constraints locally instead of having to go iteratively through forward checking\n",
              "\n",
              "Inference\n",
              "* want to do this constraint propogation first to check local consistency to speed up the process of backtracking\n",
              "* local consistency can be done with node consistency (satisfies unary constraints) and arc consistancy (satisfies binary constraints)\n",
              "* if we have two nodes Xi and Xj connected by an edge, we want to represent this as a pair of directed edges or arcs from one to the other instead of an undirected edge\n",
              "\n",
              "Arc consistency\n",
              "* form of propogation to make each arc consistent, says that node 1 to node 2 is consistent iff for every value x in 1 there is some allowed y\n",
              "* if we lose a value in node 1, we recheck all of its neighbors to see that legal moves still remain \n",
              "* by doing this check on neighbors, we detect failures earlier and can do preprocessoring or check after assigning variables.\n",
              "* arc consistent iff every value on v on node 1 is consistent with some label on node 2\n",
              "* for each of these values, if there isn't a label in node 2 consistent with the value, then remove it from node 1\n",
              "* O(d^2) time to check the arcs with d values\n",
              "\n",
              "Waltz algorithm \n",
              "* iterating over the graph allows us to propagate the consistency constraints along arcs of the graph, use these constraints to add labels towards finding the solution\n",
              "* at the same time we can eliminate labels from the constraints to find all solutions\n",
              "* assign every node in the graph all possible values, then repear until there is no change in the set of values associated with any remaining nodes, for each node 1, if a neighbor has an inconsistent value with node 1, remove it from node 1\n",
              "\n",
              "AC-3 algorithm\n",
              "* only need to look at those nodes where at least one of the neighrbors has lost a value in the previous iteration to save on time\n",
              "* similarly, if node 1 loses a value because of node 2, we don't need to check node 2 in the next round, because removing a value of node 1 can only make node 2 inconsistent with node 1, no other nodes, so don't touch node 2\n",
              "* if we have all nodes connected to every other node, n nodes compared to n -1 nodes, 2 * n * (n-1) = O(n^2)\n",
              "* d values, checking an arc is O(d^2) time, each arc can be inserted back into the queue d times, giving worse case complexity of O(n^2 * d^3)\n",
              "* if we have a planar graph, arcs is only linear in N and time complexity reduced to O(n * d^3)\n",
              "\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Assignments** - in CSPs when you give a value to a variable\n",
              "* **Consistency** - an assignment that doesn't violate any constraints, a legal move\n",
              "* **Complete** - every variable has a value\n",
              "* **Partial assignment** - some of the variables are unassigned\n",
              "* **Partial solution** - a consistent partial assignment\n",
              "* **Precedence constraints** - the tasks/constraints have to occur in a certain order, one before another\n",
              "* **Disjunctive constraints** - some events cannot happen at the same time, one first or the other\n",
              "* **Unary constraint** - value of a single variable restricted\n",
              "* **Binary constraint** - two variables involved in the constraint\n",
              "* **Global constraint** - constraint involving any number of variables, not necessarily all of them\n",
              "* **Preference constraints** - when certain solutions are preferred but not required\n",
              "* **Constraint propagation** - use the constraints to remove the legal values for the variables, which can affect other variables\n",
              "* **Local consistency** - treat each variable as a node in a graph and each constraint as an edge, propagate around\n",
              "* **Node consistent** - one node if all values satisfy the unary constraints\n",
              "* **Arc consisitent** - every value in the domain satisfies the binary constraints\n",
              "* **Path consistent** - uses implicit constraints inferred by looking at triplets of variables\n",
              "* **Resource constraint** - some limit ot the assignments, at most x people working at once\n",
              "* **Minimum remaining values** - choose the variable with the fewest legal values next\n",
              "* **Chronological backtracking** - when a branch fails, back up to the preceding node and try a different one\n",
              "* **Constraint learning** - finding minimu set of variables from conlifct that cause the problem, called no-goods\n",
              "* **Value symmetry** - different ways so assign the solutions that are all valid\n",
              "* **Symmetry breaking constraint** - some way to break the tie and reduce the value symmetry search space\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": null,
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "outputs": [],
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "* Sentences in KB can be a lot of things, expressed in a knowledge representation language, tell information about the world\n",
        "* KB initially has background knowledge of the environment\n",
        "* Every time the agent program is called, it tells the KB what it perceives, asks what is should perform, then tells the KB what action was taken\n",
        "* Need to specify what the agent knows and its goals at the knowledge level\n",
        "* Might differ significantly from the implementation level\n",
        "* A successful agent has both declarative and procedural setup\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "* Wumpus world of rooms connected by passages, Same setup as R2D2 problem\n",
        "* Performance measure, get the gold and climb out, or die by a pit or Wumpus\n",
        "* Environment: 4 x 4 grid of rooms with walls\n",
        "* actuators: forward, turn left, turn right\n",
        "* sensors: stench, breeze, glitter, bump, scream\n",
        "* Deterministic, discrete, static, single agent\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\"\n",
        "* If sentence a is true in model m, we say m satisfies a or m is a model of a\n",
        "* M(a) is the set of all models of a\n",
        "* A entails b if and only if in every model where a is true, b Is true, or a |= b iff M(a) is proper subset of M(b)\n",
        "* When an inference algorithm I derives a from KB, we write KB |-I a\n",
        "* If we have a KB that is true in the real world, then if we derive a sentence a from Kb using a sound inference procedure it is also true in the real world\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"\n",
        "* Syntax of propositional logic defines allowable atomic sentences which a single propositional symbol\n",
        "* Complex sentences constructed from simpler ones using logical connectives, not, and, or, implies, if and only if\n",
        "* The semantics are just the model setting truth values for each propositional symbol\n",
        "* Semantics must allow you to compute the truth value of any sentence in a model recursively\n",
        "* Rules expressed in truth tables that specify values of complex sentences\n",
        "* Exclusive or (xor) is false when both disjuncts are the same\n",
        "* When constructing a knowledge base, focus on immutable aspects first\n",
        "* Propositional logic is co-NP-complete, meaning every known inference algorithm has a worst-case complexity that is exponential compare to the input size\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\"* A entails b iff the sentence a ^ not b is unsatisfiable, proof of refutation or contradiction\n",
        "* Inference rules can be applies to sentences to generate proofs\n",
        "* Modus ponens, and elimination, biconditional elimination\n",
        "* Finding a proof can be more efficient in practical cases because it can ignore unlimited irrelevant propositions\n",
        "* In monotonicity, if KB entails a then KB and B entail a\n",
        "* B would draw additional conclusions but cannot invalidate any conclusion that is already made for a, follows regardless of what else is in the KB\n",
        "* Resolution is a single inference rule that yields complete inference algorithms when combined with complete search algorithms\n",
        "* Resolvents created when information applied to a sentence makes it more clear, if there is a bit in one of three spots and its not in one of the spots, then its in one of the other two spots, unit resolution inference rule\n",
        "* Unit resolution takes a clause and literal and produces a new clause, can be a single or unit clauses, generalized into a full resolution rule\n",
        "* Resulting clause should only have one copy of each literal, removing of multiple copies called factoring\n",
        "* Resolution based theorem prover can decide whether a entails b for any a and b \n",
        "* Every sentence in propositional logic is logically equivalent to conjunction of clauses\n",
        "* CNF conversion: 1. Eliminate iff with implies, eliminate implies with not a and b, move the not inwards to match with literals, distribute ands and ors \n",
        "* Convert to CNF then apply resolution rules on resulting clauses\n",
        "* Continue to resolve new clauses, add to the set if its not there\n",
        "* Continue doing this until there are no new clauses to add where KB doesn’t entail a, or two clauses resolve to the empty clause, then KB entails a\n",
        "* Resolution closure RC(S) is the set of all clauses derivable by resolution rule to clauses in S or derivatives\n",
        "* If you try to resolve two horn clauses you get back a horn clause\n",
        "* Every definite clause can bet written as an implication with a conjunction of positive literals as its premise and a single positive literal as a conclusion\n",
        "* Horn clause inference can be done with forward-chaining and backward-chaining\n",
        "* Entailment with horn clauses is done in linear time to KB\n",
        "* Forward chaining determines if a proposition symbol is entailed by a KB of definite clauses, if all premises are known, then conclusion added to known facts\n",
        "* Forward chaining is sound and complete, a. Concept of data-driven reasoning\n",
        "* Backward chaining works backward from query, finds implications who’s conclusion is query, a form of goal directed reasoning\n",
        "* Cost often much less than linear time because it only looks at the relevant facts\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "Knowledge Based Agents:\n",
        "* utilize a process of reasonign over an internal representation in deciding what actions to take\n",
        "* up to this point the states have been atomic, agents have performed a search to figure out a plan and execute actions\n",
        "* a knowledge base of KB is the critical component of a knowledge-based agent\n",
        "* A KB has sentences written in a knowledge representation language that provide assertions about the world that the agent lives in\n",
        "* Sentence can be an axiom (given) or a derived sentence (created from the other sentences in a process called inference)\n",
        "* KB needs to have background information about the world before beginning and the agent can add to it through exploring the world\n",
        "* can also query the KB and tell it to derive new knowledge to best decide what action should be taken next\n",
        "\n",
        "Wampa world\n",
        "* create a world that is deterministic, discrete, static, single agent, R2D2 attempting to find Luke, reward if he does, penalty if he dies\n",
        "* in contrast to before, we have sequential steps because the reward/penalty may not be immediate, and partially observable because R2D2 cannot see where he hasn't been\n",
        "\n",
        "Logic\n",
        "* serves as class of representations for Knowledge based agents, specifically propositional logic\n",
        "* language has a syntax that says whether or not a sentence is correctly constructed, semantics that define what the sentences mean and define the truth of each sentence in the world (or model)\n",
        "* Have a bunch of truth values for each sentence, e.g. if we have a sentence a in a model m that is true, we say m satifies a, m is a model of a, M(a) to say the set of all models of a\n",
        "* define logical reasoning from truth statements, this reasoning involves entailment relationship between sentences, one logically flows from another\n",
        "* sentence a entails sentence beta a |= B, this is only true if M(a) is a subset of M(b), or a is more specific or stronger than B\n",
        "* KBs are false where models contradict what the agent knows, and possible worlds are all worlds compatible with the KB\n",
        "* entailment used to derive conclusions through locial inference. If we have some starting sentences we can create many entailed sentences to add to the KB\n",
        "* we want to create inference algorithms as a process of finding these sentences\n",
        "* KN |-i a means that a is derived from the KB by i\n",
        "* Monotonicity occurs when if KB |= a then KB ^ B |= a and we can add this to the KB without invalidating anything else\n",
        "* if we have monotonicity, we imply that the environment is sound and only derives entailed sentences\n",
        "\n",
        "Propositional logic\n",
        "* Here we have atomic sentences tha twere represented by a single propositional symbol, these symbols stand for a statements that can be true or false, e.g. FacingEast, W1,2\n",
        "* can construct complex sentences from simpler ones using parenthese and logical connectives (not, and, or, implies, if and only if)\n",
        "* create truth tables that represent all outcomes when variables are true or false with these logical connectives\n",
        "* not inverts the input, and is only true when both p and q are true, or is true when p or q is true\n",
        "* implication, true when T -> T or F -> anything\n",
        "* iff, true when T <-> T or F <-> F\n",
        "* Sound when the inference alogirhtm only derives entailed sentences, complete when the inference algorithm can derive all entailed sentences\n",
        "\n",
        "Logical equivalence\n",
        "* two sentences are seemed logically equivalent if they are true in the same set of models, a (three lines) B\n",
        "* two sentences a and B are only logically equivalent if they both entail each other\n",
        "* have a huge list of rules for logical equivalences, commutativity, associativity, double negative, contrapositive, implication elimination, biconditional elimination, De Morgan, distributivity\n",
        "* we use inference rules to derive proofs, if we have a sentence and the values that are true, can derive a new sentence, i.e. Modus Ponens, A elimination\n",
        "\n",
        "Search equivalent\n",
        "* Initial state is the KB at the beginning, actions are all inference rules applied to the sentences, result is adding the sentence to the KB, goal is the state with the sentence we're trying to prove\n",
        "* to prove completeness, we use resolution (single inference rule) to give a complete inference algorithm with any complete search algorithm\n",
        "* if l1 and m are complementary literals (meaning one is the negation of the other), then we eliminate them using unit resolution\n",
        "* resolution only applies to clauses (disjuctions of literals), where every sentence can be converted to an equivalent conjunction of clauses\n",
        "\n",
        "Conjunctive Normal Form\n",
        "* we can convert any sentence in propositional logic to a conjunction of clauses (disjunction of literals)\n",
        "1. Eliminate iff by replacing a iff b with (a -> b) ^ (b -> a)\n",
        "2. Eliminate -> by replacing a -> with (not a) v b\n",
        "3. move the not inwards, eliminate double negation and apply De Morgan's laws\n",
        "4. Apply distributivity laws with ^ and v wherever you can\n",
        "\n",
        "Resolution Algorithm\n",
        "* use proof by contradiction in inference procedures with resolution work\n",
        "* we want to show that KB |= a by showing that KB ^ not a is unsatisfiable\n",
        "1. Convert (KB ^ not a) into a CNF using the previous rules\n",
        "2. Apply resolution rule to resulting clauses\n",
        "3. Resolve every pair that has complementary literals, producing new clauses\n",
        "4. add the clause to the set if it isnt there, repeat until either there are no new clauses that can be added (KB does not entail a), or two clauses resolve to yield the empty clause (KB does entail a)\n",
        "* Empty clause come frsom two contradictory units a and not a\n",
        "* Complete algorithm, powerful inference method\n",
        "* KBs can be formulated with more restrictive form, can be more fficient\n",
        "* Definitive clauses include literals where exactlt one is positive\n",
        "* Horn Clauses include literals where at most one is positive (includes definite clauses and clauses with no positive literals). Closed under resolution, if you apply a resolution you get the same clause back\n",
        "\n",
        "Definite Clauses\n",
        "* can write every definite clause as an implication with a premise of a conjunction of positive literals whose conjunction is positive literal. (not B v not a v C can be written as B ^ a -> C)\n",
        "* horn clause inference done with forward and backward-chaining algorithms\n",
        "* deciding horn clause entailment is done in linear time relative to the size of KB\n",
        "\n",
        "Chaining\n",
        "* Forward - kind of data-driven reasoning. Agent adds premises as percepts come in, apply the forward chaining algorithm to derive new conclusions, no query needed\n",
        "* Backward - works backward from a query, if the query is true then don't need to act, otherwise the algorithm finds the implications in KB whose conclusions is the query. All premises of one can be proved to be true, then the query is true. Form of goal directed reasoning.\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge base\" : \"central component of knowledge based agents, a set of sentences that assert things in the world\",\n",
        "\"axiom\": \"sentences that are given without being derived from others\",\n",
        "\"inference\": \"deriving new sentences from existing ones and axioms\",\n",
        "\"declarative approach\": \"designer tells sentences to the agent until it knows how to act in the environment\",\n",
        "\"procedural approach\": \"desired behaviors of the agent are encoded directly instead\",\n",
        "\"syntax\": \"how sentences in a knowledge bases are well formed\",\n",
        "\"semantics\": \"what meaning the sentences carry in a knowledge base, define truth in the world\",\n",
        "\"model\": \"in logic, means the real possible worlds/environments the agent is existing in\",\n",
        "\"entailment\": \"sentences follow logically from another sentence, a entails B, a|= B\",\n",
        "\"logical inference\": \"how the definitions of entailment are applied to derive new conclusions\",\n",
        "\"model checking\": \"when all possible models are enumerated to see if a is true in all models where KB is true\",\n",
        "\"soundness\": \"when an inference algorithm only derives entailed sentences, truth preserving\",\n",
        "\"completeness\": \"when an inference algorithm can derive any sentence that it entails\",\n",
        "\"grounding\": \"the connection between logical reasoning and the real environment where the agent lives\",\n",
        "\"propositional logic\": \"deriving syntactic algorithm for logical inferences to implement semantic notion of entailment\",\n",
        "\"Theorem proving\": \"when we apply inference rules to sentences in KB to construct proofs of the desired sentences\",\n",
        "\"logical equivalence\": \"two sentences have the same true tables in the same set of models\",\n",
        "\"validity\": \"a sentence is valid if true in all environemnts, also known as tautologies\",\n",
        "\"deduction theorem\": \"for two sentences a and b, a entails b iff a ->b is valid\",\n",
        "\"satisfiability\": \"sentence is satisfiable if it's true in some model\",\n",
        "\"monotonicity\": \"set of entailed sentences only increases as more information is gained\",\n",
        "\"Conjunctive Normal Form\": \"a sentence expressed as a conjunction of clauses\",\n",
        "\"Ground resolution theorem\": \"if a set of clauses is unsatisfiable, resolution closure contains empty clause\",\n",
        "\"definite clauses\": \"disjunction of literals where exactly one is positive\",\n",
        "\"Horn Clauses\": \"more general, disjunction of literals where at most one is positive, closed under resolution\",\n",
        "\"Goal clauses\": \"clauses with no positive literals\",\n",
        "\"k-CNF\": \"CNF sentence where each clause has at most k literals\",\n",
        "\"data driven reasoning\": \"focuses attention on the known data, forward chaining\"\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "lXNcHuKjyNXa",
        "outputId": "52fd8b0f-432a-48fd-ba8d-9761534e1b47"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "\n",
              "* Sentences in KB can be a lot of things, expressed in a knowledge representation language, tell information about the world\n",
              "* KB initially has background knowledge of the environment\n",
              "* Every time the agent program is called, it tells the KB what it perceives, asks what is should perform, then tells the KB what action was taken\n",
              "* Need to specify what the agent knows and its goals at the knowledge level\n",
              "* Might differ significantly from the implementation level\n",
              "* A successful agent has both declarative and procedural setup\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              "\n",
              "* Wumpus world of rooms connected by passages, Same setup as R2D2 problem\n",
              "* Performance measure, get the gold and climb out, or die by a pit or Wumpus\n",
              "* Environment: 4 x 4 grid of rooms with walls\n",
              "* actuators: forward, turn left, turn right\n",
              "* sensors: stench, breeze, glitter, bump, scream\n",
              "* Deterministic, discrete, static, single agent\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              "\n",
              "* If sentence a is true in model m, we say m satisfies a or m is a model of a\n",
              "* M(a) is the set of all models of a\n",
              "* A entails b if and only if in every model where a is true, b Is true, or a |= b iff M(a) is proper subset of M(b)\n",
              "* When an inference algorithm I derives a from KB, we write KB |-I a\n",
              "* If we have a KB that is true in the real world, then if we derive a sentence a from Kb using a sound inference procedure it is also true in the real world\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "\n",
              "* Syntax of propositional logic defines allowable atomic sentences which a single propositional symbol\n",
              "* Complex sentences constructed from simpler ones using logical connectives, not, and, or, implies, if and only if\n",
              "* The semantics are just the model setting truth values for each propositional symbol\n",
              "* Semantics must allow you to compute the truth value of any sentence in a model recursively\n",
              "* Rules expressed in truth tables that specify values of complex sentences\n",
              "* Exclusive or (xor) is false when both disjuncts are the same\n",
              "* When constructing a knowledge base, focus on immutable aspects first\n",
              "* Propositional logic is co-NP-complete, meaning every known inference algorithm has a worst-case complexity that is exponential compare to the input size\n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "* A entails b iff the sentence a ^ not b is unsatisfiable, proof of refutation or contradiction\n",
              "* Inference rules can be applies to sentences to generate proofs\n",
              "* Modus ponens, and elimination, biconditional elimination\n",
              "* Finding a proof can be more efficient in practical cases because it can ignore unlimited irrelevant propositions\n",
              "* In monotonicity, if KB entails a then KB and B entail a\n",
              "* B would draw additional conclusions but cannot invalidate any conclusion that is already made for a, follows regardless of what else is in the KB\n",
              "* Resolution is a single inference rule that yields complete inference algorithms when combined with complete search algorithms\n",
              "* Resolvents created when information applied to a sentence makes it more clear, if there is a bit in one of three spots and its not in one of the spots, then its in one of the other two spots, unit resolution inference rule\n",
              "* Unit resolution takes a clause and literal and produces a new clause, can be a single or unit clauses, generalized into a full resolution rule\n",
              "* Resulting clause should only have one copy of each literal, removing of multiple copies called factoring\n",
              "* Resolution based theorem prover can decide whether a entails b for any a and b \n",
              "* Every sentence in propositional logic is logically equivalent to conjunction of clauses\n",
              "* CNF conversion: 1. Eliminate iff with implies, eliminate implies with not a and b, move the not inwards to match with literals, distribute ands and ors \n",
              "* Convert to CNF then apply resolution rules on resulting clauses\n",
              "* Continue to resolve new clauses, add to the set if its not there\n",
              "* Continue doing this until there are no new clauses to add where KB doesn’t entail a, or two clauses resolve to the empty clause, then KB entails a\n",
              "* Resolution closure RC(S) is the set of all clauses derivable by resolution rule to clauses in S or derivatives\n",
              "* If you try to resolve two horn clauses you get back a horn clause\n",
              "* Every definite clause can bet written as an implication with a conjunction of positive literals as its premise and a single positive literal as a conclusion\n",
              "* Horn clause inference can be done with forward-chaining and backward-chaining\n",
              "* Entailment with horn clauses is done in linear time to KB\n",
              "* Forward chaining determines if a proposition symbol is entailed by a KB of definite clauses, if all premises are known, then conclusion added to known facts\n",
              "* Forward chaining is sound and complete, a. Concept of data-driven reasoning\n",
              "* Backward chaining works backward from query, finds implications who’s conclusion is query, a form of goal directed reasoning\n",
              "* Cost often much less than linear time because it only looks at the relevant facts\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              "\n",
              "Knowledge Based Agents:\n",
              "* utilize a process of reasonign over an internal representation in deciding what actions to take\n",
              "* up to this point the states have been atomic, agents have performed a search to figure out a plan and execute actions\n",
              "* a knowledge base of KB is the critical component of a knowledge-based agent\n",
              "* A KB has sentences written in a knowledge representation language that provide assertions about the world that the agent lives in\n",
              "* Sentence can be an axiom (given) or a derived sentence (created from the other sentences in a process called inference)\n",
              "* KB needs to have background information about the world before beginning and the agent can add to it through exploring the world\n",
              "* can also query the KB and tell it to derive new knowledge to best decide what action should be taken next\n",
              "\n",
              "Wampa world\n",
              "* create a world that is deterministic, discrete, static, single agent, R2D2 attempting to find Luke, reward if he does, penalty if he dies\n",
              "* in contrast to before, we have sequential steps because the reward/penalty may not be immediate, and partially observable because R2D2 cannot see where he hasn't been\n",
              "\n",
              "Logic\n",
              "* serves as class of representations for Knowledge based agents, specifically propositional logic\n",
              "* language has a syntax that says whether or not a sentence is correctly constructed, semantics that define what the sentences mean and define the truth of each sentence in the world (or model)\n",
              "* Have a bunch of truth values for each sentence, e.g. if we have a sentence a in a model m that is true, we say m satifies a, m is a model of a, M(a) to say the set of all models of a\n",
              "* define logical reasoning from truth statements, this reasoning involves entailment relationship between sentences, one logically flows from another\n",
              "* sentence a entails sentence beta a |= B, this is only true if M(a) is a subset of M(b), or a is more specific or stronger than B\n",
              "* KBs are false where models contradict what the agent knows, and possible worlds are all worlds compatible with the KB\n",
              "* entailment used to derive conclusions through locial inference. If we have some starting sentences we can create many entailed sentences to add to the KB\n",
              "* we want to create inference algorithms as a process of finding these sentences\n",
              "* KN |-i a means that a is derived from the KB by i\n",
              "* Monotonicity occurs when if KB |= a then KB ^ B |= a and we can add this to the KB without invalidating anything else\n",
              "* if we have monotonicity, we imply that the environment is sound and only derives entailed sentences\n",
              "\n",
              "Propositional logic\n",
              "* Here we have atomic sentences tha twere represented by a single propositional symbol, these symbols stand for a statements that can be true or false, e.g. FacingEast, W1,2\n",
              "* can construct complex sentences from simpler ones using parenthese and logical connectives (not, and, or, implies, if and only if)\n",
              "* create truth tables that represent all outcomes when variables are true or false with these logical connectives\n",
              "* not inverts the input, and is only true when both p and q are true, or is true when p or q is true\n",
              "* implication, true when T -> T or F -> anything\n",
              "* iff, true when T <-> T or F <-> F\n",
              "* Sound when the inference alogirhtm only derives entailed sentences, complete when the inference algorithm can derive all entailed sentences\n",
              "\n",
              "Logical equivalence\n",
              "* two sentences are seemed logically equivalent if they are true in the same set of models, a (three lines) B\n",
              "* two sentences a and B are only logically equivalent if they both entail each other\n",
              "* have a huge list of rules for logical equivalences, commutativity, associativity, double negative, contrapositive, implication elimination, biconditional elimination, De Morgan, distributivity\n",
              "* we use inference rules to derive proofs, if we have a sentence and the values that are true, can derive a new sentence, i.e. Modus Ponens, A elimination\n",
              "\n",
              "Search equivalent\n",
              "* Initial state is the KB at the beginning, actions are all inference rules applied to the sentences, result is adding the sentence to the KB, goal is the state with the sentence we're trying to prove\n",
              "* to prove completeness, we use resolution (single inference rule) to give a complete inference algorithm with any complete search algorithm\n",
              "* if l1 and m are complementary literals (meaning one is the negation of the other), then we eliminate them using unit resolution\n",
              "* resolution only applies to clauses (disjuctions of literals), where every sentence can be converted to an equivalent conjunction of clauses\n",
              "\n",
              "Conjunctive Normal Form\n",
              "* we can convert any sentence in propositional logic to a conjunction of clauses (disjunction of literals)\n",
              "1. Eliminate iff by replacing a iff b with (a -> b) ^ (b -> a)\n",
              "2. Eliminate -> by replacing a -> with (not a) v b\n",
              "3. move the not inwards, eliminate double negation and apply De Morgan's laws\n",
              "4. Apply distributivity laws with ^ and v wherever you can\n",
              "\n",
              "Resolution Algorithm\n",
              "* use proof by contradiction in inference procedures with resolution work\n",
              "* we want to show that KB |= a by showing that KB ^ not a is unsatisfiable\n",
              "1. Convert (KB ^ not a) into a CNF using the previous rules\n",
              "2. Apply resolution rule to resulting clauses\n",
              "3. Resolve every pair that has complementary literals, producing new clauses\n",
              "4. add the clause to the set if it isnt there, repeat until either there are no new clauses that can be added (KB does not entail a), or two clauses resolve to yield the empty clause (KB does entail a)\n",
              "* Empty clause come frsom two contradictory units a and not a\n",
              "* Complete algorithm, powerful inference method\n",
              "* KBs can be formulated with more restrictive form, can be more fficient\n",
              "* Definitive clauses include literals where exactlt one is positive\n",
              "* Horn Clauses include literals where at most one is positive (includes definite clauses and clauses with no positive literals). Closed under resolution, if you apply a resolution you get the same clause back\n",
              "\n",
              "Definite Clauses\n",
              "* can write every definite clause as an implication with a premise of a conjunction of positive literals whose conjunction is positive literal. (not B v not a v C can be written as B ^ a -> C)\n",
              "* horn clause inference done with forward and backward-chaining algorithms\n",
              "* deciding horn clause entailment is done in linear time relative to the size of KB\n",
              "\n",
              "Chaining\n",
              "* Forward - kind of data-driven reasoning. Agent adds premises as percepts come in, apply the forward chaining algorithm to derive new conclusions, no query needed\n",
              "* Backward - works backward from a query, if the query is true then don't need to act, otherwise the algorithm finds the implications in KB whose conclusions is the query. All premises of one can be proved to be true, then the query is true. Form of goal directed reasoning.\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Knowledge base** - central component of knowledge based agents, a set of sentences that assert things in the world\n",
              "* **Axiom** - sentences that are given without being derived from others\n",
              "* **Inference** - deriving new sentences from existing ones and axioms\n",
              "* **Declarative approach** - designer tells sentences to the agent until it knows how to act in the environment\n",
              "* **Procedural approach** - desired behaviors of the agent are encoded directly instead\n",
              "* **Syntax** - how sentences in a knowledge bases are well formed\n",
              "* **Semantics** - what meaning the sentences carry in a knowledge base, define truth in the world\n",
              "* **Model** - in logic, means the real possible worlds/environments the agent is existing in\n",
              "* **Entailment** - sentences follow logically from another sentence, a entails B, a|= B\n",
              "* **Logical inference** - how the definitions of entailment are applied to derive new conclusions\n",
              "* **Model checking** - when all possible models are enumerated to see if a is true in all models where KB is true\n",
              "* **Soundness** - when an inference algorithm only derives entailed sentences, truth preserving\n",
              "* **Completeness** - when an inference algorithm can derive any sentence that it entails\n",
              "* **Grounding** - the connection between logical reasoning and the real environment where the agent lives\n",
              "* **Propositional logic** - deriving syntactic algorithm for logical inferences to implement semantic notion of entailment\n",
              "* **Theorem proving** - when we apply inference rules to sentences in KB to construct proofs of the desired sentences\n",
              "* **Logical equivalence** - two sentences have the same true tables in the same set of models\n",
              "* **Validity** - a sentence is valid if true in all environemnts, also known as tautologies\n",
              "* **Deduction theorem** - for two sentences a and b, a entails b iff a ->b is valid\n",
              "* **Satisfiability** - sentence is satisfiable if it's true in some model\n",
              "* **Monotonicity** - set of entailed sentences only increases as more information is gained\n",
              "* **Conjunctive normal form** - a sentence expressed as a conjunction of clauses\n",
              "* **Ground resolution theorem** - if a set of clauses is unsatisfiable, resolution closure contains empty clause\n",
              "* **Definite clauses** - disjunction of literals where exactly one is positive\n",
              "* **Horn clauses** - more general, disjunction of literals where at most one is positive, closed under resolution\n",
              "* **Goal clauses** - clauses with no positive literals\n",
              "* **K-cnf** - CNF sentence where each clause has at most k literals\n",
              "* **Data driven reasoning** - focuses attention on the known data, forward chaining\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": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "3f1b4564-f4a4-4ee9-dd91-0aad47895b3b"
      },
      "outputs": [
        {
          "data": {
            "text/markdown": [
              "# Module 1: Rational Agents and Task Environments\n",
              "## AIMA Chapter 1.1 What is AI?\n",
              "\n",
              "* Generally want AI to do the right thing, defined as rationality\n",
              "* this intelligence can either thought processes and reasoning or actual intelligent behavior\n",
              "* computer would need natural language processing, knowledge representation, automated reasoning, and machine learning to pass the Turing test\n",
              "* Think of a human thought in terms of introspection (thinking about their thoughts), psychological experiments, and brain imaging\n",
              "* Aristotle tried to quantify what thinking was right meant, created syllogisms for patterns for arguments that gave correct conclusions when fed the right premise, initalized field of logic\n",
              "* Logicist tradition was the first forms of problems solved when a solvable problem was described in a certain way\n",
              "* probability is used to fill in the gaps of uncertainty when dealing with logical problems\n",
              "* all skills for the turing test allow rational agents to exist\n",
              "* early agents were built based on logical foundations, transitioned to be probability and machine learning to make the best decision possible in an environment\n",
              "* agents with incorrect objectives are more difficult to correct in modern design \n",
              "* not incorrect or unintelligent when it acts \"irrationally\", it is doing so to reach the objective\n",
              "* want to create agents that are provably beneficial to humans\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 The Limits of AI\n",
              "\n",
              "* Searle defined weak AI vs. strong AI, strong AI shifted to human level AI\n",
              "* Turing claimed that human behavior was too complex to simulate with any sort of computer\n",
              "* Turing outlined all of the things computers could never do, some of which has already happened\n",
              "* Turing and Godel proved there existed questions that were not answerable by formal systems\n",
              "* thought that this proved machines were inferior to humans mentally\n",
              "* incompleteness theorem that Godel created applies more to mathematics than computers\n",
              "* only really applies to formal systems that can do arithmetic\n",
              "* Turing test tried to get a human to believe that a computer answering questions was also a human\n",
              "\n",
              "\n",
              "\n",
              "## AIMA Chapter 27.1 Can Machines Really Think?\n",
              " \n",
              "* Is a machine that is intelligent actually thinking or only simulating it\n",
              "* Difficult to draw a line on consciousness, especially in computers\n",
              "* Turing believed this was a difficult but necessary problem to understand when dealing with AI\n",
              "* machines can't experience things the same way as humans but can still run code, is that really different\n",
              "\n",
              "\n",
              "## AIMA 2.1 Agents and Environments\n",
              "\n",
              "* An agents choice of action at any time can depend on its previous knowledge but nothing it hasn’t seen before\n",
              "* Agent function is a abstract definition while the agent program is the architecture implementation\n",
              "* Define agents to learn about the system, not every thing is an agent or a non agent\n",
              "\n",
              "\n",
              "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
              "\n",
              "* We need to establish performance measures because the machines have no point of view\n",
              "* Want to design performance measures towards what we want to achieve in an environment, not how we think the agent should get there\n",
              "* Rationality depends on the performance measure, the prior knowledge of the system, the actions possible, and the percept sequence to that point\n",
              "* Agent chooses an action to maximize the performance measure that is expected\n",
              "* Agent has to explore an environment if they are unfamiliar with it\n",
              "* Rationality does not equal perfection\n",
              "* Want the agent to both gather information and learn from it\n",
              "* Agent lacks autonomy since it relies on the designer to tell it what to achieve\n",
              "\n",
              "\n",
              "## AIMA 2.3 The Nature of Environments\n",
              "\n",
              "* Task environment defined by PEAS (performance, environment, actuators, sensors)\n",
              "* Tradeoffs often required in performance measures\n",
              "* The more restricted the environment, the design problem becomes easier\n",
              "* Virtual environments are just as complex as the real world, can have a software agent instead of a physical agent\n",
              "* Fully observable vs. partially observable - whether or not the sensors give the agent access to the entire environment at any given time\n",
              "* Also fully observable if the agent knows all things relevant to the action to be performed next\n",
              "* Unobservable environment created if the agent has no sensors to perceive the environment\n",
              "* Single agent vs. multiple agents important to keep in mind, can be competitive or cooperative\n",
              "* Deterministic vs. nondeterministic - whether or not the next state is determined entirely by the actions of the agent in the current state\n",
              "* Stochastic if it explicitly deals with probabilities versus nondeterministic \n",
              "* Episodic vs. sequential - whether or not it is divided into atomic episodes\n",
              "* Static vs. dynamic - whether or not the system can change while the agent makes a decision\n",
              "* If environment doesn’t change but performance score does, semidynamic\n",
              "* Discrete vs. continuous, does the state of the environment change when time is handled, does it affect the percepts or actions \n",
              "* Known vs. unknown - agents knowledge about physics of the environment, are the outcomes of the moves given for any action\n",
              "* Experiments carried out for many environments draw from an environment class\n",
              "\n",
              "\n",
              "## AIMA 2.4 The Structure of Agents\n",
              "\n",
              "* Agent architecture combines the agent program and agent function, to make the agent the architecture + program\n",
              "* Architecture makes the percepts from the sensors, runs the programs, then presents choices to make\n",
              "* Take in a percept and return an action to the actuators\n",
              "* Agent program only takes the current percept, agent function has the entire percept history\n",
              "* Need to be able to write programs to be rational from small programs instead of huge lookup tables\n",
              "* Reflex behaviors still occur in complex environments\n",
              "* Condition action rules in reflex agents, if something happens then react quickly with something else\n",
              "* Limited intelligence and only correct if the environment is fully observable\n",
              "* Can get stuck in infinite loops, or randomize its actions to get out of them\n",
              "* Model based reflex agetnts try to keep track of the previous world percepts\n",
              "* Need to know how the world changes over time, and how that is reflected in the agents percepts\n",
              "* Agent needs goal information to figure out where to go next\n",
              "* Search and planning used to determine how the agent should get to the goal\n",
              "* Utility agents have to distinguish between which world states make them happier\n",
              "* Agent chooses to maximize this utility measure\n",
              "* Agent has to choose the action that will yield the highest expected utility given the probabilities since it likely cannot always know what it will be\n",
              "* A model free agent can learn what action is best without learning how the environment changes as a result of it\n",
              "* Learning agent has a learning element that makes improvements and a performance element that makes actions\n",
              "* Learning element has a critic that tells how the agent is doing and how the performance element should be altered\n",
              "* Can give an award or penalty based on what actions the agent is taking\n",
              "* More expressive representations capture everything a less expressive representation does, often more concise\n",
              "\n",
              "\n",
              "## Module 1 Lecture Notes\n",
              "AI is the science of making machines that think like people, act like people, think rationally, and act rationally.\n",
              "* Rene Descartes - Principle of dualism - the mind or thinking itself is essentially incorporeal or spirital and that a mind exists separately from the body.\n",
              "* Alan Turing - Turing test - an evaluator judges a text based conversation between a computer and a machine, If the evaluator cannot tell the difference between the two, the machine passes the test. Are there imaginable digital computers which would do well in the imitation game?\n",
              "* John Seale - Application of rules to input symbols is not true intelligence, the Chinese Room. Contrasts strong AI with weak AI, argues that biological brains cause minds.\n",
              "Strong AI says the computer is a mind and can literally understand and have cognitive states, whereas weak AI just simulates thought, and their understanding isn't real understanding.\n",
              "* Daniel Dennett - Brain in a Vat, what makes this different from a computer processing symbols?\n",
              "Actually thinking versus simulating thinking is the main distinction in AI philosophy.\n",
              "\n",
              "Rational Agents:\n",
              "* focus in on acting rationally, and creating effective techniques for designing rational agents\n",
              "* An agent is anything that cna perceive an environment through sensors, and can act on its environment with actuators\n",
              "* A percept is the agent's inputs in the form of perceptions at a given time point.\n",
              "\n",
              "An agent is specified by an agent function (a mathematical abstract description) that maps f: P -> a , a sequence of percept vectors P to an action a from set A.\n",
              "\n",
              "P = [p0, p1, ... pt]\n",
              "A = [a0, a1, .. at]\n",
              "* An agent has sensors that perceive inputs from the environment in the form of percepts, then uses its actuators to perform actions in the environment.\n",
              "* The agent program (conversely to the agent function) runs on the architecture to produce f\n",
              "* The agent altogether is the archtiecture and the program\n",
              "\n",
              "Agent is anything that can be viewed as perceiving its environment with sensors and acting in that same environment with some form of actuators.\n",
              "* humans, thermostats, animals, roombas, robots, etc.\n",
              "A rational agent is any agent attempting to behave rationally in an environment where it perceives information. Related to consequentialism, doing \"the right thing\".\n",
              "\n",
              "Define a performance measure to see if the agent is acting rationally in the environment.\n",
              "* performance measure is a defined objective criteria for success of the behaior of the agent given the percepts as input.\n",
              "* Generally, it is better to design performance measures towards what you want the agent to achieve in the environment instead of how you think they should behave at a given point in time.\n",
              "* choose an action a for each possible input percept sequence P to maximize the performance measure.\n",
              "* In reality, the agent is not omniscient in the environment so we want to maximize the expected value of the performance measure based on the context that we have.\n",
              "\n",
              "Task Environments\n",
              "* For a given rational agent, we need to specify a task environment for which it is to find a solution.\n",
              "* PEAS: Performance Measure, Environment, Actuators, Sensors\n",
              "* Taxi example: P - safe, legal, maximize profits. E: roads, drivers, customers. A: brake, accelerator, gear shift. S: speedometer, odometer, rear camera.\n",
              "\n",
              "For a rational agent, the goal should be - given an environment defined with PEAS:\n",
              "1. Construct an agent function f (as an abstract mathematical description) to maximize the expected value of the performance measure\n",
              "2. Design an agent program (a concrete architecture implementation) to implement f.\n",
              "\n",
              "Things to consider:\n",
              "* Fully observable vs. partially observable (backgammon board vs. driving)\n",
              "* Deterministic (moves on a board) vs. nondeterministic (different results each time) vs. Stochastic (rolling a die)\n",
              "* Episodic (independent steps) vs. sequenatial (dependent steps)\n",
              "* Static (unchanging) vs. Dynamic (changing)\n",
              "* Discrete (stagnant) vs. Continuous (moving pieces around you)\n",
              "* Single vs. Multiple Agents\n",
              "\n",
              "Hardest environments are continuous, partially observable, stochastic, multiagent. \n",
              "Easier environments are static, fully observable, deterministic, discrete.\n",
              "* Reflex agents - agents that only select actions based on the current perception of information and ignore the history of the percepts\n",
              "* Problem solving agent - agents that plan ahead, consider sequence of actions towards a goal, a search.\n",
              "\n",
              "\n",
              "## Module 1 Definitions\n",
              "* **Standard model** - foundation of AI, trying to create agents that do the right thing\n",
              "* **Limited rationality** - when an agent makes the best decision possible in a constrained time environment\n",
              "* **Value alignment problem** - the objectives of the machine have to be in line with those of the human who designed it\n",
              "* **Turing test** - A test to deem whether or not a machine could think, could it make indistiguishable responses\n",
              "* **Total turing test** - Extension of a Turing test that requires computer vision and robotics to interact with the world\n",
              "* **Cognitive science** - interdisciplinary field that combines computer models and psychology to create theories about the mind\n",
              "* **Weak ai** - machines only act as if they are intelligent but are not inherently\n",
              "* **Strong ai** - machines are actually thinking consciously and not just simulating it\n",
              "* **Good old-fashioned ai** - simple logical agents criticized in early AI, couldn't capture all behaviors - qualification problem\n",
              "* **Embodied cognition** - doesn't make sense to separate the brain from the body, study the entire system\n",
              "* **Polite convention** - Turing's assertion that everyone thinks\n",
              "* **Chinese room** - Searle's thought experiment, no thinking being generated only transcription of symbols\n",
              "* **Biological naturalism** - says that mental states are high level features resulting form low level processes in neurons, which themselves don't matter\n",
              "* **Consciousness** - key point in AI, can the machine be aware of the world and experience living, do they have qualia\n",
              "* **Agent** - anything that can perceive and act in an environment with sensors, acts with actuators\n",
              "* **Percept** - what the agent is presented to perceive\n",
              "* **Percept sequence** - history of all of the percepts the agent has seen\n",
              "* **Agent function** - maps a percept sequence fed to the agent to an action\n",
              "* **Agent program** - the internal implementation of the agent function\n",
              "* **Rational agent** - any agent that acts to maximize the best outcome or best expected outcome if unsure\n",
              "* **Consequentialism** - agents performance is measure but the consequences of its actions\n",
              "* **Performance measure** - how we judge what the agent has done in an environment\n",
              "* **Omniscience** - agent knows everything about the system and its outcomes, not possible to achieve\n",
              "* **Information gathering** - collecting details about the environemtn to modify future percepts\n",
              "* **Task environments** - the problem spaces where we place agents to find solutions\n",
              "* **Simple reflex agent** - agents that select an action based only on the current percept\n",
              "* **Transition model** - knows how the world works for model based reflex agents\n",
              "* **Sensor model** - how the state is current expressed in the agents percepts\n",
              "* **Utility function** - an internal representation of the agents performance measure\n",
              "* **Problem generator** - suggests actions that leads to new environments that the agent can learn from\n",
              "* **Atomic representation** - every state of the world has no internal structure\n",
              "* **Factored representation** - splits a state up into variables and attributes with values\n",
              "* **Structured representation** - objects and their various relationships are described explicitly\n",
              "* **Localist representation** - concepts and memory locations have a one to one mapping\n",
              "* **Distributed representation** - concept spread across memory locations, each of which can have multiple concepts\n",
              "\n",
              "\n",
              "# Module 2: Python\n",
              "## Module 2 Lecture Notes\n",
              "\n",
              "Python Positive Features\n",
              "* Fast development, garbage collected with whitespace delimited syntax\n",
              "* Runs on major platforms without alterations\n",
              "* Built in types of lists, dicts, sets\n",
              "* Supported libraries of Numpy, Pandas, Sklearn, Pytorch, Tensorflow, etc. available for easy importing\n",
              "\n",
              "Simplest python program: print(\"Hello world\")\n",
              "\n",
              "Structure of a file:\n",
              "* Whitespace is meaningful, tab delimited or 4 spaces\n",
              "* Use a new line to end a line of code, or \\ to do so prematurely\n",
              "* Blocks are defined by the indendtation, colon appears at the end of a line starting a new block, subsequent blocks have more indentation if inside\n",
              "\n",
              "if expr: else:\n",
              "\n",
              "Objects\n",
              "* All data treated like an object, deleted once unreachable by garbage collection\n",
              "* Strong typing, interpreter doesn't allow incompatabilities with typings. Find out with type(object) and isinstance(object, type)\n",
              "* int, float, str, tuple, dict, list, bool, None, generator, function all first class objects\n",
              "\n",
              "Dynamic Typing  - variables aren't declared preemptively, come into existance when assigned, type determined and can be reassigned, fucntions have no signature. Typing errors have to be caught at runtime\n",
              "\n",
              "Math - Literals (integers, floats, booleans), operations (arithmetic, power (**), modulo (%), comparison, logic), assignment operators (+=, /=)\n",
              "\n",
              "Strings\n",
              "* single or double quote, can concatenate strings with +\n",
              "* can be prefixed with r to mean raw, and can print with % formatting e.g. print('%s can you count to %d' % (\"Sarah\", 1000))\n",
              "* IMMUTABLE\n",
              "* .split(), \"_\".join(words), .capitalize(), .upper(), .strip()\n",
              "\n",
              "Strings vs. Lists vs. Tuples:\n",
              "* Strings - immutable, == to check if they are the same, 'is' for if they are the same object, unicode or 2-byte chracters\n",
              "* Lists - mutable, y = x[:] to get shallow copy, deep copy also possible with import copy, can be mixed type objects\n",
              "* Tuples - immutable ordered sequence of items, can be of mixed type objects\n",
              "\n",
              "Slicing: t = ('a', 'b', 'c', 'd', 'e') [start:stop:step]\n",
              "* t[1:4] -> ('b', 'c', 'd')\n",
              "* t[1:-1] -> ('b', 'c', 'd')\n",
              "* t[1: -1: 2] -> ('b', 'd')\n",
              "* t[:2] -> ('a', 'b')\n",
              "* t[2:] -> ('c', 'd', 'e')\n",
              "\n",
              "List operations: a = [1, 2, 3, 4, 5]\n",
              "* a.append('b') -> [1, 2, 3, 4, 5, 'b']\n",
              "* a.insert(2, 'b') -> [1, 2, 'b', 3, 4, 5, 'b']\n",
              "* a.index(2) -> 1\n",
              "* a.count('b') -> 2\n",
              "* a.remove('b') -> [1, 2, 3, 4, 5, 'b']\n",
              "* a.sort(), a.reverse() operations in place, returns nothing\n",
              "\n",
              "Dictionaries - unordered hashes, keys must be immutable, constant average add, lookup, update\n",
              "* .keys(), .values(), .items() (item tuples)\n",
              "* A = {\"a\": '1', \"b\": 2}\n",
              "* d[\"a\"] -> 1\n",
              "* defaultdict automatically creates empty dictionary values\n",
              "\n",
              "Functions - beings with def, first line with less indentation outside function definition, return to send value back to caller\n",
              "* multiple return values allowed, not overloading allowed\n",
              "* default arguments allowed - def testfunc(a, b = 2, c = 'world'):\n",
              "* keyword arguments can be called out of order, but non-default arguments must come first otherwise syntaxerror\n",
              "* #args passes in variable number of non-keyword arguments\n",
              "* ##kwargs  passes in variable number of keyword arguments\n",
              "\n",
              "* Dynamic Scoping - function sees most current value of variables\n",
              "* Default parameter values only evaluated when def statement they belong to is first executed\n",
              "\n",
              "Class construction\n",
              "* Class Test - def __init__(self, name, input): ..., def func_2(self):\n",
              "* Subclasses - can extend the previous instantiation of another class, allows use of methods and attributes defined previous. class Test2(Test)\n",
              "* Can redefine a method of the parents class that will overwrite it, include the self argument\n",
              "\n",
              "Magic methods:\n",
              "* __init__: the constructor\n",
              "* __len__: how the len(obj) is defined\n",
              "* __copy__: how to copy a class\n",
              "* __cmp__: how == works\n",
              "* __add__: how + works for a class\n",
              "* __neg__: how unary negation works for class\n",
              "\n",
              "main function: if __name__ == '__main__': ...\n",
              "\n",
              "For loops:\n",
              "* For <item> in <collection>: <do statements>\n",
              "* can be tuples as well: for (x, y) in [(1, 2), (3, 4)]\n",
              "\n",
              "List Comprehension\n",
              "* list from 1 - 100: [x for x in range(1, 101)]\n",
              "* multiply by 2: [x * 2 for x in li]\n",
              "* Filtered divide: [x / 2 for x in li if x < 10]\n",
              "\n",
              "Iterators - iterable objects can be used in loops because they have __iter__ method\n",
              "* a = [1,2,3]\n",
              "* a.__iter__() produces iter object, iter(a) produces iter object\n",
              "* a.__next__() or a.next(), throws a stopiteration exception if it does not have a next element\n",
              "* Efficient in memory, do not return until called upon\n",
              "\n",
              "Generators - Iterators with __next__() method\n",
              "* use yield keyword to return a generator whenever they are called in a function\n",
              "* each time it is called, runs until it hits th enext yield statement, picks up next time where it left off\n",
              "* less code, local state maintained, computed as needed, doesn't store in memory, works for infinite sequences\n",
              "* if need to look at individual elements not as good.\n",
              "\n",
              "Imports - import packages using import <item>, from <item> import <function>, from <item> import *, import <item> as shorthand\n",
              "Pip - package installer for python, allows installation of external libraries\n",
              "\n",
              "\n",
              "\n",
              "## Module 2 Definitions\n",
              "* **Repl** - Read-Evaluate-Print Loop, type a sequence in and returns the evaluated expression\n",
              "* **Scripts** - Created text files run with python3 script.py, not REPL so need to use print\n",
              "* **First class objects** - Entity that can be dynamically created, destroyed, passed to a function, returned as a value, all rights of variable\n",
              "* **Duck typing** - establishes suitability of an object by determining presence of previous methods defined\n",
              "\n",
              "\n",
              "# Module 3: Search Problems\n",
              "## AIMA Chapter 3.1 Problem-Solving Agents\n",
              "\n",
              "* Goal formation: the person wants to get to Bucharest, makes this their goal. This goal will limit their movements and actions\n",
              "* Problem formulation: the person creates an abstract model of the environment, in this case a map of Romania with all of the cities and their distances\n",
              "* Search: before actually moving, they simulate the steps to take until a solution is found, will likely have to iterate through a bunch of them\n",
              "* Execution: the agent has created the best path and now goes down it to get to Bucharest\n",
              "* For a fully observable, deterministic, known environment we will have a fixed sequence of actions from the start to goal node\n",
              "* A search problem as the following:\n",
              "* Set of states (state space) that the environment can be\n",
              "* Initial state where the agent starts\n",
              "* Set of 1+ goal states, goal can be defined to be many different things\n",
              "* Actions available to get to the goal, each one is applicable in s\n",
              "* Transition model that describes what an action does\n",
              "* Action cost function that calculates the cost to make some action in a current state\n",
              "* Path is a sequence of actions that gets to our solution, with the optimal solution being the lowest path cost\n",
              "* Can be seen as a graph with directed edges as actions and states as nodes\n",
              "* Have to determine a level of abstraction that is valid so we can arrive at a solution, useful if it is easier than the original problem\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.2 Example Problems\n",
              "\n",
              "* Create a grid world of 2d space where the agents can move side to side and up and down\n",
              "* Vacuum world has the following setup\n",
              "* State: which objects are In each cell, agent and/or dirt\n",
              "* Initial state: any one can be chosen\n",
              "* Actions: suck, move left, or move right\n",
              "* Transition model: suck up dirt, move the agent forward for backward\n",
              "* Goal state: when everything is clean\n",
              "* Action cost: everything is 1\n",
              "* Sliding tile puzzle example:\n",
              "* states: any setup of the 1-8 tiles\n",
              "* Initial state: whichever setup of the tiles we pick to be the start\n",
              "* Actions: can slide up, down, left, right if possible\n",
              "* Transition model: if we move left, the tile in the position to move to the left actually goes there\n",
              "* Goal state: when the numbers are in order\n",
              "* Action cost: everything is 1\n",
              "* Touring problems are sets of places that have to be visited\n",
              "* VLSI layout optimal positioning is important with cell layouts and channel routings\n",
              "* Robot navigation, automatic assembly sequencing of complex objects, protein design all search problems\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.3 Search Algorithms\n",
              "\n",
              "* Representing search state space graphs as search trees, with the root as the initial point and each node in the tree corresponding to a search tree, edges are the actions to get tho that state\n",
              "* State space is the set of states in the world and actions that allow transitions, whereas the tree just describes paths to get to these states\n",
              "* Expand a node and get its children (or successor) nodes, previous node becomes the parent\n",
              "* Frontier for prioritizing what to look at next, call a node reached if its been expanded\n",
              "* A node in the tree has a state corresponding to it, a parent node, an action that got it there, and a path cost to get there from the initial state\n",
              "* Types of queues we consider: priority queue (minimum cost popped off first), FIFO (first in first out) queue, LIFO (last in first out, or a stack) queue\n",
              "* Trees have repeated states, or a cycle, redundant paths\n",
              "* If we don’t remember the past we’ll run into the same states over and over\n",
              "* Graph search keep track of the previous states and checks for redundant paths, although not always necessary/important\n",
              "* More memory but less redundant paths\n",
              "* We can check for cycles in tree search but redundancy hard to look for\n",
              "* Search must be systematic in some way in order to be complete\n",
              "* Depth is the number of actions to get to the optimal solution, or depth of the tree, m is the maximum number of actions in any path, not necessarily the optimal path, and b is the branching factor that estimates the number of successors for each node to look into\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
              "\n",
              "* FIFO queue faster than priority queue in BFS\n",
              "* BFS cost optimal when all actions have the same cost, complete in both cases\n",
              "* O(b^d) nodes generated, time and space the same\n",
              "* Memory requirements much bigger worry than execution time, cannot be solved for except in smallest instances\n",
              "* Djikstras/Uniform cost search evaluates the path cost to the current node, UCS has a goal state\n",
              "* Can be inefficient if explores large area with lose costs away from the goal node, never gets caught in single infinite path\n",
              "* DFS backs up when a goal isn’t found recursively, not cost toptimal\n",
              "* Efficient and complete in finite state spaces, can hit loops\n",
              "* Much better for memory, no reached table needed at all, small frontier\n",
              "* O(bm) complexity, b is branching factor and m is max depth of the tree\n",
              "* For backtracking to work we ned a way of undoing our modifications to the state\n",
              "* If we pick a bad L in depth limited search we are going to be inefficient\n",
              "* Iterative deepening optimal for when all actions have the same cost, O(b^d) when a solution exists and O(b^m) when it doesn’t \n",
              "* Iterative deepening generally preferred when search state space is larger than can fit in memory and the depth is unknown\n",
              "* Bidirectional has two frontiers and two tables of reach states, need to be able to reason backwards\n",
              "* Pass in 2 versions of the program and evaluation function for forward and reverse direction\n",
              "* When the first solution is found, it is guaranteed to be optimal if the evaluation function is the path cos\n",
              "* Bidirectional is complete if b is finite and both directions are breadth first or uniform cost\n",
              "* Optimal cost when all action costs are identical and both directions are breadth first or uniform cost\n",
              "\n",
              "\n",
              "## Module 3 Lecture Notes\n",
              "\n",
              "Reflex agent vs. Problem Solving Agent\n",
              "* Reflex agent ignores the past percept histroay and only makes an action based on the current percept\n",
              "* Problem Solving Agents plan ahead and perform a search to reach the solution state, execute a sequence of actions\n",
              "\n",
              "Task environment effects\n",
              "* If environment is fully oberservable, deterministics, known it is a sequence of fixed actions that won't change\n",
              "* If either partially observerable or nondeterministic the agent must be flexible with the percepts it receives before making a decision, branching strategy\n",
              "\n",
              "Search Problem components:\n",
              "1. States: a set S of possible states, with an initial state (1a) si that exists in S\n",
              "2. Actions: a set A of all possible actions that can be executed in s and are applicable\n",
              "3. Transition Model: the set of all states and all actions that exist, and their resulting successor states, denotes as s_r. The state space is comprised of the initial state and all successors\n",
              "4. Path Cost function: the performance measure that we are using to calculate the step cost, assuming its at least 0. The cost it takes from state x to state y using an action a.\n",
              "5. Goal state: The goals, s is a goal state if Goal(s) is true, can also be implicit.\n",
              "\n",
              "Formulating a Search Problem - how this is done affects the search space and the speed of search\n",
              "* Decide which properties matter versus others and how to represent each state in the environment\n",
              "* Decide which actions are possible and how we represent them in actions and transition models\n",
              "* Decide which path is next using the cost function\n",
              "\n",
              "Selecting a state space:\n",
              "* State space must be abstracted from the real world since it is very complex. State generally is a set of real-world staates\n",
              "* Action is a class of cominations of real-world equivalent actions\n",
              "* both of these are abstractions, so they should in theory be easier to solve than the real-world problem.\n",
              "\n",
              "State space terminology:\n",
              "* State space - set of all states reachable by any sequence of actions, can expand very quickly depending on how it was constructed\n",
              "* Path - how to get from one state to another state, and what actions led you there\n",
              "* Solution - a complete path from the initial state to the goal state\n",
              "* Search Tree - way to representing the paths with the initial state at the root, checks redundant nodes\n",
              "* Frontier - queue of what is to be explored next, available actions we can look at next\n",
              "* Optimal solution - optimal path from start to goal state with no possible lower cost of getting there\n",
              "\n",
              "Tree Search:\n",
              "* Go through every possible path from the initial state in some order, with the root as the initial state and all other states as leaves\n",
              "* Each path to the same node is distinct, so we may be checking for redundant paths\n",
              "* This failure to check the states can make a linear search problem become exponential\n",
              "\n",
              "State vs. Node: States are representations of physical configurations (like the game board itself), whereas nodes are the data structure of the part of a search tree, including its parent, children, costs, etc.\n",
              "\n",
              "Graph Search:\n",
              "* Attempting to improve upon tree search by storing whether or not a node has been visited before adding it to the frontier\n",
              "* Memory cost is greater than that of tree search but can make the search linear which is ideal\n",
              "\n",
              "Uninformed Search strategy ranks all nodes as equally favorable to explore, whereas an informed search ranks nodes in some uniform way\n",
              "\n",
              "Criteria for search strategies:\n",
              "* Strategy - how the tree is expeanded (queue, priority, etc.)\n",
              "* Completeness - whether or not a solution can always be found\n",
              "* Optimality - when a solution is found, is it always the lowest cost solution?\n",
              "* Time Complexity - how many nodes are generated in the exploration\n",
              "* Space Complexity - how many nodes are stored in memory simultaneously during exploration\n",
              "* b = maximum branching factor, d = depth of shallowest goal node, m - maximum length of any pace in state space\n",
              "\n",
              "Breadth-First Search (BFS)\n",
              "* Expand the nearest node first, and create a FIFO queue, putting any discovered nodes at the end of the frontier\n",
              "* look at each layer individually before moving to the next one, repeat in the next layer\n",
              "* Complete if b is finite, optimal if cost = 1 per step (although generally no), O(b^d) time complexity, O(b^d) space complexity to store all nodes\n",
              "* Very bad in situations with exponential complexity \n",
              "* use over DFS if infinite paths are possible, some solutions are short and you can get rid of bad paths\n",
              "\n",
              "Depth-First Search (DFS)\n",
              "* Expand the deepest node first, and create a LIFO queue, where any discovered nodes are at the front of the frontier\n",
              "* look at one node and go all the way down before moving to the next one, repeat with next node\n",
              "* Not complete (infinite depth, loops), not optimal, O(b^m) time complexity (bad if m >> d), O(b* m) space which is biggest win\n",
              "* Use over BFS if space is an issue and search can be altered quicktly, wrong solutions quickly discarded\n",
              "\n",
              "Depth limited search\n",
              "* DFS with a depth limit l, set beforehand. if l is at a depth less than the goal node then it is incomplete and not found, if its greater than d its inefficient and not optimal\n",
              "* Time complextity of O(b^l), space complexity of O(b * l)\n",
              "\n",
              "Iterative Deepening Search \n",
              "* Use depth first search at a depth limit set to l in each iteration, then increase it by 1, repeat\n",
              "* Makes the algorithm complete and optimal, because we always find the solution at a depth of d, the current maximum depth node\n",
              "* Time complexity is O(b^d), space is O(b * d), but now it's complete and optimal\n",
              "\n",
              "Algorithm Summary:\n",
              "BFS: Complete, Optimal, b^d time, b^d space\n",
              "DFS: Not Complete, Not Optimal, b^m time, b*m space\n",
              "Depth-limited: Not Complete, Not Optimal, b^m time, b*l space\n",
              "Iterative Deepening: Complete, Optimal, b^d time, b*d space\n",
              "\n",
              "\n",
              "\n",
              "## Module 3 Definitions\n",
              "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
              "* **Atomic representations** - states of the world in their entirety, no interal structures are visible\n",
              "* **Unknown environment** - no additional information available to the agent besides their current state\n",
              "* **Open-loop** - once a path is known the agent can ignore the percepts and execute the actions, breaks the agent-environment loop\n",
              "* **Closed-loop** - monitors the percepts while executing the actions, if there's a chance a mistake is made\n",
              "* **Model** - a mathematical description of the problem state, not the real world environment\n",
              "* **Abstraction** - when we simplify a representation so it has the appropriate amount of detail\n",
              "* **Standardized problem** - expresses problem-solving methods, a benchmark for algorithm research\n",
              "* **Real-world problem** - a problem with solutions that are actually used and unique to each environment\n",
              "* **Absolute movement actions** - up, down, left, or right\n",
              "* **Egocentric actions** - movements relative to the agent, turn left, turn right, forward, backward\n",
              "* **Traveling salesperson problem** - every city on the map has to be visited optimally\n",
              "* **Search algorithm** - looks at a search problem and returns a solution if one exists or a failure\n",
              "* **Best first search** - expand a node with the minimuum value for some evaluation function f(n)\n",
              "* **Completeness** - will we find a solution when it exists or correctly report a failure?\n",
              "* **Cost optimality** - will the solution we find be the lowest path cost?\n",
              "* **Time complexity** - Big O notation for how long it takes to reach a solution\n",
              "* **Space complexity** - Big O notation for how much memory is needed to find the solution\n",
              "* **Breadth first search** - root node expanded followed by all of its successors, and so on\n",
              "* **Early goal test** - in BFS, can check if a node is a solution when its generated\n",
              "* **Late goal test** - check to check if a node is a solution until its popped off the queue\n",
              "* **Depth first search** - explores the deepest node in the frontier first\n",
              "* **Backtracking search** - even less memory than DFS, one successor generated at a time, modifies current state instead of creating new ones\n",
              "* **Depth limited search** - DFS but only explore to a maximum depth l, pretend they have no successors\n",
              "* **Diameter** - the distance each node takes to reach any other node, good estimate for depth limited search\n",
              "* **Iterative deepening search** - depth limited by tries all values of L, combines DFS and BFS benefits\n",
              "* **Bidirectional search** - simultaneously looks forwards and backwards from the goal state hoping they meet up\n",
              "\n",
              "\n",
              "# Module 4: Informed Search\n",
              "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
              "\n",
              "* Greedy best first search is not cost optimal, complete in finite spaces but not infinite\n",
              "* Worst case time and complexity is O(V), with good heuristics can be reduced to O(bm)\n",
              "* A star search has estimated cost of the best path to the goal as the cost so far and the heuristic to get to the goal state\n",
              "* A* is complete, cost optimal depends on whether or not the heuristic is admissible\n",
              "* Heuristic is consistent if it satisfies  a triangle inequality, heuristic less than the cost of a move and that next heuristic\n",
              "* Every consistent heuristic is admissible (so cost-optimal), but not the other way around\n",
              "* Inconsistent heuristics never have to re-add a state to the frontier\n",
              "* With an inadmissible heuristic A* may or may not be cost optimal\n",
              "* Contours in the state space illustrate the search process\n",
              "* A* expands all nodes reached form the initial state where f(n) < C*, surely expanded nodes\n",
              "* Optimally efficient with consistent heuristic since it explores all nodes surely\n",
              "* Prunes away tree nodes not involved in a solution\n",
              "* Number of nodes to expand can be exponential in length of the solution\n",
              "* Main issue with A* is memory concerns\n",
              "* Can seep reference counts for number of times a state has been reached\n",
              "* If a current node exceeds f_limit in RBFS, it backs up to the next path with the backed-up value\n",
              "* RBFS more efficient than IDA* slightly, but node regeneration still a problem\n",
              "* RBFS is optimal with admissible heuristic, space complexity linear in depth of optimal solution\n",
              "* IDA* and RBFS use too little memory\n",
              "* SMA* only regenerates subtree when all other paths are worse than the one its forgotten\n",
              "* Expands the newest best leaf and deletes oldest worst leaf in case of ties\n",
              "* Complete if there is a reachable solution, optimal if optimal solution is reachable otherwise returns best reachable ones\n",
              "* Useful on easy problems, struggles on more difficult ones, thrashes between candidates\n",
              "* In bidirectional heuristic search, need to look at pairs of nodes to be expanded, heuristics of forward and backward functions\n",
              "* Sometimes more efficient than unidirectional search, sometimes not\n",
              "* If we have a good enough heuristic, A* generally the best choice\n",
              "\n",
              "\n",
              "## AIMA Chapter 3.6 Heuristic Functions\n",
              "\n",
              "* For 8 tile puzzle, can use number of misplaces tiles or Manhattan distance as a heuristic\n",
              "* Better way may be to reduce effective depth by constant compared to the true depth\n",
              "* If one heuristic is always better than another, we say it dominates it, h2 dominates h1, h2 >= h1\n",
              "* A relaxed problem can be a good heuristic as well if we let some of the rules be ignored\n",
              "* Cost of the optimal solution to this relaxed problem is admissible for the original problem\n",
              "* If we have several heuristics, pick whichever one is more accurate on that exact node\n",
              "* Admissible heuristics can also be derived from solution costs of subproblems of a particular problem\n",
              "* Pattern databases store the solution costs for these subproblem instances \n",
              "* Sum of two costs is still a lower bound on the cost of solving the entire problem so its a disjoint pattern database\n",
              "* Precomputation of optimal path costs allows faster finding of optimal solutions\n",
              "* Alternatively choose a few landmark points then compute the optimal path cost from one to another\n",
              "* Will either be optimal if it goes through all landmarks or overestimate the cost, not admissible\n",
              "* Can also add shortcuts that cut though with artificial edges\n",
              "* Differential heuristics have subtraction in them, can be efficient and admissible\n",
              "* Spread the landmarks out to be more efficient \n",
              "* Metalevel learning algorithm learns from missteps to avoid exploring non promising subtrees in the future\n",
              "\n",
              "\n",
              "## Module 4 Lecture Notes\n",
              "\n",
              "From search, we have our root node = start node, expanded nodes, frontier of nodes to explore. We have to choose a leaf node from frontier to expand depending on the search stratetgy of the algorithm.\n",
              "\n",
              "Uniform Cost Search\n",
              "* a tree search algorithm (checks redundant paths) used for traversing weighed trees, structures, or graphs\n",
              "* Basically Djistra's algorithm but with a goal state\n",
              "* previously all of our search algorithms had a step cost of one, varying that here. g(N) previouslt was the depth of the search tree\n",
              "* g(N): path cost function, assigning some unique costs to each step in a path\n",
              "* C(i, j)- cost of going from node i to node j\n",
              "* Going from node 0 to node 2 - g(N2) = C(0, 1) + C(1, 2)\n",
              "* extends node with the lowest path cost ordered by g(N) in the frontier, similar to BFS\n",
              "* Tests whether or not a node is the goal state when it is popped off the queue for expansion, NOT when added to the frontier\n",
              "* A node is updated on the frontier if a better path to the same point is found\n",
              "* BFS explores equally in all directions with the FIFO queue, smooth contour search\n",
              "* UCS prioritizes which paths to explore, favors lower path costs and gives a priority queue, cost contour but still optimal\n",
              "* Can expand the wrong way away form our goal state, thus we want a node expansion based on estimate with distance to the goal\n",
              "\n",
              "Best first search\n",
              "* Node that is next for expansion selected based on an evaluation function f(n) that is the distance to the goal esimation\n",
              "* Sort the frontier by f(n), leads to greedy search and A* search.\n",
              "\n",
              "Heuristics:\n",
              "* An educated guess that limits the search for solutions in domains that are difficult to understand.\n",
              "* Useful but not necessarily corret, algorithsm provide heuristic knowledge to solve a problem\n",
              "* h(n) takes the current state n and returns an estaimte of the distance to the goal state, straight line distances are useful and simple\n",
              "\n",
              "Admissiblility:\n",
              "* A heuristic is admissible if it is optimistic and never overestimates the cost to reach the goal node\n",
              "* for all nodes n in a system, h(n) <= h*(n) where h*(n) is the true cost, and h(n) >= 0 \n",
              "* inadmissible heuristics violate optimality, good plans trapped on frontier\n",
              "* admissible heuristics slow down bad ideas, never outweigh good paths\n",
              "* a problem with fewer restrictions on the actions is called a relaxed problem\n",
              "* cost of optimal solution to a relaxed problem is an admissible heuristic for the original one\n",
              "* h(n) is the cost of an exact solution to a relaxed problem, allow some of the rules to be broken\n",
              "\n",
              "Dominance:\n",
              "* if h2(n) >= h1(n) for all nodes n, and both are admissible, then h2 dominates h1\n",
              "* h2 is therefore optimistic and more accurate than h1, so its better to use as a heuristic\n",
              "* h*(n) is the oracle heuristic, the true distance, this and the teleporting heuristic are both admissible\n",
              "* h*(n) dominates all other heuristics and h teleport is dominated by all other heuristics\n",
              "\n",
              "Greedy best-first search: set f(n) = h(n)\n",
              "* only expand the node that is estimated to be the closest to the goal and completely ignore g(n), the cost to get to that node\n",
              "* could be a straight line heuristic (L2 distance), manhatten distance in the grid world\n",
              "* Not optimal, can find shorter optimal paths\n",
              "* Not complete, can get stuck in loops if the heuristics are set a certain way\n",
              "\n",
              "A* search - f(n) = g(n) + h(n)\n",
              "* avoid extending paths that are already expensive while also expanding the most promising first, implement in frontier priority queue by increasing f(n)\n",
              "* g(n) is the actual cost so far to reach the current node\n",
              "* h(n) is the estimated cost to get from the current node to the goal\n",
              "* f(n) is the total cost of the path through n to the goal node\n",
              "* if h(n) is an admissible heuristic, this is optimal with tree search\n",
              "* 8 puzzle, set our heuristic to be the manhatten distance or the number of out of place tiles, the former gives a better estimate\n",
              "* will be faster in general than UCS\n",
              "* UCS expands equally in all directions, whereas A* will mainly expand towards the goal and hedges to make sure its still optimal\n",
              "* Applications in path finding, motion planning, games, etc.\n",
              "\n",
              "\n",
              "\n",
              "## Module 4 Definitions\n",
              "* **Informed search strategy** - a search strategy using domain speific hints and goal locations\n",
              "* **Heuristic functions** - estimated cheapest path from a current node to the goal state\n",
              "* **Greedy best first search** - Best first search that expands only with the lowest h(n) value\n",
              "* **Straight line distance** - a heuristic in path finding that is a straight line to the goal\n",
              "* **A* search** - Most common informed algorithm, f(n) = g(n) + h(n), path cost + heuristic\n",
              "* **Admissibility** - a heuristic that never overestimates the cost to reach the goal, optimistic\n",
              "* **Consistency** - a heuristic is consisten if for every known\n",
              "* **Monotonic** - g costs always increase as you go along a path, cost is always positive\n",
              "* **Satisficing solutions** - if we explore fewer nodes with an inadmissible heuristic and accept suboptimal solutions\n",
              "* **Weighted a* search** - weight the heuristic value more heavily, f(n) = g(n) + W * h(n)\n",
              "* **Bounded suboptimal search** - look for solutions guarenteed to be within a factor W of the optimal cost\n",
              "* **Boiunded cost search** - look for solutions with cost < come C\n",
              "* **Unbounded cost search** - accept any solution of any cost as long as we find it quickly\n",
              "* **Speedy search** - version of best first search that estimates the number of actions to reach a goal\n",
              "* **Beam search** - limits the size of the frontier, keep best socres and discard the others\n",
              "* **Iterative deepening a* search** - cutoff is the g + h cost, smallest fcost in previous iteration is the cutoff value at each depth\n",
              "* **Recursive best-first search** - Like a recursive DFS, but uses f_limit to keep track of the f-value of best alternative path\n",
              "* **Simplified memory bounded a*** - proceeds like A* expanding best leaf until memory is full, drops worst leaf\n",
              "* **Front to end search** - heuristic that estimates the distance to the goal and another that meausures distance to start\n",
              "* **Front to front** - estimates the distance to the other frontier in bidirectional heuristic search\n",
              "* **Effective branching factor** - quality of a heuristic metric, branching factors that a uniform tree at depth d needs for N-1 nodes\n",
              "* **Meta-level state space** - each state captures internal state of a program searching an ordinary search space\n",
              "* **Object level state space** - each state looking at the ordinary state space itself, map of Romania e.g.\n",
              "\n",
              "\n",
              "# Module 5: Adversarial Search and Games\n",
              "## AIMA Chapter 5.1 Game Theory\n",
              "\n",
              "* Pruning makes search more efficient by ignoring portions of the tree that don’t affect the result\n",
              "* Actions referred to as moves, positions for states\n",
              "* A game has an initial state (how the game is set up), who’s move it is, the list of legal moves for that person, the result of the move with a transition model that defines the state that results from the move, is-terminal with a terminal test to see whether or not the game is ended, and a utility defined by a utility function that gives values to players in each state or at the terminal state\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
              "\n",
              "* Max wants to maximize their own score, min wants to minimize the score that max can achieve\n",
              "* Always assume the other player makes the optimal move in minimax\n",
              "* Recursive algorithm that goes down to the leaves then backs up the minimax values of the tree as the recursion returns\n",
              "* Run the utility on the leaf nodes to get the values to pass back up in recursion\n",
              "* Depth first search, time complexity of O(b^m), space complexity O(bm)\n",
              "* If more than two players, replace single value with vector of values for each utility\n",
              "* Alliances in multiplayer games affect which node is chosen in minimax\n",
              "* In alpha beta pruning, minimax decision is independent of the values of the leaves in some cases, pruned\n",
              "* If a player has a better choice at the same level or any point higher up in the tree, it doesn’t need to explore it, prune it there\n",
              "* Alpha is the value of the best choice we have found so far along the path for MAX, at least alpha\n",
              "* Beta is the value of the best choice we have found so far along the path for MIN, at most beta\n",
              "* Prunes as soon as it is worse than alpha or beta at any state, meaning different directions\n",
              "* If perfect, would only need to look at O(b^m/2) compared to O(b^m) for minimax, doesn’t happen every time but can get decently close\n",
              "* Can use iterative deepening with this search method to improve selection and reduce memory\n",
              "* Repeated states in game search trees recorded in a transposition table that looks at heuristic values of states\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
              "\n",
              "* Can cut searches early and apply heuristic evaluation functions to states\n",
              "* Cutoff tests used for deciding when to stop looking at a certain branch of the tree\n",
              "* Can only get an estimate of the expected utility of a state to the player, just like in estimated distances in search trees\n",
              "* Most evaluation functions look at features of the state and weigh them to get some value that it can compare across states, also referred to as a weighted linear function, at each position we say how important a certain feature is and sum them up to get a value (in chess)\n",
              "* This assumes the contribution of each feature is independent of the values of others, not true in many games, need to use nonlinear combinations as well\n",
              "* Tell alpha beta pruning that if some evaluation function is true then stop looking at that branch\n",
              "* Evaluation function should only look at positions with no pending moves (quiescent) that would greatly affect the resulting value\n",
              "* Forward pruning is a type b strategy to save computation time\n",
              "* Use beam search to mitigate this, look only at one string of best moves instead of all of them\n",
              "* PROBcut prunes things that were probably prunable as opposed to provably prunable \n",
              "* Late move reduction says that moves that appear later are less likely to be good moves, reduce the depth that we look at these nodes instead of completely pruning them\n",
              "* If they come back promising we can always extend them and look further\n",
              "* Computer can completely solve some tasks with a policy that maps the best next state from a current state\n",
              "* Does so with retrograde minimax, look at all possible solutions then work backwards\n",
              "\n",
              "\n",
              "## AIMA Chapter 5.5 Stochastic Games\n",
              "\n",
              "* Stochastic games include a random element as well\n",
              "* Game trees in stochastic games need to include chance nodes in addition to MAX and MIN nodes\n",
              "* At best, can pick the highest expected value of a position, or the average of all possible outcomes\n",
              "* Compute the probability of the expected value as the sum of all values weighted by probability over the number of nodes\n",
              "* Evaluation function must return expected values that are the probability of winning, harder to prune\n",
              "* Takes O(b^m * n^m), where n is the number of distinct rolls of a dice and m is the max depth of a tree\n",
              "* If we bound the value of the children, we can get an idea of the average without looking at all of the children\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
              "\n",
              "* Agent has to make actions but is unsure of which one, so it assigns probabilities\n",
              "* Work to choose which action based on the desirability of their immediate outcomes, assuming an episodic environment\n",
              "* Captured by a utility function and want to maximize the expected utility\n",
              "* Maximum expected utility theory says a rational agent should pick the action that generates the highest expected utility\n",
              "* If an agent acts to maximize this utility function that is correctly calculated, it will achieve the highest possible score performance\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
              "\n",
              "* Say that one agent either prefers A over B, indifferent between the two, or prefers or is indifferent between them\n",
              "* A and B could be states of the world, usually some uncertainty in there, think of each set of outcomes as a lottery\n",
              "* Six constants we require for a preference relation to obey\n",
              "* Orderability - given two choices, an agent must prefer one, the other, or equally preferable, cannot avoid making a decision\n",
              "* Transitivity - if an agent prefers A to B and prefers B to C, must prefer A to C\n",
              "* Continuity - if B is between a and c in preference, some probability where the agent is indifferent between getting B and the probability of getting A with probability p and c with 1 - p\n",
              "* Substitutability - if indifferent between A and B, need to be indifferent between more complex options that are the same except B is substituted for A somewhere\n",
              "* Monotonicity - If two lotteries have A and B outcomes and A is preferred, then agent must pick which one gives a higher probability to A\n",
              "* Decomposability - Compound lotteries can be reduced to more basic representations using probability\n",
              "* If these are violated, agent behaves strangely in some way\n",
              "* Existence of a utility function - if preferences are aligned then there’s some function U that gives a higher value to A over B if A is preferred to B, or makes them equal if they are indifferent\n",
              "* Expected utility of a lottery - utility of the lottery is the sum of the probability of the outcome * utility of the outcome\n",
              "* Agent only needs an ordinal utility function, or a ranking of the choices, doesn’t care about what the associated values are\n",
              "\n",
              "\n",
              "## AIMA Chapter 16.3 Utility Functions\n",
              "\n",
              "* Preference elicitation lets the human decide what the utility function should be by presenting a bunch of choices and observing what decisions are made\n",
              "* Normalized utilities use a scare of 0 to 1, with 0 being the worst possible thing and 1 being the best possible outcome\n",
              "* Give the agent the utility scale and say to choose between the utility of an object and the standard lottery, adjust it until the agent is indifferent between the two and you get the expected utility\n",
              "* Can look at tradeoffs and at some point a value is placed on decisions\n",
              "* Use micromorts in insurance, one in a million chance of death\n",
              "* QALY is quality adjusted life year for patients receiving treatment\n",
              "* Generally agents have a monotonic preference for more money\n",
              "* Expected monetary value is each outcome probability multiplied by the associated reward\n",
              "* Risk averse agents prefer a sure thing rather than a game\n",
              "* Risk-seeing agents large risks for monetary gain, usually have some amount of debt\n",
              "* Average an agent will accept instead of a chance event is the certainty equivalent \n",
              "* Difference between the EMV and certainty equivalent is called the insurance premium \n",
              "* Agents with linear curves in wealth relative to current wealth are risk neutral\n",
              "* Optimizers curve is the estimated expected utility of the best choice being too high \n",
              "* Normative theory says how a rational agent should act, describe theory is how actual agents really act, like humans\n",
              "* Certainty effect says people are strongly attached to certain gains\n",
              "* People go with certain probabilities rather than unknowns, ambiguity aversion\n",
              "* The way a decision problem is worded affects it as well, framing effect\n",
              "* People prefer relative utility judgments as well, anchoring effect\n",
              "* Evolutionary psychology investigates these irrationalities further\n",
              "\n",
              "\n",
              "## Module 5 Lecture Notes\n",
              "\n",
              "Simplest game environment - Multiagent, static (no changes while deliberating), discrete (finite state of percepts/actions), fully observable (can see entire environment, perfect information), strategic (next state determined by current state and action of one agent then the other)\n",
              "\n",
              "Our games - two players alternate moves, zero-sum (one players loss it the others gains), set of moves, well defined win/loss/draw outcome\n",
              "\n",
              "Card games - stochastic, not deterministic, not fully observable\n",
              "\n",
              "Real time strategy - continous instead of discrete, no break between actions\n",
              "\n",
              "Game setup\n",
              "* Two players MAX and MIN, MAX goes first\n",
              "* MAX always tries to maximize their turn, MIN tries to minimize the turn of MAX\n",
              "* take turns until the game is over, winner get award, loser penalty\n",
              "* Initial state (board configuration), successor functions (legal move lists), terminal state, utility function (numerical value to terminal states), search tree to determine next move\n",
              "\n",
              "Making a move\n",
              "* Look at all legal moves (successors) to the current board position\n",
              "* Evaluate each successor board poision, pick the one that leads to the best ne, repeat after your opponent does the same thing\n",
              "\n",
              "Game Trees - represent game problem by a tree, nodes are board positions, edges are the moves that can be made, root is the first position to make a move, leaves are terminal states\n",
              "* Can try to assign evaluation function f to real number scores to current position without how it got there\n",
              "* Can give scores to the output boards depending on how desirable they are\n",
              "* f(n) evaluation function is static features of board alone\n",
              "* f(n) > 0 if MAX is winning, 0 if tied, < 0 if MIN is winning\n",
              "\n",
              "Max & Min\n",
              "* MAX is the perspective we look from, try to maximize their outcome\n",
              "* Min attempts to minimize MAX's outcome\n",
              "* root is level 0, max foes first, MAX has even levels, MIN has odd levels\n",
              "\n",
              "Minimax\n",
              "* make the best move for MAX assuming MIN always makes the best move for them\n",
              "* can recursively compute, the backed up value of node is the optimal value of its children\n",
              "* MAX this means backed up value is the max of its children, MIN is min of its children\n",
              "* until game terminates, start with MAX node, expand a given number of moves, apply evlaution function, calculate backed up values, pick the optimal move, let min respond\n",
              "* minimax value is the best achievable move against a rational opponent\n",
              "* Even if min doesnt play optimally, max plays even better then since it assumes the worst case scenario if they played correctly\n",
              "\n",
              "Alpha-Beta pruning\n",
              "* minimax but keep track of alpha and beta values\n",
              "* alpha is MAX's current lower bound on MAX's outcome, MAX will never allow a move that could lead to a worse move than alpha\n",
              "* beta is MIN's current upper bound on MINs outcome, MIN will never allow a move that could lead to a better move than beta\n",
              "* When evaluating a MAX node, a value is greater than beta, can stop because MIN will never select it\n",
              "* When evaluating a MIN node, a value less than alpha, can stop because MAX will never select it\n",
              "\n",
              "Expectimax - when we have to deal with uncertain outcomes with chance instead of just the opponent\n",
              "* Randomness either through explicitly random, an opponent who acts irradically, or an action that may fail\n",
              "* now instead want to calculate the average-case (expectimax) outcomes instead of the worst case (minimax) outcomes\n",
              "* Compute the average score under optimal play, MAX nodes are the same as before, chance nodes are like MIN but uncertain outcome so we calculate the expected utility\n",
              "* have some model of probabilities for how the opponent will move in a state, could be uniform distribution, complicated computation, chance nodes, traditional adversarial response\n",
              "* in our environments we have all probabilities with chance nodes that specify distribution\n",
              "* Objectivist (frequentist) - average over repeated experiments, assertsion how future iterations will go, new evidence changes the reference class, more in line with inherently random things\n",
              "* Subjectivist (Bayesian) - degrees of belief about unobserved variables exist, learn probabilities from the past experiences and new evidence updates the beliefs. Agent believes certain things based on the state or percepts\n",
              "\n",
              "Probability\n",
              "* Random variable, represents an event with an unknown outcome, probability distribution is an assignment of weights to the outcomes\n",
              "* always have non-negative probabilities, and always have to sum to one. May change as more information is gathered\n",
              "* Expected value of the random variable function is then the average weighed by the probability of the outcomes\n",
              "* can get slow quickly if need to calculate the opponent and then they have to calculate you back, minimax helps solve this a bit\n",
              "\n",
              "Expectiminimax - environment is extra random agent player that moves after each min/max move, results in nodes that compute the appropriate combination of the child values\n",
              "\n",
              "\n",
              "## Module 5 Definitions\n",
              "* **Evaluation function** - some measure of who is winning, based on the features of the current state\n",
              "* **Perfect information** - fully obserable environment\n",
              "* **Zero sum games** - what is good for one player is bad for the other, no win win outcomes possible\n",
              "* **State space graph** - graph where states are vertices, moves are edges, different states can be reached with multiple paths\n",
              "* **Game tree** - a complete search tree that follows every possible sequence of moves to the terminal state\n",
              "* **Ply** - one move by one of the players, not for both players\n",
              "* **Minimax** - optimal strategy in a search tree given that both sides play optimally\n",
              "* **Minimax decision** - what move is ultimately chosen at the root when we calculate all of the minimax values\n",
              "* **Alpha-beta pruning** - look at values of alpha and beta and prune branches of the tree that won't contribute\n",
              "* **Type a strategy** - wide but shallow, looks at all moves to a certain depth in search game tree\n",
              "* **Type b strategy** - deep but narrow, ignore moves that look bad and following promising paths\n",
              "* **Quiescence search** - only look at certain moves that won't greatly swing the evaluation function\n",
              "* **Horizon effect** - when program is facing a bad move from the opponent and it ultimately inevitable but it tries to delay\n",
              "* **Singular extensions** - mitigate horizon effect with clearly better moves than all others in a position even if cut off\n",
              "* **Forward pruning** - prun moves that look bad but may be good ones, could be done in error\n",
              "* **Expectiminimax** - minimax game trees with chance nodes, generalization for deterministic games\n",
              "\n",
              "\n",
              "# Module 6: Constraint Satisfaction Problems\n",
              "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
              "\n",
              "* Constraint satisfaction consists of a set of variables X, a set of domains D for each variable, and a set of constraints C that allow a combination of values\n",
              "* Each domain allows a set of values for a given variable, relations define the constraints for each pair\n",
              "* Solution to a CSP has to be complete and consistent\n",
              "* Australia map coloring, have a set of variables X to be regions, domains are colors, constraints are no touching countries can be the same color\n",
              "* Constraint graphs help to visualize these relationships\n",
              "* Check on each assignment whether it is a goal or not\n",
              "* Discrete, finite domains make up the easiest CSPs\n",
              "* Discrete domain can still be infinite (numbers, strings)\n",
              "* Special solutions exists for linear constraints on integers, where each variable appears in linear form, but not for nonlinear constraints, undecidable\n",
              "* Continuous domains are common in the real world as well, linear programming, Hubble space telescope\n",
              "* Binary CSP only has unary and binary constraints, can be represented as a graph\n",
              "* Can convert an n-ary CSP to binary using dual graphs, creating a new graph for one variable for each constraint in the original graph and one binary constraint for each pair of constraints\n",
              "* Can apply costs to the assignments and turn them into constraint optimization problems\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
              "\n",
              "* Xi is arc consistent to Xj if every value in domain Di there’s some variable in Dj that satisfies the binary constraint on the arc.\n",
              "* Graph is arc consistent if every variable is arc consistent with each other\n",
              "* AC-3 maintains a queue of arcs to look through\n",
              "* Initially all arcs in the CSP, pops one off, makes it arc-consistent Xi with Xj. \n",
              "* If the domain is the same we move on, if the domain is smaller we put all arcs Xk Xi back in for all neighbors\n",
              "* If a domain goes to nothing, we have a failure and we need to return false\n",
              "* O(d^2) time to check an arc, and O(cd^3) total worse case where c is the number of arcs and d is the number of times an arc can be inserted into a queue\n",
              "* Path consistent Xi Xj with a third variable Xm if for every assignment consistent with Xi Xj there’s an assignment with Xm such that Xi Xm and Xm Xj are satisfied\n",
              "* A CSP is k-consistent if for any set of k - 1 variables with any consistent assignments, a consistent value can always be assigned to any 4th variable\n",
              "* CSP is strongly k-consistent if it is k consistent, k - 1 consistent, k - 2 consistent, … down to 1 consistent\n",
              "* Can’t represent all domains sometimes, so we do bounds propagation, set a min and max bound on the domains\n",
              "* Bounds consistent if for each variable X for lower and upper bounds there’s a value of y that satisfies the constrains between x and y\n",
              "* Sudoku is very popular CSP\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
              "\n",
              "* Often still have to perform a search after constraining with backtracking\n",
              "* CSPs are commutative which is key, doesn’t matter which order we assign things, so only need to look t one variable in each node \n",
              "* Number of leaves in depth limited search is now d^n\n",
              "* Backtracking can be improved with domain independent heuristics that take advantage of factored representation\n",
              "* Which variable should be assigned next, select unassigned variable default is just pick them in order, or randomly\n",
              "* MRV heuristic is most constrained variable, most likely to fail soonest \n",
              "* Degree heuristic reduced branching factor by selected variable involved in larger number of constraints on other variables, if the MRV is tied\n",
              "* Least constraining value good for which order to examine, prefers value that rules out the fewest choices for the neighbors\n",
              "* Forward checking - whenever a variable is assigned, forward checking establishes arc consistent for it\n",
              "* Get better results if we combine MRV with forward checking\n",
              "* MAC (maintaining arc consistency) detects consistencies early.\n",
              "* Assign a variable Xi a value, inference procedure calls AC-3 starting with the arcs Xj Xi for each unassigned neighbors of Xi, more powerful than forward checking\n",
              "* Forward checking doesn’t recursively propagate constraints like MAC\n",
              "* Keep track of assignments that conflict with some value, called the conflict set, then backup to the most recent assignment in the conflict set\n",
              "* Backjumping algorithm that uses conflict sets is called conflict-directs backjumping\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.4 Local Search for CSPs\n",
              "\n",
              "* Local search algorithms good in solving CSPs, N-Queens for example\n",
              "* Min conflicts heuristic is selecting a value that gives the minimum number of conflicts with other variable\n",
              "* Tabu search keeps a list of recently visited states handy and forbid the return to those states\n",
              "* Constraint weighing weights the variable/value pairs different so concentrate on the important bits of search\n",
              "* Local search all can be used in online setting when the problems change\n",
              "\n",
              "\n",
              "## AIMA Chapter 6.5 The Structure of Problems\n",
              "\n",
              "* Decompose into simpler problems, if we have independent subproblems can solve those first\n",
              "* Independence found by identifying connected components of the constraint graph\n",
              "* Constraint graphs are trees when any two variables are connected by only one path, then can be solved in linear time with the number of variables\n",
              "* Directional arc consistency if we look at arc consistency in one direction\n",
              "* Topological sort used when we pick a variable to be the root of the tree and order the variables outside of that\n",
              "* Don’t need to backtrack then, just move through the variable orderings\n",
              "* Cutset conditioning algorithm: choose a subset of the variables so that the graph is a tree when S is removed, S is a cycle cutest\n",
              "* For each assignment to variables in S that satisfies all constraints, remove from the domains of remaining variables any inconsistent values, and if it has a solution return it with S assignment\n",
              "* Tree decomposition transforms the graph itnto a tree where each node consists of a set of variables\n",
              "* Decomposition must have every variable in at least one of the tree nodes, if two variables are connected in the original problem they must be in at least one of trees, and if a variable appears in two nodes in the tree it must be in every node along the path connecting the nodes\n",
              "* Tree width of the decomposition is one less than the size of the largest node\n",
              "* Tree width of graph is minimum width of tree decompositions\n",
              "* CPSs with bounded tree widths are solvable in polynomial time\n",
              "\n",
              "\n",
              "## Module 6 Lecture Notes\n",
              "\n",
              "Purpose of search\n",
              "* Assume in our world we habe a single agent, deterministic actions, fully obseravle, discrete actions\n",
              "* planning involves creating a sequence of actions to get to the goal, with costs and depths, heuristics\n",
              "* identify assignments to variables, do not care how we reach the goal\n",
              "\n",
              "Constraint Satisfaction Problems\n",
              "* want to represent constraints that solutions have to satisfy in some language, make them general purpose search algorithms \n",
              "* if they are general purpose then we can specify a problem in some language and the algorithm still works\n",
              "* in a CSP we have finite set of variables X1, X2, ..., Xn, nonempty domain of values for each variable D1, D2, .. where Di = {v1, ..., vk}, finite set of constraints C1, ... Cm\n",
              "* a constraint limits the values that the varibales can take according to some rules, and a state is defined as the assignemtn of these values to the variables.\n",
              "* An assignment is consistent if it doesn't violate the constraints, sudoku, color mapping, scheduling problems\n",
              "* complete assignment is achieved when every variable is assigned a value\n",
              "* a solution has to be both complete and consistent, solutions. found using these general purpose algorithms, maximizes some objective function\n",
              "\n",
              "Map coloring example\n",
              "* have a map and can assign each country or area as a variable, domains initially are all possible colors, constraints are touching regions have to have different colors\n",
              "* how many colors are required to create a complete and consistent assignment (solution)\n",
              "\n",
              "Advantages\n",
              "* create a generic goal, successor function, and heuristics, and clean specifications can be created from them\n",
              "* the CSP can check when the variables violate a constraint with forward checking\n",
              "* prune off branches where constraints are violates as the variables are assigned values\n",
              "\n",
              "Representations\n",
              "* Graphs, where nodes are variables and the arcs are binary constraints\n",
              "* standard representation pattern which provides variables with values\n",
              "* Constraint graphs which can simiplify searches by creating independent subproblems, nodes are the variables and edges are the constraints\n",
              "* Binary CSPs where each constraint is related to two of the variables in the environment.\n",
              "* Discrete variables can have finite domains (n variables, domain size d leads to O(d^n) complete assignements, like Boolean CSPs), or infintie domains (strings, integers, start/end days for something, requires consistent language)\n",
              "* Continuous variables harder to define, start and end times for things that are constantly occurring.\n",
              "* Unary constraints involve a single variable, Binary is a pair of variables, Higher-order is 3 or more variables, can also have preferences (soft constraints) which can be enforced or not depending on rigidity of constraint.\n",
              "\n",
              "CSP as a search problem\n",
              "* if we express CSP as a search problem (initial state is empty assignment, sucessor function is next unassigned variables, goal test is when complete and consistent, path cost is the cost to assign a variable), then a solution is always found at depth n for n variables\n",
              "* Can try depth first search. If we try to expand one assignemnt per layer, we get n variables of domain size d, n*d branching at the root, n-1 * d branching at next level, n! * d^n leaves, becomes very expensive.\n",
              "* can take advantage of commutativity, the states can be assigned in any order, only need to then look at one assignment per node, so b = d with d^n leaves\n",
              "* DFS for the CPS refereed to as backtracking, when we cannot assign any legal moves we move back up the tree until we can again, continue until a complete consistent solution is reached\n",
              "* uninformed algorithm in backtracking, not assigning any costs associated with it.\n",
              "\n",
              "Backtracking performance\n",
              "* we want to create a general purpose method that has general purpose heuristic that can speed up the process and be applied to many contexts\n",
              "* to pick which variable is assigned next, want the most constrained variable first (i.e. fewest legal moves, minimum remaining values), if tied then most constraining variable (most constraints on the remaining variables in environment)\n",
              "* try the variables with the least constrining values first (rules out the fewest values for the rest of the states), and correct with forward checking\n",
              "\n",
              "Forward checking\n",
              "* we assign a variable to a domain, we want to keep a tally on the remaining legal values for the unassigned variables and go back when we have variables with no remaining values possible\n",
              "* if a failure is detected, then we use backtracking\n",
              "* cannot provide early detection for failures but moves the information forward from the assigned variable by removing the value from the neighbors\n",
              "* constraint propogation exists to repeatedly check the constraints locally instead of having to go iteratively through forward checking\n",
              "\n",
              "Inference\n",
              "* want to do this constraint propogation first to check local consistency to speed up the process of backtracking\n",
              "* local consistency can be done with node consistency (satisfies unary constraints) and arc consistancy (satisfies binary constraints)\n",
              "* if we have two nodes Xi and Xj connected by an edge, we want to represent this as a pair of directed edges or arcs from one to the other instead of an undirected edge\n",
              "\n",
              "Arc consistency\n",
              "* form of propogation to make each arc consistent, says that node 1 to node 2 is consistent iff for every value x in 1 there is some allowed y\n",
              "* if we lose a value in node 1, we recheck all of its neighbors to see that legal moves still remain \n",
              "* by doing this check on neighbors, we detect failures earlier and can do preprocessoring or check after assigning variables.\n",
              "* arc consistent iff every value on v on node 1 is consistent with some label on node 2\n",
              "* for each of these values, if there isn't a label in node 2 consistent with the value, then remove it from node 1\n",
              "* O(d^2) time to check the arcs with d values\n",
              "\n",
              "Waltz algorithm \n",
              "* iterating over the graph allows us to propagate the consistency constraints along arcs of the graph, use these constraints to add labels towards finding the solution\n",
              "* at the same time we can eliminate labels from the constraints to find all solutions\n",
              "* assign every node in the graph all possible values, then repear until there is no change in the set of values associated with any remaining nodes, for each node 1, if a neighbor has an inconsistent value with node 1, remove it from node 1\n",
              "\n",
              "AC-3 algorithm\n",
              "* only need to look at those nodes where at least one of the neighrbors has lost a value in the previous iteration to save on time\n",
              "* similarly, if node 1 loses a value because of node 2, we don't need to check node 2 in the next round, because removing a value of node 1 can only make node 2 inconsistent with node 1, no other nodes, so don't touch node 2\n",
              "* if we have all nodes connected to every other node, n nodes compared to n -1 nodes, 2 * n * (n-1) = O(n^2)\n",
              "* d values, checking an arc is O(d^2) time, each arc can be inserted back into the queue d times, giving worse case complexity of O(n^2 * d^3)\n",
              "* if we have a planar graph, arcs is only linear in N and time complexity reduced to O(n * d^3)\n",
              "\n",
              "\n",
              "\n",
              "## Module 6 Definitions\n",
              "* **Assignments** - in CSPs when you give a value to a variable\n",
              "* **Consistency** - an assignment that doesn't violate any constraints, a legal move\n",
              "* **Complete** - every variable has a value\n",
              "* **Partial assignment** - some of the variables are unassigned\n",
              "* **Partial solution** - a consistent partial assignment\n",
              "* **Precedence constraints** - the tasks/constraints have to occur in a certain order, one before another\n",
              "* **Disjunctive constraints** - some events cannot happen at the same time, one first or the other\n",
              "* **Unary constraint** - value of a single variable restricted\n",
              "* **Binary constraint** - two variables involved in the constraint\n",
              "* **Global constraint** - constraint involving any number of variables, not necessarily all of them\n",
              "* **Preference constraints** - when certain solutions are preferred but not required\n",
              "* **Constraint propagation** - use the constraints to remove the legal values for the variables, which can affect other variables\n",
              "* **Local consistency** - treat each variable as a node in a graph and each constraint as an edge, propagate around\n",
              "* **Node consistent** - one node if all values satisfy the unary constraints\n",
              "* **Arc consisitent** - every value in the domain satisfies the binary constraints\n",
              "* **Path consistent** - uses implicit constraints inferred by looking at triplets of variables\n",
              "* **Resource constraint** - some limit ot the assignments, at most x people working at once\n",
              "* **Minimum remaining values** - choose the variable with the fewest legal values next\n",
              "* **Chronological backtracking** - when a branch fails, back up to the preceding node and try a different one\n",
              "* **Constraint learning** - finding minimu set of variables from conlifct that cause the problem, called no-goods\n",
              "* **Value symmetry** - different ways so assign the solutions that are all valid\n",
              "* **Symmetry breaking constraint** - some way to break the tie and reduce the value symmetry search space\n",
              "\n",
              "\n",
              "# Module 7: Logical Agents\n",
              "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
              "\n",
              "* Sentences in KB can be a lot of things, expressed in a knowledge representation language, tell information about the world\n",
              "* KB initially has background knowledge of the environment\n",
              "* Every time the agent program is called, it tells the KB what it perceives, asks what is should perform, then tells the KB what action was taken\n",
              "* Need to specify what the agent knows and its goals at the knowledge level\n",
              "* Might differ significantly from the implementation level\n",
              "* A successful agent has both declarative and procedural setup\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.2 The Wumpus World\n",
              "\n",
              "* Wumpus world of rooms connected by passages, Same setup as R2D2 problem\n",
              "* Performance measure, get the gold and climb out, or die by a pit or Wumpus\n",
              "* Environment: 4 x 4 grid of rooms with walls\n",
              "* actuators: forward, turn left, turn right\n",
              "* sensors: stench, breeze, glitter, bump, scream\n",
              "* Deterministic, discrete, static, single agent\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.3 Logic\n",
              "\n",
              "* If sentence a is true in model m, we say m satisfies a or m is a model of a\n",
              "* M(a) is the set of all models of a\n",
              "* A entails b if and only if in every model where a is true, b Is true, or a |= b iff M(a) is proper subset of M(b)\n",
              "* When an inference algorithm I derives a from KB, we write KB |-I a\n",
              "* If we have a KB that is true in the real world, then if we derive a sentence a from Kb using a sound inference procedure it is also true in the real world\n",
              "\n",
              "\n",
              "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
              "\n",
              "* Syntax of propositional logic defines allowable atomic sentences which a single propositional symbol\n",
              "* Complex sentences constructed from simpler ones using logical connectives, not, and, or, implies, if and only if\n",
              "* The semantics are just the model setting truth values for each propositional symbol\n",
              "* Semantics must allow you to compute the truth value of any sentence in a model recursively\n",
              "* Rules expressed in truth tables that specify values of complex sentences\n",
              "* Exclusive or (xor) is false when both disjuncts are the same\n",
              "* When constructing a knowledge base, focus on immutable aspects first\n",
              "* Propositional logic is co-NP-complete, meaning every known inference algorithm has a worst-case complexity that is exponential compare to the input size\n",
              "\n",
              "\n",
              "## AIMA 7.5 Propositional Theorem Proving\n",
              "* A entails b iff the sentence a ^ not b is unsatisfiable, proof of refutation or contradiction\n",
              "* Inference rules can be applies to sentences to generate proofs\n",
              "* Modus ponens, and elimination, biconditional elimination\n",
              "* Finding a proof can be more efficient in practical cases because it can ignore unlimited irrelevant propositions\n",
              "* In monotonicity, if KB entails a then KB and B entail a\n",
              "* B would draw additional conclusions but cannot invalidate any conclusion that is already made for a, follows regardless of what else is in the KB\n",
              "* Resolution is a single inference rule that yields complete inference algorithms when combined with complete search algorithms\n",
              "* Resolvents created when information applied to a sentence makes it more clear, if there is a bit in one of three spots and its not in one of the spots, then its in one of the other two spots, unit resolution inference rule\n",
              "* Unit resolution takes a clause and literal and produces a new clause, can be a single or unit clauses, generalized into a full resolution rule\n",
              "* Resulting clause should only have one copy of each literal, removing of multiple copies called factoring\n",
              "* Resolution based theorem prover can decide whether a entails b for any a and b \n",
              "* Every sentence in propositional logic is logically equivalent to conjunction of clauses\n",
              "* CNF conversion: 1. Eliminate iff with implies, eliminate implies with not a and b, move the not inwards to match with literals, distribute ands and ors \n",
              "* Convert to CNF then apply resolution rules on resulting clauses\n",
              "* Continue to resolve new clauses, add to the set if its not there\n",
              "* Continue doing this until there are no new clauses to add where KB doesn’t entail a, or two clauses resolve to the empty clause, then KB entails a\n",
              "* Resolution closure RC(S) is the set of all clauses derivable by resolution rule to clauses in S or derivatives\n",
              "* If you try to resolve two horn clauses you get back a horn clause\n",
              "* Every definite clause can bet written as an implication with a conjunction of positive literals as its premise and a single positive literal as a conclusion\n",
              "* Horn clause inference can be done with forward-chaining and backward-chaining\n",
              "* Entailment with horn clauses is done in linear time to KB\n",
              "* Forward chaining determines if a proposition symbol is entailed by a KB of definite clauses, if all premises are known, then conclusion added to known facts\n",
              "* Forward chaining is sound and complete, a. Concept of data-driven reasoning\n",
              "* Backward chaining works backward from query, finds implications who’s conclusion is query, a form of goal directed reasoning\n",
              "* Cost often much less than linear time because it only looks at the relevant facts\n",
              "\n",
              "## Module 7 Lecture Notes\n",
              "\n",
              "Knowledge Based Agents:\n",
              "* utilize a process of reasonign over an internal representation in deciding what actions to take\n",
              "* up to this point the states have been atomic, agents have performed a search to figure out a plan and execute actions\n",
              "* a knowledge base of KB is the critical component of a knowledge-based agent\n",
              "* A KB has sentences written in a knowledge representation language that provide assertions about the world that the agent lives in\n",
              "* Sentence can be an axiom (given) or a derived sentence (created from the other sentences in a process called inference)\n",
              "* KB needs to have background information about the world before beginning and the agent can add to it through exploring the world\n",
              "* can also query the KB and tell it to derive new knowledge to best decide what action should be taken next\n",
              "\n",
              "Wampa world\n",
              "* create a world that is deterministic, discrete, static, single agent, R2D2 attempting to find Luke, reward if he does, penalty if he dies\n",
              "* in contrast to before, we have sequential steps because the reward/penalty may not be immediate, and partially observable because R2D2 cannot see where he hasn't been\n",
              "\n",
              "Logic\n",
              "* serves as class of representations for Knowledge based agents, specifically propositional logic\n",
              "* language has a syntax that says whether or not a sentence is correctly constructed, semantics that define what the sentences mean and define the truth of each sentence in the world (or model)\n",
              "* Have a bunch of truth values for each sentence, e.g. if we have a sentence a in a model m that is true, we say m satifies a, m is a model of a, M(a) to say the set of all models of a\n",
              "* define logical reasoning from truth statements, this reasoning involves entailment relationship between sentences, one logically flows from another\n",
              "* sentence a entails sentence beta a |= B, this is only true if M(a) is a subset of M(b), or a is more specific or stronger than B\n",
              "* KBs are false where models contradict what the agent knows, and possible worlds are all worlds compatible with the KB\n",
              "* entailment used to derive conclusions through locial inference. If we have some starting sentences we can create many entailed sentences to add to the KB\n",
              "* we want to create inference algorithms as a process of finding these sentences\n",
              "* KN |-i a means that a is derived from the KB by i\n",
              "* Monotonicity occurs when if KB |= a then KB ^ B |= a and we can add this to the KB without invalidating anything else\n",
              "* if we have monotonicity, we imply that the environment is sound and only derives entailed sentences\n",
              "\n",
              "Propositional logic\n",
              "* Here we have atomic sentences tha twere represented by a single propositional symbol, these symbols stand for a statements that can be true or false, e.g. FacingEast, W1,2\n",
              "* can construct complex sentences from simpler ones using parenthese and logical connectives (not, and, or, implies, if and only if)\n",
              "* create truth tables that represent all outcomes when variables are true or false with these logical connectives\n",
              "* not inverts the input, and is only true when both p and q are true, or is true when p or q is true\n",
              "* implication, true when T -> T or F -> anything\n",
              "* iff, true when T <-> T or F <-> F\n",
              "* Sound when the inference alogirhtm only derives entailed sentences, complete when the inference algorithm can derive all entailed sentences\n",
              "\n",
              "Logical equivalence\n",
              "* two sentences are seemed logically equivalent if they are true in the same set of models, a (three lines) B\n",
              "* two sentences a and B are only logically equivalent if they both entail each other\n",
              "* have a huge list of rules for logical equivalences, commutativity, associativity, double negative, contrapositive, implication elimination, biconditional elimination, De Morgan, distributivity\n",
              "* we use inference rules to derive proofs, if we have a sentence and the values that are true, can derive a new sentence, i.e. Modus Ponens, A elimination\n",
              "\n",
              "Search equivalent\n",
              "* Initial state is the KB at the beginning, actions are all inference rules applied to the sentences, result is adding the sentence to the KB, goal is the state with the sentence we're trying to prove\n",
              "* to prove completeness, we use resolution (single inference rule) to give a complete inference algorithm with any complete search algorithm\n",
              "* if l1 and m are complementary literals (meaning one is the negation of the other), then we eliminate them using unit resolution\n",
              "* resolution only applies to clauses (disjuctions of literals), where every sentence can be converted to an equivalent conjunction of clauses\n",
              "\n",
              "Conjunctive Normal Form\n",
              "* we can convert any sentence in propositional logic to a conjunction of clauses (disjunction of literals)\n",
              "1. Eliminate iff by replacing a iff b with (a -> b) ^ (b -> a)\n",
              "2. Eliminate -> by replacing a -> with (not a) v b\n",
              "3. move the not inwards, eliminate double negation and apply De Morgan's laws\n",
              "4. Apply distributivity laws with ^ and v wherever you can\n",
              "\n",
              "Resolution Algorithm\n",
              "* use proof by contradiction in inference procedures with resolution work\n",
              "* we want to show that KB |= a by showing that KB ^ not a is unsatisfiable\n",
              "1. Convert (KB ^ not a) into a CNF using the previous rules\n",
              "2. Apply resolution rule to resulting clauses\n",
              "3. Resolve every pair that has complementary literals, producing new clauses\n",
              "4. add the clause to the set if it isnt there, repeat until either there are no new clauses that can be added (KB does not entail a), or two clauses resolve to yield the empty clause (KB does entail a)\n",
              "* Empty clause come frsom two contradictory units a and not a\n",
              "* Complete algorithm, powerful inference method\n",
              "* KBs can be formulated with more restrictive form, can be more fficient\n",
              "* Definitive clauses include literals where exactlt one is positive\n",
              "* Horn Clauses include literals where at most one is positive (includes definite clauses and clauses with no positive literals). Closed under resolution, if you apply a resolution you get the same clause back\n",
              "\n",
              "Definite Clauses\n",
              "* can write every definite clause as an implication with a premise of a conjunction of positive literals whose conjunction is positive literal. (not B v not a v C can be written as B ^ a -> C)\n",
              "* horn clause inference done with forward and backward-chaining algorithms\n",
              "* deciding horn clause entailment is done in linear time relative to the size of KB\n",
              "\n",
              "Chaining\n",
              "* Forward - kind of data-driven reasoning. Agent adds premises as percepts come in, apply the forward chaining algorithm to derive new conclusions, no query needed\n",
              "* Backward - works backward from a query, if the query is true then don't need to act, otherwise the algorithm finds the implications in KB whose conclusions is the query. All premises of one can be proved to be true, then the query is true. Form of goal directed reasoning.\n",
              "\n",
              "\n",
              "## Module 7 Definitions\n",
              "* **Knowledge base** - central component of knowledge based agents, a set of sentences that assert things in the world\n",
              "* **Axiom** - sentences that are given without being derived from others\n",
              "* **Inference** - deriving new sentences from existing ones and axioms\n",
              "* **Declarative approach** - designer tells sentences to the agent until it knows how to act in the environment\n",
              "* **Procedural approach** - desired behaviors of the agent are encoded directly instead\n",
              "* **Syntax** - how sentences in a knowledge bases are well formed\n",
              "* **Semantics** - what meaning the sentences carry in a knowledge base, define truth in the world\n",
              "* **Model** - in logic, means the real possible worlds/environments the agent is existing in\n",
              "* **Entailment** - sentences follow logically from another sentence, a entails B, a|= B\n",
              "* **Logical inference** - how the definitions of entailment are applied to derive new conclusions\n",
              "* **Model checking** - when all possible models are enumerated to see if a is true in all models where KB is true\n",
              "* **Soundness** - when an inference algorithm only derives entailed sentences, truth preserving\n",
              "* **Completeness** - when an inference algorithm can derive any sentence that it entails\n",
              "* **Grounding** - the connection between logical reasoning and the real environment where the agent lives\n",
              "* **Propositional logic** - deriving syntactic algorithm for logical inferences to implement semantic notion of entailment\n",
              "* **Theorem proving** - when we apply inference rules to sentences in KB to construct proofs of the desired sentences\n",
              "* **Logical equivalence** - two sentences have the same true tables in the same set of models\n",
              "* **Validity** - a sentence is valid if true in all environemnts, also known as tautologies\n",
              "* **Deduction theorem** - for two sentences a and b, a entails b iff a ->b is valid\n",
              "* **Satisfiability** - sentence is satisfiable if it's true in some model\n",
              "* **Monotonicity** - set of entailed sentences only increases as more information is gained\n",
              "* **Conjunctive normal form** - a sentence expressed as a conjunction of clauses\n",
              "* **Ground resolution theorem** - if a set of clauses is unsatisfiable, resolution closure contains empty clause\n",
              "* **Definite clauses** - disjunction of literals where exactly one is positive\n",
              "* **Horn clauses** - more general, disjunction of literals where at most one is positive, closed under resolution\n",
              "* **Goal clauses** - clauses with no positive literals\n",
              "* **K-cnf** - CNF sentence where each clause has at most k literals\n",
              "* **Data driven reasoning** - focuses attention on the known data, forward chaining\n"
            ],
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "#@title\n",
        "# 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
}
