{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "b8972c46-17b5-47f4-815a-b2a8ef279071"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "66efb4b8-e0cc-4305-e5d6-4bbc82d9b18c"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"Acting Humanly - Turing Test - the computer needs Natural Language Processing, Knowledge Representation, Automated Reasoning, Machine Learning. A total turning test also requires computer vision and robotics. Not very focused anymore on passing this test similar to how artificial flight was achieved after moving away from mimicking birds as we do not need to replicate the exact method of flight that even fools pigeons to fly.---------------------------\n",
        "Thinking Humanly  - Human thought can be learned about in three ways (introspection, psychological experiments, brain imaging), and used to create a program that has I/O behaviors similar to humans. Cognitive Science studies this and develops parallelly to AI like seen in the field of computer vision.-------------------------\n",
        "Thinking Rationally - Concerns Logic, initially based on Aristotle's Syllogisms which yield correct conclusions given correct premises. Logistic systems could solve any problem (theoretically) that can be expressed in logical notion so the logistic tradition in AI builds on such systems to create intelligent systems. Since logic required certainty on some fronts, theory of probability is used to fill the gaps allowing reasoning even on uncertain info. It does not however, generate intelligent behavior which needs a theory of rational actions, not just rational thought--------------\n",
        "Acting Rationally - A rational agent is one that acts to generate the best expected outcome in case of uncertainty. Acting rationally does not always involve careful inference. Use knowledge representation and reasoning to get the right answer. The advantages of this approach are that it is more general that thinking rationally and more amenable to scientific development. Standard model - construction of agents that do the right thing. To account for the fact that taking the exactly optimal step is not possible every time, limited rather than perfect rationality.--------------\n",
        "Beneficial Machines - Standard model assumes we supply a fully specified objective to the machine which is not feasible. Value alignment problem deals with aligning the values of the machine and humans. Have to define the objective more complexly than just the sole objective of winning/ achieving a task as the machine may go outside the bounds of solutions we're looking for. So we make machines which know they don't entirely know the problem, in turn acting cautiously / in a way that is provably beneficial to humans. \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"Weak AI - Narrow, Strong - wide array------Arguments of Informality- made by Turnin saying human behaviour is far too complex to be captured by a set of formal rules and thus cannot be codified into a program. Good Old Fashioned AI (GOFAI) is restricted to computationalism and runs into qualification problem since it is impossible to account for every contingency. Embodied Cognition approach claims that it is not possible to contain cognition to only the brain i.e., logic and under this approach, robotics, sensors, vision etc. became central and not peripheral. Thus, the initial critique was against a certain style of programming not AI in general as it continues to develop.--------Arguement from disability - makes a claim that robots can never do 'X' but the only thing we are sure they can never do is be exactly human----------Mathematical Objection - certain mathematical questions are in principle\n",
        "unanswerable by particular formal systems. Gödel’s incompleteness theorem is a famous example. The problem is that this theorem deals with mathematics and not computers. and a lot of its assumptions on human part like consistency are unfounded while its limits on computers like unable to change their mind/ change is also unfounded as they are finite machines however large---------------Measuring AI - Turing test(30%), more a test of human gullibility, no trained judge has been fooled as of 2014. AI has focused on doing tasks effectively and not human like as the task is not to fool judges. \"\"\"\n",
        "chapter27_2 = \"\"\" The question is as relevant as asking if submarines swim.Turing said It's better to have the polite convention that everyone thinks, and this would extend to machines if we had some experience with ones that act intelligent. Now that we do have that experience, our willingness to ascribe sentience comes as much from humanoid appearance and voice as it does on pure int.________________ The Chinese Room - Created by Searle, he compares computers to Chinese room where the person and the stack of papers do not understand Chinese. Searle, a proponent of biological naturalism according to which mental states are high-level emergent features that are caused by low-level physical processes in the neurons,and it is the (unspecified) properties of the neurons that matter i.e., neurams have it while transistors don't. Same argument can also be used on humans however as we are just hunks of meat (cells) which do not understand anything by themselves._______________Consciousness and Qualia - Consciousness - Awareness of the outside world, the self and the subj experience of living. Qualia is the technical term for the intrinsic nature of experiences. It is hard to assign qualia to even animals, let alone machines. One of the reasons is that consciousness is ill-defined which might change soon as the advocates of two leading theories (global workspace theory and integrated info theory) agree that recent experiments of philosophers with neuroscientists can help confirm one theory over another. Turing believed that the theory has not much importance to building intelligent machines even tho individual aspects of consciousness—awareness, self-awareness, attention—can be programmed and can be part of an intelligent machine.It is hard for machines to emulate this unlike humans who can appreciate the subjective experience of others. Machines have no such capability even tho they can run each other's code. \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"An agent is anything that can be viewed as perceiving its environment through sensors and acting upon the environment through actuators. The term percept is used to refer to the content that the sensors are percieving and the history of this is the percept sequence. In general, the the choice of an agent cannot be based on anything that it hasn't perceived and not in its in-built knowledge. Agent function maps given percept sequence into an action and describes agent behavior. Unless we place a bound on the length of percept sequences we want to consider, the tabulating of any agent function would likely be infinite. This table is an external characterization of the agent as it records the actions the agent does in response to all possible percept sequences. Internally, the agent function for an artificial agent will be implemented by an agent program which is a concrete implementation running in some physical system unlike an agent function which is a mathematical abstract description. The notion of an agent is to be a tool for analyzing systems not an absolute characterization. \"\"\"\n",
        "chapter2_2 = \"\"\"A rational agent is one that does the right thing. Performance Measures - AI has stuck to the notion of consequentialism for defining 'the right thing'. When an agent is plucked down, it generates a sequence of actions that cause the environment to go through states and depending on the desirability of such states, the agent is said to have performed well. This notion is captured by a performance measure. Since machines do not have desires and preferences, the pref of the designer or the user is used for performance metric. These metrics may be explicit or implicit. It is best to design performance measures according the desired achieved result. It is also possible that wrong measures are put in so its important to build agents that reflect this initial uncertainty and as time goes by, learn more about the true performance measure.______Rationality - depends on performance measure that defines success criteria, agent's prior knowledge, the actions it can do, the percept sequence to date._________Omniscience, learning and autonomy - Omniscience is impossible in reality. Rationality maximizes expected performance while perfection maximizes actual performance. Info gathering is very important for rationality and is provided by exploration. Our rational agent also has to learn as much as possible from what it perceives during exploration. An agent lacks autonomy if it relies on prior knowledge more than its own percepts and learning process. \"\"\"\n",
        "chapter2_3 = \"\"\"Specifying the task environment - Also called the PEAS (Performance, Environment, Actuators and Sensors) description. First step in design of agent._______Properties of Task Environment - Very vast but dimensions (categories) exist which determine the appropriate agent design and applicability of each of the principal families of techniques for agent implementation. Fully vs Partially Observable, Single vs Multi-agent (An entity is classified as an agent instead of an object if it's behavior is best described as maximizing a performance measure whose value depends on our agent's behavior, even then it can be divided into competitive or cooperative multiagent env), Deterministic vs Non-deterministic (Not the same as stochastic which is an env that explicitly deals with probabilities whereas in nondeterm, there's no quantification of possibilities), Episodic vs Sequential, Static vs Dynamic(semi-dynamic if the system doesn't change but performance score does), Discrte vs Continuous, known vs unknown.\"\"\"\n",
        "chapter2_4 = \"\"\"Agent Architecture is the second part of the puzzle that along with agent program(which implements an agent function) creates an agent. The program and the architecture must be compatible.____________Agent Programs: they take in inputs from sensors and return an action to actuators. The agent program has no choice but to take just the current percept as the agent will have to remember percepts if it's actions depend on entire percept sequence. Since memory is an issue, AI has to focus on writing programs that produce rational behavior from small tables rather than a vast table. 4 kinds of agent programs embody the principles underlying all intelligent systems - SImple reflex, Model based reflex, goal based and utility based agents. Each of these combine particular components in particular ways to generate actions and all can be converted into learning agents to generate better agents.______Simple reflex: simplest kind, select actions on the basis of current percept only. Some simple reflex behaviors occur even in complex environments like the condition-action rule (IFTTT). Environment -> Sensors -> Current Percept -> (along with Condition-action rules ->) Action to do -> Actuators -> Env. Very simple but also limited int. as the env needs to be fully observable. To escape infinite loops due to partial observability, randomizing actions is a good idea tho it might not always be rational and there are better alternatives__________Model-based reflex agents: The most effective way to handle partial observability is to maintain an internal state that depends on percept history and reflects atleast some of the unobserved aspects of current state. We also need a transition model which helps in updating the internal state info based on info of both the effects of the agent's action as well as independent evolution of the world. We also need a sensor model which gives info on how the state is reflected in the percepts, together making the model based agents._______Goal-based agents: Goal info is also necessary adding to the previous list. This gets complicated when agents have to consider sequences of turns and thus Search and Planning are required. These agents are more versatile/flexible._________Utility-based Agent: Goals alone are not enough to generate high quality behavior, degree of utility is also an important distinguishing measure. An agent's utility function is essentially internalization of the performance measure. This is a model based agent, model-free agents can learn what actions are best in a given situation without learning how it changes the environment.__________Learning agents: Has 4 conceptual components: Learning element, performance element, critic, problem generator.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"2.4 cont..  Sensors send data to the performance element(previously the entire agent) and the critic which has the performance standard and gives feedback to learning unit. The learning unit takes the feedback and knowledge from performance element (which actuates the result) and suggests changes to perf element and learning goals to problem generator which suggests action to increase IG.___How components of agent programs work: We place representations along an axis of increasing complexity an expressive power - atomic, factored and structured \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can be viewed as perceiving its environment through sensors and acting upon the environment through actuators\",\n",
        "\"percept\" : \"ontent that the sensors are perceiving\",\n",
        "\"Percept Sequence\" : \"complete history of everything the agent has ever perceived\",\n",
        "\"Agent function.\": \"maps given percept sequence into an action and describes agent behavior\",\n",
        "\"Agent program.\": \"a concrete implementation, running within some physical system\",\n",
        "\"Rational agent.\": \"For each possible percept sequence, a rational agent should select an action that is expected to maximize \",\n",
        "\"Rational agent cont\" : \"its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\",\n",
        "\"Consequentialism .\": \"evaluate an agent’s behavior by its consequences\",\n",
        "\"Performance Measure.\": \"evaluates any given sequence of environment states\",\n",
        "\"Omniscient Agent.\": \"knows the actual outcome of its actions and can act accordingly\",\n",
        "\"Information gathering\" : \"doing actions in order to modify future percepts\",\n",
        "\"Deterministic Env\" : \" If the next state of the environment is completely determined_by_the current state and the action executed by the agent(s)\",\n",
        "\"Atomic representation\" : \"Each state of the world is indivisible, no internal structure.\",\n",
        "\"Factored rep\" : \"splits each state into a fixed set of variables or attributes each of which have a value\",\n",
        "\"Structured rep\" : \"Objects and their various/varying relationships are explicitly described\",\n",
        "\"Expressiveness\" : \"More expressive rep can capture everything less expressive rep can capture and more, usually more concise\",\n",
        "\"Localist rep\" : \"1 to 1 mapping of concepts and memory location\",\n",
        "\"distributed rep\" : \"rep_of_a_concept_is_spread_over many memory locations and each memory location is employed as a part of rep of multiple diff concepts\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2198
        },
        "cellView": "form",
        "outputId": "75238064-2672-4acb-8a36-734f58e6e822"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nActing Humanly - Turing Test - the computer needs Natural Language Processing, Knowledge Representation, Automated Reasoning, Machine Learning. A total turning test also requires computer vision and robotics. Not very focused anymore on passing this test similar to how artificial flight was achieved after moving away from mimicking birds as we do not need to replicate the exact method of flight that even fools pigeons to fly.---------------------------\nThinking Humanly  - Human thought can be learned about in three ways (introspection, psychological experiments, brain imaging), and used to create a program that has I/O behaviors similar to humans. Cognitive Science studies this and develops parallelly to AI like seen in the field of computer vision.-------------------------\nThinking Rationally - Concerns Logic, initially based on Aristotle's Syllogisms which yield correct conclusions given correct premises. Logistic systems could solve any problem (theoretically) that can be expressed in logical notion so the logistic tradition in AI builds on such systems to create intelligent systems. Since logic required certainty on some fronts, theory of probability is used to fill the gaps allowing reasoning even on uncertain info. It does not however, generate intelligent behavior which needs a theory of rational actions, not just rational thought--------------\nActing Rationally - A rational agent is one that acts to generate the best expected outcome in case of uncertainty. Acting rationally does not always involve careful inference. Use knowledge representation and reasoning to get the right answer. The advantages of this approach are that it is more general that thinking rationally and more amenable to scientific development. Standard model - construction of agents that do the right thing. To account for the fact that taking the exactly optimal step is not possible every time, limited rather than perfect rationality.--------------\nBeneficial Machines - Standard model assumes we supply a fully specified objective to the machine which is not feasible. Value alignment problem deals with aligning the values of the machine and humans. Have to define the objective more complexly than just the sole objective of winning/ achieving a task as the machine may go outside the bounds of solutions we're looking for. So we make machines which know they don't entirely know the problem, in turn acting cautiously / in a way that is provably beneficial to humans. \n\n## AIMA Chapter 27.1 The Limits of AI\nWeak AI - Narrow, Strong - wide array------Arguments of Informality- made by Turnin saying human behaviour is far too complex to be captured by a set of formal rules and thus cannot be codified into a program. Good Old Fashioned AI (GOFAI) is restricted to computationalism and runs into qualification problem since it is impossible to account for every contingency. Embodied Cognition approach claims that it is not possible to contain cognition to only the brain i.e., logic and under this approach, robotics, sensors, vision etc. became central and not peripheral. Thus, the initial critique was against a certain style of programming not AI in general as it continues to develop.--------Arguement from disability - makes a claim that robots can never do 'X' but the only thing we are sure they can never do is be exactly human----------Mathematical Objection - certain mathematical questions are in principle\nunanswerable by particular formal systems. Gödel’s incompleteness theorem is a famous example. The problem is that this theorem deals with mathematics and not computers. and a lot of its assumptions on human part like consistency are unfounded while its limits on computers like unable to change their mind/ change is also unfounded as they are finite machines however large---------------Measuring AI - Turing test(30%), more a test of human gullibility, no trained judge has been fooled as of 2014. AI has focused on doing tasks effectively and not human like as the task is not to fool judges. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n The question is as relevant as asking if submarines swim.Turing said It's better to have the polite convention that everyone thinks, and this would extend to machines if we had some experience with ones that act intelligent. Now that we do have that experience, our willingness to ascribe sentience comes as much from humanoid appearance and voice as it does on pure int.________________ The Chinese Room - Created by Searle, he compares computers to Chinese room where the person and the stack of papers do not understand Chinese. Searle, a proponent of biological naturalism according to which mental states are high-level emergent features that are caused by low-level physical processes in the neurons,and it is the (unspecified) properties of the neurons that matter i.e., neurams have it while transistors don't. Same argument can also be used on humans however as we are just hunks of meat (cells) which do not understand anything by themselves._______________Consciousness and Qualia - Consciousness - Awareness of the outside world, the self and the subj experience of living. Qualia is the technical term for the intrinsic nature of experiences. It is hard to assign qualia to even animals, let alone machines. One of the reasons is that consciousness is ill-defined which might change soon as the advocates of two leading theories (global workspace theory and integrated info theory) agree that recent experiments of philosophers with neuroscientists can help confirm one theory over another. Turing believed that the theory has not much importance to building intelligent machines even tho individual aspects of consciousness—awareness, self-awareness, attention—can be programmed and can be part of an intelligent machine.It is hard for machines to emulate this unlike humans who can appreciate the subjective experience of others. Machines have no such capability even tho they can run each other's code. \n\n## AIMA 2.1 Agents and Environments\nAn agent is anything that can be viewed as perceiving its environment through sensors and acting upon the environment through actuators. The term percept is used to refer to the content that the sensors are percieving and the history of this is the percept sequence. In general, the the choice of an agent cannot be based on anything that it hasn't perceived and not in its in-built knowledge. Agent function maps given percept sequence into an action and describes agent behavior. Unless we place a bound on the length of percept sequences we want to consider, the tabulating of any agent function would likely be infinite. This table is an external characterization of the agent as it records the actions the agent does in response to all possible percept sequences. Internally, the agent function for an artificial agent will be implemented by an agent program which is a concrete implementation running in some physical system unlike an agent function which is a mathematical abstract description. The notion of an agent is to be a tool for analyzing systems not an absolute characterization. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nA rational agent is one that does the right thing. Performance Measures - AI has stuck to the notion of consequentialism for defining 'the right thing'. When an agent is plucked down, it generates a sequence of actions that cause the environment to go through states and depending on the desirability of such states, the agent is said to have performed well. This notion is captured by a performance measure. Since machines do not have desires and preferences, the pref of the designer or the user is used for performance metric. These metrics may be explicit or implicit. It is best to design performance measures according the desired achieved result. It is also possible that wrong measures are put in so its important to build agents that reflect this initial uncertainty and as time goes by, learn more about the true performance measure.______Rationality - depends on performance measure that defines success criteria, agent's prior knowledge, the actions it can do, the percept sequence to date._________Omniscience, learning and autonomy - Omniscience is impossible in reality. Rationality maximizes expected performance while perfection maximizes actual performance. Info gathering is very important for rationality and is provided by exploration. Our rational agent also has to learn as much as possible from what it perceives during exploration. An agent lacks autonomy if it relies on prior knowledge more than its own percepts and learning process. \n\n## AIMA 2.3 The Nature of Environments\nSpecifying the task environment - Also called the PEAS (Performance, Environment, Actuators and Sensors) description. First step in design of agent._______Properties of Task Environment - Very vast but dimensions (categories) exist which determine the appropriate agent design and applicability of each of the principal families of techniques for agent implementation. Fully vs Partially Observable, Single vs Multi-agent (An entity is classified as an agent instead of an object if it's behavior is best described as maximizing a performance measure whose value depends on our agent's behavior, even then it can be divided into competitive or cooperative multiagent env), Deterministic vs Non-deterministic (Not the same as stochastic which is an env that explicitly deals with probabilities whereas in nondeterm, there's no quantification of possibilities), Episodic vs Sequential, Static vs Dynamic(semi-dynamic if the system doesn't change but performance score does), Discrte vs Continuous, known vs unknown.\n\n## AIMA 2.4 The Structure of Agents\nAgent Architecture is the second part of the puzzle that along with agent program(which implements an agent function) creates an agent. The program and the architecture must be compatible.____________Agent Programs: they take in inputs from sensors and return an action to actuators. The agent program has no choice but to take just the current percept as the agent will have to remember percepts if it's actions depend on entire percept sequence. Since memory is an issue, AI has to focus on writing programs that produce rational behavior from small tables rather than a vast table. 4 kinds of agent programs embody the principles underlying all intelligent systems - SImple reflex, Model based reflex, goal based and utility based agents. Each of these combine particular components in particular ways to generate actions and all can be converted into learning agents to generate better agents.______Simple reflex: simplest kind, select actions on the basis of current percept only. Some simple reflex behaviors occur even in complex environments like the condition-action rule (IFTTT). Environment -> Sensors -> Current Percept -> (along with Condition-action rules ->) Action to do -> Actuators -> Env. Very simple but also limited int. as the env needs to be fully observable. To escape infinite loops due to partial observability, randomizing actions is a good idea tho it might not always be rational and there are better alternatives__________Model-based reflex agents: The most effective way to handle partial observability is to maintain an internal state that depends on percept history and reflects atleast some of the unobserved aspects of current state. We also need a transition model which helps in updating the internal state info based on info of both the effects of the agent's action as well as independent evolution of the world. We also need a sensor model which gives info on how the state is reflected in the percepts, together making the model based agents._______Goal-based agents: Goal info is also necessary adding to the previous list. This gets complicated when agents have to consider sequences of turns and thus Search and Planning are required. These agents are more versatile/flexible._________Utility-based Agent: Goals alone are not enough to generate high quality behavior, degree of utility is also an important distinguishing measure. An agent's utility function is essentially internalization of the performance measure. This is a model based agent, model-free agents can learn what actions are best in a given situation without learning how it changes the environment.__________Learning agents: Has 4 conceptual components: Learning element, performance element, critic, problem generator.\n\n## Module 1 Lecture Notes\n2.4 cont..  Sensors send data to the performance element(previously the entire agent) and the critic which has the performance standard and gives feedback to learning unit. The learning unit takes the feedback and knowledge from performance element (which actuates the result) and suggests changes to perf element and learning goals to problem generator which suggests action to increase IG.___How components of agent programs work: We place representations along an axis of increasing complexity an expressive power - atomic, factored and structured \n\n## Module 1 Definitions\n* **Agent** - anything that can be viewed as perceiving its environment through sensors and acting upon the environment through actuators\n* **Percept** - ontent that the sensors are perceiving\n* **Percept sequence** - complete history of everything the agent has ever perceived\n* **Agent function.** - maps given percept sequence into an action and describes agent behavior\n* **Agent program.** - a concrete implementation, running within some physical system\n* **Rational agent.** - For each possible percept sequence, a rational agent should select an action that is expected to maximize \n* **Rational agent cont** - its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n* **Consequentialism .** - evaluate an agent’s behavior by its consequences\n* **Performance measure.** - evaluates any given sequence of environment states\n* **Omniscient agent.** - knows the actual outcome of its actions and can act accordingly\n* **Information gathering** - doing actions in order to modify future percepts\n* **Deterministic env** -  If the next state of the environment is completely determined_by_the current state and the action executed by the agent(s)\n* **Atomic representation** - Each state of the world is indivisible, no internal structure.\n* **Factored rep** - splits each state into a fixed set of variables or attributes each of which have a value\n* **Structured rep** - Objects and their various/varying relationships are explicitly described\n* **Expressiveness** - More expressive rep can capture everything less expressive rep can capture and more, usually more concise\n* **Localist rep** - 1 to 1 mapping of concepts and memory location\n* **Distributed rep** - rep_of_a_concept_is_spread_over many memory locations and each memory location is employed as a part of rep of multiple diff concepts\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\" Python - strongly but dynamically typed. List [ ], Dict { }, Tuple ( ). Operations on list - append(x), insert(index,x), index(), count(x), remove(x), sort(x)//// Operations on string - .split(\" \"), .join(\" \"), .strip(\" \"), .capitalize(), .upper()//////// For dict, keys must be immutable and can be looked up only using keys, .values() returns values while .keys() returns keys, .items() returns list of tuples. No function overloading but operator overloading. When using default values for keywords out-of-order, the keyword arguments must be used after other arguments.*args is used to accept a variable number of non-keyword arguments(x,y,z) while **kwargs is used to accept a variable number of keyword arguments(a=\"x\",b=\"y\"). To redefine a method of the parent class, include a new def using same name in the subclass. To execute the parent class version of this use parentclass.method(). Magic methods allow user-defined classes to behave like built in types Note: __bold__ letters have __ before and after them. __init__ = constructor, __len__ (define how len(obj) works), __copy__: define how copy works, __cmp__: define how ++ works etc. //////////// Iterators are objects with a __next__() method and iterable objects have __iter__ method.///// Generators are iterators and are created using the keyword 'yield', each time the __next__ method is called, it runs until it encounters a yield statement, returns that value and resumes where it left off. They use less code than std iterators and are imp for infinite seq/////////// Imports can allow use of pre-existing modules written by other people in your code.\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "\"iterable\" : \"something that can be looped over\",\n",
        "\"etc\" : \"etc\"\n",
        "}"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 393
        },
        "outputId": "0b4d1701-41ec-488e-800d-45184ce95121"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Python - strongly but dynamically typed. List [ ], Dict { }, Tuple ( ). Operations on list - append(x), insert(index,x), index(), count(x), remove(x), sort(x)//// Operations on string - .split(\" \"), .join(\" \"), .strip(\" \"), .capitalize(), .upper()//////// For dict, keys must be immutable and can be looked up only using keys, .values() returns values while .keys() returns keys, .items() returns list of tuples. No function overloading but operator overloading. When using default values for keywords out-of-order, the keyword arguments must be used after other arguments.*args is used to accept a variable number of non-keyword arguments(x,y,z) while **kwargs is used to accept a variable number of keyword arguments(a=\"x\",b=\"y\"). To redefine a method of the parent class, include a new def using same name in the subclass. To execute the parent class version of this use parentclass.method(). Magic methods allow user-defined classes to behave like built in types Note: __bold__ letters have __ before and after them. __init__ = constructor, __len__ (define how len(obj) works), __copy__: define how copy works, __cmp__: define how ++ works etc. //////////// Iterators are objects with a __next__() method and iterable objects have __iter__ method.///// Generators are iterators and are created using the keyword 'yield', each time the __next__ method is called, it runs until it encounters a yield statement, returns that value and resumes where it left off. They use less code than std iterators and are imp for infinite seq/////////// Imports can allow use of pre-existing modules written by other people in your code.\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n* **Iterable** - something that can be looped over\n* **Etc** - etc\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\"Problem solving agents use atomic reps and the agents that use factored or structured reps are called planning agents___________ We assume that the agents have access to info about the world and will take the following four-phase problem solving process: Goal formulation, Problem Formulation, Search, Execution. In a fully observable, deterministic, known env, the solution to any problem is a fixed seq of actions. This is an open-loop system as the percepts can be ignored which breaks the loop between agent and the env. If the model can be incorrect or the env is non-deterministic, a closed loop approach that monitors the percepts is better as the solutions in this case would be a branching strategy that recommends diff future actions based on the percepts. A search problem can be defined as: 1. A set of possible states called the state space, 2. The initial state 3. One or more goal states 4. Actions available to the agent 5. A transition model that describes what each action does 6. An action cost function.//////// A sequence of actions form a path and a solution is a path from initial to goal state. Optimal solution has the lowest path cost. The state space can be represented as a graph in which vertices are states and the directed edges between them are actions._________________ Formulating problems: The problem has to be formulated with the right level of detail, the process of removing details from a rep is called abstraction, choosing the right level of abstraction is necessary to ensure as much detail as possible is removed while retaining validity and ensuring that abstract actions are easy to carry out\"\"\"\n",
        "chapter3_2 = \"\"\" A standardized problem is intended to illustrate problem solving methods whereas a real-world problem is one whose solutions people actually use. A grid world is a 2d rectangular array of square cells in which agents can move from cell to cell and the cells contain objects which the agent can act upon. A Travelling Salesman problem describes a set of locations that must be visited, a VLSI layout problem requires positioning of millions of components and connections to minimize chip area and is split into cell layout and channel routing. \"\"\"\n",
        "chapter3_3 = \"\"\"A search alg takes a search problem as input and returns a solution. Algs superimpose a search tree over the state-space graph forming various paths from initial state, trying to find a path to goal state. Each node in this tree corresponds to a state and the edges correspond to actions. The state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. The search tree may have multiple paths to (and thus multiple nodes for) any given state, but each node in the tree has a unique path back to the root. Expanding a node is done by considering available actions from that state, seeing where they lead and generating a new child node for each of the resulting states. Frontier of the search tree are the set of unexpanded nodes. Any state that has had a node generated for it has been reached. Frontier divides the state-space graph into two parts, the interior region where very state has been expanded and the exterior region which has not yet been reached.____________ Best First Search: Choose node with minimum value of eval fn. f(n), by changing f(n) we get diff functions.__________ Search data structures: Search algorithms require a data structure to keep track of the search tree. A node in the tree is represented by a data structure with four components - State, Parent, Action and Path Cost. We also need a data structure to store the frontier and the appropriate choice is a queue. Three kinds of queues: 1. Priority Queue that first pops node with min. cost acc to eval fn f, used in best first search. 2. FIFO queue used in BFS 3/ LIFO queue uses in DFS. The reached states are stored as a lookup/hash table where each key is a state and each value is the node for that state.__________ Redundant Paths: There can exist repeated states in the search tree generated by a cycle/ loopy path which can make the tree infinite. A cycle is a spl case of redundant path. To eliminate redundant paths, there are 3 approaches: 1. We can remember all prev reached states (as Best FS does) 2. Ignore the problem as there are cases where we don't need to check for redundant paths. A search problem is graph search if it checks for redundant path and tree search if it does not. 3. Compromise and check for cycles but not redundant paths in general.______________ Measuring problem-solving performance: 4 ways to evaluate - 1. Completeness, 2. Cist optimality, 3.Time Complexity, 4. Space Complexity. A search algorithm must be systematic in the way it explores a space in order to be complete. In AI, the graph is represented implicitly using initial state, actions and transition_model. For such sate space, complexity is measured in terms of depth(number_of_actions_in_an_optimal_solution), max no. of actions in a path, branching factor (number_of _successors_of_a_node_that_need_to_be_considered)\"\"\"\n",
        "chapter3_4 = \"\"\" BFS - used when all actions have the same cost. Systematic - Complete. Best FS where f(n) is depth of the node. FIFO queue. We can do an early goal test checking whether a node is a solution as soon as its generated rather than a late goal test that best FS uses where we wait until the node is popped off the queue. Always Finds optimal soln. Time and Space complexity = O(b^d) b = branching factor/ d = depth__________ Dijkstra's alg or uniform cost search: Best FS where eval fn is the cost of the path from root to current node i.e., path cost. Dij's alg is UCS without a goal as UCS is Dijkstra's Algorithm which is focused on finding a single shortest path to a single finishing point rather than the shortest path to every point. The complexity of uniform-cost search is characterized in terms of C' the cost of the optimal solution, and ϵ a lower bound on the cost of each action, with Then the algorithm’s worst-case time and space complexity is O(b^(1+[C' / ϵ]) which can be much greater than b^d. UCS is complete and cost optimal _______________ Depth First Search - best FS with f(n) = negative of the depth. usually implemented as a tree search rather than graph. Not cost optimal and is not complete in infinite spaces. The adv is that the space complexity is only O(bm) where m is max depth of tree. A variant called backtracking search uses even less memory as it generates only one successor at a time which reduces the time reqd to check for cyclic path to o(1) from O(m). ____________________ Depth limited and iterative deepening: DFS with a depth limit L and treat all nodes at L as if there's no successors. Time complexity is O(b^l) and Space comp is O(bl), not complete under incorrect l, thus we iteratively deepen it. For depth limited, we can also use the info to find the diameter of the state space graph and improve efficiency. For it. deepening, time complexity is O(b^d(or m)) based on if there's a soln. or not_________ Bi-directional search: Simultaneously searches frwd from initial and backwards from goal state. The motivation is b^d/2 + b^d/2. We need two frontiers and two tables of reached states to be tracked and we have a soln if the two frontiers collide\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"Complete: BFS, UCS, Iterative deepening, Bidirectional, rest are incomplete. Optimal Cost: Same as before, BFS: TC = SC = O(b^d); UCS: TC = SC = O(b^(1+[C' / ϵ])); DFS: TC = O(b^m) and SC = o(bm); Depth limited: TC = O(b^l) and SC = o(bl); It. deepening: TC = O(b^d) and SC = o(bd); Bi-directional: SC = TC = O(b^d/2)\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1210
        },
        "outputId": "195b7145-b579-4a3d-acdf-1300e314781c"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nProblem solving agents use atomic reps and the agents that use factored or structured reps are called planning agents___________ We assume that the agents have access to info about the world and will take the following four-phase problem solving process: Goal formulation, Problem Formulation, Search, Execution. In a fully observable, deterministic, known env, the solution to any problem is a fixed seq of actions. This is an open-loop system as the percepts can be ignored which breaks the loop between agent and the env. If the model can be incorrect or the env is non-deterministic, a closed loop approach that monitors the percepts is better as the solutions in this case would be a branching strategy that recommends diff future actions based on the percepts. A search problem can be defined as: 1. A set of possible states called the state space, 2. The initial state 3. One or more goal states 4. Actions available to the agent 5. A transition model that describes what each action does 6. An action cost function.//////// A sequence of actions form a path and a solution is a path from initial to goal state. Optimal solution has the lowest path cost. The state space can be represented as a graph in which vertices are states and the directed edges between them are actions._________________ Formulating problems: The problem has to be formulated with the right level of detail, the process of removing details from a rep is called abstraction, choosing the right level of abstraction is necessary to ensure as much detail as possible is removed while retaining validity and ensuring that abstract actions are easy to carry out\n\n## AIMA Chapter 3.2 Example Problems\n A standardized problem is intended to illustrate problem solving methods whereas a real-world problem is one whose solutions people actually use. A grid world is a 2d rectangular array of square cells in which agents can move from cell to cell and the cells contain objects which the agent can act upon. A Travelling Salesman problem describes a set of locations that must be visited, a VLSI layout problem requires positioning of millions of components and connections to minimize chip area and is split into cell layout and channel routing. \n\n## AIMA Chapter 3.3 Search Algorithms\nA search alg takes a search problem as input and returns a solution. Algs superimpose a search tree over the state-space graph forming various paths from initial state, trying to find a path to goal state. Each node in this tree corresponds to a state and the edges correspond to actions. The state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. The search tree may have multiple paths to (and thus multiple nodes for) any given state, but each node in the tree has a unique path back to the root. Expanding a node is done by considering available actions from that state, seeing where they lead and generating a new child node for each of the resulting states. Frontier of the search tree are the set of unexpanded nodes. Any state that has had a node generated for it has been reached. Frontier divides the state-space graph into two parts, the interior region where very state has been expanded and the exterior region which has not yet been reached.____________ Best First Search: Choose node with minimum value of eval fn. f(n), by changing f(n) we get diff functions.__________ Search data structures: Search algorithms require a data structure to keep track of the search tree. A node in the tree is represented by a data structure with four components - State, Parent, Action and Path Cost. We also need a data structure to store the frontier and the appropriate choice is a queue. Three kinds of queues: 1. Priority Queue that first pops node with min. cost acc to eval fn f, used in best first search. 2. FIFO queue used in BFS 3/ LIFO queue uses in DFS. The reached states are stored as a lookup/hash table where each key is a state and each value is the node for that state.__________ Redundant Paths: There can exist repeated states in the search tree generated by a cycle/ loopy path which can make the tree infinite. A cycle is a spl case of redundant path. To eliminate redundant paths, there are 3 approaches: 1. We can remember all prev reached states (as Best FS does) 2. Ignore the problem as there are cases where we don't need to check for redundant paths. A search problem is graph search if it checks for redundant path and tree search if it does not. 3. Compromise and check for cycles but not redundant paths in general.______________ Measuring problem-solving performance: 4 ways to evaluate - 1. Completeness, 2. Cist optimality, 3.Time Complexity, 4. Space Complexity. A search algorithm must be systematic in the way it explores a space in order to be complete. In AI, the graph is represented implicitly using initial state, actions and transition_model. For such sate space, complexity is measured in terms of depth(number_of_actions_in_an_optimal_solution), max no. of actions in a path, branching factor (number_of _successors_of_a_node_that_need_to_be_considered)\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS - used when all actions have the same cost. Systematic - Complete. Best FS where f(n) is depth of the node. FIFO queue. We can do an early goal test checking whether a node is a solution as soon as its generated rather than a late goal test that best FS uses where we wait until the node is popped off the queue. Always Finds optimal soln. Time and Space complexity = O(b^d) b = branching factor/ d = depth__________ Dijkstra's alg or uniform cost search: Best FS where eval fn is the cost of the path from root to current node i.e., path cost. Dij's alg is UCS without a goal as UCS is Dijkstra's Algorithm which is focused on finding a single shortest path to a single finishing point rather than the shortest path to every point. The complexity of uniform-cost search is characterized in terms of C' the cost of the optimal solution, and ϵ a lower bound on the cost of each action, with Then the algorithm’s worst-case time and space complexity is O(b^(1+[C' / ϵ]) which can be much greater than b^d. UCS is complete and cost optimal _______________ Depth First Search - best FS with f(n) = negative of the depth. usually implemented as a tree search rather than graph. Not cost optimal and is not complete in infinite spaces. The adv is that the space complexity is only O(bm) where m is max depth of tree. A variant called backtracking search uses even less memory as it generates only one successor at a time which reduces the time reqd to check for cyclic path to o(1) from O(m). ____________________ Depth limited and iterative deepening: DFS with a depth limit L and treat all nodes at L as if there's no successors. Time complexity is O(b^l) and Space comp is O(bl), not complete under incorrect l, thus we iteratively deepen it. For depth limited, we can also use the info to find the diameter of the state space graph and improve efficiency. For it. deepening, time complexity is O(b^d(or m)) based on if there's a soln. or not_________ Bi-directional search: Simultaneously searches frwd from initial and backwards from goal state. The motivation is b^d/2 + b^d/2. We need two frontiers and two tables of reached states to be tracked and we have a soln if the two frontiers collide\n\n## Module 3 Lecture Notes\nComplete: BFS, UCS, Iterative deepening, Bidirectional, rest are incomplete. Optimal Cost: Same as before, BFS: TC = SC = O(b^d); UCS: TC = SC = O(b^(1+[C' / ϵ])); DFS: TC = O(b^m) and SC = o(bm); Depth limited: TC = O(b^l) and SC = o(bl); It. deepening: TC = O(b^d) and SC = o(bd); Bi-directional: SC = TC = O(b^d/2)\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\"Informed search - uses domain specific hints about the location of goals in the form of heuristic function h(n). Greedy best first search: Expands based on lowest h(n) value, f(n) = h(n). Is a graph search, is complete within finite spaces but not infinite ones. Worst case time and space complexity = O(|V|) but with good heuristic, it can be reduced to O(bm).___________ A* Search: f(n) = g(n) path cost from initial state to node n + h(n) = estimated path cost of best path that continues from n to goal. is complete and if h(n) is admissible (never overestimates), it is also cost optimal. A heuristic is consistent if for every node n and every successor n' of n generated by an action a, h(n) <= c(n,a,n')+h(n') (Triangle inequality)__________ Search Contours: Continuous contours drawn in state space to visualize a search. The g costs are monotonic, they always increase as you go along a path, but f will monotonically increase iff heuristic is consistent. A* with a consistent h is optimally efficient. It is efficient as it prunes away search tree nodes that are unnecessary for optimal solution. A* is complete, cost optimal and optimally efficient but not the best as the number of nodes expanded can be exponential in the ln of soln.___________ Satisfying search: inadmissible h and weighted A*: If we are okay with suboptimal solutions, A* expands far fewer nodes. Weighted A* - f(n) = g(n) + W*h(n) for W>1m is a somewhat greedy search and the weight makes sure it doesn't miss the answer. There's a number of criteria for what counts as good enough for suboptimal, bounded suboptimal search - soln that is guarentted to be within a constant factor W of optimal cost. bounded cost search - soln whose cost is less than some cost C, unbounded cost search -soln of any cost as long as its quick. ___________ Memory Bound search: A* consumes a lot of memory and a state is store on the frontier in two places - as a node in the frontier and as an entry in reached states table. It can be stores in only one of these or just removed from reached when we proved its no longer required to save space. We can also keep reference counts of no, of times a state has been reached and remove it from table when there's no more ways left.Cont in notes.. \"\"\"\n",
        "chapter3_6 = \"\"\"city-block distance/ Manhattan distance is the dist as sum of vertical and horizontal dist.____Effect pf heuristic accuracy on performance: One way to characterize it is the effective branching factor b* where N+1 = 1 +b*+b*^2+===b*^d where d = depth, N =total no. of nodes generate by A*. Pruning with an effective heuristic reduces Effective depth by a constant kh so total search cost reduces to O(b^(d-kh)). We say h2 dominates h1 if h2(n)>=h1(n), in this case h2 is always better than h1 as it causes lesser nodes. It is generally better to use h with higher values provided it is consistent.______ Generating heuristics for relaxed problems: A problem with fewer restrictions is a relaxed problem, so it adds edges to the state-space graph which may work as shortcuts so it might provide better solutions. the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. We can take the max of a collection of admissible heuristics and it will be the best but take slightly longer to compute._______ Generating h from subproblems: Pattern databases: Admissible h can also be derived from the solution cost of a subproblem. Pattern databases store such problems and these cannot be added__________ Generating h with landmarks: Precomputation is time-consuming but is worth it if the query will be encountered a vast number of times. Space and time complexity - is O(|v|^2) and O(|E|^3). Best to do this only for landmark points which can also be used as a part of bigger searches. shortcuts pre-defined for famous options is also a good ideas. Differential h is used in these cases________ Learning to search better: Metalevel state spaces capture internal state of a program that is searching in an ordinary/object level state space. This can be used to learn to search better and minimize the total cost._____________ Learning h from exp: A no. of features can be provided relevant to the state to predict the state's h value and this can help learn from exp\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Algs. designed to save memory - beam search limits size of frontier but makes it suboptimal and incomplete, Iterative-deepeningA* follows ID where cutoff is small f-cost of any node that exceeded the cutoff of prev, Recursive BestFS - uses an f_limit to keep track of best alternative f and unwinds to the alt path when it exceeds the limit. As it unwinds, it replaces f-value of all the nodes with the best f-value of its children if it ever wants to re-enter later. It is optimal if h(n) is admissible.  But both IDA* and RBFS use too little memory and may end up re-exploring same states so it_makes_sense_todetermine_how_much_memory_is_avaialable_and_allow_an_alg_to_use_it_all...__Memory-bound_A*(MA*)and_Simplified_MA*_do this. SMA* expands the best leaf and deletes the worst leaf, is complete if any reachable soln is there. It is optimal if any optimal soln is reachable._______ Bi-directional heuristic search: If we try using the same f, it wont work so we use fF(n) = gF(n) +hF(n) for nodes in fwd and replace F with B for backwards. Evaluation function of priority queues: f2(n) = max(2g(n), g(n) + h(n)). hF estimates distance to goal while hB estimates distance to start, this is a front-to-end appraoch. A front-to-front apprach estimates dist to the other frontier.________________\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"A* Space Complexity\" : \"O(b^d)\",    \n",
        "\"A* Time complexity\" : \"O(b^d)\",\n",
        "\"Greedy best first Time complexity\" : \"O(b^m) where m is max depth\",\n",
        "\"Greedy best first Space complexity\" : \"O(b^m) where m is max depth\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 944
        },
        "cellView": "form",
        "outputId": "30cdb622-0a85-4bc0-ae43-c24f3adb5746"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nInformed search - uses domain specific hints about the location of goals in the form of heuristic function h(n). Greedy best first search: Expands based on lowest h(n) value, f(n) = h(n). Is a graph search, is complete within finite spaces but not infinite ones. Worst case time and space complexity = O(|V|) but with good heuristic, it can be reduced to O(bm).___________ A* Search: f(n) = g(n) path cost from initial state to node n + h(n) = estimated path cost of best path that continues from n to goal. is complete and if h(n) is admissible (never overestimates), it is also cost optimal. A heuristic is consistent if for every node n and every successor n' of n generated by an action a, h(n) <= c(n,a,n')+h(n') (Triangle inequality)__________ Search Contours: Continuous contours drawn in state space to visualize a search. The g costs are monotonic, they always increase as you go along a path, but f will monotonically increase iff heuristic is consistent. A* with a consistent h is optimally efficient. It is efficient as it prunes away search tree nodes that are unnecessary for optimal solution. A* is complete, cost optimal and optimally efficient but not the best as the number of nodes expanded can be exponential in the ln of soln.___________ Satisfying search: inadmissible h and weighted A*: If we are okay with suboptimal solutions, A* expands far fewer nodes. Weighted A* - f(n) = g(n) + W*h(n) for W>1m is a somewhat greedy search and the weight makes sure it doesn't miss the answer. There's a number of criteria for what counts as good enough for suboptimal, bounded suboptimal search - soln that is guarentted to be within a constant factor W of optimal cost. bounded cost search - soln whose cost is less than some cost C, unbounded cost search -soln of any cost as long as its quick. ___________ Memory Bound search: A* consumes a lot of memory and a state is store on the frontier in two places - as a node in the frontier and as an entry in reached states table. It can be stores in only one of these or just removed from reached when we proved its no longer required to save space. We can also keep reference counts of no, of times a state has been reached and remove it from table when there's no more ways left.Cont in notes.. \n\n## AIMA Chapter 3.6 Heuristic Functions\ncity-block distance/ Manhattan distance is the dist as sum of vertical and horizontal dist.____Effect pf heuristic accuracy on performance: One way to characterize it is the effective branching factor b* where N+1 = 1 +b*+b*^2+===b*^d where d = depth, N =total no. of nodes generate by A*. Pruning with an effective heuristic reduces Effective depth by a constant kh so total search cost reduces to O(b^(d-kh)). We say h2 dominates h1 if h2(n)>=h1(n), in this case h2 is always better than h1 as it causes lesser nodes. It is generally better to use h with higher values provided it is consistent.______ Generating heuristics for relaxed problems: A problem with fewer restrictions is a relaxed problem, so it adds edges to the state-space graph which may work as shortcuts so it might provide better solutions. the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. We can take the max of a collection of admissible heuristics and it will be the best but take slightly longer to compute._______ Generating h from subproblems: Pattern databases: Admissible h can also be derived from the solution cost of a subproblem. Pattern databases store such problems and these cannot be added__________ Generating h with landmarks: Precomputation is time-consuming but is worth it if the query will be encountered a vast number of times. Space and time complexity - is O(|v|^2) and O(|E|^3). Best to do this only for landmark points which can also be used as a part of bigger searches. shortcuts pre-defined for famous options is also a good ideas. Differential h is used in these cases________ Learning to search better: Metalevel state spaces capture internal state of a program that is searching in an ordinary/object level state space. This can be used to learn to search better and minimize the total cost._____________ Learning h from exp: A no. of features can be provided relevant to the state to predict the state's h value and this can help learn from exp\n\n## Module 4 Lecture Notes\n Algs. designed to save memory - beam search limits size of frontier but makes it suboptimal and incomplete, Iterative-deepeningA* follows ID where cutoff is small f-cost of any node that exceeded the cutoff of prev, Recursive BestFS - uses an f_limit to keep track of best alternative f and unwinds to the alt path when it exceeds the limit. As it unwinds, it replaces f-value of all the nodes with the best f-value of its children if it ever wants to re-enter later. It is optimal if h(n) is admissible.  But both IDA* and RBFS use too little memory and may end up re-exploring same states so it_makes_sense_todetermine_how_much_memory_is_avaialable_and_allow_an_alg_to_use_it_all...__Memory-bound_A*(MA*)and_Simplified_MA*_do this. SMA* expands the best leaf and deletes the worst leaf, is complete if any reachable soln is there. It is optimal if any optimal soln is reachable._______ Bi-directional heuristic search: If we try using the same f, it wont work so we use fF(n) = gF(n) +hF(n) for nodes in fwd and replace F with B for backwards. Evaluation function of priority queues: f2(n) = max(2g(n), g(n) + h(n)). hF estimates distance to goal while hB estimates distance to start, this is a front-to-end appraoch. A front-to-front apprach estimates dist to the other frontier.________________\n\n## Module 4 Definitions\n* **A* space complexity** - O(b^d)\n* **A* time complexity** - O(b^d)\n* **Greedy best first time complexity** - O(b^m) where m is max depth\n* **Greedy best first space complexity** - O(b^m) where m is max depth\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\"Adversarial search has two or more agents with conflicting goals. There are 3 stances towards multi-agent networks. First is to consider them in the aggregate as an economy when there's a large no. of them. Second is to consider adversarial agents as a part of the env that makes it nondeterministic. Third to explicitly model the adv_agentswith techniques of adversarial game-tree search which is what we cover. Pruning ignores portions of trees that make no difference, hence making the search more efficient. A heuristic evaluation function is used to estimate who is winning whenever we stop searching._________ Two-player zero-sum games: __Minimax__ is used for Perfect info zero-sum games. We use move as synonym for action and position for state. A game has an initial state, legal set of moves, player whose turn it is to move, result(transition model), terminal test(for terminal state), utility function. The game tree is a search tree that follows every sequence of moves to the terminal state.\"\"\"\n",
        "chapter5_2 = \"\"\"Minimax search: Optimal strategy is worked out by determined by working out the minimax value of each state in the tree. We assume both players play optimally. Minimax decision is the optimal choice for min/max as it leads to the state with lowest/highest minimax value. The minimax algorithm performs a depth-first exploration of a game tree and the space and time complexities are as expected. If we have more than two players, we replace the single value for each node with a vector of values which gives the utility of that state from each player's perspective. Multi-player games also usually involve alliances which can be sort of predicted as usually the bottom two team against the top until it weakens___________ Alpha-Beta Pruning: Alpha is the value of the best from max player -> highest value choice we hound so far. Think alpha as \"at least\". Beta is lowest value choice, at most.__________ Move ordering: With perfect move ordering, the no. of nodes to examine are only O(b^m/2) and the effective branching factor becomes root of b rather than b. Dynamic move-ordering tries first the moves that were found to be the best in the past. We can use iterative deepening to achieve this with previous rankings informing the move ordering of new depth/ Best moves are called killer moves and to try them first is the killer move heuristic. Different permutations can end up in the same position which causes repeated states, this is called transposition and a transposition table that caches heuristic values of states is important. Even with alpha-beta pruning and move ordering, can't use minimax for chess and go coz too complex. Type A and B strategies are used for these, A is where all possible moves up to a certain depth are considered and evaluated to estimate utility of that depth whereas B ignores moves that look bad and followers promising lines as far as possible.\"\"\"\n",
        "chapter5_3 = \"\"\"To make use of limited computation time, an evaluation fn for heuristics is used to cutoff trees early and consider them terminal. This can be replaced with a cutoff test that returns true for terminal states. A heuristic eval fn returns the expected utility of the state to the player. Most eval fns work by calculating various features of the state and return an expected value. Since not all features are equal, we can use weighted linear function when adding up the individual values. It doesn't have to be proportional, just show a measure of preference. We are here making an assumption that the contribution of each factor is independent but it may not always be so and we can use a non-linear combination of features in addition. _____________ Cutting-off search: We cut-off search at a certain depth and return the eval for that state but must make sure the depth gets incremented. Eval fns should only be applied to positions that are quiescent. For nonquiescent positions, search continues till one is reached. The horizon effect is more difficult to eliminate. One strategy to mitigate the effect is to allow singular extensions _______ Forward Pruning: Prunes moves that appear to be poor moves but might be good, Beam cut is an eg. Probcut is another eg that prunes nodes probably outside the alpha beta window. Late move reductions works under the assumption that move ordering has been done well and thus late moves are less likely to be good so we limit the depth__________ Search vs lookup, loopup tables are used instead of searches for when search is over-kill or easy reference is available as the state is popular. \"\"\"\n",
        "chapter5_5 = \"\"\"include a random element and the game tree must include chance nodes in addition to max and min nodes (between min and max nodes). Instead of minimax value, we can only calculate the expectiminimax value now.__________ Evaluation for games of chance: return values that are a positive linear transformation of the probability of winning. Complexity is increased to O(b^m * n^m) where n is the no. of distinct rolls. Even chance nodes can be pruned by placing bounds on the possible values of utility functions.\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"Utility function captures the agent's preferences and assigns a single number to express the desirability of a state. The expected utility of an action given evidence is the avg utility of the outcomes.  If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score averaged over all the possible environments\"\"\"\n",
        "chapter16_2 = \"\"\"Constraints on rational preferences: Orderability (agent must have preference of one over other or rate them equally), Transitivity (if an agent prefers A to B and B to C, it must prefer A to C), Continuity (If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and  C with probability 1-p.), Substitutability (If the agent is indifferent between 2, it can use them interchangeably), Monotonicity (if A is preferred over B, lotteries with higher prob of A should be preferred), Decomposability (Compound lotteries can be reduced into single ones, or one equivalent one) These are just about preferences not utility. Value function is a preference ranking on states in a deterministic environment, also called ordinal utility function.\"\"\"\n",
        "chapter16_3 = \"\"\"Preference elicitation - presenting choices to humans and using observed preferences to pin down underlying utility function. Normalized utilities use a scale of 0 to 1. Value of statistical life is used to determine costs and benefits of regulations and interventions. Quality-adjusted life year is another measure for value of life. Expected monetary value is the sum of monetary value * probability of that value. U(L) < U(SEMV (L)) represents agents who are risk-averse in right and risk-seeking to the left. Value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. The insurance premium of a lottery is the difference between its EMV and certainty equivalent. Usually the estimated utility of the best choice is too high even with unbiased inputs due to optimizer's curse. _________ Decision theory is normative (describes how a rational agent should act). Descriptive theory describe how agents actually act. The irrational preferences can be due to certainty effect where people are strongly attracted to gain that are certain. Ambiguity aversion is also a trait seen in people, a lower version of certainty effect. Decision can also be saved using word choice which is the framing effect. Anchoring effect is how adding a really high priced option grounds other options.\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Pruning\" : \"Ignore portions of tree that don't make a difference\",\n",
        "\"Utility Function\" : \" the final numeric value to player when the game ends in terminal state\",\n",
        "\"Quiescent position\" : \"positions in which there is no pending move that would wildly swing the evaluation\",\n",
        "\"Horizon effect\": \"opponent’s move that's bad and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics\",\n",
        "\"Singular Extensions\":\"moves_that_are_clearly_better_than_all other moves in a given position, even when the search would normally be cut off at that point\",\n",
        "\"Policy\" : \"a mapping from every possible state to the best move in that state\",\n",
        "\"principle of maximum expected utility\" : \"a rational agent should choose the action that maximizes the agent’s expected utility\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1492
        },
        "outputId": "22ea83d5-aca2-4c67-e447-f8d6524af8df"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nAdversarial search has two or more agents with conflicting goals. There are 3 stances towards multi-agent networks. First is to consider them in the aggregate as an economy when there's a large no. of them. Second is to consider adversarial agents as a part of the env that makes it nondeterministic. Third to explicitly model the adv_agentswith techniques of adversarial game-tree search which is what we cover. Pruning ignores portions of trees that make no difference, hence making the search more efficient. A heuristic evaluation function is used to estimate who is winning whenever we stop searching._________ Two-player zero-sum games: __Minimax__ is used for Perfect info zero-sum games. We use move as synonym for action and position for state. A game has an initial state, legal set of moves, player whose turn it is to move, result(transition model), terminal test(for terminal state), utility function. The game tree is a search tree that follows every sequence of moves to the terminal state.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nMinimax search: Optimal strategy is worked out by determined by working out the minimax value of each state in the tree. We assume both players play optimally. Minimax decision is the optimal choice for min/max as it leads to the state with lowest/highest minimax value. The minimax algorithm performs a depth-first exploration of a game tree and the space and time complexities are as expected. If we have more than two players, we replace the single value for each node with a vector of values which gives the utility of that state from each player's perspective. Multi-player games also usually involve alliances which can be sort of predicted as usually the bottom two team against the top until it weakens___________ Alpha-Beta Pruning: Alpha is the value of the best from max player -> highest value choice we hound so far. Think alpha as \"at least\". Beta is lowest value choice, at most.__________ Move ordering: With perfect move ordering, the no. of nodes to examine are only O(b^m/2) and the effective branching factor becomes root of b rather than b. Dynamic move-ordering tries first the moves that were found to be the best in the past. We can use iterative deepening to achieve this with previous rankings informing the move ordering of new depth/ Best moves are called killer moves and to try them first is the killer move heuristic. Different permutations can end up in the same position which causes repeated states, this is called transposition and a transposition table that caches heuristic values of states is important. Even with alpha-beta pruning and move ordering, can't use minimax for chess and go coz too complex. Type A and B strategies are used for these, A is where all possible moves up to a certain depth are considered and evaluated to estimate utility of that depth whereas B ignores moves that look bad and followers promising lines as far as possible.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nTo make use of limited computation time, an evaluation fn for heuristics is used to cutoff trees early and consider them terminal. This can be replaced with a cutoff test that returns true for terminal states. A heuristic eval fn returns the expected utility of the state to the player. Most eval fns work by calculating various features of the state and return an expected value. Since not all features are equal, we can use weighted linear function when adding up the individual values. It doesn't have to be proportional, just show a measure of preference. We are here making an assumption that the contribution of each factor is independent but it may not always be so and we can use a non-linear combination of features in addition. _____________ Cutting-off search: We cut-off search at a certain depth and return the eval for that state but must make sure the depth gets incremented. Eval fns should only be applied to positions that are quiescent. For nonquiescent positions, search continues till one is reached. The horizon effect is more difficult to eliminate. One strategy to mitigate the effect is to allow singular extensions _______ Forward Pruning: Prunes moves that appear to be poor moves but might be good, Beam cut is an eg. Probcut is another eg that prunes nodes probably outside the alpha beta window. Late move reductions works under the assumption that move ordering has been done well and thus late moves are less likely to be good so we limit the depth__________ Search vs lookup, loopup tables are used instead of searches for when search is over-kill or easy reference is available as the state is popular. \n\n## AIMA Chapter 5.5 Stochastic Games\ninclude a random element and the game tree must include chance nodes in addition to max and min nodes (between min and max nodes). Instead of minimax value, we can only calculate the expectiminimax value now.__________ Evaluation for games of chance: return values that are a positive linear transformation of the probability of winning. Complexity is increased to O(b^m * n^m) where n is the no. of distinct rolls. Even chance nodes can be pruned by placing bounds on the possible values of utility functions.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nUtility function captures the agent's preferences and assigns a single number to express the desirability of a state. The expected utility of an action given evidence is the avg utility of the outcomes.  If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score averaged over all the possible environments\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nConstraints on rational preferences: Orderability (agent must have preference of one over other or rate them equally), Transitivity (if an agent prefers A to B and B to C, it must prefer A to C), Continuity (If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and  C with probability 1-p.), Substitutability (If the agent is indifferent between 2, it can use them interchangeably), Monotonicity (if A is preferred over B, lotteries with higher prob of A should be preferred), Decomposability (Compound lotteries can be reduced into single ones, or one equivalent one) These are just about preferences not utility. Value function is a preference ranking on states in a deterministic environment, also called ordinal utility function.\n\n## AIMA Chapter 16.3 Utility Functions\nPreference elicitation - presenting choices to humans and using observed preferences to pin down underlying utility function. Normalized utilities use a scale of 0 to 1. Value of statistical life is used to determine costs and benefits of regulations and interventions. Quality-adjusted life year is another measure for value of life. Expected monetary value is the sum of monetary value * probability of that value. U(L) < U(SEMV (L)) represents agents who are risk-averse in right and risk-seeking to the left. Value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. The insurance premium of a lottery is the difference between its EMV and certainty equivalent. Usually the estimated utility of the best choice is too high even with unbiased inputs due to optimizer's curse. _________ Decision theory is normative (describes how a rational agent should act). Descriptive theory describe how agents actually act. The irrational preferences can be due to certainty effect where people are strongly attracted to gain that are certain. Ambiguity aversion is also a trait seen in people, a lower version of certainty effect. Decision can also be saved using word choice which is the framing effect. Anchoring effect is how adding a really high priced option grounds other options.\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Pruning** - Ignore portions of tree that don't make a difference\n* **Utility function** -  the final numeric value to player when the game ends in terminal state\n* **Quiescent position** - positions in which there is no pending move that would wildly swing the evaluation\n* **Horizon effect** - opponent’s move that's bad and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics\n* **Singular extensions** - moves_that_are_clearly_better_than_all other moves in a given position, even when the search would normally be cut off at that point\n* **Policy** - a mapping from every possible state to the best move in that state\n* **Principle of maximum expected utility** - a rational agent should choose the action that maximizes the agent’s expected utility\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"Search problems search the state space comprised of indivisible black boxes. Here, we break open the back box using a factored representation for each state: a set of variables, each of which has a value. A CSP has 3 components: X is a set of variables {X1..Xn}, D is a set of domains, {D1,....Dn} and C a set of constraints. Each constraint can be seen as a pair of scope ( tuple of variables) and rel (relation between those variables). In a map coloring problem, X is the set of states, D is the set of colors, and C contains the states that share a border. President constraints are used when one task with 'd' duration has to be completed before another can start ( T1+d <= T2) _______ The simplest kind of CSPs involve variables that have discrete, finite domains. A discrete domain can be infinite in which we must use implicit constraints (T1+d<T2) rather than the explicit tuples of values. While special algorithms exist for solving linear constraints on integer variables, no such exists for nonlinear constraints. CSP with continuous domains are common in real-world (like linear programming). The types of constraints are unary, binary and ternary. A constraint involving an arbitrary no. of variables is a global constraint. Constraints can be represented ina a constraint hypergrpah that shows ordinary nodes as circles, hyder-nodes which represent n-ary constraint as squares. n-ary constraints can be transformed to binary with enough auxiliary variable introductions. CSPs also have preference constraints, that would be a constrainted optimization problem.\"\"\"\n",
        "chapter6_2 = \"\"\" There are diff types of local consistency- Node consistency: a single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraints. ___________ Arc consistency:if every value in its domain satisfies the variable’s binary constraints. AC-3 is the most popular method for enforcing arc-consistency. O(c*d^3) is the time complexity. To make every variable arc-consistent, the AC-3 algorithm maintains a queue of arcs to consider. Initially, the queue contains all the arcs in the CSP. (Each binary constraint becomes two arcs, one in each direction.) AC-3 then pops off an arbitrary arc (Xi,Xj) from the queue and makes arc-consistent with respect to Xj . If this leaves Di unchanged, the algorithm just moves on to the next arc. But if this revises Di (makes the domain smaller), then we add to the queue all arcs (Xk, Xi) where Xk  is a neighbour of Xi. If one Di gets revised to nothing, we return a failure. _____________ Path Consistency - tightens down the binary constraints with implicit constraints that are inferred by looking at triples of variables________ k-consistency: stronger forms of propagation. A CSP is strongly k-consistent if it is k0-consistent, k-1 consistent... 1-consistent. ____________ Global Constraints: useful to remove variables in the constraint that has a singleton domain and delete that variable's values from domains of remaining values. Resource constraint or utmost constraint is important in real life. For large resource-limited problems, it isn't possible to represent each variable in a domain and hence upper and lower bounds are used and domains are managed by bounds propagation. A CSP is bounds-consistent if for every variable X for both upper and lower bound values in X, there exists Y that satisfies the constraint\"\"\"\n",
        "chapter6_3 = \"\"\" Constraint Prop process can leave multiple variables with multiple possible values. In this case, we search for a solution using backtracking if we run into issues. To select an unassigned variable, there are several strategies including choosing the variable the minimum-remaining-values (MRV) (also called the most constrained variable, fail-first), Degree heuristic (picks the variable that has the most number of constraints, useful as a tie-breaker). Once a variable is selected, the least-constraining value is usually chosen. ____________ Forward checking is used whenever a variable is assigned to establish arc consistency for it, is a method of inference used during search. Maintaining Arc Consistency (MAC) algorithm detects inconsistencies where two or more neighbours are left with the same color left by starting the queue of arcs when inference calls AC3 with only arcs (Xj,Xi) where Xj are unassigned variables that are neighbors of Xi. ______________ Intelligent backtracking: instead of chronological backtracking of jumping to the most recent decision point, we keep track of assignments that caused the conflict (conflict set) and backjump to recent assignment in the set. Forward checking can supply this set with no extra work (add x to the set when x is deleted from a domain during forward-checking). Conflict-directed backjumping notices failure even when the variable domains are not empty by checking the variable assignment which caused this conflict to have no consistent solution.________________ Constraint Learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables is called no-good. \"\"\"\n",
        "chapter6_4 = \"\"\" min-conflicts heuristic chooses the value that results in min. no. of conflicts with other variables. Plateau search can help local search find its way off the series of plateaus which is the landscape of a CSP under min-conflicts. This wandering on the plateau can be directed with tabu search. Simulated annealing can also be used to escape from plateaus. Constraint weighting can be used to concentrate the search on important constraints \"\"\"\n",
        "chapter6_5 = \"\"\" Decomposing into subproblems is required for dealing with vast data. Some subproblems may be independent which can be ascertained by simply finding the connected components of the constraint graph. A constraint graph is a tree when any two variables are connected by only one path, needs bi-directional arc consistency. Topological sort is ordering the tree such that each variable only appears after its parent. Once we have a b-directional arc consistent graph (Time - O(n*d^2)), there's no need to backtrack we know the values we chose for parent are such that the child has a valid value. This is an efficient alg for trees and more complex graphs can be made trees by removing nodes or collapsing nodes together. _________ Cutset Conditioning: We can analyze a graph and see which points can be removed to create a tree, fix a value for them and remove them (cycle cutset) and the value from their neighbours. __________ Tree decomposition: Transform the original graph into a tree where each node consists of a set of variables such that each node is accounted for at least once, connected variables must be together. _______________ Value symmetry occurs when each variable has equal values to assign and we break this by introducing a symmetry-breaking constraint.\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"Complete Assignment\" : \" every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment\",    \n",
        "\"Constraint Propagation\":\"using constraints to reduce number of legal values for a variable, which in turn can reduce the legal values for another and so on\",\n",
        "\"Time Complexity of AC-3\" : \"O(c*d^3)\",\n",
        "\"Global Constraint\" : \"one involving an arbitrary number of variables (but not necessarily all variables)\",\n",
        "\"Constraint Learning\" : \"the idea of finding a minimum set of variables from the conflict set that causes the problem\",\n",
        "\"no-good\" : \"set of variables from constraint learning\",\n",
        "\"Plateau Search\" : \"allowing sideways moves to another state with the same score\",\n",
        "\"Tabu Search\" : \": keeping a small list of recently visited states and forbidding the algorithm to return to those states.\",\n",
        "\n",
        "}\n"
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1336
        },
        "outputId": "b8e6882b-f4aa-4024-dab3-5d57c9a32d07"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your definition of 'Constraint Propagation' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nSearch problems search the state space comprised of indivisible black boxes. Here, we break open the back box using a factored representation for each state: a set of variables, each of which has a value. A CSP has 3 components: X is a set of variables {X1..Xn}, D is a set of domains, {D1,....Dn} and C a set of constraints. Each constraint can be seen as a pair of scope ( tuple of variables) and rel (relation between those variables). In a map coloring problem, X is the set of states, D is the set of colors, and C contains the states that share a border. President constraints are used when one task with 'd' duration has to be completed before another can start ( T1+d <= T2) _______ The simplest kind of CSPs involve variables that have discrete, finite domains. A discrete domain can be infinite in which we must use implicit constraints (T1+d<T2) rather than the explicit tuples of values. While special algorithms exist for solving linear constraints on integer variables, no such exists for nonlinear constraints. CSP with continuous domains are common in real-world (like linear programming). The types of constraints are unary, binary and ternary. A constraint involving an arbitrary no. of variables is a global constraint. Constraints can be represented ina a constraint hypergrpah that shows ordinary nodes as circles, hyder-nodes which represent n-ary constraint as squares. n-ary constraints can be transformed to binary with enough auxiliary variable introductions. CSPs also have preference constraints, that would be a constrainted optimization problem.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n There are diff types of local consistency- Node consistency: a single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraints. ___________ Arc consistency:if every value in its domain satisfies the variable’s binary constraints. AC-3 is the most popular method for enforcing arc-consistency. O(c*d^3) is the time complexity. To make every variable arc-consistent, the AC-3 algorithm maintains a queue of arcs to consider. Initially, the queue contains all the arcs in the CSP. (Each binary constraint becomes two arcs, one in each direction.) AC-3 then pops off an arbitrary arc (Xi,Xj) from the queue and makes arc-consistent with respect to Xj . If this leaves Di unchanged, the algorithm just moves on to the next arc. But if this revises Di (makes the domain smaller), then we add to the queue all arcs (Xk, Xi) where Xk  is a neighbour of Xi. If one Di gets revised to nothing, we return a failure. _____________ Path Consistency - tightens down the binary constraints with implicit constraints that are inferred by looking at triples of variables________ k-consistency: stronger forms of propagation. A CSP is strongly k-consistent if it is k0-consistent, k-1 consistent... 1-consistent. ____________ Global Constraints: useful to remove variables in the constraint that has a singleton domain and delete that variable's values from domains of remaining values. Resource constraint or utmost constraint is important in real life. For large resource-limited problems, it isn't possible to represent each variable in a domain and hence upper and lower bounds are used and domains are managed by bounds propagation. A CSP is bounds-consistent if for every variable X for both upper and lower bound values in X, there exists Y that satisfies the constraint\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Constraint Prop process can leave multiple variables with multiple possible values. In this case, we search for a solution using backtracking if we run into issues. To select an unassigned variable, there are several strategies including choosing the variable the minimum-remaining-values (MRV) (also called the most constrained variable, fail-first), Degree heuristic (picks the variable that has the most number of constraints, useful as a tie-breaker). Once a variable is selected, the least-constraining value is usually chosen. ____________ Forward checking is used whenever a variable is assigned to establish arc consistency for it, is a method of inference used during search. Maintaining Arc Consistency (MAC) algorithm detects inconsistencies where two or more neighbours are left with the same color left by starting the queue of arcs when inference calls AC3 with only arcs (Xj,Xi) where Xj are unassigned variables that are neighbors of Xi. ______________ Intelligent backtracking: instead of chronological backtracking of jumping to the most recent decision point, we keep track of assignments that caused the conflict (conflict set) and backjump to recent assignment in the set. Forward checking can supply this set with no extra work (add x to the set when x is deleted from a domain during forward-checking). Conflict-directed backjumping notices failure even when the variable domains are not empty by checking the variable assignment which caused this conflict to have no consistent solution.________________ Constraint Learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables is called no-good. \n\n## AIMA Chapter 6.4 Local Search for CSPs\n min-conflicts heuristic chooses the value that results in min. no. of conflicts with other variables. Plateau search can help local search find its way off the series of plateaus which is the landscape of a CSP under min-conflicts. This wandering on the plateau can be directed with tabu search. Simulated annealing can also be used to escape from plateaus. Constraint weighting can be used to concentrate the search on important constraints \n\n## AIMA Chapter 6.5 The Structure of Problems\n Decomposing into subproblems is required for dealing with vast data. Some subproblems may be independent which can be ascertained by simply finding the connected components of the constraint graph. A constraint graph is a tree when any two variables are connected by only one path, needs bi-directional arc consistency. Topological sort is ordering the tree such that each variable only appears after its parent. Once we have a b-directional arc consistent graph (Time - O(n*d^2)), there's no need to backtrack we know the values we chose for parent are such that the child has a valid value. This is an efficient alg for trees and more complex graphs can be made trees by removing nodes or collapsing nodes together. _________ Cutset Conditioning: We can analyze a graph and see which points can be removed to create a tree, fix a value for them and remove them (cycle cutset) and the value from their neighbours. __________ Tree decomposition: Transform the original graph into a tree where each node consists of a set of variables such that each node is accounted for at least once, connected variables must be together. _______________ Value symmetry occurs when each variable has equal values to assign and we break this by introducing a symmetry-breaking constraint.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Complete assignment** -  every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment\n* **Constraint propagation** - using constraints to reduce number of legal values for a variable, which in turn can reduce the legal values for another and so on\n* **Time complexity of ac-3** - O(c*d^3)\n* **Global constraint** - one involving an arbitrary number of variables (but not necessarily all variables)\n* **Constraint learning** - the idea of finding a minimum set of variables from the conflict set that causes the problem\n* **No-good** - set of variables from constraint learning\n* **Plateau search** - allowing sideways moves to another state with the same score\n* **Tabu search** - : keeping a small list of recently visited states and forbidding the algorithm to return to those states.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"The central component of a knowledge-based agent is its knowledge base (KB) which is a set of sentences expressed in knowledge representation language. When a sentence is given, not derived it's an axiom. New sentences are added to KB using inference, though this develops over time, the agent also typically starts with some background knowledge. Each time an agent program is called, 1. it tells the KB what it perceives, 2/ it asks KB what action it should perform 3. tells the KB which action was chosen and returns the action for execution.\"\"\"\n",
        "chapter7_2 = \"\"\" Example of a knowledge based agent at work \"\"\"\n",
        "chapter7_3 = \"\"\" Logic must define the semantics or meaning of sentences that define the truth of each sentence with respect to each possible world.  Model is used instead of potential worlds, if a sentence A is true in a model M, M satisfies A or sometimes, M is a model of A. Logical entailment between sentences says that a sentence follows logically from another (A |= B), it is the case only if all points in A and B follow. The KB is false in models that contradict what the agent knows. Entailment can be used to carry out logical inference. An inference algorithm that derives only entailed sentences is called sound or truth-preserving. An inference algorithm is complete if it can derive any sentence that is entailed. General sentences are produced by learning but it is always fallible. But with good learning procedures, there is reason for optimism. \"\"\"\n",
        "chapter7_4 = \"\"\" The syntax of propositional logic defines allowable sentences. The atomic sentences consist of a single proposition symbol which can be true or false. Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. Connectivities in common use are: ¬(not) called the negation, ∧(and) called the conjunction(its parts are conjuncts), ∨(or) is a disjunction, ⇒(implies) called an implication, rules or if-then statements (In W⇒W1, W is the premise or antecedent and W1 is the conclusion or consequent), ⇔ (iff / if and only if) biconditional. This is also the order of their priority. The rules can be used to write the semantics using the truth value of each proposition symbol. The rules can also be expressed with truth tables that specify the truth value of a complex sentence for each possible assignment of truth value to its components. With semantics in place for propositional logic, we can construct a KB by first focusing on immutable aspects. An algorithm is sound if it implements directly the definition of entailment and complete if it works for any KB and A always terminates - only finite models. \"\"\"\n",
        "chapter7_5 = \"\"\" Entailment can be done by theorem proving - applying the rules of inference directly to sentences n our KB to construct a proof of the desired sentence without consulting models. Is more efficient than model checking if the no. of models is large but length of proof is small. Logical Equivalence - two sentences and are logically equivalent if they are true in the same set of models (A ≡ B). Validity - if true in all models, valid sentences are called tautologies. Satisfiability - if it is true in or satisfied by some model, these two are connected as A is satisfiable iff ¬A is not valid. Inference rules that can be applied to derive a proof. Modus Ponens Rule : α ⇒ β, α / β means that whenever α ⇒ β and α are given, then sentence β can be inferred. And- elimination is another such rule, α ∧ β/ α. Logical systems are monotonic as the set of entailed sentences can only increase as information is added to the knowledge base Rest in Notes \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"Knowledge-based agents\" : \"use a process of reasoning over an internal representation of knowledge to decide what actions to take\",    \n",
        "\"Knowledge level\" : \"we need specify only what the agent knows and what its goals are, in order to determine its behavior\",\n",
        "\"Implementation level\" : \"How knowledge is implemented\",\n",
        "\"Declarative approach\" : \"the agent designer uses TELL sentences one by one until the agent knows how to operate in its environment\",\n",
        "\"Procedural approach\" : \"encodes desired behaviors directly as program code\",\n",
        "\"Grounding\" : \"he connection between logical reasoning processes and the real environment in which the agent exists\",\n",
        "\"Literal\" : \"either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal).\",\n",
        "\"Logical entailment\" : \"A |= B\",\n",
        "\n",
        "}\n",
        "\n",
        "\n"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 990
        },
        "outputId": "70d7ec4d-5f98-4d61-df67-ebb0dd9681dc"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nThe central component of a knowledge-based agent is its knowledge base (KB) which is a set of sentences expressed in knowledge representation language. When a sentence is given, not derived it's an axiom. New sentences are added to KB using inference, though this develops over time, the agent also typically starts with some background knowledge. Each time an agent program is called, 1. it tells the KB what it perceives, 2/ it asks KB what action it should perform 3. tells the KB which action was chosen and returns the action for execution.\n\n## AIMA Chapter 7.2 The Wumpus World\n Example of a knowledge based agent at work \n\n## AIMA Chapter 7.3 Logic\n Logic must define the semantics or meaning of sentences that define the truth of each sentence with respect to each possible world.  Model is used instead of potential worlds, if a sentence A is true in a model M, M satisfies A or sometimes, M is a model of A. Logical entailment between sentences says that a sentence follows logically from another (A |= B), it is the case only if all points in A and B follow. The KB is false in models that contradict what the agent knows. Entailment can be used to carry out logical inference. An inference algorithm that derives only entailed sentences is called sound or truth-preserving. An inference algorithm is complete if it can derive any sentence that is entailed. General sentences are produced by learning but it is always fallible. But with good learning procedures, there is reason for optimism. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines allowable sentences. The atomic sentences consist of a single proposition symbol which can be true or false. Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. Connectivities in common use are: ¬(not) called the negation, ∧(and) called the conjunction(its parts are conjuncts), ∨(or) is a disjunction, ⇒(implies) called an implication, rules or if-then statements (In W⇒W1, W is the premise or antecedent and W1 is the conclusion or consequent), ⇔ (iff / if and only if) biconditional. This is also the order of their priority. The rules can be used to write the semantics using the truth value of each proposition symbol. The rules can also be expressed with truth tables that specify the truth value of a complex sentence for each possible assignment of truth value to its components. With semantics in place for propositional logic, we can construct a KB by first focusing on immutable aspects. An algorithm is sound if it implements directly the definition of entailment and complete if it works for any KB and A always terminates - only finite models. \n\n## AIMA 7.5 Propositional Theorem Proving\n Entailment can be done by theorem proving - applying the rules of inference directly to sentences n our KB to construct a proof of the desired sentence without consulting models. Is more efficient than model checking if the no. of models is large but length of proof is small. Logical Equivalence - two sentences and are logically equivalent if they are true in the same set of models (A ≡ B). Validity - if true in all models, valid sentences are called tautologies. Satisfiability - if it is true in or satisfied by some model, these two are connected as A is satisfiable iff ¬A is not valid. Inference rules that can be applied to derive a proof. Modus Ponens Rule : α ⇒ β, α / β means that whenever α ⇒ β and α are given, then sentence β can be inferred. And- elimination is another such rule, α ∧ β/ α. Logical systems are monotonic as the set of entailed sentences can only increase as information is added to the knowledge base Rest in Notes \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use a process of reasoning over an internal representation of knowledge to decide what actions to take\n* **Knowledge level** - we need specify only what the agent knows and what its goals are, in order to determine its behavior\n* **Implementation level** - How knowledge is implemented\n* **Declarative approach** - the agent designer uses TELL sentences one by one until the agent knows how to operate in its environment\n* **Procedural approach** - encodes desired behaviors directly as program code\n* **Grounding** - he connection between logical reasoning processes and the real environment in which the agent exists\n* **Literal** - either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal).\n* **Logical entailment** - A |= B\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 8425
        },
        "id": "T3cm1WV542_a",
        "outputId": "e2509050-d57e-41c4-d139-d56dcf799dad"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\nActing Humanly - Turing Test - the computer needs Natural Language Processing, Knowledge Representation, Automated Reasoning, Machine Learning. A total turning test also requires computer vision and robotics. Not very focused anymore on passing this test similar to how artificial flight was achieved after moving away from mimicking birds as we do not need to replicate the exact method of flight that even fools pigeons to fly.---------------------------\nThinking Humanly  - Human thought can be learned about in three ways (introspection, psychological experiments, brain imaging), and used to create a program that has I/O behaviors similar to humans. Cognitive Science studies this and develops parallelly to AI like seen in the field of computer vision.-------------------------\nThinking Rationally - Concerns Logic, initially based on Aristotle's Syllogisms which yield correct conclusions given correct premises. Logistic systems could solve any problem (theoretically) that can be expressed in logical notion so the logistic tradition in AI builds on such systems to create intelligent systems. Since logic required certainty on some fronts, theory of probability is used to fill the gaps allowing reasoning even on uncertain info. It does not however, generate intelligent behavior which needs a theory of rational actions, not just rational thought--------------\nActing Rationally - A rational agent is one that acts to generate the best expected outcome in case of uncertainty. Acting rationally does not always involve careful inference. Use knowledge representation and reasoning to get the right answer. The advantages of this approach are that it is more general that thinking rationally and more amenable to scientific development. Standard model - construction of agents that do the right thing. To account for the fact that taking the exactly optimal step is not possible every time, limited rather than perfect rationality.--------------\nBeneficial Machines - Standard model assumes we supply a fully specified objective to the machine which is not feasible. Value alignment problem deals with aligning the values of the machine and humans. Have to define the objective more complexly than just the sole objective of winning/ achieving a task as the machine may go outside the bounds of solutions we're looking for. So we make machines which know they don't entirely know the problem, in turn acting cautiously / in a way that is provably beneficial to humans. \n\n## AIMA Chapter 27.1 The Limits of AI\nWeak AI - Narrow, Strong - wide array------Arguments of Informality- made by Turnin saying human behaviour is far too complex to be captured by a set of formal rules and thus cannot be codified into a program. Good Old Fashioned AI (GOFAI) is restricted to computationalism and runs into qualification problem since it is impossible to account for every contingency. Embodied Cognition approach claims that it is not possible to contain cognition to only the brain i.e., logic and under this approach, robotics, sensors, vision etc. became central and not peripheral. Thus, the initial critique was against a certain style of programming not AI in general as it continues to develop.--------Arguement from disability - makes a claim that robots can never do 'X' but the only thing we are sure they can never do is be exactly human----------Mathematical Objection - certain mathematical questions are in principle\nunanswerable by particular formal systems. Gödel’s incompleteness theorem is a famous example. The problem is that this theorem deals with mathematics and not computers. and a lot of its assumptions on human part like consistency are unfounded while its limits on computers like unable to change their mind/ change is also unfounded as they are finite machines however large---------------Measuring AI - Turing test(30%), more a test of human gullibility, no trained judge has been fooled as of 2014. AI has focused on doing tasks effectively and not human like as the task is not to fool judges. \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n The question is as relevant as asking if submarines swim.Turing said It's better to have the polite convention that everyone thinks, and this would extend to machines if we had some experience with ones that act intelligent. Now that we do have that experience, our willingness to ascribe sentience comes as much from humanoid appearance and voice as it does on pure int.________________ The Chinese Room - Created by Searle, he compares computers to Chinese room where the person and the stack of papers do not understand Chinese. Searle, a proponent of biological naturalism according to which mental states are high-level emergent features that are caused by low-level physical processes in the neurons,and it is the (unspecified) properties of the neurons that matter i.e., neurams have it while transistors don't. Same argument can also be used on humans however as we are just hunks of meat (cells) which do not understand anything by themselves._______________Consciousness and Qualia - Consciousness - Awareness of the outside world, the self and the subj experience of living. Qualia is the technical term for the intrinsic nature of experiences. It is hard to assign qualia to even animals, let alone machines. One of the reasons is that consciousness is ill-defined which might change soon as the advocates of two leading theories (global workspace theory and integrated info theory) agree that recent experiments of philosophers with neuroscientists can help confirm one theory over another. Turing believed that the theory has not much importance to building intelligent machines even tho individual aspects of consciousness—awareness, self-awareness, attention—can be programmed and can be part of an intelligent machine.It is hard for machines to emulate this unlike humans who can appreciate the subjective experience of others. Machines have no such capability even tho they can run each other's code. \n\n## AIMA 2.1 Agents and Environments\nAn agent is anything that can be viewed as perceiving its environment through sensors and acting upon the environment through actuators. The term percept is used to refer to the content that the sensors are percieving and the history of this is the percept sequence. In general, the the choice of an agent cannot be based on anything that it hasn't perceived and not in its in-built knowledge. Agent function maps given percept sequence into an action and describes agent behavior. Unless we place a bound on the length of percept sequences we want to consider, the tabulating of any agent function would likely be infinite. This table is an external characterization of the agent as it records the actions the agent does in response to all possible percept sequences. Internally, the agent function for an artificial agent will be implemented by an agent program which is a concrete implementation running in some physical system unlike an agent function which is a mathematical abstract description. The notion of an agent is to be a tool for analyzing systems not an absolute characterization. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\nA rational agent is one that does the right thing. Performance Measures - AI has stuck to the notion of consequentialism for defining 'the right thing'. When an agent is plucked down, it generates a sequence of actions that cause the environment to go through states and depending on the desirability of such states, the agent is said to have performed well. This notion is captured by a performance measure. Since machines do not have desires and preferences, the pref of the designer or the user is used for performance metric. These metrics may be explicit or implicit. It is best to design performance measures according the desired achieved result. It is also possible that wrong measures are put in so its important to build agents that reflect this initial uncertainty and as time goes by, learn more about the true performance measure.______Rationality - depends on performance measure that defines success criteria, agent's prior knowledge, the actions it can do, the percept sequence to date._________Omniscience, learning and autonomy - Omniscience is impossible in reality. Rationality maximizes expected performance while perfection maximizes actual performance. Info gathering is very important for rationality and is provided by exploration. Our rational agent also has to learn as much as possible from what it perceives during exploration. An agent lacks autonomy if it relies on prior knowledge more than its own percepts and learning process. \n\n## AIMA 2.3 The Nature of Environments\nSpecifying the task environment - Also called the PEAS (Performance, Environment, Actuators and Sensors) description. First step in design of agent._______Properties of Task Environment - Very vast but dimensions (categories) exist which determine the appropriate agent design and applicability of each of the principal families of techniques for agent implementation. Fully vs Partially Observable, Single vs Multi-agent (An entity is classified as an agent instead of an object if it's behavior is best described as maximizing a performance measure whose value depends on our agent's behavior, even then it can be divided into competitive or cooperative multiagent env), Deterministic vs Non-deterministic (Not the same as stochastic which is an env that explicitly deals with probabilities whereas in nondeterm, there's no quantification of possibilities), Episodic vs Sequential, Static vs Dynamic(semi-dynamic if the system doesn't change but performance score does), Discrte vs Continuous, known vs unknown.\n\n## AIMA 2.4 The Structure of Agents\nAgent Architecture is the second part of the puzzle that along with agent program(which implements an agent function) creates an agent. The program and the architecture must be compatible.____________Agent Programs: they take in inputs from sensors and return an action to actuators. The agent program has no choice but to take just the current percept as the agent will have to remember percepts if it's actions depend on entire percept sequence. Since memory is an issue, AI has to focus on writing programs that produce rational behavior from small tables rather than a vast table. 4 kinds of agent programs embody the principles underlying all intelligent systems - SImple reflex, Model based reflex, goal based and utility based agents. Each of these combine particular components in particular ways to generate actions and all can be converted into learning agents to generate better agents.______Simple reflex: simplest kind, select actions on the basis of current percept only. Some simple reflex behaviors occur even in complex environments like the condition-action rule (IFTTT). Environment -> Sensors -> Current Percept -> (along with Condition-action rules ->) Action to do -> Actuators -> Env. Very simple but also limited int. as the env needs to be fully observable. To escape infinite loops due to partial observability, randomizing actions is a good idea tho it might not always be rational and there are better alternatives__________Model-based reflex agents: The most effective way to handle partial observability is to maintain an internal state that depends on percept history and reflects atleast some of the unobserved aspects of current state. We also need a transition model which helps in updating the internal state info based on info of both the effects of the agent's action as well as independent evolution of the world. We also need a sensor model which gives info on how the state is reflected in the percepts, together making the model based agents._______Goal-based agents: Goal info is also necessary adding to the previous list. This gets complicated when agents have to consider sequences of turns and thus Search and Planning are required. These agents are more versatile/flexible._________Utility-based Agent: Goals alone are not enough to generate high quality behavior, degree of utility is also an important distinguishing measure. An agent's utility function is essentially internalization of the performance measure. This is a model based agent, model-free agents can learn what actions are best in a given situation without learning how it changes the environment.__________Learning agents: Has 4 conceptual components: Learning element, performance element, critic, problem generator.\n\n## Module 1 Lecture Notes\n2.4 cont..  Sensors send data to the performance element(previously the entire agent) and the critic which has the performance standard and gives feedback to learning unit. The learning unit takes the feedback and knowledge from performance element (which actuates the result) and suggests changes to perf element and learning goals to problem generator which suggests action to increase IG.___How components of agent programs work: We place representations along an axis of increasing complexity an expressive power - atomic, factored and structured \n\n## Module 1 Definitions\n* **Agent** - anything that can be viewed as perceiving its environment through sensors and acting upon the environment through actuators\n* **Percept** - ontent that the sensors are perceiving\n* **Percept sequence** - complete history of everything the agent has ever perceived\n* **Agent function.** - maps given percept sequence into an action and describes agent behavior\n* **Agent program.** - a concrete implementation, running within some physical system\n* **Rational agent.** - For each possible percept sequence, a rational agent should select an action that is expected to maximize \n* **Rational agent cont** - its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n* **Consequentialism .** - evaluate an agent’s behavior by its consequences\n* **Performance measure.** - evaluates any given sequence of environment states\n* **Omniscient agent.** - knows the actual outcome of its actions and can act accordingly\n* **Information gathering** - doing actions in order to modify future percepts\n* **Deterministic env** -  If the next state of the environment is completely determined_by_the current state and the action executed by the agent(s)\n* **Atomic representation** - Each state of the world is indivisible, no internal structure.\n* **Factored rep** - splits each state into a fixed set of variables or attributes each of which have a value\n* **Structured rep** - Objects and their various/varying relationships are explicitly described\n* **Expressiveness** - More expressive rep can capture everything less expressive rep can capture and more, usually more concise\n* **Localist rep** - 1 to 1 mapping of concepts and memory location\n* **Distributed rep** - rep_of_a_concept_is_spread_over many memory locations and each memory location is employed as a part of rep of multiple diff concepts\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Python - strongly but dynamically typed. List [ ], Dict { }, Tuple ( ). Operations on list - append(x), insert(index,x), index(), count(x), remove(x), sort(x)//// Operations on string - .split(\" \"), .join(\" \"), .strip(\" \"), .capitalize(), .upper()//////// For dict, keys must be immutable and can be looked up only using keys, .values() returns values while .keys() returns keys, .items() returns list of tuples. No function overloading but operator overloading. When using default values for keywords out-of-order, the keyword arguments must be used after other arguments.*args is used to accept a variable number of non-keyword arguments(x,y,z) while **kwargs is used to accept a variable number of keyword arguments(a=\"x\",b=\"y\"). To redefine a method of the parent class, include a new def using same name in the subclass. To execute the parent class version of this use parentclass.method(). Magic methods allow user-defined classes to behave like built in types Note: __bold__ letters have __ before and after them. __init__ = constructor, __len__ (define how len(obj) works), __copy__: define how copy works, __cmp__: define how ++ works etc. //////////// Iterators are objects with a __next__() method and iterable objects have __iter__ method.///// Generators are iterators and are created using the keyword 'yield', each time the __next__ method is called, it runs until it encounters a yield statement, returns that value and resumes where it left off. They use less code than std iterators and are imp for infinite seq/////////// Imports can allow use of pre-existing modules written by other people in your code.\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n* **Iterable** - something that can be looped over\n* **Etc** - etc\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\nProblem solving agents use atomic reps and the agents that use factored or structured reps are called planning agents___________ We assume that the agents have access to info about the world and will take the following four-phase problem solving process: Goal formulation, Problem Formulation, Search, Execution. In a fully observable, deterministic, known env, the solution to any problem is a fixed seq of actions. This is an open-loop system as the percepts can be ignored which breaks the loop between agent and the env. If the model can be incorrect or the env is non-deterministic, a closed loop approach that monitors the percepts is better as the solutions in this case would be a branching strategy that recommends diff future actions based on the percepts. A search problem can be defined as: 1. A set of possible states called the state space, 2. The initial state 3. One or more goal states 4. Actions available to the agent 5. A transition model that describes what each action does 6. An action cost function.//////// A sequence of actions form a path and a solution is a path from initial to goal state. Optimal solution has the lowest path cost. The state space can be represented as a graph in which vertices are states and the directed edges between them are actions._________________ Formulating problems: The problem has to be formulated with the right level of detail, the process of removing details from a rep is called abstraction, choosing the right level of abstraction is necessary to ensure as much detail as possible is removed while retaining validity and ensuring that abstract actions are easy to carry out\n\n## AIMA Chapter 3.2 Example Problems\n A standardized problem is intended to illustrate problem solving methods whereas a real-world problem is one whose solutions people actually use. A grid world is a 2d rectangular array of square cells in which agents can move from cell to cell and the cells contain objects which the agent can act upon. A Travelling Salesman problem describes a set of locations that must be visited, a VLSI layout problem requires positioning of millions of components and connections to minimize chip area and is split into cell layout and channel routing. \n\n## AIMA Chapter 3.3 Search Algorithms\nA search alg takes a search problem as input and returns a solution. Algs superimpose a search tree over the state-space graph forming various paths from initial state, trying to find a path to goal state. Each node in this tree corresponds to a state and the edges correspond to actions. The state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. The search tree may have multiple paths to (and thus multiple nodes for) any given state, but each node in the tree has a unique path back to the root. Expanding a node is done by considering available actions from that state, seeing where they lead and generating a new child node for each of the resulting states. Frontier of the search tree are the set of unexpanded nodes. Any state that has had a node generated for it has been reached. Frontier divides the state-space graph into two parts, the interior region where very state has been expanded and the exterior region which has not yet been reached.____________ Best First Search: Choose node with minimum value of eval fn. f(n), by changing f(n) we get diff functions.__________ Search data structures: Search algorithms require a data structure to keep track of the search tree. A node in the tree is represented by a data structure with four components - State, Parent, Action and Path Cost. We also need a data structure to store the frontier and the appropriate choice is a queue. Three kinds of queues: 1. Priority Queue that first pops node with min. cost acc to eval fn f, used in best first search. 2. FIFO queue used in BFS 3/ LIFO queue uses in DFS. The reached states are stored as a lookup/hash table where each key is a state and each value is the node for that state.__________ Redundant Paths: There can exist repeated states in the search tree generated by a cycle/ loopy path which can make the tree infinite. A cycle is a spl case of redundant path. To eliminate redundant paths, there are 3 approaches: 1. We can remember all prev reached states (as Best FS does) 2. Ignore the problem as there are cases where we don't need to check for redundant paths. A search problem is graph search if it checks for redundant path and tree search if it does not. 3. Compromise and check for cycles but not redundant paths in general.______________ Measuring problem-solving performance: 4 ways to evaluate - 1. Completeness, 2. Cist optimality, 3.Time Complexity, 4. Space Complexity. A search algorithm must be systematic in the way it explores a space in order to be complete. In AI, the graph is represented implicitly using initial state, actions and transition_model. For such sate space, complexity is measured in terms of depth(number_of_actions_in_an_optimal_solution), max no. of actions in a path, branching factor (number_of _successors_of_a_node_that_need_to_be_considered)\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n BFS - used when all actions have the same cost. Systematic - Complete. Best FS where f(n) is depth of the node. FIFO queue. We can do an early goal test checking whether a node is a solution as soon as its generated rather than a late goal test that best FS uses where we wait until the node is popped off the queue. Always Finds optimal soln. Time and Space complexity = O(b^d) b = branching factor/ d = depth__________ Dijkstra's alg or uniform cost search: Best FS where eval fn is the cost of the path from root to current node i.e., path cost. Dij's alg is UCS without a goal as UCS is Dijkstra's Algorithm which is focused on finding a single shortest path to a single finishing point rather than the shortest path to every point. The complexity of uniform-cost search is characterized in terms of C' the cost of the optimal solution, and ϵ a lower bound on the cost of each action, with Then the algorithm’s worst-case time and space complexity is O(b^(1+[C' / ϵ]) which can be much greater than b^d. UCS is complete and cost optimal _______________ Depth First Search - best FS with f(n) = negative of the depth. usually implemented as a tree search rather than graph. Not cost optimal and is not complete in infinite spaces. The adv is that the space complexity is only O(bm) where m is max depth of tree. A variant called backtracking search uses even less memory as it generates only one successor at a time which reduces the time reqd to check for cyclic path to o(1) from O(m). ____________________ Depth limited and iterative deepening: DFS with a depth limit L and treat all nodes at L as if there's no successors. Time complexity is O(b^l) and Space comp is O(bl), not complete under incorrect l, thus we iteratively deepen it. For depth limited, we can also use the info to find the diameter of the state space graph and improve efficiency. For it. deepening, time complexity is O(b^d(or m)) based on if there's a soln. or not_________ Bi-directional search: Simultaneously searches frwd from initial and backwards from goal state. The motivation is b^d/2 + b^d/2. We need two frontiers and two tables of reached states to be tracked and we have a soln if the two frontiers collide\n\n## Module 3 Lecture Notes\nComplete: BFS, UCS, Iterative deepening, Bidirectional, rest are incomplete. Optimal Cost: Same as before, BFS: TC = SC = O(b^d); UCS: TC = SC = O(b^(1+[C' / ϵ])); DFS: TC = O(b^m) and SC = o(bm); Depth limited: TC = O(b^l) and SC = o(bl); It. deepening: TC = O(b^d) and SC = o(bd); Bi-directional: SC = TC = O(b^d/2)\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\nInformed search - uses domain specific hints about the location of goals in the form of heuristic function h(n). Greedy best first search: Expands based on lowest h(n) value, f(n) = h(n). Is a graph search, is complete within finite spaces but not infinite ones. Worst case time and space complexity = O(|V|) but with good heuristic, it can be reduced to O(bm).___________ A* Search: f(n) = g(n) path cost from initial state to node n + h(n) = estimated path cost of best path that continues from n to goal. is complete and if h(n) is admissible (never overestimates), it is also cost optimal. A heuristic is consistent if for every node n and every successor n' of n generated by an action a, h(n) <= c(n,a,n')+h(n') (Triangle inequality)__________ Search Contours: Continuous contours drawn in state space to visualize a search. The g costs are monotonic, they always increase as you go along a path, but f will monotonically increase iff heuristic is consistent. A* with a consistent h is optimally efficient. It is efficient as it prunes away search tree nodes that are unnecessary for optimal solution. A* is complete, cost optimal and optimally efficient but not the best as the number of nodes expanded can be exponential in the ln of soln.___________ Satisfying search: inadmissible h and weighted A*: If we are okay with suboptimal solutions, A* expands far fewer nodes. Weighted A* - f(n) = g(n) + W*h(n) for W>1m is a somewhat greedy search and the weight makes sure it doesn't miss the answer. There's a number of criteria for what counts as good enough for suboptimal, bounded suboptimal search - soln that is guarentted to be within a constant factor W of optimal cost. bounded cost search - soln whose cost is less than some cost C, unbounded cost search -soln of any cost as long as its quick. ___________ Memory Bound search: A* consumes a lot of memory and a state is store on the frontier in two places - as a node in the frontier and as an entry in reached states table. It can be stores in only one of these or just removed from reached when we proved its no longer required to save space. We can also keep reference counts of no, of times a state has been reached and remove it from table when there's no more ways left.Cont in notes.. \n\n## AIMA Chapter 3.6 Heuristic Functions\ncity-block distance/ Manhattan distance is the dist as sum of vertical and horizontal dist.____Effect pf heuristic accuracy on performance: One way to characterize it is the effective branching factor b* where N+1 = 1 +b*+b*^2+===b*^d where d = depth, N =total no. of nodes generate by A*. Pruning with an effective heuristic reduces Effective depth by a constant kh so total search cost reduces to O(b^(d-kh)). We say h2 dominates h1 if h2(n)>=h1(n), in this case h2 is always better than h1 as it causes lesser nodes. It is generally better to use h with higher values provided it is consistent.______ Generating heuristics for relaxed problems: A problem with fewer restrictions is a relaxed problem, so it adds edges to the state-space graph which may work as shortcuts so it might provide better solutions. the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. We can take the max of a collection of admissible heuristics and it will be the best but take slightly longer to compute._______ Generating h from subproblems: Pattern databases: Admissible h can also be derived from the solution cost of a subproblem. Pattern databases store such problems and these cannot be added__________ Generating h with landmarks: Precomputation is time-consuming but is worth it if the query will be encountered a vast number of times. Space and time complexity - is O(|v|^2) and O(|E|^3). Best to do this only for landmark points which can also be used as a part of bigger searches. shortcuts pre-defined for famous options is also a good ideas. Differential h is used in these cases________ Learning to search better: Metalevel state spaces capture internal state of a program that is searching in an ordinary/object level state space. This can be used to learn to search better and minimize the total cost._____________ Learning h from exp: A no. of features can be provided relevant to the state to predict the state's h value and this can help learn from exp\n\n## Module 4 Lecture Notes\n Algs. designed to save memory - beam search limits size of frontier but makes it suboptimal and incomplete, Iterative-deepeningA* follows ID where cutoff is small f-cost of any node that exceeded the cutoff of prev, Recursive BestFS - uses an f_limit to keep track of best alternative f and unwinds to the alt path when it exceeds the limit. As it unwinds, it replaces f-value of all the nodes with the best f-value of its children if it ever wants to re-enter later. It is optimal if h(n) is admissible.  But both IDA* and RBFS use too little memory and may end up re-exploring same states so it_makes_sense_todetermine_how_much_memory_is_avaialable_and_allow_an_alg_to_use_it_all...__Memory-bound_A*(MA*)and_Simplified_MA*_do this. SMA* expands the best leaf and deletes the worst leaf, is complete if any reachable soln is there. It is optimal if any optimal soln is reachable._______ Bi-directional heuristic search: If we try using the same f, it wont work so we use fF(n) = gF(n) +hF(n) for nodes in fwd and replace F with B for backwards. Evaluation function of priority queues: f2(n) = max(2g(n), g(n) + h(n)). hF estimates distance to goal while hB estimates distance to start, this is a front-to-end appraoch. A front-to-front apprach estimates dist to the other frontier.________________\n\n## Module 4 Definitions\n* **A* space complexity** - O(b^d)\n* **A* time complexity** - O(b^d)\n* **Greedy best first time complexity** - O(b^m) where m is max depth\n* **Greedy best first space complexity** - O(b^m) where m is max depth\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\nAdversarial search has two or more agents with conflicting goals. There are 3 stances towards multi-agent networks. First is to consider them in the aggregate as an economy when there's a large no. of them. Second is to consider adversarial agents as a part of the env that makes it nondeterministic. Third to explicitly model the adv_agentswith techniques of adversarial game-tree search which is what we cover. Pruning ignores portions of trees that make no difference, hence making the search more efficient. A heuristic evaluation function is used to estimate who is winning whenever we stop searching._________ Two-player zero-sum games: __Minimax__ is used for Perfect info zero-sum games. We use move as synonym for action and position for state. A game has an initial state, legal set of moves, player whose turn it is to move, result(transition model), terminal test(for terminal state), utility function. The game tree is a search tree that follows every sequence of moves to the terminal state.\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\nMinimax search: Optimal strategy is worked out by determined by working out the minimax value of each state in the tree. We assume both players play optimally. Minimax decision is the optimal choice for min/max as it leads to the state with lowest/highest minimax value. The minimax algorithm performs a depth-first exploration of a game tree and the space and time complexities are as expected. If we have more than two players, we replace the single value for each node with a vector of values which gives the utility of that state from each player's perspective. Multi-player games also usually involve alliances which can be sort of predicted as usually the bottom two team against the top until it weakens___________ Alpha-Beta Pruning: Alpha is the value of the best from max player -> highest value choice we hound so far. Think alpha as \"at least\". Beta is lowest value choice, at most.__________ Move ordering: With perfect move ordering, the no. of nodes to examine are only O(b^m/2) and the effective branching factor becomes root of b rather than b. Dynamic move-ordering tries first the moves that were found to be the best in the past. We can use iterative deepening to achieve this with previous rankings informing the move ordering of new depth/ Best moves are called killer moves and to try them first is the killer move heuristic. Different permutations can end up in the same position which causes repeated states, this is called transposition and a transposition table that caches heuristic values of states is important. Even with alpha-beta pruning and move ordering, can't use minimax for chess and go coz too complex. Type A and B strategies are used for these, A is where all possible moves up to a certain depth are considered and evaluated to estimate utility of that depth whereas B ignores moves that look bad and followers promising lines as far as possible.\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\nTo make use of limited computation time, an evaluation fn for heuristics is used to cutoff trees early and consider them terminal. This can be replaced with a cutoff test that returns true for terminal states. A heuristic eval fn returns the expected utility of the state to the player. Most eval fns work by calculating various features of the state and return an expected value. Since not all features are equal, we can use weighted linear function when adding up the individual values. It doesn't have to be proportional, just show a measure of preference. We are here making an assumption that the contribution of each factor is independent but it may not always be so and we can use a non-linear combination of features in addition. _____________ Cutting-off search: We cut-off search at a certain depth and return the eval for that state but must make sure the depth gets incremented. Eval fns should only be applied to positions that are quiescent. For nonquiescent positions, search continues till one is reached. The horizon effect is more difficult to eliminate. One strategy to mitigate the effect is to allow singular extensions _______ Forward Pruning: Prunes moves that appear to be poor moves but might be good, Beam cut is an eg. Probcut is another eg that prunes nodes probably outside the alpha beta window. Late move reductions works under the assumption that move ordering has been done well and thus late moves are less likely to be good so we limit the depth__________ Search vs lookup, loopup tables are used instead of searches for when search is over-kill or easy reference is available as the state is popular. \n\n## AIMA Chapter 5.5 Stochastic Games\ninclude a random element and the game tree must include chance nodes in addition to max and min nodes (between min and max nodes). Instead of minimax value, we can only calculate the expectiminimax value now.__________ Evaluation for games of chance: return values that are a positive linear transformation of the probability of winning. Complexity is increased to O(b^m * n^m) where n is the no. of distinct rolls. Even chance nodes can be pruned by placing bounds on the possible values of utility functions.\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\nUtility function captures the agent's preferences and assigns a single number to express the desirability of a state. The expected utility of an action given evidence is the avg utility of the outcomes.  If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score averaged over all the possible environments\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\nConstraints on rational preferences: Orderability (agent must have preference of one over other or rate them equally), Transitivity (if an agent prefers A to B and B to C, it must prefer A to C), Continuity (If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and  C with probability 1-p.), Substitutability (If the agent is indifferent between 2, it can use them interchangeably), Monotonicity (if A is preferred over B, lotteries with higher prob of A should be preferred), Decomposability (Compound lotteries can be reduced into single ones, or one equivalent one) These are just about preferences not utility. Value function is a preference ranking on states in a deterministic environment, also called ordinal utility function.\n\n## AIMA Chapter 16.3 Utility Functions\nPreference elicitation - presenting choices to humans and using observed preferences to pin down underlying utility function. Normalized utilities use a scale of 0 to 1. Value of statistical life is used to determine costs and benefits of regulations and interventions. Quality-adjusted life year is another measure for value of life. Expected monetary value is the sum of monetary value * probability of that value. U(L) < U(SEMV (L)) represents agents who are risk-averse in right and risk-seeking to the left. Value an agent will accept in lieu of a lottery is called the certainty equivalent of the lottery. The insurance premium of a lottery is the difference between its EMV and certainty equivalent. Usually the estimated utility of the best choice is too high even with unbiased inputs due to optimizer's curse. _________ Decision theory is normative (describes how a rational agent should act). Descriptive theory describe how agents actually act. The irrational preferences can be due to certainty effect where people are strongly attracted to gain that are certain. Ambiguity aversion is also a trait seen in people, a lower version of certainty effect. Decision can also be saved using word choice which is the framing effect. Anchoring effect is how adding a really high priced option grounds other options.\n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Pruning** - Ignore portions of tree that don't make a difference\n* **Utility function** -  the final numeric value to player when the game ends in terminal state\n* **Quiescent position** - positions in which there is no pending move that would wildly swing the evaluation\n* **Horizon effect** - opponent’s move that's bad and is ultimately unavoidable, but can be temporarily avoided by the use of delaying tactics\n* **Singular extensions** - moves_that_are_clearly_better_than_all other moves in a given position, even when the search would normally be cut off at that point\n* **Policy** - a mapping from every possible state to the best move in that state\n* **Principle of maximum expected utility** - a rational agent should choose the action that maximizes the agent’s expected utility\n\n\n## WARNING: Your definition of 'Constraint Propagation' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\nSearch problems search the state space comprised of indivisible black boxes. Here, we break open the back box using a factored representation for each state: a set of variables, each of which has a value. A CSP has 3 components: X is a set of variables {X1..Xn}, D is a set of domains, {D1,....Dn} and C a set of constraints. Each constraint can be seen as a pair of scope ( tuple of variables) and rel (relation between those variables). In a map coloring problem, X is the set of states, D is the set of colors, and C contains the states that share a border. President constraints are used when one task with 'd' duration has to be completed before another can start ( T1+d <= T2) _______ The simplest kind of CSPs involve variables that have discrete, finite domains. A discrete domain can be infinite in which we must use implicit constraints (T1+d<T2) rather than the explicit tuples of values. While special algorithms exist for solving linear constraints on integer variables, no such exists for nonlinear constraints. CSP with continuous domains are common in real-world (like linear programming). The types of constraints are unary, binary and ternary. A constraint involving an arbitrary no. of variables is a global constraint. Constraints can be represented ina a constraint hypergrpah that shows ordinary nodes as circles, hyder-nodes which represent n-ary constraint as squares. n-ary constraints can be transformed to binary with enough auxiliary variable introductions. CSPs also have preference constraints, that would be a constrainted optimization problem.\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n There are diff types of local consistency- Node consistency: a single variable is node-consistent if all the values in the variable's domain satisfy the variable's unary constraints. ___________ Arc consistency:if every value in its domain satisfies the variable’s binary constraints. AC-3 is the most popular method for enforcing arc-consistency. O(c*d^3) is the time complexity. To make every variable arc-consistent, the AC-3 algorithm maintains a queue of arcs to consider. Initially, the queue contains all the arcs in the CSP. (Each binary constraint becomes two arcs, one in each direction.) AC-3 then pops off an arbitrary arc (Xi,Xj) from the queue and makes arc-consistent with respect to Xj . If this leaves Di unchanged, the algorithm just moves on to the next arc. But if this revises Di (makes the domain smaller), then we add to the queue all arcs (Xk, Xi) where Xk  is a neighbour of Xi. If one Di gets revised to nothing, we return a failure. _____________ Path Consistency - tightens down the binary constraints with implicit constraints that are inferred by looking at triples of variables________ k-consistency: stronger forms of propagation. A CSP is strongly k-consistent if it is k0-consistent, k-1 consistent... 1-consistent. ____________ Global Constraints: useful to remove variables in the constraint that has a singleton domain and delete that variable's values from domains of remaining values. Resource constraint or utmost constraint is important in real life. For large resource-limited problems, it isn't possible to represent each variable in a domain and hence upper and lower bounds are used and domains are managed by bounds propagation. A CSP is bounds-consistent if for every variable X for both upper and lower bound values in X, there exists Y that satisfies the constraint\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Constraint Prop process can leave multiple variables with multiple possible values. In this case, we search for a solution using backtracking if we run into issues. To select an unassigned variable, there are several strategies including choosing the variable the minimum-remaining-values (MRV) (also called the most constrained variable, fail-first), Degree heuristic (picks the variable that has the most number of constraints, useful as a tie-breaker). Once a variable is selected, the least-constraining value is usually chosen. ____________ Forward checking is used whenever a variable is assigned to establish arc consistency for it, is a method of inference used during search. Maintaining Arc Consistency (MAC) algorithm detects inconsistencies where two or more neighbours are left with the same color left by starting the queue of arcs when inference calls AC3 with only arcs (Xj,Xi) where Xj are unassigned variables that are neighbors of Xi. ______________ Intelligent backtracking: instead of chronological backtracking of jumping to the most recent decision point, we keep track of assignments that caused the conflict (conflict set) and backjump to recent assignment in the set. Forward checking can supply this set with no extra work (add x to the set when x is deleted from a domain during forward-checking). Conflict-directed backjumping notices failure even when the variable domains are not empty by checking the variable assignment which caused this conflict to have no consistent solution.________________ Constraint Learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables is called no-good. \n\n## AIMA Chapter 6.4 Local Search for CSPs\n min-conflicts heuristic chooses the value that results in min. no. of conflicts with other variables. Plateau search can help local search find its way off the series of plateaus which is the landscape of a CSP under min-conflicts. This wandering on the plateau can be directed with tabu search. Simulated annealing can also be used to escape from plateaus. Constraint weighting can be used to concentrate the search on important constraints \n\n## AIMA Chapter 6.5 The Structure of Problems\n Decomposing into subproblems is required for dealing with vast data. Some subproblems may be independent which can be ascertained by simply finding the connected components of the constraint graph. A constraint graph is a tree when any two variables are connected by only one path, needs bi-directional arc consistency. Topological sort is ordering the tree such that each variable only appears after its parent. Once we have a b-directional arc consistent graph (Time - O(n*d^2)), there's no need to backtrack we know the values we chose for parent are such that the child has a valid value. This is an efficient alg for trees and more complex graphs can be made trees by removing nodes or collapsing nodes together. _________ Cutset Conditioning: We can analyze a graph and see which points can be removed to create a tree, fix a value for them and remove them (cycle cutset) and the value from their neighbours. __________ Tree decomposition: Transform the original graph into a tree where each node consists of a set of variables such that each node is accounted for at least once, connected variables must be together. _______________ Value symmetry occurs when each variable has equal values to assign and we break this by introducing a symmetry-breaking constraint.\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Complete assignment** -  every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment\n* **Constraint propagation** - using constraints to reduce number of legal values for a variable, which in turn can reduce the legal values for another and so on\n* **Time complexity of ac-3** - O(c*d^3)\n* **Global constraint** - one involving an arbitrary number of variables (but not necessarily all variables)\n* **Constraint learning** - the idea of finding a minimum set of variables from the conflict set that causes the problem\n* **No-good** - set of variables from constraint learning\n* **Plateau search** - allowing sideways moves to another state with the same score\n* **Tabu search** - : keeping a small list of recently visited states and forbidding the algorithm to return to those states.\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\nThe central component of a knowledge-based agent is its knowledge base (KB) which is a set of sentences expressed in knowledge representation language. When a sentence is given, not derived it's an axiom. New sentences are added to KB using inference, though this develops over time, the agent also typically starts with some background knowledge. Each time an agent program is called, 1. it tells the KB what it perceives, 2/ it asks KB what action it should perform 3. tells the KB which action was chosen and returns the action for execution.\n\n## AIMA Chapter 7.2 The Wumpus World\n Example of a knowledge based agent at work \n\n## AIMA Chapter 7.3 Logic\n Logic must define the semantics or meaning of sentences that define the truth of each sentence with respect to each possible world.  Model is used instead of potential worlds, if a sentence A is true in a model M, M satisfies A or sometimes, M is a model of A. Logical entailment between sentences says that a sentence follows logically from another (A |= B), it is the case only if all points in A and B follow. The KB is false in models that contradict what the agent knows. Entailment can be used to carry out logical inference. An inference algorithm that derives only entailed sentences is called sound or truth-preserving. An inference algorithm is complete if it can derive any sentence that is entailed. General sentences are produced by learning but it is always fallible. But with good learning procedures, there is reason for optimism. \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n The syntax of propositional logic defines allowable sentences. The atomic sentences consist of a single proposition symbol which can be true or false. Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. Connectivities in common use are: ¬(not) called the negation, ∧(and) called the conjunction(its parts are conjuncts), ∨(or) is a disjunction, ⇒(implies) called an implication, rules or if-then statements (In W⇒W1, W is the premise or antecedent and W1 is the conclusion or consequent), ⇔ (iff / if and only if) biconditional. This is also the order of their priority. The rules can be used to write the semantics using the truth value of each proposition symbol. The rules can also be expressed with truth tables that specify the truth value of a complex sentence for each possible assignment of truth value to its components. With semantics in place for propositional logic, we can construct a KB by first focusing on immutable aspects. An algorithm is sound if it implements directly the definition of entailment and complete if it works for any KB and A always terminates - only finite models. \n\n## AIMA 7.5 Propositional Theorem Proving\n Entailment can be done by theorem proving - applying the rules of inference directly to sentences n our KB to construct a proof of the desired sentence without consulting models. Is more efficient than model checking if the no. of models is large but length of proof is small. Logical Equivalence - two sentences and are logically equivalent if they are true in the same set of models (A ≡ B). Validity - if true in all models, valid sentences are called tautologies. Satisfiability - if it is true in or satisfied by some model, these two are connected as A is satisfiable iff ¬A is not valid. Inference rules that can be applied to derive a proof. Modus Ponens Rule : α ⇒ β, α / β means that whenever α ⇒ β and α are given, then sentence β can be inferred. And- elimination is another such rule, α ∧ β/ α. Logical systems are monotonic as the set of entailed sentences can only increase as information is added to the knowledge base Rest in Notes \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** - use a process of reasoning over an internal representation of knowledge to decide what actions to take\n* **Knowledge level** - we need specify only what the agent knows and what its goals are, in order to determine its behavior\n* **Implementation level** - How knowledge is implemented\n* **Declarative approach** - the agent designer uses TELL sentences one by one until the agent knows how to operate in its environment\n* **Procedural approach** - encodes desired behaviors directly as program code\n* **Grounding** - he connection between logical reasoning processes and the real environment in which the agent exists\n* **Literal** - either an atomic sentence (a positive literal) or a negated atomic sentence (a negative literal).\n* **Logical entailment** - A |= B\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}