{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e7dc6742-3334-4ecf-e554-522660936d13"
      },
      "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": 276,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7953ea8c-8076-49ad-97c9-a1c57c6cf471"
      },
      "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": 277,
      "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 = \"Shanna Edwards\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 278,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 =\"\"\" human vs rational, thought vs behavior  \n",
        "\n",
        "**Turing Test**- Actingv humanly. can a machnine think? The computer passes if a\n",
        "human can't tell it's a computer after posing written questions and getting a \\\n",
        "response. Computer would need: NLP, knowledge representation (ie what it knows),\\\n",
        "reasoning, learning & ability to adapt to new information and patterns.  \n",
        "\n",
        "Total turing test involves interacting with objects in the real world, thus the\\\n",
        "computer would also need computer vision and a physical way to move objects \\\n",
        "around   \n",
        "\n",
        "**Cognitive Modelling** approach- We have to know how humans think to say that a \\\n",
        "program thinks like a human. Learning about human thought- introspection, \\\n",
        "psychological experiments, brain imaging. \n",
        "\n",
        "\n",
        "**Law of thought** approach- thinking rationally. Artistotle's syllogisms provide\\\n",
        "a pattern for argyment where the conclusion is always correct when the premises\\\n",
        "are also correct.  e.g. Socrates is a man, all men are mortal & therefore socrates\\\n",
        "is mortal. -> govern operation of the mind -> the field of logic  \n",
        "\n",
        "develop notation for statements about the world -> programs that can solve any \\\n",
        "problem in logical notation. Logic requires certain knowledge of the world though,\\\n",
        "and this is not often the case. Probability fills the gap, and allows rigorous\\\n",
        "reasoning and rational thought, but not rational action.  \n",
        "\n",
        "**Acting rationally**- rational agent approach. Pros: no longer imitating human \\\n",
        "behaviour. more general than law of thought approach bc you can acheieve rationality\\\n",
        "in other ways than correct inference. Also allows for scientific development bc\\\n",
        "rationality is mathematically well defined(?)   \n",
        "\n",
        "**Value alignment problem**- how well your true preferences and the objective you\\\n",
        "put into the machine agree \"\"\"\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 = \"\"\" **Qualification problem**- difficulty capturing every contingency\\\n",
        "of appropriate behaviour in a set of necessary and sufficient logical rules. \n",
        "\n",
        "**embodied cognition**- cognition takes place in a body, which is in an environment.\\\n",
        "It doesn't make sense considering the brain separately, because key information\\\n",
        "would be missed. Robotics, vision etc. are more central with this approach.  \n",
        "\n",
        "Turing & Godel- Some mathematical questions are unanswerable by formal systems.  \n",
        "\n",
        "G(F) is a sentence in F, but cannot be proved by F.  \n",
        "If F is consistent, then G(F) is true.  \n",
        "\n",
        "Flaw: there are some statements that some people can't assert, and they are no\\\n",
        "less human. 2. His theory applies to mathemematics, not computers. No entity\\\n",
        "can prove things that are impossible to prove. 3. His theorem only applies to \\\n",
        "formal systmes that are powerful enough to do arithmetic, ie Turing machines. \\\n",
        "Computers and turing machines are not equivalent, bc computers are finite.\\\n",
        "Computers can also change their minds.  \n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" Alan Turing- **\"Polite convention\"** that everyone thinks. \\\n",
        "John Searle- rejects this with Chinese room argument. \n",
        "\n",
        "**Consciousness**- awareness of the outside world and the self, and the experience\\\n",
        "of living. qualia- intrinsic nature of experiences. The big Q is whether\\\n",
        "machines have this\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Agents perceive percepts with sensors and act on them with \\\n",
        "actuators.  \n",
        "\n",
        "**Percept**- what the agent is perceiving  \n",
        "Percept Sequence- The full history of all the agent has perceived. \n",
        "\n",
        "An agent's choice of action at a given time depends on its percept sequence and\\\n",
        "built-in knowledge, but not something it hasn't perceived (no omniscience). \n",
        "\n",
        "**Randomness** can be intelligent. In single-agent environments, it can help to avoid\\\n",
        "infinite loops but isn't actually usually the most rational option\n",
        "\n",
        " \"\"\"\n",
        "chapter2_2 = \"\"\" **Consequentialism**- evaluate an agent based on its consequences \n",
        "\n",
        "Design performance measure based on what you want achieved, not what you expect\\\n",
        "the agent to do (e.g. rewarding for a clean floor rather than amount of dirt\\\n",
        "cleaned). \n",
        "\n",
        "What is rational is given by: performance measure, agent's prior knowledge, \\\n",
        "agent's percept sequence to date, agent's possible actions. \n",
        "\n",
        "**Omniscience** (knowing the actual outcomes for actions) is impossible in reality \\\n",
        "so we go for rationality  \n",
        "\n",
        "**Information gathering**- improves rationality and involves doing actions to \\\n",
        "modify future percepts (e.g. exploration). \n",
        "\n",
        "An agent lacks **autonomy** when it relies on prior knowledge of its designer rather\\\n",
        "than its own learning and percepts. Rational agents should have autonomy.\n",
        "\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" **agent architecture**- agent's computing device with sensors and\\\n",
        "actuators. \n",
        "\n",
        "Agent function may depend on the whole percept history, while agent program only\\\n",
        "needs current percept.  \n",
        "\n",
        "Agent programs can be coroutines that run asynchronously with the environment.\\\n",
        "need input/output port which takes percepts and outputs actions respectively. \n",
        "\n",
        "**Simple reflex agent**- selects actions based on current percept, ingoring percept\\\n",
        "history.   \n",
        "\n",
        "**Condition ation rule**- if x then do y  \n",
        "\n",
        "**Model based agents-** keeps track of what it can't see in partially observable\\\n",
        "environments. an internal state that depends on percept history. Need: sensor\\\n",
        "model, transition model, actions, rules and state\n",
        "\n",
        "**Sensor model**- how the state of the world is reflected in the agent's percepts\\\n",
        "ie when it rains, droplets of water obstruct the view from the car(?). \n",
        "\n",
        "**Goal-based agents** also take into account their goal to make a decision. \n",
        "\n",
        "**Utility function**- agent's internalization of the performance measure \n",
        "\n",
        "**Learning agents**\n",
        "\n",
        "**Learning element**- responsible for making improvements. \n",
        "**Performance Element**- responsible for selecting external actions \n",
        "\n",
        "**Atomic representation**- each state of the world is indivisible  (ie no internal\\\n",
        " structure).  \\\n",
        "\n",
        "**Factored respresentation**- splits state up into a set of variables and \\\n",
        " attributes, each of which has value \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" **Alan Turing**- Imitation Game Test. \n",
        "\n",
        "**John Searle** - Language is just the application of rules. You need a brain to be \\\n",
        "human.  \n",
        "\n",
        "**Strong AI** - computer has a mind/has cognitive states (actually thinking) \n",
        "\n",
        "**Weak AI**- computer stimulates thought but has no real understanding \n",
        "\n",
        "**Daniel Dennett**- Brain in a vat   \n",
        "\n",
        "\n",
        "**Task Environments** (problem specification)\n",
        "need: performance measure, sensors, actuators, environment\n",
        "\n",
        "types of environments:  \n",
        "\n",
        "**fully observable**- can see all relevant objects and such (chess). \n",
        "\n",
        "**partially observable**- can access some information (self driving car, robot vaccuum)\n",
        "\n",
        "**deterministic**- knowledge of an action's results(ie next state is completely\\\n",
        "determined by this one).\n",
        "wrt specific agents (chess). \n",
        "\n",
        "**non-deterministic**- games of chance, outcome uncertain\n",
        "-> often called stochastic (probabilistic)\n",
        "\n",
        "**episodic**- agents need to process self-contained episodes. choice not dependent on\n",
        "previous decisions e.g. (picking defective items off assembly line)  \n",
        "\n",
        "**sequential**- this decision affects future ones. thus involves planning ahead. \n",
        "\n",
        "**static**- doesn't change while agent deliberates (crossword puzzle). \n",
        "\n",
        "**dynamic**- environment can change (self driving car). \n",
        "  \n",
        "**semi-dynamic**- agent score changed but not the environment? (chess penalty for \\\n",
        "taking too long)   \n",
        "\n",
        "**discrete**- applies to the state of the environment, the handling of time, \\\n",
        "percepts and actions. finite set of actions, discrete states (board games). \n",
        "\n",
        "continuous is the opposite\n",
        "\n",
        "**single agent**. \n",
        "\n",
        "**multiagent**- can be competetive or cooperative, usually assume other agent is \\\n",
        "acting rationally.  \n",
        "\n",
        "**Known** (vs unknown environment)- state of knowledge about the law of physics\\\n",
        "for the environment. we know how the world works. KNown environments can still\\\n",
        "be partially observable (e.g. solitaire, where you don't see the cards\\\n",
        "beforehand but you know the rules)\n",
        "\n",
        "**Reflex agent** selects actions based on current percept, ignoring previous stuff. \n",
        "\n",
        "**problem-solving agent** plans ahead and considers path to goal   \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 (through sensors) and act(through \\\n",
        "actuators) in an environment\",\n",
        "\"agent function\" : \"takes a sequence of percepts and maps each to an action  \\\n",
        "from a predefined list. abstract mathematical description\",\n",
        "\"agent program\" : \"concrete implementation of the agent function running on a\\\n",
        "physical system\",\n",
        "\"percept\" : \"perceptual inputs.. stuff happening in the world\",\n",
        "\"performance measure\" : \"criteria for success +1 for good things -1 for \\\n",
        "bad things. evalutates the behavior of agent \",\n",
        "\"rational agent\" : \"perceives its environment and behaves rationally. ie selects\\\n",
        "an action to maximize the expected value of its performance measure\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 279,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b3967052-10f8-4398-ecd5-16fda9c57dca"
      },
      "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": 280,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n human vs rational, thought vs behavior  \n\n**Turing Test**- Actingv humanly. can a machnine think? The computer passes if a\nhuman can't tell it's a computer after posing written questions and getting a response. Computer would need: NLP, knowledge representation (ie what it knows),reasoning, learning & ability to adapt to new information and patterns.  \n\nTotal turing test involves interacting with objects in the real world, thus thecomputer would also need computer vision and a physical way to move objects around   \n\n**Cognitive Modelling** approach- We have to know how humans think to say that a program thinks like a human. Learning about human thought- introspection, psychological experiments, brain imaging. \n\n\n**Law of thought** approach- thinking rationally. Artistotle's syllogisms providea pattern for argyment where the conclusion is always correct when the premisesare also correct.  e.g. Socrates is a man, all men are mortal & therefore socratesis mortal. -> govern operation of the mind -> the field of logic  \n\ndevelop notation for statements about the world -> programs that can solve any problem in logical notation. Logic requires certain knowledge of the world though,and this is not often the case. Probability fills the gap, and allows rigorousreasoning and rational thought, but not rational action.  \n\n**Acting rationally**- rational agent approach. Pros: no longer imitating human behaviour. more general than law of thought approach bc you can acheieve rationalityin other ways than correct inference. Also allows for scientific development bcrationality is mathematically well defined(?)   \n\n**Value alignment problem**- how well your true preferences and the objective youput into the machine agree \n\n## AIMA Chapter 27.1 The Limits of AI\n **Qualification problem**- difficulty capturing every contingencyof appropriate behaviour in a set of necessary and sufficient logical rules. \n\n**embodied cognition**- cognition takes place in a body, which is in an environment.It doesn't make sense considering the brain separately, because key informationwould be missed. Robotics, vision etc. are more central with this approach.  \n\nTuring & Godel- Some mathematical questions are unanswerable by formal systems.  \n\nG(F) is a sentence in F, but cannot be proved by F.  \nIf F is consistent, then G(F) is true.  \n\nFlaw: there are some statements that some people can't assert, and they are noless human. 2. His theory applies to mathemematics, not computers. No entitycan prove things that are impossible to prove. 3. His theorem only applies to formal systmes that are powerful enough to do arithmetic, ie Turing machines. Computers and turing machines are not equivalent, bc computers are finite.Computers can also change their minds.  \n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Alan Turing- **\"Polite convention\"** that everyone thinks. John Searle- rejects this with Chinese room argument. \n\n**Consciousness**- awareness of the outside world and the self, and the experienceof living. qualia- intrinsic nature of experiences. The big Q is whethermachines have this\n\n## AIMA 2.1 Agents and Environments\n Agents perceive percepts with sensors and act on them with actuators.  \n\n**Percept**- what the agent is perceiving  \nPercept Sequence- The full history of all the agent has perceived. \n\nAn agent's choice of action at a given time depends on its percept sequence andbuilt-in knowledge, but not something it hasn't perceived (no omniscience). \n\n**Randomness** can be intelligent. In single-agent environments, it can help to avoidinfinite loops but isn't actually usually the most rational option\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n **Consequentialism**- evaluate an agent based on its consequences \n\nDesign performance measure based on what you want achieved, not what you expectthe agent to do (e.g. rewarding for a clean floor rather than amount of dirtcleaned). \n\nWhat is rational is given by: performance measure, agent's prior knowledge, agent's percept sequence to date, agent's possible actions. \n\n**Omniscience** (knowing the actual outcomes for actions) is impossible in reality so we go for rationality  \n\n**Information gathering**- improves rationality and involves doing actions to modify future percepts (e.g. exploration). \n\nAn agent lacks **autonomy** when it relies on prior knowledge of its designer ratherthan its own learning and percepts. Rational agents should have autonomy.\n\n\n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n **agent architecture**- agent's computing device with sensors andactuators. \n\nAgent function may depend on the whole percept history, while agent program onlyneeds current percept.  \n\nAgent programs can be coroutines that run asynchronously with the environment.need input/output port which takes percepts and outputs actions respectively. \n\n**Simple reflex agent**- selects actions based on current percept, ingoring percepthistory.   \n\n**Condition ation rule**- if x then do y  \n\n**Model based agents-** keeps track of what it can't see in partially observableenvironments. an internal state that depends on percept history. Need: sensormodel, transition model, actions, rules and state\n\n**Sensor model**- how the state of the world is reflected in the agent's perceptsie when it rains, droplets of water obstruct the view from the car(?). \n\n**Goal-based agents** also take into account their goal to make a decision. \n\n**Utility function**- agent's internalization of the performance measure \n\n**Learning agents**\n\n**Learning element**- responsible for making improvements. \n**Performance Element**- responsible for selecting external actions \n\n**Atomic representation**- each state of the world is indivisible  (ie no internal structure).  \n**Factored respresentation**- splits state up into a set of variables and  attributes, each of which has value \n\n\n\n## Module 1 Lecture Notes\n **Alan Turing**- Imitation Game Test. \n\n**John Searle** - Language is just the application of rules. You need a brain to be human.  \n\n**Strong AI** - computer has a mind/has cognitive states (actually thinking) \n\n**Weak AI**- computer stimulates thought but has no real understanding \n\n**Daniel Dennett**- Brain in a vat   \n\n\n**Task Environments** (problem specification)\nneed: performance measure, sensors, actuators, environment\n\ntypes of environments:  \n\n**fully observable**- can see all relevant objects and such (chess). \n\n**partially observable**- can access some information (self driving car, robot vaccuum)\n\n**deterministic**- knowledge of an action's results(ie next state is completelydetermined by this one).\nwrt specific agents (chess). \n\n**non-deterministic**- games of chance, outcome uncertain\n-> often called stochastic (probabilistic)\n\n**episodic**- agents need to process self-contained episodes. choice not dependent on\nprevious decisions e.g. (picking defective items off assembly line)  \n\n**sequential**- this decision affects future ones. thus involves planning ahead. \n\n**static**- doesn't change while agent deliberates (crossword puzzle). \n\n**dynamic**- environment can change (self driving car). \n  \n**semi-dynamic**- agent score changed but not the environment? (chess penalty for taking too long)   \n\n**discrete**- applies to the state of the environment, the handling of time, percepts and actions. finite set of actions, discrete states (board games). \n\ncontinuous is the opposite\n\n**single agent**. \n\n**multiagent**- can be competetive or cooperative, usually assume other agent is acting rationally.  \n\n**Known** (vs unknown environment)- state of knowledge about the law of physicsfor the environment. we know how the world works. KNown environments can stillbe partially observable (e.g. solitaire, where you don't see the cardsbeforehand but you know the rules)\n\n**Reflex agent** selects actions based on current percept, ignoring previous stuff. \n\n**problem-solving agent** plans ahead and considers path to goal   \n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive (through sensors) and act(through actuators) in an environment\n* **Agent function** - takes a sequence of percepts and maps each to an action  from a predefined list. abstract mathematical description\n* **Agent program** - concrete implementation of the agent function running on aphysical system\n* **Percept** - perceptual inputs.. stuff happening in the world\n* **Performance measure** - criteria for success +1 for good things -1 for bad things. evalutates the behavior of agent \n* **Rational agent** - perceives its environment and behaves rationally. ie selectsan action to maximize the expected value of its performance measure\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "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": "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 = \"\"\"White space matters in python. use backslash to \\\n",
        "continue line.  \n",
        "\n",
        "**Strong typed**- every object has a fixed type so interpreter doesn't allow \\\n",
        "incompatible operations.  \n",
        "\n",
        "Also **dynamically typed**- no type signatures for functions, types of var not\\\n",
        "declared and you can reassign them to a diff type\n",
        "\n",
        "**Power**- 2^4= 2**4 \n",
        "\n",
        "+= -= etc. as in Java but no ++ or --\n",
        "\n",
        "**Strings:** \n",
        "\n",
        "1.immutable \n",
        "2. single or double quotes, triple for multi-line \n",
        "3. ```+``` for concatenation \n",
        "\n",
        "r'\\n' means raw   \n",
        "\n",
        "print(%s can speak %d languages\" % (\"C3PO\", 2)). \n",
        "\n",
        "use y= x[:] to obtain a shallow copy \n",
        "\n",
        "**==** compare by value \n",
        "\n",
        "**is** compare by object reference \n",
        "\n",
        "**Tuples** immutable ordered sequence of items (can have mixed types) e.g\\\n",
        "(1, \"two\", 3.0)\n",
        "\n",
        "**List** Mutable ordered sequence of items (mixed types) e.g [1,2,3]. \n",
        " \n",
        "``` x[index]```  to acess element   \n",
        "\n",
        "``` x[-index]```  for negative lookup  \n",
        "\n",
        "``` x[i1:i2]```  for slicing, includive of i1 exclusive of i2. \n",
        "\n",
        "``` x[i1:i2:n]```  from i1 to i2 choosing every nth item \n",
        "\n",
        "``` x[:i1]```  copy from beginning  \n",
        "\n",
        "``` x[i1:]```  copy from i1 to end\n",
        "\n",
        "``` li.append()```   \n",
        "\n",
        "``` li.insert(i, e)```  insert e at index i \n",
        "\n",
        "``` li.index(e)```  index of first occurence of e in li\n",
        "\n",
        "``` li.count('b')```  num occurences\n",
        "\n",
        "``` li.remove(e) ``` remove first occurence of e\n",
        "\n",
        "``` li.reverse() ``` reverse in place (bc lists are mutable) \n",
        "\n",
        "``` li.sort() ``` sort in place \n",
        "\n",
        "``` sorted(li) ``` sorted copy \n",
        "\n",
        "``` x.join(\" z\") ``` \n",
        "\n",
        "``` x.split(\" \") ``` \n",
        "\n",
        "``` x.capitalize() ``` dog -> Dog \n",
        "\n",
        "``` x.upper() ``` dog -> DOG\n",
        "\n",
        "``` x.strip('-') ``` hi- -> hi \n",
        "\n",
        "**Dictionaries** \n",
        "\n",
        "immutable keys (like tuples) bc hashable \n",
        "\n",
        "```d = {\"a\": 1, \"b\":2} ``` \n",
        "\n",
        "d[a] = 1 (but cannot get by value) \n",
        "\n",
        "```d.keys(), d.values(), d.items()```\n",
        "\n",
        "**functions** \n",
        "\n",
        "``` def example_function(input1, input2 = 3):  ```  \n",
        "\n",
        "can return multiple values! will be a tuple  \n",
        "\n",
        "nondefault values come first, else SyntaxError \n",
        "\n",
        "```example_function(3, input2 = 4)``` keyword args should come last else err \n",
        "\n",
        "```*args``` for any number of nonkeyword arguments func(*li) or func(x,y,x)\n",
        "\n",
        "```**kwargs``` for any number of keyword arguments func(**dict) or func(in= \"x\", z=\"y\")  \n",
        "\n",
        "``` def example_function(input1, *args, **kwargs):  ```  \n",
        "\n",
        "**Functions** can be assigned to variables, stored in data structures, passed in\\\n",
        "as args, returned etc \n",
        "\n",
        "**Higher order function**  \n",
        "\n",
        "``` \n",
        "def compose(f, g, x):\n",
        "      return f(g(x)) \n",
        "\n",
        "compose(str, sum, [1,2,3]) \n",
        "``` \n",
        "\n",
        "**Classes**  \n",
        "\n",
        "``` class Student(PennStudent, OtherClass): #PennStudent is a superclass  \n",
        "  univ: \"penn\" #class attribute\n",
        "  def __init__(self): #constructor\n",
        "    PennStudent.__init__(self)\n",
        "    self.var = var\n",
        "  def method():\n",
        "\n",
        "student1 = Student(etc.)\n",
        "student1.method() or Student.method(student1) \n",
        "```\n",
        "**Magic methods** \n",
        "\n",
        "__len__  \n",
        "\n",
        "__copy__ \n",
        "\n",
        "__cmp__ for == \n",
        "\n",
        "__add__  \n",
        "\n",
        "__neg__ -  \n",
        "\n",
        "__str__ for print() \n",
        "\n",
        "``` for x in range(5):\n",
        "#[0-4]\n",
        "```\n",
        "\n",
        "``` [x**2 for x in n if y]\n",
        "    d = {k:v for (k,v) in l}, also sets \n",
        "``` \n",
        "\n",
        "Iterators: has a next() method, but no hasNext() so catch exception. \n",
        "\n",
        "```i = iter(lst)\n",
        "``` \n",
        "\n",
        "```\n",
        "try: \n",
        "    print(g.next())\n",
        "except StopIteration:\n",
        "  #stuff \n",
        "\n",
        "\n",
        "// integer division \n",
        "```\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"immutability\" : \"object cannot be modified after creation\",\n",
        "\"first class object\" : \"functions can be destroyed, created, passed to other \\\n",
        "functions, returned as a value etc.\"\n",
        "\n",
        "}"
      ],
      "execution_count": 281,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "50341970-b9dc-498b-e388-832418c6c196"
      },
      "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": 282,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\nWhite space matters in python. use backslash to continue line.  \n\n**Strong typed**- every object has a fixed type so interpreter doesn't allow incompatible operations.  \n\nAlso **dynamically typed**- no type signatures for functions, types of var notdeclared and you can reassign them to a diff type\n\n**Power**- 2^4= 2**4 \n\n+= -= etc. as in Java but no ++ or --\n\n**Strings:** \n\n1.immutable \n2. single or double quotes, triple for multi-line \n3. ```+``` for concatenation \n\nr'\n' means raw   \n\nprint(%s can speak %d languages\" % (\"C3PO\", 2)). \n\nuse y= x[:] to obtain a shallow copy \n\n**==** compare by value \n\n**is** compare by object reference \n\n**Tuples** immutable ordered sequence of items (can have mixed types) e.g(1, \"two\", 3.0)\n\n**List** Mutable ordered sequence of items (mixed types) e.g [1,2,3]. \n \n``` x[index]```  to acess element   \n\n``` x[-index]```  for negative lookup  \n\n``` x[i1:i2]```  for slicing, includive of i1 exclusive of i2. \n\n``` x[i1:i2:n]```  from i1 to i2 choosing every nth item \n\n``` x[:i1]```  copy from beginning  \n\n``` x[i1:]```  copy from i1 to end\n\n``` li.append()```   \n\n``` li.insert(i, e)```  insert e at index i \n\n``` li.index(e)```  index of first occurence of e in li\n\n``` li.count('b')```  num occurences\n\n``` li.remove(e) ``` remove first occurence of e\n\n``` li.reverse() ``` reverse in place (bc lists are mutable) \n\n``` li.sort() ``` sort in place \n\n``` sorted(li) ``` sorted copy \n\n``` x.join(\" z\") ``` \n\n``` x.split(\" \") ``` \n\n``` x.capitalize() ``` dog -> Dog \n\n``` x.upper() ``` dog -> DOG\n\n``` x.strip('-') ``` hi- -> hi \n\n**Dictionaries** \n\nimmutable keys (like tuples) bc hashable \n\n```d = {\"a\": 1, \"b\":2} ``` \n\nd[a] = 1 (but cannot get by value) \n\n```d.keys(), d.values(), d.items()```\n\n**functions** \n\n``` def example_function(input1, input2 = 3):  ```  \n\ncan return multiple values! will be a tuple  \n\nnondefault values come first, else SyntaxError \n\n```example_function(3, input2 = 4)``` keyword args should come last else err \n\n```*args``` for any number of nonkeyword arguments func(*li) or func(x,y,x)\n\n```**kwargs``` for any number of keyword arguments func(**dict) or func(in= \"x\", z=\"y\")  \n\n``` def example_function(input1, *args, **kwargs):  ```  \n\n**Functions** can be assigned to variables, stored in data structures, passed inas args, returned etc \n\n**Higher order function**  \n\n``` \ndef compose(f, g, x):\n      return f(g(x)) \n\ncompose(str, sum, [1,2,3]) \n``` \n\n**Classes**  \n\n``` class Student(PennStudent, OtherClass): #PennStudent is a superclass  \n  univ: \"penn\" #class attribute\n  def __init__(self): #constructor\n    PennStudent.__init__(self)\n    self.var = var\n  def method():\n\nstudent1 = Student(etc.)\nstudent1.method() or Student.method(student1) \n```\n**Magic methods** \n\n__len__  \n\n__copy__ \n\n__cmp__ for == \n\n__add__  \n\n__neg__ -  \n\n__str__ for print() \n\n``` for x in range(5):\n#[0-4]\n```\n\n``` [x**2 for x in n if y]\n    d = {k:v for (k,v) in l}, also sets \n``` \n\nIterators: has a next() method, but no hasNext() so catch exception. \n\n```i = iter(lst)\n``` \n\n```\ntry: \n    print(g.next())\nexcept StopIteration:\n  #stuff \n\n\n// integer division \n```\n\n\n## Module 2 Definitions\n* **Immutability** - object cannot be modified after creation\n* **First class object** - functions can be destroyed, created, passed to other functions, returned as a value etc.\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" Problem Solving agents use an atomic representation of states. \n",
        "\n",
        "**closed loop** system monitors percepts (good for non-deterministic). \n",
        "\n",
        "**open loop system** ignores percepts. no loop between agent and evironment \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" **touring problem** gives a set of location to visit rather than\\\n",
        "one goal. **TSP** involves visiting all nodes  \n",
        "\n",
        "**Robot navigation** path finiding in a 2d space (multi-d if interacting with\\\n",
        "objects\"\"\"\n",
        "chapter3_3 = \"\"\" **state space** set of states in the world and transition model\n",
        "\n",
        "**Search tree** node containing states of the world (& other stuff) joined by \\\n",
        "actions where one path leads to goal. ie defining paths between states to goal \n",
        "\n",
        "**Best-first search** chooses node with minimal f(n) (evaluation function). uses\\\n",
        "ap priority queue\n",
        "\n",
        "**Node** - State, parent, action, path cost g(n)\n",
        "\n",
        "  \"\"\"\n",
        "chapter3_4 = \"\"\" **BFS** \n",
        "\n",
        "``` \n",
        "node <- node(problem.initial) \n",
        "\n",
        "if node has goal state then return node \n",
        "\n",
        "otherwise, \n",
        "\n",
        "frontier = Queue()\n",
        "frontier.put(node)\n",
        "\n",
        "reached = {}  \n",
        "reached[problem.initial] = True\n",
        "\n",
        "came_from = {} \n",
        "came_from[problem.initial] = None\n",
        "\n",
        "while not frontier.empty(): \n",
        "    curr = frontier.get()\n",
        "    for next in neighbors(curr):\n",
        "      if next has goal return next\n",
        "      if next not in reached: \n",
        "        reached[next] = True\n",
        "        came_from[next] = curr\n",
        "        frontier.put(next)\n",
        "```\n",
        "\n",
        "**Dijkstra's or uniform cost**\n",
        "- best-first with f(n) as cost of path from root to current node (g(n))\n",
        "\n",
        "- check for goal when selected for expansion rather than when added to frontier. \\\n",
        "So if checks if a node is the goal after adding to frontier  \n",
        "\n",
        "- if all action costs are > 0, then no infinite path issue. it is optimal and \n",
        "complete \n",
        "\n",
        "- runtime depends on path cost lower bound and cost of the optimal solution. \\\n",
        "When action costs are equal, O(b^{d+1}), similar to bfs \n",
        "\n",
        "\n",
        "**Iterative-deepening and DLS**  \n",
        "\n",
        "IDS keeps running until failure (returned instead of cutoff) or result \n",
        "\n",
        "``` \n",
        "for depth = 0 to infinity, DLS(depth) \n",
        "``` \n",
        "\n",
        "for DLS, if (depth) > l, then cutoff is result. otherwise, check for cycles\\\n",
        "and continue as normal.  \n",
        "\n",
        "**Bi-directional search** \n",
        "- finds path from initial state to goal and vice versa. Stops when the two\\\n",
        "frontiers overlap. Motivation b^{d/2} + b^{d/2} < b^d. Must keep track of 2 sets\\\n",
        "of reached states, frontiers etc. \n",
        "\n",
        "Using best-first approach, you'd expand smallest-cost node across either frontier\\\n",
        "\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" **Search problem** - \n",
        "\n",
        "**states**- set S, state space, all possible states \n",
        "\n",
        "an **initial state**- $ s \\in S $\n",
        "\n",
        "set of **goal states**\n",
        "\n",
        "**actions**- set A. Actions(a) returns the actions **applicable** in s \n",
        "\n",
        "**transition model**- how to transition from one state to another, given input\n",
        "\n",
        "$ \\fforall s \\fforall a \\in Actions(s) Result(s, a) -> s_r $. \n",
        "\n",
        "path cost/performance measure- must be additive  \n",
        "\n",
        "$ c(x,a,y) \\geq $ is step cost where action a goes from state x to y \n",
        "\n",
        "Goal test: goal(s), is s the goal state? \n",
        "\n",
        "**Tree Search** - Does not check for redundant paths. It goes through all possible\\\n",
        "paths from  initial state or root. \n",
        "\n",
        "**Graph Search** - tree search modification that now checks redundant paths (ie)\\\n",
        "keep track of states seen so far. Uses more memory and faster and avoids loops \n",
        "\n",
        "**Uniformed search**- uses only problem definition so all non-goal states are the\\\n",
        "same \n",
        "\n",
        "**BFS** \n",
        "- FIFO queue frontier\n",
        "\n",
        "- add node to q after checking goal state  \n",
        "\n",
        "- complete if max branching factor(b) is finite  \n",
        "\n",
        "- optimal if cost = 1 per step (equally unweighted) \n",
        "\n",
        "- Time O(b^d) d= depth of least cost solution\n",
        "\n",
        "- Space O(b^d) bc stores every node  \n",
        "\n",
        "- good for possible infinite paths, if solutions have short paths, can discard\\\n",
        "unlikely paths quickly  \n",
        "\n",
        "- call to best-first search where f(n) is the depth\n",
        "\n",
        "**DFS** \n",
        "- LIFO queue frontier\n",
        "\n",
        "- not complete (loops & infinite depth) except if you account for repeasted states\\\n",
        "along path \n",
        "\n",
        "- not optimal \n",
        "\n",
        "- O(b^m) time. bad if m >> d where m is maximum depth of state space \n",
        "\n",
        "- Space O(bm) (good for restricted space or when there are many long-path\\\n",
        " solutions) \n",
        "\n",
        "- call to best-first with f(n) as negative depth(deepest first)\n",
        "\n",
        "**Depth-Limited Search: DLS** \n",
        "- DFS with limit l \n",
        "\n",
        "- no infinite paths \n",
        "\n",
        "- if l = d then optimal, otherwise not\n",
        "\n",
        "- generally incomplete and not optimal\n",
        "\n",
        "- incomplete if l < d, suboptimal if l > d\n",
        "\n",
        "- O(b^l) time \n",
        "\n",
        "- O(bl) space \n",
        "\n",
        "**Iterative deepening search** \n",
        "- Do DLS with increasing l \n",
        "\n",
        "- complete(?) & optimal \n",
        "\n",
        "- time complexity O(b^d)\n",
        "\n",
        "- O(bd) space\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\", \n",
        " \"state space\" : \"the set of all states reachable by any sequence of actions from\\\n",
        " the initial state\",\n",
        "\"path\" : \"sequence of actions from one state to another\",\n",
        "\"solution\" : \"path from initial state to goal. A solution is optimal if no other\\\n",
        "has a lower path cost\",\n",
        "\"frontier\" : \"states available to be expanded\",\n",
        "\"completeness\" : \"whether search strategy will find a solution or not\",\n",
        "\"optimality\" : \"whether it finds the path with the lowest cost first\",\n",
        "\"planning agents\": \"use factored or structured representations of states \\\n",
        "(internal structure)\"\n",
        "\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 283,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b612a43e-2595-4800-9873-0895f7be9fb3"
      },
      "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": 284,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem Solving agents use an atomic representation of states. \n\n**closed loop** system monitors percepts (good for non-deterministic). \n\n**open loop system** ignores percepts. no loop between agent and evironment \n\n\n\n\n## AIMA Chapter 3.2 Example Problems\n **touring problem** gives a set of location to visit rather thanone goal. **TSP** involves visiting all nodes  \n\n**Robot navigation** path finiding in a 2d space (multi-d if interacting withobjects\n\n## AIMA Chapter 3.3 Search Algorithms\n **state space** set of states in the world and transition model\n\n**Search tree** node containing states of the world (& other stuff) joined by actions where one path leads to goal. ie defining paths between states to goal \n\n**Best-first search** chooses node with minimal f(n) (evaluation function). usesap priority queue\n\n**Node** - State, parent, action, path cost g(n)\n\n  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n **BFS** \n\n``` \nnode <- node(problem.initial) \n\nif node has goal state then return node \n\notherwise, \n\nfrontier = Queue()\nfrontier.put(node)\n\nreached = {}  \nreached[problem.initial] = True\n\ncame_from = {} \ncame_from[problem.initial] = None\n\nwhile not frontier.empty(): \n    curr = frontier.get()\n    for next in neighbors(curr):\n      if next has goal return next\n      if next not in reached: \n        reached[next] = True\n        came_from[next] = curr\n        frontier.put(next)\n```\n\n**Dijkstra's or uniform cost**\n- best-first with f(n) as cost of path from root to current node (g(n))\n\n- check for goal when selected for expansion rather than when added to frontier. So if checks if a node is the goal after adding to frontier  \n\n- if all action costs are > 0, then no infinite path issue. it is optimal and \ncomplete \n\n- runtime depends on path cost lower bound and cost of the optimal solution. When action costs are equal, O(b^{d+1}), similar to bfs \n\n\n**Iterative-deepening and DLS**  \n\nIDS keeps running until failure (returned instead of cutoff) or result \n\n``` \nfor depth = 0 to infinity, DLS(depth) \n``` \n\nfor DLS, if (depth) > l, then cutoff is result. otherwise, check for cyclesand continue as normal.  \n\n**Bi-directional search** \n- finds path from initial state to goal and vice versa. Stops when the twofrontiers overlap. Motivation b^{d/2} + b^{d/2} < b^d. Must keep track of 2 setsof reached states, frontiers etc. \n\nUsing best-first approach, you'd expand smallest-cost node across either frontier\n\n\n \n\n## Module 3 Lecture Notes\n **Search problem** - \n\n**states**- set S, state space, all possible states \n\nan **initial state**- $ s \\in S $\n\nset of **goal states**\n\n**actions**- set A. Actions(a) returns the actions **applicable** in s \n\n**transition model**- how to transition from one state to another, given input\n\n$ \fforall s \fforall a \\in Actions(s) Result(s, a) -> s_r $. \n\npath cost/performance measure- must be additive  \n\n$ c(x,a,y) \\geq $ is step cost where action a goes from state x to y \n\nGoal test: goal(s), is s the goal state? \n\n**Tree Search** - Does not check for redundant paths. It goes through all possiblepaths from  initial state or root. \n\n**Graph Search** - tree search modification that now checks redundant paths (ie)keep track of states seen so far. Uses more memory and faster and avoids loops \n\n**Uniformed search**- uses only problem definition so all non-goal states are thesame \n\n**BFS** \n- FIFO queue frontier\n\n- add node to q after checking goal state  \n\n- complete if max branching factor(b) is finite  \n\n- optimal if cost = 1 per step (equally unweighted) \n\n- Time O(b^d) d= depth of least cost solution\n\n- Space O(b^d) bc stores every node  \n\n- good for possible infinite paths, if solutions have short paths, can discardunlikely paths quickly  \n\n- call to best-first search where f(n) is the depth\n\n**DFS** \n- LIFO queue frontier\n\n- not complete (loops & infinite depth) except if you account for repeasted statesalong path \n\n- not optimal \n\n- O(b^m) time. bad if m >> d where m is maximum depth of state space \n\n- Space O(bm) (good for restricted space or when there are many long-path solutions) \n\n- call to best-first with f(n) as negative depth(deepest first)\n\n**Depth-Limited Search: DLS** \n- DFS with limit l \n\n- no infinite paths \n\n- if l = d then optimal, otherwise not\n\n- generally incomplete and not optimal\n\n- incomplete if l < d, suboptimal if l > d\n\n- O(b^l) time \n\n- O(bl) space \n\n**Iterative deepening search** \n- Do DLS with increasing l \n\n- complete(?) & optimal \n\n- time complexity O(b^d)\n\n- O(bd) space\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - the set of all states reachable by any sequence of actions from the initial state\n* **Path** - sequence of actions from one state to another\n* **Solution** - path from initial state to goal. A solution is optimal if no otherhas a lower path cost\n* **Frontier** - states available to be expanded\n* **Completeness** - whether search strategy will find a solution or not\n* **Optimality** - whether it finds the path with the lowest cost first\n* **Planning agents** - use factored or structured representations of states (internal structure)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" **Consistency** \n",
        "\n",
        "h(n) <= c(n,a,n')+ h*(n') \n",
        "\n",
        "Every consistent heuristic is admissible, but not the other way around \n",
        "\n",
        "if the optimal solution has cost C* and the second best, C2, then A* returns the\\\n",
        "cost-optimal solution is h(n) never overestimates the cost by more than C2-C*.\n",
        "\n",
        "if h(n) is admissible for all nodes on the path, A* returns a cost-optimal sol\\\n",
        " regardless of other nodes. \n",
        "\n",
        " Along the path, g(n) is strictly monotonic(increasing). So, contours of the\\\n",
        "  state space don't overlap. If h(n) is consistent, f(n) (=g +h)is monotonic too.\n",
        "\n",
        "All nodes where f(n) < C* are **surely expanded nodes** \n",
        "\n",
        "no nodes with f(n) > C* will be expanded, but some with f(n) = C* \n",
        "\n",
        "\n",
        "Weighted A search \n",
        " \n",
        "Expands nodes with weighted heuristic value: \n",
        "\n",
        "f(n) = g(n) + W * h(n) for some W > 1 \n",
        "\n",
        "**Speedy search**- unbounded-cost search alg. Type of Greedy best-first search,\\\n",
        "where h(n) is the num steps to goal, regardless of cost. Same as GBFS when weights\\\n",
        " are uniform, but potentially faster otherwise. \n",
        "\n",
        " **Beam search** - incomplete and suboptimal but better for memory, because\\\n",
        "  frontier is bounded. So keep best k nodes, discarding others. \n",
        "  Alternative- keep track of nodes within delta of the best f-store node. all \\\n",
        "  strong candidates kept, weak ones discarded. \n",
        "\n",
        "```\n",
        "Iterative-deepening A* search \n",
        "```\n",
        "\n",
        "The cutoff is f-cost (g + h), rather than depth this time. It is the smalled f \\\n",
        "cost of any node that exceeded the cutoff in the previous iteration. \n",
        "\n",
        "**Recursive best first search** does best first search in linear space. Keeps \\\n",
        "track of the best f-value for alternate paths available from any ancestor of \\\n",
        "curr node. If any node exceeds this, the recursion bubbles back up and replaces \\\n",
        "the other f values with the backed up value along the way.  \n",
        "\n",
        "- optimal if h(n) is admissible \n",
        "\n",
        "**memory bounded A star** and simplified MBAstar. It does regular A star until\\\n",
        " memory is full, then drops the worst node(highest f) to add a new one. Also \\\n",
        " backs up the value of f for that worst node. For ties, we expand the newest \\\n",
        " and delete the oldest. \n",
        "\n",
        "SMBA star is complete if there is a reachable solution (if d is less than memory size) \\\n",
        "\n",
        "\"\"\"\n",
        "chapter3_6 = \"\"\" **Effective branching structure**, \n",
        "```\n",
        "b* - way to qualify a heuristic \n",
        "```\n",
        "\n",
        "N - total number of nodes generated by A* \n",
        "d - solution depth \n",
        "\n",
        "\n",
        "$N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d$\n",
        "\n",
        "Good heuristics have a branching factor close to 1 \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" **Greedy Best-first** \n",
        "- Select node with minimal h(n) = f(n), completely ignore g(n) \n",
        "\n",
        "- like UCS but f(n) replaces path cost (g(n)) \n",
        "\n",
        "- Priority queue \n",
        "\n",
        "- not optimal \n",
        "\n",
        "- not complete (can get stuck in loops) \n",
        "\n",
        "- O(|V|) time and space (but can be reduced to O(bm))\n",
        "\n",
        "```\n",
        "frontier = Priorityqueue() \n",
        "frontier.put(start, 0) \n",
        "came_from={}\n",
        "came_from[start] = None\n",
        "\n",
        "while !frontier.empty: \n",
        "    current = frontier.get()\n",
        "\n",
        "    if current == goal: \n",
        "      break\n",
        "    for next in current.neighbours:\n",
        "      if next not in came_from:\n",
        "        came_from[next] = current\n",
        "        priority = heuristic(next,goal)\n",
        "        frontier.put(next, priority)\n",
        "```\n",
        "\n",
        "**Manhattan distance** heuristic for a grid: \n",
        "\n",
        "- admissible \n",
        "\n",
        "```\n",
        "return abs(a.x -b.x) +  abs(a.y - b.y) \n",
        "```\n",
        "\n",
        "- can use straight line distance also\n",
        "\n",
        "Euclidean distance vs Manhattan distance  (?) \n",
        "\n",
        "\n",
        "```\n",
        "A* Search\n",
        "```\n",
        "\n",
        "- expand with minimal f(n) = g(n) + h(n) \n",
        "\n",
        "- h(n) must be admissible/optimistic \n",
        "\n",
        "- Priority queue \n",
        "\n",
        "- stop when goal node is expanded (ie top of priority queue) \n",
        "\n",
        "- optimal, complete, optimally efficient \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"heuristic function\" : \"h(n). gives an estimate of distance to goal from state s\\\n",
        "at node n\",   \n",
        "\"g(n)\": \"path cost\",\n",
        "\"admissible heuristic\" : \"will never overestimate cost to goal\",\n",
        "\"dominance\" : \"h2 dominates h1 if for all n h2(n) >= h1(n). h2 is better because\\\n",
        "it is optimistic, but a better estimate\",\n",
        "\"pruning\" : \"eliminating/not examining unlikely possibilites\",\n",
        "\"satisficing solutions\": \"using an inadmissible heuristic that may be more accurate,\\\n",
        " but risk missing the optimal solution. Less nodes expanded\",\n",
        " \"bounded suboptimal search\" : \"solution guaranteed to be within a constant\\\n",
        "factor, W, of the optimal cost\",\n",
        "\"bounded-cost search\" : \"solution has cost less than some constant C\",\n",
        "\"unbounded cost search\" :\"accept a solution of any cost, quickly\",\n",
        " \"optimally efficient\" : \"expanding min # of nodes to get an optimal solution\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 285,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "c997c569-b8b6-4d4c-83d1-c966c7f956b2"
      },
      "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": 286,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n **Consistency** \n\nh(n) <= c(n,a,n')+ h*(n') \n\nEvery consistent heuristic is admissible, but not the other way around \n\nif the optimal solution has cost C* and the second best, C2, then A* returns thecost-optimal solution is h(n) never overestimates the cost by more than C2-C*.\n\nif h(n) is admissible for all nodes on the path, A* returns a cost-optimal sol regardless of other nodes. \n\n Along the path, g(n) is strictly monotonic(increasing). So, contours of the  state space don't overlap. If h(n) is consistent, f(n) (=g +h)is monotonic too.\n\nAll nodes where f(n) < C* are **surely expanded nodes** \n\nno nodes with f(n) > C* will be expanded, but some with f(n) = C* \n\n\nWeighted A search \n \nExpands nodes with weighted heuristic value: \n\nf(n) = g(n) + W * h(n) for some W > 1 \n\n**Speedy search**- unbounded-cost search alg. Type of Greedy best-first search,where h(n) is the num steps to goal, regardless of cost. Same as GBFS when weights are uniform, but potentially faster otherwise. \n\n **Beam search** - incomplete and suboptimal but better for memory, because  frontier is bounded. So keep best k nodes, discarding others. \n  Alternative- keep track of nodes within delta of the best f-store node. all   strong candidates kept, weak ones discarded. \n\n```\nIterative-deepening A* search \n```\n\nThe cutoff is f-cost (g + h), rather than depth this time. It is the smalled f cost of any node that exceeded the cutoff in the previous iteration. \n\n**Recursive best first search** does best first search in linear space. Keeps track of the best f-value for alternate paths available from any ancestor of curr node. If any node exceeds this, the recursion bubbles back up and replaces the other f values with the backed up value along the way.  \n\n- optimal if h(n) is admissible \n\n**memory bounded A star** and simplified MBAstar. It does regular A star until memory is full, then drops the worst node(highest f) to add a new one. Also  backs up the value of f for that worst node. For ties, we expand the newest  and delete the oldest. \n\nSMBA star is complete if there is a reachable solution (if d is less than memory size) \n\n\n## AIMA Chapter 3.6 Heuristic Functions\n **Effective branching structure**, \n```\nb* - way to qualify a heuristic \n```\n\nN - total number of nodes generated by A* \nd - solution depth \n\n\n$N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d$\n\nGood heuristics have a branching factor close to 1 \n\n\n\n## Module 4 Lecture Notes\n **Greedy Best-first** \n- Select node with minimal h(n) = f(n), completely ignore g(n) \n\n- like UCS but f(n) replaces path cost (g(n)) \n\n- Priority queue \n\n- not optimal \n\n- not complete (can get stuck in loops) \n\n- O(|V|) time and space (but can be reduced to O(bm))\n\n```\nfrontier = Priorityqueue() \nfrontier.put(start, 0) \ncame_from={}\ncame_from[start] = None\n\nwhile !frontier.empty: \n    current = frontier.get()\n\n    if current == goal: \n      break\n    for next in current.neighbours:\n      if next not in came_from:\n        came_from[next] = current\n        priority = heuristic(next,goal)\n        frontier.put(next, priority)\n```\n\n**Manhattan distance** heuristic for a grid: \n\n- admissible \n\n```\nreturn abs(a.x -b.x) +  abs(a.y - b.y) \n```\n\n- can use straight line distance also\n\nEuclidean distance vs Manhattan distance  (?) \n\n\n```\nA* Search\n```\n\n- expand with minimal f(n) = g(n) + h(n) \n\n- h(n) must be admissible/optimistic \n\n- Priority queue \n\n- stop when goal node is expanded (ie top of priority queue) \n\n- optimal, complete, optimally efficient \n\n \n\n## Module 4 Definitions\n* **Heuristic function** - h(n). gives an estimate of distance to goal from state sat node n\n* **G(n)** - path cost\n* **Admissible heuristic** - will never overestimate cost to goal\n* **Dominance** - h2 dominates h1 if for all n h2(n) >= h1(n). h2 is better becauseit is optimistic, but a better estimate\n* **Pruning** - eliminating/not examining unlikely possibilites\n* **Satisficing solutions** - using an inadmissible heuristic that may be more accurate, but risk missing the optimal solution. Less nodes expanded\n* **Bounded suboptimal search** - solution guaranteed to be within a constantfactor, W, of the optimal cost\n* **Bounded-cost search** - solution has cost less than some constant C\n* **Unbounded cost search** - accept a solution of any cost, quickly\n* **Optimally efficient** - ?\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" \n",
        "\n",
        "**Minimax search**  \n",
        "\n",
        "O(b^m) time where b= legal moves at each point, m = max depth of tree \n",
        "\n",
        "O(bm) space if actions generated all at once, O(m) if 1 by 1 \n",
        "\n",
        "**Minimax value-** max's utility of being in that state, \\\n",
        "assuming that both players played optimally. Terminal nodes minmax value is just\\\n",
        "their utility. For non-terminal nodes, max chooses the highest possible value, min\\\n",
        "chooses the lowest one (from max's perspective)  \n",
        "\n",
        "\n",
        "**minimax decision**- minimax value of root \n",
        "\n",
        "```\n",
        "function minimax-search(game, state) returns an action  \n",
        "player = #whose play it is\n",
        "value, move = max_value(game, state) \n",
        "return move\n",
        "\n",
        "function max-value(game, state) returns (utility, move)\n",
        "if game is in winning state, return game.utility(state, player), null\n",
        "v = -infinity\n",
        "move = null\n",
        "\n",
        "for every action in game.state.possible_actions: \n",
        "  v2, a2 = min-value(game, game.Result(a, state))\n",
        "  if v2 > v,\n",
        "    v, move = v2, a\n",
        "return v, move\n",
        "\n",
        "#analogous for min \n",
        "``` \n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" \n",
        "\n",
        "\n",
        "**alpha** - best value for max, ie lower bound on max's outcome \"at least\"\n",
        "\n",
        "**beta**- best value for min, ie upeer bound on min's outcome \"at most\"\n",
        "\n",
        "Stop evaluating when max finds a value > beta, or when min finds a value < alpha \n",
        "\n",
        "**alpha-beta search** \n",
        "\n",
        "```\n",
        "function ab(game, state) returns an action  \n",
        "player = #whose play it is\n",
        "value, move = max_value(game, state, -inf, +inf) \n",
        "return move\n",
        "\n",
        "function max-value(game, state, alpha, beta) returns (utility, move)\n",
        "if game is in winning state, return game.utility(state, player), null\n",
        "v = -infinity\n",
        "move = null\n",
        "\n",
        "for every action in game.state.possible_actions: \n",
        "  v2, a2 = min-value(game, game.Result(a, state), alpha, beta)\n",
        "  if v2 > v,\n",
        "    v, move = v2, a\n",
        "    alpha = max(alpha, v)\n",
        "  if v >= beta then return v, move\n",
        "return v, move\n",
        "\n",
        "#analogous for min \n",
        "``` \n",
        "\n",
        "Since the ordering of the nodes matter for ab search, if we can acheive near- \\\n",
        "perfect ordering, we could do O(b^{m/2}). b is now sqrt(b) \n",
        "\n",
        "With random ordering- O(b^{3m/4}) \n",
        "\n",
        "**killer move heuristic** - trying killer/best moves first\n",
        " \"\"\"\n",
        "chapter5_3 = \"\"\" Stop search early and apply an **evalutation function** ie. \\\n",
        "estimating utility for nonterminal states. Introduce **cutoff test** which \\\n",
        "includes all terminal nodes by default, but will search up to depth d \n",
        "\n",
        "One possible evaluation function- getting the **expected value** \n",
        "\n",
        "prob * cost \n",
        "\n",
        "chess eg (0.82 * +1) + (0.02 * 0) + (0.16 * 1/2) = 0.9 \n",
        "\n",
        "**Weighted linear function** because that^ is too hard in practice. \n",
        "\n",
        "**EVAL(s)** = $w_1 f_1(s)$ + ... + $w_n_ f_n$\n",
        "fi- feature of position (like number of black pawns), w is weight(importance of \\\n",
        "feature, range from 0(loss) to 1(win))  \n",
        "This assumes that the feature is independent of the value for other features, \\\n",
        "which is usually not the case. \n",
        "\n",
        "\n",
        "Evaluation function needs to be strongly correlated with chances of winning, but\\\n",
        " not necessarily linearly. \n",
        " \n",
        " \n",
        " **forward pruning** prunes moves that appear to be bad, but could potentially \\\n",
        " be good ones. Saves time at risk of making an error \n",
        " \n",
        " **probcut**- probabilistic cut. uses prior experience and stats to tell you \\\n",
        " nodes that a re probably outside the (alpha, beta) window. Lessens the chance \\\n",
        " that the best move will be pruned. It does a shallow search to calculate v, \\\n",
        " then determines the likelihood of  v at d, being outside (a,b) \n",
        " \n",
        " **late move reduction** assumes that we have a good ordering of moves and limits\\\n",
        "  the depths of later moves (not eliminate them completely)  \"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\" Games involving chance. E.g. backgammon \n",
        "\n",
        "Search tree now contains chance nodes (bc don't know what will happen next if it \\\n",
        "is based on a die roll). For this, P. 1/36 for double die rolls and 1/18 for \\\n",
        "distinct ones. Note 5-6 = 6-5. \n",
        "\n",
        "**expectiminimax** - a generalization of minimax. Regular nodes work the same. \\\n",
        "For chance nodes, we calculate the **expected value** => sum of value over all \\\n",
        "outcomes, weighted by probability of that action. \n",
        "\n",
        "**O(b^m n^m)** time where n is the number of distinct rolls\n",
        "\n",
        "In chance games, eval function must return values that are a  **positive linear \\\n",
        "transformation** of the probability(win-lose) or the expected utility(not zero sum) \n",
        " \n",
        " \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" **decision-theoretic agent** chooses based on beliefs and wants \\\n",
        "\n",
        "Rather than binary states, states have a continuous range of values.. so you can \\\n",
        "easily choose a better choice when there is no best. \n",
        "\n",
        "If there is uncertainty about states, and possible actions then P(s'|s,a) is the \\\n",
        "probability of reaching state s' after applying a in s. \n",
        "\n",
        "P(Result(a) == s') is the outcome we care about. \n",
        "\n",
        "P(Result(a) == s') =  Sum for all possible actions, P(a)P(s'|s,a) \n",
        "\n",
        "**MEU** maximizes the average utility. \n",
        "\n",
        "The utility function guides agents step by step. It applies to the **next** state. \\\n",
        "Meanwhile, the performance measure is external and applies to history/a sequence \\\n",
        "of steps.  \n",
        "\n",
        "if an agent acts to maximize a utility fucntion that reflects the performance \\\n",
        "measure, then the agent will acheieve the highest possible performance score, \\\n",
        "averaged over all the environments. \n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" **Lottery** the set of all possible outcomes(each w their own) \\\n",
        "probabilities. \n",
        "\n",
        "**Constraints for Preference Relation:** \n",
        "\n",
        "**Orderability**- agent has to choose and cannot avoid deciding. Decide on a or\\\n",
        " b or both \n",
        "\n",
        "**Transitivity**- if A > B and B > C, then A > C \n",
        "\n",
        "**Continuity**- if Pr(A) = p, then Pr(B) =  1 - p \n",
        "\n",
        "**Substitutability**- If an agent is indifferent to A and B, then the agent is \\\n",
        "indifferent to lotteries that essentially the same, except you substitute between \\\n",
        "A/B. A ~ B => [p, A; 1- P, C] ~ [p, B; 1- P, C]  \n",
        "\n",
        "**Monotonicity**- If 2 lotteries have the same possible outcomes, A and B, then \\\n",
        "if the agent prefers A, then the agent must prefer the. lottery that has a higher \\\n",
        "probability for A. \n",
        "\n",
        "**Decomposaibility**- Use probability rules to simplify compound lotteries \\\n",
        "[p, A; 1 - p, [q:B, 1-q,C]] ~ [p, A; q(1-p),B; (1-q)(1-p), C] \n",
        "\n",
        "If an agent follows the above axioms, then: \n",
        "\n",
        "- There is a utility function, U, such that U(A) > U(B) iff the agent prefers A \\\n",
        "and U(A) = U(B) if the agent is indifferent \n",
        "\n",
        "The expected utility of a lottery is the sum of the probability of each outcome \\\n",
        "times the utility of that outcome. \n",
        "\n",
        "Thus, a utility function exists for any rational agent, but they are not necessarily \\\n",
        "unique.\n",
        "\n",
        "**value function or ordinal utility function**- using a preference ranking on states \\\n",
        "(actual values don't matter) \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" Utility functions map from lotteries to real numbers. \n",
        "\n",
        "To build a **decision-theoretic system** \n",
        "\n",
        "**preference elucidation**- presenting many choices to human and determining \\\n",
        "underlying utility function from observed preferences \n",
        "\n",
        "**Normalize utilities**- ie give them a scale by giving best and worst case their \\\n",
        "values \n",
        "\n",
        "You can then assess the utility of S by comparing to the range of values in the \\\n",
        "standard lottery (ie given the bounds generated above). The first value of \\\n",
        "indifference is the utility. \n",
        "\n",
        "**Normative theory**- describes how an agent should act \n",
        "\n",
        "**Descriptive theory**- describes how the act actually acts \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" \n",
        "\n",
        "games are **multi agent** \n",
        "simplest game environment: multiagent, static, discrete, fully-observable, \\\n",
        "strategic(ie next state is determines by curr state and actions ofagents) \n",
        "\n",
        "zero-sum, clear set of legal moves, two players alternate moves, well-defined \n",
        "outcome (ie win, lose, draw) \n",
        "\n",
        "**egocentric POV** ie even levels = max, odd = min \n",
        "\n",
        "expectimax- average score, assuming optimal play\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"ply\" : \"one action by one player (1 level deeper in tree) (move can mean both\\\n",
        " players did something)\",    \n",
        " \"type A strategy\" : \"wide but shallow, see all nodes up to a certain depth. \\\n",
        " Chess\",\n",
        " \"type B strategy\" : \"deep but narrow, follow promising moves as far down as \\\n",
        " possible. GO, since b is much higher \",\n",
        " \"quiescent state\" : \"there is no pending move (like capturing the queen\",\n",
        " \"policy\" : \"mapping of each state to the best possible move in that state\",\n",
        " \"random variable\" : \"event whose outcome is unknown\",\n",
        " \"probability distribution\" : \"asdignment of weights to outcomes\",  \n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 287,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "1739f612-4008-417e-c447-5ad0f810a36d"
      },
      "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": 288,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \n\n**Minimax search**  \n\nO(b^m) time where b= legal moves at each point, m = max depth of tree \n\nO(bm) space if actions generated all at once, O(m) if 1 by 1 \n\n**Minimax value-** max's utility of being in that state, assuming that both players played optimally. Terminal nodes minmax value is justtheir utility. For non-terminal nodes, max chooses the highest possible value, minchooses the lowest one (from max's perspective)  \n\n\n**minimax decision**- minimax value of root \n\n```\nfunction minimax-search(game, state) returns an action  \nplayer = #whose play it is\nvalue, move = max_value(game, state) \nreturn move\n\nfunction max-value(game, state) returns (utility, move)\nif game is in winning state, return game.utility(state, player), null\nv = -infinity\nmove = null\n\nfor every action in game.state.possible_actions: \n  v2, a2 = min-value(game, game.Result(a, state))\n  if v2 > v,\n    v, move = v2, a\nreturn v, move\n\n#analogous for min \n``` \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n\n\n**alpha** - best value for max, ie lower bound on max's outcome \"at least\"\n\n**beta**- best value for min, ie upeer bound on min's outcome \"at most\"\n\nStop evaluating when max finds a value > beta, or when min finds a value < alpha \n\n**alpha-beta search** \n\n```\nfunction ab(game, state) returns an action  \nplayer = #whose play it is\nvalue, move = max_value(game, state, -inf, +inf) \nreturn move\n\nfunction max-value(game, state, alpha, beta) returns (utility, move)\nif game is in winning state, return game.utility(state, player), null\nv = -infinity\nmove = null\n\nfor every action in game.state.possible_actions: \n  v2, a2 = min-value(game, game.Result(a, state), alpha, beta)\n  if v2 > v,\n    v, move = v2, a\n    alpha = max(alpha, v)\n  if v >= beta then return v, move\nreturn v, move\n\n#analogous for min \n``` \n\nSince the ordering of the nodes matter for ab search, if we can acheive near- perfect ordering, we could do O(b^{m/2}). b is now sqrt(b) \n\nWith random ordering- O(b^{3m/4}) \n\n**killer move heuristic** - trying killer/best moves first\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Stop search early and apply an **evalutation function** ie. estimating utility for nonterminal states. Introduce **cutoff test** which includes all terminal nodes by default, but will search up to depth d \n\nOne possible evaluation function- getting the **expected value** \n\nprob * cost \n\nchess eg (0.82 * +1) + (0.02 * 0) + (0.16 * 1/2) = 0.9 \n\n**Weighted linear function** because that^ is too hard in practice. \n\n**EVAL(s)** = $w_1 f_1(s)$ + ... + $w_n_ f_n$\nfi- feature of position (like number of black pawns), w is weight(importance of feature, range from 0(loss) to 1(win))  \nThis assumes that the feature is independent of the value for other features, which is usually not the case. \n\n\nEvaluation function needs to be strongly correlated with chances of winning, but not necessarily linearly. \n \n \n **forward pruning** prunes moves that appear to be bad, but could potentially  be good ones. Saves time at risk of making an error \n \n **probcut**- probabilistic cut. uses prior experience and stats to tell you  nodes that a re probably outside the (alpha, beta) window. Lessens the chance  that the best move will be pruned. It does a shallow search to calculate v,  then determines the likelihood of  v at d, being outside (a,b) \n \n **late move reduction** assumes that we have a good ordering of moves and limits  the depths of later moves (not eliminate them completely)  \n\n## AIMA Chapter 5.5 Stochastic Games\n Games involving chance. E.g. backgammon \n\nSearch tree now contains chance nodes (bc don't know what will happen next if it is based on a die roll). For this, P. 1/36 for double die rolls and 1/18 for distinct ones. Note 5-6 = 6-5. \n\n**expectiminimax** - a generalization of minimax. Regular nodes work the same. For chance nodes, we calculate the **expected value** => sum of value over all outcomes, weighted by probability of that action. \n\n**O(b^m n^m)** time where n is the number of distinct rolls\n\nIn chance games, eval function must return values that are a  **positive linear transformation** of the probability(win-lose) or the expected utility(not zero sum) \n \n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n **decision-theoretic agent** chooses based on beliefs and wants \nRather than binary states, states have a continuous range of values.. so you can easily choose a better choice when there is no best. \n\nIf there is uncertainty about states, and possible actions then P(s'|s,a) is the probability of reaching state s' after applying a in s. \n\nP(Result(a) == s') is the outcome we care about. \n\nP(Result(a) == s') =  Sum for all possible actions, P(a)P(s'|s,a) \n\n**MEU** maximizes the average utility. \n\nThe utility function guides agents step by step. It applies to the **next** state. Meanwhile, the performance measure is external and applies to history/a sequence of steps.  \n\nif an agent acts to maximize a utility fucntion that reflects the performance measure, then the agent will acheieve the highest possible performance score, averaged over all the environments. \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n **Lottery** the set of all possible outcomes(each w their own) probabilities. \n\n**Constraints for Preference Relation:** \n\n**Orderability**- agent has to choose and cannot avoid deciding. Decide on a or b or both \n\n**Transitivity**- if A > B and B > C, then A > C \n\n**Continuity**- if Pr(A) = p, then Pr(B) =  1 - p \n\n**Substitutability**- If an agent is indifferent to A and B, then the agent is indifferent to lotteries that essentially the same, except you substitute between A/B. A ~ B => [p, A; 1- P, C] ~ [p, B; 1- P, C]  \n\n**Monotonicity**- If 2 lotteries have the same possible outcomes, A and B, then if the agent prefers A, then the agent must prefer the. lottery that has a higher probability for A. \n\n**Decomposaibility**- Use probability rules to simplify compound lotteries [p, A; 1 - p, [q:B, 1-q,C]] ~ [p, A; q(1-p),B; (1-q)(1-p), C] \n\nIf an agent follows the above axioms, then: \n\n- There is a utility function, U, such that U(A) > U(B) iff the agent prefers A and U(A) = U(B) if the agent is indifferent \n\nThe expected utility of a lottery is the sum of the probability of each outcome times the utility of that outcome. \n\nThus, a utility function exists for any rational agent, but they are not necessarily unique.\n\n**value function or ordinal utility function**- using a preference ranking on states (actual values don't matter) \n\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions map from lotteries to real numbers. \n\nTo build a **decision-theoretic system** \n\n**preference elucidation**- presenting many choices to human and determining underlying utility function from observed preferences \n\n**Normalize utilities**- ie give them a scale by giving best and worst case their values \n\nYou can then assess the utility of S by comparing to the range of values in the standard lottery (ie given the bounds generated above). The first value of indifference is the utility. \n\n**Normative theory**- describes how an agent should act \n\n**Descriptive theory**- describes how the act actually acts \n\n## Module 5 Lecture Notes\n \n\ngames are **multi agent** \nsimplest game environment: multiagent, static, discrete, fully-observable, strategic(ie next state is determines by curr state and actions ofagents) \n\nzero-sum, clear set of legal moves, two players alternate moves, well-defined \noutcome (ie win, lose, draw) \n\n**egocentric POV** ie even levels = max, odd = min \n\nexpectimax- average score, assuming optimal play\n\n\n\n\n## Module 5 Definitions\n* **Ply** - one action by one player (1 level deeper in tree) (move can mean both players did something)\n* **Type a strategy** - wide but shallow, see all nodes up to a certain depth.  Chess\n* **Type b strategy** - deep but narrow, follow promising moves as far down as  possible. GO, since b is much higher \n* **Quiescent state** - there is no pending move (like capturing the queen\n* **Policy** - mapping of each state to the best possible move in that state\n* **Random variable** - event whose outcome is unknown\n* **Probability distribution** - asdignment of weights to outcomes\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "a5311f5b-f5a2-4f1f-c0e1-ed31eb5df338"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" **CSP Problem**- each state is a set of variables with their own \\\n",
        "values. The problem is solved when all variables have a value that satisfies constraints\n",
        "\n",
        "- use general, rather than domain specific heuristics \n",
        "\n",
        "More formally: \n",
        "- X is the set of variables, {X_1, ..., X_n}  \n",
        "\n",
        "- D is the set of domains, {D_1, ..., D_n}, one for each variable \n",
        "\n",
        "- C is the set of contraints that specify allowable combinations of values in the \\\n",
        "form of <scope, rel>. e.g. <(X1, X2),{(3,2), (3,1), (2,1)}> or <(X1, X2), X1 > X2> \n",
        "\n",
        "e.g. D_1 has the set of allowable values {v_1, ..., v_k} for variable X_1 \n",
        "\n",
        "Solving a CSP involves values to variables. It is NP-Complete \n",
        "\n",
        "**constraint graph** represents variables as nodes and constraints as edges between \\\n",
        "them \n",
        "\n",
        "simplest CSP- discrete, finite domains \n",
        "\n",
        "**unary constraint**- restricts the value of a single day \n",
        "\n",
        "**binary constraint**- relates 2 variables \n",
        "\n",
        "**binary CSP** can be respresented as a constraint graph. It has only unary and \\\n",
        "binary constraints \n",
        "\n",
        "**global constraint**_ involves an arbitrary amount of variables (does NOT need \\\n",
        "to include all) aka **higher order constraint** \n",
        "\n",
        "\n",
        "**preference constraints** allow you to indicate preferred solution, unlike \\\n",
        "**absolute** which is exactly what it sounds like. \n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "\n",
        "**AC-3 Enforces arc consistency** \n",
        "- O(d^2) time to check the consistency of an arc, so total O(cd^3) worst-case \\\n",
        "for a CSP with n variables and domain size at most d and c binary constraints. \\\n",
        "If there are n nodes, then it's O(n^2d^3), since each node can be connected to \\\n",
        "every other node (ie O(n^2) nodes). Checking one arc takes O(d^2) time, and each \\\n",
        "arc can be inserted into the q up to d times.\n",
        "\n",
        "- for planar constraints, we get O(nd^3)  (bc number of arcs is linear wrt n)\n",
        "\n",
        "- maintain queue of arcs (initially all) -> each constraint is 2 arcs, 1 in each \\\n",
        "direction \n",
        "\n",
        "- pops an arc from queue randomly and then makes it arc consisdent. If this  \\\n",
        "doesn't change D, then move on. if D is different, then add all the arcs (Xk, Xi) \\\n",
        "\n",
        "If Di is revised to nothing, return failure bc inconsistent. Keep going until \\\n",
        "loop is done running, then the output will be the arc consistent version of the \\\n",
        "graph \n",
        "\n",
        "Arc consistency tightens down the domains(unary constraints) using the arcs \\\n",
        "(binary contraints) \n",
        "\n",
        "\n",
        "**path consistency** tightens the binary constraints by using implicit constraints \\\n",
        "that are inferred by looking at 3 variables at a time. So {Xi, Xj} is path \\\n",
        "consistent wrt Xm if for every assignment for Xi and Xj (that satisfy their \\\n",
        "own constraints), there is also an assignment for Xm, that satisfies \\\n",
        "{Xi, Xm} and {Xm, Xj} [3-consistency, for binary constraint graphs]\n",
        "\n",
        "a CSP is **k-consistent** if for any set of k - 1 vriables, a consistent value \\\n",
        "can always be assigned to any kth variable. \n",
        "\n",
        "a CSP is **strongly k-consistent** if it is k consistent, k -1 consistent, k - 2 \\\n",
        "consistent... and 1 consistent. Solve by assigning variables in order: since \\\n",
        "an answer is guarantied. For each variable Xij,  we only need to search d values \\\n",
        "in the domain to find a value consistent with X_1 ... X_{i-1}. Runtime O(n^2d)\n",
        "\n",
        "```\n",
        "function AC3 returns false(inconsistent) or true(consistent)\n",
        "queue = all arcs in csp\n",
        "\n",
        "while !queue.empty():\n",
        "    (Xi, Xj) = queue.pop()\n",
        "    if revise(csp, Xi, Xj) then\n",
        "      if size Di = 0 return false\n",
        "      else, for each Xk in {neighbours(Xi) - Xj}: \n",
        "          add(Xk, Xi) to the queue\n",
        "return true \n",
        "\n",
        "\n",
        "function review(csp, Xi, Xj) return true iff we revise the domain of Xi \n",
        "  revised = false\n",
        "  for each x in Di do\n",
        "  if no value y in Dj allows (x,y) to satisfy the constraint between Xi and Xy,\n",
        "  then delete x from Di\n",
        "    revised = true\n",
        "  return revised\n",
        "\n",
        "```\n",
        "\n",
        "for Alldiff, for m variables with n distinct states, if m > n, then the constraint \\\n",
        "cannot be satisfied \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter6_3 = \"\"\" **Backtracking search** is helpful for particial solutions from \\\n",
        "AC-3, where you still need to find the optimal solution. Tree has  d^n leaves, \\\n",
        "once you recognize commutativity. so it is a DFS with single varriable assignments \n",
        "\n",
        "\n",
        "```\n",
        "function Backtracking-search(csp) returns solution or failure \n",
        "  return backtrack(csp, {}) \n",
        "\n",
        "function backtrack(csp, assignment) returns solution or failure \n",
        "if assignment is complete then return assignment\n",
        "var = select unassigned variable \n",
        "\n",
        "for each value in domainVals(csp, var, assignemnt): \n",
        "    if value is consistent with assignment then: \n",
        "      add {var = value} to assignemnt \n",
        "      inferences = inference(csp, var, assignment) \n",
        "      if inferences !failure then: \n",
        "        add inferences to csp\n",
        "        result = backtrack(csp, assignemnt) \n",
        "        if result !failure then return result\n",
        "          remove inferences from csp \n",
        "          remove {var = value} from assignment\n",
        "return failure \n",
        "```\n",
        "\n",
        "**Domain independent heuristics for backtracking search** \n",
        "-  Order of assigning variables and values. simplest- in order, randomly. Best \\\n",
        "option- choose variable with fewest \"legal\" values. ie. **minimum-remaining-values\\\n",
        " heuristic** \n",
        "\n",
        " **degree heuristic** attempts to reduce branching factor on future choices by \\\n",
        " selecting the variable that i involved in the largest number of constraints \\\n",
        " on other unassigned variables \n",
        "\n",
        "\n",
        " **least constraining value heuristic** prefers the value that rules out the \\\n",
        " fewest choices for the neighbours \n",
        "\n",
        "\n",
        "**Inference** e.g. helps to reduce domains during search \n",
        "\n",
        "**Forwards-checking** is making a variable arc consistent when it is assigned. So \\\n",
        "we keep track of possible values for all vars. If any unassigned vars has no \\\n",
        "more possible values, then terminate \n",
        "\n",
        "\n",
        "**maintaining arc consistency** detects inconsistencies in assignment. After a \\\n",
        "variable is assigned, INFERENCE procedure uses AC3 with a queue of all the arcs \\\n",
        "(Xj, Xi) for the Xi we assigned all its unassigned neighbours Xj. If constraint \\\n",
        "propagation (done by AC3) gives us an empty set, then we backtrack immediately. \n",
        "\n",
        "MAC is more powerful than AC3 because it does the same checking, but also recursively \\\n",
        "propagates constraints when the domain variables change \n",
        "\n",
        "**backjumping** backtracks to the most recent assignment when a conflic is found. \\\n",
        "It finds the exact solution as forward tracking.\n",
        "\n",
        "**constraint learning** is finding a minimum set of variables from the conflict \\\n",
        "set that causes a problem. The variables and their corresponding values form a \\\n",
        "**no good** and we can record them (by adding a new constraint, or keep track in \\\n",
        "memory) and reference, to avoid that combination in the future \n",
        " \"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\" **local search** can solve many CSPs. Each state assigns a  \\\n",
        "value to every variable and then the search changes the value of one variable at \\\n",
        "a time. \n",
        "\n",
        "**min conflicts heuristic** changes the value of the one with the least conflicts \n",
        "\n",
        "```function minConflicts(csp, max_steps) returns solution or failure \n",
        "max steps = num steps before giving up\n",
        "\n",
        "current = an initial complete assignment of CSP\n",
        "\n",
        "for i = 1 to max_steps: \n",
        "  if current is a solution for csp then return current \n",
        "  var = a conflicted variable from cspvairables\n",
        "  value = the value for var that minimizes its conflicts\n",
        "  set var = value in current \n",
        "return failure \n",
        "```\n",
        "\n",
        "**constraint weighting** aims to concentrate on the important constraints by giving \\\n",
        "each one a weight. At each step of the search, choose a value/variable pair that \\\n",
        "gives the lowest weight for all violated constraints. Then, adjust the weights \\\n",
        "by incrementing the weight of each contraint violated by this assigment \n",
        "\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\" Create independent subproblems -> find connected components of \\\n",
        "the constraint graph. Each one is a subproblem. -> greatly reduces runtime \n",
        "\n",
        "to ~ O(d^n) \n",
        "\n",
        "any tree CSP can be solved linearly in the number of variables \n",
        "\n",
        "a CSP is **directionally arc consistent** under an ordering of variables X1, X2, \\\n",
        "..., Xn iff Xi is arc-consistent with each Xj for j > i \n",
        "\n",
        "Can reduce constraint graph by:  \n",
        "**cutset conditioning** where you assign some values so the remaining ones form \\\n",
        "a tree \n",
        "\n",
        "**tree conditioning** creates a tree from the graph, where each node is a set of \\\n",
        "variables. if two variables are connected by a constraint, they're in the same \\\n",
        "node of the tree. If a varaible appears in 2 tree nodes, it appears all along \\\n",
        "the path connecting those nodes \n",
        "\n",
        "Tree CSP solves in O(nd^2) time \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" \n",
        "\n",
        "**constraint propagation**- using the constraints to reduce \\\n",
        "num possible values for the next var, which does that for the next var and so \\\n",
        "on. It enforces constraints locally\n",
        "\n",
        "a variable is **node consistent** if all its domain values satisfy the unary \\\n",
        "constraints and a graph is node consistent if all its variables are [1 consistent]\n",
        "\n",
        "a variable is **arc consistent** if every value satisfies the binary constraints \n",
        "a graph is arc consistent if every variable is arc consistent with every other \\\n",
        "variable [2-consistent]\n",
        "\n",
        "CSPs are specialized for identification problems. \n",
        "\n",
        "**discrete variables**: \n",
        "finite domains: n vars, O(d^n) complete assignments w domain d \n",
        "infinite domains: like scheduling jobs (vars for start and end of each job) \n",
        "\n",
        "**Continuous variables** -> e.g. start and end time for Hubble ST \n",
        "\n",
        "Can express a CSP as a search problem: \n",
        "\n",
        "- initial state: {} empty assignment \n",
        "\n",
        "- successor function: assign value to any unassigned var wo constraint conflict \n",
        "\n",
        "-goal test: see if assignment is complete \n",
        "\n",
        "- path cost: a constant cost per step \n",
        "\n",
        "A solution for n variables is always found at depth n, hence depth-first approach \n",
        "\n",
        "for n variables and domain size d, branching factor = n*d, \n",
        "\n",
        "num leaves= d^n (given commutativity) \n",
        "\n",
        "**heuristic order:** \n",
        "- choose most contrained variable (fewest value options) \n",
        "- if tie, choose most contrinaing variable (imposes most constraints) \n",
        "- then, for values, choose least contraining. \n",
        "\n",
        "**Constraint propagation** is an inference technique that eliminates values if \\\n",
        "they violate local consistency \n",
        "\n",
        "\n",
        "from constraint graph to directed graph -> now nodes are joined by two edges, going \\\n",
        "opposite ways. Simplest form of propagation enforces arc consistency.\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"consistent assignment\" : \"assignment of value to variable that does not violate \\\n",
        "any constraints. aka legal assignment\",   \n",
        "\"complete assignment\" : \"one where every variable gets a value\",\n",
        "\"solution to a CSP\": \"consistent, complete assignment of values to vars\",\n",
        "\"partial assignment\" : \"one that leaves some variables unassigned\",\n",
        "\"partial solution\" : \"Partial assignment that is consistent\",\n",
        "\"conflict set for A\" : \"set of all the assignments in conflict with A\",\n",
        "\"tree width of a graph\" : \"1 less than the size of the largest node/ minimum \\\n",
        "width of all tree decompositions \", \n",
        "}\n"
      ],
      "execution_count": 310,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 259\n",
            "The length in characters is 1712\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "e95db955-f304-45e6-97b8-6919847528a4"
      },
      "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": 290,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n **CSP Problem**- each state is a set of variables with their own values. The problem is solved when all variables have a value that satisfies constraints\n\n- use general, rather than domain specific heuristics \n\nMore formally: \n- X is the set of variables, {X_1, ..., X_n}  \n\n- D is the set of domains, {D_1, ..., D_n}, one for each variable \n\n- C is the set of contraints that specify allowable combinations of values in the form of <scope, rel>. e.g. <(X1, X2),{(3,2), (3,1), (2,1)}> or <(X1, X2), X1 > X2> \n\ne.g. D_1 has the set of allowable values {v_1, ..., v_k} for variable X_1 \n\nSolving a CSP involves values to variables. It is NP-Complete \n\n**constraint graph** represents variables as nodes and constraints as edges between them \n\nsimplest CSP- discrete, finite domains \n\n**unary constraint**- restricts the value of a single day \n\n**binary constraint**- relates 2 variables \n\n**binary CSP** can be respresented as a constraint graph. It has only unary and binary constraints \n\n**global constraint**_ involves an arbitrary amount of variables (does NOT need to include all) aka **higher order constraint** \n\n\n**preference constraints** allow you to indicate preferred solution, unlike **absolute** which is exactly what it sounds like. \n\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n **constraint propagation**- using the constraints to reduce num possible values for the next var, which does that for the next var and so on. It enforces constraints locally\n\na variable is **node consistent** if all its domain values satisfy the unary constraints and a graph is node consistent if all its variables are [1 consistent]\n\na variable is **arc consistent** if every value satisfies the binary constraints \na graph is arc consistent if every variable is arc consistent with every other variable [2-consistent]\n\n**AC-3 Enforces arc consistency** \n- O(d^2) time to check the consistency of an arc, so total O(cd^3) worst-case for a CSP with n variables and domain size at most d and c binary constraints. If there are n nodes, then it's O(n^2d^3), since each node can be connected to every other node (ie O(n^2) nodes). Checking one arc takes O(d^2) time, and each arc can be inserted into the q up to d times.\n\n- maintain queue of arcs (initially all) -> each constraint is 2 arcs, 1 in each direction \n\n- pops an arc from queue randomly and then makes it arc consisdent. If this  doesn't change D, then move on. if D is different, then add all the arcs (Xk, Xi) \nIf Di is revised to nothing, return failure bc inconsistent. Keep going until loop is done running, then the output will be the arc consistent version of the graph \n\nArc consistency tightens down the domains(unary constraints) using the arcs (binary contraints) \n\n\n**path consistency** tightens the binary constraints by using implicit constraints that are inferred by looking at 3 variables at a time. So {Xi, Xj} is path consistent wrt Xm if for every assignment for Xi and Xj (that satisfy their own constraints), there is also an assignment for Xm, that satisfies {Xi, Xm} and {Xm, Xj} [3-consistency, for binary constraint graphs]\n\na CSP is **k-consistent** if for any set of k - 1 vriables, a consistent value can always be assigned to any kth variable. \n\na CSP is **strongly k-consistent** if it is k consistent, k -1 consistent, k - 2 consistent... and 1 consistent. Solve by assigning variables in order: since an answer is guarantied. For each variable Xij,  we only need to search d values in the domain to find a value consistent with X_1 ... X_{i-1}. Runtime O(n^2d)\n\n```\nfunction AC3 returns false(inconsistent) or true(consistent)\nqueue = all arcs in csp\n\nwhile !queue.empty():\n    (Xi, Xj) = queue.pop()\n    if revise(csp, Xi, Xj) then\n      if size Di = 0 return false\n      else, for each Xk in {neighbours(Xi) - Xj}: \n          add(Xk, Xi) to the queue\nreturn true \n\n\nfunction review(csp, Xi, Xj) return true iff we revise the domain of Xi \n  revised = false\n  for each x in Di do\n  if no value y in Dj allows (x,y) to satisfy the constraint between Xi and Xy,\n  then delete x from Di\n    revised = true\n  return revised\n\n```\n\nfor Alldiff, for m variables with n distinct states, if m > n, then the constraint cannot be satisfied \n\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n **Backtracking search** is helpful for particial solutions from AC-3, where you still need to find the optimal solution. Tree has  d^n leaves, once you recognize commutativity. so it is a DFS with single varriable assignments \n\n\n```\nfunction Backtracking-search(csp) returns solution or failure \n  return backtrack(csp, {}) \n\nfunction backtrack(csp, assignment) returns solution or failure \nif assignment is complete then return assignment\nvar = select unassigned variable \n\nfor each value in domainVals(csp, var, assignemnt): \n    if value is consistent with assignment then: \n      add {var = value} to assignemnt \n      inferences = inference(csp, var, assignment) \n      if inferences !failure then: \n        add inferences to csp\n        result = backtrack(csp, assignemnt) \n        if result !failure then return result\n          remove inferences from csp \n          remove {var = value} from assignment\nreturn failure \n```\n\n**Domain independent heuristics for backtracking search** \n-  Order of assigning variables and values. simplest- in order, randomly. Best option- choose variable with fewest \"legal\" values. ie. **minimum-remaining-values heuristic** \n\n **degree heuristic** attempts to reduce branching factor on future choices by  selecting the variable that i involved in the largest number of constraints  on other unassigned variables \n\n\n **least constraining value heuristic** prefers the value that rules out the  fewest choices for the neighbours \n\n\n**Inference** e.g. helps to reduce domains during search \n\n**Forwards-checking** is making a variable arc consistent when it is assigned. So we keep track of possible values for all vars. If any unassigned vars has no more possible values, then terminate \n\n\n**maintaining arc consistency** detects inconsistencies in assignment. After a variable is assigned, INFERENCE procedure uses AC3 with a queue of all the arcs (Xj, Xi) for the Xi we assigned all its unassigned neighbours Xj. If constraint propagation (done by AC3) gives us an empty set, then we backtrack immediately. \n\nMAC is more powerful than AC3 because it does the same checking, but also recursively propagates constraints when the domain variables change \n\n**backjumping** backtracks to the most recent assignment when a conflic is found. It finds the exact solution as forward tracking.\n\n**constraint learning** is finding a minimum set of variables from the conflict set that causes a problem. The variables and their corresponding values form a **no good** and we can record them (by adding a new constraint, or keep track in memory) and reference, to avoid that combination in the future \n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n **local search** can solve many CSPs. Each state assigns a  value to every variable and then the search changes the value of one variable at a time. \n\n**min conflicts heuristic** changes the value of the one with the least conflicts \n\n```function minConflicts(csp, max_steps) returns solution or failure \nmax steps = num steps before giving up\n\ncurrent = an initial complete assignment of CSP\n\nfor i = 1 to max_steps: \n  if current is a solution for csp then return current \n  var = a conflicted variable from cspvairables\n  value = the value for var that minimizes its conflicts\n  set var = value in current \nreturn failure \n```\n\n**constraint weighting** aims to concentrate on the important constraints by giving each one a weight. At each step of the search, choose a value/variable pair that gives the lowest weight for all violated constraints. Then, adjust the weights by incrementing the weight of each contraint violated by this assigment \n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n Create independent subproblems -> find connected components of the constraint graph. Each one is a subproblem. -> greatly reduces runtime \n\nto ~ O(d^n) \n\nany tree CSP can be solved linearly in the number of variables \n\na CSP is **directionally arc consistent** under an ordering of variables X1, X2, ..., Xn iff Xi is arc-consistent with each Xj for j > i \n\nCan reduce constraint graph by:  \n**cutset conditioning** where you assign some values so the remaining ones form a tree \n\n**tree conditioning** creates a tree from the graph, where each node is a set of variables. if two variables are connected by a constraint, they're in the same node of the tree. If a varaible appears in 2 tree nodes, it appears all along the path connecting those nodes \n\nTree CSP solves in O(nd^2) time \n\n\n\n\n## Module 6 Lecture Notes\n CSPs are specialized for identification problems. \n\n**discrete variables**: \nfinite domains: n vars, O(d^n) complete assignments w domain d \ninfinite domains: like scheduling jobs (vars for start and end of each job) \n\n**Continuous variables** -> e.g. start and end time for Hubble ST \n\nCan express a CSP as a search problem: \n\n- initial state: {} empty assignment \n\n- successor function: assign value to any unassigned var wo constraint conflict \n\n-goal test: see if assignment is complete \n\n- path cost: a constant cost per step \n\nA solution for n variables is always found at depth n, hence depth-first approach \n\nfor n variables and domain size d, branching factor = n*d, \n\nnum leaves= d^n (given commutativity) \n\n**heuristic order:** \n- choose most contrained variable (fewest value options) \n- if tie, choose most contrinaing variable (imposes most constraints) \n- then, for values, choose least contraining. \n\n**Constraint propagation** is an inference technique that eliminates values if they violate local consistency \n\n\nfrom constraint graph to directed graph -> now nodes are joined by two edges, going opposite ways. Simplest form of propagation enforces arc consistency.\n\n\n\n\n\n## Module 6 Definitions\n* **Consistent assignment** - assignment of value to variable that does not violate any constraints. aka legal assignment\n* **Complete assignment** - one where every variable gets a value\n* **Solution to a csp** - consistent, complete assignment of values to vars\n* **Partial assignment** - one that leaves some variables unassigned\n* **Partial solution** - Partial assignment that is consistent\n* **Conflict set for a** - set of all the assignments in conflict with A\n* **Tree width of a graph** - 1 less than the size of the largest node/ minimum width of all tree decompositions \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 = \"\"\" **Knowledge-based agents** use reasoning over their internal \\\n",
        "representation to decide what to do \n",
        "\n",
        "Different from the **problem-solving agents** which only know the state, actions \\\n",
        "and the resulting state of performing each action \n",
        "\n",
        "**knowledge base (KB) ** is a set of sentences (in technical sense). Each sentence \\\n",
        "is esxpressed in **knowledge representation language** and represents an assertion \\\n",
        "about the world  \n",
        "\n",
        "An **axiom** is a sentence not derived from other sentences (it's given)  \n",
        "\n",
        "**tell**- add new sentences \n",
        "\n",
        "**ask**- query KB about the world \n",
        "\n",
        "**Inference**- is deriving new sentences from old ones \n",
        "\n",
        "every time the agent function is called: \n",
        "- it **tells** the KB about the new percept \n",
        "- it **asks** about the best possible action for that percept at this time t \n",
        "- it **tells** the KB which action it has performed \n",
        "\n",
        "\n",
        "**knowledge level description**- agent only needs KB and its goals to determine \\\n",
        "its behaviour \n",
        "\n",
        "**implementation level**- the physical means of acheiving the goal (like how \\\n",
        "we represent the map for instance?) \n",
        "\n",
        "\n",
        "**declarative  approach to knowledge building** involves just feeding an agent \\\n",
        "its sentences, ie telling it all it needs to know \n",
        "\n",
        "**procedural approach** encodes desired behaviours directly as program code \n",
        "\n",
        "The best agents combine both approaches. \n",
        "\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\" Conclusions are **guaranteed** to be correct if the availavle \\\n",
        "information is correct  \"\"\"\n",
        "chapter7_3 = \"\"\" **syntax** describes the rules for the language. It specifies \\\n",
        "that sentences should be **well-formed** \n",
        "\n",
        "Logic must also define the **semantics** of the sentences, ie their meaning. \\\n",
        "Semantics define the truth of a sentence wrt each possible world. \n",
        "\n",
        "For each world, it can only be true or false, no in-between (though later fuzzy \\\n",
        "logic will consid3er degrees of truth) \n",
        "\n",
        "**model** = possible world. Sets a truth value for every propositional symbol \n",
        "\n",
        "If a sentence, a, is true in a model, m, we say that m satisfies a or m is a model \\\n",
        "of a. \n",
        "\n",
        "**M(a)** is the mean of all models of a \n",
        "\n",
        "**entailment**- the idea that a sentence follows logically from another \\ \n",
        "**A |= b** means A entails b. True if for every model in which a is true, b is alsp \\\n",
        "true. So If M(A) is a subset of M(B). and in this case A is a **stronger** \\\n",
        " assertion than B, because it rules out more possible worlds. \n",
        "\n",
        " KB can be a set of sentences of a single sentence that asserts all the individual \\\n",
        " sentences. It is **false** in models that contradict what the agents knows \n",
        "\n",
        " **model checking** involves checking to see if a is true in all models where KB \n",
        " is true.. so we check all models against KB. \n",
        "\n",
        " **KB |=i a** means a can be derived from KB using inference algorithm i. Think \\\n",
        " of a as the needle, KB as the haystack, and inference is finding a in KB. \\\n",
        " Entailment is a even being in KB \n",
        "\n",
        " A **sound or truth-preserving** algorithm derives only entailed sentences. \n",
        "\n",
        " Model checking is sound, and works if the model space is finite. \n",
        "\n",
        " An algorithm is **complete** if it can derive any sentence that is entailed \n",
        "\n",
        " **grounding**- the connection between logical reasoning and the real world \\\n",
        " environment where the agent exists. ie how do we know KB is true in the real \\\n",
        " world? Through the agent's **sensors** \n",
        "\n",
        " **learning** is the process of coming up with general rules from perceptual \\\n",
        " experience (like that if there is a stench, then a wumpus is nearby) \n",
        "\n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" **atomic sentences** consist of a single proposition symbol(can \\\n",
        "be true or false) \n",
        "\n",
        "\n",
        " **complex sentences** combine atomic ones with logical connectives \n",
        "\n",
        "a **literal** is an atomic sentence or a negated atomic sentence (true or false) \n",
        "\n",
        "**conjunction** = and = $\\land$\n",
        "\n",
        "**disjunction** = or = $\\lor$ \n",
        "\n",
        "**implication** = rules or if/then = A => B, where a is the **premise or\\\n",
        " antecedent** and B is the **conclusion or consequent** \n",
        "\n",
        " **biconditional** = iff = A <=> B \n",
        " \n",
        " **operator precedence** in order: not, and, or, implies, biconditional \n",
        " \n",
        " To derive the truth value of complex sentences, follow the boolean logic rules \\\n",
        " from the atomic sentence. Note: P <=> Q is true if P = Q (so opposite XOR) \n",
        "\n",
        " **TT-entails** is complete and sound. for n sentences in alpha, it runs in \\\n",
        " O(2^n) time and O(n) space, since the enumeration is depth first \n",
        "\n",
        " ```\n",
        " function TT(KB, alpha) returns true or false \n",
        " KB = knowledge base,\n",
        " alpha = query = a sentence in propositional logic \n",
        "\n",
        " symbols = list of proposition symbols in KB and alpha \n",
        " return TTCheckall(KB, alpha, symbols) \n",
        "\n",
        " function TTCheckall(KB, alpha, symbols, model) returns true or false\n",
        "if symbols.empty:\n",
        "    KB.model == true then return a.model == true [because they must both be true \\\n",
        "    for entailment]\n",
        "    else return true [when KB is false, always return true]\n",
        "else \n",
        "  P = symbols[0]\n",
        "  rest = {all other symbols}\n",
        "  return (TTCheckall(KB, alpha, rest, model U {P = true}) and (\\\n",
        "  TTCheckall(KB, alpha, rest, model U {P = false}))\n",
        "```\n",
        " \"\"\"\n",
        "chapter7_5 = \"\"\" **Theorem proving** involves applying rules of inference to \\\n",
        "sentences in KB to prove a sentence (rather than model checking, which takes \\\n",
        "lots of time).  Better bc you can ignore any number of irrelevant propositions \n",
        "\n",
        "a is **logically equivalent** to b if they are true for the same set of models \n",
        "\n",
        "a == B iff a |= b and b |= a  (so they entail each other)\n",
        "\n",
        "**deduction theorem** a |= b iff (a=> b) is valid\n",
        "\n",
        "a is **valid** iff notA is satisfiable and the contrapositive is true  \n",
        "\n",
        "a |= b iff (a ^ notB) is unsatisfiable \n",
        "\n",
        "**modus ponens**- {a=> b, a}/{b} means that when a => b and a are given, then we \\\n",
        "can infer B. \n",
        "\n",
        "**AND elimination**- a and b / a  (so from a and b, we can infer any of the conjuncts \\\n",
        ") \n",
        "\n",
        "**proof problem:**\n",
        "- initial state: the initial knowledge base \n",
        "\n",
        "- actions: all inference rules applied to all the sentences that match the top \\\n",
        "half of the inference rule \n",
        "\n",
        "- result of an action : add the sentence in the botom half of the inference rule \n",
        "\n",
        "- goal: a state that contains the sentence we are trying to prove \n",
        "\n",
        "**monotonicity** holds, and states that the set of entailed sentences can only \\\n",
        "increase after information is added to the knowledge base \n",
        "\n",
        "non-monotonic logic captures \"mind changing\" \n",
        "\n",
        "**factoring** is removing multiple copies of the same literal \n",
        "\n",
        "resolution rule- eliminating complementary literals anded together. Only \n",
        "works on clauses (ie disjunctions of literals). It is sounds and complete. \n",
        "\n",
        "All propositions can be converted to **CNF**, conjunctive normative form. A \\\n",
        "conjunction of clauses \n",
        "\n",
        "**contrapositive**- a => b == notB => notA \n",
        "**implication elimination**- a  => B == notA or B \n",
        "**biconditional elimination**- a <=> B == (a => B) and (B => a) \n",
        "**commutativity**- A and B == B and A (applies to or) \n",
        "**associativity**- A and (B and C) == (A and B) and C (applies to or) \n",
        "**Demorgan**- not(A and B) == notA or notB (analagous for or)\n",
        "**distributivity of and over or**- a and (b or c) == (a and b) or (a and c) (\\\n",
        "analagous for or over and) \n",
        "\n",
        "**ground resolution theorem**- if a clause in unsatisfiable, the resolution \\\n",
        "closure of those caluses contains the empty clause. \n",
        "\n",
        "resolving two horn clauses, gives another horn clause. That is, horn clauses \\\n",
        "are **closed** under resolution \n",
        "\n",
        "definite clauses can be written as implication. conjunction of positive literals => \\\n",
        "single positive literals. e.g. (notA or notB or C) == (A and B) => C. \n",
        "\n",
        "In horn form, the premise = **body** and the conclusion = **head** \n",
        "\n",
        "deciding entailment with horn clauses can be done in linear time wrt size of KB \n",
        "\n",
        "ie using horn/definite clauses can be faster.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" \n",
        "**Forward chaining** decides if a query q is entailed by a KB of definite clauses. \n",
        "Starts with the known facts/positive literals. if the premise of an implication is \\\n",
        "known, then we can add its conclusion to the set of known facts. We go until we \\\n",
        "can add the query to our KB, or until no further inferences can be made. This is \\\n",
        "**data-driven reasoning**\n",
        "\n",
        "**backward chaining** works backward from a query and is a type of **goal-directed \\\n",
        "reasoning**. if the query is true, no work is needed. Else, the agortihm finds \\\n",
        "implications in the KB whos conclusions == query. We can use backward chaining to \\\n",
        "see if all the premises of the implication is true, in which case the query is true.\n",
        "\n",
        "Convert B <=> A or C to CNF.\n",
        "\n",
        "1. Eliminate biconditionals. B => (A or C) and (A or C) => B  \n",
        "\n",
        "\n",
        "2. Eliminate implications. (notB OR A or C) and (not(A or C) OR B) \n",
        "\n",
        "\n",
        "3. CNF requires NOT to only apply to literals. Move not inwards:  \n",
        "\n",
        "\n",
        "(notB or A or C) AND ((notA and notC) or B) \n",
        "\n",
        "\n",
        "4. use distributivity to get rid of nested ands/ors:  \n",
        "\n",
        "\n",
        "notB or A or C AND((B or notA) AND (B or notC))  \n",
        "\n",
        "\n",
        "\n",
        "**logic** serves as a general class of **representations** for KBagents. \n",
        "\n",
        "\n",
        "**Inference based on resolution** seeks to prove by contradition. ie prove that \n",
        "KB and notA is unsatisfiable, to show that KB |= a. First, convert KB and notA \n",
        "to CNF. Then, for each pair with complementary literals, resolve them to produce \\\n",
        "a new clause. Continue until: no new clauses can be added (! KB |= a) \\\n",
        "or two clauses resolve to empty clause (KB |= a). \n",
        "\n",
        "**empty clause** a contradiction, something like P and notP \n",
        "\n",
        "``` \n",
        "function PLrESOLUTION(KB, alpha) returns true or false \n",
        "  clauses = set of clasues in CNF form \n",
        "  new = {} \n",
        "  while true: \n",
        "      for each pair of clauses, ci Cj:\n",
        "          resolvents = PL-resolve(Ci, Cj) \n",
        "          if resolvents contains the empty clause return true \n",
        "          else new = new + resolvents\n",
        "      if new is a subset of clauses, return false\n",
        "      else clauses = clauses + new\n",
        "```\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"syntax of propositional logic\" : \"defines the allowable sentences\",\n",
        "\"semantics\" : \"rules for determining the truth of a sentence with respect to a \\\n",
        "specific model. ie their meaning\",\n",
        "\"valid sentence\" : \"true for all models e.g P or notP. aka Tautology\",\n",
        "\"satisfiable\" : \"true for some/any model\",\n",
        "\"clause\" : \"disjunction of literals\",\n",
        "\"definite clause\" : \"disjunction of literals where exactly one is positive. All \\\n",
        "definite clauses are horn clauses\",\n",
        "\"horn clause\" : \"disjunction of literalys where at most one is positive\", \n",
        "\"goal clause\" : \"a clause with no positive literals\",\n",
        "\"fact\" : \"sentence with a single positive literal\",\n",
        "\"complementary literals\" : \"one is the negation of the other\"\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 306,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b94f29f8-f748-4504-cd7a-f4d0b3b911f2"
      },
      "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": 307,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n **Knowledge-based agents** use reasoning over their internal representation to decide what to do \n\nDifferent from the **problem-solving agents** which only know the state, actions and the resulting state of performing each action \n\n**knowledge base (KB) ** is a set of sentences (in technical sense). Each sentence is esxpressed in **knowledge representation language** and represents an assertion about the world  \n\nAn **axiom** is a sentence not derived from other sentences (it's given)  \n\n**tell**- add new sentences \n\n**ask**- query KB about the world \n\n**Inference**- is deriving new sentences from old ones \n\nevery time the agent function is called: \n- it **tells** the KB about the new percept \n- it **asks** about the best possible action for that percept at this time t \n- it **tells** the KB which action it has performed \n\n\n**knowledge level description**- agent only needs KB and its goals to determine its behaviour \n\n**implementation level**- the physical means of acheiving the goal (like how we represent the map for instance?) \n\n\n**declarative  approach to knowledge building** involves just feeding an agent its sentences, ie telling it all it needs to know \n\n**procedural approach** encodes desired behaviours directly as program code \n\nThe best agents combine both approaches. \n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Conclusions are **guaranteed** to be correct if the availavle information is correct  \n\n## AIMA Chapter 7.3 Logic\n **syntax** describes the rules for the language. It specifies that sentences should be **well-formed** \n\nLogic must also define the **semantics** of the sentences, ie their meaning. Semantics define the truth of a sentence wrt each possible world. \n\nFor each world, it can only be true or false, no in-between (though later fuzzy logic will consid3er degrees of truth) \n\n**model** = possible world. Sets a truth value for every propositional symbol \n\nIf a sentence, a, is true in a model, m, we say that m satisfies a or m is a model of a. \n\n**M(a)** is the mean of all models of a \n\n**entailment**- the idea that a sentence follows logically from another \\ \n**A |= b** means A entails b. True if for every model in which a is true, b is alsp true. So If M(A) is a subset of M(B). and in this case A is a **stronger**  assertion than B, because it rules out more possible worlds. \n\n KB can be a set of sentences of a single sentence that asserts all the individual  sentences. It is **false** in models that contradict what the agents knows \n\n **model checking** involves checking to see if a is true in all models where KB \n is true.. so we check all models against KB. \n\n **KB |=i a** means a can be derived from KB using inference algorithm i. Think  of a as the needle, KB as the haystack, and inference is finding a in KB.  Entailment is a even being in KB \n\n A **sound or truth-preserving** algorithm derives only entailed sentences. \n\n Model checking is sound, and works if the model space is finite. \n\n An algorithm is **complete** if it can derive any sentence that is entailed \n\n **grounding**- the connection between logical reasoning and the real world  environment where the agent exists. ie how do we know KB is true in the real  world? Through the agent's **sensors** \n\n **learning** is the process of coming up with general rules from perceptual  experience (like that if there is a stench, then a wumpus is nearby) \n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n **atomic sentences** consist of a single proposition symbol(can be true or false) \n\n\n **complex sentences** combine atomic ones with logical connectives \n\na **literal** is an atomic sentence or a negated atomic sentence (true or false) \n\n**conjunction** = and = $\\land$\n\n**disjunction** = or = $\\lor$ \n\n**implication** = rules or if/then = A => B, where a is the **premise or antecedent** and B is the **conclusion or consequent** \n\n **biconditional** = iff = A <=> B \n \n **operator precedence** in order: not, and, or, implies, biconditional \n \n To derive the truth value of complex sentences, follow the boolean logic rules  from the atomic sentence. Note: P <=> Q is true if P = Q (so opposite XOR) \n\n **TT-entails** is complete and sound. for n sentences in alpha, it runs in  O(2^n) time and O(n) space, since the enumeration is depth first \n\n ```\n function TT(KB, alpha) returns true or false \n KB = knowledge base,\n alpha = query = a sentence in propositional logic \n\n symbols = list of proposition symbols in KB and alpha \n return TTCheckall(KB, alpha, symbols) \n\n function TTCheckall(KB, alpha, symbols, model) returns true or false\nif symbols.empty:\n    KB.model == true then return a.model == true [because they must both be true     for entailment]\n    else return true [when KB is false, always return true]\nelse \n  P = symbols[0]\n  rest = {all other symbols}\n  return (TTCheckall(KB, alpha, rest, model U {P = true}) and (  TTCheckall(KB, alpha, rest, model U {P = false}))\n```\n \n\n## AIMA 7.5 Propositional Theorem Proving\n **Theorem proving** involves applying rules of inference to sentences in KB to prove a sentence (rather than model checking, which takes lots of time).  Better bc you can ignore any number of irrelevant propositions \n\na is **logically equivalent** to b if they are true for the same set of models \n\na == B iff a |= b and b |= a  (so they entail each other)\n\n**deduction theorem** a |= b iff (a=> b) is valid\n\na is **valid** iff notA is satisfiable and the contrapositive is true  \n\na |= b iff (a ^ notB) is unsatisfiable \n\n**modus ponens**- {a=> b, a}/{b} means that when a => b and a are given, then we can infer B. \n\n**AND elimination**- a and b / a  (so from a and b, we can infer any of the conjuncts ) \n\n**proof problem:**\n- initial state: the initial knowledge base \n\n- actions: all inference rules applied to all the sentences that match the top half of the inference rule \n\n- result of an action : add the sentence in the botom half of the inference rule \n\n- goal: a state that contains the sentence we are trying to prove \n\n**monotonicity** holds, and states that the set of entailed sentences can only increase after information is added to the knowledge base \n\nnon-monotonic logic captures \"mind changing\" \n\n**factoring** is removing multiple copies of the same literal \n\nresolution rule- eliminating complementary literals anded together. Only \nworks on clauses (ie disjunctions of literals). It is sounds and complete. \n\nAll propositions can be converted to **CNF**, conjunctive normative form. A conjunction of clauses \n\n**contrapositive**- a => b == notB => notA \n**implication elimination**- a  => B == notA or B \n**biconditional elimination**- a <=> B == (a => B) and (B => a) \n**commutativity**- A and B == B and A (applies to or) \n**associativity**- A and (B and C) == (A and B) and C (applies to or) \n**Demorgan**- not(A and B) == notA or notB (analagous for or)\n**distributivity of and over or**- a and (b or c) == (a and b) or (a and c) (analagous for or over and) \n\n**ground resolution theorem**- if a clause in unsatisfiable, the resolution closure of those caluses contains the empty clause. \n\nresolving two horn clauses, gives another horn clause. That is, horn clauses are **closed** under resolution \n\ndefinite clauses can be written as implication. conjunction of positive literals => single positive literals. e.g. (notA or notB or C) == (A and B) => C. \n\nIn horn form, the premise = **body** and the conclusion = **head** \n\ndeciding entailment with horn clauses can be done in linear time wrt size of KB \n\nie using horn/definite clauses can be faster.\n\n\n\n\n## Module 7 Lecture Notes\n \n**Forward chaining** decides if a query q is entailed by a KB of definite clauses. \nStarts with the known facts/positive literals. if the premise of an implication is known, then we can add its conclusion to the set of known facts. We go until we can add the query to our KB, or until no further inferences can be made. This is **data-driven reasoning**\n\n**backward chaining** works backward from a query and is a type of **goal-directed reasoning**. if the query is true, no work is needed. Else, the agortihm finds implications in the KB whos conclusions == query. We can use backward chaining to see if all the premises of the implication is true, in which case the query is true.\n\nConvert B <=> A or C to CNF.\n\n1. Eliminate biconditionals. B => (A or C) and (A or C) => B  \n\n\n2. Eliminate implications. (notB OR A or C) and (not(A or C) OR B) \n\n\n3. CNF requires NOT to only apply to literals. Move not inwards:  \n\n\n(notB or A or C) AND ((notA and notC) or B) \n\n\n4. use distributivity to get rid of nested ands/ors:  \n\n\nnotB or A or C AND((B or notA) AND (B or notC))  \n\n\n\n**logic** serves as a general class of **representations** for KBagents. \n\n\n**Inference based on resolution** seeks to prove by contradition. ie prove that \nKB and notA is unsatisfiable, to show that KB |= a. First, convert KB and notA \nto CNF. Then, for each pair with complementary literals, resolve them to produce a new clause. Continue until: no new clauses can be added (! KB |= a) or two clauses resolve to empty clause (KB |= a). \n\n**empty clause** a contradiction, something like P and notP \n\n``` \nfunction PLrESOLUTION(KB, alpha) returns true or false \n  clauses = set of clasues in CNF form \n  new = {} \n  while true: \n      for each pair of clauses, ci Cj:\n          resolvents = PL-resolve(Ci, Cj) \n          if resolvents contains the empty clause return true \n          else new = new + resolvents\n      if new is a subset of clauses, return false\n      else clauses = clauses + new\n```\n\n\n\n\n## Module 7 Definitions\n* **Syntax of propositional logic** - defines the allowable sentences\n* **Semantics** - rules for determining the truth of a sentence with respect to a specific model. ie their meaning\n* **Valid sentence** - true for all models e.g P or notP. aka Tautology\n* **Satisfiable** - true for some/any model\n* **Clause** - disjunction of literals\n* **Definite clause** - disjunction of literals where exactly one is positive. All definite clauses are horn clauses\n* **Horn clause** - disjunction of literalys where at most one is positive\n* **Goal clause** - a clause with no positive literals\n* **Fact** - sentence with a single positive literal\n* **Complementary literals** - one is the negation of the other\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": "8a3f72b7-b6bc-40b3-edf7-fba78b607367"
      },
      "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": 303,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n human vs rational, thought vs behavior  \n\n**Turing Test**- Actingv humanly. can a machnine think? The computer passes if a\nhuman can't tell it's a computer after posing written questions and getting a response. Computer would need: NLP, knowledge representation (ie what it knows),reasoning, learning & ability to adapt to new information and patterns.  \n\nTotal turing test involves interacting with objects in the real world, thus thecomputer would also need computer vision and a physical way to move objects around   \n\n**Cognitive Modelling** approach- We have to know how humans think to say that a program thinks like a human. Learning about human thought- introspection, psychological experiments, brain imaging. \n\n\n**Law of thought** approach- thinking rationally. Artistotle's syllogisms providea pattern for argyment where the conclusion is always correct when the premisesare also correct.  e.g. Socrates is a man, all men are mortal & therefore socratesis mortal. -> govern operation of the mind -> the field of logic  \n\ndevelop notation for statements about the world -> programs that can solve any problem in logical notation. Logic requires certain knowledge of the world though,and this is not often the case. Probability fills the gap, and allows rigorousreasoning and rational thought, but not rational action.  \n\n**Acting rationally**- rational agent approach. Pros: no longer imitating human behaviour. more general than law of thought approach bc you can acheieve rationalityin other ways than correct inference. Also allows for scientific development bcrationality is mathematically well defined(?)   \n\n**Value alignment problem**- how well your true preferences and the objective youput into the machine agree \n\n## AIMA Chapter 27.1 The Limits of AI\n **Qualification problem**- difficulty capturing every contingencyof appropriate behaviour in a set of necessary and sufficient logical rules. \n\n**embodied cognition**- cognition takes place in a body, which is in an environment.It doesn't make sense considering the brain separately, because key informationwould be missed. Robotics, vision etc. are more central with this approach.  \n\nTuring & Godel- Some mathematical questions are unanswerable by formal systems.  \n\nG(F) is a sentence in F, but cannot be proved by F.  \nIf F is consistent, then G(F) is true.  \n\nFlaw: there are some statements that some people can't assert, and they are noless human. 2. His theory applies to mathemematics, not computers. No entitycan prove things that are impossible to prove. 3. His theorem only applies to formal systmes that are powerful enough to do arithmetic, ie Turing machines. Computers and turing machines are not equivalent, bc computers are finite.Computers can also change their minds.  \n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Alan Turing- **\"Polite convention\"** that everyone thinks. John Searle- rejects this with Chinese room argument. \n\n**Consciousness**- awareness of the outside world and the self, and the experienceof living. qualia- intrinsic nature of experiences. The big Q is whethermachines have this\n\n## AIMA 2.1 Agents and Environments\n Agents perceive percepts with sensors and act on them with actuators.  \n\n**Percept**- what the agent is perceiving  \nPercept Sequence- The full history of all the agent has perceived. \n\nAn agent's choice of action at a given time depends on its percept sequence andbuilt-in knowledge, but not something it hasn't perceived (no omniscience). \n\n**Randomness** can be intelligent. In single-agent environments, it can help to avoidinfinite loops but isn't actually usually the most rational option\n\n \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n **Consequentialism**- evaluate an agent based on its consequences \n\nDesign performance measure based on what you want achieved, not what you expectthe agent to do (e.g. rewarding for a clean floor rather than amount of dirtcleaned). \n\nWhat is rational is given by: performance measure, agent's prior knowledge, agent's percept sequence to date, agent's possible actions. \n\n**Omniscience** (knowing the actual outcomes for actions) is impossible in reality so we go for rationality  \n\n**Information gathering**- improves rationality and involves doing actions to modify future percepts (e.g. exploration). \n\nAn agent lacks **autonomy** when it relies on prior knowledge of its designer ratherthan its own learning and percepts. Rational agents should have autonomy.\n\n\n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n **agent architecture**- agent's computing device with sensors andactuators. \n\nAgent function may depend on the whole percept history, while agent program onlyneeds current percept.  \n\nAgent programs can be coroutines that run asynchronously with the environment.need input/output port which takes percepts and outputs actions respectively. \n\n**Simple reflex agent**- selects actions based on current percept, ingoring percepthistory.   \n\n**Condition ation rule**- if x then do y  \n\n**Model based agents-** keeps track of what it can't see in partially observableenvironments. an internal state that depends on percept history. Need: sensormodel, transition model, actions, rules and state\n\n**Sensor model**- how the state of the world is reflected in the agent's perceptsie when it rains, droplets of water obstruct the view from the car(?). \n\n**Goal-based agents** also take into account their goal to make a decision. \n\n**Utility function**- agent's internalization of the performance measure \n\n**Learning agents**\n\n**Learning element**- responsible for making improvements. \n**Performance Element**- responsible for selecting external actions \n\n**Atomic representation**- each state of the world is indivisible  (ie no internal structure).  \n**Factored respresentation**- splits state up into a set of variables and  attributes, each of which has value \n\n\n\n## Module 1 Lecture Notes\n **Alan Turing**- Imitation Game Test. \n\n**John Searle** - Language is just the application of rules. You need a brain to be human.  \n\n**Strong AI** - computer has a mind/has cognitive states (actually thinking) \n\n**Weak AI**- computer stimulates thought but has no real understanding \n\n**Daniel Dennett**- Brain in a vat   \n\n\n**Task Environments** (problem specification)\nneed: performance measure, sensors, actuators, environment\n\ntypes of environments:  \n\n**fully observable**- can see all relevant objects and such (chess). \n\n**partially observable**- can access some information (self driving car, robot vaccuum)\n\n**deterministic**- knowledge of an action's results(ie next state is completelydetermined by this one).\nwrt specific agents (chess). \n\n**non-deterministic**- games of chance, outcome uncertain\n-> often called stochastic (probabilistic)\n\n**episodic**- agents need to process self-contained episodes. choice not dependent on\nprevious decisions e.g. (picking defective items off assembly line)  \n\n**sequential**- this decision affects future ones. thus involves planning ahead. \n\n**static**- doesn't change while agent deliberates (crossword puzzle). \n\n**dynamic**- environment can change (self driving car). \n  \n**semi-dynamic**- agent score changed but not the environment? (chess penalty for taking too long)   \n\n**discrete**- applies to the state of the environment, the handling of time, percepts and actions. finite set of actions, discrete states (board games). \n\ncontinuous is the opposite\n\n**single agent**. \n\n**multiagent**- can be competetive or cooperative, usually assume other agent is acting rationally.  \n\n**Known** (vs unknown environment)- state of knowledge about the law of physicsfor the environment. we know how the world works. KNown environments can stillbe partially observable (e.g. solitaire, where you don't see the cardsbeforehand but you know the rules)\n\n**Reflex agent** selects actions based on current percept, ignoring previous stuff. \n\n**problem-solving agent** plans ahead and considers path to goal   \n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive (through sensors) and act(through actuators) in an environment\n* **Agent function** - takes a sequence of percepts and maps each to an action  from a predefined list. abstract mathematical description\n* **Agent program** - concrete implementation of the agent function running on aphysical system\n* **Percept** - perceptual inputs.. stuff happening in the world\n* **Performance measure** - criteria for success +1 for good things -1 for bad things. evalutates the behavior of agent \n* **Rational agent** - perceives its environment and behaves rationally. ie selectsan action to maximize the expected value of its performance measure\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\nWhite space matters in python. use backslash to continue line.  \n\n**Strong typed**- every object has a fixed type so interpreter doesn't allow incompatible operations.  \n\nAlso **dynamically typed**- no type signatures for functions, types of var notdeclared and you can reassign them to a diff type\n\n**Power**- 2^4= 2**4 \n\n+= -= etc. as in Java but no ++ or --\n\n**Strings:** \n\n1.immutable \n2. single or double quotes, triple for multi-line \n3. ```+``` for concatenation \n\nr'\n' means raw   \n\nprint(%s can speak %d languages\" % (\"C3PO\", 2)). \n\nuse y= x[:] to obtain a shallow copy \n\n**==** compare by value \n\n**is** compare by object reference \n\n**Tuples** immutable ordered sequence of items (can have mixed types) e.g(1, \"two\", 3.0)\n\n**List** Mutable ordered sequence of items (mixed types) e.g [1,2,3]. \n \n``` x[index]```  to acess element   \n\n``` x[-index]```  for negative lookup  \n\n``` x[i1:i2]```  for slicing, includive of i1 exclusive of i2. \n\n``` x[i1:i2:n]```  from i1 to i2 choosing every nth item \n\n``` x[:i1]```  copy from beginning  \n\n``` x[i1:]```  copy from i1 to end\n\n``` li.append()```   \n\n``` li.insert(i, e)```  insert e at index i \n\n``` li.index(e)```  index of first occurence of e in li\n\n``` li.count('b')```  num occurences\n\n``` li.remove(e) ``` remove first occurence of e\n\n``` li.reverse() ``` reverse in place (bc lists are mutable) \n\n``` li.sort() ``` sort in place \n\n``` sorted(li) ``` sorted copy \n\n``` x.join(\" z\") ``` \n\n``` x.split(\" \") ``` \n\n``` x.capitalize() ``` dog -> Dog \n\n``` x.upper() ``` dog -> DOG\n\n``` x.strip('-') ``` hi- -> hi \n\n**Dictionaries** \n\nimmutable keys (like tuples) bc hashable \n\n```d = {\"a\": 1, \"b\":2} ``` \n\nd[a] = 1 (but cannot get by value) \n\n```d.keys(), d.values(), d.items()```\n\n**functions** \n\n``` def example_function(input1, input2 = 3):  ```  \n\ncan return multiple values! will be a tuple  \n\nnondefault values come first, else SyntaxError \n\n```example_function(3, input2 = 4)``` keyword args should come last else err \n\n```*args``` for any number of nonkeyword arguments func(*li) or func(x,y,x)\n\n```**kwargs``` for any number of keyword arguments func(**dict) or func(in= \"x\", z=\"y\")  \n\n``` def example_function(input1, *args, **kwargs):  ```  \n\n**Functions** can be assigned to variables, stored in data structures, passed inas args, returned etc \n\n**Higher order function**  \n\n``` \ndef compose(f, g, x):\n      return f(g(x)) \n\ncompose(str, sum, [1,2,3]) \n``` \n\n**Classes**  \n\n``` class Student(PennStudent, OtherClass): #PennStudent is a superclass  \n  univ: \"penn\" #class attribute\n  def __init__(self): #constructor\n    PennStudent.__init__(self)\n    self.var = var\n  def method():\n\nstudent1 = Student(etc.)\nstudent1.method() or Student.method(student1) \n```\n**Magic methods** \n\n__len__  \n\n__copy__ \n\n__cmp__ for == \n\n__add__  \n\n__neg__ -  \n\n__str__ for print() \n\n``` for x in range(5):\n#[0-4]\n```\n\n``` [x**2 for x in n if y]\n    d = {k:v for (k,v) in l}, also sets \n``` \n\nIterators: has a next() method, but no hasNext() so catch exception. \n\n```i = iter(lst)\n``` \n\n```\ntry: \n    print(g.next())\nexcept StopIteration:\n  #stuff \n\n\n// integer division \n```\n\n\n## Module 2 Definitions\n* **Immutability** - object cannot be modified after creation\n* **First class object** - functions can be destroyed, created, passed to other functions, returned as a value etc.\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Problem Solving agents use an atomic representation of states. \n\n**closed loop** system monitors percepts (good for non-deterministic). \n\n**open loop system** ignores percepts. no loop between agent and evironment \n\n\n\n\n## AIMA Chapter 3.2 Example Problems\n **touring problem** gives a set of location to visit rather thanone goal. **TSP** involves visiting all nodes  \n\n**Robot navigation** path finiding in a 2d space (multi-d if interacting withobjects\n\n## AIMA Chapter 3.3 Search Algorithms\n **state space** set of states in the world and transition model\n\n**Search tree** node containing states of the world (& other stuff) joined by actions where one path leads to goal. ie defining paths between states to goal \n\n**Best-first search** chooses node with minimal f(n) (evaluation function). usesap priority queue\n\n**Node** - State, parent, action, path cost g(n)\n\n  \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n **BFS** \n\n``` \nnode <- node(problem.initial) \n\nif node has goal state then return node \n\notherwise, \n\nfrontier = Queue()\nfrontier.put(node)\n\nreached = {}  \nreached[problem.initial] = True\n\ncame_from = {} \ncame_from[problem.initial] = None\n\nwhile not frontier.empty(): \n    curr = frontier.get()\n    for next in neighbors(curr):\n      if next has goal return next\n      if next not in reached: \n        reached[next] = True\n        came_from[next] = curr\n        frontier.put(next)\n```\n\n**Dijkstra's or uniform cost**\n- best-first with f(n) as cost of path from root to current node (g(n))\n\n- check for goal when selected for expansion rather than when added to frontier. So if checks if a node is the goal after adding to frontier  \n\n- if all action costs are > 0, then no infinite path issue. it is optimal and \ncomplete \n\n- runtime depends on path cost lower bound and cost of the optimal solution. When action costs are equal, O(b^{d+1}), similar to bfs \n\n\n**Iterative-deepening and DLS**  \n\nIDS keeps running until failure (returned instead of cutoff) or result \n\n``` \nfor depth = 0 to infinity, DLS(depth) \n``` \n\nfor DLS, if (depth) > l, then cutoff is result. otherwise, check for cyclesand continue as normal.  \n\n**Bi-directional search** \n- finds path from initial state to goal and vice versa. Stops when the twofrontiers overlap. Motivation b^{d/2} + b^{d/2} < b^d. Must keep track of 2 setsof reached states, frontiers etc. \n\nUsing best-first approach, you'd expand smallest-cost node across either frontier\n\n\n \n\n## Module 3 Lecture Notes\n **Search problem** - \n\n**states**- set S, state space, all possible states \n\nan **initial state**- $ s \\in S $\n\nset of **goal states**\n\n**actions**- set A. Actions(a) returns the actions **applicable** in s \n\n**transition model**- how to transition from one state to another, given input\n\n$ \fforall s \fforall a \\in Actions(s) Result(s, a) -> s_r $. \n\npath cost/performance measure- must be additive  \n\n$ c(x,a,y) \\geq $ is step cost where action a goes from state x to y \n\nGoal test: goal(s), is s the goal state? \n\n**Tree Search** - Does not check for redundant paths. It goes through all possiblepaths from  initial state or root. \n\n**Graph Search** - tree search modification that now checks redundant paths (ie)keep track of states seen so far. Uses more memory and faster and avoids loops \n\n**Uniformed search**- uses only problem definition so all non-goal states are thesame \n\n**BFS** \n- FIFO queue frontier\n\n- add node to q after checking goal state  \n\n- complete if max branching factor(b) is finite  \n\n- optimal if cost = 1 per step (equally unweighted) \n\n- Time O(b^d) d= depth of least cost solution\n\n- Space O(b^d) bc stores every node  \n\n- good for possible infinite paths, if solutions have short paths, can discardunlikely paths quickly  \n\n- call to best-first search where f(n) is the depth\n\n**DFS** \n- LIFO queue frontier\n\n- not complete (loops & infinite depth) except if you account for repeasted statesalong path \n\n- not optimal \n\n- O(b^m) time. bad if m >> d where m is maximum depth of state space \n\n- Space O(bm) (good for restricted space or when there are many long-path solutions) \n\n- call to best-first with f(n) as negative depth(deepest first)\n\n**Depth-Limited Search: DLS** \n- DFS with limit l \n\n- no infinite paths \n\n- if l = d then optimal, otherwise not\n\n- generally incomplete and not optimal\n\n- incomplete if l < d, suboptimal if l > d\n\n- O(b^l) time \n\n- O(bl) space \n\n**Iterative deepening search** \n- Do DLS with increasing l \n\n- complete(?) & optimal \n\n- time complexity O(b^d)\n\n- O(bd) space\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - the set of all states reachable by any sequence of actions from the initial state\n* **Path** - sequence of actions from one state to another\n* **Solution** - path from initial state to goal. A solution is optimal if no otherhas a lower path cost\n* **Frontier** - states available to be expanded\n* **Completeness** - whether search strategy will find a solution or not\n* **Optimality** - whether it finds the path with the lowest cost first\n* **Planning agents** - use factored or structured representations of states (internal structure)\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n **Consistency** \n\nh(n) <= c(n,a,n')+ h*(n') \n\nEvery consistent heuristic is admissible, but not the other way around \n\nif the optimal solution has cost C* and the second best, C2, then A* returns thecost-optimal solution is h(n) never overestimates the cost by more than C2-C*.\n\nif h(n) is admissible for all nodes on the path, A* returns a cost-optimal sol regardless of other nodes. \n\n Along the path, g(n) is strictly monotonic(increasing). So, contours of the  state space don't overlap. If h(n) is consistent, f(n) (=g +h)is monotonic too.\n\nAll nodes where f(n) < C* are **surely expanded nodes** \n\nno nodes with f(n) > C* will be expanded, but some with f(n) = C* \n\n\nWeighted A search \n \nExpands nodes with weighted heuristic value: \n\nf(n) = g(n) + W * h(n) for some W > 1 \n\n**Speedy search**- unbounded-cost search alg. Type of Greedy best-first search,where h(n) is the num steps to goal, regardless of cost. Same as GBFS when weights are uniform, but potentially faster otherwise. \n\n **Beam search** - incomplete and suboptimal but better for memory, because  frontier is bounded. So keep best k nodes, discarding others. \n  Alternative- keep track of nodes within delta of the best f-store node. all   strong candidates kept, weak ones discarded. \n\n```\nIterative-deepening A* search \n```\n\nThe cutoff is f-cost (g + h), rather than depth this time. It is the smalled f cost of any node that exceeded the cutoff in the previous iteration. \n\n**Recursive best first search** does best first search in linear space. Keeps track of the best f-value for alternate paths available from any ancestor of curr node. If any node exceeds this, the recursion bubbles back up and replaces the other f values with the backed up value along the way.  \n\n- optimal if h(n) is admissible \n\n**memory bounded A star** and simplified MBAstar. It does regular A star until memory is full, then drops the worst node(highest f) to add a new one. Also  backs up the value of f for that worst node. For ties, we expand the newest  and delete the oldest. \n\nSMBA star is complete if there is a reachable solution (if d is less than memory size) \n\n\n## AIMA Chapter 3.6 Heuristic Functions\n **Effective branching structure**, \n```\nb* - way to qualify a heuristic \n```\n\nN - total number of nodes generated by A* \nd - solution depth \n\n\n$N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d$\n\nGood heuristics have a branching factor close to 1 \n\n\n\n## Module 4 Lecture Notes\n **Greedy Best-first** \n- Select node with minimal h(n) = f(n), completely ignore g(n) \n\n- like UCS but f(n) replaces path cost (g(n)) \n\n- Priority queue \n\n- not optimal \n\n- not complete (can get stuck in loops) \n\n- O(|V|) time and space (but can be reduced to O(bm))\n\n```\nfrontier = Priorityqueue() \nfrontier.put(start, 0) \ncame_from={}\ncame_from[start] = None\n\nwhile !frontier.empty: \n    current = frontier.get()\n\n    if current == goal: \n      break\n    for next in current.neighbours:\n      if next not in came_from:\n        came_from[next] = current\n        priority = heuristic(next,goal)\n        frontier.put(next, priority)\n```\n\n**Manhattan distance** heuristic for a grid: \n\n- admissible \n\n```\nreturn abs(a.x -b.x) +  abs(a.y - b.y) \n```\n\n- can use straight line distance also\n\nEuclidean distance vs Manhattan distance  (?) \n\n\n```\nA* Search\n```\n\n- expand with minimal f(n) = g(n) + h(n) \n\n- h(n) must be admissible/optimistic \n\n- Priority queue \n\n- stop when goal node is expanded (ie top of priority queue) \n\n- optimal, complete, optimally efficient \n\n \n\n## Module 4 Definitions\n* **Heuristic function** - h(n). gives an estimate of distance to goal from state sat node n\n* **G(n)** - path cost\n* **Admissible heuristic** - will never overestimate cost to goal\n* **Dominance** - h2 dominates h1 if for all n h2(n) >= h1(n). h2 is better becauseit is optimistic, but a better estimate\n* **Pruning** - eliminating/not examining unlikely possibilites\n* **Satisficing solutions** - using an inadmissible heuristic that may be more accurate, but risk missing the optimal solution. Less nodes expanded\n* **Bounded suboptimal search** - solution guaranteed to be within a constantfactor, W, of the optimal cost\n* **Bounded-cost search** - solution has cost less than some constant C\n* **Unbounded cost search** - accept a solution of any cost, quickly\n* **Optimally efficient** - ?\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n \n\n**Minimax search**  \n\nO(b^m) time where b= legal moves at each point, m = max depth of tree \n\nO(bm) space if actions generated all at once, O(m) if 1 by 1 \n\n**Minimax value-** max's utility of being in that state, assuming that both players played optimally. Terminal nodes minmax value is justtheir utility. For non-terminal nodes, max chooses the highest possible value, minchooses the lowest one (from max's perspective)  \n\n\n**minimax decision**- minimax value of root \n\n```\nfunction minimax-search(game, state) returns an action  \nplayer = #whose play it is\nvalue, move = max_value(game, state) \nreturn move\n\nfunction max-value(game, state) returns (utility, move)\nif game is in winning state, return game.utility(state, player), null\nv = -infinity\nmove = null\n\nfor every action in game.state.possible_actions: \n  v2, a2 = min-value(game, game.Result(a, state))\n  if v2 > v,\n    v, move = v2, a\nreturn v, move\n\n#analogous for min \n``` \n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n \n\n\n**alpha** - best value for max, ie lower bound on max's outcome \"at least\"\n\n**beta**- best value for min, ie upeer bound on min's outcome \"at most\"\n\nStop evaluating when max finds a value > beta, or when min finds a value < alpha \n\n**alpha-beta search** \n\n```\nfunction ab(game, state) returns an action  \nplayer = #whose play it is\nvalue, move = max_value(game, state, -inf, +inf) \nreturn move\n\nfunction max-value(game, state, alpha, beta) returns (utility, move)\nif game is in winning state, return game.utility(state, player), null\nv = -infinity\nmove = null\n\nfor every action in game.state.possible_actions: \n  v2, a2 = min-value(game, game.Result(a, state), alpha, beta)\n  if v2 > v,\n    v, move = v2, a\n    alpha = max(alpha, v)\n  if v >= beta then return v, move\nreturn v, move\n\n#analogous for min \n``` \n\nSince the ordering of the nodes matter for ab search, if we can acheive near- perfect ordering, we could do O(b^{m/2}). b is now sqrt(b) \n\nWith random ordering- O(b^{3m/4}) \n\n**killer move heuristic** - trying killer/best moves first\n \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Stop search early and apply an **evalutation function** ie. estimating utility for nonterminal states. Introduce **cutoff test** which includes all terminal nodes by default, but will search up to depth d \n\nOne possible evaluation function- getting the **expected value** \n\nprob * cost \n\nchess eg (0.82 * +1) + (0.02 * 0) + (0.16 * 1/2) = 0.9 \n\n**Weighted linear function** because that^ is too hard in practice. \n\n**EVAL(s)** = $w_1 f_1(s)$ + ... + $w_n_ f_n$\nfi- feature of position (like number of black pawns), w is weight(importance of feature, range from 0(loss) to 1(win))  \nThis assumes that the feature is independent of the value for other features, which is usually not the case. \n\n\nEvaluation function needs to be strongly correlated with chances of winning, but not necessarily linearly. \n \n \n **forward pruning** prunes moves that appear to be bad, but could potentially  be good ones. Saves time at risk of making an error \n \n **probcut**- probabilistic cut. uses prior experience and stats to tell you  nodes that a re probably outside the (alpha, beta) window. Lessens the chance  that the best move will be pruned. It does a shallow search to calculate v,  then determines the likelihood of  v at d, being outside (a,b) \n \n **late move reduction** assumes that we have a good ordering of moves and limits  the depths of later moves (not eliminate them completely)  \n\n## AIMA Chapter 5.5 Stochastic Games\n Games involving chance. E.g. backgammon \n\nSearch tree now contains chance nodes (bc don't know what will happen next if it is based on a die roll). For this, P. 1/36 for double die rolls and 1/18 for distinct ones. Note 5-6 = 6-5. \n\n**expectiminimax** - a generalization of minimax. Regular nodes work the same. For chance nodes, we calculate the **expected value** => sum of value over all outcomes, weighted by probability of that action. \n\n**O(b^m n^m)** time where n is the number of distinct rolls\n\nIn chance games, eval function must return values that are a  **positive linear transformation** of the probability(win-lose) or the expected utility(not zero sum) \n \n \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n **decision-theoretic agent** chooses based on beliefs and wants \nRather than binary states, states have a continuous range of values.. so you can easily choose a better choice when there is no best. \n\nIf there is uncertainty about states, and possible actions then P(s'|s,a) is the probability of reaching state s' after applying a in s. \n\nP(Result(a) == s') is the outcome we care about. \n\nP(Result(a) == s') =  Sum for all possible actions, P(a)P(s'|s,a) \n\n**MEU** maximizes the average utility. \n\nThe utility function guides agents step by step. It applies to the **next** state. Meanwhile, the performance measure is external and applies to history/a sequence of steps.  \n\nif an agent acts to maximize a utility fucntion that reflects the performance measure, then the agent will acheieve the highest possible performance score, averaged over all the environments. \n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n **Lottery** the set of all possible outcomes(each w their own) probabilities. \n\n**Constraints for Preference Relation:** \n\n**Orderability**- agent has to choose and cannot avoid deciding. Decide on a or b or both \n\n**Transitivity**- if A > B and B > C, then A > C \n\n**Continuity**- if Pr(A) = p, then Pr(B) =  1 - p \n\n**Substitutability**- If an agent is indifferent to A and B, then the agent is indifferent to lotteries that essentially the same, except you substitute between A/B. A ~ B => [p, A; 1- P, C] ~ [p, B; 1- P, C]  \n\n**Monotonicity**- If 2 lotteries have the same possible outcomes, A and B, then if the agent prefers A, then the agent must prefer the. lottery that has a higher probability for A. \n\n**Decomposaibility**- Use probability rules to simplify compound lotteries [p, A; 1 - p, [q:B, 1-q,C]] ~ [p, A; q(1-p),B; (1-q)(1-p), C] \n\nIf an agent follows the above axioms, then: \n\n- There is a utility function, U, such that U(A) > U(B) iff the agent prefers A and U(A) = U(B) if the agent is indifferent \n\nThe expected utility of a lottery is the sum of the probability of each outcome times the utility of that outcome. \n\nThus, a utility function exists for any rational agent, but they are not necessarily unique.\n\n**value function or ordinal utility function**- using a preference ranking on states (actual values don't matter) \n\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n Utility functions map from lotteries to real numbers. \n\nTo build a **decision-theoretic system** \n\n**preference elucidation**- presenting many choices to human and determining underlying utility function from observed preferences \n\n**Normalize utilities**- ie give them a scale by giving best and worst case their values \n\nYou can then assess the utility of S by comparing to the range of values in the standard lottery (ie given the bounds generated above). The first value of indifference is the utility. \n\n**Normative theory**- describes how an agent should act \n\n**Descriptive theory**- describes how the act actually acts \n\n## Module 5 Lecture Notes\n \n\ngames are **multi agent** \nsimplest game environment: multiagent, static, discrete, fully-observable, strategic(ie next state is determines by curr state and actions ofagents) \n\nzero-sum, clear set of legal moves, two players alternate moves, well-defined \noutcome (ie win, lose, draw) \n\n**egocentric POV** ie even levels = max, odd = min \n\nexpectimax- average score, assuming optimal play\n\n\n\n\n## Module 5 Definitions\n* **Ply** - one action by one player (1 level deeper in tree) (move can mean both players did something)\n* **Type a strategy** - wide but shallow, see all nodes up to a certain depth.  Chess\n* **Type b strategy** - deep but narrow, follow promising moves as far down as  possible. GO, since b is much higher \n* **Quiescent state** - there is no pending move (like capturing the queen\n* **Policy** - mapping of each state to the best possible move in that state\n* **Random variable** - event whose outcome is unknown\n* **Probability distribution** - asdignment of weights to outcomes\n\n\n## WARNING: Your summary of 'AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n **CSP Problem**- each state is a set of variables with their own values. The problem is solved when all variables have a value that satisfies constraints\n\n- use general, rather than domain specific heuristics \n\nMore formally: \n- X is the set of variables, {X_1, ..., X_n}  \n\n- D is the set of domains, {D_1, ..., D_n}, one for each variable \n\n- C is the set of contraints that specify allowable combinations of values in the form of <scope, rel>. e.g. <(X1, X2),{(3,2), (3,1), (2,1)}> or <(X1, X2), X1 > X2> \n\ne.g. D_1 has the set of allowable values {v_1, ..., v_k} for variable X_1 \n\nSolving a CSP involves values to variables. It is NP-Complete \n\n**constraint graph** represents variables as nodes and constraints as edges between them \n\nsimplest CSP- discrete, finite domains \n\n**unary constraint**- restricts the value of a single day \n\n**binary constraint**- relates 2 variables \n\n**binary CSP** can be respresented as a constraint graph. It has only unary and binary constraints \n\n**global constraint**_ involves an arbitrary amount of variables (does NOT need to include all) aka **higher order constraint** \n\n\n**preference constraints** allow you to indicate preferred solution, unlike **absolute** which is exactly what it sounds like. \n\n\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n **constraint propagation**- using the constraints to reduce num possible values for the next var, which does that for the next var and so on. It enforces constraints locally\n\na variable is **node consistent** if all its domain values satisfy the unary constraints and a graph is node consistent if all its variables are [1 consistent]\n\na variable is **arc consistent** if every value satisfies the binary constraints \na graph is arc consistent if every variable is arc consistent with every other variable [2-consistent]\n\n**AC-3 Enforces arc consistency** \n- O(d^2) time to check the consistency of an arc, so total O(cd^3) worst-case for a CSP with n variables and domain size at most d and c binary constraints. If there are n nodes, then it's O(n^2d^3), since each node can be connected to every other node (ie O(n^2) nodes). Checking one arc takes O(d^2) time, and each arc can be inserted into the q up to d times.\n\n- maintain queue of arcs (initially all) -> each constraint is 2 arcs, 1 in each direction \n\n- pops an arc from queue randomly and then makes it arc consisdent. If this  doesn't change D, then move on. if D is different, then add all the arcs (Xk, Xi) \nIf Di is revised to nothing, return failure bc inconsistent. Keep going until loop is done running, then the output will be the arc consistent version of the graph \n\nArc consistency tightens down the domains(unary constraints) using the arcs (binary contraints) \n\n\n**path consistency** tightens the binary constraints by using implicit constraints that are inferred by looking at 3 variables at a time. So {Xi, Xj} is path consistent wrt Xm if for every assignment for Xi and Xj (that satisfy their own constraints), there is also an assignment for Xm, that satisfies {Xi, Xm} and {Xm, Xj} [3-consistency, for binary constraint graphs]\n\na CSP is **k-consistent** if for any set of k - 1 vriables, a consistent value can always be assigned to any kth variable. \n\na CSP is **strongly k-consistent** if it is k consistent, k -1 consistent, k - 2 consistent... and 1 consistent. Solve by assigning variables in order: since an answer is guarantied. For each variable Xij,  we only need to search d values in the domain to find a value consistent with X_1 ... X_{i-1}. Runtime O(n^2d)\n\n```\nfunction AC3 returns false(inconsistent) or true(consistent)\nqueue = all arcs in csp\n\nwhile !queue.empty():\n    (Xi, Xj) = queue.pop()\n    if revise(csp, Xi, Xj) then\n      if size Di = 0 return false\n      else, for each Xk in {neighbours(Xi) - Xj}: \n          add(Xk, Xi) to the queue\nreturn true \n\n\nfunction review(csp, Xi, Xj) return true iff we revise the domain of Xi \n  revised = false\n  for each x in Di do\n  if no value y in Dj allows (x,y) to satisfy the constraint between Xi and Xy,\n  then delete x from Di\n    revised = true\n  return revised\n\n```\n\nfor Alldiff, for m variables with n distinct states, if m > n, then the constraint cannot be satisfied \n\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n **Backtracking search** is helpful for particial solutions from AC-3, where you still need to find the optimal solution. Tree has  d^n leaves, once you recognize commutativity. so it is a DFS with single varriable assignments \n\n\n```\nfunction Backtracking-search(csp) returns solution or failure \n  return backtrack(csp, {}) \n\nfunction backtrack(csp, assignment) returns solution or failure \nif assignment is complete then return assignment\nvar = select unassigned variable \n\nfor each value in domainVals(csp, var, assignemnt): \n    if value is consistent with assignment then: \n      add {var = value} to assignemnt \n      inferences = inference(csp, var, assignment) \n      if inferences !failure then: \n        add inferences to csp\n        result = backtrack(csp, assignemnt) \n        if result !failure then return result\n          remove inferences from csp \n          remove {var = value} from assignment\nreturn failure \n```\n\n**Domain independent heuristics for backtracking search** \n-  Order of assigning variables and values. simplest- in order, randomly. Best option- choose variable with fewest \"legal\" values. ie. **minimum-remaining-values heuristic** \n\n **degree heuristic** attempts to reduce branching factor on future choices by  selecting the variable that i involved in the largest number of constraints  on other unassigned variables \n\n\n **least constraining value heuristic** prefers the value that rules out the  fewest choices for the neighbours \n\n\n**Inference** e.g. helps to reduce domains during search \n\n**Forwards-checking** is making a variable arc consistent when it is assigned. So we keep track of possible values for all vars. If any unassigned vars has no more possible values, then terminate \n\n\n**maintaining arc consistency** detects inconsistencies in assignment. After a variable is assigned, INFERENCE procedure uses AC3 with a queue of all the arcs (Xj, Xi) for the Xi we assigned all its unassigned neighbours Xj. If constraint propagation (done by AC3) gives us an empty set, then we backtrack immediately. \n\nMAC is more powerful than AC3 because it does the same checking, but also recursively propagates constraints when the domain variables change \n\n**backjumping** backtracks to the most recent assignment when a conflic is found. It finds the exact solution as forward tracking.\n\n**constraint learning** is finding a minimum set of variables from the conflict set that causes a problem. The variables and their corresponding values form a **no good** and we can record them (by adding a new constraint, or keep track in memory) and reference, to avoid that combination in the future \n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n **local search** can solve many CSPs. Each state assigns a  value to every variable and then the search changes the value of one variable at a time. \n\n**min conflicts heuristic** changes the value of the one with the least conflicts \n\n```function minConflicts(csp, max_steps) returns solution or failure \nmax steps = num steps before giving up\n\ncurrent = an initial complete assignment of CSP\n\nfor i = 1 to max_steps: \n  if current is a solution for csp then return current \n  var = a conflicted variable from cspvairables\n  value = the value for var that minimizes its conflicts\n  set var = value in current \nreturn failure \n```\n\n**constraint weighting** aims to concentrate on the important constraints by giving each one a weight. At each step of the search, choose a value/variable pair that gives the lowest weight for all violated constraints. Then, adjust the weights by incrementing the weight of each contraint violated by this assigment \n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n Create independent subproblems -> find connected components of the constraint graph. Each one is a subproblem. -> greatly reduces runtime \n\nto ~ O(d^n) \n\nany tree CSP can be solved linearly in the number of variables \n\na CSP is **directionally arc consistent** under an ordering of variables X1, X2, ..., Xn iff Xi is arc-consistent with each Xj for j > i \n\nCan reduce constraint graph by:  \n**cutset conditioning** where you assign some values so the remaining ones form a tree \n\n**tree conditioning** creates a tree from the graph, where each node is a set of variables. if two variables are connected by a constraint, they're in the same node of the tree. If a varaible appears in 2 tree nodes, it appears all along the path connecting those nodes \n\nTree CSP solves in O(nd^2) time \n\n\n\n\n## Module 6 Lecture Notes\n CSPs are specialized for identification problems. \n\n**discrete variables**: \nfinite domains: n vars, O(d^n) complete assignments w domain d \ninfinite domains: like scheduling jobs (vars for start and end of each job) \n\n**Continuous variables** -> e.g. start and end time for Hubble ST \n\nCan express a CSP as a search problem: \n\n- initial state: {} empty assignment \n\n- successor function: assign value to any unassigned var wo constraint conflict \n\n-goal test: see if assignment is complete \n\n- path cost: a constant cost per step \n\nA solution for n variables is always found at depth n, hence depth-first approach \n\nfor n variables and domain size d, branching factor = n*d, \n\nnum leaves= d^n (given commutativity) \n\n**heuristic order:** \n- choose most contrained variable (fewest value options) \n- if tie, choose most contrinaing variable (imposes most constraints) \n- then, for values, choose least contraining. \n\n**Constraint propagation** is an inference technique that eliminates values if they violate local consistency \n\n\nfrom constraint graph to directed graph -> now nodes are joined by two edges, going opposite ways. Simplest form of propagation enforces arc consistency.\n\n\n\n\n\n## Module 6 Definitions\n* **Consistent assignment** - assignment of value to variable that does not violate any constraints. aka legal assignment\n* **Complete assignment** - one where every variable gets a value\n* **Solution to a csp** - consistent, complete assignment of values to vars\n* **Partial assignment** - one that leaves some variables unassigned\n* **Partial solution** - Partial assignment that is consistent\n* **Conflict set for a** - set of all the assignments in conflict with A\n* **Tree width of a graph** - 1 less than the size of the largest node/ minimum width of all tree decompositions \n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n **Knowledge-based agents** use reasoning over their internal representation to decide what to do \n\nDifferent from the **problem-solving agents** which only know the state, actions and the resulting state of performing each action \n\n**knowledge base (KB) ** is a set of sentences (in technical sense). Each sentence is esxpressed in **knowledge representation language** and represents an assertion about the world  \n\nAn **axiom** is a sentence not derived from other sentences (it's given)  \n\n**tell**- add new sentences \n\n**ask**- query KB about the world \n\n**Inference**- is deriving new sentences from old ones \n\nevery time the agent function is called: \n- it **tells** the KB about the new percept \n- it **asks** about the best possible action for that percept at this time t \n- it **tells** the KB which action it has performed \n\n\n**knowledge level description**- agent only needs KB and its goals to determine its behaviour \n\n**implementation level**- the physical means of acheiving the goal (like how we represent the map for instance?) \n\n\n**declarative  approach to knowledge building** involves just feeding an agent its sentences, ie telling it all it needs to know \n\n**procedural approach** encodes desired behaviours directly as program code \n\nThe best agents combine both approaches. \n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n Conclusions are **guaranteed** to be correct if the availavle information is correct  \n\n## AIMA Chapter 7.3 Logic\n **syntax** describes the rules for the language. It specifies that sentences should be **well-formed** \n\nLogic must also define the **semantics** of the sentences, ie their meaning. Semantics define the truth of a sentence wrt each possible world. \n\nFor each world, it can only be true or false, no in-between (though later fuzzy logic will consid3er degrees of truth) \n\n**model** = possible world. Sets a truth value for every propositional symbol \n\nIf a sentence, a, is true in a model, m, we say that m satisfies a or m is a model of a. \n\n**M(a)** is the mean of all models of a \n\n**entailment**- the idea that a sentence follows logically from another \\ \n**A |= b** means A entails b. True if for every model in which a is true, b is alsp true. So If M(A) is a subset of M(B). and in this case A is a **stronger**  assertion than B, because it rules out more possible worlds. \n\n KB can be a set of sentences of a single sentence that asserts all the individual  sentences. It is **false** in models that contradict what the agents knows \n\n **model checking** involves checking to see if a is true in all models where KB \n is true.. so we check all models against KB. \n\n **KB |=i a** means a can be derived from KB using inference algorithm i. Think  of a as the needle, KB as the haystack, and inference is finding a in KB.  Entailment is a even being in KB \n\n A **sound or truth-preserving** algorithm derives only entailed sentences. \n\n Model checking is sound, and works if the model space is finite. \n\n An algorithm is **complete** if it can derive any sentence that is entailed \n\n **grounding**- the connection between logical reasoning and the real world  environment where the agent exists. ie how do we know KB is true in the real  world? Through the agent's **sensors** \n\n **learning** is the process of coming up with general rules from perceptual  experience (like that if there is a stench, then a wumpus is nearby) \n\n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n **atomic sentences** consist of a single proposition symbol(can be true or false) \n\n\n **complex sentences** combine atomic ones with logical connectives \n\na **literal** is an atomic sentence or a negated atomic sentence (true or false) \n\n**conjunction** = and = $\\land$\n\n**disjunction** = or = $\\lor$ \n\n**implication** = rules or if/then = A => B, where a is the **premise or antecedent** and B is the **conclusion or consequent** \n\n **biconditional** = iff = A <=> B \n \n **operator precedence** in order: not, and, or, implies, biconditional \n \n To derive the truth value of complex sentences, follow the boolean logic rules  from the atomic sentence. Note: P <=> Q is true if P = Q (so opposite XOR) \n\n **TT-entails** is complete and sound. for n sentences in alpha, it runs in  O(2^n) time and O(n) space, since the enumeration is depth first \n\n ```\n function TT(KB, alpha) returns true or false \n KB = knowledge base,\n alpha = query = a sentence in propositional logic \n\n symbols = list of proposition symbols in KB and alpha \n return TTCheckall(KB, alpha, symbols) \n\n function TTCheckall(KB, alpha, symbols, model) returns true or false\nif symbols.empty:\n    KB.model == true then return a.model == true [because they must both be true     for entailment]\n    else return true [when KB is false, always return true]\nelse \n  P = symbols[0]\n  rest = {all other symbols}\n  return (TTCheckall(KB, alpha, rest, model U {P = true}) and (  TTCheckall(KB, alpha, rest, model U {P = false}))\n```\n \n\n## AIMA 7.5 Propositional Theorem Proving\n **Theorem proving** involves applying rules of inference to sentences in KB to prove a sentence (rather than model checking, which takes lots of time).  Better bc you can ignore any number of irrelevant propositions \n\na is **logically equivalent** to b if they are true for the same set of models \n\na == B iff a |= b and b |= a \n\n**deduction theorem** a |= b iff (a=> b) is valid\n\na is **valid** iff notA is satisfiable and the contrapositive is true  \n\na |= b iff (a ^ notB) is unsatisfiable \n\n**modus ponens**- {a=> b, a}/{b} means that when a => b and a are given, then we can infer B. \n\n**AND elimination**- a and b / a  (so from a and b, we can infer any of the conjuncts ) \n\n**proof problem:**\n- initial state: the initial knowledge base \n\n- actions: all inference rules applied to all the sentences that match the top half of the inference rule \n\n- result of an action : add the sentence in the botom half of the inference rule \n\n- goal: a state that contains the sentence we are trying to prove \n\n**monotonicity** holds, and states that the set of entailed sentences can only increase after information is added to the knowledge base \n\nnon-monotonic logic captures \"mind changing\" \n\n**factoring** is removing multiple copies of the same literal \n\nresolution rule- using other propositions to resolve the value of a literal. Only \nworks on clauses (ie disjunctions of literals). It is sounds and complete. \n\nAll propositions can be converted to **CNF**, conjunctive normative form. A conjunction of clauses \n\n**Infeence based on resolution** seeks to prove by contradition. ie prove that \nKB and notA is unsatisfiable, to show that KB |= a. First, convert KB and notA \nto CNF. Then, for each pair with complementary literals, resolve them to produce a new clause. Continue until: no new clauses can be added (! KB |= a) or two clauses resolve to empty clause (KB |= a). \n\n**ground resolution theorem**- if a clause in unsatisfiable, the resolution closure of those caluses contains the empty clause. \n\nresolving two horn clauses, gives another horn clause. That is, horn clauses are **closed** under resolution \n\ndefinite clauses can be written as implication. conjunction of positive literals => single positive literals. e.g. (notA or notB or C) == (A and B) => C. \n\nIn horn form, the premise = **body** and the conclusion = **head** \n\ndeciding entailment with horn clauses can be done in linear time wrt size of KB \n\n\n\n\n## Module 7 Lecture Notes\n \n**Forward chaining** decides if a query q is entailed by a KB of definite clauses. \nStarts with the known facts/positive literals. if the premise of an implication is known, then we can add its conclusion to the set of known facts. We go until we can add the query to our KB, or until no further inferences can be made  \n\n\nConvert B <=> A or C to CNF.\n\n1. Eliminate biconditionals. B => (A or C) and (A or C) => B \n\n2. Eliminate implications. (notB OR A or C) and (not(A or C) OR B)\n\n3. CNF requires NOT to only apply to literals. Move not inwards: \n\n(notB or A or C) AND ((notA and notC) or B)\n\n4. use distributivity to get rid of nested ands/ors: \n\nnotB or A or C AND((B or notA) AND (B or notC)) \n\n\n**contrapositive**- a => b == notB => notA \n**implication elimination**- a  => B == notA or B \n**biconditional elimination**- a <=> B == (a => B) and (B => a) \n**commutativity**- A and B == B and A (applies to or) \n**associativity**- A and (B and C) == (A and B) and C (applies to or) \n**Demorgan**- not(A and B) == notA or notB (analagous for or)\n**distributivity of and over or**- a and (b or c) == (a and b) or (a and c) (analagous for or over and) \n\n\n\n\n## Module 7 Definitions\n* **Syntax of propositional logic** - defines the allowable sentences\n* **Semantics** - rules for determining the truth of a sentence with respect to a specific model\n* **Valid sentence** - true for all models e.g P or notP. aka Tautology\n* **Satisfiable** - true for some/any model\n* **Clause** - disjunction of literals\n* **Definite clause** - disjunction of literals where exactly one is positive. All definite clauses are horn clauses\n* **Horn clause** - disjunction of literalys where at most one is positive\n* **Goal clause** - a clause with no positive literals\n* **Fact** - sentence with a single positive literal\n* **Complementary literals** - one is the negation of the other\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}