{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "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": "59f9ccf7-3642-4da5-d23e-57554ca33729"
      },
      "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": 1,
      "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": "a71ca967-5045-4fe3-f13b-3bbade97681a"
      },
      "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": 2,
      "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": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "fb6b4c68-eda1-48ac-c7d8-b97652dd314c"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" AI has two dimemsions namely human/rational & thought/behviour(act) - so four combinations. Turing Test Approach (Acting Humanly) checks if a computer can pass as human \\\n",
        "             while answering questions. It requires NLP, Knowledge Representation, Automated Reasoning, ML capabilities. Additionally, Total Turing Test checks \\\n",
        "             CV and Robotics abilities. Cognitive Modeling Approach (Thinking Humanly) learns human thought through 1)introspection, 2) psychological experiments, 3)brain imaging. \\\n",
        "             Laws of Thought Approach (Thinking Rationally) was based on the syllogisms by Aristotle that provided patterns for argument structures to yield corresct \\\n",
        "             solutions given correct premises. It was meant to govern the operations of the mind and initiated the field of logic. \\\n",
        "             Obstacles to this approach are the difficulty to represent informal knowledge in formal terms and the difference in problem solving in principle vs practice. \\\n",
        "             The Rational Agent Approach (Acting Rationallly) \\\n",
        "             expects agents to operate autonomously based on perceived input, adapt to change and pursue goals. Similar to laws of thought, making correct inferences \\\n",
        "             but more general and can be represented mathematically. Here, inference is useful not necessary. Focus is on the study and construction of agents that do the right thing, which becomes the objective \\\n",
        "             provided to the agent. This is called the Standard Model. \\\n",
        "             The problem of achieving agreement between the true preferences and the objective put into the machine is called the value alignment problem. \\\n",
        "             The values or objectives put into the machine must be aligned with those of the human. \n",
        "             \"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\" Limits are - Argument from Informality, Argument from Disability, Mathematical Objection, Measuring AI (Turing test). \\\n",
        "              Firstly, Turing argues about informality where he says that human behaviour is far too complex to be represented by a formal set of rules that can be coded onto \\\n",
        "              a computer program. \\ \n",
        "              The embodied cognition approach claims that it makes no sense to consider the brain separately: \\\n",
        "              cognition takes place within a body, which is embedded in an environment. \\\n",
        "              The system is to be studied as a whole; the brain’s functioning exploits regularities in its environment, including the rest of its body. \\\n",
        "              Under the embodied cognition approach, robotics, vision, and other sensors become central, not peripheral. \\\n",
        "              Secondly, Turing states that machines cannot do certain things like express emotions, be the subject of its own thought or do something really new. \\\n",
        "              Finally, Turing states that many mathematical questions are unanswerable by some formal systems. \\\n",
        "              Go ̈del sentence G(F) is a sentence of F, but cannot be proved within F. If F is consistent, then G(F) is true. \\\n",
        "              Machines are mentally inferior to humans since they are formal systems limited by the incompleteness theorem. \\\n",
        "              They cannot establish the truth of their own Go ̈del sentence. Humans don't have this limitation. \\\n",
        "              Issues with the theorem - an agent should not be ashamed that it cannot establish the truth of some sentence while other agents can; \\\n",
        "              results apply to mathematics, not to computers (cannot prove something that is impossible to prove); \\\n",
        "              it applies only to formal systems that are powerful enough to do arithmetic (Turing machines which are infinite).\n",
        "              \"\"\"\n",
        "\n",
        "chapter27_2 = \"\"\" Chinese Room Argument talks about computers having understanding when they perform a task. \\\n",
        "              He also talks about biological naturalism, according to which mental states are high-level emergent features \\\n",
        "              caused by low-level physical processes in the neurons, and it is the (unspecified) properties of the neurons that matter. \\\n",
        "              Another issue is conciousness which refers to the awareness of the outside world. \\\n",
        "              Individual aspects of consciousness—awareness, self-awareness, attention— can be programmed and can be part of an intelligent machine. \\\n",
        "              Behaving intelligently requires some degree of awareness, varying from task to task. \\\n",
        "              Tasks involving human interaction will require a model of human subjective experience.\n",
        "              \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system. \"\"\"\n",
        "\n",
        "chapter2_2 = \"\"\" For performance measures, we consider the notion of consequentialism - evaluating agent's behaviour by consequences. \\\n",
        "             Performance measure evaluates the desirability of an agent given a sequence of environmental states. \\\n",
        "             Rule of thumb is to design performance measures according to what is to be achieved in the environment, rather than how the agent should behave. \\\n",
        "             Rationality depends on: performance measure that defines the criterion of success, agent’s prior knowledge of the environment, actions that it can perform \\\n",
        "             and the percept sequence to date. \\\n",
        "             In an unknown environment, agents may learn through exploration. Information gathering - performing actions to modify future percepts. \\\n",
        "             An agent lacks autonomy if it relies on prior knowledge of its designer rather than its own percepts and learning processes to perform actions. \\\n",
        "             A rational agent should be autonomous and learn what it can to compensate for partial or incorrect prior knowledge.\n",
        "             \"\"\"\n",
        "\n",
        "chapter2_3 = \"\"\" Task environments are problem to which rational agents are the solutions. They are usually specified using the PEAS description \\\n",
        "             (Performance, Environment, Actuators, Sensors). \\\n",
        "             Properties of task environment - fully/partially observable, unobservable; single/multi agent; deterministic/non-deterministic; \\\n",
        "             stochatic (similar to non-deterministic but with probabilities); episodic (experience divided into atomic episodes each independant of the other) \\\n",
        "             /sequential(current decision could affect all future decisions - may have to think ahead); static/dynamic; discrete/ continuous \\\n",
        "             (state of the environment, the way time is handled, and the percepts and actions of the agent); known/unknown (not about environment but agent's knowledge); \\\n",
        "             Known environment, the outcomes (or outcome probabilities if the environment is nondeterministic) for all actions are given. \\\n",
        "             If unknown, the agent will have to learn how it works in order to make good decisions. \\\n",
        "             The distinction between known and unknown environments differs from fully and partially observable environments. \\\n",
        "             Environment may be partially observable & known — for example, in solitaire, rules are known but still unable to see the cards that have not yet been turned over. \\\n",
        "             Unknown environment can be fully observable — in a new video game, the screen may show the entire game state but I what the buttons do is not knownn until tried. \\\n",
        "             The hardest case is partially observable, multiagent, nondeterministic, sequential, dy- namic, continuous, and unknown. \n",
        "             \"\"\"\n",
        "\n",
        "chapter2_4 = \"\"\" Agent program implements agent function - run on agent architecture (computer program with sensors and actuators) \\\n",
        "             '''\n",
        "\n",
        "             function TABLE_DRIVEN_AGENT(percept) returns an action\n",
        "                persistent: percepts, a sequence, initally empty\n",
        "                            table, actions indexed by percept sequences, initially fully indexed\n",
        "\n",
        "                append percept to end of percepts\n",
        "                return LOOKUP(percepts, table)\n",
        "\n",
        "            function SIMPLE-REFLEX-AGENT(percept) returns an action \n",
        "                persistent: rules, a set of condition–action rules\n",
        "                \n",
        "                state←INTERPRET-INPUT(percept) \n",
        "                rule←RULE-MATCH(state,rules) \n",
        "                return rule.ACTION\n",
        "\n",
        "            function MODEL-BASED-REFLEX-AGENT(percept) returns an action \n",
        "                persistent: state, the agent’s current conception of the world state\n",
        "                            transition model, sensor model, rules\n",
        "                            action, the most recent action, initially none\n",
        "\n",
        "                state←UPDATE-STATE(state,action,percept,transition model,sensor model) \n",
        "                rule←RULE-MATCH(state,rules)\n",
        "                return rule.ACTION\n",
        "                \n",
        "             '''\n",
        "             Goal-based agents achieve their goals, utility-based agents maximize their own expected happiness.\n",
        "             Learning agent - learning element, performance element, critic, problem generator\n",
        "             \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive its environment through sensors and act upon it through actuators\",\n",
        "\"percept\" : \"an agent's perceptual input at a given instance\",\n",
        "\"agent function\" : \"maps a percept sequence to an action\",\n",
        "\"Rational agent\" : \"for each percept sequence, selects an action that is expected to max performance measure\",\n",
        "\"Omniscient agent\" : \"knows the actual outcome of its actions and can act accordingly\",\n",
        "\"Deterministtic\" : \"next state of the environment is completely determined by the current state and the action executed by the agent\",\n",
        "\"simple reflex agent\" : \"selects actions on the basis of the current percept, ignoring the rest of the percept history\",\n",
        "\"model-based agent\" : \"transition and sensor model keep track of the state of the world—given the limitations of the agent’s sensors\",\n",
        "\"transition model\" : \"a description of how the next state depends on the current state and action\",\n",
        "\"sensor model\" : \"a description of how the current world state is reflected in the agent’s percepts\",\n",
        "\"utility function\" : \"internalization of the agent's performance measure\",\n",
        "\"Qualification problem\" : \"the issue with capturing every contingency of appropriate behaviour in a set of necessary and sufficient logical rules\",\n",
        "\"qualia\" : \"intrinsic nature of experiences\",\n",
        "\"Weak AI\" : \"refers to the idea that machines could act as if they were intelligent\",\n",
        "\"Strong AI\" : \"assertion that machines that do so are actually consciously thinking (not just simulating thinking)\",\n",
        "\"Human-level AI or general AI\" : \"Programs that can solve a wide range of tasks, including novel ones, as well as a human\"\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter2_4.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter2_4))\n"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 498\n",
            "The length in characters is 1468\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 2023
        },
        "outputId": "0e4bdc13-389d-4d14-c604-de578f04f272"
      },
      "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": 5,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n AI has two dimemsions namely human/rational & thought/behviour(act) - so four combinations. Turing Test Approach (Acting Humanly) checks if a computer can pass as human              while answering questions. It requires NLP, Knowledge Representation, Automated Reasoning, ML capabilities. Additionally, Total Turing Test checks              CV and Robotics abilities. Cognitive Modeling Approach (Thinking Humanly) learns human thought through 1)introspection, 2) psychological experiments, 3)brain imaging.              Laws of Thought Approach (Thinking Rationally) was based on the syllogisms by Aristotle that provided patterns for argument structures to yield corresct              solutions given correct premises. It was meant to govern the operations of the mind and initiated the field of logic.              Obstacles to this approach are the difficulty to represent informal knowledge in formal terms and the difference in problem solving in principle vs practice.              The Rational Agent Approach (Acting Rationallly)              expects agents to operate autonomously based on perceived input, adapt to change and pursue goals. Similar to laws of thought, making correct inferences              but more general and can be represented mathematically. Here, inference is useful not necessary. Focus is on the study and construction of agents that do the right thing, which becomes the objective              provided to the agent. This is called the Standard Model.              The problem of achieving agreement between the true preferences and the objective put into the machine is called the value alignment problem.              The values or objectives put into the machine must be aligned with those of the human. \n             \n\n## AIMA Chapter 27.1 The Limits of AI\n Limits are - Argument from Informality, Argument from Disability, Mathematical Objection, Measuring AI (Turing test).               Firstly, Turing argues about informality where he says that human behaviour is far too complex to be represented by a formal set of rules that can be coded onto               a computer program. \\ \n              The embodied cognition approach claims that it makes no sense to consider the brain separately:               cognition takes place within a body, which is embedded in an environment.               The system is to be studied as a whole; the brain’s functioning exploits regularities in its environment, including the rest of its body.               Under the embodied cognition approach, robotics, vision, and other sensors become central, not peripheral.               Secondly, Turing states that machines cannot do certain things like express emotions, be the subject of its own thought or do something really new.               Finally, Turing states that many mathematical questions are unanswerable by some formal systems.               Go ̈del sentence G(F) is a sentence of F, but cannot be proved within F. If F is consistent, then G(F) is true.               Machines are mentally inferior to humans since they are formal systems limited by the incompleteness theorem.               They cannot establish the truth of their own Go ̈del sentence. Humans don't have this limitation.               Issues with the theorem - an agent should not be ashamed that it cannot establish the truth of some sentence while other agents can;               results apply to mathematics, not to computers (cannot prove something that is impossible to prove);               it applies only to formal systems that are powerful enough to do arithmetic (Turing machines which are infinite).\n              \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Chinese Room Argument talks about computers having understanding when they perform a task.               He also talks about biological naturalism, according to which mental states are high-level emergent features               caused by low-level physical processes in the neurons, and it is the (unspecified) properties of the neurons that matter.               Another issue is conciousness which refers to the awareness of the outside world.               Individual aspects of consciousness—awareness, self-awareness, attention— can be programmed and can be part of an intelligent machine.               Behaving intelligently requires some degree of awareness, varying from task to task.               Tasks involving human interaction will require a model of human subjective experience.\n              \n\n## AIMA 2.1 Agents and Environments\n The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n For performance measures, we consider the notion of consequentialism - evaluating agent's behaviour by consequences.              Performance measure evaluates the desirability of an agent given a sequence of environmental states.              Rule of thumb is to design performance measures according to what is to be achieved in the environment, rather than how the agent should behave.              Rationality depends on: performance measure that defines the criterion of success, agent’s prior knowledge of the environment, actions that it can perform              and the percept sequence to date.              In an unknown environment, agents may learn through exploration. Information gathering - performing actions to modify future percepts.              An agent lacks autonomy if it relies on prior knowledge of its designer rather than its own percepts and learning processes to perform actions.              A rational agent should be autonomous and learn what it can to compensate for partial or incorrect prior knowledge.\n             \n\n## AIMA 2.3 The Nature of Environments\n Task environments are problem to which rational agents are the solutions. They are usually specified using the PEAS description              (Performance, Environment, Actuators, Sensors).              Properties of task environment - fully/partially observable, unobservable; single/multi agent; deterministic/non-deterministic;              stochatic (similar to non-deterministic but with probabilities); episodic (experience divided into atomic episodes each independant of the other)              /sequential(current decision could affect all future decisions - may have to think ahead); static/dynamic; discrete/ continuous              (state of the environment, the way time is handled, and the percepts and actions of the agent); known/unknown (not about environment but agent's knowledge);              Known environment, the outcomes (or outcome probabilities if the environment is nondeterministic) for all actions are given.              If unknown, the agent will have to learn how it works in order to make good decisions.              The distinction between known and unknown environments differs from fully and partially observable environments.              Environment may be partially observable & known — for example, in solitaire, rules are known but still unable to see the cards that have not yet been turned over.              Unknown environment can be fully observable — in a new video game, the screen may show the entire game state but I what the buttons do is not knownn until tried.              The hardest case is partially observable, multiagent, nondeterministic, sequential, dy- namic, continuous, and unknown. \n             \n\n## AIMA 2.4 The Structure of Agents\n Agent program implements agent function - run on agent architecture (computer program with sensors and actuators)              '''\n\n             function TABLE_DRIVEN_AGENT(percept) returns an action\n                persistent: percepts, a sequence, initally empty\n                            table, actions indexed by percept sequences, initially fully indexed\n\n                append percept to end of percepts\n                return LOOKUP(percepts, table)\n\n            function SIMPLE-REFLEX-AGENT(percept) returns an action \n                persistent: rules, a set of condition–action rules\n                \n                state←INTERPRET-INPUT(percept) \n                rule←RULE-MATCH(state,rules) \n                return rule.ACTION\n\n            function MODEL-BASED-REFLEX-AGENT(percept) returns an action \n                persistent: state, the agent’s current conception of the world state\n                            transition model, sensor model, rules\n                            action, the most recent action, initially none\n\n                state←UPDATE-STATE(state,action,percept,transition model,sensor model) \n                rule←RULE-MATCH(state,rules)\n                return rule.ACTION\n                \n             '''\n             Goal-based agents achieve their goals, utility-based agents maximize their own expected happiness.\n             Learning agent - learning element, performance element, critic, problem generator\n             \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive its environment through sensors and act upon it through actuators\n* **Percept** - an agent's perceptual input at a given instance\n* **Agent function** - maps a percept sequence to an action\n* **Rational agent** - for each percept sequence, selects an action that is expected to max performance measure\n* **Omniscient agent** - knows the actual outcome of its actions and can act accordingly\n* **Deterministtic** - next state of the environment is completely determined by the current state and the action executed by the agent\n* **Simple reflex agent** - selects actions on the basis of the current percept, ignoring the rest of the percept history\n* **Model-based agent** - transition and sensor model keep track of the state of the world—given the limitations of the agent’s sensors\n* **Transition model** - a description of how the next state depends on the current state and action\n* **Sensor model** - a description of how the current world state is reflected in the agent’s percepts\n* **Utility function** - internalization of the agent's performance measure\n* **Qualification problem** - the issue with capturing every contingency of appropriate behaviour in a set of necessary and sufficient logical rules\n* **Qualia** - intrinsic nature of experiences\n* **Weak ai** - refers to the idea that machines could act as if they were intelligent\n* **Strong ai** - assertion that machines that do so are actually consciously thinking (not just simulating thinking)\n* **Human-level ai or general ai** - Programs that can solve a wide range of tasks, including novel ones, as well as a human\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 = \"\"\" References and mutabililty - strings are immutable while lists are mutable \\n\n",
        "                            >>>x='foo ' \\n\n",
        "                            >>> y = x \\n\n",
        "                            >>> x = x.strip() # new obj \\n\n",
        "                            >>> x \\n\n",
        "                            'foo' \\n\n",
        "                            >>> y \\n\n",
        "                            'foo ' \\n\n",
        "                            >>> x = [1, 2, 3, 4] \\n\n",
        "                            >>> y = x \\n\n",
        "                            >>> x.append(5) #same obj \\n\n",
        "                            >>> y \\n\n",
        "                            [1, 2, 3, 4, 5] \\n\n",
        "                            >>> x \\n\n",
        "                            [1, 2, 3, 4, 5] \\n\n",
        "\n",
        "                            Python doesn’t allow function overloading like Java does. Unlike Java, a Python function is specified by its name alone. \\\n",
        "                            Two different functions can’t have the same name, even if they have different numbers, order, or names of arguments. \\\n",
        "                            Operator overloading (overloading +, ==, -, etc.) is possible using special methods on while implementing a class. \\\n",
        "                            *args - Suppose you want to accept a variable number of non-keyword arguments to your function. \\\n",
        "                            **kwargs - Suppose you want to accept a variable number of keyword arguments to your function. \\\n",
        "\n",
        "                            '''\n",
        "                            class DiGraph:\n",
        "                              def search(self, u, visited):\n",
        "                                  # If we haven't visited this node...\n",
        "                                  if u not in visited:\n",
        "                                      yield u # yield it\n",
        "                                      visited.add(u) # and remember we've visited it now.\n",
        "                                      # Then, if there are any adjacent nodes...\n",
        "                                      if u in self.adj:\n",
        "                                          for v in self.adj[u]: # for each adjacent node...\n",
        "                                              # search for all nodes reachable from *it*...\n",
        "                                              for w in self.search(v, visited):\n",
        "                                                  # and yield each one.\n",
        "                                                  yield w\n",
        "                            '''\n",
        "                            \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"ability of a literal to have its value modified\",\n",
        "}"
      ],
      "execution_count": 152,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1b7c4268-f4f0-4062-b3ae-7556830c9579"
      },
      "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": 153,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n References and mutabililty - strings are immutable while lists are mutable \n\n                            >>>x='foo ' \n\n                            >>> y = x \n\n                            >>> x = x.strip() # new obj \n\n                            >>> x \n\n                            'foo' \n\n                            >>> y \n\n                            'foo ' \n\n                            >>> x = [1, 2, 3, 4] \n\n                            >>> y = x \n\n                            >>> x.append(5) #same obj \n\n                            >>> y \n\n                            [1, 2, 3, 4, 5] \n\n                            >>> x \n\n                            [1, 2, 3, 4, 5] \n\n\n                            Python doesn’t allow function overloading like Java does. Unlike Java, a Python function is specified by its name alone.                             Two different functions can’t have the same name, even if they have different numbers, order, or names of arguments.                             Operator overloading (overloading +, ==, -, etc.) is possible using special methods on while implementing a class.                             *args - Suppose you want to accept a variable number of non-keyword arguments to your function.                             **kwargs - Suppose you want to accept a variable number of keyword arguments to your function. \n                            '''\n                            class DiGraph:\n                              def search(self, u, visited):\n                                  # If we haven't visited this node...\n                                  if u not in visited:\n                                      yield u # yield it\n                                      visited.add(u) # and remember we've visited it now.\n                                      # Then, if there are any adjacent nodes...\n                                      if u in self.adj:\n                                          for v in self.adj[u]: # for each adjacent node...\n                                              # search for all nodes reachable from *it*...\n                                              for w in self.search(v, visited):\n                                                  # and yield each one.\n                                                  yield w\n                            '''\n                            \n\n## Module 2 Definitions\n* **Mutability** - ability of a literal to have its value modified\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",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "ff937881-9076-4061-fec4-7067abd9d64c"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Search problem is defined by 1) Set of states - state space, 2) Initial state 3) Set of one or more goal states \\\n",
        "             4) Finite set of actions, 5) Transition model 6) Action-cost function. \\\n",
        "             Search algorithm data structure - NODE has the following components: State, Parent, Action, Path-cost.\n",
        "             Frontier is stored in queue with the following possible operations: IsEmpty(), Pop(), Top(), Add().\n",
        "             \"\"\"\n",
        "\n",
        "chapter3_2 = \"\"\" \n",
        "             '''\n",
        "             function BEST-FIRST-SEARCH(problem, f) returns a solution node or failure \n",
        "                node←NODE(STATE=problem.INITIAL)\n",
        "                frontier ← a priority queue ordered by f , with node as an element\n",
        "                reached←a lookup table, with one entry with key problem.INITIAL and value node \n",
        "                while not IS-EMPTY(frontier) do\n",
        "                    node←POP(frontier)\n",
        "                    if problem.IS-GOAL(node.STATE) then return node \n",
        "                    for each child in EXPAND(problem, node) do\n",
        "                        s←child.STATE\n",
        "                        if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n",
        "                            reached[s] ← child\n",
        "                            add child to frontier return failure\n",
        "            \n",
        "            function EXPAND(problem,node) yields nodes \n",
        "                s←node.STATE\n",
        "                for each action in problem.ACTIONS(s) do\n",
        "                    s′ ←problem.RESULT(s,action)\n",
        "                    cost←node.PATH-COST + problem.ACTION-COST(s,action,s′)\n",
        "                    yield NODE(STATE=s′, PARENT=node, ACTION=action, PATH-COST=cost)\n",
        "             '''\n",
        "\n",
        "             Best first search is Dijkstra’s algorithm or UCS.\n",
        "             \"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\" \n",
        "             BEST-FIRST - Late Goal Test(after popping). \\\n",
        "             BREADTH-FIRST - Early Goal Test (check if node is solution when generated)\n",
        "             '''\n",
        "             function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure \n",
        "                for depth = 0 to ∞ do\n",
        "                    result←DEPTH-LIMITED-SEARCH(problem,depth) \n",
        "                    if result ̸= cutoff then return result\n",
        "             \n",
        "             function DEPTH-LIMITED-SEARCH(problem, l) returns a node or failure or cutoff \n",
        "                    frontier←a LIFO queue (stack) with NODE(problem.INITIAL) as an element \n",
        "                    result ← failure\n",
        "                    while not IS-EMPTY(frontier) do\n",
        "                      node←POP(frontier)\n",
        "                      if problem.IS-GOAL(node.STATE) then return node \n",
        "                      if DEPTH(node) > l then\n",
        "                          result ← cutoff\n",
        "                      else if not IS-CYCLE(node) do\n",
        "                          for each child in EXPAND(problem, node) do \n",
        "                              add child to frontier\n",
        "                    return result\n",
        "             '''\n",
        "             \"\"\"\n",
        "\n",
        "chapter3_4 = \"\"\"\n",
        "             '''\n",
        "             BiBF-SEARCH(problemF , fF , problemB, fB) \n",
        "                  while not TERMINATED(solution, frontierF , frontierB)\n",
        "                      if fF (TOP(frontierF )) < fB(TOP(frontierB))\n",
        "                          solution←PROCEED(F, problemF frontierF, reachedF, reachedB, solution) \n",
        "                      else solution←PROCEED(B, problemB, frontierB, reachedB, reachedF, solution)\n",
        "                      \n",
        "             PROCEED(dir, problem, frontier, reached, reached2, solution) \n",
        "                  node←POP(frontier)\n",
        "                  for child in EXPAND(problem, node)\n",
        "                      s←child.STATE\n",
        "                      if s not in reached or PATH-COST(child) < PATH-COST(reached[s])\n",
        "                          reached[s] ← child\n",
        "                          add child to frontier\n",
        "                          if s in reached2\n",
        "                              solution2 ← JOIN-NODES(dir, child, reached2[s]))\n",
        "                              if PATH-COST(solution2) < PATH-COST(solution)\n",
        "                                  solution ← solution2\n",
        "             '''\n",
        "             \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" \n",
        "                        '''\n",
        "             function BREADTH-FIRST-SEARCH(problem) returns a solution node or failure \n",
        "                node←NODE(problem.INITIAL)\n",
        "                if problem.IS-GOAL(node.STATE) then return node\n",
        "                frontier ← a FIFO queue, with node as an element reached←{problem.INITIAL}\n",
        "                while not IS-EMPTY(frontier) do \n",
        "                    node←POP(frontier)\n",
        "                    for each child in EXPAND(problem, node) do\n",
        "                        s←child.STATE\n",
        "                        if problem.IS-GOAL(s) then return child if s is not in reached then\n",
        "                            add s to reached\n",
        "                            add child to frontier return failure\n",
        "                \n",
        "             function UNIFORM-COST-SEARCH(problem) returns a solution node, or failure \n",
        "                return BEST-FIRST-SEARCH(problem, PATH-COST)\n",
        "             '''\n",
        "                        \"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        "\"Standardized problem\" : \"concise, exact description of a problem used as a benchmark - abstraction involved\",\n",
        "\"real-world problem\" : \"solution matters in a real-world scenario, formulation is idiosyncratic not standardized\",\n",
        "\"search algorithm\" : \"takes a search problem as input and returns a solution, or an indication of failure\",\n",
        "\"backtracking search\" : \"DFS variant generating one successor at a time having space complexity O(m)\"\n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_4.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_4))"
      ],
      "execution_count": 43,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 491\n",
            "The length in characters is 1094\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1826
        },
        "outputId": "6ebc01b4-e720-49f4-b376-32dab6edc673"
      },
      "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": 44,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Search problem is defined by 1) Set of states - state space, 2) Initial state 3) Set of one or more goal states              4) Finite set of actions, 5) Transition model 6) Action-cost function.              Search algorithm data structure - NODE has the following components: State, Parent, Action, Path-cost.\n             Frontier is stored in queue with the following possible operations: IsEmpty(), Pop(), Top(), Add().\n             \n\n## AIMA Chapter 3.2 Example Problems\n \n             '''\n             function BEST-FIRST-SEARCH(problem, f) returns a solution node or failure \n                node←NODE(STATE=problem.INITIAL)\n                frontier ← a priority queue ordered by f , with node as an element\n                reached←a lookup table, with one entry with key problem.INITIAL and value node \n                while not IS-EMPTY(frontier) do\n                    node←POP(frontier)\n                    if problem.IS-GOAL(node.STATE) then return node \n                    for each child in EXPAND(problem, node) do\n                        s←child.STATE\n                        if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n                            reached[s] ← child\n                            add child to frontier return failure\n            \n            function EXPAND(problem,node) yields nodes \n                s←node.STATE\n                for each action in problem.ACTIONS(s) do\n                    s′ ←problem.RESULT(s,action)\n                    cost←node.PATH-COST + problem.ACTION-COST(s,action,s′)\n                    yield NODE(STATE=s′, PARENT=node, ACTION=action, PATH-COST=cost)\n             '''\n\n             Best first search is Dijkstra’s algorithm or UCS.\n             \n\n## AIMA Chapter 3.3 Search Algorithms\n \n             BEST-FIRST - Late Goal Test(after popping).              BREADTH-FIRST - Early Goal Test (check if node is solution when generated)\n             '''\n             function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure \n                for depth = 0 to ∞ do\n                    result←DEPTH-LIMITED-SEARCH(problem,depth) \n                    if result ̸= cutoff then return result\n             \n             function DEPTH-LIMITED-SEARCH(problem, l) returns a node or failure or cutoff \n                    frontier←a LIFO queue (stack) with NODE(problem.INITIAL) as an element \n                    result ← failure\n                    while not IS-EMPTY(frontier) do\n                      node←POP(frontier)\n                      if problem.IS-GOAL(node.STATE) then return node \n                      if DEPTH(node) > l then\n                          result ← cutoff\n                      else if not IS-CYCLE(node) do\n                          for each child in EXPAND(problem, node) do \n                              add child to frontier\n                    return result\n             '''\n             \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n             '''\n             BiBF-SEARCH(problemF , fF , problemB, fB) \n                  while not TERMINATED(solution, frontierF , frontierB)\n                      if fF (TOP(frontierF )) < fB(TOP(frontierB))\n                          solution←PROCEED(F, problemF frontierF, reachedF, reachedB, solution) \n                      else solution←PROCEED(B, problemB, frontierB, reachedB, reachedF, solution)\n                      \n             PROCEED(dir, problem, frontier, reached, reached2, solution) \n                  node←POP(frontier)\n                  for child in EXPAND(problem, node)\n                      s←child.STATE\n                      if s not in reached or PATH-COST(child) < PATH-COST(reached[s])\n                          reached[s] ← child\n                          add child to frontier\n                          if s in reached2\n                              solution2 ← JOIN-NODES(dir, child, reached2[s]))\n                              if PATH-COST(solution2) < PATH-COST(solution)\n                                  solution ← solution2\n             '''\n             \n\n## Module 3 Lecture Notes\n \n                        '''\n             function BREADTH-FIRST-SEARCH(problem) returns a solution node or failure \n                node←NODE(problem.INITIAL)\n                if problem.IS-GOAL(node.STATE) then return node\n                frontier ← a FIFO queue, with node as an element reached←{problem.INITIAL}\n                while not IS-EMPTY(frontier) do \n                    node←POP(frontier)\n                    for each child in EXPAND(problem, node) do\n                        s←child.STATE\n                        if problem.IS-GOAL(s) then return child if s is not in reached then\n                            add s to reached\n                            add child to frontier return failure\n                \n             function UNIFORM-COST-SEARCH(problem) returns a solution node, or failure \n                return BEST-FIRST-SEARCH(problem, PATH-COST)\n             '''\n                        \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Standardized problem** - concise, exact description of a problem used as a benchmark - abstraction involved\n* **Real-world problem** - solution matters in a real-world scenario, formulation is idiosyncratic not standardized\n* **Search algorithm** - takes a search problem as input and returns a solution, or an indication of failure\n* **Backtracking search** - DFS variant generating one successor at a time having space complexity O(m)\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",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "36cf5150-2386-4e6f-e669-6495cfc19d75"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Admissable heuristic never over-estimates. A* is complete and optimal if heuristic is optimistic. \\\n",
        "             A heuristic h(n) is consistent if, for every node n and every successor n′ of n generated by an action a,: \\\n",
        "             h(n) ≤ c(n,a,n′)+h(n′). \\\n",
        "             A∗ expands all nodes that can be reached from the initial state on a path where every node on the path has f (n) < C∗. \\\n",
        "             These are surely expanded nodes. \\\n",
        "             A∗ might then expand some of the nodes right on the “goal contour” (where f (n) = C∗) before selecting a goal node. \\\n",
        "             A∗ expands no nodes with f(n)>C∗. \\\n",
        "             A∗ is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution. \\\n",
        "             RBFS (recursive best-first search) and SMA∗ (simplified memory-bounded A∗) are robust, optimal search algorithms that use limited amounts of memory; \\\n",
        "             given enough time, they can solve problems for which A∗ runs out of memory. \\\n",
        "             Weighted A∗ search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality. \\\n",
        "             Beam search puts a limit on the size of the frontier; that makes it incomplete and suboptimal, \\\n",
        "             but it often finds reasonably good solutions and runs faster than complete searches.\n",
        "             \"\"\"\n",
        "chapter3_6 = \"\"\" The performance of heuristic search algorithms depends on the quality of the heuristic function. \\\n",
        "             One can sometimes construct good heuristics by relaxing the problem definition, by storing precomputed solution costs \\\n",
        "             for subproblems in a pattern database, by defining landmarks, or by learning from experience with the problem class. \n",
        "             \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"Heuristic function\" : \"estimated cost of the cheapest path from the state at node n to a goal state\",   \n",
        "\"Consistent heuristic\" : \"When going from neighboring nodes a to b, the heuristic difference/step cost never overestimates the actual step cost\",\n",
        "\"Greedy best-first search\": \"form of best-first search that expands first the node with the lowest h(n) value - closest node to goal\",\n",
        "\"IDA∗\" : \"iterative deepening version of A∗, adressessing the space complexity issue.\" \n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter3_5.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter3_5))"
      ],
      "execution_count": 78,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 365\n",
            "The length in characters is 1324\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 545
        },
        "outputId": "b0f239f6-3c0e-41e8-a012-a5d6c2bcc79e"
      },
      "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": 79,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Admissable heuristic never over-estimates. A* is complete and optimal if heuristic is optimistic.              A heuristic h(n) 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′).              A∗ expands all nodes that can be reached from the initial state on a path where every node on the path has f (n) < C∗.              These are surely expanded nodes.              A∗ might then expand some of the nodes right on the “goal contour” (where f (n) = C∗) before selecting a goal node.              A∗ expands no nodes with f(n)>C∗.              A∗ is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.              RBFS (recursive best-first search) and SMA∗ (simplified memory-bounded A∗) are robust, optimal search algorithms that use limited amounts of memory;              given enough time, they can solve problems for which A∗ runs out of memory.              Weighted A∗ search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.              Beam search puts a limit on the size of the frontier; that makes it incomplete and suboptimal,              but it often finds reasonably good solutions and runs faster than complete searches.\n             \n\n## AIMA Chapter 3.6 Heuristic Functions\n The performance of heuristic search algorithms depends on the quality of the heuristic function.              One can sometimes construct good heuristics by relaxing the problem definition, by storing precomputed solution costs              for subproblems in a pattern database, by defining landmarks, or by learning from experience with the problem class. \n             \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Heuristic function** - estimated cost of the cheapest path from the state at node n to a goal state\n* **Consistent heuristic** - When going from neighboring nodes a to b, the heuristic difference/step cost never overestimates the actual step cost\n* **Greedy best-first search** - form of best-first search that expands first the node with the lowest h(n) value - closest node to goal\n* **Ida∗** - iterative deepening version of A∗, adressessing the space complexity issue.\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",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 0
        },
        "outputId": "c078135b-fe8f-4847-c9df-e7e012e00435"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" A game can be formally defined with the following elements:\n",
        "            • S0: The initial state, which specifies how the game is set up at the start.\n",
        "            • TO-MOVE(s): The player whose turn it is to move in state s.\n",
        "            • ACTIONS(s): The set of legal moves in state s.\n",
        "            • RESULT(s, a): The transition model, which defines the state resulting from taking action a in state s.\n",
        "            • IS-TERMINAL(s): A terminal test, which is true when the game is over and false otherwise.\n",
        "            • UTILITY(s, p): A utility function (also called an objective function or payoff function), which defines the final numeric value to player p when the game ends in terminal state s. \n",
        "            \n",
        "            \"\"\"\n",
        "\n",
        "chapter5_2 = \"\"\" In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information,\n",
        "             the minimax algorithm can select optimal moves by a depth-first enumeration of the game tree.\n",
        "             \"\"\"\n",
        "\n",
        "chapter5_3 = \"\"\" A heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state s to player p \"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\" Stochastic games - unpredictable due to the random element. Chance nodes exist between alternating MIN and MAX nodes. \\\n",
        "             The branches leading from each chance node denote the possible dice rolls; each branch is labeled with the roll and its probability. \\\n",
        "             The expected value of a position is calculated as the average over all possible outcomes of the chance nodes. \\\n",
        "             This leads to the expectiminimax value for games with chance nodes, a generalization of the minimax value for deterministic games. \\\n",
        "             The legal moves for MAX and MIN will depend on the outcome of the dice roll in the previous chance node). \\\n",
        "             '''\n",
        "             EXPECTIMINIMAX(s) =\n",
        "                UTILITY(s,MAX) if IS-TERMINAL(s)\n",
        "                maxa EXPECTIMINIMAX(RESULT(s, a)) if TO-MOVE(s)= MAX  \n",
        "                mina EXPECTIMINIMAX(RESULT(s, a)) if TO-MOVE(s)= MIN\n",
        "                ∑r P(r)EXPECTIMINIMAX(RESULT(s, r)) if TO-MOVE(s)= CHANCE\n",
        "            where r represents a possible dice roll (or other chance event) and RESULT(s,r) is the result of dice roll r on state s.\n",
        "            '''\n",
        "            \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Utility function, U (s), captures an agent's preferences by assigning a single number to express the desirability of a state. \\\n",
        "              The expected utility of an action given the evidence, EU(a), is the average utility value of the outcomes, weighted by the probability that the outcome occurs: \\\n",
        "              EU(a) = ∑P(RESULT(a)=s′)U(s′). \\\n",
        "              According to the principle of maximum expected utility (MEU), a rational agent should choose the action that maximizes it’s expected utility: \\\n",
        "                action = argmaxEU(a)\n",
        "              If it does so, it will attain the highest possible performance measure.\n",
        "              \"\"\"\n",
        "\n",
        "chapter16_2 = \"\"\" The utility theory aims to mazimize the expected utility. The MEU principle is derived from the following constraints: \\ \n",
        "              Orderability, transitivity, continuity, substitutability, monotonicity, decomposability. \\\n",
        "              In a deterministic environment, an agent needs only a preference ranking on states not the numbers itself. \\\n",
        "              This is called a value function or ordinal utility function.\n",
        "              \"\"\"\n",
        "\n",
        "chapter16_3 = \"\"\" Preference elicitation presents choices to humans and observes preferences to pin down underlying utility functions. \\\n",
        "              \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "                        '''\n",
        "            function MINIMAX-SEARCH(game, state) returns an action \n",
        "                player←game.TO-MOVE(state)\n",
        "                value, move←MAX-VALUE(game, state)\n",
        "                return move\n",
        "            function MAX-VALUE(game, state) returns a (utility, move) pair\n",
        "                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n",
        "                v←−∞\n",
        "                for each a in game.ACTIONS(state) do\n",
        "                    v2, a2←MIN-VALUE(game, game.RESULT(state, a)) \n",
        "                    if v2 > v then\n",
        "                        v, move←v2, a \n",
        "                return v, move\n",
        "            function MIN-VALUE(game, state) returns a (utility, move) pair\n",
        "                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n",
        "                v←+∞\n",
        "                for each a in game.ACTIONS(state) do\n",
        "                    v2, a2←MAX-VALUE(game, game.RESULT(state, a)) \n",
        "                    if v2 < v then\n",
        "                        v, move←v2, a \n",
        "                return v, move\n",
        "            '''\n",
        "            --------------------\n",
        "            '''\n",
        "             function ALPHA-BETA-SEARCH(game, state) returns an action \n",
        "                player←game.TO-MOVE(state)\n",
        "                value, move←MAX-VALUE(game, state,−∞,+∞)\n",
        "                return move\n",
        "             function MAX-VALUE(game, state, α, β) returns a (utility, move) pair\n",
        "                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n",
        "                v←−∞\n",
        "                for each a in game.ACTIONS(state) do\n",
        "                    v2, a2←MIN-VALUE(game, game.RESULT(state, a),α,β) \n",
        "                    if v2 > v then\n",
        "                        v, move←v2, a\n",
        "                        α←MAX(α, v)\n",
        "                    if v ≥ β then return v, move\n",
        "                return v, move\n",
        "             function MIN-VALUE(game, state, α, β) returns a (utility, move) pair\n",
        "                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n",
        "                v←+∞\n",
        "                for each a in game.ACTIONS(state) do\n",
        "                    v2, a2←MAX-VALUE(game, game.RESULT(state, a),α,β) \n",
        "                    if v2 < v then\n",
        "                        v, move←v2, a\n",
        "                        β←MIN(β, v)\n",
        "                    if v ≤ α then return v, move\n",
        "                return v, move\n",
        "              '''\n",
        "                        \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"Orderability\" : \"Exactly one of(A≻B),(B≻A), or(A∼B)holds [prefer one or both are equal]\", \n",
        "\"Transitivity\" : \"(A≻B)∧(B≻C) ⇒ (A≻C)\", \n",
        "\"Continuity\" : \"B between A and C in preference, then for probability p, agent will be indifferent between getting B & A+C\", \n",
        "\"Substitutability\" : \"If indifferent to A and B, then same for complex lotteries where B substituted for A\", \n",
        "\"Monotonicity\" : \"For same outcomes, if A is preferred to B then lottery with higher probability for A is preferred\", \n",
        "\"Decomposability\" : \"Compound lotteries may be reduced to simple ones using laws of probability\",  \n",
        "\"Expected Utility of a Lottery\" : \"The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\"  \n",
        "}\n",
        "\n",
        "print(\"The length in words is\", len(chapter5_2.split(' ')))\n",
        "print(\"The length in characters is\", len(chapter5_2))"
      ],
      "execution_count": 103,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 51\n",
            "The length in characters is 214\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1845
        },
        "outputId": "eca33976-398d-4c54-e59a-0918304ebcb8"
      },
      "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": 104,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n A game can be formally defined with the following elements:\n            • S0: The initial state, which specifies how the game is set up at the start.\n            • TO-MOVE(s): The player whose turn it is to move in state s.\n            • ACTIONS(s): The set of legal moves in state s.\n            • RESULT(s, a): The transition model, which defines the state resulting from taking action a in state s.\n            • IS-TERMINAL(s): A terminal test, which is true when the game is over and false otherwise.\n            • UTILITY(s, p): A utility function (also called an objective function or payoff function), which defines the final numeric value to player p when the game ends in terminal state s. \n            \n            \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information,\n             the minimax algorithm can select optimal moves by a depth-first enumeration of the game tree.\n             \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n A heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state s to player p \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games - unpredictable due to the random element. Chance nodes exist between alternating MIN and MAX nodes.              The branches leading from each chance node denote the possible dice rolls; each branch is labeled with the roll and its probability.              The expected value of a position is calculated as the average over all possible outcomes of the chance nodes.              This leads to the expectiminimax value for games with chance nodes, a generalization of the minimax value for deterministic games.              The legal moves for MAX and MIN will depend on the outcome of the dice roll in the previous chance node).              '''\n             EXPECTIMINIMAX(s) =\n                UTILITY(s,MAX) if IS-TERMINAL(s)\n                maxa EXPECTIMINIMAX(RESULT(s, a)) if TO-MOVE(s)= MAX  \n                mina EXPECTIMINIMAX(RESULT(s, a)) if TO-MOVE(s)= MIN\n                ∑r P(r)EXPECTIMINIMAX(RESULT(s, r)) if TO-MOVE(s)= CHANCE\n            where r represents a possible dice roll (or other chance event) and RESULT(s,r) is the result of dice roll r on state s.\n            '''\n            \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Utility function, U (s), captures an agent's preferences by assigning a single number to express the desirability of a state.               The expected utility of an action given the evidence, EU(a), is the average utility value of the outcomes, weighted by the probability that the outcome occurs:               EU(a) = ∑P(RESULT(a)=s′)U(s′).               According to the principle of maximum expected utility (MEU), a rational agent should choose the action that maximizes it’s expected utility:                 action = argmaxEU(a)\n              If it does so, it will attain the highest possible performance measure.\n              \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n The utility theory aims to mazimize the expected utility. The MEU principle is derived from the following constraints: \\ \n              Orderability, transitivity, continuity, substitutability, monotonicity, decomposability.               In a deterministic environment, an agent needs only a preference ranking on states not the numbers itself.               This is called a value function or ordinal utility function.\n              \n\n## AIMA Chapter 16.3 Utility Functions\n Preference elicitation presents choices to humans and observes preferences to pin down underlying utility functions.               \n\n## Module 5 Lecture Notes\n \n                        '''\n            function MINIMAX-SEARCH(game, state) returns an action \n                player←game.TO-MOVE(state)\n                value, move←MAX-VALUE(game, state)\n                return move\n            function MAX-VALUE(game, state) returns a (utility, move) pair\n                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n                v←−∞\n                for each a in game.ACTIONS(state) do\n                    v2, a2←MIN-VALUE(game, game.RESULT(state, a)) \n                    if v2 > v then\n                        v, move←v2, a \n                return v, move\n            function MIN-VALUE(game, state) returns a (utility, move) pair\n                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n                v←+∞\n                for each a in game.ACTIONS(state) do\n                    v2, a2←MAX-VALUE(game, game.RESULT(state, a)) \n                    if v2 < v then\n                        v, move←v2, a \n                return v, move\n            '''\n            --------------------\n            '''\n             function ALPHA-BETA-SEARCH(game, state) returns an action \n                player←game.TO-MOVE(state)\n                value, move←MAX-VALUE(game, state,−∞,+∞)\n                return move\n             function MAX-VALUE(game, state, α, β) returns a (utility, move) pair\n                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n                v←−∞\n                for each a in game.ACTIONS(state) do\n                    v2, a2←MIN-VALUE(game, game.RESULT(state, a),α,β) \n                    if v2 > v then\n                        v, move←v2, a\n                        α←MAX(α, v)\n                    if v ≥ β then return v, move\n                return v, move\n             function MIN-VALUE(game, state, α, β) returns a (utility, move) pair\n                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n                v←+∞\n                for each a in game.ACTIONS(state) do\n                    v2, a2←MAX-VALUE(game, game.RESULT(state, a),α,β) \n                    if v2 < v then\n                        v, move←v2, a\n                        β←MIN(β, v)\n                    if v ≤ α then return v, move\n                return v, move\n              '''\n                        \n\n## Module 5 Definitions\n* **Orderability** - Exactly one of(A≻B),(B≻A), or(A∼B)holds [prefer one or both are equal]\n* **Transitivity** - (A≻B)∧(B≻C) ⇒ (A≻C)\n* **Continuity** - B between A and C in preference, then for probability p, agent will be indifferent between getting B & A+C\n* **Substitutability** - If indifferent to A and B, then same for complex lotteries where B substituted for A\n* **Monotonicity** - For same outcomes, if A is preferred to B then lottery with higher probability for A is preferred\n* **Decomposability** - Compound lotteries may be reduced to simple ones using laws of probability\n* **Expected utility of a lottery** - The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\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 = \"\"\" A constraint satisfaction problem consists of three components, namely, X which is a set of variables, {X1,...,Xn}, \\\n",
        "                D which is a set of domains, {D1,...,Dn}, one for each variable and C which is a set of constraints that specify allowable combinations of values. \\\n",
        "               CSPs assign values to variables,{Xi=vi,Xj=vj,...} and solving such a problem is NP complete. An assignment that does not violate any constraints is \\\n",
        "               called a consistent or legal assignment. \\\n",
        "               A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment. \\\n",
        "              Problems can be easily formulated as CSPs due to natural representation and easy pruning. \\\n",
        "              Variations of CSP - finite/infinite, discrete/continuous, linear/non-linear, unary/binary/global.\n",
        "              \"\"\"\n",
        "\n",
        "chapter6_2 = \"\"\" A CSP algorithm can generate successors by choosing a new variable assignment, or it perform inference in the form of constraint propagation: \\\n",
        "             using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on. \\\n",
        "             This leaves fewer options for the next choice of a variable assignment. Constraint propagation may be intertwined with search, or it may be done as a preprocessing step, before search starts. \\\n",
        "             Sometimes this preprocessing can solve the whole problem, so no search is required at all. \\\n",
        "             Local consistency treats each variable as a node in a graph and each binary constraint as an edge, and removes inconsistent values throughout the graph. \\\n",
        "            Stronger forms of propagation can be defined with the notion of k-consistency. \\\n",
        "            A CSP is k- consistent if, for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. \\\n",
        "            A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)- consistent, ... all the way down to 1-consistent.  \\\n",
        "             \"\"\"\n",
        "\n",
        "chapter6_3 = \"\"\" \n",
        "             '''\n",
        "             function BACKTRACKING-SEARCH(csp) returns a solution or failure \n",
        "                  return BACKTRACK(csp,{})\n",
        "             function BACKTRACK(csp, assignment) returns a solution or failure\n",
        "                  if assignment is complete then return assignment\n",
        "                  var ← SELECT-UNASSIGNED-VARIABLE(csp, assignment)\n",
        "                  for each value in ORDER-DOMAIN-VALUES(csp, var, assignment) do\n",
        "                      if value is consistent with assignment then\n",
        "                          add {var = value} to assignment \n",
        "                          inferences←INFERENCE(csp,var,assignment) \n",
        "                          if inferences ̸= failure then\n",
        "                              add inferences to csp\n",
        "                              result ← BACKTRACK(csp, assignment) \n",
        "                              if result ̸= failure then return result \n",
        "                              remove inferences from csp\n",
        "                          remove {var = value} from assignment return failure\n",
        "              '''\n",
        "             \"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\" Local search algorithms use a complete-state formulation where each state assigns a value to every variable, \\\n",
        "                and the search changes the value of one variable at a time. It uses the min-conflicts heuristic.\n",
        "                function MIN-CONFLICTS(csp, max steps) returns a solution or failure \n",
        "                inputs: csp, a constraint satisfaction problem\n",
        "                        max steps, the number of steps allowed before giving up\n",
        "                    current ← an initial complete assignment for csp \n",
        "                    for i=1 to max steps do\n",
        "                      if current is a solution for csp then \n",
        "                        return current\n",
        "                      var←a randomly chosen conflicted variable from csp.VARIABLES \n",
        "                      value←the value v for var that minimizes CONFLICTS(csp,var,v,current) \n",
        "                      set var = value in current\n",
        "                    return failure\n",
        "              \"\"\"\n",
        "\n",
        "chapter6_5 = \"\"\"  Any tree-structured CSP can be solved in time linear in the number of variables. \n",
        "                  To solve a tree-structured CSP, first pick any variable to be the root of the tree, and \n",
        "                  choose an ordering of the variables such that each variable appears after its parent in the tree. Such an ordering is called a topological sort.\n",
        "                  Any tree with n nodes has n − 1 edges, so we can make this graph directed arc-consistent in O(n) steps, \n",
        "                  each of which must compare up to d possible domain values for two variables, for a total time of O(nd^2).\n",
        "                  Cutset conditioning can reduce a general CSP to a tree-structured one and is quite efficient (requiring only linear memory) if a small cutset can be found. \n",
        "                  Tree decomposition techniques transform the CSP into a tree of subproblems and are efficient if the tree width of the constraint graph is small; \n",
        "                  however they need memory exponential in the tree width of the constraint graph. \n",
        "             \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Some heuristics for CSPs are:\n",
        "                        1) Most constrained variable/ Minimum remaining values or fail-first heuristic [avoid pointless search by early failure detection]\n",
        "                        2) Most constraining variable or degree heuristic [reduces brancing factor by selecting variable with largest number of constraints on neighbours]\n",
        "                        3) Least constraining value - order while examining values [prefers values which rule out fewest choices for neighbours] \n",
        "                        4) Forward checking - when a variable X is assigned, the forward-checking process establishes arc consistency for it: \n",
        "                              for each unassigned variable Y that is connected to X by a constraint, delete from Y ’s domain any value that is inconsistent with the value chosen for X.\n",
        "                        \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"node-consistent\" : \"all the values in the variable’s domain satisfy the variable’s unary constraints\",  \n",
        "\"arc-consistent\" : \"every value in its domain satisfies the variable’s binary constraints\" ,\n",
        "\"Path consistency\" : \"tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\" \n",
        "}\n"
      ],
      "execution_count": 110,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1236
        },
        "outputId": "94d9971c-e995-4991-8dbf-f55722239350"
      },
      "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": 111,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n A constraint satisfaction problem consists of three components, namely, X which is a set of variables, {X1,...,Xn},                 D which is a set of domains, {D1,...,Dn}, one for each variable and C which is a set of constraints that specify allowable combinations of values.                CSPs assign values to variables,{Xi=vi,Xj=vj,...} and solving such a problem is NP complete. An assignment that does not violate any constraints is                called a consistent or legal assignment.                A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment.               Problems can be easily formulated as CSPs due to natural representation and easy pruning.               Variations of CSP - finite/infinite, discrete/continuous, linear/non-linear, unary/binary/global.\n              \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n A CSP algorithm can generate successors by choosing a new variable assignment, or it perform inference in the form of constraint propagation:              using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on.              This leaves fewer options for the next choice of a variable assignment. Constraint propagation may be intertwined with search, or it may be done as a preprocessing step, before search starts.              Sometimes this preprocessing can solve the whole problem, so no search is required at all.              Local consistency treats each variable as a node in a graph and each binary constraint as an edge, and removes inconsistent values throughout the graph.             Stronger forms of propagation can be defined with the notion of k-consistency.             A CSP is k- consistent if, for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.             A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)- consistent, ... all the way down to 1-consistent.               \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n             '''\n             function BACKTRACKING-SEARCH(csp) returns a solution or failure \n                  return BACKTRACK(csp,{})\n             function BACKTRACK(csp, assignment) returns a solution or failure\n                  if assignment is complete then return assignment\n                  var ← SELECT-UNASSIGNED-VARIABLE(csp, assignment)\n                  for each value in ORDER-DOMAIN-VALUES(csp, var, assignment) do\n                      if value is consistent with assignment then\n                          add {var = value} to assignment \n                          inferences←INFERENCE(csp,var,assignment) \n                          if inferences ̸= failure then\n                              add inferences to csp\n                              result ← BACKTRACK(csp, assignment) \n                              if result ̸= failure then return result \n                              remove inferences from csp\n                          remove {var = value} from assignment return failure\n              '''\n             \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search algorithms use a complete-state formulation where each state assigns a value to every variable,                 and the search changes the value of one variable at a time. It uses the min-conflicts heuristic.\n                function MIN-CONFLICTS(csp, max steps) returns a solution or failure \n                inputs: csp, a constraint satisfaction problem\n                        max steps, the number of steps allowed before giving up\n                    current ← an initial complete assignment for csp \n                    for i=1 to max steps do\n                      if current is a solution for csp then \n                        return current\n                      var←a randomly chosen conflicted variable from csp.VARIABLES \n                      value←the value v for var that minimizes CONFLICTS(csp,var,v,current) \n                      set var = value in current\n                    return failure\n              \n\n## AIMA Chapter 6.5 The Structure of Problems\n  Any tree-structured CSP can be solved in time linear in the number of variables. \n                  To solve a tree-structured CSP, first pick any variable to be the root of the tree, and \n                  choose an ordering of the variables such that each variable appears after its parent in the tree. Such an ordering is called a topological sort.\n                  Any tree with n nodes has n − 1 edges, so we can make this graph directed arc-consistent in O(n) steps, \n                  each of which must compare up to d possible domain values for two variables, for a total time of O(nd^2).\n                  Cutset conditioning can reduce a general CSP to a tree-structured one and is quite efficient (requiring only linear memory) if a small cutset can be found. \n                  Tree decomposition techniques transform the CSP into a tree of subproblems and are efficient if the tree width of the constraint graph is small; \n                  however they need memory exponential in the tree width of the constraint graph. \n             \n\n## Module 6 Lecture Notes\n Some heuristics for CSPs are:\n                        1) Most constrained variable/ Minimum remaining values or fail-first heuristic [avoid pointless search by early failure detection]\n                        2) Most constraining variable or degree heuristic [reduces brancing factor by selecting variable with largest number of constraints on neighbours]\n                        3) Least constraining value - order while examining values [prefers values which rule out fewest choices for neighbours] \n                        4) Forward checking - when a variable X is assigned, the forward-checking process establishes arc consistency for it: \n                              for each unassigned variable Y that is connected to X by a constraint, delete from Y ’s domain any value that is inconsistent with the value chosen for X.\n                        \n\n## Module 6 Definitions\n* **Node-consistent** - all the values in the variable’s domain satisfy the variable’s unary constraints\n* **Arc-consistent** - every value in its domain satisfies the variable’s binary constraints\n* **Path consistency** - tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\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 = \"\"\" A KB is a set of sentences represented in a knowledge representation language each expressing an assertion of the world. \\\n",
        "             Inference must obey the requirement that when one ASKs a question of the knowledge base, the answer should follow from what has \\\n",
        "             been told (or TELLed) to the knowledge base previously. \\\n",
        "             These sentences are expressed according to the syntax of the representation language, which specifies all the sentences that are well formed. \\\n",
        "             Logic defines the semantics, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world. \\\n",
        "             Knowledge level specifies what the agent knows and what its goals are, to determine its behaviour. \n",
        "             A KB can be built on two appraoches, DECLRATIVE tells what it to be known while PROCEDURAL encodes desired behaviour in program code.  \n",
        "             \"\"\"\n",
        "\n",
        "chapter7_2 = \"\"\" The Wumpus World \"\"\"\n",
        "\n",
        "chapter7_3 = \"\"\" Models are mathematical abstactions with a fixed truth value for relevant sentences. \\\n",
        "             If a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α. \n",
        "             We use the notation M(α) to mean the set of all models of α.\n",
        "             For logical entailment, we have α |= β if and only if M(α) ⊆ M(β). \n",
        "             Entailment is used to perform logical inferencing using a model checking algorithm.\n",
        "             An inference algorithm that derives only entailed sentences is called sound or truth-preserving.\n",
        "             An inference algorithm is complete if it can derive any sentence that is entailed. \n",
        "             \"\"\"\n",
        "\n",
        "chapter7_4 = \"\"\" Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. \n",
        "            There are five connectives in common use: ¬  ∧ ∨ ⇒ ⇔ \n",
        "            \"\"\"\n",
        "\n",
        "chapter7_5 = \"\"\" Logical equivalence means α≡β if and only if α|=β and β|=α. \n",
        "             Proof problem is defined using - INITIAL STATE: the initial knowledge base, \n",
        "             ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule, \n",
        "             RESULT: the result of an action is to add the sentence in the bottom half of the inference rule, and\n",
        "             GOAL: the goal is a state that contains the sentence we are trying to prove.\n",
        "             An important property of logical systems is monotonicity, which says that the set of entailed sentences can only increase as information \\\n",
        "             is added to the knowledge base. For any sentences α and β, if KB |= α then KB∧β |= α.\n",
        "             \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Resolution  - If li and 𝓂 are complementary literals, which means that one is the negation of another, then we can eliminate \\\n",
        "                      them via unit resolution. [Full resolution rule for complementary literals li and 𝓂j] \\\n",
        "                      Resolution rule only applies to clauses - disjunction of literals but every sentence can be a conjunction of clauses. \\\n",
        "                      \n",
        "                      Conjunctive Normal Form (CNF)\n",
        "                      1) Every sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals.\n",
        "                      2) Eliminate⇔byreplacing𝛂⇔βwith(𝛂⟹β)⋀(β⟹𝛂)\n",
        "                      3) Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β\n",
        "                      4) Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n",
        "                      5) Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\n",
        "                      \n",
        "                      '''\n",
        "                      Resolution Algorithm\n",
        "                      Inference procedures based on resolution work using the principle of proof by contradiction.\n",
        "                      To show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable. Here’s how:\n",
        "                      First, convert (KB ⋀ ¬𝛂) into CNF\n",
        "                      Then apply the resolution rule to the resulting clauses.\n",
        "                      Resolve every pair that contains complementary literals to produce a new clause If that new clause isn’t already present, then add it to the set.\n",
        "                      Continue the process until one of two things happens:\n",
        "                      1)There are no new clauses that can be added. In this case, the KB does not entail 𝛂 \n",
        "                      2)Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂\n",
        "                      '''\n",
        "\n",
        "                      Forward Chaining is a kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and\n",
        "                      then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\n",
        "                      Backward chaining a form of goal-directed reasoning - working backwards from a query. If the query is known to be true, then no work is needed.\n",
        "                      Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining),\n",
        "                      then the query is true.\n",
        "                      \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"axiom\" : \"sentence that is taken as being given without being derived from other sentences\",    \n",
        "\"inference\" : \"deriving new sentences from old\",\n",
        "\"logical entailment\" : \"α |= β if and only if, in every model in which α is true, β is also true.\",\n",
        "\"theorem proving\" : \"applying rules of inference directly to sentences in KB to construct a proof of the desired sentence without consulting models\",\n",
        "\"logical equivalence\" : \"two sentences α and β are logically equivalent if they are true in the same set of models.\",\n",
        "\"Definite clause\" : \"disjunction of literals where exactly one is positive\",\n",
        "\"Horn clause\" : \"disjunction of literals where at most one is positive\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 141,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1247
        },
        "outputId": "c2f31fbd-7fb4-47ed-d1bd-f10681211b54"
      },
      "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": 142,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n A KB is a set of sentences represented in a knowledge representation language each expressing an assertion of the world.              Inference must obey the requirement that when one ASKs a question of the knowledge base, the answer should follow from what has              been told (or TELLed) to the knowledge base previously.              These sentences are expressed according to the syntax of the representation language, which specifies all the sentences that are well formed.              Logic defines the semantics, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world.              Knowledge level specifies what the agent knows and what its goals are, to determine its behaviour. \n             A KB can be built on two appraoches, DECLRATIVE tells what it to be known while PROCEDURAL encodes desired behaviour in program code.  \n             \n\n## AIMA Chapter 7.2 The Wumpus World\n The Wumpus World \n\n## AIMA Chapter 7.3 Logic\n Models are mathematical abstactions with a fixed truth value for relevant sentences.              If a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α. \n             We use the notation M(α) to mean the set of all models of α.\n             For logical entailment, we have α |= β if and only if M(α) ⊆ M(β). \n             Entailment is used to perform logical inferencing using a model checking algorithm.\n             An inference algorithm that derives only entailed sentences is called sound or truth-preserving.\n             An inference algorithm is complete if it can derive any sentence that is entailed. \n             \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. \n            There are five connectives in common use: ¬  ∧ ∨ ⇒ ⇔ \n            \n\n## AIMA 7.5 Propositional Theorem Proving\n Logical equivalence means α≡β if and only if α|=β and β|=α. \n             Proof problem is defined using - INITIAL STATE: the initial knowledge base, \n             ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule, \n             RESULT: the result of an action is to add the sentence in the bottom half of the inference rule, and\n             GOAL: the goal is a state that contains the sentence we are trying to prove.\n             An important property of logical systems is monotonicity, which says that the set of entailed sentences can only increase as information              is added to the knowledge base. For any sentences α and β, if KB |= α then KB∧β |= α.\n             \n\n## Module 7 Lecture Notes\n Resolution  - If li and 𝓂 are complementary literals, which means that one is the negation of another, then we can eliminate                       them via unit resolution. [Full resolution rule for complementary literals li and 𝓂j]                       Resolution rule only applies to clauses - disjunction of literals but every sentence can be a conjunction of clauses.                       \n                      Conjunctive Normal Form (CNF)\n                      1) Every sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals.\n                      2) Eliminate⇔byreplacing𝛂⇔βwith(𝛂⟹β)⋀(β⟹𝛂)\n                      3) Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β\n                      4) Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n                      5) Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\n                      \n                      '''\n                      Resolution Algorithm\n                      Inference procedures based on resolution work using the principle of proof by contradiction.\n                      To show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable. Here’s how:\n                      First, convert (KB ⋀ ¬𝛂) into CNF\n                      Then apply the resolution rule to the resulting clauses.\n                      Resolve every pair that contains complementary literals to produce a new clause If that new clause isn’t already present, then add it to the set.\n                      Continue the process until one of two things happens:\n                      1)There are no new clauses that can be added. In this case, the KB does not entail 𝛂 \n                      2)Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂\n                      '''\n\n                      Forward Chaining is a kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and\n                      then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\n                      Backward chaining a form of goal-directed reasoning - working backwards from a query. If the query is known to be true, then no work is needed.\n                      Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining),\n                      then the query is true.\n                      \n\n## Module 7 Definitions\n* **Axiom** - sentence that is taken as being given without being derived from other sentences\n* **Inference** - deriving new sentences from old\n* **Logical entailment** - α |= β if and only if, in every model in which α is true, β is also true.\n* **Theorem proving** - applying rules of inference directly to sentences in KB to construct a proof of the desired sentence without consulting models\n* **Logical equivalence** - two sentences α and β are logically equivalent if they are true in the same set of models.\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals where at most one is positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "6ead4600-29b4-4905-e59f-56436c5942c5"
      },
      "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": 155,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n AI has two dimemsions namely human/rational & thought/behviour(act) - so four combinations. Turing Test Approach (Acting Humanly) checks if a computer can pass as human              while answering questions. It requires NLP, Knowledge Representation, Automated Reasoning, ML capabilities. Additionally, Total Turing Test checks              CV and Robotics abilities. Cognitive Modeling Approach (Thinking Humanly) learns human thought through 1)introspection, 2) psychological experiments, 3)brain imaging.              Laws of Thought Approach (Thinking Rationally) was based on the syllogisms by Aristotle that provided patterns for argument structures to yield corresct              solutions given correct premises. It was meant to govern the operations of the mind and initiated the field of logic.              Obstacles to this approach are the difficulty to represent informal knowledge in formal terms and the difference in problem solving in principle vs practice.              The Rational Agent Approach (Acting Rationallly)              expects agents to operate autonomously based on perceived input, adapt to change and pursue goals. Similar to laws of thought, making correct inferences              but more general and can be represented mathematically. Here, inference is useful not necessary. Focus is on the study and construction of agents that do the right thing, which becomes the objective              provided to the agent. This is called the Standard Model.              The problem of achieving agreement between the true preferences and the objective put into the machine is called the value alignment problem.              The values or objectives put into the machine must be aligned with those of the human. \n             \n\n## AIMA Chapter 27.1 The Limits of AI\n Limits are - Argument from Informality, Argument from Disability, Mathematical Objection, Measuring AI (Turing test).               Firstly, Turing argues about informality where he says that human behaviour is far too complex to be represented by a formal set of rules that can be coded onto               a computer program. \\ \n              The embodied cognition approach claims that it makes no sense to consider the brain separately:               cognition takes place within a body, which is embedded in an environment.               The system is to be studied as a whole; the brain’s functioning exploits regularities in its environment, including the rest of its body.               Under the embodied cognition approach, robotics, vision, and other sensors become central, not peripheral.               Secondly, Turing states that machines cannot do certain things like express emotions, be the subject of its own thought or do something really new.               Finally, Turing states that many mathematical questions are unanswerable by some formal systems.               Go ̈del sentence G(F) is a sentence of F, but cannot be proved within F. If F is consistent, then G(F) is true.               Machines are mentally inferior to humans since they are formal systems limited by the incompleteness theorem.               They cannot establish the truth of their own Go ̈del sentence. Humans don't have this limitation.               Issues with the theorem - an agent should not be ashamed that it cannot establish the truth of some sentence while other agents can;               results apply to mathematics, not to computers (cannot prove something that is impossible to prove);               it applies only to formal systems that are powerful enough to do arithmetic (Turing machines which are infinite).\n              \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Chinese Room Argument talks about computers having understanding when they perform a task.               He also talks about biological naturalism, according to which mental states are high-level emergent features               caused by low-level physical processes in the neurons, and it is the (unspecified) properties of the neurons that matter.               Another issue is conciousness which refers to the awareness of the outside world.               Individual aspects of consciousness—awareness, self-awareness, attention— can be programmed and can be part of an intelligent machine.               Behaving intelligently requires some degree of awareness, varying from task to task.               Tasks involving human interaction will require a model of human subjective experience.\n              \n\n## AIMA 2.1 Agents and Environments\n The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system. \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n For performance measures, we consider the notion of consequentialism - evaluating agent's behaviour by consequences.              Performance measure evaluates the desirability of an agent given a sequence of environmental states.              Rule of thumb is to design performance measures according to what is to be achieved in the environment, rather than how the agent should behave.              Rationality depends on: performance measure that defines the criterion of success, agent’s prior knowledge of the environment, actions that it can perform              and the percept sequence to date.              In an unknown environment, agents may learn through exploration. Information gathering - performing actions to modify future percepts.              An agent lacks autonomy if it relies on prior knowledge of its designer rather than its own percepts and learning processes to perform actions.              A rational agent should be autonomous and learn what it can to compensate for partial or incorrect prior knowledge.\n             \n\n## AIMA 2.3 The Nature of Environments\n Task environments are problem to which rational agents are the solutions. They are usually specified using the PEAS description              (Performance, Environment, Actuators, Sensors).              Properties of task environment - fully/partially observable, unobservable; single/multi agent; deterministic/non-deterministic;              stochatic (similar to non-deterministic but with probabilities); episodic (experience divided into atomic episodes each independant of the other)              /sequential(current decision could affect all future decisions - may have to think ahead); static/dynamic; discrete/ continuous              (state of the environment, the way time is handled, and the percepts and actions of the agent); known/unknown (not about environment but agent's knowledge);              Known environment, the outcomes (or outcome probabilities if the environment is nondeterministic) for all actions are given.              If unknown, the agent will have to learn how it works in order to make good decisions.              The distinction between known and unknown environments differs from fully and partially observable environments.              Environment may be partially observable & known — for example, in solitaire, rules are known but still unable to see the cards that have not yet been turned over.              Unknown environment can be fully observable — in a new video game, the screen may show the entire game state but I what the buttons do is not knownn until tried.              The hardest case is partially observable, multiagent, nondeterministic, sequential, dy- namic, continuous, and unknown. \n             \n\n## AIMA 2.4 The Structure of Agents\n Agent program implements agent function - run on agent architecture (computer program with sensors and actuators)              '''\n\n             function TABLE_DRIVEN_AGENT(percept) returns an action\n                persistent: percepts, a sequence, initally empty\n                            table, actions indexed by percept sequences, initially fully indexed\n\n                append percept to end of percepts\n                return LOOKUP(percepts, table)\n\n            function SIMPLE-REFLEX-AGENT(percept) returns an action \n                persistent: rules, a set of condition–action rules\n                \n                state←INTERPRET-INPUT(percept) \n                rule←RULE-MATCH(state,rules) \n                return rule.ACTION\n\n            function MODEL-BASED-REFLEX-AGENT(percept) returns an action \n                persistent: state, the agent’s current conception of the world state\n                            transition model, sensor model, rules\n                            action, the most recent action, initially none\n\n                state←UPDATE-STATE(state,action,percept,transition model,sensor model) \n                rule←RULE-MATCH(state,rules)\n                return rule.ACTION\n                \n             '''\n             Goal-based agents achieve their goals, utility-based agents maximize their own expected happiness.\n             Learning agent - learning element, performance element, critic, problem generator\n             \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Agent** - anything that can perceive its environment through sensors and act upon it through actuators\n* **Percept** - an agent's perceptual input at a given instance\n* **Agent function** - maps a percept sequence to an action\n* **Rational agent** - for each percept sequence, selects an action that is expected to max performance measure\n* **Omniscient agent** - knows the actual outcome of its actions and can act accordingly\n* **Deterministtic** - next state of the environment is completely determined by the current state and the action executed by the agent\n* **Simple reflex agent** - selects actions on the basis of the current percept, ignoring the rest of the percept history\n* **Model-based agent** - transition and sensor model keep track of the state of the world—given the limitations of the agent’s sensors\n* **Transition model** - a description of how the next state depends on the current state and action\n* **Sensor model** - a description of how the current world state is reflected in the agent’s percepts\n* **Utility function** - internalization of the agent's performance measure\n* **Qualification problem** - the issue with capturing every contingency of appropriate behaviour in a set of necessary and sufficient logical rules\n* **Qualia** - intrinsic nature of experiences\n* **Weak ai** - refers to the idea that machines could act as if they were intelligent\n* **Strong ai** - assertion that machines that do so are actually consciously thinking (not just simulating thinking)\n* **Human-level ai or general ai** - Programs that can solve a wide range of tasks, including novel ones, as well as a human\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n References and mutabililty - strings are immutable while lists are mutable \n\n                            >>>x='foo ' \n\n                            >>> y = x \n\n                            >>> x = x.strip() # new obj \n\n                            >>> x \n\n                            'foo' \n\n                            >>> y \n\n                            'foo ' \n\n                            >>> x = [1, 2, 3, 4] \n\n                            >>> y = x \n\n                            >>> x.append(5) #same obj \n\n                            >>> y \n\n                            [1, 2, 3, 4, 5] \n\n                            >>> x \n\n                            [1, 2, 3, 4, 5] \n\n\n                            Python doesn’t allow function overloading like Java does. Unlike Java, a Python function is specified by its name alone.                             Two different functions can’t have the same name, even if they have different numbers, order, or names of arguments.                             Operator overloading (overloading +, ==, -, etc.) is possible using special methods on while implementing a class.                             *args - Suppose you want to accept a variable number of non-keyword arguments to your function.                             **kwargs - Suppose you want to accept a variable number of keyword arguments to your function. \n                            '''\n                            class DiGraph:\n                              def search(self, u, visited):\n                                  # If we haven't visited this node...\n                                  if u not in visited:\n                                      yield u # yield it\n                                      visited.add(u) # and remember we've visited it now.\n                                      # Then, if there are any adjacent nodes...\n                                      if u in self.adj:\n                                          for v in self.adj[u]: # for each adjacent node...\n                                              # search for all nodes reachable from *it*...\n                                              for w in self.search(v, visited):\n                                                  # and yield each one.\n                                                  yield w\n                            '''\n                            \n\n## Module 2 Definitions\n* **Mutability** - ability of a literal to have its value modified\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Search problem is defined by 1) Set of states - state space, 2) Initial state 3) Set of one or more goal states              4) Finite set of actions, 5) Transition model 6) Action-cost function.              Search algorithm data structure - NODE has the following components: State, Parent, Action, Path-cost.\n             Frontier is stored in queue with the following possible operations: IsEmpty(), Pop(), Top(), Add().\n             \n\n## AIMA Chapter 3.2 Example Problems\n \n             '''\n             function BEST-FIRST-SEARCH(problem, f) returns a solution node or failure \n                node←NODE(STATE=problem.INITIAL)\n                frontier ← a priority queue ordered by f , with node as an element\n                reached←a lookup table, with one entry with key problem.INITIAL and value node \n                while not IS-EMPTY(frontier) do\n                    node←POP(frontier)\n                    if problem.IS-GOAL(node.STATE) then return node \n                    for each child in EXPAND(problem, node) do\n                        s←child.STATE\n                        if s is not in reached or child.PATH-COST < reached[s].PATH-COST then\n                            reached[s] ← child\n                            add child to frontier return failure\n            \n            function EXPAND(problem,node) yields nodes \n                s←node.STATE\n                for each action in problem.ACTIONS(s) do\n                    s′ ←problem.RESULT(s,action)\n                    cost←node.PATH-COST + problem.ACTION-COST(s,action,s′)\n                    yield NODE(STATE=s′, PARENT=node, ACTION=action, PATH-COST=cost)\n             '''\n\n             Best first search is Dijkstra’s algorithm or UCS.\n             \n\n## AIMA Chapter 3.3 Search Algorithms\n \n             BEST-FIRST - Late Goal Test(after popping).              BREADTH-FIRST - Early Goal Test (check if node is solution when generated)\n             '''\n             function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure \n                for depth = 0 to ∞ do\n                    result←DEPTH-LIMITED-SEARCH(problem,depth) \n                    if result ̸= cutoff then return result\n             \n             function DEPTH-LIMITED-SEARCH(problem, l) returns a node or failure or cutoff \n                    frontier←a LIFO queue (stack) with NODE(problem.INITIAL) as an element \n                    result ← failure\n                    while not IS-EMPTY(frontier) do\n                      node←POP(frontier)\n                      if problem.IS-GOAL(node.STATE) then return node \n                      if DEPTH(node) > l then\n                          result ← cutoff\n                      else if not IS-CYCLE(node) do\n                          for each child in EXPAND(problem, node) do \n                              add child to frontier\n                    return result\n             '''\n             \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n             '''\n             BiBF-SEARCH(problemF , fF , problemB, fB) \n                  while not TERMINATED(solution, frontierF , frontierB)\n                      if fF (TOP(frontierF )) < fB(TOP(frontierB))\n                          solution←PROCEED(F, problemF frontierF, reachedF, reachedB, solution) \n                      else solution←PROCEED(B, problemB, frontierB, reachedB, reachedF, solution)\n                      \n             PROCEED(dir, problem, frontier, reached, reached2, solution) \n                  node←POP(frontier)\n                  for child in EXPAND(problem, node)\n                      s←child.STATE\n                      if s not in reached or PATH-COST(child) < PATH-COST(reached[s])\n                          reached[s] ← child\n                          add child to frontier\n                          if s in reached2\n                              solution2 ← JOIN-NODES(dir, child, reached2[s]))\n                              if PATH-COST(solution2) < PATH-COST(solution)\n                                  solution ← solution2\n             '''\n             \n\n## Module 3 Lecture Notes\n \n                        '''\n             function BREADTH-FIRST-SEARCH(problem) returns a solution node or failure \n                node←NODE(problem.INITIAL)\n                if problem.IS-GOAL(node.STATE) then return node\n                frontier ← a FIFO queue, with node as an element reached←{problem.INITIAL}\n                while not IS-EMPTY(frontier) do \n                    node←POP(frontier)\n                    for each child in EXPAND(problem, node) do\n                        s←child.STATE\n                        if problem.IS-GOAL(s) then return child if s is not in reached then\n                            add s to reached\n                            add child to frontier return failure\n                \n             function UNIFORM-COST-SEARCH(problem) returns a solution node, or failure \n                return BEST-FIRST-SEARCH(problem, PATH-COST)\n             '''\n                        \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Standardized problem** - concise, exact description of a problem used as a benchmark - abstraction involved\n* **Real-world problem** - solution matters in a real-world scenario, formulation is idiosyncratic not standardized\n* **Search algorithm** - takes a search problem as input and returns a solution, or an indication of failure\n* **Backtracking search** - DFS variant generating one successor at a time having space complexity O(m)\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Admissable heuristic never over-estimates. A* is complete and optimal if heuristic is optimistic.              A heuristic h(n) 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′).              A∗ expands all nodes that can be reached from the initial state on a path where every node on the path has f (n) < C∗.              These are surely expanded nodes.              A∗ might then expand some of the nodes right on the “goal contour” (where f (n) = C∗) before selecting a goal node.              A∗ expands no nodes with f(n)>C∗.              A∗ is efficient because it prunes away search tree nodes that are not necessary for finding an optimal solution.              RBFS (recursive best-first search) and SMA∗ (simplified memory-bounded A∗) are robust, optimal search algorithms that use limited amounts of memory;              given enough time, they can solve problems for which A∗ runs out of memory.              Weighted A∗ search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality.              Beam search puts a limit on the size of the frontier; that makes it incomplete and suboptimal,              but it often finds reasonably good solutions and runs faster than complete searches.\n             \n\n## AIMA Chapter 3.6 Heuristic Functions\n The performance of heuristic search algorithms depends on the quality of the heuristic function.              One can sometimes construct good heuristics by relaxing the problem definition, by storing precomputed solution costs              for subproblems in a pattern database, by defining landmarks, or by learning from experience with the problem class. \n             \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Heuristic function** - estimated cost of the cheapest path from the state at node n to a goal state\n* **Consistent heuristic** - When going from neighboring nodes a to b, the heuristic difference/step cost never overestimates the actual step cost\n* **Greedy best-first search** - form of best-first search that expands first the node with the lowest h(n) value - closest node to goal\n* **Ida∗** - iterative deepening version of A∗, adressessing the space complexity issue.\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n A game can be formally defined with the following elements:\n            • S0: The initial state, which specifies how the game is set up at the start.\n            • TO-MOVE(s): The player whose turn it is to move in state s.\n            • ACTIONS(s): The set of legal moves in state s.\n            • RESULT(s, a): The transition model, which defines the state resulting from taking action a in state s.\n            • IS-TERMINAL(s): A terminal test, which is true when the game is over and false otherwise.\n            • UTILITY(s, p): A utility function (also called an objective function or payoff function), which defines the final numeric value to player p when the game ends in terminal state s. \n            \n            \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information,\n             the minimax algorithm can select optimal moves by a depth-first enumeration of the game tree.\n             \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n A heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state s to player p \n\n## AIMA Chapter 5.5 Stochastic Games\n Stochastic games - unpredictable due to the random element. Chance nodes exist between alternating MIN and MAX nodes.              The branches leading from each chance node denote the possible dice rolls; each branch is labeled with the roll and its probability.              The expected value of a position is calculated as the average over all possible outcomes of the chance nodes.              This leads to the expectiminimax value for games with chance nodes, a generalization of the minimax value for deterministic games.              The legal moves for MAX and MIN will depend on the outcome of the dice roll in the previous chance node).              '''\n             EXPECTIMINIMAX(s) =\n                UTILITY(s,MAX) if IS-TERMINAL(s)\n                maxa EXPECTIMINIMAX(RESULT(s, a)) if TO-MOVE(s)= MAX  \n                mina EXPECTIMINIMAX(RESULT(s, a)) if TO-MOVE(s)= MIN\n                ∑r P(r)EXPECTIMINIMAX(RESULT(s, r)) if TO-MOVE(s)= CHANCE\n            where r represents a possible dice roll (or other chance event) and RESULT(s,r) is the result of dice roll r on state s.\n            '''\n            \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Utility function, U (s), captures an agent's preferences by assigning a single number to express the desirability of a state.               The expected utility of an action given the evidence, EU(a), is the average utility value of the outcomes, weighted by the probability that the outcome occurs:               EU(a) = ∑P(RESULT(a)=s′)U(s′).               According to the principle of maximum expected utility (MEU), a rational agent should choose the action that maximizes it’s expected utility:                 action = argmaxEU(a)\n              If it does so, it will attain the highest possible performance measure.\n              \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n The utility theory aims to mazimize the expected utility. The MEU principle is derived from the following constraints: \\ \n              Orderability, transitivity, continuity, substitutability, monotonicity, decomposability.               In a deterministic environment, an agent needs only a preference ranking on states not the numbers itself.               This is called a value function or ordinal utility function.\n              \n\n## AIMA Chapter 16.3 Utility Functions\n Preference elicitation presents choices to humans and observes preferences to pin down underlying utility functions.               \n\n## Module 5 Lecture Notes\n \n                        '''\n            function MINIMAX-SEARCH(game, state) returns an action \n                player←game.TO-MOVE(state)\n                value, move←MAX-VALUE(game, state)\n                return move\n            function MAX-VALUE(game, state) returns a (utility, move) pair\n                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n                v←−∞\n                for each a in game.ACTIONS(state) do\n                    v2, a2←MIN-VALUE(game, game.RESULT(state, a)) \n                    if v2 > v then\n                        v, move←v2, a \n                return v, move\n            function MIN-VALUE(game, state) returns a (utility, move) pair\n                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n                v←+∞\n                for each a in game.ACTIONS(state) do\n                    v2, a2←MAX-VALUE(game, game.RESULT(state, a)) \n                    if v2 < v then\n                        v, move←v2, a \n                return v, move\n            '''\n            --------------------\n            '''\n             function ALPHA-BETA-SEARCH(game, state) returns an action \n                player←game.TO-MOVE(state)\n                value, move←MAX-VALUE(game, state,−∞,+∞)\n                return move\n             function MAX-VALUE(game, state, α, β) returns a (utility, move) pair\n                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n                v←−∞\n                for each a in game.ACTIONS(state) do\n                    v2, a2←MIN-VALUE(game, game.RESULT(state, a),α,β) \n                    if v2 > v then\n                        v, move←v2, a\n                        α←MAX(α, v)\n                    if v ≥ β then return v, move\n                return v, move\n             function MIN-VALUE(game, state, α, β) returns a (utility, move) pair\n                if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null \n                v←+∞\n                for each a in game.ACTIONS(state) do\n                    v2, a2←MAX-VALUE(game, game.RESULT(state, a),α,β) \n                    if v2 < v then\n                        v, move←v2, a\n                        β←MIN(β, v)\n                    if v ≤ α then return v, move\n                return v, move\n              '''\n                        \n\n## Module 5 Definitions\n* **Orderability** - Exactly one of(A≻B),(B≻A), or(A∼B)holds [prefer one or both are equal]\n* **Transitivity** - (A≻B)∧(B≻C) ⇒ (A≻C)\n* **Continuity** - B between A and C in preference, then for probability p, agent will be indifferent between getting B & A+C\n* **Substitutability** - If indifferent to A and B, then same for complex lotteries where B substituted for A\n* **Monotonicity** - For same outcomes, if A is preferred to B then lottery with higher probability for A is preferred\n* **Decomposability** - Compound lotteries may be reduced to simple ones using laws of probability\n* **Expected utility of a lottery** - The utility of a lottery is the sum of the probability of each outcome times the utility of that outcome.\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n A constraint satisfaction problem consists of three components, namely, X which is a set of variables, {X1,...,Xn},                 D which is a set of domains, {D1,...,Dn}, one for each variable and C which is a set of constraints that specify allowable combinations of values.                CSPs assign values to variables,{Xi=vi,Xj=vj,...} and solving such a problem is NP complete. An assignment that does not violate any constraints is                called a consistent or legal assignment.                A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment.               Problems can be easily formulated as CSPs due to natural representation and easy pruning.               Variations of CSP - finite/infinite, discrete/continuous, linear/non-linear, unary/binary/global.\n              \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n A CSP algorithm can generate successors by choosing a new variable assignment, or it perform inference in the form of constraint propagation:              using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on.              This leaves fewer options for the next choice of a variable assignment. Constraint propagation may be intertwined with search, or it may be done as a preprocessing step, before search starts.              Sometimes this preprocessing can solve the whole problem, so no search is required at all.              Local consistency treats each variable as a node in a graph and each binary constraint as an edge, and removes inconsistent values throughout the graph.             Stronger forms of propagation can be defined with the notion of k-consistency.             A CSP is k- consistent if, for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.             A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)- consistent, ... all the way down to 1-consistent.               \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \n             '''\n             function BACKTRACKING-SEARCH(csp) returns a solution or failure \n                  return BACKTRACK(csp,{})\n             function BACKTRACK(csp, assignment) returns a solution or failure\n                  if assignment is complete then return assignment\n                  var ← SELECT-UNASSIGNED-VARIABLE(csp, assignment)\n                  for each value in ORDER-DOMAIN-VALUES(csp, var, assignment) do\n                      if value is consistent with assignment then\n                          add {var = value} to assignment \n                          inferences←INFERENCE(csp,var,assignment) \n                          if inferences ̸= failure then\n                              add inferences to csp\n                              result ← BACKTRACK(csp, assignment) \n                              if result ̸= failure then return result \n                              remove inferences from csp\n                          remove {var = value} from assignment return failure\n              '''\n             \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Local search algorithms use a complete-state formulation where each state assigns a value to every variable,                 and the search changes the value of one variable at a time. It uses the min-conflicts heuristic.\n                function MIN-CONFLICTS(csp, max steps) returns a solution or failure \n                inputs: csp, a constraint satisfaction problem\n                        max steps, the number of steps allowed before giving up\n                    current ← an initial complete assignment for csp \n                    for i=1 to max steps do\n                      if current is a solution for csp then \n                        return current\n                      var←a randomly chosen conflicted variable from csp.VARIABLES \n                      value←the value v for var that minimizes CONFLICTS(csp,var,v,current) \n                      set var = value in current\n                    return failure\n              \n\n## AIMA Chapter 6.5 The Structure of Problems\n  Any tree-structured CSP can be solved in time linear in the number of variables. \n                  To solve a tree-structured CSP, first pick any variable to be the root of the tree, and \n                  choose an ordering of the variables such that each variable appears after its parent in the tree. Such an ordering is called a topological sort.\n                  Any tree with n nodes has n − 1 edges, so we can make this graph directed arc-consistent in O(n) steps, \n                  each of which must compare up to d possible domain values for two variables, for a total time of O(nd^2).\n                  Cutset conditioning can reduce a general CSP to a tree-structured one and is quite efficient (requiring only linear memory) if a small cutset can be found. \n                  Tree decomposition techniques transform the CSP into a tree of subproblems and are efficient if the tree width of the constraint graph is small; \n                  however they need memory exponential in the tree width of the constraint graph. \n             \n\n## Module 6 Lecture Notes\n Some heuristics for CSPs are:\n                        1) Most constrained variable/ Minimum remaining values or fail-first heuristic [avoid pointless search by early failure detection]\n                        2) Most constraining variable or degree heuristic [reduces brancing factor by selecting variable with largest number of constraints on neighbours]\n                        3) Least constraining value - order while examining values [prefers values which rule out fewest choices for neighbours] \n                        4) Forward checking - when a variable X is assigned, the forward-checking process establishes arc consistency for it: \n                              for each unassigned variable Y that is connected to X by a constraint, delete from Y ’s domain any value that is inconsistent with the value chosen for X.\n                        \n\n## Module 6 Definitions\n* **Node-consistent** - all the values in the variable’s domain satisfy the variable’s unary constraints\n* **Arc-consistent** - every value in its domain satisfies the variable’s binary constraints\n* **Path consistency** - tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n A KB is a set of sentences represented in a knowledge representation language each expressing an assertion of the world.              Inference must obey the requirement that when one ASKs a question of the knowledge base, the answer should follow from what has              been told (or TELLed) to the knowledge base previously.              These sentences are expressed according to the syntax of the representation language, which specifies all the sentences that are well formed.              Logic defines the semantics, or meaning, of sentences. The semantics defines the truth of each sentence with respect to each possible world.              Knowledge level specifies what the agent knows and what its goals are, to determine its behaviour. \n             A KB can be built on two appraoches, DECLRATIVE tells what it to be known while PROCEDURAL encodes desired behaviour in program code.  \n             \n\n## AIMA Chapter 7.2 The Wumpus World\n The Wumpus World \n\n## AIMA Chapter 7.3 Logic\n Models are mathematical abstactions with a fixed truth value for relevant sentences.              If a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α. \n             We use the notation M(α) to mean the set of all models of α.\n             For logical entailment, we have α |= β if and only if M(α) ⊆ M(β). \n             Entailment is used to perform logical inferencing using a model checking algorithm.\n             An inference algorithm that derives only entailed sentences is called sound or truth-preserving.\n             An inference algorithm is complete if it can derive any sentence that is entailed. \n             \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. \n            There are five connectives in common use: ¬  ∧ ∨ ⇒ ⇔ \n            \n\n## AIMA 7.5 Propositional Theorem Proving\n Logical equivalence means α≡β if and only if α|=β and β|=α. \n             Proof problem is defined using - INITIAL STATE: the initial knowledge base, \n             ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule, \n             RESULT: the result of an action is to add the sentence in the bottom half of the inference rule, and\n             GOAL: the goal is a state that contains the sentence we are trying to prove.\n             An important property of logical systems is monotonicity, which says that the set of entailed sentences can only increase as information              is added to the knowledge base. For any sentences α and β, if KB |= α then KB∧β |= α.\n             \n\n## Module 7 Lecture Notes\n Resolution  - If li and 𝓂 are complementary literals, which means that one is the negation of another, then we can eliminate                       them via unit resolution. [Full resolution rule for complementary literals li and 𝓂j]                       Resolution rule only applies to clauses - disjunction of literals but every sentence can be a conjunction of clauses.                       \n                      Conjunctive Normal Form (CNF)\n                      1) Every sentence of propositional logic is logically equivalent to a conjunction of clauses. Clauses are disjunctions of literals.\n                      2) Eliminate⇔byreplacing𝛂⇔βwith(𝛂⟹β)⋀(β⟹𝛂)\n                      3) Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β\n                      4) Move ¬ inwards (eliminate double negation, and apply De Morgan’s rules\n                      5) Now the sentence will contain nested ⋀ and ⋁ operators applied to literals. Apply distributivity law to distribute ⋁ over ⋀ wherever possible.\n                      \n                      '''\n                      Resolution Algorithm\n                      Inference procedures based on resolution work using the principle of proof by contradiction.\n                      To show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable. Here’s how:\n                      First, convert (KB ⋀ ¬𝛂) into CNF\n                      Then apply the resolution rule to the resulting clauses.\n                      Resolve every pair that contains complementary literals to produce a new clause If that new clause isn’t already present, then add it to the set.\n                      Continue the process until one of two things happens:\n                      1)There are no new clauses that can be added. In this case, the KB does not entail 𝛂 \n                      2)Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂\n                      '''\n\n                      Forward Chaining is a kind of data-driven reasoning. An agent can start with known data, adding premises as new percepts come in, and\n                      then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\n                      Backward chaining a form of goal-directed reasoning - working backwards from a query. If the query is known to be true, then no work is needed.\n                      Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining),\n                      then the query is true.\n                      \n\n## Module 7 Definitions\n* **Axiom** - sentence that is taken as being given without being derived from other sentences\n* **Inference** - deriving new sentences from old\n* **Logical entailment** - α |= β if and only if, in every model in which α is true, β is also true.\n* **Theorem proving** - applying rules of inference directly to sentences in KB to construct a proof of the desired sentence without consulting models\n* **Logical equivalence** - two sentences α and β are logically equivalent if they are true in the same set of models.\n* **Definite clause** - disjunction of literals where exactly one is positive\n* **Horn clause** - disjunction of literals where at most one is positive\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}