{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "IK_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": "aee840de-c629-45ce-dba7-b9bbcc22d84a"
      },
      "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": 292,
      "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": "3b1487ac-1f42-4383-f5d1-4cb4d09cf691"
      },
      "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": 293,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 294,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "04bcdc31-39bf-4a31-a365-3e6ba9120ac5"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\" human/rational and thought/behavior.\n",
        "Approaches: \n",
        "Turing: cannot tell if response is from person or computer \n",
        "Cognitive model: Compare how program solve w\\\\how computer solves. \n",
        "Laws othought: Use logic notation to solve problems, use probability to fill in certaintiy gap.\n",
        "Rationl agent: More general than laws othought, more flexible as science develops, so better than just imitating behavior.\n",
        "\n",
        "Standard model focus on study/construction of agents that do the right thing\n",
        "\n",
        "Value alginemnt problem is that what we actualy want vs what we put into machine. \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 = \"\"\" Turing said human behavior isn't guided by formal rules, use \\\n",
        "informal guideslines that are cannot be quantify/coded. Dreyfus, critique of GOFAI, simple agents \\ \n",
        "using just logical rules.\\\n",
        "Embodied cogntion centers whole system, body, brain, enviornment. So sensors are \\\n",
        "very important.\n",
        "Argument from disability - can't do lovely things humans can. But over time lots\\\n",
        "actually have done lots.\n",
        "\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" Don't know if people think, but have polite convention to pretend they do\\\n",
        "Chinese room from Searle argues computers don't just rule book. Biological naturalism \\\n",
        "mental states can only come from neurons. Don't need to solve consciousness question\\\n",
        "to make parts of (e.g.e awarness, attention) intellegent systems\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Agents percieve the enviornment via its sensors, and then make\\\n",
        "an action by actuators\n",
        "Example sensors: cameras, infrared. Example actuators: motors\n",
        "Percept is one thing that an agent's sensors percieves, and percept sequence is \\\n",
        "history of the perceptions.\n",
        "Agent func maps a _percept sequnce_ to actions. Would be a huge table b/c percept\\\n",
        "sequences get infinte. Internally have agent program - actual implrementation on real system.\n",
        "\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\" AI uses consquentalism, evaulate behavior based on conseuqneces,\\\n",
        "using performance measure that looks at sequence of states. Performance measures \\\n",
        "come from humans. Better to design perfmes for what one wants instead of how agent \\\n",
        "should behave.\n",
        "\n",
        "Rationality depends on: \n",
        "1. Perfmes\n",
        "2. Prior knowledge of env\n",
        "3. Actions available\n",
        "4. Percept seq\n",
        "\n",
        "So rational agent, for all percept seq, chose action to max perfmes based on \\\n",
        "current percseq and knowlege.\n",
        "\n",
        "Rationality max expected perf. Not same as perfection (actual perf).\n",
        "\n",
        "Information gatherin and exploration important to rationality. \n",
        "\n",
        "Agents with autonomy do better, b/c can learn. Need some base knowlegde.\n",
        "\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\" Task env needs to be specifed, give the Performance, \\\n",
        "Enviornment Actuators Sensors.\n",
        "\n",
        "- Fully observable/Partially: can percieve whole relevant env?. Things can be \\\n",
        "obscured or missing from data (ex: can't know what others think)\n",
        "\n",
        "- Single/Multiagent: Crossword vs. chess. 2nd agent needs to have a perfmes, \\\n",
        "that depends on 1st agent's perfmes. Can be competitive or cooperative. \n",
        "\n",
        "- Deterministic/nondet: If can determine next state based on now+action. \\\n",
        "If partially observable could seem nondet. \n",
        "\n",
        "-- Stochastic - if deal w/ quantified probabilities \n",
        "\n",
        "- Episodic/Sequential: atomic steps, don't depend on each other.\n",
        "e.g. picking out parts on assembly line. Chess/driving are seq. \n",
        "\n",
        "- Static/Dynaic: Does env change while agent is thinking? Static means don't \\\n",
        "have to resample env. \n",
        "\n",
        "-- semidynamic: If env is static, but perfmes changes w/time. Ex. chess w/timer.\n",
        "\n",
        "- Discrete/continous: State, time, percpets, and actions. Chess is discrete\\\n",
        "(state, percept, action), driving is continous.\n",
        "\n",
        "- Known/unknown: Know physics of env? I.e outcome/probab of outcome for an action \\\n",
        "given or not? Can be known but partially observable. Ex: solitare.\n",
        "Can also be uknown but observable, ex: video game & controller. \n",
        "Perfmes can be uknown (designer don't know it or the user's pref,)\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\" agent is architecture + program\n",
        "**Simple reflex agent** select actions based only on current percept, not history\n",
        "**condition-action rule** – ex, break if car has lights on. Too simple, needs \\\n",
        "fully observable env. Otherwise might get stuck in loop (ex. robot w/o location)\\\n",
        "can use randomization to break out of infinite loops. In this case > simple reflex agent\\\n",
        "though usually not rational.\n",
        "\n",
        "**Model-based agent**\n",
        "Need to keep track of state to keep track of some unobserved parts of the world.\n",
        "1. Maintain knowledge of world physics, called transition model of the world.\n",
        "current state + action -> transition\n",
        "2. Also need info on how world translated to agent's percepts. Sensor model\n",
        "This is the best guess, not absolute certainty \n",
        "\n",
        "**goal-based agent**\n",
        "current state + transition model + goals -> action. Flexibile b/c can change goal\n",
        "\n",
        "**utility-based agent**\n",
        "Goals are more binary, utility as perfmes -> higher qual. Utility function and\\\n",
        "external perfmes need to line up.\n",
        "Try to maximize expected utility. Highest perfromance = rational.\n",
        "\n",
        "How to build these agents?\n",
        "**Learning agents**\n",
        "Has 4 parts:\n",
        "1. learning element: makes improvements\n",
        "2. performance element: select actions (basically the agent)\n",
        "3. Critic: gives feedback to learning el., says how perf el. needs to moded\n",
        "4. Problem generator: suggest actions that will lead to new experiences/explorations\n",
        "\n",
        "ways to represent components that rep the env:\n",
        "1.Atomic: single atom of knoweldge, ex: city name\n",
        "2.Factored: fixed variables/attributes w/ values. Ex. for driving: how much gas\\\n",
        "in tank, GPS coordinate\n",
        "3.Strcutred: entities & relations\n",
        "\n",
        "These are level of expresivness. Most expressive, can capture everything as less exp\\\n",
        "but more concisely. \n",
        "\n",
        "localist rep = 1:1 map concept to mem location\n",
        "distributed rep = rep is spread over mem locations\n",
        "distributed is more robust, withstand noise/dataloss\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "Descartes - I think therefore I am. Didn't think machines could replicate humans\n",
        "Turing - Can machines think too difficult. Can a machine reply in a way that can't \n",
        "be distinguished from a human? Can a machine pass\n",
        "\n",
        "Searle, says Turing's machine is too simple. Can just look up symbols and follow syntax.\n",
        "\n",
        "Eliza an early NLP threapist. Rogerian psychotherapy. \n",
        "\n",
        "Searle distinction betwee weak AI that just simulates thought and strong AI.\n",
        "Says biology is necessary for intelligence. \n",
        "\n",
        "Dan Dennett, remove brain from the body and have radio links to the body. Who is the person?\n",
        "The brain in the vat? or the body out in the field?\n",
        "If replace body, but also brain computations, same person?\n",
        "\n",
        "Rational agents - act rationally.\n",
        "agent fucntion maps sequence of percept vectors P to an action a from set A\n",
        "a math abstraction\n",
        "\n",
        "agent program runs on physical architeure to produce f. Agent = architecture + program.\n",
        "\n",
        "Agent is anything that percives its enviornment through sensors and actus on it\n",
        "through actuators. Thermostats also qualify - b/c senses temp and adjusts boilers.\n",
        "\n",
        "Rational beahvior - doing the right thing. AI is concerned with consequentialism,\n",
        "evaluate agents based on its consequences. Should require omniscience. \n",
        "\n",
        "Simon - bounded rationality, people choose alternatives they prefer. \n",
        "\n",
        "Use a performance measure to measure if agent was succsesful. Better to design one\n",
        "for  the behvaior you want to be achieved than for how the agent should behave. \n",
        "\n",
        "Rational agent choses the action that maximizes the expected value of its performance measure.\n",
        "\n",
        "Deterministic - know what happens after selecting an action.\n",
        "Non-deterministic - don't know what will happen. Could be many results. Games of chance\n",
        "Stochastic - Non-deterministic that can be quantified. \n",
        "\n",
        "Epsidoic - parts on an assembly line\n",
        "Sequential - current decision affects future actions \n",
        "\n",
        "Static vs. dynamic - nothing changes while thinking vs. changes while thinking.\n",
        "\n",
        "Discrete vs. continous - discrete states, particular moves that can take, continous,\n",
        "how the variables change\n",
        "\n",
        "Single agent vs mutli-agent: 1 agent or multiple each trying to max their own performance measure\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"ration agent\": \"one that acts to achieve the best outcome/best expected outcome\",\n",
        "\"natural language processing\" : \"use human language\",\n",
        "\"knowledge representation\": \"store knowledge & percepts\",\n",
        "\"automated reasoning\": \"answer qs and make inferences\",\n",
        "\"machine learning\": \"adapt to changes, find/deduce patterns\",\n",
        "\"computer vision\": \"perecption of enviornment\",\n",
        "\"robotics\": \"movement & interactions w/env\",\n",
        "\"introspection\": \"notice thinking as it happens\",\n",
        "\"psychological experiments\": \"observe people's behavior\",\n",
        "\"brain imaging\" : \"scans when person performs action\",\n",
        "\"weak AI\": \"machine action as though its can think - simultation\",\n",
        "\"strong AI\": \"machine can actually think; general AI\",\n",
        "\"Qualia\": \"instance of consciousness\",\n",
        "\"autonomy\": \"able to learn on its own\",\n",
        "\"task enviornment\": \"Perfromance, Enviornment, Actuators, Sensors\"\n",
        "\n",
        "\n",
        "\n",
        "}\n",
        "\n",
        "print(f\"chapter 2_1: word length:{len(chapter2_1.split(' '))} charchters: {len(chapter2_1)}\")\n",
        "print(f\"chapter 2_2: word length:{len(chapter2_2.split(' '))} charchters: {len(chapter2_2)}\")\n",
        "print(f\"chapter 2_3: word length:{len(chapter2_3.split(' '))} charchters: {len(chapter2_3)}\")\n",
        "print(f\"chapter 2_4: word length:{len(chapter2_4.split(' '))} charchters: {len(chapter2_4)}\")\n",
        "\n"
      ],
      "execution_count": 295,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "chapter 2_1: word length:62 charchters: 432\n",
            "chapter 2_2: word length:92 charchters: 661\n",
            "chapter 2_3: word length:186 charchters: 1272\n",
            "chapter 2_4: word length:259 charchters: 1857\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "953c8a1f-3b77-4fec-915f-c70b3ea97061"
      },
      "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": 296,
      "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/rational and thought/behavior.\nApproaches: \nTuring: cannot tell if response is from person or computer \nCognitive model: Compare how program solve w\\how computer solves. \nLaws othought: Use logic notation to solve problems, use probability to fill in certaintiy gap.\nRationl agent: More general than laws othought, more flexible as science develops, so better than just imitating behavior.\n\nStandard model focus on study/construction of agents that do the right thing\n\nValue alginemnt problem is that what we actualy want vs what we put into machine. \n\n\n## AIMA Chapter 27.1 The Limits of AI\n Turing said human behavior isn't guided by formal rules, use informal guideslines that are cannot be quantify/coded. Dreyfus, critique of GOFAI, simple agents \\ \nusing just logical rules.Embodied cogntion centers whole system, body, brain, enviornment. So sensors are very important.\nArgument from disability - can't do lovely things humans can. But over time lotsactually have done lots.\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Don't know if people think, but have polite convention to pretend they doChinese room from Searle argues computers don't just rule book. Biological naturalism mental states can only come from neurons. Don't need to solve consciousness questionto make parts of (e.g.e awarness, attention) intellegent systems\n\n## AIMA 2.1 Agents and Environments\n Agents percieve the enviornment via its sensors, and then makean action by actuators\nExample sensors: cameras, infrared. Example actuators: motors\nPercept is one thing that an agent's sensors percieves, and percept sequence is history of the perceptions.\nAgent func maps a _percept sequnce_ to actions. Would be a huge table b/c perceptsequences get infinte. Internally have agent program - actual implrementation on real system.\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n AI uses consquentalism, evaulate behavior based on conseuqneces,using performance measure that looks at sequence of states. Performance measures come from humans. Better to design perfmes for what one wants instead of how agent should behave.\n\nRationality depends on: \n1. Perfmes\n2. Prior knowledge of env\n3. Actions available\n4. Percept seq\n\nSo rational agent, for all percept seq, chose action to max perfmes based on current percseq and knowlege.\n\nRationality max expected perf. Not same as perfection (actual perf).\n\nInformation gatherin and exploration important to rationality. \n\nAgents with autonomy do better, b/c can learn. Need some base knowlegde.\n\n\n\n## AIMA 2.3 The Nature of Environments\n Task env needs to be specifed, give the Performance, Enviornment Actuators Sensors.\n\n- Fully observable/Partially: can percieve whole relevant env?. Things can be obscured or missing from data (ex: can't know what others think)\n\n- Single/Multiagent: Crossword vs. chess. 2nd agent needs to have a perfmes, that depends on 1st agent's perfmes. Can be competitive or cooperative. \n\n- Deterministic/nondet: If can determine next state based on now+action. If partially observable could seem nondet. \n\n-- Stochastic - if deal w/ quantified probabilities \n\n- Episodic/Sequential: atomic steps, don't depend on each other.\ne.g. picking out parts on assembly line. Chess/driving are seq. \n\n- Static/Dynaic: Does env change while agent is thinking? Static means don't have to resample env. \n\n-- semidynamic: If env is static, but perfmes changes w/time. Ex. chess w/timer.\n\n- Discrete/continous: State, time, percpets, and actions. Chess is discrete(state, percept, action), driving is continous.\n\n- Known/unknown: Know physics of env? I.e outcome/probab of outcome for an action given or not? Can be known but partially observable. Ex: solitare.\nCan also be uknown but observable, ex: video game & controller. \nPerfmes can be uknown (designer don't know it or the user's pref,)\n\n\n## AIMA 2.4 The Structure of Agents\n agent is architecture + program\n**Simple reflex agent** select actions based only on current percept, not history\n**condition-action rule** – ex, break if car has lights on. Too simple, needs fully observable env. Otherwise might get stuck in loop (ex. robot w/o location)can use randomization to break out of infinite loops. In this case > simple reflex agentthough usually not rational.\n\n**Model-based agent**\nNeed to keep track of state to keep track of some unobserved parts of the world.\n1. Maintain knowledge of world physics, called transition model of the world.\ncurrent state + action -> transition\n2. Also need info on how world translated to agent's percepts. Sensor model\nThis is the best guess, not absolute certainty \n\n**goal-based agent**\ncurrent state + transition model + goals -> action. Flexibile b/c can change goal\n\n**utility-based agent**\nGoals are more binary, utility as perfmes -> higher qual. Utility function andexternal perfmes need to line up.\nTry to maximize expected utility. Highest perfromance = rational.\n\nHow to build these agents?\n**Learning agents**\nHas 4 parts:\n1. learning element: makes improvements\n2. performance element: select actions (basically the agent)\n3. Critic: gives feedback to learning el., says how perf el. needs to moded\n4. Problem generator: suggest actions that will lead to new experiences/explorations\n\nways to represent components that rep the env:\n1.Atomic: single atom of knoweldge, ex: city name\n2.Factored: fixed variables/attributes w/ values. Ex. for driving: how much gasin tank, GPS coordinate\n3.Strcutred: entities & relations\n\nThese are level of expresivness. Most expressive, can capture everything as less expbut more concisely. \n\nlocalist rep = 1:1 map concept to mem location\ndistributed rep = rep is spread over mem locations\ndistributed is more robust, withstand noise/dataloss\n\n\n\n## Module 1 Lecture Notes\n\nDescartes - I think therefore I am. Didn't think machines could replicate humans\nTuring - Can machines think too difficult. Can a machine reply in a way that can't \nbe distinguished from a human? Can a machine pass\n\nSearle, says Turing's machine is too simple. Can just look up symbols and follow syntax.\n\nEliza an early NLP threapist. Rogerian psychotherapy. \n\nSearle distinction betwee weak AI that just simulates thought and strong AI.\nSays biology is necessary for intelligence. \n\nDan Dennett, remove brain from the body and have radio links to the body. Who is the person?\nThe brain in the vat? or the body out in the field?\nIf replace body, but also brain computations, same person?\n\nRational agents - act rationally.\nagent fucntion maps sequence of percept vectors P to an action a from set A\na math abstraction\n\nagent program runs on physical architeure to produce f. Agent = architecture + program.\n\nAgent is anything that percives its enviornment through sensors and actus on it\nthrough actuators. Thermostats also qualify - b/c senses temp and adjusts boilers.\n\nRational beahvior - doing the right thing. AI is concerned with consequentialism,\nevaluate agents based on its consequences. Should require omniscience. \n\nSimon - bounded rationality, people choose alternatives they prefer. \n\nUse a performance measure to measure if agent was succsesful. Better to design one\nfor  the behvaior you want to be achieved than for how the agent should behave. \n\nRational agent choses the action that maximizes the expected value of its performance measure.\n\nDeterministic - know what happens after selecting an action.\nNon-deterministic - don't know what will happen. Could be many results. Games of chance\nStochastic - Non-deterministic that can be quantified. \n\nEpsidoic - parts on an assembly line\nSequential - current decision affects future actions \n\nStatic vs. dynamic - nothing changes while thinking vs. changes while thinking.\n\nDiscrete vs. continous - discrete states, particular moves that can take, continous,\nhow the variables change\n\nSingle agent vs mutli-agent: 1 agent or multiple each trying to max their own performance measure\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Ration agent** - one that acts to achieve the best outcome/best expected outcome\n* **Natural language processing** - use human language\n* **Knowledge representation** - store knowledge & percepts\n* **Automated reasoning** - answer qs and make inferences\n* **Machine learning** - adapt to changes, find/deduce patterns\n* **Computer vision** - perecption of enviornment\n* **Robotics** - movement & interactions w/env\n* **Introspection** - notice thinking as it happens\n* **Psychological experiments** - observe people's behavior\n* **Brain imaging** - scans when person performs action\n* **Weak ai** - machine action as though its can think - simultation\n* **Strong ai** - machine can actually think; general AI\n* **Qualia** - instance of consciousness\n* **Autonomy** - able to learn on its own\n* **Task enviornment** - Perfromance, Enviornment, Actuators, Sensors\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "python is dynamically typed, variables come into existance when assigned\n",
        "Type can be updated so type(var) can change in different parts. Don't have type \n",
        "signatures\n",
        "\n",
        "no \"++\" or \"--\"\n",
        "\n",
        "can concat with +. \n",
        "r'\\n' is a raw string, won't be new line. \n",
        "\n",
        "Strings are immutable. So checking \"==\" checks if the two have the same value\n",
        "while \"is\" check if points to the same object\n",
        "\n",
        "y=x[:] is a shallow copy of any sequence (new object)\n",
        "\n",
        "tuple is immutable. Can be of mixed types\n",
        "string is immutable. All unicode, 2 byte chars. \n",
        "\n",
        "t[1:-1]: returns everything but the last item\n",
        "t[1:-1:2] every nth (2nd here) number\n",
        "t[:2] from start to 2nd item but not 3rd (i.e. index 2 not inclusive)\n",
        "t[2:] start from the 3rd item, to end. (i.e index 2 is inclusive)\n",
        "\n",
        "li.reverse() reverses in place\n",
        "li.sort() sorts list in place\n",
        "li.sort(fn) function by which to sort\n",
        "sorted(li) returns a copy of a sorted list\n",
        "\n",
        "s=\"Sentence with words\"\n",
        "words = s.split(\" \")\n",
        "\"_\".join(words)\n",
        "\n",
        "a.strip('-'), a.capitalize.() all return copies\n",
        "\n",
        "Dictionaries are unordered. Keys must be immutable. \n",
        "\n",
        "d.keys() gets list of keys, d.values() gets values, d.itesm() list item tuples\n",
        "defaultdict intializes nonexistan diciontary values\n",
        "collections import counter, counts \n",
        "\n",
        "Can return mutliple values by returning them with commas. Returned as tuple. \n",
        "\n",
        "No function overloading. Can have operator overloading by implementing magic methods.\n",
        "\n",
        "keyword arguments, allow function to be called outo f order. Used after all \n",
        "other agruments. ex: def fun(a, b, c), call fun(2, c=43, b=1)\n",
        "\n",
        "*args variable number of non-keyword arguments Can pass any number of args. \n",
        "Can give individual args, or pass a list and unapck it with *lst, ex. func(*lst)\n",
        "\n",
        "**kwargs any number of keyword arguments. Can pass a dictionary\n",
        "fun(**my_dict), so then key-value pairs, will become keyword arugments.\n",
        "\n",
        "Uses dynamic scope. Most recent value of global var. \n",
        "\n",
        "Can have subclasses by\n",
        "class Child_Cls(Parent_Class_Name):\n",
        "  def __init__(self, x, y):\n",
        "    Parent_Class.__init__(self, x, y)\n",
        "\n",
        "generators are less code than standard iterator, maintain local state automatically,\n",
        "Values are computed one at a time, so don't have to store the entire sequence in memory.\n",
        "Good for aggregating (summing/counting) in once pass, but bad if you need to check\n",
        "individual values. \n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 297,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 765
        },
        "outputId": "0ec1408d-e815-4f98-e5af-48c9f897dff9"
      },
      "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": 298,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\npython is dynamically typed, variables come into existance when assigned\nType can be updated so type(var) can change in different parts. Don't have type \nsignatures\n\nno \"++\" or \"--\"\n\ncan concat with +. \nr'\n' is a raw string, won't be new line. \n\nStrings are immutable. So checking \"==\" checks if the two have the same value\nwhile \"is\" check if points to the same object\n\ny=x[:] is a shallow copy of any sequence (new object)\n\ntuple is immutable. Can be of mixed types\nstring is immutable. All unicode, 2 byte chars. \n\nt[1:-1]: returns everything but the last item\nt[1:-1:2] every nth (2nd here) number\nt[:2] from start to 2nd item but not 3rd (i.e. index 2 not inclusive)\nt[2:] start from the 3rd item, to end. (i.e index 2 is inclusive)\n\nli.reverse() reverses in place\nli.sort() sorts list in place\nli.sort(fn) function by which to sort\nsorted(li) returns a copy of a sorted list\n\ns=\"Sentence with words\"\nwords = s.split(\" \")\n\"_\".join(words)\n\na.strip('-'), a.capitalize.() all return copies\n\nDictionaries are unordered. Keys must be immutable. \n\nd.keys() gets list of keys, d.values() gets values, d.itesm() list item tuples\ndefaultdict intializes nonexistan diciontary values\ncollections import counter, counts \n\nCan return mutliple values by returning them with commas. Returned as tuple. \n\nNo function overloading. Can have operator overloading by implementing magic methods.\n\nkeyword arguments, allow function to be called outo f order. Used after all \nother agruments. ex: def fun(a, b, c), call fun(2, c=43, b=1)\n\n*args variable number of non-keyword arguments Can pass any number of args. \nCan give individual args, or pass a list and unapck it with *lst, ex. func(*lst)\n\n**kwargs any number of keyword arguments. Can pass a dictionary\nfun(**my_dict), so then key-value pairs, will become keyword arugments.\n\nUses dynamic scope. Most recent value of global var. \n\nCan have subclasses by\nclass Child_Cls(Parent_Class_Name):\n  def __init__(self, x, y):\n    Parent_Class.__init__(self, x, y)\n\ngenerators are less code than standard iterator, maintain local state automatically,\nValues are computed one at a time, so don't have to store the entire sequence in memory.\nGood for aggregating (summing/counting) in once pass, but bad if you need to check\nindividual values. \n\n\n\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "72f20778-5b18-4c23-c019-47dcfcbd2bfc"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" In fully observable, det, known, envs the solution is a \\\n",
        "fixed set of actions.\n",
        "In that case can just exectue actions with sensor data. Called open loop.\n",
        "Otherwise you need to use close-loop to consider sensors.\n",
        "\n",
        "Search problem has possible envs - state space, with one it starts out in,\\\n",
        "the initial state.\n",
        "\n",
        "Then there is a goal state (can be multiple or alt)\n",
        "\n",
        "Has actions that the agent can take - applicable actions.\n",
        "Transition model says what the action will do.\n",
        "Action cost function - what's the cost of action _a_ when in _s_ to go to _s'_\n",
        "\n",
        "Solution is a path from intial to goal, optimal solution is lowest cost\n",
        "\n",
        "abstarction is **vlaid**  can translate into real world solution.\n",
        "**useful** if action easier in abstraction\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\" Robot nav is like route finding. 2d if just moving, but multi if has arms/legs;\\\n",
        "also have to deal with errors.\n",
        "\n",
        "Assemby sequenceing: figure out how to optimize the order of steps in assembly\"\"\"\n",
        "\n",
        "chapter3_3 = \"\"\"input into a search algorithm is a a serach problem and output is\\\n",
        "either a solution or failure. \n",
        "Search tree has paths from inital state to other states, including the goal.\\\n",
        "Each node is a state, can have multiple nodes for a state. State space can be infinite.\n",
        "\n",
        "In search start with root, then can expand the node, meaning eval actions, which \\\n",
        "generates new nodes corrpesonding to next state.\n",
        "\n",
        "Fronter are nodes that have been reached but not expanded.\n",
        "\n",
        "Best first search, decide which node to expand next using an eval function _f(n)_ \\\n",
        "expand node with min valu in _f(n)_. Expand if hasn't been reached before _or_ \\\n",
        "if new cost is lower than previous cost. \n",
        "\n",
        "Node has 4 parts:\n",
        "1. State\n",
        "2. Parent: node it came from\n",
        "3. Actions: what actions to parent caused to get to this state/node\n",
        "4. Path cost: total cost from inital state\n",
        "\n",
        "Represent frontier with a queue. Use hashtable to store reached. \n",
        "\n",
        "**Repeated states** mean that a tree can have a cycle (A-B-A), making the search tree infinite.\n",
        "More general case of **redundant path**, which visits unnecessary nodes. \n",
        "\n",
        "Graph search is different from tree-like search because it checks if there is a redundnat paths.\n",
        "Could also just check for cycles. Can do that by keeping track of parent, and if it reappeared.\n",
        "\n",
        "To eavluate an algorithm:\n",
        "1. Completness: find a solution if it exists/failure if doesn't?\n",
        "2. Cost optimality: lowest cost solution\n",
        "3. Time complexity: What's the time or _O()_?\n",
        "4. Space complexity: How much memory is needed? \n",
        "\n",
        "Completness tricky in infinite spaces b/c can keep following a path forever.\n",
        "Search needs to systematic in it's pathfinding to make sure it can reach a state.\n",
        "Ex: sprial path in infinite gird. But w/no solution can't terminate\n",
        "\n",
        "Measure time/space with:\n",
        "1. _d_/**depth**: # actions in best solution\n",
        "2. _m_ : max number of actions\n",
        "3. _b_/**branching factor**: # children for a node\n",
        "\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "BFS is good when equal cost actions. Expand root, then 1 level of chidren, then 2nd level etc..\n",
        "Works for infinte state spaces, b/c it's systemic. Similar to Best first, where _f(n)_ = depth(n)\n",
        "\n",
        "Use FIFO q, and set for states, b/c can't get a better path after 1st visit. \n",
        "\n",
        "Can use early goal testing b/c of that, where test if == goal when reach, rather than expand.\n",
        "Always finds the optimal path if all costs are same. If solution is at depth _d_ \\\n",
        "cost is:\n",
        "$$ 1 + b + b^2 + b^3 + ... + b^d = O(b^d)$$\n",
        "\n",
        "where _b_ is the branching factor. b/c at each level get #(b)s * b sucessors\n",
        "_O(b^d)_ for both time and space\n",
        "\n",
        "Too big of time and space for any medium/large problem.\n",
        "\n",
        "Dijkstra's algortihm = unifrom cost search, _f(n)_ is cost of path from root to node\n",
        "Can re-add items to frontier if find lower cost, do late-goal checking.\n",
        "Complexity is $$O(b^{1+\\lfloor(C^*/\\epsilon)\\rfloor})$$\n",
        "which is >> than $b^d$, b/c always explore all possible low-cost even if not in right direction.\n",
        "If all costs is same it's $b^{d+1}$\n",
        "\n",
        "DFS expands the deepest nodes, analogus to best first search w/ $f(n)$ is $-d$.\n",
        "Usually done as tree-search instead of graph search. Don't track visited nodes.\n",
        "Not optimal, first solution found is returned, which could be deeper than it \\\n",
        "needs to be.\n",
        "\n",
        "Complete for tree state spaces, for acylic it may revisit same state.\n",
        "For state spaces with cycles it might be in infite loop.\n",
        "In infinite spaces it can go on forever, not systemic. Which means it's not complete.\n",
        "\n",
        "Mem complexity is $O(bm)$, w/ b = branching factor, and m = max depth\n",
        "\n",
        "**Backtracking search** only have one successor node at time (not all), so use less memory.\n",
        "Dones't clone state to modify, so only keeps one state. so have a path of $O(m)$\n",
        "\n",
        "** Depth limited search**, limit the search only deapth $l$. So time complexity is\n",
        "$O(b^l)$ and space complexity is $O(bl)$. Can be incomplete if $l$ is too small.\n",
        "if know diameter of the graph can set $l$ to that.\n",
        "\n",
        "**Iterative deepening search**, don't pick $l$ but rather systematically increase\n",
        "it's value between iterations. \n",
        "Space complexity is $O(bd)$ when there is a solution and $O(bm)$ if no \\\n",
        "solution (finite graph). \n",
        "Optimal if all costs are equal, complete if acycilc or if check for cycles. \n",
        "Time complexity is $O(b^d)$, $O(b^m)$ if no solution.\n",
        "\n",
        "Same big O in time as BFS, though with higher constants. Ex: b = 10, d = 5\n",
        "$$N(IDS) = (d)b^1 + (d - 1)b^2 + (d - 2)b^3 + ...  + b^d$$\n",
        "$$N(IDS) = 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450$$\n",
        "$$N(BFS) = 10 + 100 + 1,000 + 10,000 + 100,000 = 111,110$$\n",
        "\n",
        "**Bidirection search**: search from initial state and backwards from goal state\n",
        "until they meet, better time comlexity b/c $b^{d/2} + b^{d/2} < b^{d}$\n",
        "if $f(n)$ is the path cost, and optimal cost is $C^*$ then at most cost of a  \\\n",
        "node will be $C^* /2$\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "Need \n",
        "1. A set of states\n",
        "2. an intial state\n",
        "3. Actions a set of possible actions\n",
        "4. Transition model - for all actions in a state, result of applying action in the state\n",
        "5. Path cost - perfmesure what is the cost, per perfmesure. Could be #actions, #miles\n",
        "6. Goal - test if a state is a goal state. \n",
        "\n",
        "What is the tranisition if apply action to a state in vaccum world? If in left and apply left\n",
        "stay in the same state. If apply right, new state. \n",
        "\n",
        "A solution is a sequence of actions from intial state to a goal state.\n",
        "Optimal solution has lowest path cost. \n",
        "\n",
        "State space - all states reachable from the inital state by some sequence\n",
        "Path - set of acitons between states\n",
        "Frontier - states that are available for expanding\n",
        "Solution - path from s_i to s_f,  where s_f = goal\n",
        "\n",
        "General process\n",
        "intialize frontier to intial state\n",
        "do\n",
        "  if frontier is empty then return Failure\n",
        "  choose a leaf node to expand by some strategy and remove from frontier\n",
        "  if node  state is the goal state reun solution\n",
        "  otherwise expand the node and add decendents to frontier. \n",
        "\n",
        "failure to detected repeated states makes linear problem exponential. Keep track\n",
        "of visited states to avoid revisiting. But state space can be large, so this\n",
        "can take up a lot of memory. \n",
        "\n",
        "Uninformed search - don't use any infromation from the world. All non-goal nodes look good.\n",
        "Search strategy = order of tree expansion. \n",
        "\n",
        "BFS - expand shallowest node first. Use a FIFO search \n",
        "DFS - expand deepest nodes. Not complete, fails in infite depth, loops. \n",
        "Not complete or optimal. Complete in finite spaces though. \n",
        "$O(b^m)$ is terrible if m is much larger than d. But if solutions are dense\n",
        "could be faster. Space is linear $O(b*m)$ b/c have to keep branches at least level\n",
        "\n",
        "DFS is better if space is restricted, lots of possible soluitions w/long paths\n",
        "and wrong paths end quickly.\n",
        "\n",
        "BFS if possibly infinte. Solutions have short paths. can quickly discared unlikely paths. \n",
        "\n",
        "IDDFS - increase the depth at each iteration. Explore all nodes at level 0, 1, 2...\n",
        "etc.. but in DFS order. Complete if no infinite paths. Time is $O(b^d)$, space is $O(bd)$\n",
        "optimal if step is 1\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",
        "\"goal formulation\": \"decide on objectives -> actions\",\n",
        "\"problem formulation\": \"describe the states/actions for goal\",\n",
        "\"solution\" : \"sequence of actions that gets to the goal\",\n",
        "\"standardized problem\": \"used to demo a method\",\n",
        "\"real-world-problem\": \"actually in the world, non-standard\",\n",
        "\"touring problem\": \"all points that must be visted\",\n",
        "\"TSP\": \"lik touring, visit all cites with lowest cost\",\n",
        "\"VLSI layout\": \"how to place componets/connect on a chip whil optimize area, delay\\\n",
        "max outpput\",\n",
        "\"Diameter\": \"max distance b/t 2 nodes in a graph\"    \n",
        "}\n",
        "\n",
        "print(f\"chapter 3_1: word length:{len(chapter3_1.split(' '))} charchters: {len(chapter3_1)}\")\n",
        "print(f\"chapter 3_2: word length:{len(chapter3_2.split(' '))} charchters: {len(chapter3_2)}\")\n",
        "print(f\"chapter 3_3: word length:{len(chapter3_3.split(' '))} charchters: {len(chapter3_3)}\")\n",
        "print(f\"chapter 3_4: word length:{len(chapter3_4.split(' '))} charchters: {len(chapter3_4)}\")\n"
      ],
      "execution_count": 299,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "chapter 3_1: word length:118 charchters: 728\n",
            "chapter 3_2: word length:33 charchters: 190\n",
            "chapter 3_3: word length:293 charchters: 1865\n",
            "chapter 3_4: word length:474 charchters: 2792\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "44e8f180-40a0-4135-c426-fbdf98893637"
      },
      "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": 300,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n In fully observable, det, known, envs the solution is a fixed set of actions.\nIn that case can just exectue actions with sensor data. Called open loop.\nOtherwise you need to use close-loop to consider sensors.\n\nSearch problem has possible envs - state space, with one it starts out in,the initial state.\n\nThen there is a goal state (can be multiple or alt)\n\nHas actions that the agent can take - applicable actions.\nTransition model says what the action will do.\nAction cost function - what's the cost of action _a_ when in _s_ to go to _s'_\n\nSolution is a path from intial to goal, optimal solution is lowest cost\n\nabstarction is **vlaid**  can translate into real world solution.\n**useful** if action easier in abstraction\n\n\n\n\n## AIMA Chapter 3.2 Example Problems\n Robot nav is like route finding. 2d if just moving, but multi if has arms/legs;also have to deal with errors.\n\nAssemby sequenceing: figure out how to optimize the order of steps in assembly\n\n## AIMA Chapter 3.3 Search Algorithms\ninput into a search algorithm is a a serach problem and output iseither a solution or failure. \nSearch tree has paths from inital state to other states, including the goal.Each node is a state, can have multiple nodes for a state. State space can be infinite.\n\nIn search start with root, then can expand the node, meaning eval actions, which generates new nodes corrpesonding to next state.\n\nFronter are nodes that have been reached but not expanded.\n\nBest first search, decide which node to expand next using an eval function _f(n)_ expand node with min valu in _f(n)_. Expand if hasn't been reached before _or_ if new cost is lower than previous cost. \n\nNode has 4 parts:\n1. State\n2. Parent: node it came from\n3. Actions: what actions to parent caused to get to this state/node\n4. Path cost: total cost from inital state\n\nRepresent frontier with a queue. Use hashtable to store reached. \n\n**Repeated states** mean that a tree can have a cycle (A-B-A), making the search tree infinite.\nMore general case of **redundant path**, which visits unnecessary nodes. \n\nGraph search is different from tree-like search because it checks if there is a redundnat paths.\nCould also just check for cycles. Can do that by keeping track of parent, and if it reappeared.\n\nTo eavluate an algorithm:\n1. Completness: find a solution if it exists/failure if doesn't?\n2. Cost optimality: lowest cost solution\n3. Time complexity: What's the time or _O()_?\n4. Space complexity: How much memory is needed? \n\nCompletness tricky in infinite spaces b/c can keep following a path forever.\nSearch needs to systematic in it's pathfinding to make sure it can reach a state.\nEx: sprial path in infinite gird. But w/no solution can't terminate\n\nMeasure time/space with:\n1. _d_/**depth**: # actions in best solution\n2. _m_ : max number of actions\n3. _b_/**branching factor**: # children for a node\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBFS is good when equal cost actions. Expand root, then 1 level of chidren, then 2nd level etc..\nWorks for infinte state spaces, b/c it's systemic. Similar to Best first, where _f(n)_ = depth(n)\n\nUse FIFO q, and set for states, b/c can't get a better path after 1st visit. \n\nCan use early goal testing b/c of that, where test if == goal when reach, rather than expand.\nAlways finds the optimal path if all costs are same. If solution is at depth _d_ cost is:\n$$ 1 + b + b^2 + b^3 + ... + b^d = O(b^d)$$\n\nwhere _b_ is the branching factor. b/c at each level get #(b)s * b sucessors\n_O(b^d)_ for both time and space\n\nToo big of time and space for any medium/large problem.\n\nDijkstra's algortihm = unifrom cost search, _f(n)_ is cost of path from root to node\nCan re-add items to frontier if find lower cost, do late-goal checking.\nComplexity is $$O(b^{1+\\lfloor(C^*/\\epsilon)\rfloor})$$\nwhich is >> than $b^d$, b/c always explore all possible low-cost even if not in right direction.\nIf all costs is same it's $b^{d+1}$\n\nDFS expands the deepest nodes, analogus to best first search w/ $f(n)$ is $-d$.\nUsually done as tree-search instead of graph search. Don't track visited nodes.\nNot optimal, first solution found is returned, which could be deeper than it needs to be.\n\nComplete for tree state spaces, for acylic it may revisit same state.\nFor state spaces with cycles it might be in infite loop.\nIn infinite spaces it can go on forever, not systemic. Which means it's not complete.\n\nMem complexity is $O(bm)$, w/ b = branching factor, and m = max depth\n\n**Backtracking search** only have one successor node at time (not all), so use less memory.\nDones't clone state to modify, so only keeps one state. so have a path of $O(m)$\n\n** Depth limited search**, limit the search only deapth $l$. So time complexity is\n$O(b^l)$ and space complexity is $O(bl)$. Can be incomplete if $l$ is too small.\nif know diameter of the graph can set $l$ to that.\n\n**Iterative deepening search**, don't pick $l$ but rather systematically increase\nit's value between iterations. \nSpace complexity is $O(bd)$ when there is a solution and $O(bm)$ if no solution (finite graph). \nOptimal if all costs are equal, complete if acycilc or if check for cycles. \nTime complexity is $O(b^d)$, $O(b^m)$ if no solution.\n\nSame big O in time as BFS, though with higher constants. Ex: b = 10, d = 5\n$$N(IDS) = (d)b^1 + (d - 1)b^2 + (d - 2)b^3 + ...  + b^d$$\n$$N(IDS) = 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450$$\n$$N(BFS) = 10 + 100 + 1,000 + 10,000 + 100,000 = 111,110$$\n\n**Bidirection search**: search from initial state and backwards from goal state\nuntil they meet, better time comlexity b/c $b^{d/2} + b^{d/2} < b^{d}$\nif $f(n)$ is the path cost, and optimal cost is $C^*$ then at most cost of a  node will be $C^* /2$\n\n\n\n## Module 3 Lecture Notes\n\nNeed \n1. A set of states\n2. an intial state\n3. Actions a set of possible actions\n4. Transition model - for all actions in a state, result of applying action in the state\n5. Path cost - perfmesure what is the cost, per perfmesure. Could be #actions, #miles\n6. Goal - test if a state is a goal state. \n\nWhat is the tranisition if apply action to a state in vaccum world? If in left and apply left\nstay in the same state. If apply right, new state. \n\nA solution is a sequence of actions from intial state to a goal state.\nOptimal solution has lowest path cost. \n\nState space - all states reachable from the inital state by some sequence\nPath - set of acitons between states\nFrontier - states that are available for expanding\nSolution - path from s_i to s_f,  where s_f = goal\n\nGeneral process\nintialize frontier to intial state\ndo\n  if frontier is empty then return Failure\n  choose a leaf node to expand by some strategy and remove from frontier\n  if node  state is the goal state reun solution\n  otherwise expand the node and add decendents to frontier. \n\nfailure to detected repeated states makes linear problem exponential. Keep track\nof visited states to avoid revisiting. But state space can be large, so this\ncan take up a lot of memory. \n\nUninformed search - don't use any infromation from the world. All non-goal nodes look good.\nSearch strategy = order of tree expansion. \n\nBFS - expand shallowest node first. Use a FIFO search \nDFS - expand deepest nodes. Not complete, fails in infite depth, loops. \nNot complete or optimal. Complete in finite spaces though. \n$O(b^m)$ is terrible if m is much larger than d. But if solutions are dense\ncould be faster. Space is linear $O(b*m)$ b/c have to keep branches at least level\n\nDFS is better if space is restricted, lots of possible soluitions w/long paths\nand wrong paths end quickly.\n\nBFS if possibly infinte. Solutions have short paths. can quickly discared unlikely paths. \n\nIDDFS - increase the depth at each iteration. Explore all nodes at level 0, 1, 2...\netc.. but in DFS order. Complete if no infinite paths. Time is $O(b^d)$, space is $O(bd)$\noptimal if step is 1\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Goal formulation** - decide on objectives -> actions\n* **Problem formulation** - describe the states/actions for goal\n* **Solution** - sequence of actions that gets to the goal\n* **Standardized problem** - used to demo a method\n* **Real-world-problem** - actually in the world, non-standard\n* **Touring problem** - all points that must be visted\n* **Tsp** - lik touring, visit all cites with lowest cost\n* **Vlsi layout** - how to place componets/connect on a chip whil optimize area, delaymax outpput\n* **Diameter** - max distance b/t 2 nodes in a graph\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5ec2aa2f-b154-4ff2-ece4-017d2fe9df92"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" \n",
        "**Greedy best first search**, chooses node w/lowest $h(n) to expand, making it\n",
        "Not always optimal cost. \n",
        "\n",
        "time and space complxity is $O(abs(V))$ but can reduce on certain problems to $O(bm)$\n",
        "\n",
        "$h(n)$ is **consistent** if $$h(n) <= c(n, a, n') + h(n')$$\n",
        "That is the (est cost of n -> goal) <= (cost n -> n') + (est cost of n' -> goal)\n",
        "this is the triangle inequality\n",
        "\n",
        "consistent heuristic => admissible, but admissible not necessairly consistent \n",
        "\n",
        "consistent heuristic never repeat states, so don't renter into reached\n",
        "\n",
        "If $h(n)$ is inadmissible, A* might be optimal.  If there is an optimal\n",
        "path where $h(n)$ is admissible for every node on that path \n",
        "\n",
        "Or if optimal cost is $C$, and 2nd best is $C_2$, and $h(n) <= truecost(n)+C_2-C$\n",
        "\n",
        "Costs of $g(n)$ are mono increase. But costs of $h(n)$ are only mono increase\n",
        "if consistent. \n",
        "\n",
        "A\\* is **optimally efficient**. It\n",
        "1. expands all neighbs of inital state w/ $f(n)<C^*$, \n",
        "2. might expand some nodes that are $f(n)=C^*$$, \n",
        "3. Doesnt' expand nodes with $f(n)>C^*$\n",
        " \n",
        "**Satisficing** solutions not optimal but acceptable. Might use inadmissible heuristic\n",
        "\n",
        "**Weighted A\\* Search** weight the heuristic so $f(n)=g(n)+W*h(n)$, $W>1$.\n",
        "Will get a soultion that's between $C^* and W*C^*$\n",
        "\n",
        "**Bounded suboptimal search** look for solution w/cost <= $W*C^*$\n",
        "\n",
        "**Bounded-cost** sol is less than some $C$\n",
        "**unbounded-cost** accept any fast found sol. Ex. speedy search\n",
        "$h(n) = count(actions(n))$\n",
        "\n",
        "$A\\*$  uses memory $O(b^d)$. Can try an implement where keep state only in \n",
        "_reached_ or _frontier_, not both. Or remove state from _reached_ if no longer needed. \n",
        "Ex. don't allow U turns, So only check _frontier_, no need for _reached_.\n",
        "\n",
        "Or can use **reference count** of # times state has been reached,\n",
        "remove it if can't be reached again after a certain count.\n",
        "in grid world has 4 neighbs, so can only reach it 4 times. \n",
        "\n",
        "**Beam search** put a limit on frontier size. Only keep a certain # of nodes\n",
        "with the best $f(n)$. Incomplete and suboptimal. Can be near-optimal. Like a \n",
        "very focused version of search. Can also keep all node w/ $f(n)$ that is $<= \\delta +$ \n",
        "the best $f(n)$.\n",
        "\n",
        "**Iterative-deepening A\\* Search** like IDDFS. Don't have to keep all reached in mem\n",
        "but added cost of repeat visits of states. Cutoff is $f(n)$, updated to be the smallest\n",
        "$f(n)$ that missed the cutoff in pervious round. Good for integer $f(n)$s b/c\n",
        "can't have more iterations that the $C^*$, but if f cost is diff for every node\n",
        "then number of iteraitons could be the same as the # of states\n",
        "\n",
        "**RBFS** and **IDA\\* ** use too little memory. \n",
        "\n",
        "**Memory bounded A\\* ** and Simplified. Keep as many as mem allows, then drop worst leaf.\n",
        "But back up value of forgotten leaf to parent. Expands newest- and deletes oldest- best.\n",
        "\n",
        "SMA is complete if $d$ < mem size. Optimal if optimal solution is <= $d$ < mem size.\n",
        "\n",
        "SMA is good when node generation more expensive than frontier/reached set. \n",
        "\n",
        "Mem limitations can make it impossible to solve, if need to regenerate nodes. \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\" effective branching factor, number of nodes to expand to get to solution\n",
        "$$ N = b^* + (b^*)^2 + ... + (b^*)^d$$\n",
        "\n",
        "Better heuristic has a b* closer to 1. Another measure is reduction of effective depth. \n",
        "By $k_h$ amount so cost is $O(b^{d-k_h})$\n",
        "\n",
        "If heuristic h2 always >= h1, h2 **dominates** h1.\n",
        "\n",
        "Relaxed problem removes some restriction on problem actions, to help generate _h_.\n",
        "Leads to a expanded graph of the original problem graph.\n",
        "Heuristic needs to be easy to generate, solve problem w/o search\n",
        "If have multiple heursitcs can use a composite, picking the highest one for a node.\n",
        "\n",
        "Can have a database of suproblems of original problem, storing solution for\n",
        "every possible subproblem. Go from goal to other permutation, storing cost.\n",
        "Then heuristic becomes a lookup. Can do it from multiple instances of the subproblem,\n",
        "and the combine the heuristic by taking the max of $h_i(n)$. Can't add b/c overlap costs.\n",
        "Could only count of pieces that are important in subproblem, making a **disjoint pattern database**.\n",
        "\n",
        "Mapping services use precomputation between points. Do it with landmarks. Fo every L,\n",
        "and every v find optimal path v->L. Storing the costs creates an inaddmissible heuristic.\n",
        "where $h(n) = min [ C(n,L) + C(L, goal)]$ for Ls\n",
        "\n",
        "Can be admissilbe if use $h(n) = max [ C(n,L) - C(goal, L)]. Chose a landmark beyond the goal,\n",
        "and subtract the extra distance beyond the goal. \n",
        "\n",
        "Pick landmarks by finding center of graph and then adding Ls furthest out around the center.\n",
        "\n",
        "Metalevel state space - the internal state space of the algorithm. \n",
        "ex. each state is a search tree. Can use learnig to see which paths in the metalevel\n",
        "are not helpful. Goals is minimize computationl cost + path cost. \n",
        "\n",
        "Can use features in machine learning to improve heuristic generation. Ex. x1\n",
        "num of misplaced tiles, or x2, adjustcent tiles that shouldn't be. Can combine\n",
        "features with $h(n)= c_1x_1(n) + c_2x_2(n)$. Not necessarily admissible or consistent\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" \n",
        "Uniform cost search - costs are **not** actually uniform. Edge weights actually matter.\n",
        "Path cost is the generally the cost of transitioning from one node to the next.\n",
        "Monotonically increasing. \n",
        "\n",
        "UCS - expands the node with lowest path cost. Use a priority queue orderd by g(n)\n",
        "Different from BFS, test for goal when selected for expansion in UCS, not when \n",
        "added to frontier as in BFS. B/C can reach node from multiple places. \n",
        "$f(n) = g(n)$\n",
        "\n",
        "Informed search\n",
        "Use an estiamte to distance to the goal.\n",
        "Best-first earch: node sleected for expansinon based on eval function $f(n)$\n",
        "$f(n)$ can also include a estimate of the distance to the goal.\n",
        "Priority queue based on $f(n)$.\n",
        "3 covered: uniform cost, greedy,  and A\\*\n",
        "\n",
        "Greedy search, expand based on estimate to goal, ignore path cost. So only $h(n)$\n",
        "if true cost is lower migtht be lower than found cost, if esimtate is way off.\n",
        "Not optimal, and not complete can get stuck in loops.  \n",
        "$f(n) = h(n)$\n",
        "\n",
        "A\\* search is bes known form of best-first earch. Avoid expanding paths that are \n",
        "already expensive, expand most promising ones first\n",
        "$f(n) = g(n) + h(n)$\n",
        "\n",
        "**admisisible** if never overestimates the cost to the goal, it's optimisic.\n",
        "$h(n) \\leq h\\*(n)$ where $h\\*$ is the the true cost from n\n",
        "$h(n) \\geq 0$ $h(G)$ = 0 for a goal. Straight line distance never overstimates\n",
        "actual road distance. \n",
        "\n",
        "if H(n) is admissible, A\\* in Tree Search is optimal\n",
        "\n",
        "admissible, slows down bad paths. Inadmissible ones push good paths in the frontier.\n",
        "Don't return a goal node until we expand it, because needs to be at top of frontier,\n",
        "b/c can have shorter paths than the first one. \n",
        "\n",
        "Relaxed contraints, reduce some of the rules in the problem. Ex: move a tile anywhere,\n",
        "or any adjustent square. The cost of a relaxed problem is a lower bound on the cost \n",
        "of the origianl \n",
        "\n",
        "$h_2(n) \\geq h_1(n)$ and both are admissible, then $h_2$ dominates $h_1$. $h_2$\n",
        "is more accurate than $h_1$. Expand fewer nodes with a better (more dominante) heuristic.\n",
        "\n",
        "$h\\*(n)$ is the best possible heuristic (oracle), dominates all. \n",
        "0 is the worst admissible heuristic, dominated by all. \n",
        "\n",
        "in uniform cost serach, it's like A\\* where $h(n)$=0 for all. \n",
        "\n",
        " \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "print(f\"chapter 3_5: word length:{len(chapter3_5.split(' '))} charchters: {len(chapter3_5)}\")\n",
        "print(f\"chapter 3_6: word length:{len(chapter3_6.split(' '))} charchters: {len(chapter3_6)}\")\n",
        "\n"
      ],
      "execution_count": 301,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "chapter 3_5: word length:474 charchters: 2985\n",
            "chapter 3_6: word length:305 charchters: 1948\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "280bbbeb-610d-481e-ebeb-b9dc4842c450"
      },
      "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\", module3_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": 302,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n**Greedy best first search**, chooses node w/lowest $h(n) to expand, making it\nNot always optimal cost. \n\ntime and space complxity is $O(abs(V))$ but can reduce on certain problems to $O(bm)$\n\n$h(n)$ is **consistent** if $$h(n) <= c(n, a, n') + h(n')$$\nThat is the (est cost of n -> goal) <= (cost n -> n') + (est cost of n' -> goal)\nthis is the triangle inequality\n\nconsistent heuristic => admissible, but admissible not necessairly consistent \n\nconsistent heuristic never repeat states, so don't renter into reached\n\nIf $h(n)$ is inadmissible, A* might be optimal.  If there is an optimal\npath where $h(n)$ is admissible for every node on that path \n\nOr if optimal cost is $C$, and 2nd best is $C_2$, and $h(n) <= truecost(n)+C_2-C$\n\nCosts of $g(n)$ are mono increase. But costs of $h(n)$ are only mono increase\nif consistent. \n\nA\\* is **optimally efficient**. It\n1. expands all neighbs of inital state w/ $f(n)<C^*$, \n2. might expand some nodes that are $f(n)=C^*$$, \n3. Doesnt' expand nodes with $f(n)>C^*$\n \n**Satisficing** solutions not optimal but acceptable. Might use inadmissible heuristic\n\n**Weighted A\\* Search** weight the heuristic so $f(n)=g(n)+W*h(n)$, $W>1$.\nWill get a soultion that's between $C^* and W*C^*$\n\n**Bounded suboptimal search** look for solution w/cost <= $W*C^*$\n\n**Bounded-cost** sol is less than some $C$\n**unbounded-cost** accept any fast found sol. Ex. speedy search\n$h(n) = count(actions(n))$\n\n$A\\*$  uses memory $O(b^d)$. Can try an implement where keep state only in \n_reached_ or _frontier_, not both. Or remove state from _reached_ if no longer needed. \nEx. don't allow U turns, So only check _frontier_, no need for _reached_.\n\nOr can use **reference count** of # times state has been reached,\nremove it if can't be reached again after a certain count.\nin grid world has 4 neighbs, so can only reach it 4 times. \n\n**Beam search** put a limit on frontier size. Only keep a certain # of nodes\nwith the best $f(n)$. Incomplete and suboptimal. Can be near-optimal. Like a \nvery focused version of search. Can also keep all node w/ $f(n)$ that is $<= \\delta +$ \nthe best $f(n)$.\n\n**Iterative-deepening A\\* Search** like IDDFS. Don't have to keep all reached in mem\nbut added cost of repeat visits of states. Cutoff is $f(n)$, updated to be the smallest\n$f(n)$ that missed the cutoff in pervious round. Good for integer $f(n)$s b/c\ncan't have more iterations that the $C^*$, but if f cost is diff for every node\nthen number of iteraitons could be the same as the # of states\n\n**RBFS** and **IDA\\* ** use too little memory. \n\n**Memory bounded A\\* ** and Simplified. Keep as many as mem allows, then drop worst leaf.\nBut back up value of forgotten leaf to parent. Expands newest- and deletes oldest- best.\n\nSMA is complete if $d$ < mem size. Optimal if optimal solution is <= $d$ < mem size.\n\nSMA is good when node generation more expensive than frontier/reached set. \n\nMem limitations can make it impossible to solve, if need to regenerate nodes. \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n effective branching factor, number of nodes to expand to get to solution\n$$ N = b^* + (b^*)^2 + ... + (b^*)^d$$\n\nBetter heuristic has a b* closer to 1. Another measure is reduction of effective depth. \nBy $k_h$ amount so cost is $O(b^{d-k_h})$\n\nIf heuristic h2 always >= h1, h2 **dominates** h1.\n\nRelaxed problem removes some restriction on problem actions, to help generate _h_.\nLeads to a expanded graph of the original problem graph.\nHeuristic needs to be easy to generate, solve problem w/o search\nIf have multiple heursitcs can use a composite, picking the highest one for a node.\n\nCan have a database of suproblems of original problem, storing solution for\nevery possible subproblem. Go from goal to other permutation, storing cost.\nThen heuristic becomes a lookup. Can do it from multiple instances of the subproblem,\nand the combine the heuristic by taking the max of $h_i(n)$. Can't add b/c overlap costs.\nCould only count of pieces that are important in subproblem, making a **disjoint pattern database**.\n\nMapping services use precomputation between points. Do it with landmarks. Fo every L,\nand every v find optimal path v->L. Storing the costs creates an inaddmissible heuristic.\nwhere $h(n) = min [ C(n,L) + C(L, goal)]$ for Ls\n\nCan be admissilbe if use $h(n) = max [ C(n,L) - C(goal, L)]. Chose a landmark beyond the goal,\nand subtract the extra distance beyond the goal. \n\nPick landmarks by finding center of graph and then adding Ls furthest out around the center.\n\nMetalevel state space - the internal state space of the algorithm. \nex. each state is a search tree. Can use learnig to see which paths in the metalevel\nare not helpful. Goals is minimize computationl cost + path cost. \n\nCan use features in machine learning to improve heuristic generation. Ex. x1\nnum of misplaced tiles, or x2, adjustcent tiles that shouldn't be. Can combine\nfeatures with $h(n)= c_1x_1(n) + c_2x_2(n)$. Not necessarily admissible or consistent\n\n\n\n## Module 4 Lecture Notes\n\nNeed \n1. A set of states\n2. an intial state\n3. Actions a set of possible actions\n4. Transition model - for all actions in a state, result of applying action in the state\n5. Path cost - perfmesure what is the cost, per perfmesure. Could be #actions, #miles\n6. Goal - test if a state is a goal state. \n\nWhat is the tranisition if apply action to a state in vaccum world? If in left and apply left\nstay in the same state. If apply right, new state. \n\nA solution is a sequence of actions from intial state to a goal state.\nOptimal solution has lowest path cost. \n\nState space - all states reachable from the inital state by some sequence\nPath - set of acitons between states\nFrontier - states that are available for expanding\nSolution - path from s_i to s_f,  where s_f = goal\n\nGeneral process\nintialize frontier to intial state\ndo\n  if frontier is empty then return Failure\n  choose a leaf node to expand by some strategy and remove from frontier\n  if node  state is the goal state reun solution\n  otherwise expand the node and add decendents to frontier. \n\nfailure to detected repeated states makes linear problem exponential. Keep track\nof visited states to avoid revisiting. But state space can be large, so this\ncan take up a lot of memory. \n\nUninformed search - don't use any infromation from the world. All non-goal nodes look good.\nSearch strategy = order of tree expansion. \n\nBFS - expand shallowest node first. Use a FIFO search \nDFS - expand deepest nodes. Not complete, fails in infite depth, loops. \nNot complete or optimal. Complete in finite spaces though. \n$O(b^m)$ is terrible if m is much larger than d. But if solutions are dense\ncould be faster. Space is linear $O(b*m)$ b/c have to keep branches at least level\n\nDFS is better if space is restricted, lots of possible soluitions w/long paths\nand wrong paths end quickly.\n\nBFS if possibly infinte. Solutions have short paths. can quickly discared unlikely paths. \n\nIDDFS - increase the depth at each iteration. Explore all nodes at level 0, 1, 2...\netc.. but in DFS order. Complete if no infinite paths. Time is $O(b^d)$, space is $O(bd)$\noptimal if step is 1\n\n\n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1bc0d2e5-4d67-48fd-de1e-dd0820201843"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Zero sum games, only 1 winner. \n",
        "Max moves first\n",
        "game tree is a search tree with all moves to game end (i.e. terminal state). \n",
        "\n",
        "can either use a eval function to tell who is winning or run simulations.\n",
        "\n",
        "Have $S_0$, intila state, \n",
        "To-Move(s): current player\n",
        "Actions(s): Actions in state S\n",
        "Result(s, a): What is result of action in a state\n",
        "Is-Termina(s): Is the game over?\n",
        "Utility(s,p): What's the score the player?\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter5_2 = \"\"\" Ply is a move by a single player\n",
        "Evaluate the max utility based on each action, knowing subsequent action by min.\n",
        "\n",
        "Might not always be best to do a optimal move when playing a suboptimal player,\n",
        "can take a risk if porbablity of good move is high, and think min player won't \n",
        "find its optimal move.\n",
        "\n",
        "Minimax uses DFS, if b moves at teach step, with max depth m, $O(b^m)$ time complexity.\n",
        "If generate all actions then $O(bm)$, if one at a time then $O(m)\n",
        "\n",
        "In multiplayer games, backup the value of the max for the player whose turn it is at the leaf\n",
        "\n",
        "Alliances can form in multiplayer games b/t weaker position players. Can also form\n",
        "in 2 player non-zero-sum games. \n",
        "\n",
        "**Alpha-beta pruning** \n",
        "$\\alpha$ is highest value along the path for max, value be at least that much\n",
        "$\\beta$ is the lowset value along the path for min, value at most that much\n",
        "if value < $\\alpha$ for min, or > $\\beta$ for max, return.\n",
        "\n",
        "If leaves are ordered best to worst, would have $O(b^{m/2}$, branching factor would be $b^{1/2}$\n",
        "If randomly guess would have $O(b^{3m/4})$.\n",
        "\n",
        "Killer moves are the best moves. If try them first for killer move heuristic.\n",
        "\n",
        "Can reduce redundency by keeping a **transposition table** that is a table of\n",
        "the heurisitc value of states. \n",
        "\n",
        "**Type A stragegy**, limit all moves up to a depth, and estimate the utility. Width over depth. Chess\n",
        "**Type B stargegy**, go only with most promising moves as far as possible. Depth over width.  Go.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter5_3 = \"\"\" \n",
        "For heuristic a-b search,use eval func to estimate util of state, and decide if \n",
        "to cut it off before terminal state.\n",
        "\n",
        "eval vunction is somewhere betwen win and loss. Can work calculating\n",
        "features of state (ex. #whit-pawns). Then has probability of win given features\n",
        "grouped into categories. \n",
        "\n",
        "Since above is too expeirence depednent, eval each feature and combine. Ex.\n",
        "give value to each chess piece. Then arrangement might be another feature.\n",
        "$$Eval(s)  = \\sum_{i=1}^n {W_if_i(s)}$$\n",
        "eval func needs to be correlated to chance of winning, can be non-linear.\n",
        "\n",
        "Can cutoff after reaching a certain depth, retrun the eval for the player\n",
        "of the state at that depth.\n",
        "\n",
        "Eval func should only be applied when the position is **quiescent**, no upcoming\n",
        "move that will change the eval a lot. Otherwise need to continue the search.\n",
        "Can limit quiescent search to only certain important moves.\n",
        "\n",
        "**Horizion effect** delay inevitable move to later time.\n",
        "**Singular extensions** add moves that are def better than all others.\n",
        "\n",
        "**Forward pruning** removes moves that seem bad, but might be good. Saves\n",
        "comp but could result in mistake. Type B strate.\n",
        "\n",
        "Probcut algorithm prunes out nodes that are probably not in [$\\alpha$, $\\beta$]\n",
        "\n",
        "late move reduction - reduce depth of search for later moves.\n",
        "\n",
        "Can use table lookup for the opening and ending of chess. Then can switch to search.\n",
        "**Policy** maps a state to the best move. Retrograde minimax, ex. reverse\n",
        "moves from wining positions in chess.\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter5_5 = \"\"\"Stochastic games have an aspect of chance. Needs to include\n",
        "chance nodes in the search, + max/min nodes.\n",
        "\n",
        "need to calculate the expected value of a position - the **expectiminimiax** val.\n",
        "\n",
        "if want to use an approx with cutoff search, need to use values that are pos\n",
        "linear transfomrations for probability. \n",
        "\n",
        "Time complexity is $O(b^mn^m)$ where n is number of rolls (i.e. possibilities)\n",
        "\n",
        "Can prune chance nodes by bounding utility values.\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" \n",
        "Decision theory is about choosing an action based on immediate result. Assume\n",
        "episodic env. **Utilitity funcion** evals a state, and **expected utility** is the avg.\n",
        "utility value of outomes * probability that it happens. \n",
        "\n",
        "**Max expected utility (MEU)** has rational agent pick the action with\n",
        "max expected utility. \n",
        "\n",
        "Doesn't operationalize AI rationality though. Still need to estimate probabilities\n",
        "of states and possibly search for uitilities of states. \n",
        "\n",
        "Util function applies step by step. If agent maxes it and it reflects perfmes\n",
        "then it will have best perfmes.\n",
        "\n",
        "\"\"\"\n",
        "chapter16_2 = \"\"\" \n",
        "Outcomes for actions are a lottery L =[$p_1,S_1; p_2S_2, ... p_n,S_n$],\n",
        "and each S_i can be a state or a lottery. \n",
        "\n",
        "6 constraints for prefrence relations - axioms of utility theory:\n",
        "1. Orderability: Either A > B, B > A or A~B\n",
        "2. Transitivity: (A > B) $\\wedge$ (B > C) => A > C\n",
        "3. Continuity: indifferent between a lottery for [A,C], and p =1 B \n",
        "A > B > C => $\\exists$ p [p,A; 1-p, C] ~ B\n",
        "4. Substitutability: if indifferent between two lotteries, then also indifferent about\n",
        "complex lotteries that just sub the original lotterires:\n",
        " A ~ B => [p, A; 1 - p, C] ~ [p, B; 1 - p, C]\n",
        "\n",
        "5. Monotonicity: If A > B, then prefer lottery that has higher probability of A\n",
        " A > B => (p > q <=> [p,A; 1 - p, B] > [q, A; 1 - q, B])\n",
        "6. Decomposability: can use probabilities to decompose a lottery to simpler verison\n",
        "[p, A; 1-p, [q,B; 1 - q, C]] ~ [p, A; (1 - p)q,B; (1 - p)(1 - q),C]\n",
        "\n",
        "Axioms lead to:\n",
        "1. Existence of utility function: have to have a Util func to be consistent w/axiom.\n",
        "2. Expected utility of lottery: sum of probabilities times U(outcome)\n",
        "\n",
        "util function not necessirly unique. Can tranfrom util function to $aU(S)+b$ get\n",
        "the same result.\n",
        "In det enviornments only need to rank states, called **ordinal utility function**\n",
        "\n",
        "\n",
        " \"\"\"\n",
        "chapter16_3 = \"\"\" Prefrence elicitation - show people choices and observe\n",
        "to determine utility func\n",
        "\n",
        "Helpful to have some scale. So fix u-top = \"best utility\" and u-bot\"worst possible\". \n",
        "Can normalize with u-top =1  and u-bot $ =0\n",
        "\n",
        "can find util of S by finding $p$ where agent S ~ [p,u-top; (1-p),u-bot].\n",
        "\n",
        "**micromort** - 1 in mill chance of death. Used to estimate values\n",
        "\n",
        "**QALY** - quality adjusted life year. How much patients are willing to accept\n",
        "shorter life expectancy to avoid disability. \n",
        "\n",
        "Usually prefer more money to less, (AEQ). This is monotonic preference for money.\n",
        "**Expected monetary value** of a gamble is probability of win*payoff, + probability of loss*0.\n",
        "utility not directly proportional to money. 1st million has more utility than 2nd. \n",
        "\n",
        "Utility of money estimated to be logritimic. S shape when combined with negatives.\n",
        "That is, additional debt worht extra ris after a certain point. \n",
        "On positive side $U(L) < U(S_{EMV(L)})$, S is a sure thing. So agents are risk averse\n",
        "in the positive end. Risk-seeking in the negative end. \n",
        "\n",
        "certaininty equivalent is how much you'd accept as sure thing in place of a gamble\n",
        "to make more.\n",
        "\n",
        "Difference between EMV(L) - certaininty equivalent = insurance premium. \n",
        "\n",
        "For small changes, looks linear on the curve, so is **risk-neutral**. \n",
        "\n",
        "Have to use estimate utilitiy in real world. Even though unbiased, real outcome\n",
        "will typically be worse. This is because tend to select optimistic estimates.\n",
        "With more choices more optimistic estaimtes are more likely. this is the otpimizer's\n",
        "curse. \n",
        "\n",
        "Decision theory is normative, how should agents act. Descriptive theory says how\n",
        "actually act. \n",
        "\n",
        "Ex. certainity effect - people prefere things that are certain. Don't trust\n",
        "statesd probabilities. Prefer known probabilities. \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "Games have an opponent, as compared with puzzle\n",
        "\n",
        "Simple game envs:\n",
        "multiagent, static (no changes while thinking), discrete -finite set of perceptions/actions\n",
        "full observable - can see the entire game\n",
        "strategic - next move is dteremined by current state + agent action + opponent action\n",
        "\n",
        "Key properiteis:\n",
        "1. 2 players alternate moves\n",
        "2. Zero sum game\n",
        "3. Clear set of legal moves\n",
        "4. Well definied outcomes\n",
        "\n",
        "Card games are stochastic, not fully observable. Real time strat games are continous.\n",
        "\n",
        "Evaluate how good a position is by eval funciont $f(n)$. Based on statsic features of the board\n",
        "\n",
        "\n",
        "Minimax - have to assume min will reply w/ best posible move. No hope chess.\n",
        "Max value of children, min for min value of children. \n",
        "\n",
        "Expectimax there is a chance added to the minimax search. Values in the \n",
        "chance nodes are avg. case outcomes. Chance nodes are like min nodes\n",
        "but outcome is uncertain. Take weighted average of children. \n",
        "\n",
        "pruning more useful in large branching. Order affects pruning,\n",
        "if the nodes are not randomly distributed, may not be efficient. \n",
        "If a game is deterministic exptiminimimax == minimax\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "print(f\"chapter 16_3: {len(chapter16_3.split(' '))}\")\n",
        "\n",
        "\n"
      ],
      "execution_count": 303,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "chapter 16_3: 263\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "53829510-044f-4f11-c192-a2a10fe361c3"
      },
      "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": 304,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Zero sum games, only 1 winner. \nMax moves first\ngame tree is a search tree with all moves to game end (i.e. terminal state). \n\ncan either use a eval function to tell who is winning or run simulations.\n\nHave $S_0$, intila state, \nTo-Move(s): current player\nActions(s): Actions in state S\nResult(s, a): What is result of action in a state\nIs-Termina(s): Is the game over?\nUtility(s,p): What's the score the player?\n\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Ply is a move by a single player\nEvaluate the max utility based on each action, knowing subsequent action by min.\n\nMight not always be best to do a optimal move when playing a suboptimal player,\ncan take a risk if porbablity of good move is high, and think min player won't \nfind its optimal move.\n\nMinimax uses DFS, if b moves at teach step, with max depth m, $O(b^m)$ time complexity.\nIf generate all actions then $O(bm)$, if one at a time then $O(m)\n\nIn multiplayer games, backup the value of the max for the player whose turn it is at the leaf\n\nAlliances can form in multiplayer games b/t weaker position players. Can also form\nin 2 player non-zero-sum games. \n\n**Alpha-beta pruning** \n$\u0007lpha$ is highest value along the path for max, value be at least that much\n$\beta$ is the lowset value along the path for min, value at most that much\nif value < $\u0007lpha$ for min, or > $\beta$ for max, return.\n\nIf leaves are ordered best to worst, would have $O(b^{m/2}$, branching factor would be $b^{1/2}$\nIf randomly guess would have $O(b^{3m/4})$.\n\nKiller moves are the best moves. If try them first for killer move heuristic.\n\nCan reduce redundency by keeping a **transposition table** that is a table of\nthe heurisitc value of states. \n\n**Type A stragegy**, limit all moves up to a depth, and estimate the utility. Width over depth. Chess\n**Type B stargegy**, go only with most promising moves as far as possible. Depth over width.  Go.\n\n\n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nFor heuristic a-b search,use eval func to estimate util of state, and decide if \nto cut it off before terminal state.\n\neval vunction is somewhere betwen win and loss. Can work calculating\nfeatures of state (ex. #whit-pawns). Then has probability of win given features\ngrouped into categories. \n\nSince above is too expeirence depednent, eval each feature and combine. Ex.\ngive value to each chess piece. Then arrangement might be another feature.\n$$Eval(s)  = \\sum_{i=1}^n {W_if_i(s)}$$\neval func needs to be correlated to chance of winning, can be non-linear.\n\nCan cutoff after reaching a certain depth, retrun the eval for the player\nof the state at that depth.\n\nEval func should only be applied when the position is **quiescent**, no upcoming\nmove that will change the eval a lot. Otherwise need to continue the search.\nCan limit quiescent search to only certain important moves.\n\n**Horizion effect** delay inevitable move to later time.\n**Singular extensions** add moves that are def better than all others.\n\n**Forward pruning** removes moves that seem bad, but might be good. Saves\ncomp but could result in mistake. Type B strate.\n\nProbcut algorithm prunes out nodes that are probably not in [$\u0007lpha$, $\beta$]\n\nlate move reduction - reduce depth of search for later moves.\n\nCan use table lookup for the opening and ending of chess. Then can switch to search.\n**Policy** maps a state to the best move. Retrograde minimax, ex. reverse\nmoves from wining positions in chess.\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\nStochastic games have an aspect of chance. Needs to include\nchance nodes in the search, + max/min nodes.\n\nneed to calculate the expected value of a position - the **expectiminimiax** val.\n\nif want to use an approx with cutoff search, need to use values that are pos\nlinear transfomrations for probability. \n\nTime complexity is $O(b^mn^m)$ where n is number of rolls (i.e. possibilities)\n\nCan prune chance nodes by bounding utility values.\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nDecision theory is about choosing an action based on immediate result. Assume\nepisodic env. **Utilitity funcion** evals a state, and **expected utility** is the avg.\nutility value of outomes * probability that it happens. \n\n**Max expected utility (MEU)** has rational agent pick the action with\nmax expected utility. \n\nDoesn't operationalize AI rationality though. Still need to estimate probabilities\nof states and possibly search for uitilities of states. \n\nUtil function applies step by step. If agent maxes it and it reflects perfmes\nthen it will have best perfmes.\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nOutcomes for actions are a lottery L =[$p_1,S_1; p_2S_2, ... p_n,S_n$],\nand each S_i can be a state or a lottery. \n\n6 constraints for prefrence relations - axioms of utility theory:\n1. Orderability: Either A > B, B > A or A~B\n2. Transitivity: (A > B) $\\wedge$ (B > C) => A > C\n3. Continuity: indifferent between a lottery for [A,C], and p =1 B \nA > B > C => $\\exists$ p [p,A; 1-p, C] ~ B\n4. Substitutability: if indifferent between two lotteries, then also indifferent about\ncomplex lotteries that just sub the original lotterires:\n A ~ B => [p, A; 1 - p, C] ~ [p, B; 1 - p, C]\n\n5. Monotonicity: If A > B, then prefer lottery that has higher probability of A\n A > B => (p > q <=> [p,A; 1 - p, B] > [q, A; 1 - q, B])\n6. Decomposability: can use probabilities to decompose a lottery to simpler verison\n[p, A; 1-p, [q,B; 1 - q, C]] ~ [p, A; (1 - p)q,B; (1 - p)(1 - q),C]\n\nAxioms lead to:\n1. Existence of utility function: have to have a Util func to be consistent w/axiom.\n2. Expected utility of lottery: sum of probabilities times U(outcome)\n\nutil function not necessirly unique. Can tranfrom util function to $aU(S)+b$ get\nthe same result.\nIn det enviornments only need to rank states, called **ordinal utility function**\n\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n Prefrence elicitation - show people choices and observe\nto determine utility func\n\nHelpful to have some scale. So fix u-top = \"best utility\" and u-bot\"worst possible\". \nCan normalize with u-top =1  and u-bot $ =0\n\ncan find util of S by finding $p$ where agent S ~ [p,u-top; (1-p),u-bot].\n\n**micromort** - 1 in mill chance of death. Used to estimate values\n\n**QALY** - quality adjusted life year. How much patients are willing to accept\nshorter life expectancy to avoid disability. \n\nUsually prefer more money to less, (AEQ). This is monotonic preference for money.\n**Expected monetary value** of a gamble is probability of win*payoff, + probability of loss*0.\nutility not directly proportional to money. 1st million has more utility than 2nd. \n\nUtility of money estimated to be logritimic. S shape when combined with negatives.\nThat is, additional debt worht extra ris after a certain point. \nOn positive side $U(L) < U(S_{EMV(L)})$, S is a sure thing. So agents are risk averse\nin the positive end. Risk-seeking in the negative end. \n\ncertaininty equivalent is how much you'd accept as sure thing in place of a gamble\nto make more.\n\nDifference between EMV(L) - certaininty equivalent = insurance premium. \n\nFor small changes, looks linear on the curve, so is **risk-neutral**. \n\nHave to use estimate utilitiy in real world. Even though unbiased, real outcome\nwill typically be worse. This is because tend to select optimistic estimates.\nWith more choices more optimistic estaimtes are more likely. this is the otpimizer's\ncurse. \n\nDecision theory is normative, how should agents act. Descriptive theory says how\nactually act. \n\nEx. certainity effect - people prefere things that are certain. Don't trust\nstatesd probabilities. Prefer known probabilities. \n\n\n\n\n## Module 5 Lecture Notes\n\nGames have an opponent, as compared with puzzle\n\nSimple game envs:\nmultiagent, static (no changes while thinking), discrete -finite set of perceptions/actions\nfull observable - can see the entire game\nstrategic - next move is dteremined by current state + agent action + opponent action\n\nKey properiteis:\n1. 2 players alternate moves\n2. Zero sum game\n3. Clear set of legal moves\n4. Well definied outcomes\n\nCard games are stochastic, not fully observable. Real time strat games are continous.\n\nEvaluate how good a position is by eval funciont $f(n)$. Based on statsic features of the board\n\n\nMinimax - have to assume min will reply w/ best posible move. No hope chess.\nMax value of children, min for min value of children. \n\nExpectimax there is a chance added to the minimax search. Values in the \nchance nodes are avg. case outcomes. Chance nodes are like min nodes\nbut outcome is uncertain. Take weighted average of children. \n\npruning more useful in large branching. Order affects pruning,\nif the nodes are not randomly distributed, may not be efficient. \nIf a game is deterministic exptiminimimax == minimax\n\n\n## Module 5 Definitions\n* **Concept** - definition\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": "6b17d4f8-1d90-40be-8eb6-5a7196a46bbe"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\"\n",
        "**constraint satisfaction problem** has states with sets of variables with values.\n",
        "solved when  all variables' values satisifies constraints for the variable.\n",
        "\n",
        "CSP has:\n",
        "X: set of vars\n",
        "D: set of domains for every variable\n",
        "C: set of constriants\n",
        "\n",
        "$D_i$ is set of valid valudes for $X_i$.\n",
        "$C_j$ has (scope, rel) pair, where scope is all the vars affected by the constraint,\n",
        "rel is definition vals the var can be. \n",
        "\n",
        "Assignment of values to vars is **consistent** if no constraints are violated.\n",
        "**Complete** is one where every variable is assigned a val.\n",
        "Solution is consistent & complete.\n",
        "Partial assignment - some are not assigne. Some not assigned, but assigned ones are valid.\n",
        "\n",
        "Can solve problems faster with CSP than atomic state-space search. Can prune a lot.\n",
        "\n",
        "Ex. is car assembly jobs.\n",
        "Task1_time + task1_duration <= Task2_time, where task2 must occur after task1\n",
        "or also have disjunctiv contrastins where Task_A + time <= Task_B or Task_B+time <= Task_A\n",
        "\n",
        "Simple CSP have discrete, finite domains. No algorithm for solving nonlinear constraints\n",
        "on integer variables. \n",
        "Can also have continous domains. Linear programming is best example. Constrains are linear ineq.\n",
        "\n",
        "Types of constraints:\n",
        "1. Unary: constriant on the single variable. ex. SA != green.\n",
        "2. Binary: constraint w/ 2 variables, ex. SA != NSW\n",
        "\n",
        "**binary CSP** only unary and binary constraints. \n",
        "\n",
        "**global constraint** is on $n$ number of variables. Doesn't have to be all.\n",
        "Alldiff is a common one where all vars need to be diff.\n",
        "\n",
        "constraint hypergraph has regular nodes and hypernodes for constraints .\n",
        "Can transfrom finite-domain constraint to binary constraint w/aux variables.\n",
        "Can also use a **dual graph**, where constraints become the variables, and binary\n",
        "constraint for all pairs of constraints that have the overlapping variables. \n",
        "\n",
        "Can have preference constraints that rank prefrence of solutions. Can use cost\n",
        "to represent constraints, w/ more prefereable costing less. This is a constrained\n",
        "optimization problem COP.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_2 = \"\"\"CSP alogrith can assign vars or use **constraint propagation**,\n",
        "using constraints to remove vals for a var, which then affects another var,\n",
        "and so on. Can reduce or eliminate search.\n",
        "\n",
        "**local consistency**, each var is a node and constraints are edges. To have\n",
        "local consistency eliminate inconsistent vals.\n",
        "\n",
        "Types of local consistency:\n",
        "1. Node-consistent: for all vars, all vals in its domain satisfy unary constraints.\n",
        "Do this at the start of solution. Sometimes expect only binary constraints, so\n",
        "this is a pre-processing step.\n",
        "2. Arc consitency: for all var pairs, all vals in domain satisfy binary constriants. \n",
        "i.e for $X_i$ and $X_j$, and for $D_i$ there is a value in $D_j$ that satisfy\n",
        "constraint on $(X_i, X_j)$\n",
        "\n",
        "AC3 enforces arc-consistency. Has que of arcs. Pop off an arc $(X_i, X_j)$,\n",
        "If change $D_i$, add all arcs ($X_k$, $X_i$) for each neighbor $X_k$ of $X_i$.\n",
        "So now need to recheck if small domain $D_i$ causes elimination in $D_k$.\n",
        "If $D_i$ = $\\emptyset$ know no solution exists. New CSP = Original CSP,\n",
        "but arc-consistent will have faster search. \n",
        "Checking arc consistency is $O(d^2)$ time for each of the $c$ constraints,\n",
        "and can add an arc at most $d$ times, so time complexity is $O(cd^3)$\n",
        "\n",
        "**Path consistency**, uses implicit constraints by examinig triples of \n",
        "variables. Kind like how arc consistency maeks unary constraints strong by\n",
        "looking at binary constraints?\n",
        "Path consistent if for every {$X_i = a , X_j = b$} that's arc consistent,\n",
        "X_m has value to satisfy {$X_i, X_m$} and {$X_m, X_j$}. Consitent path from\n",
        "$X_i$ -> $X_m$ -> $X_j$\n",
        "\n",
        "**K consistency**, if for consistent assignment to set of $k -1$ vars can\n",
        "have consistet assignment to k_th var. 1 consistnecy is with empty set (aka \n",
        "node consistency). 2-consistency == arc. \n",
        "\n",
        "CSP is strongly k-consistent if k consistent, k-1 consistent...1 consistent. \n",
        "If strongly k-consistent, can find solution for each $X_i$ by looking at\n",
        "d values and it be consistent with $X_1 ... X_{i-1}$. Total complexity is\n",
        "$O(k^2d). But CSP is NP-complete.\n",
        "\n",
        "For alldiff, for any singleton value in a domain, remove that val from\n",
        "domains of all other variables. If an empty set is produced, or fewer values\n",
        "than vars, than inconsistency is detected. \n",
        "\n",
        "**Resource constraint**, at most check sum of min val of all domains, to see if\n",
        "violate at most constraints. Can also delete max val if not consistent with min vals.\n",
        "\n",
        "**Bounds propogration** if two constraints, may change lower and upper bounds based on \n",
        "combination of constraints. Bound consistent if every X, for every upper\n",
        "and lower bound value, there is a value in Y that is consistent.\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_3 = \"\"\"\n",
        "**commutativity** property, if the order of assignment doesn't matter. reduced by\n",
        "factor of n! (n = # vars), to $d^n$ leaves. \n",
        "\n",
        "Backtracking algorithm picks unassigned var, assigns it value and then recurses.\n",
        "Return if solved, if failure restore to previous state. \n",
        "\n",
        "For choosing variables, can do it in order, or randomly but not optimal.\n",
        "Use the **minimum-remaining-values heuristic** to chose var with fewest vals. Aka\n",
        "\"Most contrained variable\" and \"fail-first\". Prunes tree faster.  \n",
        "\n",
        "**degree heuristic** - reduce branching by choosing var with most constraints\n",
        "on unassigned vars (the degree of the node)\n",
        "\n",
        "After choosing a variable, choose value. **least-constarining-value** heuristic,\n",
        "choose val that eliminates fewest choices for neighbors. Fail-last strategy,\n",
        "because looking for one solution, so choose most likely to work (least constarining)\n",
        "\n",
        "AC3 reduces var domains before search, can be good during search too. Can use\n",
        "**Forward checking** when a var is assigned, forward checking checks arc consistnecy.\n",
        "But doesn't look that far.\n",
        "\n",
        "**Maintainin Arc Consistency** does check for that. After a var is assigned\n",
        "calls AC3 but only on ($X_j, X_i$) for $X_j$ unassigned neighbor of $X_i$.\n",
        "Then AC3 does its thing, and if fails know can backtrack. \n",
        "\n",
        "Bactracking can be improved if backtrack to the variable that made a var impossible.\n",
        "Tarck set of assignments that in conflict with a var, called a **conflict set**.\n",
        "Jumps back to the most recent assignment in the conflict set. Can use forward\n",
        "checking, adding assignment x to  neighbor X of Y to Y's conflict set. Somewhat\n",
        "redundent with forward checking and MAC?\n",
        "\n",
        "Can use stronger notion that it's the assignment plus assignment of preceding var\n",
        "and subsequent vars. **conflict-directed backjumping**.\n",
        "\n",
        "Works by jumping back from $X_j$ to previous variable $X_i$ in conflict set, and \n",
        "add conflict set of $X_j$ to that of $X_i$. (except X_i itself).\n",
        "\n",
        "**Constraining learning** find minimum set of vars in conflict that led to failure.\n",
        "These vars and the vals are recorded as **no-good**, and don't allow the combination.\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "Local search can work well for CSP. \n",
        "\n",
        "**min-conflicts** heuristic, Assign a value to each var. pick one  that's \n",
        "conflicted then change the value to something that results in lowest number of conflicts\n",
        "\n",
        "Min-conflict is really effective in easy problems. Where solutions are densely distributed.\n",
        "Work well for hard problems.\n",
        "\n",
        "May use plateau search where move sideways to states with equal scores. **Tabu search**\n",
        "keeps a list of visted states and doesn't repeat.\n",
        "\n",
        "**constrain weighting** gives a weight to each constraint. Choose var/val to change\n",
        "that will create lowest toatal weight across wrong assignments. Adjust weight of\n",
        "constraints that are violted by assignments. Most difficult constraints get heavier over time.\n",
        "\n",
        "\"\"\"\n",
        "chapter6_5 = \"\"\"\n",
        "**Independent subproblems** - are the components connected. Total work is $O(d^cn/c)$,\n",
        "which is less than $O(d^n)$ work for non-decomposed problem. \n",
        "\n",
        "A constraint graph is a tree if vars are only connected by 1 path. Any such\n",
        "CSP can be solved in linear time in $n$ (n= # vars). \n",
        "\n",
        "**Directional arc consistency** - every ($X_i$, $X_j$) is consistent with $j > i$\n",
        "\n",
        "to solve tree-structured CSP pick a root node, and toplogically sort remaining nodes.\n",
        "Enforce arc-consitency in $O(n)$ steps, need to compare at most $d$ values for every \n",
        "one of the $n-1$ edges, so $O(n*d^2)$. Once arc consistent can choose values at each step.\n",
        "Each parent and child pair is consistent, so can pick something for parent, and have child\n",
        "consistent. \n",
        "\n",
        "Can reduce a constraint graph to a tree in a few ways\n",
        "\n",
        "Cutset conditioning, assign a value to some var so that reamining vars are a tree,\n",
        "remove vals from other domains inconsistent with that assignment. If there is a\n",
        "solution for the new CSP, it will be consitent with the removed node. Since \n",
        "might not have a solution for the chosen value for the removed var, need to try \n",
        "every val. \n",
        "\n",
        "Total time complexity is $O(d^c * (n-c)d^2$. Because need to try $d^c$ for the \n",
        "vars in S, the cycle cutset being removed, and then need to solve a tree with size\n",
        "$n - c$. With smaller $c$ have bigger savings. But $c$ can be $(n-2)$. \n",
        "Finding smallest cycle cutset is NP-Hard. \n",
        "\n",
        "Another option is to try tree decomposition. Graph becomes a tree where every node\n",
        "is a set of vars such that:\n",
        "1. Every var appears in at least 1 node\n",
        "2. If 2 vars have a constraint, they need to be togeter in at least 1 node\n",
        "3. If a var is in 2 nodes, $u, v$ in the tree, it must be in every node on the path\n",
        "connecting $u,v$\n",
        "\n",
        "1& makes sure that all vars and constraints are represented. 3 means the var has\n",
        "the same value everywhere. \n",
        "\n",
        "Then can solve in $O(n*d^2)$, n=# tree nodes, d is the largest domain, where\n",
        "in the tree domain is a set of tuples of values.\n",
        "\n",
        "tree width is size of largest node - 1. Tree width a graph is the min width of all\n",
        "tree decompositions. graph w/ tree width $w$ can be solved in $O(nd^{w+1})$.\n",
        "\n",
        "Finding tree decomposition is NP-hard. When there is a cycle-custer size $c$\n",
        "there is a tree width $w < c + 1$.\n",
        "\n",
        "$value symmetry$$, can permute values in a solution. Can break that by imposing\n",
        "symmetry breaking constraint, like requiring alphabetical ordering. NP hard. \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "print(f\"length of 6_1: {len(chapter6_1.split(' '))}\")\n",
        "print(f\"length of 6_2: {len(chapter6_2.split(' '))}\")\n",
        "print(f\"length of 6_3: {len(chapter6_3.split(' '))}\")\n",
        "print(f\"length of 6_4: {len(chapter6_4.split(' '))}\")"
      ],
      "execution_count": 305,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "length of 6_1: 284\n",
            "length of 6_2: 399\n",
            "length of 6_3: 302\n",
            "length of 6_4: 104\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "b5c01039-f320-4e20-ca01-fb47d3b2fef0"
      },
      "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": 306,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n**constraint satisfaction problem** has states with sets of variables with values.\nsolved when  all variables' values satisifies constraints for the variable.\n\nCSP has:\nX: set of vars\nD: set of domains for every variable\nC: set of constriants\n\n$D_i$ is set of valid valudes for $X_i$.\n$C_j$ has (scope, rel) pair, where scope is all the vars affected by the constraint,\nrel is definition vals the var can be. \n\nAssignment of values to vars is **consistent** if no constraints are violated.\n**Complete** is one where every variable is assigned a val.\nSolution is consistent & complete.\nPartial assignment - some are not assigne. Some not assigned, but assigned ones are valid.\n\nCan solve problems faster with CSP than atomic state-space search. Can prune a lot.\n\nEx. is car assembly jobs.\nTask1_time + task1_duration <= Task2_time, where task2 must occur after task1\nor also have disjunctiv contrastins where Task_A + time <= Task_B or Task_B+time <= Task_A\n\nSimple CSP have discrete, finite domains. No algorithm for solving nonlinear constraints\non integer variables. \nCan also have continous domains. Linear programming is best example. Constrains are linear ineq.\n\nTypes of constraints:\n1. Unary: constriant on the single variable. ex. SA != green.\n2. Binary: constraint w/ 2 variables, ex. SA != NSW\n\n**binary CSP** only unary and binary constraints. \n\n**global constraint** is on $n$ number of variables. Doesn't have to be all.\nAlldiff is a common one where all vars need to be diff.\n\nconstraint hypergraph has regular nodes and hypernodes for constraints .\nCan transfrom finite-domain constraint to binary constraint w/aux variables.\nCan also use a **dual graph**, where constraints become the variables, and binary\nconstraint for all pairs of constraints that have the overlapping variables. \n\nCan have preference constraints that rank prefrence of solutions. Can use cost\nto represent constraints, w/ more prefereable costing less. This is a constrained\noptimization problem COP.\n\n\n\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nCSP alogrith can assign vars or use **constraint propagation**,\nusing constraints to remove vals for a var, which then affects another var,\nand so on. Can reduce or eliminate search.\n\n**local consistency**, each var is a node and constraints are edges. To have\nlocal consistency eliminate inconsistent vals.\n\nTypes of local consistency:\n1. Node-consistent: for all vars, all vals in its domain satisfy unary constraints.\nDo this at the start of solution. Sometimes expect only binary constraints, so\nthis is a pre-processing step.\n2. Arc consitency: for all var pairs, all vals in domain satisfy binary constriants. \ni.e for $X_i$ and $X_j$, and for $D_i$ there is a value in $D_j$ that satisfy\nconstraint on $(X_i, X_j)$\n\nAC3 enforces arc-consistency. Has que of arcs. Pop off an arc $(X_i, X_j)$,\nIf change $D_i$, add all arcs ($X_k$, $X_i$) for each neighbor $X_k$ of $X_i$.\nSo now need to recheck if small domain $D_i$ causes elimination in $D_k$.\nIf $D_i$ = $\\emptyset$ know no solution exists. New CSP = Original CSP,\nbut arc-consistent will have faster search. \nChecking arc consistency is $O(d^2)$ time for each of the $c$ constraints,\nand can add an arc at most $d$ times, so time complexity is $O(cd^3)$\n\n**Path consistency**, uses implicit constraints by examinig triples of \nvariables. Kind like how arc consistency maeks unary constraints strong by\nlooking at binary constraints?\nPath consistent if for every {$X_i = a , X_j = b$} that's arc consistent,\nX_m has value to satisfy {$X_i, X_m$} and {$X_m, X_j$}. Consitent path from\n$X_i$ -> $X_m$ -> $X_j$\n\n**K consistency**, if for consistent assignment to set of $k -1$ vars can\nhave consistet assignment to k_th var. 1 consistnecy is with empty set (aka \nnode consistency). 2-consistency == arc. \n\nCSP is strongly k-consistent if k consistent, k-1 consistent...1 consistent. \nIf strongly k-consistent, can find solution for each $X_i$ by looking at\nd values and it be consistent with $X_1 ... X_{i-1}$. Total complexity is\n$O(k^2d). But CSP is NP-complete.\n\nFor alldiff, for any singleton value in a domain, remove that val from\ndomains of all other variables. If an empty set is produced, or fewer values\nthan vars, than inconsistency is detected. \n\n**Resource constraint**, at most check sum of min val of all domains, to see if\nviolate at most constraints. Can also delete max val if not consistent with min vals.\n\n**Bounds propogration** if two constraints, may change lower and upper bounds based on \ncombination of constraints. Bound consistent if every X, for every upper\nand lower bound value, there is a value in Y that is consistent.\n\n\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n**commutativity** property, if the order of assignment doesn't matter. reduced by\nfactor of n! (n = # vars), to $d^n$ leaves. \n\nBacktracking algorithm picks unassigned var, assigns it value and then recurses.\nReturn if solved, if failure restore to previous state. \n\nFor choosing variables, can do it in order, or randomly but not optimal.\nUse the **minimum-remaining-values heuristic** to chose var with fewest vals. Aka\n\"Most contrained variable\" and \"fail-first\". Prunes tree faster.  \n\n**degree heuristic** - reduce branching by choosing var with most constraints\non unassigned vars (the degree of the node)\n\nAfter choosing a variable, choose value. **least-constarining-value** heuristic,\nchoose val that eliminates fewest choices for neighbors. Fail-last strategy,\nbecause looking for one solution, so choose most likely to work (least constarining)\n\nAC3 reduces var domains before search, can be good during search too. Can use\n**Forward checking** when a var is assigned, forward checking checks arc consistnecy.\nBut doesn't look that far.\n\n**Maintainin Arc Consistency** does check for that. After a var is assigned\ncalls AC3 but only on ($X_j, X_i$) for $X_j$ unassigned neighbor of $X_i$.\nThen AC3 does its thing, and if fails know can backtrack. \n\nBactracking can be improved if backtrack to the variable that made a var impossible.\nTarck set of assignments that in conflict with a var, called a **conflict set**.\nJumps back to the most recent assignment in the conflict set. Can use forward\nchecking, adding assignment x to  neighbor X of Y to Y's conflict set. Somewhat\nredundent with forward checking and MAC?\n\nCan use stronger notion that it's the assignment plus assignment of preceding var\nand subsequent vars. **conflict-directed backjumping**.\n\nWorks by jumping back from $X_j$ to previous variable $X_i$ in conflict set, and \nadd conflict set of $X_j$ to that of $X_i$. (except X_i itself).\n\n**Constraining learning** find minimum set of vars in conflict that led to failure.\nThese vars and the vals are recorded as **no-good**, and don't allow the combination.\n\n\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nLocal search can work well for CSP. \n\n**min-conflicts** heuristic, Assign a value to each var. pick one  that's \nconflicted then change the value to something that results in lowest number of conflicts\n\nMin-conflict is really effective in easy problems. Where solutions are densely distributed.\nWork well for hard problems.\n\nMay use plateau search where move sideways to states with equal scores. **Tabu search**\nkeeps a list of visted states and doesn't repeat.\n\n**constrain weighting** gives a weight to each constraint. Choose var/val to change\nthat will create lowest toatal weight across wrong assignments. Adjust weight of\nconstraints that are violted by assignments. Most difficult constraints get heavier over time.\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n**Independent subproblems** - are the components connected. Total work is $O(d^cn/c)$,\nwhich is less than $O(d^n)$ work for non-decomposed problem. \n\nA constraint graph is a tree if vars are only connected by 1 path. Any such\nCSP can be solved in linear time in $n$ (n= # vars). \n\n**Directional arc consistency** - every ($X_i$, $X_j$) is consistent with $j > i$\n\nto solve tree-structured CSP pick a root node, and toplogically sort remaining nodes.\nEnforce arc-consitency in $O(n)$ steps, need to compare at most $d$ values for every \none of the $n-1$ edges, so $O(n*d^2)$. Once arc consistent can choose values at each step.\nEach parent and child pair is consistent, so can pick something for parent, and have child\nconsistent. \n\nCan reduce a constraint graph to a tree in a few ways\n\nCutset conditioning, assign a value to some var so that reamining vars are a tree,\nremove vals from other domains inconsistent with that assignment. If there is a\nsolution for the new CSP, it will be consitent with the removed node. Since \nmight not have a solution for the chosen value for the removed var, need to try \nevery val. \n\nTotal time complexity is $O(d^c * (n-c)d^2$. Because need to try $d^c$ for the \nvars in S, the cycle cutset being removed, and then need to solve a tree with size\n$n - c$. With smaller $c$ have bigger savings. But $c$ can be $(n-2)$. \nFinding smallest cycle cutset is NP-Hard. \n\nAnother option is to try tree decomposition. Graph becomes a tree where every node\nis a set of vars such that:\n1. Every var appears in at least 1 node\n2. If 2 vars have a constraint, they need to be togeter in at least 1 node\n3. If a var is in 2 nodes, $u, v$ in the tree, it must be in every node on the path\nconnecting $u,v$\n\n1& makes sure that all vars and constraints are represented. 3 means the var has\nthe same value everywhere. \n\nThen can solve in $O(n*d^2)$, n=# tree nodes, d is the largest domain, where\nin the tree domain is a set of tuples of values.\n\ntree width is size of largest node - 1. Tree width a graph is the min width of all\ntree decompositions. graph w/ tree width $w$ can be solved in $O(nd^{w+1})$.\n\nFinding tree decomposition is NP-hard. When there is a cycle-custer size $c$\nthere is a tree width $w < c + 1$.\n\n$value symmetry$$, can permute values in a solution. Can break that by imposing\nsymmetry breaking constraint, like requiring alphabetical ordering. NP hard. \n\n\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\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",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7da61264-01e6-4cef-bdd8-f97590d6d123"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\"\n",
        "**knowledget base (KB)** composted of **sentences** in knowledge representation\n",
        "language. Axioms are un-derived (i.e. bases).\n",
        "To add a setnence you \"Tell\" and to query you \"Ask\" the KB.\n",
        "\n",
        "**Infrence** - derives new sentences from old. \n",
        "\n",
        "Sequence is \n",
        "1. Tell  KB what the agent percieved, \n",
        "2. Asks KB for best action, \n",
        "3. Agent programs Tells KB which action it chose. Returns action.\n",
        "\n",
        "description are given at the knowledge leve, not at the implementation level.\n",
        "Tell it waht it needs to know. Declarative approach. Proceudal approach puts\n",
        "desired behavior in the code. \n",
        "\n",
        "Learning agent learns by itself, knowledge comes from series of percepts.\n",
        "can be autonomous \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter7_2 = \"\"\"\n",
        "Wumpus world is deterministic, discrete, static, single agent, sequential,\n",
        "partially observable. Location of pits can either be unobserved, and the\n",
        "transition model is complete, and discovery completes the knoweldge of the state\n",
        "or tranistion model is incompelte and discovery fills in the transition model. \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "**Syntax** says all sentences are properly formed.\n",
        "Logic defines **semantics** - truth of a setnence in a possible world. Ex:\n",
        "x + y = 4 is true in world where x = 2, y =2. Must be either true or false in a\n",
        "world. \n",
        "\n",
        "**Model** - math abstraction of a world with fixed truth vals for all sentences.\n",
        "$m$ **satisfies** $\\alpha$  or $m$ is a model of $\\alpha$ means that \n",
        "$\\alpha$ sentence is true in model $m$.  \n",
        "\n",
        "If $a$ logically follows from $b$, say $a$ entails $b$:\n",
        "$a \\models b$, which means that in every model where $a$ is true, $b$ is true\n",
        "so $a \\models b \\iff M(a) \\subseteq M(b)$. So $a$ is stronger.\n",
        "\n",
        "KB is a set of sentences, false in $m$ that contridicts known facts. \n",
        "\n",
        "Can look at a setence and see if in every world where KB true, is $a_i$ also true?\n",
        "if so then $KB \\models a_i$\n",
        "\n",
        "OTH if $\\exists$ $m$ where KB is true and $a_j$ is false, then $KB$ doesn't entail $a_j$.\n",
        "Inconclusive if $a_j$ is holds in a paritcular world. This is called model checking.\n",
        "Check that $M(KB) \\subseteq M(a)$. Model checking works for finite spaces of models.\n",
        "\n",
        "Inference is finding the entailment $a$ needle in the haystack of $KB$. \n",
        "Say that $KB \\vdash_i a$, which is a is derived from KB by i\n",
        "\n",
        "If an algorithm derives entailed sentences it is sound/truth-preserving. \n",
        "If the algorithm can derive all entailed sentences it is complete. \n",
        "Can be a problem for infinite consequences can still have completenesl\n",
        "\n",
        "If KB is true in real world then any derived sentence by sound algorithm is also true. \n",
        "\n",
        "**Grounding** is there a connection b/t KB and real env? Sensors connect it. But\n",
        "some rules are not based on sensors, but on perceptual experience. Learning. \n",
        "\n",
        "\"\"\"\n",
        "chapter7_4 = \"\"\"atomic sentences have 1 propositiona sybmol, the proposition \n",
        "is T/F.\n",
        "\n",
        "Complex setnences are amde from simpler sentences and logical connectives.\n",
        "literal is either atomic or negated atomic. \n",
        "\n",
        "$ A \\Rightarrow B$ is an implication, A is the permise and B is conclusion/consequent. \n",
        "\n",
        "Order precendence:\n",
        "$\\\\neg$ $\\wedge$ $\\\\vee$ $\\Rightarrow$ $\\iff$\n",
        "\n",
        "$P \\Rightarrow Q$ is true unless $P = T$ and $Q = F$\n",
        "$P \\iff Q$ is true iff P&Q are the same value. \n",
        "\n",
        "$P \\Rightarrow Q$ is saying if P is true than Q is true, but if P is false,\n",
        "then no conclusion and so Q can be anything. The sentence as a whole is true.\n",
        "Sentence is only false if $P$ is true and $Q$ is false. \n",
        "\n",
        "Can generate all models and see where KB it true, and some sentence $a$ is true.\n",
        "KB is true if $R_i$s are true, which are the sentences\n",
        "\n",
        "$O(2^n)$ models. Space is $O(n)$ b/c DFS. \n",
        "\n",
        "Propositional entailment is co-NP-compelte. \n",
        "\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\" \n",
        "**theorem proving**, apply rules of inferences to create proofs of a sentence\n",
        "\n",
        "**logical equivalence** $a \\equiv b$ iff $a \\models b$ and $b \\models a$.\n",
        "\n",
        "If a sentence is T for all models it is valid. Ex: $P \\\\vee \\\\neg P$. Tautology. \n",
        "\n",
        "For $a, b$,  $a \\models b$ iff $a \\Rightarrow b$ is valid. Either\n",
        "$a \\Rightarrow b$ in every model, or prove $(a \\Rightarrow b) \\equiv True$\n",
        "\n",
        "SAT if sentence can hold true in some model. SAT is NP-complete \n",
        "\n",
        "Validity related to sat, $a$ sat iff $\\neg a $ not valid\n",
        "$a \\models b$ iff $(a \\wedge \\\\neg b)$ is unsat. ==Proof by contridiction. \n",
        "Assume $\\\\neg b$, show contridicts $a$\n",
        "\n",
        "proof search alg: Initial state of KB. Actions are the inf-rules applied\n",
        "to sentences on top half of inf-rule -> bottom of the inf-rule. \n",
        "The goal get to state that has the target sentence to prove \n",
        "\n",
        "More efficent than model search b/c can ignore irrelevant propositions. \n",
        "\n",
        "Entainled sentences are monotonic, can only increase as information is added.\n",
        "$KB \\models a \\Rightarrow (KB \\wedge b) \\models a$. Can apply rules whenver. \n",
        "\n",
        "Resolution + complete search -> complete inference algorithm.\n",
        "\n",
        "Unit resolution rule. For literals, $l_1...\\\\vee ... l_k$ if $l_i$ and $m$ are complementary,\n",
        "& we have $m$ then have new clause w/o $l_i$.\n",
        "\n",
        "can be generalized with multi pairs, only resolve one pair of literals at a time. \n",
        "\n",
        "Resulting clause should contain only 1 copy of each literal. **factoring**. \n",
        "\n",
        "Reso based theroem prover can see if $a \\models b$ holds for any any a b\n",
        "\n",
        "Reso is only applid to disjunct. Every sentence can be translated to CNF. \n",
        "\n",
        "Reso alg work by contridiction. Convert an implies into CNF.\n",
        "Then apply reso rule to the clauses. Add resulting clause to the set\n",
        "If no new clauses to add KB doesn't entail a.\n",
        "If yield an emptly clause then KB entails a. Empty clause implies a contridiction\n",
        "\n",
        "Reso closure is the set S  all clauses dervied by applying the reso-rule to c's in S.\n",
        "\n",
        "Ground resolution theorem: for an unsat set of c's, the reso closure is empty\n",
        "\n",
        "**Definite clause** is a disjunction of literals w/ only 1 positve\n",
        "ex: $(\\\\neg A \\\\vee \\\\neg B \\\\vee C)$\n",
        "\n",
        "**Horn clause** is disjunction of literals w/ <= 1 positive. Def clause=Horn.\n",
        "\n",
        "**Goal clause** 0 positives. \n",
        "\n",
        "2 horn claues resolved get a horn clause\n",
        "\n",
        "KB w/ only definite clauses:\n",
        "1. Every def clause can be transformed to implication\n",
        "ex: $(\\\\neg A \\\\vee \\\\neg B \\\\vee C)$ can be $(A \\wedge \\B \\Rightarrow C )$\n",
        "In this horn, permise=**body**, conclusion=**head**.\n",
        "Single pos literal is a **fact**\n",
        "\n",
        "2. Can use forward/backward chaining. Base for logic programming. \n",
        "3. Entalinment can be done in linear time wrt KB.\n",
        "\n",
        "Forward chaining check if $KB \\models q$, starts with facts and adds conclusions\n",
        "from implications where facts are known to set. Keeps going til\n",
        "find q or no more inferences. linear time.  Data-driven reasoning.\n",
        "\n",
        "\n",
        "Backward chaining is the other way. From q, finds implication in KB w/conclusion q. \n",
        "If 1 implications can proved true, then q is true. linear time. Goal-directed reasoning. \n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\"\n",
        "Knowledge based agents reason over a representation of the world. \n",
        "Different from the problem-solving agents is the representation of the world.\n",
        "In problem-sovling the representaiotns are atomic.\n",
        "\n",
        "Have a KB which is a set of sentences written in knowledge representation language\n",
        "\n",
        "axioms are given setnences. Dervied sentences are derived from other sentences through inference.\n",
        "\n",
        "B entails a is only if M(b) is a subset of M(a)\n",
        "every model whre b is true, a is also true\n",
        "\n",
        "does KB entail a? If in every model where KB is true, a is also true.\n",
        "If there is a model where KB is true, but a is false, then KB doesn't entail a.\n",
        "\n",
        "Infrence Rules:\n",
        "\n",
        "**Modus Ponens**: \n",
        "$\\\\frac{a \\Rightarrow b, b}{b}$\n",
        "If know that \"a then b\", and given a, then know b. \n",
        "\n",
        "**And elimination**:\n",
        "$\\\\frac{a \\wedge b}{a}$. Given a and b, a holds.\n",
        "\n",
        "**Biconditional elimination**\n",
        "$\\\\frac{a \\iff b}{(a \\Rightarrow b) \\wedge (b \\Rightarrow a)}$ \n",
        "and\n",
        "$\\\\frac{(a \\Rightarrow b) \\wedge (b \\Rightarrow a)}{a \\iff b}$ \n",
        "\n",
        "Search for a proof, \n",
        "inital state is the intial KB\n",
        "Actionss all inteference rules applied to to half of inf-rule\n",
        "Result is the add sentencs to the bottom halfo the KB\n",
        "Goal is the state w/ the setnence trying to prove. \n",
        "\n",
        "Resolution alogirthm\n",
        "1. Convert $KB \\wedge \\\\not a$ into CNF\n",
        "2. apply resolution to the resulting clauses\n",
        "3. Resolve pairs that contain the complmentary literals to make new claus\n",
        "4. if new clause isn't already in set, add it\n",
        "5.continue until either: 1. no new clauses, then KB doesn't entail a, \n",
        "or 2. get an empty clause which means KB does entail a\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n",
        "print(f\"word length of chapter7_5: {len(chapter7_5.split(' '))}, character count: {len(chapter7_5)}\")\n"
      ],
      "execution_count": 307,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "word length of chapter7_5: 485, character count: 2990\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "9583877e-78e3-42cb-bb08-cabfb3675374"
      },
      "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": 308,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n**knowledget base (KB)** composted of **sentences** in knowledge representation\nlanguage. Axioms are un-derived (i.e. bases).\nTo add a setnence you \"Tell\" and to query you \"Ask\" the KB.\n\n**Infrence** - derives new sentences from old. \n\nSequence is \n1. Tell  KB what the agent percieved, \n2. Asks KB for best action, \n3. Agent programs Tells KB which action it chose. Returns action.\n\ndescription are given at the knowledge leve, not at the implementation level.\nTell it waht it needs to know. Declarative approach. Proceudal approach puts\ndesired behavior in the code. \n\nLearning agent learns by itself, knowledge comes from series of percepts.\ncan be autonomous \n\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\nWumpus world is deterministic, discrete, static, single agent, sequential,\npartially observable. Location of pits can either be unobserved, and the\ntransition model is complete, and discovery completes the knoweldge of the state\nor tranistion model is incompelte and discovery fills in the transition model. \n\n\n\n\n## AIMA Chapter 7.3 Logic\n \n**Syntax** says all sentences are properly formed.\nLogic defines **semantics** - truth of a setnence in a possible world. Ex:\nx + y = 4 is true in world where x = 2, y =2. Must be either true or false in a\nworld. \n\n**Model** - math abstraction of a world with fixed truth vals for all sentences.\n$m$ **satisfies** $\u0007lpha$  or $m$ is a model of $\u0007lpha$ means that \n$\u0007lpha$ sentence is true in model $m$.  \n\nIf $a$ logically follows from $b$, say $a$ entails $b$:\n$a \\models b$, which means that in every model where $a$ is true, $b$ is true\nso $a \\models b \\iff M(a) \\subseteq M(b)$. So $a$ is stronger.\n\nKB is a set of sentences, false in $m$ that contridicts known facts. \n\nCan look at a setence and see if in every world where KB true, is $a_i$ also true?\nif so then $KB \\models a_i$\n\nOTH if $\\exists$ $m$ where KB is true and $a_j$ is false, then $KB$ doesn't entail $a_j$.\nInconclusive if $a_j$ is holds in a paritcular world. This is called model checking.\nCheck that $M(KB) \\subseteq M(a)$. Model checking works for finite spaces of models.\n\nInference is finding the entailment $a$ needle in the haystack of $KB$. \nSay that $KB \u000bdash_i a$, which is a is derived from KB by i\n\nIf an algorithm derives entailed sentences it is sound/truth-preserving. \nIf the algorithm can derive all entailed sentences it is complete. \nCan be a problem for infinite consequences can still have completenesl\n\nIf KB is true in real world then any derived sentence by sound algorithm is also true. \n\n**Grounding** is there a connection b/t KB and real env? Sensors connect it. But\nsome rules are not based on sensors, but on perceptual experience. Learning. \n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\natomic sentences have 1 propositiona sybmol, the proposition \nis T/F.\n\nComplex setnences are amde from simpler sentences and logical connectives.\nliteral is either atomic or negated atomic. \n\n$ A \\Rightarrow B$ is an implication, A is the permise and B is conclusion/consequent. \n\nOrder precendence:\n$\\neg$ $\\wedge$ $\\vee$ $\\Rightarrow$ $\\iff$\n\n$P \\Rightarrow Q$ is true unless $P = T$ and $Q = F$\n$P \\iff Q$ is true iff P&Q are the same value. \n\n$P \\Rightarrow Q$ is saying if P is true than Q is true, but if P is false,\nthen no conclusion and so Q can be anything. The sentence as a whole is true.\nSentence is only false if $P$ is true and $Q$ is false. \n\nCan generate all models and see where KB it true, and some sentence $a$ is true.\nKB is true if $R_i$s are true, which are the sentences\n\n$O(2^n)$ models. Space is $O(n)$ b/c DFS. \n\nPropositional entailment is co-NP-compelte. \n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \n**theorem proving**, apply rules of inferences to create proofs of a sentence\n\n**logical equivalence** $a \\equiv b$ iff $a \\models b$ and $b \\models a$.\n\nIf a sentence is T for all models it is valid. Ex: $P \\vee \\neg P$. Tautology. \n\nFor $a, b$,  $a \\models b$ iff $a \\Rightarrow b$ is valid. Either\n$a \\Rightarrow b$ in every model, or prove $(a \\Rightarrow b) \\equiv True$\n\nSAT if sentence can hold true in some model. SAT is NP-complete \n\nValidity related to sat, $a$ sat iff $\neg a $ not valid\n$a \\models b$ iff $(a \\wedge \\neg b)$ is unsat. ==Proof by contridiction. \nAssume $\\neg b$, show contridicts $a$\n\nproof search alg: Initial state of KB. Actions are the inf-rules applied\nto sentences on top half of inf-rule -> bottom of the inf-rule. \nThe goal get to state that has the target sentence to prove \n\nMore efficent than model search b/c can ignore irrelevant propositions. \n\nEntainled sentences are monotonic, can only increase as information is added.\n$KB \\models a \\Rightarrow (KB \\wedge b) \\models a$. Can apply rules whenver. \n\nResolution + complete search -> complete inference algorithm.\n\nUnit resolution rule. For literals, $l_1...\\vee ... l_k$ if $l_i$ and $m$ are complementary,\n& we have $m$ then have new clause w/o $l_i$.\n\ncan be generalized with multi pairs, only resolve one pair of literals at a time. \n\nResulting clause should contain only 1 copy of each literal. **factoring**. \n\nReso based theroem prover can see if $a \\models b$ holds for any any a b\n\nReso is only applid to disjunct. Every sentence can be translated to CNF. \n\nReso alg work by contridiction. Convert an implies into CNF.\nThen apply reso rule to the clauses. Add resulting clause to the set\nIf no new clauses to add KB doesn't entail a.\nIf yield an emptly clause then KB entails a. Empty clause implies a contridiction\n\nReso closure is the set S  all clauses dervied by applying the reso-rule to c's in S.\n\nGround resolution theorem: for an unsat set of c's, the reso closure is empty\n\n**Definite clause** is a disjunction of literals w/ only 1 positve\nex: $(\\neg A \\vee \\neg B \\vee C)$\n\n**Horn clause** is disjunction of literals w/ <= 1 positive. Def clause=Horn.\n\n**Goal clause** 0 positives. \n\n2 horn claues resolved get a horn clause\n\nKB w/ only definite clauses:\n1. Every def clause can be transformed to implication\nex: $(\\neg A \\vee \\neg B \\vee C)$ can be $(A \\wedge \\B \\Rightarrow C )$\nIn this horn, permise=**body**, conclusion=**head**.\nSingle pos literal is a **fact**\n\n2. Can use forward/backward chaining. Base for logic programming. \n3. Entalinment can be done in linear time wrt KB.\n\nForward chaining check if $KB \\models q$, starts with facts and adds conclusions\nfrom implications where facts are known to set. Keeps going til\nfind q or no more inferences. linear time.  Data-driven reasoning.\n\n\nBackward chaining is the other way. From q, finds implication in KB w/conclusion q. \nIf 1 implications can proved true, then q is true. linear time. Goal-directed reasoning. \n\n\n\n## Module 7 Lecture Notes\n\nKnowledge based agents reason over a representation of the world. \nDifferent from the problem-solving agents is the representation of the world.\nIn problem-sovling the representaiotns are atomic.\n\nHave a KB which is a set of sentences written in knowledge representation language\n\naxioms are given setnences. Dervied sentences are derived from other sentences through inference.\n\nB entails a is only if M(b) is a subset of M(a)\nevery model whre b is true, a is also true\n\ndoes KB entail a? If in every model where KB is true, a is also true.\nIf there is a model where KB is true, but a is false, then KB doesn't entail a.\n\nInfrence Rules:\n\n**Modus Ponens**: \n$\\frac{a \\Rightarrow b, b}{b}$\nIf know that \"a then b\", and given a, then know b. \n\n**And elimination**:\n$\\frac{a \\wedge b}{a}$. Given a and b, a holds.\n\n**Biconditional elimination**\n$\\frac{a \\iff b}{(a \\Rightarrow b) \\wedge (b \\Rightarrow a)}$ \nand\n$\\frac{(a \\Rightarrow b) \\wedge (b \\Rightarrow a)}{a \\iff b}$ \n\n## Module 7 Definitions\n* **Concept** - definition\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": "90367e2c-108d-4a39-f63b-365377834d68"
      },
      "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": 309,
      "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/rational and thought/behavior.\nApproaches: \nTuring: cannot tell if response is from person or computer \nCognitive model: Compare how program solve w\\how computer solves. \nLaws othought: Use logic notation to solve problems, use probability to fill in certaintiy gap.\nRationl agent: More general than laws othought, more flexible as science develops, so better than just imitating behavior.\n\nStandard model focus on study/construction of agents that do the right thing\n\nValue alginemnt problem is that what we actualy want vs what we put into machine. \n\n\n## AIMA Chapter 27.1 The Limits of AI\n Turing said human behavior isn't guided by formal rules, use informal guideslines that are cannot be quantify/coded. Dreyfus, critique of GOFAI, simple agents \\ \nusing just logical rules.Embodied cogntion centers whole system, body, brain, enviornment. So sensors are very important.\nArgument from disability - can't do lovely things humans can. But over time lotsactually have done lots.\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Don't know if people think, but have polite convention to pretend they doChinese room from Searle argues computers don't just rule book. Biological naturalism mental states can only come from neurons. Don't need to solve consciousness questionto make parts of (e.g.e awarness, attention) intellegent systems\n\n## AIMA 2.1 Agents and Environments\n Agents percieve the enviornment via its sensors, and then makean action by actuators\nExample sensors: cameras, infrared. Example actuators: motors\nPercept is one thing that an agent's sensors percieves, and percept sequence is history of the perceptions.\nAgent func maps a _percept sequnce_ to actions. Would be a huge table b/c perceptsequences get infinte. Internally have agent program - actual implrementation on real system.\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n AI uses consquentalism, evaulate behavior based on conseuqneces,using performance measure that looks at sequence of states. Performance measures come from humans. Better to design perfmes for what one wants instead of how agent should behave.\n\nRationality depends on: \n1. Perfmes\n2. Prior knowledge of env\n3. Actions available\n4. Percept seq\n\nSo rational agent, for all percept seq, chose action to max perfmes based on current percseq and knowlege.\n\nRationality max expected perf. Not same as perfection (actual perf).\n\nInformation gatherin and exploration important to rationality. \n\nAgents with autonomy do better, b/c can learn. Need some base knowlegde.\n\n\n\n## AIMA 2.3 The Nature of Environments\n Task env needs to be specifed, give the Performance, Enviornment Actuators Sensors.\n\n- Fully observable/Partially: can percieve whole relevant env?. Things can be obscured or missing from data (ex: can't know what others think)\n\n- Single/Multiagent: Crossword vs. chess. 2nd agent needs to have a perfmes, that depends on 1st agent's perfmes. Can be competitive or cooperative. \n\n- Deterministic/nondet: If can determine next state based on now+action. If partially observable could seem nondet. \n\n-- Stochastic - if deal w/ quantified probabilities \n\n- Episodic/Sequential: atomic steps, don't depend on each other.\ne.g. picking out parts on assembly line. Chess/driving are seq. \n\n- Static/Dynaic: Does env change while agent is thinking? Static means don't have to resample env. \n\n-- semidynamic: If env is static, but perfmes changes w/time. Ex. chess w/timer.\n\n- Discrete/continous: State, time, percpets, and actions. Chess is discrete(state, percept, action), driving is continous.\n\n- Known/unknown: Know physics of env? I.e outcome/probab of outcome for an action given or not? Can be known but partially observable. Ex: solitare.\nCan also be uknown but observable, ex: video game & controller. \nPerfmes can be uknown (designer don't know it or the user's pref,)\n\n\n## AIMA 2.4 The Structure of Agents\n agent is architecture + program\n**Simple reflex agent** select actions based only on current percept, not history\n**condition-action rule** – ex, break if car has lights on. Too simple, needs fully observable env. Otherwise might get stuck in loop (ex. robot w/o location)can use randomization to break out of infinite loops. In this case > simple reflex agentthough usually not rational.\n\n**Model-based agent**\nNeed to keep track of state to keep track of some unobserved parts of the world.\n1. Maintain knowledge of world physics, called transition model of the world.\ncurrent state + action -> transition\n2. Also need info on how world translated to agent's percepts. Sensor model\nThis is the best guess, not absolute certainty \n\n**goal-based agent**\ncurrent state + transition model + goals -> action. Flexibile b/c can change goal\n\n**utility-based agent**\nGoals are more binary, utility as perfmes -> higher qual. Utility function andexternal perfmes need to line up.\nTry to maximize expected utility. Highest perfromance = rational.\n\nHow to build these agents?\n**Learning agents**\nHas 4 parts:\n1. learning element: makes improvements\n2. performance element: select actions (basically the agent)\n3. Critic: gives feedback to learning el., says how perf el. needs to moded\n4. Problem generator: suggest actions that will lead to new experiences/explorations\n\nways to represent components that rep the env:\n1.Atomic: single atom of knoweldge, ex: city name\n2.Factored: fixed variables/attributes w/ values. Ex. for driving: how much gasin tank, GPS coordinate\n3.Strcutred: entities & relations\n\nThese are level of expresivness. Most expressive, can capture everything as less expbut more concisely. \n\nlocalist rep = 1:1 map concept to mem location\ndistributed rep = rep is spread over mem locations\ndistributed is more robust, withstand noise/dataloss\n\n\n\n## Module 1 Lecture Notes\n\nDescartes - I think therefore I am. Didn't think machines could replicate humans\nTuring - Can machines think too difficult. Can a machine reply in a way that can't \nbe distinguished from a human? Can a machine pass\n\nSearle, says Turing's machine is too simple. Can just look up symbols and follow syntax.\n\nEliza an early NLP threapist. Rogerian psychotherapy. \n\nSearle distinction betwee weak AI that just simulates thought and strong AI.\nSays biology is necessary for intelligence. \n\nDan Dennett, remove brain from the body and have radio links to the body. Who is the person?\nThe brain in the vat? or the body out in the field?\nIf replace body, but also brain computations, same person?\n\nRational agents - act rationally.\nagent fucntion maps sequence of percept vectors P to an action a from set A\na math abstraction\n\nagent program runs on physical architeure to produce f. Agent = architecture + program.\n\nAgent is anything that percives its enviornment through sensors and actus on it\nthrough actuators. Thermostats also qualify - b/c senses temp and adjusts boilers.\n\nRational beahvior - doing the right thing. AI is concerned with consequentialism,\nevaluate agents based on its consequences. Should require omniscience. \n\nSimon - bounded rationality, people choose alternatives they prefer. \n\nUse a performance measure to measure if agent was succsesful. Better to design one\nfor  the behvaior you want to be achieved than for how the agent should behave. \n\nRational agent choses the action that maximizes the expected value of its performance measure.\n\nDeterministic - know what happens after selecting an action.\nNon-deterministic - don't know what will happen. Could be many results. Games of chance\nStochastic - Non-deterministic that can be quantified. \n\nEpsidoic - parts on an assembly line\nSequential - current decision affects future actions \n\nStatic vs. dynamic - nothing changes while thinking vs. changes while thinking.\n\nDiscrete vs. continous - discrete states, particular moves that can take, continous,\nhow the variables change\n\nSingle agent vs mutli-agent: 1 agent or multiple each trying to max their own performance measure\n\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Ration agent** - one that acts to achieve the best outcome/best expected outcome\n* **Natural language processing** - use human language\n* **Knowledge representation** - store knowledge & percepts\n* **Automated reasoning** - answer qs and make inferences\n* **Machine learning** - adapt to changes, find/deduce patterns\n* **Computer vision** - perecption of enviornment\n* **Robotics** - movement & interactions w/env\n* **Introspection** - notice thinking as it happens\n* **Psychological experiments** - observe people's behavior\n* **Brain imaging** - scans when person performs action\n* **Weak ai** - machine action as though its can think - simultation\n* **Strong ai** - machine can actually think; general AI\n* **Qualia** - instance of consciousness\n* **Autonomy** - able to learn on its own\n* **Task enviornment** - Perfromance, Enviornment, Actuators, Sensors\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\npython is dynamically typed, variables come into existance when assigned\nType can be updated so type(var) can change in different parts. Don't have type \nsignatures\n\nno \"++\" or \"--\"\n\ncan concat with +. \nr'\n' is a raw string, won't be new line. \n\nStrings are immutable. So checking \"==\" checks if the two have the same value\nwhile \"is\" check if points to the same object\n\ny=x[:] is a shallow copy of any sequence (new object)\n\ntuple is immutable. Can be of mixed types\nstring is immutable. All unicode, 2 byte chars. \n\nt[1:-1]: returns everything but the last item\nt[1:-1:2] every nth (2nd here) number\nt[:2] from start to 2nd item but not 3rd (i.e. index 2 not inclusive)\nt[2:] start from the 3rd item, to end. (i.e index 2 is inclusive)\n\nli.reverse() reverses in place\nli.sort() sorts list in place\nli.sort(fn) function by which to sort\nsorted(li) returns a copy of a sorted list\n\ns=\"Sentence with words\"\nwords = s.split(\" \")\n\"_\".join(words)\n\na.strip('-'), a.capitalize.() all return copies\n\nDictionaries are unordered. Keys must be immutable. \n\nd.keys() gets list of keys, d.values() gets values, d.itesm() list item tuples\ndefaultdict intializes nonexistan diciontary values\ncollections import counter, counts \n\nCan return mutliple values by returning them with commas. Returned as tuple. \n\nNo function overloading. Can have operator overloading by implementing magic methods.\n\nkeyword arguments, allow function to be called outo f order. Used after all \nother agruments. ex: def fun(a, b, c), call fun(2, c=43, b=1)\n\n*args variable number of non-keyword arguments Can pass any number of args. \nCan give individual args, or pass a list and unapck it with *lst, ex. func(*lst)\n\n**kwargs any number of keyword arguments. Can pass a dictionary\nfun(**my_dict), so then key-value pairs, will become keyword arugments.\n\nUses dynamic scope. Most recent value of global var. \n\nCan have subclasses by\nclass Child_Cls(Parent_Class_Name):\n  def __init__(self, x, y):\n    Parent_Class.__init__(self, x, y)\n\ngenerators are less code than standard iterator, maintain local state automatically,\nValues are computed one at a time, so don't have to store the entire sequence in memory.\nGood for aggregating (summing/counting) in once pass, but bad if you need to check\nindividual values. \n\n\n\n\n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n In fully observable, det, known, envs the solution is a fixed set of actions.\nIn that case can just exectue actions with sensor data. Called open loop.\nOtherwise you need to use close-loop to consider sensors.\n\nSearch problem has possible envs - state space, with one it starts out in,the initial state.\n\nThen there is a goal state (can be multiple or alt)\n\nHas actions that the agent can take - applicable actions.\nTransition model says what the action will do.\nAction cost function - what's the cost of action _a_ when in _s_ to go to _s'_\n\nSolution is a path from intial to goal, optimal solution is lowest cost\n\nabstarction is **vlaid**  can translate into real world solution.\n**useful** if action easier in abstraction\n\n\n\n\n## AIMA Chapter 3.2 Example Problems\n Robot nav is like route finding. 2d if just moving, but multi if has arms/legs;also have to deal with errors.\n\nAssemby sequenceing: figure out how to optimize the order of steps in assembly\n\n## AIMA Chapter 3.3 Search Algorithms\ninput into a search algorithm is a a serach problem and output iseither a solution or failure. \nSearch tree has paths from inital state to other states, including the goal.Each node is a state, can have multiple nodes for a state. State space can be infinite.\n\nIn search start with root, then can expand the node, meaning eval actions, which generates new nodes corrpesonding to next state.\n\nFronter are nodes that have been reached but not expanded.\n\nBest first search, decide which node to expand next using an eval function _f(n)_ expand node with min valu in _f(n)_. Expand if hasn't been reached before _or_ if new cost is lower than previous cost. \n\nNode has 4 parts:\n1. State\n2. Parent: node it came from\n3. Actions: what actions to parent caused to get to this state/node\n4. Path cost: total cost from inital state\n\nRepresent frontier with a queue. Use hashtable to store reached. \n\n**Repeated states** mean that a tree can have a cycle (A-B-A), making the search tree infinite.\nMore general case of **redundant path**, which visits unnecessary nodes. \n\nGraph search is different from tree-like search because it checks if there is a redundnat paths.\nCould also just check for cycles. Can do that by keeping track of parent, and if it reappeared.\n\nTo eavluate an algorithm:\n1. Completness: find a solution if it exists/failure if doesn't?\n2. Cost optimality: lowest cost solution\n3. Time complexity: What's the time or _O()_?\n4. Space complexity: How much memory is needed? \n\nCompletness tricky in infinite spaces b/c can keep following a path forever.\nSearch needs to systematic in it's pathfinding to make sure it can reach a state.\nEx: sprial path in infinite gird. But w/no solution can't terminate\n\nMeasure time/space with:\n1. _d_/**depth**: # actions in best solution\n2. _m_ : max number of actions\n3. _b_/**branching factor**: # children for a node\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\nBFS is good when equal cost actions. Expand root, then 1 level of chidren, then 2nd level etc..\nWorks for infinte state spaces, b/c it's systemic. Similar to Best first, where _f(n)_ = depth(n)\n\nUse FIFO q, and set for states, b/c can't get a better path after 1st visit. \n\nCan use early goal testing b/c of that, where test if == goal when reach, rather than expand.\nAlways finds the optimal path if all costs are same. If solution is at depth _d_ cost is:\n$$ 1 + b + b^2 + b^3 + ... + b^d = O(b^d)$$\n\nwhere _b_ is the branching factor. b/c at each level get #(b)s * b sucessors\n_O(b^d)_ for both time and space\n\nToo big of time and space for any medium/large problem.\n\nDijkstra's algortihm = unifrom cost search, _f(n)_ is cost of path from root to node\nCan re-add items to frontier if find lower cost, do late-goal checking.\nComplexity is $$O(b^{1+\\lfloor(C^*/\\epsilon)\rfloor})$$\nwhich is >> than $b^d$, b/c always explore all possible low-cost even if not in right direction.\nIf all costs is same it's $b^{d+1}$\n\nDFS expands the deepest nodes, analogus to best first search w/ $f(n)$ is $-d$.\nUsually done as tree-search instead of graph search. Don't track visited nodes.\nNot optimal, first solution found is returned, which could be deeper than it needs to be.\n\nComplete for tree state spaces, for acylic it may revisit same state.\nFor state spaces with cycles it might be in infite loop.\nIn infinite spaces it can go on forever, not systemic. Which means it's not complete.\n\nMem complexity is $O(bm)$, w/ b = branching factor, and m = max depth\n\n**Backtracking search** only have one successor node at time (not all), so use less memory.\nDones't clone state to modify, so only keeps one state. so have a path of $O(m)$\n\n** Depth limited search**, limit the search only deapth $l$. So time complexity is\n$O(b^l)$ and space complexity is $O(bl)$. Can be incomplete if $l$ is too small.\nif know diameter of the graph can set $l$ to that.\n\n**Iterative deepening search**, don't pick $l$ but rather systematically increase\nit's value between iterations. \nSpace complexity is $O(bd)$ when there is a solution and $O(bm)$ if no solution (finite graph). \nOptimal if all costs are equal, complete if acycilc or if check for cycles. \nTime complexity is $O(b^d)$, $O(b^m)$ if no solution.\n\nSame big O in time as BFS, though with higher constants. Ex: b = 10, d = 5\n$$N(IDS) = (d)b^1 + (d - 1)b^2 + (d - 2)b^3 + ...  + b^d$$\n$$N(IDS) = 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450$$\n$$N(BFS) = 10 + 100 + 1,000 + 10,000 + 100,000 = 111,110$$\n\n**Bidirection search**: search from initial state and backwards from goal state\nuntil they meet, better time comlexity b/c $b^{d/2} + b^{d/2} < b^{d}$\nif $f(n)$ is the path cost, and optimal cost is $C^*$ then at most cost of a  node will be $C^* /2$\n\n\n\n## Module 3 Lecture Notes\n\nNeed \n1. A set of states\n2. an intial state\n3. Actions a set of possible actions\n4. Transition model - for all actions in a state, result of applying action in the state\n5. Path cost - perfmesure what is the cost, per perfmesure. Could be #actions, #miles\n6. Goal - test if a state is a goal state. \n\nWhat is the tranisition if apply action to a state in vaccum world? If in left and apply left\nstay in the same state. If apply right, new state. \n\nA solution is a sequence of actions from intial state to a goal state.\nOptimal solution has lowest path cost. \n\nState space - all states reachable from the inital state by some sequence\nPath - set of acitons between states\nFrontier - states that are available for expanding\nSolution - path from s_i to s_f,  where s_f = goal\n\nGeneral process\nintialize frontier to intial state\ndo\n  if frontier is empty then return Failure\n  choose a leaf node to expand by some strategy and remove from frontier\n  if node  state is the goal state reun solution\n  otherwise expand the node and add decendents to frontier. \n\nfailure to detected repeated states makes linear problem exponential. Keep track\nof visited states to avoid revisiting. But state space can be large, so this\ncan take up a lot of memory. \n\nUninformed search - don't use any infromation from the world. All non-goal nodes look good.\nSearch strategy = order of tree expansion. \n\nBFS - expand shallowest node first. Use a FIFO search \nDFS - expand deepest nodes. Not complete, fails in infite depth, loops. \nNot complete or optimal. Complete in finite spaces though. \n$O(b^m)$ is terrible if m is much larger than d. But if solutions are dense\ncould be faster. Space is linear $O(b*m)$ b/c have to keep branches at least level\n\nDFS is better if space is restricted, lots of possible soluitions w/long paths\nand wrong paths end quickly.\n\nBFS if possibly infinte. Solutions have short paths. can quickly discared unlikely paths. \n\nIDDFS - increase the depth at each iteration. Explore all nodes at level 0, 1, 2...\netc.. but in DFS order. Complete if no infinite paths. Time is $O(b^d)$, space is $O(bd)$\noptimal if step is 1\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **Goal formulation** - decide on objectives -> actions\n* **Problem formulation** - describe the states/actions for goal\n* **Solution** - sequence of actions that gets to the goal\n* **Standardized problem** - used to demo a method\n* **Real-world-problem** - actually in the world, non-standard\n* **Touring problem** - all points that must be visted\n* **Tsp** - lik touring, visit all cites with lowest cost\n* **Vlsi layout** - how to place componets/connect on a chip whil optimize area, delaymax outpput\n* **Diameter** - max distance b/t 2 nodes in a graph\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n \n**Greedy best first search**, chooses node w/lowest $h(n) to expand, making it\nNot always optimal cost. \n\ntime and space complxity is $O(abs(V))$ but can reduce on certain problems to $O(bm)$\n\n$h(n)$ is **consistent** if $$h(n) <= c(n, a, n') + h(n')$$\nThat is the (est cost of n -> goal) <= (cost n -> n') + (est cost of n' -> goal)\nthis is the triangle inequality\n\nconsistent heuristic => admissible, but admissible not necessairly consistent \n\nconsistent heuristic never repeat states, so don't renter into reached\n\nIf $h(n)$ is inadmissible, A* might be optimal.  If there is an optimal\npath where $h(n)$ is admissible for every node on that path \n\nOr if optimal cost is $C$, and 2nd best is $C_2$, and $h(n) <= truecost(n)+C_2-C$\n\nCosts of $g(n)$ are mono increase. But costs of $h(n)$ are only mono increase\nif consistent. \n\nA\\* is **optimally efficient**. It\n1. expands all neighbs of inital state w/ $f(n)<C^*$, \n2. might expand some nodes that are $f(n)=C^*$$, \n3. Doesnt' expand nodes with $f(n)>C^*$\n \n**Satisficing** solutions not optimal but acceptable. Might use inadmissible heuristic\n\n**Weighted A\\* Search** weight the heuristic so $f(n)=g(n)+W*h(n)$, $W>1$.\nWill get a soultion that's between $C^* and W*C^*$\n\n**Bounded suboptimal search** look for solution w/cost <= $W*C^*$\n\n**Bounded-cost** sol is less than some $C$\n**unbounded-cost** accept any fast found sol. Ex. speedy search\n$h(n) = count(actions(n))$\n\n$A\\*$  uses memory $O(b^d)$. Can try an implement where keep state only in \n_reached_ or _frontier_, not both. Or remove state from _reached_ if no longer needed. \nEx. don't allow U turns, So only check _frontier_, no need for _reached_.\n\nOr can use **reference count** of # times state has been reached,\nremove it if can't be reached again after a certain count.\nin grid world has 4 neighbs, so can only reach it 4 times. \n\n**Beam search** put a limit on frontier size. Only keep a certain # of nodes\nwith the best $f(n)$. Incomplete and suboptimal. Can be near-optimal. Like a \nvery focused version of search. Can also keep all node w/ $f(n)$ that is $<= \\delta +$ \nthe best $f(n)$.\n\n**Iterative-deepening A\\* Search** like IDDFS. Don't have to keep all reached in mem\nbut added cost of repeat visits of states. Cutoff is $f(n)$, updated to be the smallest\n$f(n)$ that missed the cutoff in pervious round. Good for integer $f(n)$s b/c\ncan't have more iterations that the $C^*$, but if f cost is diff for every node\nthen number of iteraitons could be the same as the # of states\n\n**RBFS** and **IDA\\* ** use too little memory. \n\n**Memory bounded A\\* ** and Simplified. Keep as many as mem allows, then drop worst leaf.\nBut back up value of forgotten leaf to parent. Expands newest- and deletes oldest- best.\n\nSMA is complete if $d$ < mem size. Optimal if optimal solution is <= $d$ < mem size.\n\nSMA is good when node generation more expensive than frontier/reached set. \n\nMem limitations can make it impossible to solve, if need to regenerate nodes. \n\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n effective branching factor, number of nodes to expand to get to solution\n$$ N = b^* + (b^*)^2 + ... + (b^*)^d$$\n\nBetter heuristic has a b* closer to 1. Another measure is reduction of effective depth. \nBy $k_h$ amount so cost is $O(b^{d-k_h})$\n\nIf heuristic h2 always >= h1, h2 **dominates** h1.\n\nRelaxed problem removes some restriction on problem actions, to help generate _h_.\nLeads to a expanded graph of the original problem graph.\nHeuristic needs to be easy to generate, solve problem w/o search\nIf have multiple heursitcs can use a composite, picking the highest one for a node.\n\nCan have a database of suproblems of original problem, storing solution for\nevery possible subproblem. Go from goal to other permutation, storing cost.\nThen heuristic becomes a lookup. Can do it from multiple instances of the subproblem,\nand the combine the heuristic by taking the max of $h_i(n)$. Can't add b/c overlap costs.\nCould only count of pieces that are important in subproblem, making a **disjoint pattern database**.\n\nMapping services use precomputation between points. Do it with landmarks. Fo every L,\nand every v find optimal path v->L. Storing the costs creates an inaddmissible heuristic.\nwhere $h(n) = min [ C(n,L) + C(L, goal)]$ for Ls\n\nCan be admissilbe if use $h(n) = max [ C(n,L) - C(goal, L)]. Chose a landmark beyond the goal,\nand subtract the extra distance beyond the goal. \n\nPick landmarks by finding center of graph and then adding Ls furthest out around the center.\n\nMetalevel state space - the internal state space of the algorithm. \nex. each state is a search tree. Can use learnig to see which paths in the metalevel\nare not helpful. Goals is minimize computationl cost + path cost. \n\nCan use features in machine learning to improve heuristic generation. Ex. x1\nnum of misplaced tiles, or x2, adjustcent tiles that shouldn't be. Can combine\nfeatures with $h(n)= c_1x_1(n) + c_2x_2(n)$. Not necessarily admissible or consistent\n\n\n\n## Module 4 Lecture Notes\n\nNeed \n1. A set of states\n2. an intial state\n3. Actions a set of possible actions\n4. Transition model - for all actions in a state, result of applying action in the state\n5. Path cost - perfmesure what is the cost, per perfmesure. Could be #actions, #miles\n6. Goal - test if a state is a goal state. \n\nWhat is the tranisition if apply action to a state in vaccum world? If in left and apply left\nstay in the same state. If apply right, new state. \n\nA solution is a sequence of actions from intial state to a goal state.\nOptimal solution has lowest path cost. \n\nState space - all states reachable from the inital state by some sequence\nPath - set of acitons between states\nFrontier - states that are available for expanding\nSolution - path from s_i to s_f,  where s_f = goal\n\nGeneral process\nintialize frontier to intial state\ndo\n  if frontier is empty then return Failure\n  choose a leaf node to expand by some strategy and remove from frontier\n  if node  state is the goal state reun solution\n  otherwise expand the node and add decendents to frontier. \n\nfailure to detected repeated states makes linear problem exponential. Keep track\nof visited states to avoid revisiting. But state space can be large, so this\ncan take up a lot of memory. \n\nUninformed search - don't use any infromation from the world. All non-goal nodes look good.\nSearch strategy = order of tree expansion. \n\nBFS - expand shallowest node first. Use a FIFO search \nDFS - expand deepest nodes. Not complete, fails in infite depth, loops. \nNot complete or optimal. Complete in finite spaces though. \n$O(b^m)$ is terrible if m is much larger than d. But if solutions are dense\ncould be faster. Space is linear $O(b*m)$ b/c have to keep branches at least level\n\nDFS is better if space is restricted, lots of possible soluitions w/long paths\nand wrong paths end quickly.\n\nBFS if possibly infinte. Solutions have short paths. can quickly discared unlikely paths. \n\nIDDFS - increase the depth at each iteration. Explore all nodes at level 0, 1, 2...\netc.. but in DFS order. Complete if no infinite paths. Time is $O(b^d)$, space is $O(bd)$\noptimal if step is 1\n\n\n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Zero sum games, only 1 winner. \nMax moves first\ngame tree is a search tree with all moves to game end (i.e. terminal state). \n\ncan either use a eval function to tell who is winning or run simulations.\n\nHave $S_0$, intila state, \nTo-Move(s): current player\nActions(s): Actions in state S\nResult(s, a): What is result of action in a state\nIs-Termina(s): Is the game over?\nUtility(s,p): What's the score the player?\n\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Ply is a move by a single player\nEvaluate the max utility based on each action, knowing subsequent action by min.\n\nMight not always be best to do a optimal move when playing a suboptimal player,\ncan take a risk if porbablity of good move is high, and think min player won't \nfind its optimal move.\n\nMinimax uses DFS, if b moves at teach step, with max depth m, $O(b^m)$ time complexity.\nIf generate all actions then $O(bm)$, if one at a time then $O(m)\n\nIn multiplayer games, backup the value of the max for the player whose turn it is at the leaf\n\nAlliances can form in multiplayer games b/t weaker position players. Can also form\nin 2 player non-zero-sum games. \n\n**Alpha-beta pruning** \n$\u0007lpha$ is highest value along the path for max, value be at least that much\n$\beta$ is the lowset value along the path for min, value at most that much\nif value < $\u0007lpha$ for min, or > $\beta$ for max, return.\n\nIf leaves are ordered best to worst, would have $O(b^{m/2}$, branching factor would be $b^{1/2}$\nIf randomly guess would have $O(b^{3m/4})$.\n\nKiller moves are the best moves. If try them first for killer move heuristic.\n\nCan reduce redundency by keeping a **transposition table** that is a table of\nthe heurisitc value of states. \n\n**Type A stragegy**, limit all moves up to a depth, and estimate the utility. Width over depth. Chess\n**Type B stargegy**, go only with most promising moves as far as possible. Depth over width.  Go.\n\n\n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n \nFor heuristic a-b search,use eval func to estimate util of state, and decide if \nto cut it off before terminal state.\n\neval vunction is somewhere betwen win and loss. Can work calculating\nfeatures of state (ex. #whit-pawns). Then has probability of win given features\ngrouped into categories. \n\nSince above is too expeirence depednent, eval each feature and combine. Ex.\ngive value to each chess piece. Then arrangement might be another feature.\n$$Eval(s)  = \\sum_{i=1}^n {W_if_i(s)}$$\neval func needs to be correlated to chance of winning, can be non-linear.\n\nCan cutoff after reaching a certain depth, retrun the eval for the player\nof the state at that depth.\n\nEval func should only be applied when the position is **quiescent**, no upcoming\nmove that will change the eval a lot. Otherwise need to continue the search.\nCan limit quiescent search to only certain important moves.\n\n**Horizion effect** delay inevitable move to later time.\n**Singular extensions** add moves that are def better than all others.\n\n**Forward pruning** removes moves that seem bad, but might be good. Saves\ncomp but could result in mistake. Type B strate.\n\nProbcut algorithm prunes out nodes that are probably not in [$\u0007lpha$, $\beta$]\n\nlate move reduction - reduce depth of search for later moves.\n\nCan use table lookup for the opening and ending of chess. Then can switch to search.\n**Policy** maps a state to the best move. Retrograde minimax, ex. reverse\nmoves from wining positions in chess.\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\nStochastic games have an aspect of chance. Needs to include\nchance nodes in the search, + max/min nodes.\n\nneed to calculate the expected value of a position - the **expectiminimiax** val.\n\nif want to use an approx with cutoff search, need to use values that are pos\nlinear transfomrations for probability. \n\nTime complexity is $O(b^mn^m)$ where n is number of rolls (i.e. possibilities)\n\nCan prune chance nodes by bounding utility values.\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n \nDecision theory is about choosing an action based on immediate result. Assume\nepisodic env. **Utilitity funcion** evals a state, and **expected utility** is the avg.\nutility value of outomes * probability that it happens. \n\n**Max expected utility (MEU)** has rational agent pick the action with\nmax expected utility. \n\nDoesn't operationalize AI rationality though. Still need to estimate probabilities\nof states and possibly search for uitilities of states. \n\nUtil function applies step by step. If agent maxes it and it reflects perfmes\nthen it will have best perfmes.\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n \nOutcomes for actions are a lottery L =[$p_1,S_1; p_2S_2, ... p_n,S_n$],\nand each S_i can be a state or a lottery. \n\n6 constraints for prefrence relations - axioms of utility theory:\n1. Orderability: Either A > B, B > A or A~B\n2. Transitivity: (A > B) $\\wedge$ (B > C) => A > C\n3. Continuity: indifferent between a lottery for [A,C], and p =1 B \nA > B > C => $\\exists$ p [p,A; 1-p, C] ~ B\n4. Substitutability: if indifferent between two lotteries, then also indifferent about\ncomplex lotteries that just sub the original lotterires:\n A ~ B => [p, A; 1 - p, C] ~ [p, B; 1 - p, C]\n\n5. Monotonicity: If A > B, then prefer lottery that has higher probability of A\n A > B => (p > q <=> [p,A; 1 - p, B] > [q, A; 1 - q, B])\n6. Decomposability: can use probabilities to decompose a lottery to simpler verison\n[p, A; 1-p, [q,B; 1 - q, C]] ~ [p, A; (1 - p)q,B; (1 - p)(1 - q),C]\n\nAxioms lead to:\n1. Existence of utility function: have to have a Util func to be consistent w/axiom.\n2. Expected utility of lottery: sum of probabilities times U(outcome)\n\nutil function not necessirly unique. Can tranfrom util function to $aU(S)+b$ get\nthe same result.\nIn det enviornments only need to rank states, called **ordinal utility function**\n\n\n \n\n## AIMA Chapter 16.3 Utility Functions\n Prefrence elicitation - show people choices and observe\nto determine utility func\n\nHelpful to have some scale. So fix u-top = \"best utility\" and u-bot\"worst possible\". \nCan normalize with u-top =1  and u-bot $ =0\n\ncan find util of S by finding $p$ where agent S ~ [p,u-top; (1-p),u-bot].\n\n**micromort** - 1 in mill chance of death. Used to estimate values\n\n**QALY** - quality adjusted life year. How much patients are willing to accept\nshorter life expectancy to avoid disability. \n\nUsually prefer more money to less, (AEQ). This is monotonic preference for money.\n**Expected monetary value** of a gamble is probability of win*payoff, + probability of loss*0.\nutility not directly proportional to money. 1st million has more utility than 2nd. \n\nUtility of money estimated to be logritimic. S shape when combined with negatives.\nThat is, additional debt worht extra ris after a certain point. \nOn positive side $U(L) < U(S_{EMV(L)})$, S is a sure thing. So agents are risk averse\nin the positive end. Risk-seeking in the negative end. \n\ncertaininty equivalent is how much you'd accept as sure thing in place of a gamble\nto make more.\n\nDifference between EMV(L) - certaininty equivalent = insurance premium. \n\nFor small changes, looks linear on the curve, so is **risk-neutral**. \n\nHave to use estimate utilitiy in real world. Even though unbiased, real outcome\nwill typically be worse. This is because tend to select optimistic estimates.\nWith more choices more optimistic estaimtes are more likely. this is the otpimizer's\ncurse. \n\nDecision theory is normative, how should agents act. Descriptive theory says how\nactually act. \n\nEx. certainity effect - people prefere things that are certain. Don't trust\nstatesd probabilities. Prefer known probabilities. \n\n\n\n\n## Module 5 Lecture Notes\n\nGames have an opponent, as compared with puzzle\n\nSimple game envs:\nmultiagent, static (no changes while thinking), discrete -finite set of perceptions/actions\nfull observable - can see the entire game\nstrategic - next move is dteremined by current state + agent action + opponent action\n\nKey properiteis:\n1. 2 players alternate moves\n2. Zero sum game\n3. Clear set of legal moves\n4. Well definied outcomes\n\nCard games are stochastic, not fully observable. Real time strat games are continous.\n\nEvaluate how good a position is by eval funciont $f(n)$. Based on statsic features of the board\n\n\nMinimax - have to assume min will reply w/ best posible move. No hope chess.\nMax value of children, min for min value of children. \n\nExpectimax there is a chance added to the minimax search. Values in the \nchance nodes are avg. case outcomes. Chance nodes are like min nodes\nbut outcome is uncertain. Take weighted average of children. \n\npruning more useful in large branching. Order affects pruning,\nif the nodes are not randomly distributed, may not be efficient. \nIf a game is deterministic exptiminimimax == minimax\n\n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n**constraint satisfaction problem** has states with sets of variables with values.\nsolved when  all variables' values satisifies constraints for the variable.\n\nCSP has:\nX: set of vars\nD: set of domains for every variable\nC: set of constriants\n\n$D_i$ is set of valid valudes for $X_i$.\n$C_j$ has (scope, rel) pair, where scope is all the vars affected by the constraint,\nrel is definition vals the var can be. \n\nAssignment of values to vars is **consistent** if no constraints are violated.\n**Complete** is one where every variable is assigned a val.\nSolution is consistent & complete.\nPartial assignment - some are not assigne. Some not assigned, but assigned ones are valid.\n\nCan solve problems faster with CSP than atomic state-space search. Can prune a lot.\n\nEx. is car assembly jobs.\nTask1_time + task1_duration <= Task2_time, where task2 must occur after task1\nor also have disjunctiv contrastins where Task_A + time <= Task_B or Task_B+time <= Task_A\n\nSimple CSP have discrete, finite domains. No algorithm for solving nonlinear constraints\non integer variables. \nCan also have continous domains. Linear programming is best example. Constrains are linear ineq.\n\nTypes of constraints:\n1. Unary: constriant on the single variable. ex. SA != green.\n2. Binary: constraint w/ 2 variables, ex. SA != NSW\n\n**binary CSP** only unary and binary constraints. \n\n**global constraint** is on $n$ number of variables. Doesn't have to be all.\nAlldiff is a common one where all vars need to be diff.\n\nconstraint hypergraph has regular nodes and hypernodes for constraints .\nCan transfrom finite-domain constraint to binary constraint w/aux variables.\nCan also use a **dual graph**, where constraints become the variables, and binary\nconstraint for all pairs of constraints that have the overlapping variables. \n\nCan have preference constraints that rank prefrence of solutions. Can use cost\nto represent constraints, w/ more prefereable costing less. This is a constrained\noptimization problem COP.\n\n\n\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\nCSP alogrith can assign vars or use **constraint propagation**,\nusing constraints to remove vals for a var, which then affects another var,\nand so on. Can reduce or eliminate search.\n\n**local consistency**, each var is a node and constraints are edges. To have\nlocal consistency eliminate inconsistent vals.\n\nTypes of local consistency:\n1. Node-consistent: for all vars, all vals in its domain satisfy unary constraints.\nDo this at the start of solution. Sometimes expect only binary constraints, so\nthis is a pre-processing step.\n2. Arc consitency: for all var pairs, all vals in domain satisfy binary constriants. \ni.e for $X_i$ and $X_j$, and for $D_i$ there is a value in $D_j$ that satisfy\nconstraint on $(X_i, X_j)$\n\nAC3 enforces arc-consistency. Has que of arcs. Pop off an arc $(X_i, X_j)$,\nIf change $D_i$, add all arcs ($X_k$, $X_i$) for each neighbor $X_k$ of $X_i$.\nSo now need to recheck if small domain $D_i$ causes elimination in $D_k$.\nIf $D_i$ = $\\emptyset$ know no solution exists. New CSP = Original CSP,\nbut arc-consistent will have faster search. \nChecking arc consistency is $O(d^2)$ time for each of the $c$ constraints,\nand can add an arc at most $d$ times, so time complexity is $O(cd^3)$\n\n**Path consistency**, uses implicit constraints by examinig triples of \nvariables. Kind like how arc consistency maeks unary constraints strong by\nlooking at binary constraints?\nPath consistent if for every {$X_i = a , X_j = b$} that's arc consistent,\nX_m has value to satisfy {$X_i, X_m$} and {$X_m, X_j$}. Consitent path from\n$X_i$ -> $X_m$ -> $X_j$\n\n**K consistency**, if for consistent assignment to set of $k -1$ vars can\nhave consistet assignment to k_th var. 1 consistnecy is with empty set (aka \nnode consistency). 2-consistency == arc. \n\nCSP is strongly k-consistent if k consistent, k-1 consistent...1 consistent. \nIf strongly k-consistent, can find solution for each $X_i$ by looking at\nd values and it be consistent with $X_1 ... X_{i-1}$. Total complexity is\n$O(k^2d). But CSP is NP-complete.\n\nFor alldiff, for any singleton value in a domain, remove that val from\ndomains of all other variables. If an empty set is produced, or fewer values\nthan vars, than inconsistency is detected. \n\n**Resource constraint**, at most check sum of min val of all domains, to see if\nviolate at most constraints. Can also delete max val if not consistent with min vals.\n\n**Bounds propogration** if two constraints, may change lower and upper bounds based on \ncombination of constraints. Bound consistent if every X, for every upper\nand lower bound value, there is a value in Y that is consistent.\n\n\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n**commutativity** property, if the order of assignment doesn't matter. reduced by\nfactor of n! (n = # vars), to $d^n$ leaves. \n\nBacktracking algorithm picks unassigned var, assigns it value and then recurses.\nReturn if solved, if failure restore to previous state. \n\nFor choosing variables, can do it in order, or randomly but not optimal.\nUse the **minimum-remaining-values heuristic** to chose var with fewest vals. Aka\n\"Most contrained variable\" and \"fail-first\". Prunes tree faster.  \n\n**degree heuristic** - reduce branching by choosing var with most constraints\non unassigned vars (the degree of the node)\n\nAfter choosing a variable, choose value. **least-constarining-value** heuristic,\nchoose val that eliminates fewest choices for neighbors. Fail-last strategy,\nbecause looking for one solution, so choose most likely to work (least constarining)\n\nAC3 reduces var domains before search, can be good during search too. Can use\n**Forward checking** when a var is assigned, forward checking checks arc consistnecy.\nBut doesn't look that far.\n\n**Maintainin Arc Consistency** does check for that. After a var is assigned\ncalls AC3 but only on ($X_j, X_i$) for $X_j$ unassigned neighbor of $X_i$.\nThen AC3 does its thing, and if fails know can backtrack. \n\nBactracking can be improved if backtrack to the variable that made a var impossible.\nTarck set of assignments that in conflict with a var, called a **conflict set**.\nJumps back to the most recent assignment in the conflict set. Can use forward\nchecking, adding assignment x to  neighbor X of Y to Y's conflict set. Somewhat\nredundent with forward checking and MAC?\n\nCan use stronger notion that it's the assignment plus assignment of preceding var\nand subsequent vars. **conflict-directed backjumping**.\n\nWorks by jumping back from $X_j$ to previous variable $X_i$ in conflict set, and \nadd conflict set of $X_j$ to that of $X_i$. (except X_i itself).\n\n**Constraining learning** find minimum set of vars in conflict that led to failure.\nThese vars and the vals are recorded as **no-good**, and don't allow the combination.\n\n\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nLocal search can work well for CSP. \n\n**min-conflicts** heuristic, Assign a value to each var. pick one  that's \nconflicted then change the value to something that results in lowest number of conflicts\n\nMin-conflict is really effective in easy problems. Where solutions are densely distributed.\nWork well for hard problems.\n\nMay use plateau search where move sideways to states with equal scores. **Tabu search**\nkeeps a list of visted states and doesn't repeat.\n\n**constrain weighting** gives a weight to each constraint. Choose var/val to change\nthat will create lowest toatal weight across wrong assignments. Adjust weight of\nconstraints that are violted by assignments. Most difficult constraints get heavier over time.\n\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n**Independent subproblems** - are the components connected. Total work is $O(d^cn/c)$,\nwhich is less than $O(d^n)$ work for non-decomposed problem. \n\nA constraint graph is a tree if vars are only connected by 1 path. Any such\nCSP can be solved in linear time in $n$ (n= # vars). \n\n**Directional arc consistency** - every ($X_i$, $X_j$) is consistent with $j > i$\n\nto solve tree-structured CSP pick a root node, and toplogically sort remaining nodes.\nEnforce arc-consitency in $O(n)$ steps, need to compare at most $d$ values for every \none of the $n-1$ edges, so $O(n*d^2)$. Once arc consistent can choose values at each step.\nEach parent and child pair is consistent, so can pick something for parent, and have child\nconsistent. \n\nCan reduce a constraint graph to a tree in a few ways\n\nCutset conditioning, assign a value to some var so that reamining vars are a tree,\nremove vals from other domains inconsistent with that assignment. If there is a\nsolution for the new CSP, it will be consitent with the removed node. Since \nmight not have a solution for the chosen value for the removed var, need to try \nevery val. \n\nTotal time complexity is $O(d^c * (n-c)d^2$. Because need to try $d^c$ for the \nvars in S, the cycle cutset being removed, and then need to solve a tree with size\n$n - c$. With smaller $c$ have bigger savings. But $c$ can be $(n-2)$. \nFinding smallest cycle cutset is NP-Hard. \n\nAnother option is to try tree decomposition. Graph becomes a tree where every node\nis a set of vars such that:\n1. Every var appears in at least 1 node\n2. If 2 vars have a constraint, they need to be togeter in at least 1 node\n3. If a var is in 2 nodes, $u, v$ in the tree, it must be in every node on the path\nconnecting $u,v$\n\n1& makes sure that all vars and constraints are represented. 3 means the var has\nthe same value everywhere. \n\nThen can solve in $O(n*d^2)$, n=# tree nodes, d is the largest domain, where\nin the tree domain is a set of tuples of values.\n\ntree width is size of largest node - 1. Tree width a graph is the min width of all\ntree decompositions. graph w/ tree width $w$ can be solved in $O(nd^{w+1})$.\n\nFinding tree decomposition is NP-hard. When there is a cycle-custer size $c$\nthere is a tree width $w < c + 1$.\n\n$value symmetry$$, can permute values in a solution. Can break that by imposing\nsymmetry breaking constraint, like requiring alphabetical ordering. NP hard. \n\n\n\n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n**knowledget base (KB)** composted of **sentences** in knowledge representation\nlanguage. Axioms are un-derived (i.e. bases).\nTo add a setnence you \"Tell\" and to query you \"Ask\" the KB.\n\n**Infrence** - derives new sentences from old. \n\nSequence is \n1. Tell  KB what the agent percieved, \n2. Asks KB for best action, \n3. Agent programs Tells KB which action it chose. Returns action.\n\ndescription are given at the knowledge leve, not at the implementation level.\nTell it waht it needs to know. Declarative approach. Proceudal approach puts\ndesired behavior in the code. \n\nLearning agent learns by itself, knowledge comes from series of percepts.\ncan be autonomous \n\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n\nWumpus world is deterministic, discrete, static, single agent, sequential,\npartially observable. Location of pits can either be unobserved, and the\ntransition model is complete, and discovery completes the knoweldge of the state\nor tranistion model is incompelte and discovery fills in the transition model. \n\n\n\n\n## AIMA Chapter 7.3 Logic\n \n**Syntax** says all sentences are properly formed.\nLogic defines **semantics** - truth of a setnence in a possible world. Ex:\nx + y = 4 is true in world where x = 2, y =2. Must be either true or false in a\nworld. \n\n**Model** - math abstraction of a world with fixed truth vals for all sentences.\n$m$ **satisfies** $\u0007lpha$  or $m$ is a model of $\u0007lpha$ means that \n$\u0007lpha$ sentence is true in model $m$.  \n\nIf $a$ logically follows from $b$, say $a$ entails $b$:\n$a \\models b$, which means that in every model where $a$ is true, $b$ is true\nso $a \\models b \\iff M(a) \\subseteq M(b)$. So $a$ is stronger.\n\nKB is a set of sentences, false in $m$ that contridicts known facts. \n\nCan look at a setence and see if in every world where KB true, is $a_i$ also true?\nif so then $KB \\models a_i$\n\nOTH if $\\exists$ $m$ where KB is true and $a_j$ is false, then $KB$ doesn't entail $a_j$.\nInconclusive if $a_j$ is holds in a paritcular world. This is called model checking.\nCheck that $M(KB) \\subseteq M(a)$. Model checking works for finite spaces of models.\n\nInference is finding the entailment $a$ needle in the haystack of $KB$. \nSay that $KB \u000bdash_i a$, which is a is derived from KB by i\n\nIf an algorithm derives entailed sentences it is sound/truth-preserving. \nIf the algorithm can derive all entailed sentences it is complete. \nCan be a problem for infinite consequences can still have completenesl\n\nIf KB is true in real world then any derived sentence by sound algorithm is also true. \n\n**Grounding** is there a connection b/t KB and real env? Sensors connect it. But\nsome rules are not based on sensors, but on perceptual experience. Learning. \n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\natomic sentences have 1 propositiona sybmol, the proposition \nis T/F.\n\nComplex setnences are amde from simpler sentences and logical connectives.\nliteral is either atomic or negated atomic. \n\n$ A \\Rightarrow B$ is an implication, A is the permise and B is conclusion/consequent. \n\nOrder precendence:\n$\\neg$ $\\wedge$ $\\vee$ $\\Rightarrow$ $\\iff$\n\n$P \\Rightarrow Q$ is true unless $P = T$ and $Q = F$\n$P \\iff Q$ is true iff P&Q are the same value. \n\n$P \\Rightarrow Q$ is saying if P is true than Q is true, but if P is false,\nthen no conclusion and so Q can be anything. The sentence as a whole is true.\nSentence is only false if $P$ is true and $Q$ is false. \n\nCan generate all models and see where KB it true, and some sentence $a$ is true.\nKB is true if $R_i$s are true, which are the sentences\n\n$O(2^n)$ models. Space is $O(n)$ b/c DFS. \n\nPropositional entailment is co-NP-compelte. \n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n \n**theorem proving**, apply rules of inferences to create proofs of a sentence\n\n**logical equivalence** $a \\equiv b$ iff $a \\models b$ and $b \\models a$.\n\nIf a sentence is T for all models it is valid. Ex: $P \\vee \\neg P$. Tautology. \n\nFor $a, b$,  $a \\models b$ iff $a \\Rightarrow b$ is valid. Either\n$a \\Rightarrow b$ in every model, or prove $(a \\Rightarrow b) \\equiv True$\n\nSAT if sentence can hold true in some model. SAT is NP-complete \n\nValidity related to sat, $a$ sat iff $\neg a $ not valid\n$a \\models b$ iff $(a \\wedge \\neg b)$ is unsat. ==Proof by contridiction. \nAssume $\\neg b$, show contridicts $a$\n\nproof search alg: Initial state of KB. Actions are the inf-rules applied\nto sentences on top half of inf-rule -> bottom of the inf-rule. \nThe goal get to state that has the target sentence to prove \n\nMore efficent than model search b/c can ignore irrelevant propositions. \n\nEntainled sentences are monotonic, can only increase as information is added.\n$KB \\models a \\Rightarrow (KB \\wedge b) \\models a$. Can apply rules whenver. \n\nResolution + complete search -> complete inference algorithm.\n\nUnit resolution rule. For literals, $l_1...\\vee ... l_k$ if $l_i$ and $m$ are complementary,\n& we have $m$ then have new clause w/o $l_i$.\n\ncan be generalized with multi pairs, only resolve one pair of literals at a time. \n\nResulting clause should contain only 1 copy of each literal. **factoring**. \n\nReso based theroem prover can see if $a \\models b$ holds for any any a b\n\nReso is only applid to disjunct. Every sentence can be translated to CNF. \n\nReso alg work by contridiction. Convert an implies into CNF.\nThen apply reso rule to the clauses. Add resulting clause to the set\nIf no new clauses to add KB doesn't entail a.\nIf yield an emptly clause then KB entails a. Empty clause implies a contridiction\n\nReso closure is the set S  all clauses dervied by applying the reso-rule to c's in S.\n\nGround resolution theorem: for an unsat set of c's, the reso closure is empty\n\n**Definite clause** is a disjunction of literals w/ only 1 positve\nex: $(\\neg A \\vee \\neg B \\vee C)$\n\n**Horn clause** is disjunction of literals w/ <= 1 positive. Def clause=Horn.\n\n**Goal clause** 0 positives. \n\n2 horn claues resolved get a horn clause\n\nKB w/ only definite clauses:\n1. Every def clause can be transformed to implication\nex: $(\\neg A \\vee \\neg B \\vee C)$ can be $(A \\wedge \\B \\Rightarrow C )$\nIn this horn, permise=**body**, conclusion=**head**.\nSingle pos literal is a **fact**\n\n2. Can use forward/backward chaining. Base for logic programming. \n3. Entalinment can be done in linear time wrt KB.\n\nForward chaining check if $KB \\models q$, starts with facts and adds conclusions\nfrom implications where facts are known to set. Keeps going til\nfind q or no more inferences. linear time.  Data-driven reasoning.\n\n\nBackward chaining is the other way. From q, finds implication in KB w/conclusion q. \nIf 1 implications can proved true, then q is true. linear time. Goal-directed reasoning. \n\n\n\n## Module 7 Lecture Notes\n\nKnowledge based agents reason over a representation of the world. \nDifferent from the problem-solving agents is the representation of the world.\nIn problem-sovling the representaiotns are atomic.\n\nHave a KB which is a set of sentences written in knowledge representation language\n\naxioms are given setnences. Dervied sentences are derived from other sentences through inference.\n\nB entails a is only if M(b) is a subset of M(a)\nevery model whre b is true, a is also true\n\ndoes KB entail a? If in every model where KB is true, a is also true.\nIf there is a model where KB is true, but a is false, then KB doesn't entail a.\n\nInfrence Rules:\n\n**Modus Ponens**: \n$\\frac{a \\Rightarrow b, b}{b}$\nIf know that \"a then b\", and given a, then know b. \n\n**And elimination**:\n$\\frac{a \\wedge b}{a}$. Given a and b, a holds.\n\n**Biconditional elimination**\n$\\frac{a \\iff b}{(a \\Rightarrow b) \\wedge (b \\Rightarrow a)}$ \nand\n$\\frac{(a \\Rightarrow b) \\wedge (b \\Rightarrow a)}{a \\iff b}$ \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}