{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "brNDGX-kvzds"
   },
   "source": [
    "# Template for Notes for CIS 521 Midterm 1\n",
    "\n",
    "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
    "\n",
    "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
    "\n",
    "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "aPtM8g7R0Pds"
   },
   "source": [
    "# Instructions\n",
    "\n",
    "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
    "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
    "3. Read the notes below about how you can format your summaries.\n",
    "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
    "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
    "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
    "* Run the last cell of this notebook\n",
    "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
    "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
    "* In the print options, change the layout from Landscape to Portrait. \n",
    "* Clicking the Save, will save a PDF that you can then print.\n",
    "\n",
    "## Formatting Notes\n",
    "\n",
    "1. The max length for each section's summary is 500 words / 3000 characters.\n",
    "2. You can also write a 2000 word summary of the lectures for each module.\n",
    "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
    "2. You can use Markdown formatting for your summaries. \n",
    "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
    "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
    "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
    "```\n",
    "def function():\n",
    "      print('hello world')\n",
    "```\n",
    "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "cw5IpDLCZa4W"
   },
   "source": [
    "## Example summary\n",
    "\n",
    "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "lzaavW96tcxM",
    "outputId": "aadb3c59-f716-4564-ff73-050087799ed4"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The example summary is 116 words long, so you could write an additional 384 words.\n"
     ]
    }
   ],
   "source": [
    "chapter_2_1_example = \"\"\"\n",
    "Regular expressions are an algebraic notation for characterizing \\\n",
    "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
    "Only the first matching result will be shown. The search string is case sensitive, \\\n",
    "but it can consist of a single character or a sequence of characters. \\\n",
    "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
    "for characters over a range. The caret specifies the non-existence of a character. \\\n",
    "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
    "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
    "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
    "...\n",
    "\"\"\"\n",
    "\n",
    "length = len(chapter_2_1_example.split(\" \"))\n",
    "print(\"The example summary is {len} words long, so you could write an additional \\\n",
    "{remaining} words.\".format(len=length, remaining=(500-length)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "s3Uk9gQTevcj"
   },
   "source": [
    "## Example summary length\n",
    "\n",
    "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "8DvZ57A-djo1",
    "outputId": "d59d6de9-232c-4038-882c-425b0639aec4"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 500\n",
      "The length in characters is 3030\n"
     ]
    }
   ],
   "source": [
    "# This is an example of a 500 word placeholder\n",
    "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
    " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
    " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
    " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
    " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
    " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
    " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
    " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
    " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
    " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
    " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
    " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
    " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
    " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
    " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
    " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
    " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
    " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
    " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
    " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
    " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
    " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
    " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
    " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
    " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
    " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
    " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
    " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
    " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
    " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
    " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
    " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
    " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
    " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
    " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
    " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
    " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
    " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
    "\n",
    "print(\"The length in words is\", len(placeholder.split(' ')))\n",
    "print(\"The length in characters is\", len(placeholder))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "5yG3-YncJfTB"
   },
   "source": [
    "# Permissions to use your summaries\n",
    "\n",
    "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
    "\n",
    "1. Please enter your name.  \n",
    "\n",
    "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
    "\n",
    "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "2RECnJArJew4"
   },
   "outputs": [],
   "source": [
    "name = \"\"\n",
    "permission = True\n",
    "anonymous = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GZZXyrV-xuAp"
   },
   "source": [
    "# Module 1 - Intro to AI"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "Y2NfE1CKxzS-"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
    "\n",
    "chapter1_1 = \"\"\"\n",
    "Artificial intelligence is concerned with understanding the definition of rationality. \n",
    "There have been various definitions of rationality, and people have proposed numerous methods of quantifying and capturing rationality.\n",
    "1. The first approach is the Turing test approach, which seeks to determine whether a computer can \"think\" by assessing its (1) NLP, (2) knowledge representation, \n",
    "(3) automated reasoning, and (4) machine learning. An extension would be the total Turing test, which requires physical interaction with objects in the world.\n",
    "2. A contrasting approach is the cognitive modeling approach, whicch is concerned with understanding the human mind and our inner thoughts.\n",
    "3. The third approach is the \"laws of thought\" method. Aristotle determined that syllogisms and logic can be used to solve puzzles and thought. However, it generates rational thoughts\n",
    "instead of the rational action required for intelligent behavior.\n",
    "4. Rational-agent approach involves agents and acting rationally. Advantages include (1) more general since it's more open to possible mechanisms of achieving rationality, (2) \n",
    "more amenable to scientific development. This approach has generally prevailed across the field, even being deemed the \"standard model\".\n",
    "\n",
    "When building rational agents, need to keep in mind that we want AI to pursue our objectives instead of their objectives.\n",
    "\"\"\" \n",
    "\n",
    "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
    "chapter27_1 = \"\"\"\n",
    "- Turing argues that human behavior is too complex to be captured by formal set of rules (underlies informal rules that cannot be instilled into a machine)\n",
    "- Good Old-Fashioned AI (GOFAI)\n",
    "- **Qualification problem**\n",
    "  - Tough to capture all appropriate behavior in a set of logical rules\n",
    "- Situated agents respond better than disembodied logical inference engines\n",
    "  - I.e. understanding a dog comes better from seeing and interacting rather than \"Dog => Mammal\"\n",
    "- Embodied cognition\n",
    "  - Need to study the system as a whole: mind, body, environment\n",
    "- Programs are better than humans in some areas, but significantly behind on others.\n",
    "- Programs cannot be exactly like humans\n",
    "- Today, programs have achieved some aspects of human performance, but not representative of real humans outside encoded areas\n",
    "\"\"\"\n",
    "chapter27_2 = \"\"\"\n",
    "- **Polite convention**\n",
    "  - Assume that everyone thinks, should translate to machines as well\n",
    "- **Chinese room** argument\n",
    "  - Computers do not think since they are simply following rules\n",
    "- **Consciousness**\n",
    "  - Awareness of the outside world, oneself, and experiences\n",
    "- Humans have advantage over machines due to subjectivness and ability to appreciate subjective experiences\n",
    "\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
    "chapter2_1 = \"\"\"\n",
    "Agents interact with their environment through sensors (which fetch percepts) and perform actions through actuators.\n",
    "An agent's decisions at any point in time can be based on given knowledge and percept sequence (history), but not on the future or anything it hasn't perceived\n",
    "\"\"\"\n",
    "chapter2_2 = \"\"\"\n",
    "Consequentialism is when we evaluate an agent based on its consequences rather than the decisions.\n",
    "One part of consequentialism is the performance measure, which evaluates any sequence of states from the environment.\n",
    "In general, it is better to design a performance measure based on what wants to be achieved rather than accordin to how you think the agent should act.\n",
    "\n",
    "**Rational agent** = rational agent selects action that will maximize expected utility based on provided percept sequences.\n",
    "Rationality maximizes expected utility. Perfection and omniscience, on the other hand, maximize actual utility.\n",
    "Rational agents must gather as munch information as possible and learn, thereby improving on itself autonomously.\n",
    "\"\"\"\n",
    "chapter2_3 = \"\"\"\n",
    "**Task environments** = problems that rational agents are the solutions of. Need to fully define prior to designing agent.\n",
    "**PEAS** = Performance, Environment, Actuators, Sensors.  \n",
    "  - I.e. Taxi Driver\n",
    "    - P: safe, fast, legal, comfortable, maximize profits\n",
    "    - E: roads, traffic, pedestrians, customers\n",
    "    - A: steering, acccelerator, brake, signal\n",
    "    - S: cameras, radar, speedometer, GPS\n",
    "\n",
    "Entities whose behavior maximizes a measure that depends on another agent's behavior must be viewed as an agent.\n",
    "\n",
    "Chess is a competitive multiagent environment, whereas taxi-driving is a cooperative multiagent environment.\n",
    "\n",
    "Experiments are often done on a variety of environments, typically in a group called an **environment class**\n",
    "\"\"\"\n",
    "chapter2_4 = \"\"\"\n",
    "Agent architecture: $$agent = architecture + program$$\n",
    "Agent program can only use current percept, whereas agent function has access to entire percept history.\n",
    "\n",
    "**Table-Driven Agent**:\n",
    "```\n",
    "def TABLE_DRIVEN_AGENT(percept)\n",
    "  append percept to the end of percepts\n",
    "  action = LOOKUP(percepts, table)\n",
    "  return action\n",
    "```\n",
    "  - Not feasible, daunting size\n",
    "  - No physical agent can store this table\n",
    "  - No time to create the table\n",
    "  - Cannot learn from all the table entries\n",
    "    - Need to produce rational behavior from smaller program\n",
    "\n",
    "**Simple reflex agents**\n",
    "- Acting on innate reflex (condition-action rule)\n",
    "- Only works if correct decision can be found based on only current percept (if fully observable)\n",
    "- Susceptible to even a little bit of unobservability\n",
    "- Randomized simple reflex agent might outperform a deterministic simple reflex agent\n",
    "- In single-agent environments, randomization is typically not rational\n",
    "\n",
    "**Model-based reflex agents**\n",
    "- Method for handling partial observability\n",
    "- Agent leeps internal state that depends on history and reflects parts of unobserved parts of current situation\n",
    "- Need two kinds of information:\n",
    "  - How the environment changes\n",
    "    - Impacts of an agent's decisions\n",
    "    - World changes independently of the entity\n",
    "    - Also known as **transition model**\n",
    "      - I.e. if car turns steering wheel, car turns\n",
    "  - How the environment's changes are reflected in agent's percepts\n",
    "    - Also known as **sensor model**\n",
    "      - I.e. if camera gets wet, droplets partially obscure view\n",
    "- Typically cannot guess environment exactly\n",
    "\n",
    "**Goal-based agents**\n",
    "- Search and planning are key subareas dedicated to finding sequences to achieve goals\n",
    "- More flexible\n",
    "\n",
    "**Utility-based agents**\n",
    "- Specifies tradeoffs for conflicting goals\n",
    "- Worried about expected utility rather than absolute utility due to not being omniscient\n",
    "- Need to keep track of environment (difficult)\n",
    "\n",
    "- Any agent can be built into a learning agent\n",
    "  - Allows agent to grow more competent than later on\n",
    "  - Divided into 4 components:\n",
    "    - Learning element --> making improvements\n",
    "    - Performance element --> selecting external actions\n",
    "    - Critic --> informs agent of its performance relative to standard\n",
    "    - Problem generator --> suggesting actions to new experiences\n",
    "      - Sacrifice short term for long term gains\n",
    "\n",
    "- More expressive language is more concise, but more learning is more complex as expressiveness increases\n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module1_lecture_notes = \"\"\"\n",
    "- An agent is specified by an agent function that maps a sequence of percept vectors P to an action a from a set A\n",
    "- Agents perceive their environment through **sensors** and act upon it through **actuators**\n",
    "  - Humans (sensors = {eyes, ears}, actuators = {hands, legs, mouth})\n",
    "  - Other agents: robots, thermostats, touchless faucets\n",
    "- **Rationality**\n",
    "  - In Philosophy, AI is concerted with *consequentialism*, in that we evaluate an agent based on the consequences only\n",
    "  - In Economics, rationality is a framework for understanding behavior. Assuming people have preferences and choose what they prefer, we aggregate all decisions to see total social behavior.\n",
    "- **Performance measure**\n",
    "  - Objective criteria to determine success of an agent given percepts\n",
    "  - Design measures based on *\"what should be achieved\"* rather than *\"how you think the agent will act\"*\n",
    "  - In most cases, total omniscience is not possible, so act out of expectation\n",
    "- **Task environments**\n",
    "  - Problem specification for with the agent is a solution\n",
    "  - PEAS (specifications for a task environment)\n",
    "    - **P**erformance measure, **E**nvironment, **A**ctuators, **S**ensors\n",
    "- Fully Observable vs. Partially Observable\n",
    "  - Fully Observable --> sensors can detect all states of the environment\n",
    "  - Partially Observable --> sensors do not have access to all states of the environment\n",
    "- Deterministic vs. Nondeterministic vs. Stochastic\n",
    "  - Deterministic --> know with certainty immediate result of action\n",
    "  - Nondeterministic --> outcome is uncertain based on action (games of chance)\n",
    "  - Stochastic --> nondeterministic where we have quantified probabilities/likelihood of outcomes\n",
    "- Episodic vs. Sequential\n",
    "  - Episodic --> agent processes self-contained episodes (decision is independent of past decisions)\n",
    "  - Sequential --> immediate decision impacts future\n",
    "- Static vs. Dynamic\n",
    "  - Static --> environment remains unchanged while deliberating over action\n",
    "  - Dynamic --> environment that changes while deliberating\n",
    "- Discrete vs. Continuous\n",
    "  - Discrete --> finite set of actions and can separate different states\n",
    "  - Continuous --> follow range of values\n",
    "- Single Agent vs. Multi Agent\n",
    "  - Single Agent --> only one agent is attempting to maximize outcome\n",
    "  - Multi Agent --> exist other agents acting rationally\n",
    "\n",
    "Reflex agents - one that selects an action based on the current percept (episodic)\n",
    "\n",
    "Problem solving agent - must plan ahead and involves a computational search\n",
    "\n",
    "Hardest environment = Continuous, partially observable, stochastic, multi agent\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",
    "\"artificial intelligence\" : \"understanding and building intelligent entities\",\n",
    "\"rationality\" : \"doing the right thing\",\n",
    "\"Turing test\" : \"thought experiment to question: 'Can a machine think?'. Pass if human cannot tell difference in responses\",\n",
    "\"natural language processing\" : \"communicate successfully in a human language\",\n",
    "\"knowledge representation\" : \"store what it can gather through hearing and learning\",\n",
    "\"automated reasoning\" : \"respond to questions and to reach new conclusions\",\n",
    "\"machine learning\" : \"adapt to new scenarios and to extrapolate patterns\",\n",
    "\"Total Turing Test\" : \"extension of Turing test to require interaction with objects and people (computer vision & robotics)\",\n",
    "\"cognitive science\" : \"builds theories of human mind by connecting connects computer models and psychological experiments\",\n",
    "\"weak AI\" : \"machines acting as if they were intelligent\",\n",
    "\"strong AI\": \"machines acting intelligently (consciously thinking)\",\n",
    "\"agent\" : \"anything that can perceive and act in an environment\",\n",
    "\"rational agent\" : \"agent that acts to maximize expected outcome\",\n",
    "\"value alignment problem\" : \"system's goals and objectives should be aligned with humans\",\n",
    "\"percept\" : \"agent’s perceptual inputs at any given instance\",\n",
    "\"percept sequence\" : \"history of everything an agent as perceived\",\n",
    "\"agent function\" : \"mapping of percept sequence to action\",\n",
    "\"agent program\" : \"concrete implementation of agent program acting in a physical system\",\n",
    "\"omniscience\" : \"knows the real outcome of actions in advance (distinct from rationality)\",\n",
    "\"information gathering\" : \"performing actions in order to modify and enhance future percepts\",\n",
    "\"exploration\" : \"information gathering done to an initially unknown environment\",\n",
    "\"autonomy\" : \"ability to handle its own percepts and learn on its own without relying heavily on designer\",\n",
    "\"task environment\" : \"problems that rational agents are the solutions of\",\n",
    "\"unobservable\" : \"agent has no sensors\",\n",
    "\"competitive\" : \"competing against each other to maximize personal utility (usually at the expense of the other)\",\n",
    "\"cooperative\" : \"working with each other to maximize collective utility\",\n",
    "\"stochastic\" : \"nondeterministic process that explicitly deals with probabilities\",\n",
    "\"semidynamic\" : \"environment doesn't change over time, but performance score does\",\n",
    "\"simple reflex agent\" : \"agent that ignores prior percept, only looking at current percept\",\n",
    "\"transition model\" : \"how the world works\",\n",
    "\"sensor model\" : \"how the world's state is reflected in the percepts\",\n",
    "\"utility function\" : \"performance measure of utility\",\n",
    "\"atomic representation\" : \"each state of the world is independent/no structure\",\n",
    "\"factored representation\" : \"fixed set of attributes representing each state\",\n",
    "\"structured representation\" : \"underlying representations can be described explicitly\",\n",
    "\"localist representation\" : \"direct mapping between concepts and memory locations\",\n",
    "\"distributed representation\" : \"concept spread over multiple locations (resistant to noise)\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "elCCgY64spuq"
   },
   "source": [
    "## Preview of your notes for Module 1\n",
    "\n",
    "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "gYYeNcdM_maE",
    "outputId": "19a3b4c3-16a9-4316-8ccd-48d3642f4899"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       "\n",
       "Artificial intelligence is concerned with understanding the definition of rationality. \n",
       "There have been various definitions of rationality, and people have proposed numerous methods of quantifying and capturing rationality.\n",
       "1. The first approach is the Turing test approach, which seeks to determine whether a computer can \"think\" by assessing its (1) NLP, (2) knowledge representation, \n",
       "(3) automated reasoning, and (4) machine learning. An extension would be the total Turing test, which requires physical interaction with objects in the world.\n",
       "2. A contrasting approach is the cognitive modeling approach, whicch is concerned with understanding the human mind and our inner thoughts.\n",
       "3. The third approach is the \"laws of thought\" method. Aristotle determined that syllogisms and logic can be used to solve puzzles and thought. However, it generates rational thoughts\n",
       "instead of the rational action required for intelligent behavior.\n",
       "4. Rational-agent approach involves agents and acting rationally. Advantages include (1) more general since it's more open to possible mechanisms of achieving rationality, (2) \n",
       "more amenable to scientific development. This approach has generally prevailed across the field, even being deemed the \"standard model\".\n",
       "\n",
       "When building rational agents, need to keep in mind that we want AI to pursue our objectives instead of their objectives.\n",
       "\n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       "\n",
       "- Turing argues that human behavior is too complex to be captured by formal set of rules (underlies informal rules that cannot be instilled into a machine)\n",
       "- Good Old-Fashioned AI (GOFAI)\n",
       "- **Qualification problem**\n",
       "  - Tough to capture all appropriate behavior in a set of logical rules\n",
       "- Situated agents respond better than disembodied logical inference engines\n",
       "  - I.e. understanding a dog comes better from seeing and interacting rather than \"Dog => Mammal\"\n",
       "- Embodied cognition\n",
       "  - Need to study the system as a whole: mind, body, environment\n",
       "- Programs are better than humans in some areas, but significantly behind on others.\n",
       "- Programs cannot be exactly like humans\n",
       "- Today, programs have achieved some aspects of human performance, but not representative of real humans outside encoded areas\n",
       "\n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       "\n",
       "- **Polite convention**\n",
       "  - Assume that everyone thinks, should translate to machines as well\n",
       "- **Chinese room** argument\n",
       "  - Computers do not think since they are simply following rules\n",
       "- **Consciousness**\n",
       "  - Awareness of the outside world, oneself, and experiences\n",
       "- Humans have advantage over machines due to subjectivness and ability to appreciate subjective experiences\n",
       "\n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       "\n",
       "Agents interact with their environment through sensors (which fetch percepts) and perform actions through actuators.\n",
       "An agent's decisions at any point in time can be based on given knowledge and percept sequence (history), but not on the future or anything it hasn't perceived\n",
       "\n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       "\n",
       "Consequentialism is when we evaluate an agent based on its consequences rather than the decisions.\n",
       "One part of consequentialism is the performance measure, which evaluates any sequence of states from the environment.\n",
       "In general, it is better to design a performance measure based on what wants to be achieved rather than accordin to how you think the agent should act.\n",
       "\n",
       "**Rational agent** = rational agent selects action that will maximize expected utility based on provided percept sequences.\n",
       "Rationality maximizes expected utility. Perfection and omniscience, on the other hand, maximize actual utility.\n",
       "Rational agents must gather as munch information as possible and learn, thereby improving on itself autonomously.\n",
       "\n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       "\n",
       "**Task environments** = problems that rational agents are the solutions of. Need to fully define prior to designing agent.\n",
       "**PEAS** = Performance, Environment, Actuators, Sensors.  \n",
       "  - I.e. Taxi Driver\n",
       "    - P: safe, fast, legal, comfortable, maximize profits\n",
       "    - E: roads, traffic, pedestrians, customers\n",
       "    - A: steering, acccelerator, brake, signal\n",
       "    - S: cameras, radar, speedometer, GPS\n",
       "\n",
       "Entities whose behavior maximizes a measure that depends on another agent's behavior must be viewed as an agent.\n",
       "\n",
       "Chess is a competitive multiagent environment, whereas taxi-driving is a cooperative multiagent environment.\n",
       "\n",
       "Experiments are often done on a variety of environments, typically in a group called an **environment class**\n",
       "\n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       "\n",
       "Agent architecture: $$agent = architecture + program$$\n",
       "Agent program can only use current percept, whereas agent function has access to entire percept history.\n",
       "\n",
       "**Table-Driven Agent**:\n",
       "```\n",
       "def TABLE_DRIVEN_AGENT(percept)\n",
       "  append percept to the end of percepts\n",
       "  action = LOOKUP(percepts, table)\n",
       "  return action\n",
       "```\n",
       "  - Not feasible, daunting size\n",
       "  - No physical agent can store this table\n",
       "  - No time to create the table\n",
       "  - Cannot learn from all the table entries\n",
       "    - Need to produce rational behavior from smaller program\n",
       "\n",
       "**Simple reflex agents**\n",
       "- Acting on innate reflex (condition-action rule)\n",
       "- Only works if correct decision can be found based on only current percept (if fully observable)\n",
       "- Susceptible to even a little bit of unobservability\n",
       "- Randomized simple reflex agent might outperform a deterministic simple reflex agent\n",
       "- In single-agent environments, randomization is typically not rational\n",
       "\n",
       "**Model-based reflex agents**\n",
       "- Method for handling partial observability\n",
       "- Agent leeps internal state that depends on history and reflects parts of unobserved parts of current situation\n",
       "- Need two kinds of information:\n",
       "  - How the environment changes\n",
       "    - Impacts of an agent's decisions\n",
       "    - World changes independently of the entity\n",
       "    - Also known as **transition model**\n",
       "      - I.e. if car turns steering wheel, car turns\n",
       "  - How the environment's changes are reflected in agent's percepts\n",
       "    - Also known as **sensor model**\n",
       "      - I.e. if camera gets wet, droplets partially obscure view\n",
       "- Typically cannot guess environment exactly\n",
       "\n",
       "**Goal-based agents**\n",
       "- Search and planning are key subareas dedicated to finding sequences to achieve goals\n",
       "- More flexible\n",
       "\n",
       "**Utility-based agents**\n",
       "- Specifies tradeoffs for conflicting goals\n",
       "- Worried about expected utility rather than absolute utility due to not being omniscient\n",
       "- Need to keep track of environment (difficult)\n",
       "\n",
       "- Any agent can be built into a learning agent\n",
       "  - Allows agent to grow more competent than later on\n",
       "  - Divided into 4 components:\n",
       "    - Learning element --> making improvements\n",
       "    - Performance element --> selecting external actions\n",
       "    - Critic --> informs agent of its performance relative to standard\n",
       "    - Problem generator --> suggesting actions to new experiences\n",
       "      - Sacrifice short term for long term gains\n",
       "\n",
       "- More expressive language is more concise, but more learning is more complex as expressiveness increases\n",
       "\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       "\n",
       "- An agent is specified by an agent function that maps a sequence of percept vectors P to an action a from a set A\n",
       "- Agents perceive their environment through **sensors** and act upon it through **actuators**\n",
       "  - Humans (sensors = {eyes, ears}, actuators = {hands, legs, mouth})\n",
       "  - Other agents: robots, thermostats, touchless faucets\n",
       "- **Rationality**\n",
       "  - In Philosophy, AI is concerted with *consequentialism*, in that we evaluate an agent based on the consequences only\n",
       "  - In Economics, rationality is a framework for understanding behavior. Assuming people have preferences and choose what they prefer, we aggregate all decisions to see total social behavior.\n",
       "- **Performance measure**\n",
       "  - Objective criteria to determine success of an agent given percepts\n",
       "  - Design measures based on *\"what should be achieved\"* rather than *\"how you think the agent will act\"*\n",
       "  - In most cases, total omniscience is not possible, so act out of expectation\n",
       "- **Task environments**\n",
       "  - Problem specification for with the agent is a solution\n",
       "  - PEAS (specifications for a task environment)\n",
       "    - **P**erformance measure, **E**nvironment, **A**ctuators, **S**ensors\n",
       "- Fully Observable vs. Partially Observable\n",
       "  - Fully Observable --> sensors can detect all states of the environment\n",
       "  - Partially Observable --> sensors do not have access to all states of the environment\n",
       "- Deterministic vs. Nondeterministic vs. Stochastic\n",
       "  - Deterministic --> know with certainty immediate result of action\n",
       "  - Nondeterministic --> outcome is uncertain based on action (games of chance)\n",
       "  - Stochastic --> nondeterministic where we have quantified probabilities/likelihood of outcomes\n",
       "- Episodic vs. Sequential\n",
       "  - Episodic --> agent processes self-contained episodes (decision is independent of past decisions)\n",
       "  - Sequential --> immediate decision impacts future\n",
       "- Static vs. Dynamic\n",
       "  - Static --> environment remains unchanged while deliberating over action\n",
       "  - Dynamic --> environment that changes while deliberating\n",
       "- Discrete vs. Continuous\n",
       "  - Discrete --> finite set of actions and can separate different states\n",
       "  - Continuous --> follow range of values\n",
       "- Single Agent vs. Multi Agent\n",
       "  - Single Agent --> only one agent is attempting to maximize outcome\n",
       "  - Multi Agent --> exist other agents acting rationally\n",
       "\n",
       "Reflex agents - one that selects an action based on the current percept (episodic)\n",
       "\n",
       "Problem solving agent - must plan ahead and involves a computational search\n",
       "\n",
       "Hardest environment = Continuous, partially observable, stochastic, multi agent\n",
       "\n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Artificial intelligence** - understanding and building intelligent entities\n",
       "* **Rationality** - doing the right thing\n",
       "* **Turing test** - thought experiment to question: 'Can a machine think?'. Pass if human cannot tell difference in responses\n",
       "* **Natural language processing** - communicate successfully in a human language\n",
       "* **Knowledge representation** - store what it can gather through hearing and learning\n",
       "* **Automated reasoning** - respond to questions and to reach new conclusions\n",
       "* **Machine learning** - adapt to new scenarios and to extrapolate patterns\n",
       "* **Total turing test** - extension of Turing test to require interaction with objects and people (computer vision & robotics)\n",
       "* **Cognitive science** - builds theories of human mind by connecting connects computer models and psychological experiments\n",
       "* **Weak ai** - machines acting as if they were intelligent\n",
       "* **Strong ai** - machines acting intelligently (consciously thinking)\n",
       "* **Agent** - anything that can perceive and act in an environment\n",
       "* **Rational agent** - agent that acts to maximize expected outcome\n",
       "* **Value alignment problem** - system's goals and objectives should be aligned with humans\n",
       "* **Percept** - agent’s perceptual inputs at any given instance\n",
       "* **Percept sequence** - history of everything an agent as perceived\n",
       "* **Agent function** - mapping of percept sequence to action\n",
       "* **Agent program** - concrete implementation of agent program acting in a physical system\n",
       "* **Omniscience** - knows the real outcome of actions in advance (distinct from rationality)\n",
       "* **Information gathering** - performing actions in order to modify and enhance future percepts\n",
       "* **Exploration** - information gathering done to an initially unknown environment\n",
       "* **Autonomy** - ability to handle its own percepts and learn on its own without relying heavily on designer\n",
       "* **Task environment** - problems that rational agents are the solutions of\n",
       "* **Unobservable** - agent has no sensors\n",
       "* **Competitive** - competing against each other to maximize personal utility (usually at the expense of the other)\n",
       "* **Cooperative** - working with each other to maximize collective utility\n",
       "* **Stochastic** - nondeterministic process that explicitly deals with probabilities\n",
       "* **Semidynamic** - environment doesn't change over time, but performance score does\n",
       "* **Simple reflex agent** - agent that ignores prior percept, only looking at current percept\n",
       "* **Transition model** - how the world works\n",
       "* **Sensor model** - how the world's state is reflected in the percepts\n",
       "* **Utility function** - performance measure of utility\n",
       "* **Atomic representation** - each state of the world is independent/no structure\n",
       "* **Factored representation** - fixed set of attributes representing each state\n",
       "* **Structured representation** - underlying representations can be described explicitly\n",
       "* **Localist representation** - direct mapping between concepts and memory locations\n",
       "* **Distributed representation** - concept spread over multiple locations (resistant to noise)\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "from IPython.display import display, Markdown, Latex\n",
    "\n",
    "module1_sections = [\n",
    "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
    "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
    "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
    "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
    "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
    "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
    "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
    "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
    "]\n",
    "\n",
    "\n",
    "def length_check(sections):\n",
    "  warnings = \"\"\n",
    "  for section, summary in sections:\n",
    "    max_word_length = 500\n",
    "    max_character_length = 3000\n",
    "    if \"lecture\" in section.lower():\n",
    "      # It's OK to do longer summaries of the lectures\n",
    "      max_word_length = 2000\n",
    "      max_character_length = 12000  \n",
    "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
    "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
    "  return warnings\n",
    "\n",
    "def length_check_definitions(definitions):\n",
    "  warnings = \"\"\n",
    "  for concept, definition in definitions.items():\n",
    "    if(len(definition.split(' ')) > 20):\n",
    "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
    "  return warnings\n",
    "\n",
    "\n",
    "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
    "  markdown = \"\"\n",
    "\n",
    "  # Check summary lengths\n",
    "  warnings = length_check(sections)\n",
    "  if warnings != \"\":\n",
    "    markdown += \"## \" + warnings\n",
    "\n",
    "  # Check definition lengths\n",
    "  warnings = length_check_definitions(definitions)\n",
    "  if warnings != \"\":\n",
    "    markdown += \"## \" + warnings\n",
    "\n",
    "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
    "\n",
    "\n",
    "  for section, summary in sections:\n",
    "    if show_placeholder and summary == \" Your summary here \":\n",
    "      summary = placeholder\n",
    "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
    "  \n",
    "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
    "  for concept, definition in definitions.items():\n",
    "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
    "  return markdown\n",
    "\n",
    "\n",
    "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
    "display(Markdown(module1_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9xRbdqDox2zD"
   },
   "source": [
    "#Module 2 - Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "DpBvu7EMx7sy"
   },
   "outputs": [],
   "source": [
    "# No readings for this module.  Instead you can summarize the lecture instead.\n",
    "\n",
    "# Lecture notes \n",
    "module2_lecture_notes = \"\"\"\n",
    "- Suitable for everyday tasks, easy to understand (like English)\n",
    "- Garbage collected, intuitive syntax\n",
    "- Lots of 3rd party libraries\n",
    "  - NumPy (MatLab)\n",
    "  - Pandas (data analysis)\n",
    "  - Sklearn (ML)\n",
    "  - Pytorch, TensorFlow (deep learning)\n",
    "\n",
    "- Strongly Typed\n",
    "  - Cannot do `\"foo\" + 2`, get type by doing `type(object)` or `isinstance(object, type)`\n",
    "- Everything is represented as an Object\n",
    "- Dynamically Typed\n",
    "  - `type(var)` is automatically determined and found\n",
    "  - Although nice, disadvantage is that type errors are only caught at runtime\n",
    "- Strings are immutable\n",
    "\n",
    "- `x[:]` creates a shallow copy of the list `x`\n",
    "\n",
    "**Tuples**\n",
    "- Immutable ordered sequence of items\n",
    "- Cannot be modified after creation\n",
    "- Can be of mixed types\n",
    "- `my_tuple = (21, 'abc', 4.56, \"hello\")`\n",
    "- Works with indexing `my_tuple[2]` or `my_tuple[-1]` and slicing `my_tuple[1:3]`\n",
    "\n",
    "**Counter**\n",
    "```python\n",
    "from collections import Counter\n",
    "d = Counter()\n",
    "d['a']    # 0\n",
    "d['dog'] += 10\n",
    "d['dog']  # 10\n",
    "```\n",
    "\n",
    "- No overloading (function names must be unique)\n",
    "- Non-default arguments must always precede default arguments (`SyntaxError`)\n",
    "- `*args` is a way to pass in a variable number of non-keyword arguments\n",
    "- `**kwargs` - pass in variable number of keyword arguments\n",
    "- Default arguments are only evaluated the first time (memoization)\n",
    "\n",
    "- Functions are first class functions (treated as variables)\n",
    "\n",
    "```python\n",
    "class Subclass(Parent_Class):\n",
    "  # class attributes go here\n",
    "  def __init__(self, ...):\n",
    "    self.name = \"\"\n",
    "```\n",
    "\n",
    "**Magic Methods**\n",
    "- Examples: `__init__`, `__len__`, `__copy__`, `__cmp__`, `__add__`, `__neg__`\n",
    "- `if __name__ == '__main__':`\n",
    "\n",
    "**List Comprehension**\n",
    "- `[expression for name in list if filter]`\n",
    "- Same idea for dictionary and set comprehensions\n",
    "\n",
    "**Generators**\n",
    "- Iterator\n",
    "- Inserted by usinig `yield` keyword\n",
    "- Can be called as a for loop\n",
    "- Lazy evaluation (will stop when reaches first yield, then will continue)\n",
    "- Benefits:\n",
    "  - Less code\n",
    "  - Values computed as needed\n",
    "  - Avoid storing entire sequence in memory\n",
    "- `StopIteration` exception (`try: except StopIteration:`)\n",
    "\n",
    "**Imports**\n",
    "```python\n",
    "import math\n",
    "math.sqrt(9)\n",
    "\n",
    "from math import sqrt\n",
    "sqrt(9)\n",
    "\n",
    "import numpy as np\n",
    "```\n",
    "\"\"\"\n",
    "\n",
    "# Each definition should be at most 20 words long.\n",
    "module2_definitions = {\n",
    "\"strongly typed\" : \"objects of different types cannot interact\",\n",
    "\"dynamically typed\" : \"exact type is determined at runtime\",\n",
    "\"mutability\" : \"able to be modified and aliased\",\n",
    "\"duck typing\" : \"dynamic typing, check for presence of function/attribute\"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "ydOK__lwWgdp",
    "outputId": "dabf8a8f-34d3-488e-d414-9ee954f356d4"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       "\n",
       "- Suitable for everyday tasks, easy to understand (like English)\n",
       "- Garbage collected, intuitive syntax\n",
       "- Lots of 3rd party libraries\n",
       "  - NumPy (MatLab)\n",
       "  - Pandas (data analysis)\n",
       "  - Sklearn (ML)\n",
       "  - Pytorch, TensorFlow (deep learning)\n",
       "\n",
       "- Strongly Typed\n",
       "  - Cannot do `\"foo\" + 2`, get type by doing `type(object)` or `isinstance(object, type)`\n",
       "- Everything is represented as an Object\n",
       "- Dynamically Typed\n",
       "  - `type(var)` is automatically determined and found\n",
       "  - Although nice, disadvantage is that type errors are only caught at runtime\n",
       "- Strings are immutable\n",
       "\n",
       "- `x[:]` creates a shallow copy of the list `x`\n",
       "\n",
       "**Tuples**\n",
       "- Immutable ordered sequence of items\n",
       "- Cannot be modified after creation\n",
       "- Can be of mixed types\n",
       "- `my_tuple = (21, 'abc', 4.56, \"hello\")`\n",
       "- Works with indexing `my_tuple[2]` or `my_tuple[-1]` and slicing `my_tuple[1:3]`\n",
       "\n",
       "**Counter**\n",
       "```python\n",
       "from collections import Counter\n",
       "d = Counter()\n",
       "d['a']    # 0\n",
       "d['dog'] += 10\n",
       "d['dog']  # 10\n",
       "```\n",
       "\n",
       "- No overloading (function names must be unique)\n",
       "- Non-default arguments must always precede default arguments (`SyntaxError`)\n",
       "- `*args` is a way to pass in a variable number of non-keyword arguments\n",
       "- `**kwargs` - pass in variable number of keyword arguments\n",
       "- Default arguments are only evaluated the first time (memoization)\n",
       "\n",
       "- Functions are first class functions (treated as variables)\n",
       "\n",
       "```python\n",
       "class Subclass(Parent_Class):\n",
       "  # class attributes go here\n",
       "  def __init__(self, ...):\n",
       "    self.name = \"\"\n",
       "```\n",
       "\n",
       "**Magic Methods**\n",
       "- Examples: `__init__`, `__len__`, `__copy__`, `__cmp__`, `__add__`, `__neg__`\n",
       "- `if __name__ == '__main__':`\n",
       "\n",
       "**List Comprehension**\n",
       "- `[expression for name in list if filter]`\n",
       "- Same idea for dictionary and set comprehensions\n",
       "\n",
       "**Generators**\n",
       "- Iterator\n",
       "- Inserted by usinig `yield` keyword\n",
       "- Can be called as a for loop\n",
       "- Lazy evaluation (will stop when reaches first yield, then will continue)\n",
       "- Benefits:\n",
       "  - Less code\n",
       "  - Values computed as needed\n",
       "  - Avoid storing entire sequence in memory\n",
       "- `StopIteration` exception (`try: except StopIteration:`)\n",
       "\n",
       "**Imports**\n",
       "```python\n",
       "import math\n",
       "math.sqrt(9)\n",
       "\n",
       "from math import sqrt\n",
       "sqrt(9)\n",
       "\n",
       "import numpy as np\n",
       "```\n",
       "\n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Strongly typed** - objects of different types cannot interact\n",
       "* **Dynamically typed** - exact type is determined at runtime\n",
       "* **Mutability** - able to be modified and aliased\n",
       "* **Duck typing** - dynamic typing, check for presence of function/attribute\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "\n",
    "module2_sections = [\n",
    "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
    "]\n",
    "\n",
    "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
    "display(Markdown(module2_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "46MQLR-Gx8dZ"
   },
   "source": [
    "#Module 3 - Search Problems"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "BN0b1eVYx-nd"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
    "chapter3_1 = \"\"\"\n",
    "- 4 phase problem-solving process:\n",
    "  - **Goal formulation** --> organizational factor, limit objectives and scope of project\n",
    "  - **Problem formulation** --> description of states and actions needed on journey\n",
    "  - **Search** --> simulation of actions, repeated until goal/solution is found or not possible\n",
    "  - **Execution** --> running actions in sequence\n",
    "- Solution is a fixed sequence of actions when located in a fully observable, deterministic, known environment\n",
    "\n",
    "**Search Problem**\n",
    "- Defined as follows:\n",
    "  - **State space** - set of locations of environment\n",
    "  - **Initial state** - starting location\n",
    "  - **Goal state(s)** - can be multiple\n",
    "  - **Actions** - `Actions(s)` gives finite set of possible actions to be run in state `s`\n",
    "  - **Transition model** - results of each possible action from `Actions(s)` (transition model)\n",
    "  - **Action cost function** - cost of applying action `a`\n",
    "\n",
    "- Need to find right level of abstraction and detail to provide to the agent (cannot be too detailed or vague)\n",
    "- Good amount of abstraction involves removing as much detail as possible while keeping validify\n",
    "\"\"\"\n",
    "chapter3_2 = \"\"\"\n",
    "Standardized vs. Real-World Problems\n",
    "\n",
    "**Standardized Problems**\n",
    "- Grid world problem\n",
    "  - 2D array of cells, i.e. vacuum world\n",
    "- Sliding tile puzzle\n",
    "  - States: location of each tile\n",
    "  - Initial state: any state\n",
    "  - Actions: `Left`, `Right`, `Up`, `Down`\n",
    "  - Transition model: moving a piece\n",
    "  - Goal: numbers in order\n",
    "  - Action cost: each costs 1 action point\n",
    "- Knuth's conjecture that any positive integer can be reached by a sequence of sqrt, floor, and factorial ops from 4\n",
    "  - States: positive real nums\n",
    "  - Initial state: 4\n",
    "  - Actions: sqrt, floor, factorial\n",
    "  - Transition model: mathematical definitions\n",
    "  - Goal: desired positive integer\n",
    "  - Action cost: each costs 1 action point\n",
    "\n",
    "**Real-World Problems**\n",
    "- Route-finding problem\n",
    "  - Examples: GPS, web surfing, streaming, airline travel\n",
    "  - Airline Travel\n",
    "    - States: each state records location, cost, status, and additional extra information\n",
    "    - Initial state: home airport\n",
    "    - Actions: take any flight from current airport, any seat class, depart after current time, etc.\n",
    "    - Transition model: take from airportA to airportB\n",
    "    - Goal: arrive at destination\n",
    "    - Action cost: cost of flight, waiting time, quality of experience, etc.\n",
    "- Touring problems\n",
    "  - Traveling salesperson problem (every city on the map must be visited)\n",
    "  - Robot navigation\n",
    "  - Automatic assembly sequencing, protein design\n",
    "\"\"\"\n",
    "chapter3_3 = \"\"\"\n",
    "- Form search tree over state space to build a graph\n",
    "  - Root is initial state\n",
    "  - Traverse tree to find node that represents goal\n",
    "\n",
    "- Frontier --> separates two regions of the graph: the region where every state has been expanded and a region where states have not been reached\n",
    "\n",
    "**Best-First Search**\n",
    "- Greedily choose node $n$ with minimum value (calculated by evaluation function)\n",
    "\n",
    "```python\n",
    "def best_first_search(problem, f):\n",
    "  node = Node(problem.initial)\n",
    "  frontier = priority queue ordered by f, with node as element\n",
    "  reached = lookup table with one entry with key problem.initial and value node\n",
    "  while not is_empty(frontier):\n",
    "    node = frontier.pop()\n",
    "    if problem.is_goal(node.state):\n",
    "      return node\n",
    "    for child in expand(problem, node):\n",
    "      s = child.state\n",
    "      if s not in reched or child.path_cost < reached[s].path_cost:\n",
    "        reached[s] = child\n",
    "        frontier.add(child)\n",
    "  return failure\n",
    "```\n",
    "- Algorithms are weak and poor if they cannot remember the past (possibly infinite due to loops)\n",
    "- **Graph search** - checks for redundant paths\n",
    "- **Tree search** - does not check for redundant paths (save space by not storing reached states)\n",
    "\n",
    "**Evaluation of Performance**\n",
    "- 4 ways:\n",
    "  - **Completeness** --> guaranteed to find a solution if one exists, or report failure\n",
    "  - **Cost optimality** --> finds solution with minimum cost\n",
    "  - **Time complexity** --> time of solution relative to number of inputs\n",
    "  - **Space complexity** --> memory/space of solution relative to number of inputs\n",
    "- Complexity may also be measured by depth $d$, maximum number of actions $m$, or branching factor/node successors $b$\n",
    "\"\"\"\n",
    "chapter3_4 = \"\"\"\n",
    "- Uninformed search algorithms do not know how close they are to the goal state\n",
    "\n",
    "**Breadth First Search (BFS)**\n",
    "- Expand nodes by successors in waves\n",
    "- FIFO queue based, use set of states instead of map\n",
    "  - *Early Goal Test* - check whether a node is a solution as soon as its visited\n",
    "  - *Late Goal Test* - check whether a node is a solution when it the node in question (popped from queue)\n",
    "- Always finds **cost-optimal solution only when all actions have the same cost**\n",
    "- Always complete\n",
    "- Time complexity: $O(b^d)$, Space complexity: $O(b^d)$\n",
    "- Memory is bigger concern than time\n",
    "  - As a result, exponential search cannot solve larger uninformed search problems\n",
    "\n",
    "**Uniform-Cost Search / Dijkstra's**\n",
    "- Used when actions have varying costs\n",
    "- Expand based on distance from source (may need to relax distances)\n",
    "- Cost of optimal solution = $C^*$, $\\epsilon$ is lower bound on cost of action\n",
    "  - Time complexity: $O(b^{1 + \\lfloor C^* / \\epsilon \\\\rfloor })$, Space complexity: $O(b^{1 + \\\\lfloor C^* / \\epsilon \\\\rfloor})$\n",
    "- Complete, cost-optimal\n",
    "\n",
    "**Depth-First Search**\n",
    "- Expands deepest nodes first\n",
    "- Implemented as a tree search instead of a graph search\n",
    "  - Does not keep reached states\n",
    "- Not cost optimal (finds the first solution)\n",
    "- Finite spaces:\n",
    "  - Efficient and complete\n",
    "- Requires less memory than other traversals\n",
    "  - Small frontier, no reached table of states\n",
    "  - Time complexity: $O(b^m)$, Space complexity: $O(bm)$\n",
    "- **Backtracking search** variant\n",
    "  - Only 1 successor generated at each time\n",
    "  - Critical for large state environments\n",
    "\n",
    "**Depth-Limited Search**\n",
    "- Similar to DFS, but include upper limit of depth $l$\n",
    "- Time complexity: $O(b^l)$, Space complexity: $O(bl)$\n",
    "- Can choose good $l$ if we know some info (ie. diameter) of the problem\n",
    "\n",
    "**Iterative-Deepening Search**\n",
    "- Similar to depth-limited search, but tries all values for $l$ from 0 upwards\n",
    "  - Terminates either when solution is found or failure value\n",
    "  - Time complexity: $O(b^d)$ when exists solution, $O(b^m)$ when no solution\n",
    "  - Space complexity: $O(bd)$ when exists solution, $O(bm)$ when no solution\n",
    "- Does not matter that nodes at top of repeated since it is much smaller compared to nodes at bottom\n",
    "- Overall, **preferred uninformed search strategy** when state space is large and depth is not known\n",
    "\n",
    "**Bidirectional Search**\n",
    "- Searches forward from start state and backwards from end state(s), terminating when the two meet\n",
    "- Keep track of two frontiers and two reached tables\n",
    "- Time complexity: $O(b^{d/2})$, Space complexity: $O(b^{d/2})$\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module3_lecture_notes = \"\"\"\n",
    "**DFS vs BFS:**\n",
    "\n",
    "*Use DFS if:* space is restricted, there are many possible solutions amnd long paths are ended quickly\n",
    "\n",
    "*Use BFS if:* possible infinite paths, some solutions have short paths\n",
    "\n",
    "For **depth limited search**, if $l = d$, then optimal. However, if $l < d$, then incomplete. if $l > d$ not optimal\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",
    "\"informed\" : \"agent can estimate its distance from the goal\",\n",
    "\"uninformed\" : \"agent cannot estimate its distance from the goal\",\n",
    "\"open-loop\" : \"ignoring percepts while on the path to a solution (guaranteed to be correct and lead to goal)\",\n",
    "\"closed-loop\" : \"monitors perepts while following path to goal (nondeterministic or possibly incorrect sequence)\",\n",
    "\"State space\" : \"set of locations of environment\",\n",
    "\"Initial state\" : \"starting location\",\n",
    "\"Goal state(s)\" : \"can be multiple\",\n",
    "\"Actions\" : \"`Actions(s)` gives finite set of possible actions to be run in state `s`\",\n",
    "\"Transition model\" : \"results of each possible action from `Actions(s)` (transition model)\",\n",
    "\"Action cost function\" : \"cost of applying action `a`\",\n",
    "\"optimal solution\" : \"lowest path cost\",\n",
    "\"model\" : \"abstract mathematical description\",\n",
    "\"abstraction\" : \"removing explicit details from representation\",\n",
    "\"standardized problem\" : \"illustrate various problem-solving methods (benchmark for algo performance)\",\n",
    "\"real-world problem\" : \"concrete solutions that people use and is unique/individual\",\n",
    "\"search algorithm\" : \"problem as input, returns a solution or none if not possible\",\n",
    "\"frontier\" : \"set of next unexpanded nodes\",\n",
    "\"Best-First Search\" : \"greedily choose node $n$ with minimum value (calculated by evaluation function)\",\n",
    "\"priority queue\" : \"queue where nodes are ordered based on priority (i.e. min cost) - best-first search\",\n",
    "\"fifo queue\" : \"first-in-first-out, queue (BFS)\",\n",
    "\"lifo queue\" : \"last-in-first-out, stack (DFS)\",\n",
    "\"graph search\" : \"checks for redundant paths (stores reached states)\",\n",
    "\"tree search\" : \"does not check for redundant paths (save space by not storing reached states)\",\n",
    "\"breadth-first search (BFS)\" : \"expand nodes by successors in waves (queue based)\",\n",
    "\"uniform-cost search\" : \"(dijkstra) least cost nodes from sourc e are expanded\",\n",
    "\"depth-first search (DFS)\" : \"expand deepest nodes first in a tree search (stack based)\",\n",
    "\"depth-limited search\" : \"DFS with maximum depth layer $l$\",\n",
    "\"iterative-deepening search\" : \"depth-limited search where all values for $l$ are tried\",\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "afc8abbf-517a-4afb-ce2d-4a66903f0552"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       "\n",
       "- 4 phase problem-solving process:\n",
       "  - **Goal formulation** --> organizational factor, limit objectives and scope of project\n",
       "  - **Problem formulation** --> description of states and actions needed on journey\n",
       "  - **Search** --> simulation of actions, repeated until goal/solution is found or not possible\n",
       "  - **Execution** --> running actions in sequence\n",
       "- Solution is a fixed sequence of actions when located in a fully observable, deterministic, known environment\n",
       "\n",
       "**Search Problem**\n",
       "- Defined as follows:\n",
       "  - **State space** - set of locations of environment\n",
       "  - **Initial state** - starting location\n",
       "  - **Goal state(s)** - can be multiple\n",
       "  - **Actions** - `Actions(s)` gives finite set of possible actions to be run in state `s`\n",
       "  - **Transition model** - results of each possible action from `Actions(s)` (transition model)\n",
       "  - **Action cost function** - cost of applying action `a`\n",
       "\n",
       "- Need to find right level of abstraction and detail to provide to the agent (cannot be too detailed or vague)\n",
       "- Good amount of abstraction involves removing as much detail as possible while keeping validify\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       "\n",
       "Standardized vs. Real-World Problems\n",
       "\n",
       "**Standardized Problems**\n",
       "- Grid world problem\n",
       "  - 2D array of cells, i.e. vacuum world\n",
       "- Sliding tile puzzle\n",
       "  - States: location of each tile\n",
       "  - Initial state: any state\n",
       "  - Actions: `Left`, `Right`, `Up`, `Down`\n",
       "  - Transition model: moving a piece\n",
       "  - Goal: numbers in order\n",
       "  - Action cost: each costs 1 action point\n",
       "- Knuth's conjecture that any positive integer can be reached by a sequence of sqrt, floor, and factorial ops from 4\n",
       "  - States: positive real nums\n",
       "  - Initial state: 4\n",
       "  - Actions: sqrt, floor, factorial\n",
       "  - Transition model: mathematical definitions\n",
       "  - Goal: desired positive integer\n",
       "  - Action cost: each costs 1 action point\n",
       "\n",
       "**Real-World Problems**\n",
       "- Route-finding problem\n",
       "  - Examples: GPS, web surfing, streaming, airline travel\n",
       "  - Airline Travel\n",
       "    - States: each state records location, cost, status, and additional extra information\n",
       "    - Initial state: home airport\n",
       "    - Actions: take any flight from current airport, any seat class, depart after current time, etc.\n",
       "    - Transition model: take from airportA to airportB\n",
       "    - Goal: arrive at destination\n",
       "    - Action cost: cost of flight, waiting time, quality of experience, etc.\n",
       "- Touring problems\n",
       "  - Traveling salesperson problem (every city on the map must be visited)\n",
       "  - Robot navigation\n",
       "  - Automatic assembly sequencing, protein design\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       "\n",
       "- Form search tree over state space to build a graph\n",
       "  - Root is initial state\n",
       "  - Traverse tree to find node that represents goal\n",
       "\n",
       "- Frontier --> separates two regions of the graph: the region where every state has been expanded and a region where states have not been reached\n",
       "\n",
       "**Best-First Search**\n",
       "- Greedily choose node $n$ with minimum value (calculated by evaluation function)\n",
       "\n",
       "```python\n",
       "def best_first_search(problem, f):\n",
       "  node = Node(problem.initial)\n",
       "  frontier = priority queue ordered by f, with node as element\n",
       "  reached = lookup table with one entry with key problem.initial and value node\n",
       "  while not is_empty(frontier):\n",
       "    node = frontier.pop()\n",
       "    if problem.is_goal(node.state):\n",
       "      return node\n",
       "    for child in expand(problem, node):\n",
       "      s = child.state\n",
       "      if s not in reched or child.path_cost < reached[s].path_cost:\n",
       "        reached[s] = child\n",
       "        frontier.add(child)\n",
       "  return failure\n",
       "```\n",
       "- Algorithms are weak and poor if they cannot remember the past (possibly infinite due to loops)\n",
       "- **Graph search** - checks for redundant paths\n",
       "- **Tree search** - does not check for redundant paths (save space by not storing reached states)\n",
       "\n",
       "**Evaluation of Performance**\n",
       "- 4 ways:\n",
       "  - **Completeness** --> guaranteed to find a solution if one exists, or report failure\n",
       "  - **Cost optimality** --> finds solution with minimum cost\n",
       "  - **Time complexity** --> time of solution relative to number of inputs\n",
       "  - **Space complexity** --> memory/space of solution relative to number of inputs\n",
       "- Complexity may also be measured by depth $d$, maximum number of actions $m$, or branching factor/node successors $b$\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       "\n",
       "- Uninformed search algorithms do not know how close they are to the goal state\n",
       "\n",
       "**Breadth First Search (BFS)**\n",
       "- Expand nodes by successors in waves\n",
       "- FIFO queue based, use set of states instead of map\n",
       "  - *Early Goal Test* - check whether a node is a solution as soon as its visited\n",
       "  - *Late Goal Test* - check whether a node is a solution when it the node in question (popped from queue)\n",
       "- Always finds **cost-optimal solution only when all actions have the same cost**\n",
       "- Always complete\n",
       "- Time complexity: $O(b^d)$, Space complexity: $O(b^d)$\n",
       "- Memory is bigger concern than time\n",
       "  - As a result, exponential search cannot solve larger uninformed search problems\n",
       "\n",
       "**Uniform-Cost Search / Dijkstra's**\n",
       "- Used when actions have varying costs\n",
       "- Expand based on distance from source (may need to relax distances)\n",
       "- Cost of optimal solution = $C^*$, $\\epsilon$ is lower bound on cost of action\n",
       "  - Time complexity: $O(b^{1 + \\lfloor C^* / \\epsilon \\rfloor })$, Space complexity: $O(b^{1 + \\lfloor C^* / \\epsilon \\rfloor})$\n",
       "- Complete, cost-optimal\n",
       "\n",
       "**Depth-First Search**\n",
       "- Expands deepest nodes first\n",
       "- Implemented as a tree search instead of a graph search\n",
       "  - Does not keep reached states\n",
       "- Not cost optimal (finds the first solution)\n",
       "- Finite spaces:\n",
       "  - Efficient and complete\n",
       "- Requires less memory than other traversals\n",
       "  - Small frontier, no reached table of states\n",
       "  - Time complexity: $O(b^m)$, Space complexity: $O(bm)$\n",
       "- **Backtracking search** variant\n",
       "  - Only 1 successor generated at each time\n",
       "  - Critical for large state environments\n",
       "\n",
       "**Depth-Limited Search**\n",
       "- Similar to DFS, but include upper limit of depth $l$\n",
       "- Time complexity: $O(b^l)$, Space complexity: $O(bl)$\n",
       "- Can choose good $l$ if we know some info (ie. diameter) of the problem\n",
       "\n",
       "**Iterative-Deepening Search**\n",
       "- Similar to depth-limited search, but tries all values for $l$ from 0 upwards\n",
       "  - Terminates either when solution is found or failure value\n",
       "  - Time complexity: $O(b^d)$ when exists solution, $O(b^m)$ when no solution\n",
       "  - Space complexity: $O(bd)$ when exists solution, $O(bm)$ when no solution\n",
       "- Does not matter that nodes at top of repeated since it is much smaller compared to nodes at bottom\n",
       "- Overall, **preferred uninformed search strategy** when state space is large and depth is not known\n",
       "\n",
       "**Bidirectional Search**\n",
       "- Searches forward from start state and backwards from end state(s), terminating when the two meet\n",
       "- Keep track of two frontiers and two reached tables\n",
       "- Time complexity: $O(b^{d/2})$, Space complexity: $O(b^{d/2})$\n",
       "\n",
       "\n",
       "## Module 3 Lecture Notes\n",
       "\n",
       "**DFS vs BFS:**\n",
       "\n",
       "*Use DFS if:* space is restricted, there are many possible solutions amnd long paths are ended quickly\n",
       "\n",
       "*Use BFS if:* possible infinite paths, some solutions have short paths\n",
       "\n",
       "For **depth limited search**, if $l = d$, then optimal. However, if $l < d$, then incomplete. if $l > d$ not optimal\n",
       "\n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "* **Informed** - agent can estimate its distance from the goal\n",
       "* **Uninformed** - agent cannot estimate its distance from the goal\n",
       "* **Open-loop** - ignoring percepts while on the path to a solution (guaranteed to be correct and lead to goal)\n",
       "* **Closed-loop** - monitors perepts while following path to goal (nondeterministic or possibly incorrect sequence)\n",
       "* **State space** - set of locations of environment\n",
       "* **Initial state** - starting location\n",
       "* **Goal state(s)** - can be multiple\n",
       "* **Actions** - `Actions(s)` gives finite set of possible actions to be run in state `s`\n",
       "* **Transition model** - results of each possible action from `Actions(s)` (transition model)\n",
       "* **Action cost function** - cost of applying action `a`\n",
       "* **Optimal solution** - lowest path cost\n",
       "* **Model** - abstract mathematical description\n",
       "* **Abstraction** - removing explicit details from representation\n",
       "* **Standardized problem** - illustrate various problem-solving methods (benchmark for algo performance)\n",
       "* **Real-world problem** - concrete solutions that people use and is unique/individual\n",
       "* **Search algorithm** - problem as input, returns a solution or none if not possible\n",
       "* **Frontier** - set of next unexpanded nodes\n",
       "* **Best-first search** - greedily choose node $n$ with minimum value (calculated by evaluation function)\n",
       "* **Priority queue** - queue where nodes are ordered based on priority (i.e. min cost) - best-first search\n",
       "* **Fifo queue** - first-in-first-out, queue (BFS)\n",
       "* **Lifo queue** - last-in-first-out, stack (DFS)\n",
       "* **Graph search** - checks for redundant paths (stores reached states)\n",
       "* **Tree search** - does not check for redundant paths (save space by not storing reached states)\n",
       "* **Breadth-first search (bfs)** - expand nodes by successors in waves (queue based)\n",
       "* **Uniform-cost search** - (dijkstra) least cost nodes from sourc e are expanded\n",
       "* **Depth-first search (dfs)** - expand deepest nodes first in a tree search (stack based)\n",
       "* **Depth-limited search** - DFS with maximum depth layer $l$\n",
       "* **Iterative-deepening search** - depth-limited search where all values for $l$ are tried\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module3_sections = [\n",
    "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
    "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
    "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
    "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
    "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
    "]\n",
    "\n",
    "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
    "display(Markdown(module3_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WHREsHSSyA-h"
   },
   "source": [
    "#Module 4 - Informed Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "tuFC8w7CyCns"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
    "chapter3_5 = \"\"\"\n",
    "**Greedy Best-First Search**\n",
    "- Best-first search with $f(n)=h(n)$\n",
    "- Greediness can lead to worse results than being careful (not always optimal)\n",
    "- Complete in finite spaces, but not in infinite ones\n",
    "- Time complexity: $O(V)$, Space complexity: $O(V)$\n",
    "- With a good heuristic: Time complexity: $O(bm)$, Space complexity: $O(bm)$\n",
    "\n",
    "**A* Search**\n",
    "- Best-first search with $f(n)=g(n)+h(n)$ where $g(n)$ is path cost from source to $n$ and $h(n)$ is estimated cost from $n$ to goal\n",
    "- Complete\n",
    "- Cost-optimal depends on the heuristic\n",
    "  - Good heuristic should be admissible\n",
    "- Every consistent heuristic is admissible so a consistent heuristic is cost-optimal.\n",
    "  - Vice versa is not true\n",
    "  - Consistent if $h(n) \\leq c(n,a,n')+h(n')$ for all nodes $n$ adn successors $n'$ of $n$ by action $a$\n",
    "- An inadmissible heuristic may not be cost-optimal.\n",
    "- $g$ costs are monotonic since action costs are always positive, causing path cost always increases as you go along the path\n",
    "- If $C^*$ is the cost of the optimal solution path, then:\n",
    "  - Expands all nodes that can be visited from the source on the path where each node in the path has $f(n)<C^*$ (surely expanded nodes)\n",
    "  - Might expand some nodes on goal contour where $f(n)=C^*$ before selecting goal node\n",
    "  - Expands no nodes with $f(n)>C^*$\n",
    "- Optimally efficient\n",
    "- A* prunes search tree nodes that are not necessary for finding optimal solution\n",
    "- However, number of nodes expanded can potentially be exponential in solution\n",
    "\n",
    "- Inadmissible heuristics risk missing optimal solutions, but can reduce number of nodes expanded\n",
    "- Weighted A* search = $f(n) = g(n) + W * h(n)$\n",
    "\n",
    "**Methods of saving space for A\\***\n",
    "- Only store node in one of either frontier or reached states\n",
    "- Remove nodes from reached set when no longer needed\n",
    "- MA* (memory-bounded A*), SMA* (simplified MA*)\n",
    "\n",
    "**Beam search**\n",
    "- Limits size of frontier\n",
    "- Keeps only $k$ nodes in frontier\n",
    "- Incomplete & suboptimal, but if a good $k$ is choen, makes good use of memory and speed\n",
    "\n",
    "**Iterative-deepening A* search (IDA*)**\n",
    "- A* without keeping visited set, but possibly visit states multiple times\n",
    "- Cutoff is $f(n)$ --> each iteration, cutoff is smallest $f(n)$ that exceeded the cutoff on prior iteration\n",
    "\n",
    "**Recursive best-first search (RBFS)**\n",
    "- best-first search using only linear space\n",
    "- If node surpasses `f_limit`, recursion unwinds and replaces with backed-up value (best $f(n)$ among children)\n",
    "- Suffers from excessive node regeneration\n",
    "- RBFS is optimal if $h(n)$ is admissible\n",
    "- Space is linear $O(d)$ in terms of depth of deepest optimal solution\n",
    "\n",
    "**Bidirectional heuristic search**\n",
    "- No guarantee of optimal cost or optimally efficient (even with admissible $h(n)$)\n",
    "\"\"\"\n",
    "chapter3_6 = \"\"\"\n",
    "**Quality of Heuristic**\n",
    "- Effective branching factor $b^*$\n",
    "  - $N+1=1+b^*+(b^*)^2+...+(b^*)^d$\n",
    "  - Attempt to minimize $b^*$ as much as possible, value close to 1\n",
    "- Effective depth\n",
    "  - Reduce by constant $k_h$ compared to true depth\n",
    "- Domination\n",
    "  - If $h_2(n) \\geq h_1(n)$, then $h_2$ dominates $h_1$\n",
    "    - Implies that $h_2$ will never expand more nodes than $h_1$\n",
    "    - Generally better to use an $h(n)$ function with higher values\n",
    "\n",
    "- Any optimal solution in the original problem is also a solution in the relaxed problem\n",
    "  - However, relaxed problem may have more optimal solutions\n",
    "  - Cost of an optimal solution to relaxed is an admissible heuristic for the original\n",
    "\n",
    "- Landmark points - help to check since most paths will go through landmark\n",
    "  - Works well because lots of traffic goes through landmarks\n",
    "\n",
    "- Overall, can generate good heuristics by relaxing, storinig precomputed costs of subproblems, defining landmarks, or learning from experience\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module4_lecture_notes = \"\"\"\n",
    "**A* Search**\n",
    "- Prune out paths that are already known to be expensive\n",
    "\n",
    "**Dominance: metric on better heuristics**\n",
    "- If $h_2(n) \\geq h_1(n)$ for all $n$, then $h_2$ dominates $h_1$\n",
    "  - Implies that $h_2$ is optimistic, but more accurate than $h_1$ and so $h_2$ is better for search\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module4_definitions = {\n",
    "\"informed search\" : \"uses hints about the environment to solve problem more efficiently than uninformed search\",\n",
    "\"heuristic function\" : \"estimated cost of the path from current state to goal state\",\n",
    "\"greedy best-first search\" : \"best-first search with $f(n) = h(n)$\",\n",
    "\"a* search\" : \"best-first search with $f(n)=g(n)+h(n)$\",\n",
    "\"admissibility\" : \"$0 \\leq h(n) \\leq h^*(n)$ where $h^*(n)=$true cost; never overestimates cost to reach the terminating state (optimistic)\",\n",
    "\"consistency\" : \"$h(n) \\leq c(n,a,n') + h(n')$ for each $n$ and successor $n'$ for action $a$\",\n",
    "\"surely expanded nodes\" : \"nodes that can be visited from the start on the path where each node has $f(n)<C^*$\",\n",
    "\"satisficing\" : \"suboptimal solution that is 'good enough'\",\n",
    "\"inadmissible heuristic\" : \"overestimates cost to reah goal\",\n",
    "\"bounded suboptimal search\" : \"finds solution within constant $W$ of optimal cost (use weighted A*)\",\n",
    "\"bounded cost search\" : \"finds solution where cost is less than constant $C$\",\n",
    "\"unbounded cost search\" : \"finds solution of any cost as long as its found quickly\",\n",
    "\"speedy search\" : \"greedy best-first variant where h(n) = estimated actions to goal (fast but high cost)\",\n",
    "\"beam search\" : \"search algo that only keeps $k$ nodes in frontier\",\n",
    "\"iterative-deepening A* search\" : \"A* without keeping visited set, but possibly visit states multiple times\",\n",
    "\"recursive best-first search\" : \"best-first search using only linear space\",\n",
    "\"weighted A* search\" : \"A* expanding fewer nodes, but sacrificing optimality\",\n",
    "\"manhattan distance\" : \"sum of horizontal and vertical distances\",\n",
    "\"effective branching factor ($b^*$)\" : \"number of nodes expanded for given node $n$\",\n",
    "\"relaxed problem\" : \"a problem with fewer restrictions\",\n",
    "\"pattern database\" : \"mapping from subproblem to solution cost\",\n",
    "\"differential heuristic\" : \"heuristic that is both efficient and admissible with subtraction\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "d702b2dc-6510-4860-ba8d-7dfd92c7be91"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       "\n",
       "**Greedy Best-First Search**\n",
       "- Best-first search with $f(n)=h(n)$\n",
       "- Greediness can lead to worse results than being careful (not always optimal)\n",
       "- Complete in finite spaces, but not in infinite ones\n",
       "- Time complexity: $O(V)$, Space complexity: $O(V)$\n",
       "- With a good heuristic: Time complexity: $O(bm)$, Space complexity: $O(bm)$\n",
       "\n",
       "**A* Search**\n",
       "- Best-first search with $f(n)=g(n)+h(n)$ where $g(n)$ is path cost from source to $n$ and $h(n)$ is estimated cost from $n$ to goal\n",
       "- Complete\n",
       "- Cost-optimal depends on the heuristic\n",
       "  - Good heuristic should be admissible\n",
       "- Every consistent heuristic is admissible so a consistent heuristic is cost-optimal.\n",
       "  - Vice versa is not true\n",
       "  - Consistent if $h(n) \\leq c(n,a,n')+h(n')$ for all nodes $n$ adn successors $n'$ of $n$ by action $a$\n",
       "- An inadmissible heuristic may not be cost-optimal.\n",
       "- $g$ costs are monotonic since action costs are always positive, causing path cost always increases as you go along the path\n",
       "- If $C^*$ is the cost of the optimal solution path, then:\n",
       "  - Expands all nodes that can be visited from the source on the path where each node in the path has $f(n)<C^*$ (surely expanded nodes)\n",
       "  - Might expand some nodes on goal contour where $f(n)=C^*$ before selecting goal node\n",
       "  - Expands no nodes with $f(n)>C^*$\n",
       "- Optimally efficient\n",
       "- A* prunes search tree nodes that are not necessary for finding optimal solution\n",
       "- However, number of nodes expanded can potentially be exponential in solution\n",
       "\n",
       "- Inadmissible heuristics risk missing optimal solutions, but can reduce number of nodes expanded\n",
       "- Weighted A* search = $f(n) = g(n) + W * h(n)$\n",
       "\n",
       "**Methods of saving space for A\\***\n",
       "- Only store node in one of either frontier or reached states\n",
       "- Remove nodes from reached set when no longer needed\n",
       "- MA* (memory-bounded A*), SMA* (simplified MA*)\n",
       "\n",
       "**Beam search**\n",
       "- Limits size of frontier\n",
       "- Keeps only $k$ nodes in frontier\n",
       "- Incomplete & suboptimal, but if a good $k$ is choen, makes good use of memory and speed\n",
       "\n",
       "**Iterative-deepening A* search (IDA*)**\n",
       "- A* without keeping visited set, but possibly visit states multiple times\n",
       "- Cutoff is $f(n)$ --> each iteration, cutoff is smallest $f(n)$ that exceeded the cutoff on prior iteration\n",
       "\n",
       "**Recursive best-first search (RBFS)**\n",
       "- best-first search using only linear space\n",
       "- If node surpasses `f_limit`, recursion unwinds and replaces with backed-up value (best $f(n)$ among children)\n",
       "- Suffers from excessive node regeneration\n",
       "- RBFS is optimal if $h(n)$ is admissible\n",
       "- Space is linear $O(d)$ in terms of depth of deepest optimal solution\n",
       "\n",
       "**Bidirectional heuristic search**\n",
       "- No guarantee of optimal cost or optimally efficient (even with admissible $h(n)$)\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       "\n",
       "**Quality of Heuristic**\n",
       "- Effective branching factor $b^*$\n",
       "  - $N+1=1+b^*+(b^*)^2+...+(b^*)^d$\n",
       "  - Attempt to minimize $b^*$ as much as possible, value close to 1\n",
       "- Effective depth\n",
       "  - Reduce by constant $k_h$ compared to true depth\n",
       "- Domination\n",
       "  - If $h_2(n) \\geq h_1(n)$, then $h_2$ dominates $h_1$\n",
       "    - Implies that $h_2$ will never expand more nodes than $h_1$\n",
       "    - Generally better to use an $h(n)$ function with higher values\n",
       "\n",
       "- Any optimal solution in the original problem is also a solution in the relaxed problem\n",
       "  - However, relaxed problem may have more optimal solutions\n",
       "  - Cost of an optimal solution to relaxed is an admissible heuristic for the original\n",
       "\n",
       "- Landmark points - help to check since most paths will go through landmark\n",
       "  - Works well because lots of traffic goes through landmarks\n",
       "\n",
       "- Overall, can generate good heuristics by relaxing, storinig precomputed costs of subproblems, defining landmarks, or learning from experience\n",
       "\n",
       "\n",
       "## Module 4 Lecture Notes\n",
       "\n",
       "**A* Search**\n",
       "- Prune out paths that are already known to be expensive\n",
       "\n",
       "**Dominance: metric on better heuristics**\n",
       "- If $h_2(n) \\geq h_1(n)$ for all $n$, then $h_2$ dominates $h_1$\n",
       "  - Implies that $h_2$ is optimistic, but more accurate than $h_1$ and so $h_2$ is better for search\n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Informed search** - uses hints about the environment to solve problem more efficiently than uninformed search\n",
       "* **Heuristic function** - estimated cost of the path from current state to goal state\n",
       "* **Greedy best-first search** - best-first search with $f(n) = h(n)$\n",
       "* **A* search** - best-first search with $f(n)=g(n)+h(n)$\n",
       "* **Admissibility** - $0 \\leq h(n) \\leq h^*(n)$ where $h^*(n)=$true cost; never overestimates cost to reach the terminating state (optimistic)\n",
       "* **Consistency** - $h(n) \\leq c(n,a,n') + h(n')$ for each $n$ and successor $n'$ for action $a$\n",
       "* **Surely expanded nodes** - nodes that can be visited from the start on the path where each node has $f(n)<C^*$\n",
       "* **Satisficing** - suboptimal solution that is 'good enough'\n",
       "* **Inadmissible heuristic** - overestimates cost to reah goal\n",
       "* **Bounded suboptimal search** - finds solution within constant $W$ of optimal cost (use weighted A*)\n",
       "* **Bounded cost search** - finds solution where cost is less than constant $C$\n",
       "* **Unbounded cost search** - finds solution of any cost as long as its found quickly\n",
       "* **Speedy search** - greedy best-first variant where h(n) = estimated actions to goal (fast but high cost)\n",
       "* **Beam search** - search algo that only keeps $k$ nodes in frontier\n",
       "* **Iterative-deepening a* search** - A* without keeping visited set, but possibly visit states multiple times\n",
       "* **Recursive best-first search** - best-first search using only linear space\n",
       "* **Weighted a* search** - A* expanding fewer nodes, but sacrificing optimality\n",
       "* **Manhattan distance** - sum of horizontal and vertical distances\n",
       "* **Effective branching factor ($b^*$)** - number of nodes expanded for given node $n$\n",
       "* **Relaxed problem** - a problem with fewer restrictions\n",
       "* **Pattern database** - mapping from subproblem to solution cost\n",
       "* **Differential heuristic** - heuristic that is both efficient and admissible with subtraction\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module4_sections = [\n",
    "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
    "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
    "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
    "]\n",
    "\n",
    "module4_markdown = format_module(4, \"Informed Search\", \n",
    "                         module4_sections, \n",
    "                         module4_definitions)\n",
    "display(Markdown(module4_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F3FPMzG9yUls"
   },
   "source": [
    "#Module 5 - Adversarial Search and Games"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
    "chapter5_1 = \"\"\"\n",
    "- Treat multiagent environments as an economy, a part of the environments\n",
    "\"\"\"\n",
    "chapter5_2 = \"\"\"\n",
    "**Minimax Algorithm**\n",
    "- MAX chooses to maximize minimax value, MIN chooses to minimize minimax value\n",
    "- Minimax value is the minimum possible utility in any iteration of the game\n",
    "  - If opponent plays suboptimally, can increase utility, but may not necessarily play minimax optimal move\n",
    "- DFS exploration (Time: $O(b^m)$, Space: $O(bm)$)\n",
    "- Exponential means it's impractical for larger games\n",
    "- Alliances/betrayals may form and make concrete what would've happened in minimax games\n",
    "\n",
    "**Alpha-Beta Pruning**\n",
    "- $\\\\alpha$ = value of the best (heighest) utility we have so far on any point along the path for MAX\n",
    "  - at least\n",
    "- $\\\\beta$ = value of the best (lowest) utility found so far on any point along the path for MIN\n",
    "  - at most\n",
    "- Prunes as soon as the value of the current node is known to be worse (less) \n",
    "than the current $\\\\alpha$ or (greater than) $\\\\beta$ for MAX or MIN, respectively\n",
    "- Order of visiting nodes affects alpha-beta pruning effectiveness\n",
    "- Perfectly, alpha-beta pruning only needs to visit $O(b^{m/2})$ nodes since effective branching factor is $\\sqrt{b}$\n",
    "- Trying moves that worked well in the past can help (iterative deepening)\n",
    "- Repeated states can come up due to **transpositions** (solution: transposition table)\n",
    "\"\"\"\n",
    "chapter5_3 = \"\"\"\n",
    "- Cutoff test\n",
    "\n",
    "**Evaluation Functions**\n",
    "- Good eval functions\n",
    "  - Computation should not take too long\n",
    "  - Strongly correlated with real chances of winning\n",
    "- Most eval functions compute distinct numbers for each feature and combine them for a total value\n",
    "  - Ie. *material value* for chess\n",
    "- Eval function should only be evaluated on **quiescent** (no pending moves) positions\n",
    "\n",
    "- **Horizon effect** is difficult to eliminate\n",
    "  - **Singular extensions** --> moves that are more optimal than other moves, but would normally be cut off\n",
    "    - Effective since number of singular extensions is usually low\n",
    "\n",
    "- Forward pruning - eliminating moves that look bad\n",
    "- Many complex games use table lookup instead of search for the beginning and ends of the game (when there are popular options)\n",
    "  - i.e. chess (pawn to e4)\n",
    "\"\"\"\n",
    "chapter5_5 = \"\"\"\n",
    "**Stochastic Games**\n",
    "- Maximize expected value of positions (average of all possible outcomes of chance nodes)\n",
    "- **Expectiminimax value** - minimax value with expectation involved\n",
    "  - Time: $O(b^mn^m)$ where $n=$ number of distinct rolls\n",
    "  - Difficult to predict since possibilities are multiplied tremendously\n",
    "\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
    "chapter16_1 = \"\"\"\n",
    "Decision theory = choosing actions based on their immediate outcomes (captured by utility function)\n",
    "Maximum expected utility (MEU) - rational agent should choose action to maximize expected util\n",
    "  - formalizes the notion of \"doing the right thing\", but does not operationalize it\n",
    "\"\"\"\n",
    "chapter16_2 = \"\"\"\n",
    "Preference relation constraints:\n",
    "1. Orderability - must be able to sort preferences/order lotteries\n",
    "2. Transitivity - prefer A to B, prefer B to C, then must prefer A to C\n",
    "3. Continuity - if preference is A-B-C, then at some point, agent is indifferent about definitely getting B versus yielding A with prob $p$ and C with $1-p$\n",
    "4. Substitutability - A and B are indifferent and can be substituted without changing outcome\n",
    "5. Monotonicity - if A and B have same outcome, then agent should prefer the one with the higher probability of occurring\n",
    "6. Decomposability - compound lotteries can be decomposed into smaller ones using probability\n",
    "\n",
    "Effect on utility:\n",
    "1. Existence of utility function - exists a function $U$ such that $U(A) > U(B)$ iff $A$ preferred over $B$ (same for indifference)\n",
    "2. Expected utility of a lottery - sum of probability of each outcomes multiplied by actual utility of outcome\n",
    "\n",
    "Decisions depend only on preferences (numbers don't matter)\n",
    "\"\"\"\n",
    "chapter16_3 = \"\"\"\n",
    "Certainty Effect\n",
    "- Reduce computational burden\n",
    "- Distrust legitimacy of the stated probabilities\n",
    "- Accounting for emotional state\n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module5_lecture_notes = \"\"\"\n",
    "Evaluation function - based on static features of the board alone\n",
    "\n",
    "**Alpha-Beta Pruning**\n",
    "- MAX will never allow move where $v \\leq \\\\alpha$\n",
    "- MIN will never allow move where $v \\geq \\\\beta$\n",
    "- Stop evaluating branch when:\n",
    "  - For MAX, stop when value $v \\geq \\\\beta$\n",
    "  - For MIN, stop when value $v \\leq \\\\alpha$\n",
    "\n",
    "**Expectimax Search**\n",
    "- Compute the average score under optimal play\n",
    "  - Calculate expected utilities\n",
    "- Pruning is more difficult with chance\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module5_definitions = {\n",
    "\"imperfect information\" : \"not all information is visible\",\n",
    "\"perfect information\" : \"fully observable\",\n",
    "\"zero-sum games\" : \"good for one is bad for the other\",\n",
    "\"minimax search\" : \"maximize minimum game where game has multiple outcome scores\",    \n",
    "\"minimax value\" : \"utility at the current state assuming both players have acted rationally\",\n",
    "\"pruning\" : \"computing minimax decision without examining all states\",\n",
    "\"alpha-beta pruning\" : \"$\\\\alpha=$ at least, $\\\\beta=$ at most\",\n",
    "\"transpositions\" : \"different permutations of the sequence that end in same position\",\n",
    "\"transposition table\" : \"cache for mapping position to heuristic value\",\n",
    "\"Type A strategy\" : \"considers *wide but shallow* portion of search tree (all moves to depth $d$, heuristically eval to get utility)\",\n",
    "\"Type B strategy\" : \"considers *deep but narrow* portion of search tree (ignores bad, follows promising)\",\n",
    "\"quiescent\" : \"positions that have no pending moves\",\n",
    "\"horizon effect\" : \"when the delaying moves unnecessarily weaken the position or give up additional material to postpone the eventual loss\",\n",
    "\"forward pruning\" : \"pruning moves that look like bad moves (risky - could be good)\",\n",
    "\"late move reduction\" : \"assumption that moves done later are less likely to be good moves\",\n",
    "\"policy\" : \"mapping from states to best move\",\n",
    "\"stochastic games\" : \"games with unpredictability (not deterministic)\",\n",
    "\"chance nodes\" : \"nodes indicating possible outcomes that are not under user's control\",\n",
    "\"value function\" : \"decision depends only on preferences (not numbers)\",\n",
    "\"ordinal utility function\" : \"decision depends only on preferences (not numbers)\",\n",
    "\"preference elicitation\" : \"observe preferences and compute utility function by presenting choices\",\n",
    "\"normalized utilities\" : \"normalized scale for presenting utility\",\n",
    "\"risk averse\" : \"prefer outcomes with low uncertainty, even if average outcome of higher risk is higher\",\n",
    "\"risk seeking\" : \"prefer outcomes with high uncertainty\",\n",
    "\"certainty effect\" : \"people are strongly attracted to certainty\",\n",
    "\"ambiguity aversion\" : \"people choose known probabilty over unknowns\",\n",
    "\"framing effect\" : \"wordings can influence decisions\",\n",
    "\"anchoring effect\" : \"judging based on some fixed anchor point\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "ebc41c75-0f09-4c3f-e177-806d7937b233"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       "\n",
       "- Treat multiagent environments as an economy, a part of the environments\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       "\n",
       "**Minimax Algorithm**\n",
       "- MAX chooses to maximize minimax value, MIN chooses to minimize minimax value\n",
       "- Minimax value is the minimum possible utility in any iteration of the game\n",
       "  - If opponent plays suboptimally, can increase utility, but may not necessarily play minimax optimal move\n",
       "- DFS exploration (Time: $O(b^m)$, Space: $O(bm)$)\n",
       "- Exponential means it's impractical for larger games\n",
       "- Alliances/betrayals may form and make concrete what would've happened in minimax games\n",
       "\n",
       "**Alpha-Beta Pruning**\n",
       "- $\\alpha$ = value of the best (heighest) utility we have so far on any point along the path for MAX\n",
       "  - at least\n",
       "- $\\beta$ = value of the best (lowest) utility found so far on any point along the path for MIN\n",
       "  - at most\n",
       "- Prunes as soon as the value of the current node is known to be worse (less) \n",
       "than the current $\\alpha$ or (greater than) $\\beta$ for MAX or MIN, respectively\n",
       "- Order of visiting nodes affects alpha-beta pruning effectiveness\n",
       "- Perfectly, alpha-beta pruning only needs to visit $O(b^{m/2})$ nodes since effective branching factor is $\\sqrt{b}$\n",
       "- Trying moves that worked well in the past can help (iterative deepening)\n",
       "- Repeated states can come up due to **transpositions** (solution: transposition table)\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       "\n",
       "- Cutoff test\n",
       "\n",
       "**Evaluation Functions**\n",
       "- Good eval functions\n",
       "  - Computation should not take too long\n",
       "  - Strongly correlated with real chances of winning\n",
       "- Most eval functions compute distinct numbers for each feature and combine them for a total value\n",
       "  - Ie. *material value* for chess\n",
       "- Eval function should only be evaluated on **quiescent** (no pending moves) positions\n",
       "\n",
       "- **Horizon effect** is difficult to eliminate\n",
       "  - **Singular extensions** --> moves that are more optimal than other moves, but would normally be cut off\n",
       "    - Effective since number of singular extensions is usually low\n",
       "\n",
       "- Forward pruning - eliminating moves that look bad\n",
       "- Many complex games use table lookup instead of search for the beginning and ends of the game (when there are popular options)\n",
       "  - i.e. chess (pawn to e4)\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       "\n",
       "**Stochastic Games**\n",
       "- Maximize expected value of positions (average of all possible outcomes of chance nodes)\n",
       "- **Expectiminimax value** - minimax value with expectation involved\n",
       "  - Time: $O(b^mn^m)$ where $n=$ number of distinct rolls\n",
       "  - Difficult to predict since possibilities are multiplied tremendously\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       "\n",
       "Decision theory = choosing actions based on their immediate outcomes (captured by utility function)\n",
       "Maximum expected utility (MEU) - rational agent should choose action to maximize expected util\n",
       "  - formalizes the notion of \"doing the right thing\", but does not operationalize it\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       "\n",
       "Preference relation constraints:\n",
       "1. Orderability - must be able to sort preferences/order lotteries\n",
       "2. Transitivity - prefer A to B, prefer B to C, then must prefer A to C\n",
       "3. Continuity - if preference is A-B-C, then at some point, agent is indifferent about definitely getting B versus yielding A with prob $p$ and C with $1-p$\n",
       "4. Substitutability - A and B are indifferent and can be substituted without changing outcome\n",
       "5. Monotonicity - if A and B have same outcome, then agent should prefer the one with the higher probability of occurring\n",
       "6. Decomposability - compound lotteries can be decomposed into smaller ones using probability\n",
       "\n",
       "Effect on utility:\n",
       "1. Existence of utility function - exists a function $U$ such that $U(A) > U(B)$ iff $A$ preferred over $B$ (same for indifference)\n",
       "2. Expected utility of a lottery - sum of probability of each outcomes multiplied by actual utility of outcome\n",
       "\n",
       "Decisions depend only on preferences (numbers don't matter)\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       "\n",
       "Certainty Effect\n",
       "- Reduce computational burden\n",
       "- Distrust legitimacy of the stated probabilities\n",
       "- Accounting for emotional state\n",
       "\n",
       "\n",
       "## Module 5 Lecture Notes\n",
       "\n",
       "Evaluation function - based on static features of the board alone\n",
       "\n",
       "**Alpha-Beta Pruning**\n",
       "- MAX will never allow move where $v \\leq \\alpha$\n",
       "- MIN will never allow move where $v \\geq \\beta$\n",
       "- Stop evaluating branch when:\n",
       "  - For MAX, stop when value $v \\geq \\beta$\n",
       "  - For MIN, stop when value $v \\leq \\alpha$\n",
       "\n",
       "**Expectimax Search**\n",
       "- Compute the average score under optimal play\n",
       "  - Calculate expected utilities\n",
       "- Pruning is more difficult with chance\n",
       "\n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Imperfect information** - not all information is visible\n",
       "* **Perfect information** - fully observable\n",
       "* **Zero-sum games** - good for one is bad for the other\n",
       "* **Minimax search** - maximize minimum game where game has multiple outcome scores\n",
       "* **Minimax value** - utility at the current state assuming both players have acted rationally\n",
       "* **Pruning** - computing minimax decision without examining all states\n",
       "* **Alpha-beta pruning** - $\\alpha=$ at least, $\\beta=$ at most\n",
       "* **Transpositions** - different permutations of the sequence that end in same position\n",
       "* **Transposition table** - cache for mapping position to heuristic value\n",
       "* **Type a strategy** - considers *wide but shallow* portion of search tree (all moves to depth $d$, heuristically eval to get utility)\n",
       "* **Type b strategy** - considers *deep but narrow* portion of search tree (ignores bad, follows promising)\n",
       "* **Quiescent** - positions that have no pending moves\n",
       "* **Horizon effect** - when the delaying moves unnecessarily weaken the position or give up additional material to postpone the eventual loss\n",
       "* **Forward pruning** - pruning moves that look like bad moves (risky - could be good)\n",
       "* **Late move reduction** - assumption that moves done later are less likely to be good moves\n",
       "* **Policy** - mapping from states to best move\n",
       "* **Stochastic games** - games with unpredictability (not deterministic)\n",
       "* **Chance nodes** - nodes indicating possible outcomes that are not under user's control\n",
       "* **Value function** - decision depends only on preferences (not numbers)\n",
       "* **Ordinal utility function** - decision depends only on preferences (not numbers)\n",
       "* **Preference elicitation** - observe preferences and compute utility function by presenting choices\n",
       "* **Normalized utilities** - normalized scale for presenting utility\n",
       "* **Risk averse** - prefer outcomes with low uncertainty, even if average outcome of higher risk is higher\n",
       "* **Risk seeking** - prefer outcomes with high uncertainty\n",
       "* **Certainty effect** - people are strongly attracted to certainty\n",
       "* **Ambiguity aversion** - people choose known probabilty over unknowns\n",
       "* **Framing effect** - wordings can influence decisions\n",
       "* **Anchoring effect** - judging based on some fixed anchor point\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module5_sections = [\n",
    "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
    "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
    "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
    "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
    "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
    "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
    "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
    "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
    "]\n",
    "\n",
    "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
    "                         module5_sections, \n",
    "                         module5_definitions)\n",
    "display(Markdown(module5_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "qVSQhTVSyYYO"
   },
   "source": [
    "#Module 6 - \"Constraint Satisfaction Problems\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "Wm4mfW82yaRH"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
    "chapter6_1 = \"\"\"\n",
    "**CSP Definition**\n",
    "- 3 components:\n",
    "  - $X=\\{X_1, X_2, ..., X_n\\}$ where $X$ is a variable\n",
    "  - $D=\\{D_1, D_2, ..., D_n\\}$ where $D$ is a domain\n",
    "  - $C$ is a set of constraints that specify allowable combinations of values\n",
    "- Solving CSP is NP-complete\n",
    "\n",
    "- CSPs are an easy, natural representation for problems\n",
    "- Lots of development work in history\n",
    "- Prune lots of search space at a time\n",
    "\n",
    "- Simplest CSP is discrete, finite domains\n",
    "  - Coloring problem, scheduling, 8 queens problem\n",
    "\"\"\"\n",
    "chapter6_2 = \"\"\"\n",
    "Local consistency - enforcing local consistency in all parts of a graph leads inconsistent values to be eliminated\n",
    "\n",
    "**AC-3** = popular arc consistency algorithm\n",
    "- queue of arcs (initialized to all arcs)\n",
    "- pop off arbitrary arc ($X_i$, $X_j$) -> make $X_i$ arc consistent with $X_j$\n",
    "  - If domain doesn't change, then continue\n",
    "  - If domain changes, then add all arcs ($X_k$, $X_i$) where $X_k$ is a neighbor of $X_i$\n",
    "    - Changing $i$'s domain might change $k$\n",
    "  - If $i$'s new domain is empty, then report failure\n",
    "- Time: $O(cd^3)$ where $d$ is max domain size, $c$ is number of arcs\n",
    "\n",
    "**Path consistency** - Tighter set of binary constraints\n",
    "\n",
    "**K-consistency** - a consistent value can always be assigned to a $k$th variable for any set of $k-1$ variables\n",
    "\n",
    "Example of CSP - Sudoku\n",
    "\"\"\"\n",
    "chapter6_3 = \"\"\"\n",
    "- CSPs are **commutative**\n",
    "- Backtracking search can be improved using *domain-independent* heuristics to take advantage of CSPs\n",
    "\n",
    "**Strategies for assigning variable values**\n",
    "- Simplest is to go in order $\\{X_1,X_2,...\\}$. Next is to choose randomly. Neither is optimal\n",
    "- **Minimum-Remaining-Values** heuristic\n",
    "  - Chooses variable that is most constrained, pruning subtree\n",
    "  - If no legal moves remain, return FAILURE\n",
    "- **Degree heuristic**\n",
    "  - Tries to reduce the branching factor on future choices\n",
    "- Once a variable has been selected, use **least-constraining-value**\n",
    "  - Wants to leave maximum flexibility for subsequent variables\n",
    "\n",
    "**Search and inference**\n",
    "- **Forward checking** --> delete from $Y$'s domain all inconsistent values chosen for $X$\n",
    "- **Maintaining Arc Consistency**\n",
    "  - More powerful than forward checking\n",
    "  - Forward checking does not recursively propagate constraints when changes are made to domains, whereas MAC does\n",
    "\n",
    "**Backtracking**\n",
    "- Chronological backtracking is suboptimal/can be improved\n",
    "- Backjumping is an improvement\n",
    "  - Ie. conflict-directed backjumping\n",
    "\n",
    "**Constraint learning**\n",
    "- Minimum set of variables from conflict set is **no-good**\n",
    "  - Record no-good either by adding new constraint or keeping in cache\n",
    "\"\"\"\n",
    "chapter6_4 = \"\"\"\n",
    "**Min-conflicts** - heuristic to choose value that results in minimum number of future conflicts\n",
    "- N-queens problem\n",
    "  - Runtime of min-conflicts is independent of problem size\n",
    "- **Tabu search** - small list of visited states and forbidding algorithm from returning to them\n",
    "- Local search can be used in online settings where problems change\n",
    "\"\"\"\n",
    "chapter6_5 = \"\"\"\n",
    "Independence - finding connected components and solving independent subproblems\n",
    "\n",
    "All tree-structured CSPs can be solved in linear time with respect to number of variables\n",
    "- Directional arc consistency\n",
    "- Can be solved through topological ordering\n",
    "\n",
    "**Cutset conditioning algorithm**\n",
    "1. Find and select subset $S$ of variables so that graph becomes a tree after removal ($S$ is a cycle cutset)\n",
    "2. For each assignment of variables in $S$ that satisfies constraints,\n",
    "  - Remove all inconsistent values with assignment for $S$ from domains of remaining variables\n",
    "  - Return CSP solution with $S$'s assignment\n",
    "\n",
    "**Tree decomposition**\n",
    "- 3 requirements\n",
    "  - Each variable in the original problem shows up in at least one tree node\n",
    "  - Two variables connected by constraint in original problem must appear together in at least one tree node\n",
    "  - If a variable is in two tree nodes, must appear in every node along the path to those nodes\n",
    "- Solve in $O(nd^2)$ time where $n$ is number of tree nodes and $d$ is size of the largest domain\n",
    "- Efficient if tree width is small\n",
    "\n",
    "**Value symmetry**\n",
    "- Assign values interchangeably\n",
    "- Resolved by introducing **symmetry-breaking constraint**\n",
    "  - Ie. imposing arbitrary ordering\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module6_lecture_notes = \"\"\"\n",
    "- Assumptions: single agent, deterministic, fully observed state, discrete state space\n",
    "- Planning: sequences of actions\n",
    "- Identification: assignments to variables\n",
    "\n",
    "- Formal declarative language to find solutions for *general purpose* problems\n",
    "\n",
    "**Varieties of CSPs**\n",
    "- Discrete variables\n",
    "  - finite domains\n",
    "    - $n$ variables, $d$ domain size --> $O(d^n)$ complete assignments\n",
    "  - infinite domains\n",
    "    - integers, strings, etc.\n",
    "- Continuous variables\n",
    "  - linear constraints solvable in polynomial time by linear programming\n",
    "\n",
    "**Improving backtracking**\n",
    "- Most constrained variable (MRV heuristic)\n",
    "  - \"fail as quickly as possible\"\n",
    "  - Most constraining variable (tiebreaker)\n",
    "    - Choose variable with most constraints on remaining variables\n",
    "    - Combination of the two heuristics lead to direct solution (no backtracking)\n",
    "- Least constraining value\n",
    "  - Given variable choose least constraining heurstic (fewest values remaining)\n",
    "- Forward checking\n",
    "  - Check remaining unassigned variable\n",
    "  - Terminate when any unassigned variable has no remaining legal values\n",
    "  - Use DS to keep track of remaining values for each variable\n",
    "  - Propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures\n",
    "\n",
    "**Interefence in CSP**\n",
    "- Local consistency (defined by two constraints)\n",
    "  - Node consistency: satisfies unary constraints\n",
    "  - Arc consistency: satisfies binary constraints\n",
    "    - arc (i,j) is consistent iff every value v on $X_i$ is consistent with some label on $Y_j$\n",
    "- **AC-3**\n",
    "  - Only need to examine those $X_i$ where at least one neighbor of $X_i$ has lost a value\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module6_definitions = {\n",
    "\"constraint satisfaction problem\" : \"problem with sets of variables and values\",    \n",
    "\"consistent assignment\" : \"assignment that does not break any of the contraints of a CSP\",\n",
    "\"complete assignment\" : \"every variable in a CSP is assigned a value\",\n",
    "\"solution\" : \"consistent, complete assignment for a CSP\",\n",
    "\"partial assignment\" : \"assignment that leaves some variables unassigned\",\n",
    "\"partial solution\" : \"consistent, partial assignment\",\n",
    "\"precedence constraint\" : \"constraint that $T_1$ must come before $T_2$\",\n",
    "\"disjunctive constraint\" : \"constraint that must not overlap\",\n",
    "\"unary constraint\" : \"a single variable's value is restricted ($SA \\neq green$)\",\n",
    "\"binary constraint\" : \"two variables values are restricted against each other ($SA \\neq NSW$)\",\n",
    "\"binary CSP\" : \"CSP with only binary and unary constraints\",\n",
    "\"global constraint\" : \"constraint with arbitrary number of variables\",\n",
    "\"preference constraints\" : \"CSP constraints where solutions are preferred over others\",\n",
    "\"constrained optimization problem\" : \"CSP with preferences are solved with optimizations (ie. linear programs)\",\n",
    "\"constraint propagation\" : \"reduce the number of legal values for variable based on constraints\",\n",
    "\"node-consistent\" : \"all values in the variable'd domain satisfy unary constraints\",\n",
    "\"arc-consistent\" : \"all values satisfy binary constraints\",\n",
    "\"strongly $k$-consistent\" : \"k-consistent, (k-1)-consistent, ..., down to 1-consistent\",\n",
    "\"resource constraint\" : \"constraint in dedication of resources\",\n",
    "\"bounds propagation\" : \"managing upper and lower bounds for domains and adjusting as necessary\",\n",
    "\"minimum-remaining-values (MRV)\" : \"heuristic that chooses the variable with the fewest legal moves\",\n",
    "\"least-constraining-value\" : \"prefers value that rules out the fewest choices for neighbors\",\n",
    "\"forward checking\" : \"establishes arc consistency for variable $X$ when assigned (delete any inconsistent value in $Y$ from $X$)\",\n",
    "\"chronological backtracking\" : \"if search fails, back up and try different value\",\n",
    "\"backjumping\" : \"backtrack to most recent assignment in the conflict set\",\n",
    "\"constraint learning\" : \"finding minimum set of variables from set that causes problem\",\n",
    "\"independent subproblems\" : \"solutions to subproblems that when combined, yield solution for entire problem\"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "dc4c6c22-6117-4b6c-a3ce-ceab9b046746"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       "\n",
       "**CSP Definition**\n",
       "- 3 components:\n",
       "  - $X=\\{X_1, X_2, ..., X_n\\}$ where $X$ is a variable\n",
       "  - $D=\\{D_1, D_2, ..., D_n\\}$ where $D$ is a domain\n",
       "  - $C$ is a set of constraints that specify allowable combinations of values\n",
       "- Solving CSP is NP-complete\n",
       "\n",
       "- CSPs are an easy, natural representation for problems\n",
       "- Lots of development work in history\n",
       "- Prune lots of search space at a time\n",
       "\n",
       "- Simplest CSP is discrete, finite domains\n",
       "  - Coloring problem, scheduling, 8 queens problem\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       "\n",
       "Local consistency - enforcing local consistency in all parts of a graph leads inconsistent values to be eliminated\n",
       "\n",
       "**AC-3** = popular arc consistency algorithm\n",
       "- queue of arcs (initialized to all arcs)\n",
       "- pop off arbitrary arc ($X_i$, $X_j$) -> make $X_i$ arc consistent with $X_j$\n",
       "  - If domain doesn't change, then continue\n",
       "  - If domain changes, then add all arcs ($X_k$, $X_i$) where $X_k$ is a neighbor of $X_i$\n",
       "    - Changing $i$'s domain might change $k$\n",
       "  - If $i$'s new domain is empty, then report failure\n",
       "- Time: $O(cd^3)$ where $d$ is max domain size, $c$ is number of arcs\n",
       "\n",
       "**Path consistency** - Tighter set of binary constraints\n",
       "\n",
       "**K-consistency** - a consistent value can always be assigned to a $k$th variable for any set of $k-1$ variables\n",
       "\n",
       "Example of CSP - Sudoku\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       "\n",
       "- CSPs are **commutative**\n",
       "- Backtracking search can be improved using *domain-independent* heuristics to take advantage of CSPs\n",
       "\n",
       "**Strategies for assigning variable values**\n",
       "- Simplest is to go in order $\\{X_1,X_2,...\\}$. Next is to choose randomly. Neither is optimal\n",
       "- **Minimum-Remaining-Values** heuristic\n",
       "  - Chooses variable that is most constrained, pruning subtree\n",
       "  - If no legal moves remain, return FAILURE\n",
       "- **Degree heuristic**\n",
       "  - Tries to reduce the branching factor on future choices\n",
       "- Once a variable has been selected, use **least-constraining-value**\n",
       "  - Wants to leave maximum flexibility for subsequent variables\n",
       "\n",
       "**Search and inference**\n",
       "- **Forward checking** --> delete from $Y$'s domain all inconsistent values chosen for $X$\n",
       "- **Maintaining Arc Consistency**\n",
       "  - More powerful than forward checking\n",
       "  - Forward checking does not recursively propagate constraints when changes are made to domains, whereas MAC does\n",
       "\n",
       "**Backtracking**\n",
       "- Chronological backtracking is suboptimal/can be improved\n",
       "- Backjumping is an improvement\n",
       "  - Ie. conflict-directed backjumping\n",
       "\n",
       "**Constraint learning**\n",
       "- Minimum set of variables from conflict set is **no-good**\n",
       "  - Record no-good either by adding new constraint or keeping in cache\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       "\n",
       "**Min-conflicts** - heuristic to choose value that results in minimum number of future conflicts\n",
       "- N-queens problem\n",
       "  - Runtime of min-conflicts is independent of problem size\n",
       "- **Tabu search** - small list of visited states and forbidding algorithm from returning to them\n",
       "- Local search can be used in online settings where problems change\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       "\n",
       "Independence - finding connected components and solving independent subproblems\n",
       "\n",
       "All tree-structured CSPs can be solved in linear time with respect to number of variables\n",
       "- Directional arc consistency\n",
       "- Can be solved through topological ordering\n",
       "\n",
       "**Cutset conditioning algorithm**\n",
       "1. Find and select subset $S$ of variables so that graph becomes a tree after removal ($S$ is a cycle cutset)\n",
       "2. For each assignment of variables in $S$ that satisfies constraints,\n",
       "  - Remove all inconsistent values with assignment for $S$ from domains of remaining variables\n",
       "  - Return CSP solution with $S$'s assignment\n",
       "\n",
       "**Tree decomposition**\n",
       "- 3 requirements\n",
       "  - Each variable in the original problem shows up in at least one tree node\n",
       "  - Two variables connected by constraint in original problem must appear together in at least one tree node\n",
       "  - If a variable is in two tree nodes, must appear in every node along the path to those nodes\n",
       "- Solve in $O(nd^2)$ time where $n$ is number of tree nodes and $d$ is size of the largest domain\n",
       "- Efficient if tree width is small\n",
       "\n",
       "**Value symmetry**\n",
       "- Assign values interchangeably\n",
       "- Resolved by introducing **symmetry-breaking constraint**\n",
       "  - Ie. imposing arbitrary ordering\n",
       "\n",
       "\n",
       "## Module 6 Lecture Notes\n",
       "\n",
       "- Assumptions: single agent, deterministic, fully observed state, discrete state space\n",
       "- Planning: sequences of actions\n",
       "- Identification: assignments to variables\n",
       "\n",
       "- Formal declarative language to find solutions for *general purpose* problems\n",
       "\n",
       "**Varieties of CSPs**\n",
       "- Discrete variables\n",
       "  - finite domains\n",
       "    - $n$ variables, $d$ domain size --> $O(d^n)$ complete assignments\n",
       "  - infinite domains\n",
       "    - integers, strings, etc.\n",
       "- Continuous variables\n",
       "  - linear constraints solvable in polynomial time by linear programming\n",
       "\n",
       "**Improving backtracking**\n",
       "- Most constrained variable (MRV heuristic)\n",
       "  - \"fail as quickly as possible\"\n",
       "  - Most constraining variable (tiebreaker)\n",
       "    - Choose variable with most constraints on remaining variables\n",
       "    - Combination of the two heuristics lead to direct solution (no backtracking)\n",
       "- Least constraining value\n",
       "  - Given variable choose least constraining heurstic (fewest values remaining)\n",
       "- Forward checking\n",
       "  - Check remaining unassigned variable\n",
       "  - Terminate when any unassigned variable has no remaining legal values\n",
       "  - Use DS to keep track of remaining values for each variable\n",
       "  - Propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures\n",
       "\n",
       "**Interefence in CSP**\n",
       "- Local consistency (defined by two constraints)\n",
       "  - Node consistency: satisfies unary constraints\n",
       "  - Arc consistency: satisfies binary constraints\n",
       "    - arc (i,j) is consistent iff every value v on $X_i$ is consistent with some label on $Y_j$\n",
       "- **AC-3**\n",
       "  - Only need to examine those $X_i$ where at least one neighbor of $X_i$ has lost a value\n",
       "\n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Constraint satisfaction problem** - problem with sets of variables and values\n",
       "* **Consistent assignment** - assignment that does not break any of the contraints of a CSP\n",
       "* **Complete assignment** - every variable in a CSP is assigned a value\n",
       "* **Solution** - consistent, complete assignment for a CSP\n",
       "* **Partial assignment** - assignment that leaves some variables unassigned\n",
       "* **Partial solution** - consistent, partial assignment\n",
       "* **Precedence constraint** - constraint that $T_1$ must come before $T_2$\n",
       "* **Disjunctive constraint** - constraint that must not overlap\n",
       "* **Unary constraint** - a single variable's value is restricted ($SA \n",
       "eq green$)\n",
       "* **Binary constraint** - two variables values are restricted against each other ($SA \n",
       "eq NSW$)\n",
       "* **Binary csp** - CSP with only binary and unary constraints\n",
       "* **Global constraint** - constraint with arbitrary number of variables\n",
       "* **Preference constraints** - CSP constraints where solutions are preferred over others\n",
       "* **Constrained optimization problem** - CSP with preferences are solved with optimizations (ie. linear programs)\n",
       "* **Constraint propagation** - reduce the number of legal values for variable based on constraints\n",
       "* **Node-consistent** - all values in the variable'd domain satisfy unary constraints\n",
       "* **Arc-consistent** - all values satisfy binary constraints\n",
       "* **Strongly $k$-consistent** - k-consistent, (k-1)-consistent, ..., down to 1-consistent\n",
       "* **Resource constraint** - constraint in dedication of resources\n",
       "* **Bounds propagation** - managing upper and lower bounds for domains and adjusting as necessary\n",
       "* **Minimum-remaining-values (mrv)** - heuristic that chooses the variable with the fewest legal moves\n",
       "* **Least-constraining-value** - prefers value that rules out the fewest choices for neighbors\n",
       "* **Forward checking** - establishes arc consistency for variable $X$ when assigned (delete any inconsistent value in $Y$ from $X$)\n",
       "* **Chronological backtracking** - if search fails, back up and try different value\n",
       "* **Backjumping** - backtrack to most recent assignment in the conflict set\n",
       "* **Constraint learning** - finding minimum set of variables from set that causes problem\n",
       "* **Independent subproblems** - solutions to subproblems that when combined, yield solution for entire problem\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module6_sections = [\n",
    "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
    "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
    "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
    "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
    "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
    "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
    "]\n",
    "\n",
    "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
    "                         module6_sections, \n",
    "                         module6_definitions)\n",
    "display(Markdown(module6_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RYESi2kMybL8"
   },
   "source": [
    "#Module 7 - Logical Agents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
    "\n",
    "chapter7_1 = \"\"\"\n",
    "- Knowledge-based agents don't care about implementation level\n",
    "  - Built by `TELL`ing what it needs to know\n",
    "  - From an empty knowledge base, repeatedly tell sentences until agent grows autonomous\n",
    "    - **Declarative** approach\n",
    "- Learning agent can be fully autonomous\n",
    "\"\"\"\n",
    "chapter7_2 = \"\"\"\n",
    "Wumpus World\n",
    "- **Performance Measure**: gold for leaving with gold, falling into pit or being eaten, actions taken, using arrow\n",
    "- **Environment**: 4x4 grid, walls surrounding, locations of gold and wumpus chosen randomly\n",
    "- **Actuators**: move, turn, grab gold, shoot, climb out of cave\n",
    "- **Sensors**: perceive Stench, perceive Breeze, perceive Glitter, perceive Bump, hear Scream\n",
    "- Must combine history of percepts to arrive at inferences\n",
    "- If conclusion is drawn from percepts, then guaranteed to be correct if percepts are correct\n",
    "\"\"\"\n",
    "chapter7_3 = \"\"\"\n",
    "- Standard logics: every sentence must be true or false (no in-between)\n",
    "- $M$ is a model of $\\\\alpha$ if $\\\\alpha$ is true for model $m$\n",
    "- $\\\\alpha \\\\models \\\\beta$ iff $M(\\\\alpha) \\subseteq M(\\\\beta)$\n",
    "- Meaning and truth of sentences/percepts comes from agent's sensors\n",
    "  - Used for general purpose learning (although fallible, provide some optimism)\n",
    "\"\"\"\n",
    "chapter7_4 = \"\"\"\n",
    "- Complex sentences are built by concatenating smaller sentences\n",
    "- Connected by logical connectives\n",
    "  - $\\\\neg$ (not) represents negation\n",
    "  - $\\\\land$ (and) represents conjuncction\n",
    "  - $\\\\lor$ (or) represents disjunction\n",
    "  - $\\\\implies$ (implies) represents implication (premise/antecedent $\\\\implies$ conclusion/consequent)\n",
    "  - $\\\\Leftrightarrow$ (if and only if) represents biconditional\n",
    "- Solving atomic sentences:\n",
    "  - $True$ is true in every model (same for $False$)\n",
    "  - Truth values must be specified directly\n",
    "- Solving complex sentences\n",
    "  - $\\\\neg P$ holds iff $P$ is false\n",
    "  - $P \\\\land Q$ holds iff both $P$ and $Q$ are true\n",
    "  - $P \\\\lor Q$ holds iff either $P$ or $Q$ are true\n",
    "  - $P \\\\implies Q$ holds unless $P$ is true and $Q$ is false\n",
    "  - $P \\\\Leftrightarrow Q$ holds iff $P$ and $Q$ are of the same parity\n",
    "\"\"\"\n",
    "chapter7_5 = \"\"\"\n",
    "- $(\\\\alpha \\\\land \\\\beta) \\\\equiv (\\\\beta \\\\land \\\\alpha)$ - commutativity of $\\\\land$\n",
    "- $(\\\\alpha \\\\lor \\\\beta) \\\\equiv (\\\\beta \\\\lor \\\\alpha)$ - commutativity of $\\\\lor$\n",
    "- $((\\\\alpha \\\\land \\\\beta) \\land \\\\gamma) \\\\equiv (\\\\alpha \\\\land (\\\\beta \\\\land \\\\gamma))$ - associativity of $\\\\land$\n",
    "- $((\\\\alpha \\\\lor \\\\beta) \\lor \\\\gamma) \\\\equiv (\\\\alpha \\\\lor (\\\\beta \\\\lor \\\\gamma))$ - associativity of $\\\\lor$\n",
    "- $\\\\neg (\\\\neg \\\\alpha) \\\\equiv \\\\alpha$ - double-negation elimination \n",
    "- $(\\\\alpha \\\\implies \\\\beta) \\\\equiv (\\\\neg \\\\beta \\\\implies \\\\neg \\\\alpha)$ - contraposition\n",
    "- $(\\\\alpha \\\\implies \\\\beta) \\\\equiv (\\\\neg \\\\alpha \\\\lor \\\\beta)$ - implication elimination\n",
    "- $(\\\\alpha \\\\Leftrightarrow \\\\beta) \\\\equiv ((\\\\alpha \\\\implies \\\\beta) \\\\land (\\\\beta \\\\implies \\\\alpha))$ - biconditional elimination\n",
    "- $\\\\neg (\\\\alpha \\\\land \\\\beta) \\\\equiv (\\\\neg \\\\alpha \\\\lor \\\\neg \\\\beta)$ - De Morgan\n",
    "- $\\\\neg (\\\\alpha \\\\lor \\\\beta) \\\\equiv (\\\\neg \\\\alpha \\\\land \\\\neg \\\\beta)$ - De Morgan\n",
    "- $(\\\\alpha \\\\land (\\\\beta \\lor \\\\gamma)) \\\\equiv ((\\\\alpha \\\\land \\\\beta) \\\\lor (\\\\alpha \\\\land \\\\gamma))$ - distributivity of $\\\\land$ over $\\\\lor$\n",
    "- $(\\\\alpha \\\\lor (\\\\beta \\land \\\\gamma)) \\\\equiv ((\\\\alpha \\\\lor \\\\beta) \\\\land (\\\\alpha \\\\lor \\\\gamma))$ - distributivity of $\\\\lor$ over $\\\\land$\n",
    "\n",
    "- Monotonicity - set of entailed sentences can only *increase* when information is added\n",
    "- Forward chaining is sound and complete\n",
    "- Logic can serve as a general class of representations\n",
    "  - Defines semantics of sentences\n",
    "- $\\\\alpha \\\\models \\\\beta$ iff $M(\\\\alpha) \\subseteq M(\\\\beta)$\n",
    "  - $\\\\alpha$ is more specific than $\\\\beta$\n",
    "  - $\\\\beta$ = \"agent is a robot\", $\\\\alpha$ = \"agent is an astromech\"\n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module7_lecture_notes = \"\"\"\n",
    "- Component of knowledge based agent is a knowledge base\n",
    "- Single inference rule **resolution** which yields complete inference algorithm\n",
    "- Can eliminate complementary literals due to **unit resolution** (only applies to clauses)\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module7_definitions = {\n",
    "\"knowledge-based agents\" : \"reasoning to decide actions, in combination with internal representations\",    \n",
    "\"knowledge representation language\" : \"group of sentences expressed to represent something about the world\",\n",
    "\"axiom\" : \"sentence given without being derived\",\n",
    "\"knowledge level\" : \"specify only what the agent knows and its goals\",\n",
    "\"model checking\" : \"enumeration of possible models to check where $\\\\alpha$ is true in all models of $KB$\",\n",
    "\"entailment\" : \"sentence A follows logically from another sentence B\",\n",
    "\"sound/truth-perserving\" : \"does not make things up, only entailed sentences (highly desirable)\",\n",
    "\"completeness\" : \"can derive any sentence it has entailed\",\n",
    "\"grounding\" : \"connection between actual environment of an agent and logical reasoning\",\n",
    "\"logical equivalence\" : \"sentences are true in same set of models ($\\\\equiv$)\",\n",
    "\"tautology\" : \"valid sentence (necessarily true)\",\n",
    "\"satisfiability\" : \"true in some model (SAT) problem\",\n",
    "\"Modus Ponens\" : \"$\\\\alpha \\\\implies \\\\beta, \\\\alpha$ gives you $\\\\beta$\",\n",
    "\"And-Elimination\" : \"any conjuncts can be inferred from a conjunction\",\n",
    "\"ground resolution theorem\" : \"resolution closure is empty clause if set of clauses is unsatisfiable\",\n",
    "\"Definite clause\" : \"disjunction of literals where 1 is positive\",\n",
    "\"Goal clause\" : \"disjunction of literals where 0 are positive\",\n",
    "\"Horn clause\" : \"disjunction of literals where at most 1 is positive (goal + definite)\",\n",
    "\"Forward chaining\" : \"progressively using known premises to derive new conclusions - no specific query (data driven reasoning)\",\n",
    "\"Backward chanining\" : \"progressively works backwards from query - goal directed reasoning\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "2b626558-1383-461a-a793-e62162fbe296"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       "\n",
       "- Knowledge-based agents don't care about implementation level\n",
       "  - Built by `TELL`ing what it needs to know\n",
       "  - From an empty knowledge base, repeatedly tell sentences until agent grows autonomous\n",
       "    - **Declarative** approach\n",
       "- Learning agent can be fully autonomous\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       "\n",
       "Wumpus World\n",
       "- **Performance Measure**: gold for leaving with gold, falling into pit or being eaten, actions taken, using arrow\n",
       "- **Environment**: 4x4 grid, walls surrounding, locations of gold and wumpus chosen randomly\n",
       "- **Actuators**: move, turn, grab gold, shoot, climb out of cave\n",
       "- **Sensors**: perceive Stench, perceive Breeze, perceive Glitter, perceive Bump, hear Scream\n",
       "- Must combine history of percepts to arrive at inferences\n",
       "- If conclusion is drawn from percepts, then guaranteed to be correct if percepts are correct\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       "\n",
       "- Standard logics: every sentence must be true or false (no in-between)\n",
       "- $M$ is a model of $\\alpha$ if $\\alpha$ is true for model $m$\n",
       "- $\\alpha \\models \\beta$ iff $M(\\alpha) \\subseteq M(\\beta)$\n",
       "- Meaning and truth of sentences/percepts comes from agent's sensors\n",
       "  - Used for general purpose learning (although fallible, provide some optimism)\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       "\n",
       "- Complex sentences are built by concatenating smaller sentences\n",
       "- Connected by logical connectives\n",
       "  - $\\neg$ (not) represents negation\n",
       "  - $\\land$ (and) represents conjuncction\n",
       "  - $\\lor$ (or) represents disjunction\n",
       "  - $\\implies$ (implies) represents implication (premise/antecedent $\\implies$ conclusion/consequent)\n",
       "  - $\\Leftrightarrow$ (if and only if) represents biconditional\n",
       "- Solving atomic sentences:\n",
       "  - $True$ is true in every model (same for $False$)\n",
       "  - Truth values must be specified directly\n",
       "- Solving complex sentences\n",
       "  - $\\neg P$ holds iff $P$ is false\n",
       "  - $P \\land Q$ holds iff both $P$ and $Q$ are true\n",
       "  - $P \\lor Q$ holds iff either $P$ or $Q$ are true\n",
       "  - $P \\implies Q$ holds unless $P$ is true and $Q$ is false\n",
       "  - $P \\Leftrightarrow Q$ holds iff $P$ and $Q$ are of the same parity\n",
       "\n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       "\n",
       "- $(\\alpha \\land \\beta) \\equiv (\\beta \\land \\alpha)$ - commutativity of $\\land$\n",
       "- $(\\alpha \\lor \\beta) \\equiv (\\beta \\lor \\alpha)$ - commutativity of $\\lor$\n",
       "- $((\\alpha \\land \\beta) \\land \\gamma) \\equiv (\\alpha \\land (\\beta \\land \\gamma))$ - associativity of $\\land$\n",
       "- $((\\alpha \\lor \\beta) \\lor \\gamma) \\equiv (\\alpha \\lor (\\beta \\lor \\gamma))$ - associativity of $\\lor$\n",
       "- $\\neg (\\neg \\alpha) \\equiv \\alpha$ - double-negation elimination \n",
       "- $(\\alpha \\implies \\beta) \\equiv (\\neg \\beta \\implies \\neg \\alpha)$ - contraposition\n",
       "- $(\\alpha \\implies \\beta) \\equiv (\\neg \\alpha \\lor \\beta)$ - implication elimination\n",
       "- $(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\implies \\beta) \\land (\\beta \\implies \\alpha))$ - biconditional elimination\n",
       "- $\\neg (\\alpha \\land \\beta) \\equiv (\\neg \\alpha \\lor \\neg \\beta)$ - De Morgan\n",
       "- $\\neg (\\alpha \\lor \\beta) \\equiv (\\neg \\alpha \\land \\neg \\beta)$ - De Morgan\n",
       "- $(\\alpha \\land (\\beta \\lor \\gamma)) \\equiv ((\\alpha \\land \\beta) \\lor (\\alpha \\land \\gamma))$ - distributivity of $\\land$ over $\\lor$\n",
       "- $(\\alpha \\lor (\\beta \\land \\gamma)) \\equiv ((\\alpha \\lor \\beta) \\land (\\alpha \\lor \\gamma))$ - distributivity of $\\lor$ over $\\land$\n",
       "\n",
       "- Monotonicity - set of entailed sentences can only *increase* when information is added\n",
       "- Forward chaining is sound and complete\n",
       "- Logic can serve as a general class of representations\n",
       "  - Defines semantics of sentences\n",
       "- $\\alpha \\models \\beta$ iff $M(\\alpha) \\subseteq M(\\beta)$\n",
       "  - $\\alpha$ is more specific than $\\beta$\n",
       "  - $\\beta$ = \"agent is a robot\", $\\alpha$ = \"agent is an astromech\"\n",
       "\n",
       "\n",
       "## Module 7 Lecture Notes\n",
       "\n",
       "- Component of knowledge based agent is a knowledge base\n",
       "- Single inference rule **resolution** which yields complete inference algorithm\n",
       "- Can eliminate complementary literals due to **unit resolution** (only applies to clauses)\n",
       "\n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge-based agents** - reasoning to decide actions, in combination with internal representations\n",
       "* **Knowledge representation language** - group of sentences expressed to represent something about the world\n",
       "* **Axiom** - sentence given without being derived\n",
       "* **Knowledge level** - specify only what the agent knows and its goals\n",
       "* **Model checking** - enumeration of possible models to check where $\\alpha$ is true in all models of $KB$\n",
       "* **Entailment** - sentence A follows logically from another sentence B\n",
       "* **Sound/truth-perserving** - does not make things up, only entailed sentences (highly desirable)\n",
       "* **Completeness** - can derive any sentence it has entailed\n",
       "* **Grounding** - connection between actual environment of an agent and logical reasoning\n",
       "* **Logical equivalence** - sentences are true in same set of models ($\\equiv$)\n",
       "* **Tautology** - valid sentence (necessarily true)\n",
       "* **Satisfiability** - true in some model (SAT) problem\n",
       "* **Modus ponens** - $\\alpha \\implies \\beta, \\alpha$ gives you $\\beta$\n",
       "* **And-elimination** - any conjuncts can be inferred from a conjunction\n",
       "* **Ground resolution theorem** - resolution closure is empty clause if set of clauses is unsatisfiable\n",
       "* **Definite clause** - disjunction of literals where 1 is positive\n",
       "* **Goal clause** - disjunction of literals where 0 are positive\n",
       "* **Horn clause** - disjunction of literals where at most 1 is positive (goal + definite)\n",
       "* **Forward chaining** - progressively using known premises to derive new conclusions - no specific query (data driven reasoning)\n",
       "* **Backward chanining** - progressively works backwards from query - goal directed reasoning\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module7_sections = [\n",
    "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
    "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
    "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
    "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
    "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
    "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
    "]\n",
    "\n",
    "module7_markdown = format_module(7, \"Logical Agents\", \n",
    "                         module7_sections, \n",
    "                         module7_definitions)\n",
    "display(Markdown(module7_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vX7lbnJd4sT5"
   },
   "source": [
    "# Your Exam Notes\n",
    "\n",
    "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
    "\n",
    "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
    "* Run the cell below. \n",
    "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
    "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
    "* In the print options, change the layout from Landscape to Portrait. \n",
    "* Clicking the Save, will save a PDF that you can then print.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "T3cm1WV542_a",
    "outputId": "3adc1d85-0aa8-4e4b-8b10-cf8b0a995e06"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       "\n",
       "Artificial intelligence is concerned with understanding the definition of rationality. \n",
       "There have been various definitions of rationality, and people have proposed numerous methods of quantifying and capturing rationality.\n",
       "1. The first approach is the Turing test approach, which seeks to determine whether a computer can \"think\" by assessing its (1) NLP, (2) knowledge representation, \n",
       "(3) automated reasoning, and (4) machine learning. An extension would be the total Turing test, which requires physical interaction with objects in the world.\n",
       "2. A contrasting approach is the cognitive modeling approach, whicch is concerned with understanding the human mind and our inner thoughts.\n",
       "3. The third approach is the \"laws of thought\" method. Aristotle determined that syllogisms and logic can be used to solve puzzles and thought. However, it generates rational thoughts\n",
       "instead of the rational action required for intelligent behavior.\n",
       "4. Rational-agent approach involves agents and acting rationally. Advantages include (1) more general since it's more open to possible mechanisms of achieving rationality, (2) \n",
       "more amenable to scientific development. This approach has generally prevailed across the field, even being deemed the \"standard model\".\n",
       "\n",
       "When building rational agents, need to keep in mind that we want AI to pursue our objectives instead of their objectives.\n",
       "\n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       "\n",
       "- Turing argues that human behavior is too complex to be captured by formal set of rules (underlies informal rules that cannot be instilled into a machine)\n",
       "- Good Old-Fashioned AI (GOFAI)\n",
       "- **Qualification problem**\n",
       "  - Tough to capture all appropriate behavior in a set of logical rules\n",
       "- Situated agents respond better than disembodied logical inference engines\n",
       "  - I.e. understanding a dog comes better from seeing and interacting rather than \"Dog => Mammal\"\n",
       "- Embodied cognition\n",
       "  - Need to study the system as a whole: mind, body, environment\n",
       "- Programs are better than humans in some areas, but significantly behind on others.\n",
       "- Programs cannot be exactly like humans\n",
       "- Today, programs have achieved some aspects of human performance, but not representative of real humans outside encoded areas\n",
       "\n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       "\n",
       "- **Polite convention**\n",
       "  - Assume that everyone thinks, should translate to machines as well\n",
       "- **Chinese room** argument\n",
       "  - Computers do not think since they are simply following rules\n",
       "- **Consciousness**\n",
       "  - Awareness of the outside world, oneself, and experiences\n",
       "- Humans have advantage over machines due to subjectivness and ability to appreciate subjective experiences\n",
       "\n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       "\n",
       "Agents interact with their environment through sensors (which fetch percepts) and perform actions through actuators.\n",
       "An agent's decisions at any point in time can be based on given knowledge and percept sequence (history), but not on the future or anything it hasn't perceived\n",
       "\n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       "\n",
       "Consequentialism is when we evaluate an agent based on its consequences rather than the decisions.\n",
       "One part of consequentialism is the performance measure, which evaluates any sequence of states from the environment.\n",
       "In general, it is better to design a performance measure based on what wants to be achieved rather than accordin to how you think the agent should act.\n",
       "\n",
       "**Rational agent** = rational agent selects action that will maximize expected utility based on provided percept sequences.\n",
       "Rationality maximizes expected utility. Perfection and omniscience, on the other hand, maximize actual utility.\n",
       "Rational agents must gather as munch information as possible and learn, thereby improving on itself autonomously.\n",
       "\n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       "\n",
       "**Task environments** = problems that rational agents are the solutions of. Need to fully define prior to designing agent.\n",
       "**PEAS** = Performance, Environment, Actuators, Sensors.  \n",
       "  - I.e. Taxi Driver\n",
       "    - P: safe, fast, legal, comfortable, maximize profits\n",
       "    - E: roads, traffic, pedestrians, customers\n",
       "    - A: steering, acccelerator, brake, signal\n",
       "    - S: cameras, radar, speedometer, GPS\n",
       "\n",
       "Entities whose behavior maximizes a measure that depends on another agent's behavior must be viewed as an agent.\n",
       "\n",
       "Chess is a competitive multiagent environment, whereas taxi-driving is a cooperative multiagent environment.\n",
       "\n",
       "Experiments are often done on a variety of environments, typically in a group called an **environment class**\n",
       "\n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       "\n",
       "Agent architecture: $$agent = architecture + program$$\n",
       "Agent program can only use current percept, whereas agent function has access to entire percept history.\n",
       "\n",
       "**Table-Driven Agent**:\n",
       "```\n",
       "def TABLE_DRIVEN_AGENT(percept)\n",
       "  append percept to the end of percepts\n",
       "  action = LOOKUP(percepts, table)\n",
       "  return action\n",
       "```\n",
       "  - Not feasible, daunting size\n",
       "  - No physical agent can store this table\n",
       "  - No time to create the table\n",
       "  - Cannot learn from all the table entries\n",
       "    - Need to produce rational behavior from smaller program\n",
       "\n",
       "**Simple reflex agents**\n",
       "- Acting on innate reflex (condition-action rule)\n",
       "- Only works if correct decision can be found based on only current percept (if fully observable)\n",
       "- Susceptible to even a little bit of unobservability\n",
       "- Randomized simple reflex agent might outperform a deterministic simple reflex agent\n",
       "- In single-agent environments, randomization is typically not rational\n",
       "\n",
       "**Model-based reflex agents**\n",
       "- Method for handling partial observability\n",
       "- Agent leeps internal state that depends on history and reflects parts of unobserved parts of current situation\n",
       "- Need two kinds of information:\n",
       "  - How the environment changes\n",
       "    - Impacts of an agent's decisions\n",
       "    - World changes independently of the entity\n",
       "    - Also known as **transition model**\n",
       "      - I.e. if car turns steering wheel, car turns\n",
       "  - How the environment's changes are reflected in agent's percepts\n",
       "    - Also known as **sensor model**\n",
       "      - I.e. if camera gets wet, droplets partially obscure view\n",
       "- Typically cannot guess environment exactly\n",
       "\n",
       "**Goal-based agents**\n",
       "- Search and planning are key subareas dedicated to finding sequences to achieve goals\n",
       "- More flexible\n",
       "\n",
       "**Utility-based agents**\n",
       "- Specifies tradeoffs for conflicting goals\n",
       "- Worried about expected utility rather than absolute utility due to not being omniscient\n",
       "- Need to keep track of environment (difficult)\n",
       "\n",
       "- Any agent can be built into a learning agent\n",
       "  - Allows agent to grow more competent than later on\n",
       "  - Divided into 4 components:\n",
       "    - Learning element --> making improvements\n",
       "    - Performance element --> selecting external actions\n",
       "    - Critic --> informs agent of its performance relative to standard\n",
       "    - Problem generator --> suggesting actions to new experiences\n",
       "      - Sacrifice short term for long term gains\n",
       "\n",
       "- More expressive language is more concise, but more learning is more complex as expressiveness increases\n",
       "\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       "\n",
       "- An agent is specified by an agent function that maps a sequence of percept vectors P to an action a from a set A\n",
       "- Agents perceive their environment through **sensors** and act upon it through **actuators**\n",
       "  - Humans (sensors = {eyes, ears}, actuators = {hands, legs, mouth})\n",
       "  - Other agents: robots, thermostats, touchless faucets\n",
       "- **Rationality**\n",
       "  - In Philosophy, AI is concerted with *consequentialism*, in that we evaluate an agent based on the consequences only\n",
       "  - In Economics, rationality is a framework for understanding behavior. Assuming people have preferences and choose what they prefer, we aggregate all decisions to see total social behavior.\n",
       "- **Performance measure**\n",
       "  - Objective criteria to determine success of an agent given percepts\n",
       "  - Design measures based on *\"what should be achieved\"* rather than *\"how you think the agent will act\"*\n",
       "  - In most cases, total omniscience is not possible, so act out of expectation\n",
       "- **Task environments**\n",
       "  - Problem specification for with the agent is a solution\n",
       "  - PEAS (specifications for a task environment)\n",
       "    - **P**erformance measure, **E**nvironment, **A**ctuators, **S**ensors\n",
       "- Fully Observable vs. Partially Observable\n",
       "  - Fully Observable --> sensors can detect all states of the environment\n",
       "  - Partially Observable --> sensors do not have access to all states of the environment\n",
       "- Deterministic vs. Nondeterministic vs. Stochastic\n",
       "  - Deterministic --> know with certainty immediate result of action\n",
       "  - Nondeterministic --> outcome is uncertain based on action (games of chance)\n",
       "  - Stochastic --> nondeterministic where we have quantified probabilities/likelihood of outcomes\n",
       "- Episodic vs. Sequential\n",
       "  - Episodic --> agent processes self-contained episodes (decision is independent of past decisions)\n",
       "  - Sequential --> immediate decision impacts future\n",
       "- Static vs. Dynamic\n",
       "  - Static --> environment remains unchanged while deliberating over action\n",
       "  - Dynamic --> environment that changes while deliberating\n",
       "- Discrete vs. Continuous\n",
       "  - Discrete --> finite set of actions and can separate different states\n",
       "  - Continuous --> follow range of values\n",
       "- Single Agent vs. Multi Agent\n",
       "  - Single Agent --> only one agent is attempting to maximize outcome\n",
       "  - Multi Agent --> exist other agents acting rationally\n",
       "\n",
       "Reflex agents - one that selects an action based on the current percept (episodic)\n",
       "\n",
       "Problem solving agent - must plan ahead and involves a computational search\n",
       "\n",
       "Hardest environment = Continuous, partially observable, stochastic, multi agent\n",
       "\n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Artificial intelligence** - understanding and building intelligent entities\n",
       "* **Rationality** - doing the right thing\n",
       "* **Turing test** - thought experiment to question: 'Can a machine think?'. Pass if human cannot tell difference in responses\n",
       "* **Natural language processing** - communicate successfully in a human language\n",
       "* **Knowledge representation** - store what it can gather through hearing and learning\n",
       "* **Automated reasoning** - respond to questions and to reach new conclusions\n",
       "* **Machine learning** - adapt to new scenarios and to extrapolate patterns\n",
       "* **Total turing test** - extension of Turing test to require interaction with objects and people (computer vision & robotics)\n",
       "* **Cognitive science** - builds theories of human mind by connecting connects computer models and psychological experiments\n",
       "* **Weak ai** - machines acting as if they were intelligent\n",
       "* **Strong ai** - machines acting intelligently (consciously thinking)\n",
       "* **Agent** - anything that can perceive and act in an environment\n",
       "* **Rational agent** - agent that acts to maximize expected outcome\n",
       "* **Value alignment problem** - system's goals and objectives should be aligned with humans\n",
       "* **Percept** - agent’s perceptual inputs at any given instance\n",
       "* **Percept sequence** - history of everything an agent as perceived\n",
       "* **Agent function** - mapping of percept sequence to action\n",
       "* **Agent program** - concrete implementation of agent program acting in a physical system\n",
       "* **Omniscience** - knows the real outcome of actions in advance (distinct from rationality)\n",
       "* **Information gathering** - performing actions in order to modify and enhance future percepts\n",
       "* **Exploration** - information gathering done to an initially unknown environment\n",
       "* **Autonomy** - ability to handle its own percepts and learn on its own without relying heavily on designer\n",
       "* **Task environment** - problems that rational agents are the solutions of\n",
       "* **Unobservable** - agent has no sensors\n",
       "* **Competitive** - competing against each other to maximize personal utility (usually at the expense of the other)\n",
       "* **Cooperative** - working with each other to maximize collective utility\n",
       "* **Stochastic** - nondeterministic process that explicitly deals with probabilities\n",
       "* **Semidynamic** - environment doesn't change over time, but performance score does\n",
       "* **Simple reflex agent** - agent that ignores prior percept, only looking at current percept\n",
       "* **Transition model** - how the world works\n",
       "* **Sensor model** - how the world's state is reflected in the percepts\n",
       "* **Utility function** - performance measure of utility\n",
       "* **Atomic representation** - each state of the world is independent/no structure\n",
       "* **Factored representation** - fixed set of attributes representing each state\n",
       "* **Structured representation** - underlying representations can be described explicitly\n",
       "* **Localist representation** - direct mapping between concepts and memory locations\n",
       "* **Distributed representation** - concept spread over multiple locations (resistant to noise)\n",
       "\n",
       "\n",
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       "\n",
       "- Suitable for everyday tasks, easy to understand (like English)\n",
       "- Garbage collected, intuitive syntax\n",
       "- Lots of 3rd party libraries\n",
       "  - NumPy (MatLab)\n",
       "  - Pandas (data analysis)\n",
       "  - Sklearn (ML)\n",
       "  - Pytorch, TensorFlow (deep learning)\n",
       "\n",
       "- Strongly Typed\n",
       "  - Cannot do `\"foo\" + 2`, get type by doing `type(object)` or `isinstance(object, type)`\n",
       "- Everything is represented as an Object\n",
       "- Dynamically Typed\n",
       "  - `type(var)` is automatically determined and found\n",
       "  - Although nice, disadvantage is that type errors are only caught at runtime\n",
       "- Strings are immutable\n",
       "\n",
       "- `x[:]` creates a shallow copy of the list `x`\n",
       "\n",
       "**Tuples**\n",
       "- Immutable ordered sequence of items\n",
       "- Cannot be modified after creation\n",
       "- Can be of mixed types\n",
       "- `my_tuple = (21, 'abc', 4.56, \"hello\")`\n",
       "- Works with indexing `my_tuple[2]` or `my_tuple[-1]` and slicing `my_tuple[1:3]`\n",
       "\n",
       "**Counter**\n",
       "```python\n",
       "from collections import Counter\n",
       "d = Counter()\n",
       "d['a']    # 0\n",
       "d['dog'] += 10\n",
       "d['dog']  # 10\n",
       "```\n",
       "\n",
       "- No overloading (function names must be unique)\n",
       "- Non-default arguments must always precede default arguments (`SyntaxError`)\n",
       "- `*args` is a way to pass in a variable number of non-keyword arguments\n",
       "- `**kwargs` - pass in variable number of keyword arguments\n",
       "- Default arguments are only evaluated the first time (memoization)\n",
       "\n",
       "- Functions are first class functions (treated as variables)\n",
       "\n",
       "```python\n",
       "class Subclass(Parent_Class):\n",
       "  # class attributes go here\n",
       "  def __init__(self, ...):\n",
       "    self.name = \"\"\n",
       "```\n",
       "\n",
       "**Magic Methods**\n",
       "- Examples: `__init__`, `__len__`, `__copy__`, `__cmp__`, `__add__`, `__neg__`\n",
       "- `if __name__ == '__main__':`\n",
       "\n",
       "**List Comprehension**\n",
       "- `[expression for name in list if filter]`\n",
       "- Same idea for dictionary and set comprehensions\n",
       "\n",
       "**Generators**\n",
       "- Iterator\n",
       "- Inserted by usinig `yield` keyword\n",
       "- Can be called as a for loop\n",
       "- Lazy evaluation (will stop when reaches first yield, then will continue)\n",
       "- Benefits:\n",
       "  - Less code\n",
       "  - Values computed as needed\n",
       "  - Avoid storing entire sequence in memory\n",
       "- `StopIteration` exception (`try: except StopIteration:`)\n",
       "\n",
       "**Imports**\n",
       "```python\n",
       "import math\n",
       "math.sqrt(9)\n",
       "\n",
       "from math import sqrt\n",
       "sqrt(9)\n",
       "\n",
       "import numpy as np\n",
       "```\n",
       "\n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Strongly typed** - objects of different types cannot interact\n",
       "* **Dynamically typed** - exact type is determined at runtime\n",
       "* **Mutability** - able to be modified and aliased\n",
       "* **Duck typing** - dynamic typing, check for presence of function/attribute\n",
       "\n",
       "\n",
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       "\n",
       "- 4 phase problem-solving process:\n",
       "  - **Goal formulation** --> organizational factor, limit objectives and scope of project\n",
       "  - **Problem formulation** --> description of states and actions needed on journey\n",
       "  - **Search** --> simulation of actions, repeated until goal/solution is found or not possible\n",
       "  - **Execution** --> running actions in sequence\n",
       "- Solution is a fixed sequence of actions when located in a fully observable, deterministic, known environment\n",
       "\n",
       "**Search Problem**\n",
       "- Defined as follows:\n",
       "  - **State space** - set of locations of environment\n",
       "  - **Initial state** - starting location\n",
       "  - **Goal state(s)** - can be multiple\n",
       "  - **Actions** - `Actions(s)` gives finite set of possible actions to be run in state `s`\n",
       "  - **Transition model** - results of each possible action from `Actions(s)` (transition model)\n",
       "  - **Action cost function** - cost of applying action `a`\n",
       "\n",
       "- Need to find right level of abstraction and detail to provide to the agent (cannot be too detailed or vague)\n",
       "- Good amount of abstraction involves removing as much detail as possible while keeping validify\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       "\n",
       "Standardized vs. Real-World Problems\n",
       "\n",
       "**Standardized Problems**\n",
       "- Grid world problem\n",
       "  - 2D array of cells, i.e. vacuum world\n",
       "- Sliding tile puzzle\n",
       "  - States: location of each tile\n",
       "  - Initial state: any state\n",
       "  - Actions: `Left`, `Right`, `Up`, `Down`\n",
       "  - Transition model: moving a piece\n",
       "  - Goal: numbers in order\n",
       "  - Action cost: each costs 1 action point\n",
       "- Knuth's conjecture that any positive integer can be reached by a sequence of sqrt, floor, and factorial ops from 4\n",
       "  - States: positive real nums\n",
       "  - Initial state: 4\n",
       "  - Actions: sqrt, floor, factorial\n",
       "  - Transition model: mathematical definitions\n",
       "  - Goal: desired positive integer\n",
       "  - Action cost: each costs 1 action point\n",
       "\n",
       "**Real-World Problems**\n",
       "- Route-finding problem\n",
       "  - Examples: GPS, web surfing, streaming, airline travel\n",
       "  - Airline Travel\n",
       "    - States: each state records location, cost, status, and additional extra information\n",
       "    - Initial state: home airport\n",
       "    - Actions: take any flight from current airport, any seat class, depart after current time, etc.\n",
       "    - Transition model: take from airportA to airportB\n",
       "    - Goal: arrive at destination\n",
       "    - Action cost: cost of flight, waiting time, quality of experience, etc.\n",
       "- Touring problems\n",
       "  - Traveling salesperson problem (every city on the map must be visited)\n",
       "  - Robot navigation\n",
       "  - Automatic assembly sequencing, protein design\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       "\n",
       "- Form search tree over state space to build a graph\n",
       "  - Root is initial state\n",
       "  - Traverse tree to find node that represents goal\n",
       "\n",
       "- Frontier --> separates two regions of the graph: the region where every state has been expanded and a region where states have not been reached\n",
       "\n",
       "**Best-First Search**\n",
       "- Greedily choose node $n$ with minimum value (calculated by evaluation function)\n",
       "\n",
       "```python\n",
       "def best_first_search(problem, f):\n",
       "  node = Node(problem.initial)\n",
       "  frontier = priority queue ordered by f, with node as element\n",
       "  reached = lookup table with one entry with key problem.initial and value node\n",
       "  while not is_empty(frontier):\n",
       "    node = frontier.pop()\n",
       "    if problem.is_goal(node.state):\n",
       "      return node\n",
       "    for child in expand(problem, node):\n",
       "      s = child.state\n",
       "      if s not in reched or child.path_cost < reached[s].path_cost:\n",
       "        reached[s] = child\n",
       "        frontier.add(child)\n",
       "  return failure\n",
       "```\n",
       "- Algorithms are weak and poor if they cannot remember the past (possibly infinite due to loops)\n",
       "- **Graph search** - checks for redundant paths\n",
       "- **Tree search** - does not check for redundant paths (save space by not storing reached states)\n",
       "\n",
       "**Evaluation of Performance**\n",
       "- 4 ways:\n",
       "  - **Completeness** --> guaranteed to find a solution if one exists, or report failure\n",
       "  - **Cost optimality** --> finds solution with minimum cost\n",
       "  - **Time complexity** --> time of solution relative to number of inputs\n",
       "  - **Space complexity** --> memory/space of solution relative to number of inputs\n",
       "- Complexity may also be measured by depth $d$, maximum number of actions $m$, or branching factor/node successors $b$\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       "\n",
       "- Uninformed search algorithms do not know how close they are to the goal state\n",
       "\n",
       "**Breadth First Search (BFS)**\n",
       "- Expand nodes by successors in waves\n",
       "- FIFO queue based, use set of states instead of map\n",
       "  - *Early Goal Test* - check whether a node is a solution as soon as its visited\n",
       "  - *Late Goal Test* - check whether a node is a solution when it the node in question (popped from queue)\n",
       "- Always finds **cost-optimal solution only when all actions have the same cost**\n",
       "- Always complete\n",
       "- Time complexity: $O(b^d)$, Space complexity: $O(b^d)$\n",
       "- Memory is bigger concern than time\n",
       "  - As a result, exponential search cannot solve larger uninformed search problems\n",
       "\n",
       "**Uniform-Cost Search / Dijkstra's**\n",
       "- Used when actions have varying costs\n",
       "- Expand based on distance from source (may need to relax distances)\n",
       "- Cost of optimal solution = $C^*$, $\\epsilon$ is lower bound on cost of action\n",
       "  - Time complexity: $O(b^{1 + \\lfloor C^* / \\epsilon \\rfloor })$, Space complexity: $O(b^{1 + \\lfloor C^* / \\epsilon \\rfloor})$\n",
       "- Complete, cost-optimal\n",
       "\n",
       "**Depth-First Search**\n",
       "- Expands deepest nodes first\n",
       "- Implemented as a tree search instead of a graph search\n",
       "  - Does not keep reached states\n",
       "- Not cost optimal (finds the first solution)\n",
       "- Finite spaces:\n",
       "  - Efficient and complete\n",
       "- Requires less memory than other traversals\n",
       "  - Small frontier, no reached table of states\n",
       "  - Time complexity: $O(b^m)$, Space complexity: $O(bm)$\n",
       "- **Backtracking search** variant\n",
       "  - Only 1 successor generated at each time\n",
       "  - Critical for large state environments\n",
       "\n",
       "**Depth-Limited Search**\n",
       "- Similar to DFS, but include upper limit of depth $l$\n",
       "- Time complexity: $O(b^l)$, Space complexity: $O(bl)$\n",
       "- Can choose good $l$ if we know some info (ie. diameter) of the problem\n",
       "\n",
       "**Iterative-Deepening Search**\n",
       "- Similar to depth-limited search, but tries all values for $l$ from 0 upwards\n",
       "  - Terminates either when solution is found or failure value\n",
       "  - Time complexity: $O(b^d)$ when exists solution, $O(b^m)$ when no solution\n",
       "  - Space complexity: $O(bd)$ when exists solution, $O(bm)$ when no solution\n",
       "- Does not matter that nodes at top of repeated since it is much smaller compared to nodes at bottom\n",
       "- Overall, **preferred uninformed search strategy** when state space is large and depth is not known\n",
       "\n",
       "**Bidirectional Search**\n",
       "- Searches forward from start state and backwards from end state(s), terminating when the two meet\n",
       "- Keep track of two frontiers and two reached tables\n",
       "- Time complexity: $O(b^{d/2})$, Space complexity: $O(b^{d/2})$\n",
       "\n",
       "\n",
       "## Module 3 Lecture Notes\n",
       "\n",
       "**DFS vs BFS:**\n",
       "\n",
       "*Use DFS if:* space is restricted, there are many possible solutions amnd long paths are ended quickly\n",
       "\n",
       "*Use BFS if:* possible infinite paths, some solutions have short paths\n",
       "\n",
       "For **depth limited search**, if $l = d$, then optimal. However, if $l < d$, then incomplete. if $l > d$ not optimal\n",
       "\n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "* **Informed** - agent can estimate its distance from the goal\n",
       "* **Uninformed** - agent cannot estimate its distance from the goal\n",
       "* **Open-loop** - ignoring percepts while on the path to a solution (guaranteed to be correct and lead to goal)\n",
       "* **Closed-loop** - monitors perepts while following path to goal (nondeterministic or possibly incorrect sequence)\n",
       "* **State space** - set of locations of environment\n",
       "* **Initial state** - starting location\n",
       "* **Goal state(s)** - can be multiple\n",
       "* **Actions** - `Actions(s)` gives finite set of possible actions to be run in state `s`\n",
       "* **Transition model** - results of each possible action from `Actions(s)` (transition model)\n",
       "* **Action cost function** - cost of applying action `a`\n",
       "* **Optimal solution** - lowest path cost\n",
       "* **Model** - abstract mathematical description\n",
       "* **Abstraction** - removing explicit details from representation\n",
       "* **Standardized problem** - illustrate various problem-solving methods (benchmark for algo performance)\n",
       "* **Real-world problem** - concrete solutions that people use and is unique/individual\n",
       "* **Search algorithm** - problem as input, returns a solution or none if not possible\n",
       "* **Frontier** - set of next unexpanded nodes\n",
       "* **Best-first search** - greedily choose node $n$ with minimum value (calculated by evaluation function)\n",
       "* **Priority queue** - queue where nodes are ordered based on priority (i.e. min cost) - best-first search\n",
       "* **Fifo queue** - first-in-first-out, queue (BFS)\n",
       "* **Lifo queue** - last-in-first-out, stack (DFS)\n",
       "* **Graph search** - checks for redundant paths (stores reached states)\n",
       "* **Tree search** - does not check for redundant paths (save space by not storing reached states)\n",
       "* **Breadth-first search (bfs)** - expand nodes by successors in waves (queue based)\n",
       "* **Uniform-cost search** - (dijkstra) least cost nodes from sourc e are expanded\n",
       "* **Depth-first search (dfs)** - expand deepest nodes first in a tree search (stack based)\n",
       "* **Depth-limited search** - DFS with maximum depth layer $l$\n",
       "* **Iterative-deepening search** - depth-limited search where all values for $l$ are tried\n",
       "\n",
       "\n",
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       "\n",
       "**Greedy Best-First Search**\n",
       "- Best-first search with $f(n)=h(n)$\n",
       "- Greediness can lead to worse results than being careful (not always optimal)\n",
       "- Complete in finite spaces, but not in infinite ones\n",
       "- Time complexity: $O(V)$, Space complexity: $O(V)$\n",
       "- With a good heuristic: Time complexity: $O(bm)$, Space complexity: $O(bm)$\n",
       "\n",
       "**A* Search**\n",
       "- Best-first search with $f(n)=g(n)+h(n)$ where $g(n)$ is path cost from source to $n$ and $h(n)$ is estimated cost from $n$ to goal\n",
       "- Complete\n",
       "- Cost-optimal depends on the heuristic\n",
       "  - Good heuristic should be admissible\n",
       "- Every consistent heuristic is admissible so a consistent heuristic is cost-optimal.\n",
       "  - Vice versa is not true\n",
       "  - Consistent if $h(n) \\leq c(n,a,n')+h(n')$ for all nodes $n$ adn successors $n'$ of $n$ by action $a$\n",
       "- An inadmissible heuristic may not be cost-optimal.\n",
       "- $g$ costs are monotonic since action costs are always positive, causing path cost always increases as you go along the path\n",
       "- If $C^*$ is the cost of the optimal solution path, then:\n",
       "  - Expands all nodes that can be visited from the source on the path where each node in the path has $f(n)<C^*$ (surely expanded nodes)\n",
       "  - Might expand some nodes on goal contour where $f(n)=C^*$ before selecting goal node\n",
       "  - Expands no nodes with $f(n)>C^*$\n",
       "- Optimally efficient\n",
       "- A* prunes search tree nodes that are not necessary for finding optimal solution\n",
       "- However, number of nodes expanded can potentially be exponential in solution\n",
       "\n",
       "- Inadmissible heuristics risk missing optimal solutions, but can reduce number of nodes expanded\n",
       "- Weighted A* search = $f(n) = g(n) + W * h(n)$\n",
       "\n",
       "**Methods of saving space for A\\***\n",
       "- Only store node in one of either frontier or reached states\n",
       "- Remove nodes from reached set when no longer needed\n",
       "- MA* (memory-bounded A*), SMA* (simplified MA*)\n",
       "\n",
       "**Beam search**\n",
       "- Limits size of frontier\n",
       "- Keeps only $k$ nodes in frontier\n",
       "- Incomplete & suboptimal, but if a good $k$ is choen, makes good use of memory and speed\n",
       "\n",
       "**Iterative-deepening A* search (IDA*)**\n",
       "- A* without keeping visited set, but possibly visit states multiple times\n",
       "- Cutoff is $f(n)$ --> each iteration, cutoff is smallest $f(n)$ that exceeded the cutoff on prior iteration\n",
       "\n",
       "**Recursive best-first search (RBFS)**\n",
       "- best-first search using only linear space\n",
       "- If node surpasses `f_limit`, recursion unwinds and replaces with backed-up value (best $f(n)$ among children)\n",
       "- Suffers from excessive node regeneration\n",
       "- RBFS is optimal if $h(n)$ is admissible\n",
       "- Space is linear $O(d)$ in terms of depth of deepest optimal solution\n",
       "\n",
       "**Bidirectional heuristic search**\n",
       "- No guarantee of optimal cost or optimally efficient (even with admissible $h(n)$)\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       "\n",
       "**Quality of Heuristic**\n",
       "- Effective branching factor $b^*$\n",
       "  - $N+1=1+b^*+(b^*)^2+...+(b^*)^d$\n",
       "  - Attempt to minimize $b^*$ as much as possible, value close to 1\n",
       "- Effective depth\n",
       "  - Reduce by constant $k_h$ compared to true depth\n",
       "- Domination\n",
       "  - If $h_2(n) \\geq h_1(n)$, then $h_2$ dominates $h_1$\n",
       "    - Implies that $h_2$ will never expand more nodes than $h_1$\n",
       "    - Generally better to use an $h(n)$ function with higher values\n",
       "\n",
       "- Any optimal solution in the original problem is also a solution in the relaxed problem\n",
       "  - However, relaxed problem may have more optimal solutions\n",
       "  - Cost of an optimal solution to relaxed is an admissible heuristic for the original\n",
       "\n",
       "- Landmark points - help to check since most paths will go through landmark\n",
       "  - Works well because lots of traffic goes through landmarks\n",
       "\n",
       "- Overall, can generate good heuristics by relaxing, storinig precomputed costs of subproblems, defining landmarks, or learning from experience\n",
       "\n",
       "\n",
       "## Module 4 Lecture Notes\n",
       "\n",
       "**A* Search**\n",
       "- Prune out paths that are already known to be expensive\n",
       "\n",
       "**Dominance: metric on better heuristics**\n",
       "- If $h_2(n) \\geq h_1(n)$ for all $n$, then $h_2$ dominates $h_1$\n",
       "  - Implies that $h_2$ is optimistic, but more accurate than $h_1$ and so $h_2$ is better for search\n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Informed search** - uses hints about the environment to solve problem more efficiently than uninformed search\n",
       "* **Heuristic function** - estimated cost of the path from current state to goal state\n",
       "* **Greedy best-first search** - best-first search with $f(n) = h(n)$\n",
       "* **A* search** - best-first search with $f(n)=g(n)+h(n)$\n",
       "* **Admissibility** - $0 \\leq h(n) \\leq h^*(n)$ where $h^*(n)=$true cost; never overestimates cost to reach the terminating state (optimistic)\n",
       "* **Consistency** - $h(n) \\leq c(n,a,n') + h(n')$ for each $n$ and successor $n'$ for action $a$\n",
       "* **Surely expanded nodes** - nodes that can be visited from the start on the path where each node has $f(n)<C^*$\n",
       "* **Satisficing** - suboptimal solution that is 'good enough'\n",
       "* **Inadmissible heuristic** - overestimates cost to reah goal\n",
       "* **Bounded suboptimal search** - finds solution within constant $W$ of optimal cost (use weighted A*)\n",
       "* **Bounded cost search** - finds solution where cost is less than constant $C$\n",
       "* **Unbounded cost search** - finds solution of any cost as long as its found quickly\n",
       "* **Speedy search** - greedy best-first variant where h(n) = estimated actions to goal (fast but high cost)\n",
       "* **Beam search** - search algo that only keeps $k$ nodes in frontier\n",
       "* **Iterative-deepening a* search** - A* without keeping visited set, but possibly visit states multiple times\n",
       "* **Recursive best-first search** - best-first search using only linear space\n",
       "* **Weighted a* search** - A* expanding fewer nodes, but sacrificing optimality\n",
       "* **Manhattan distance** - sum of horizontal and vertical distances\n",
       "* **Effective branching factor ($b^*$)** - number of nodes expanded for given node $n$\n",
       "* **Relaxed problem** - a problem with fewer restrictions\n",
       "* **Pattern database** - mapping from subproblem to solution cost\n",
       "* **Differential heuristic** - heuristic that is both efficient and admissible with subtraction\n",
       "\n",
       "\n",
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       "\n",
       "- Treat multiagent environments as an economy, a part of the environments\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       "\n",
       "**Minimax Algorithm**\n",
       "- MAX chooses to maximize minimax value, MIN chooses to minimize minimax value\n",
       "- Minimax value is the minimum possible utility in any iteration of the game\n",
       "  - If opponent plays suboptimally, can increase utility, but may not necessarily play minimax optimal move\n",
       "- DFS exploration (Time: $O(b^m)$, Space: $O(bm)$)\n",
       "- Exponential means it's impractical for larger games\n",
       "- Alliances/betrayals may form and make concrete what would've happened in minimax games\n",
       "\n",
       "**Alpha-Beta Pruning**\n",
       "- $\\alpha$ = value of the best (heighest) utility we have so far on any point along the path for MAX\n",
       "  - at least\n",
       "- $\\beta$ = value of the best (lowest) utility found so far on any point along the path for MIN\n",
       "  - at most\n",
       "- Prunes as soon as the value of the current node is known to be worse (less) \n",
       "than the current $\\alpha$ or (greater than) $\\beta$ for MAX or MIN, respectively\n",
       "- Order of visiting nodes affects alpha-beta pruning effectiveness\n",
       "- Perfectly, alpha-beta pruning only needs to visit $O(b^{m/2})$ nodes since effective branching factor is $\\sqrt{b}$\n",
       "- Trying moves that worked well in the past can help (iterative deepening)\n",
       "- Repeated states can come up due to **transpositions** (solution: transposition table)\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       "\n",
       "- Cutoff test\n",
       "\n",
       "**Evaluation Functions**\n",
       "- Good eval functions\n",
       "  - Computation should not take too long\n",
       "  - Strongly correlated with real chances of winning\n",
       "- Most eval functions compute distinct numbers for each feature and combine them for a total value\n",
       "  - Ie. *material value* for chess\n",
       "- Eval function should only be evaluated on **quiescent** (no pending moves) positions\n",
       "\n",
       "- **Horizon effect** is difficult to eliminate\n",
       "  - **Singular extensions** --> moves that are more optimal than other moves, but would normally be cut off\n",
       "    - Effective since number of singular extensions is usually low\n",
       "\n",
       "- Forward pruning - eliminating moves that look bad\n",
       "- Many complex games use table lookup instead of search for the beginning and ends of the game (when there are popular options)\n",
       "  - i.e. chess (pawn to e4)\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       "\n",
       "**Stochastic Games**\n",
       "- Maximize expected value of positions (average of all possible outcomes of chance nodes)\n",
       "- **Expectiminimax value** - minimax value with expectation involved\n",
       "  - Time: $O(b^mn^m)$ where $n=$ number of distinct rolls\n",
       "  - Difficult to predict since possibilities are multiplied tremendously\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       "\n",
       "Decision theory = choosing actions based on their immediate outcomes (captured by utility function)\n",
       "Maximum expected utility (MEU) - rational agent should choose action to maximize expected util\n",
       "  - formalizes the notion of \"doing the right thing\", but does not operationalize it\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       "\n",
       "Preference relation constraints:\n",
       "1. Orderability - must be able to sort preferences/order lotteries\n",
       "2. Transitivity - prefer A to B, prefer B to C, then must prefer A to C\n",
       "3. Continuity - if preference is A-B-C, then at some point, agent is indifferent about definitely getting B versus yielding A with prob $p$ and C with $1-p$\n",
       "4. Substitutability - A and B are indifferent and can be substituted without changing outcome\n",
       "5. Monotonicity - if A and B have same outcome, then agent should prefer the one with the higher probability of occurring\n",
       "6. Decomposability - compound lotteries can be decomposed into smaller ones using probability\n",
       "\n",
       "Effect on utility:\n",
       "1. Existence of utility function - exists a function $U$ such that $U(A) > U(B)$ iff $A$ preferred over $B$ (same for indifference)\n",
       "2. Expected utility of a lottery - sum of probability of each outcomes multiplied by actual utility of outcome\n",
       "\n",
       "Decisions depend only on preferences (numbers don't matter)\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       "\n",
       "Certainty Effect\n",
       "- Reduce computational burden\n",
       "- Distrust legitimacy of the stated probabilities\n",
       "- Accounting for emotional state\n",
       "\n",
       "\n",
       "## Module 5 Lecture Notes\n",
       "\n",
       "Evaluation function - based on static features of the board alone\n",
       "\n",
       "**Alpha-Beta Pruning**\n",
       "- MAX will never allow move where $v \\leq \\alpha$\n",
       "- MIN will never allow move where $v \\geq \\beta$\n",
       "- Stop evaluating branch when:\n",
       "  - For MAX, stop when value $v \\geq \\beta$\n",
       "  - For MIN, stop when value $v \\leq \\alpha$\n",
       "\n",
       "**Expectimax Search**\n",
       "- Compute the average score under optimal play\n",
       "  - Calculate expected utilities\n",
       "- Pruning is more difficult with chance\n",
       "\n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Imperfect information** - not all information is visible\n",
       "* **Perfect information** - fully observable\n",
       "* **Zero-sum games** - good for one is bad for the other\n",
       "* **Minimax search** - maximize minimum game where game has multiple outcome scores\n",
       "* **Minimax value** - utility at the current state assuming both players have acted rationally\n",
       "* **Pruning** - computing minimax decision without examining all states\n",
       "* **Alpha-beta pruning** - $\\alpha=$ at least, $\\beta=$ at most\n",
       "* **Transpositions** - different permutations of the sequence that end in same position\n",
       "* **Transposition table** - cache for mapping position to heuristic value\n",
       "* **Type a strategy** - considers *wide but shallow* portion of search tree (all moves to depth $d$, heuristically eval to get utility)\n",
       "* **Type b strategy** - considers *deep but narrow* portion of search tree (ignores bad, follows promising)\n",
       "* **Quiescent** - positions that have no pending moves\n",
       "* **Horizon effect** - when the delaying moves unnecessarily weaken the position or give up additional material to postpone the eventual loss\n",
       "* **Forward pruning** - pruning moves that look like bad moves (risky - could be good)\n",
       "* **Late move reduction** - assumption that moves done later are less likely to be good moves\n",
       "* **Policy** - mapping from states to best move\n",
       "* **Stochastic games** - games with unpredictability (not deterministic)\n",
       "* **Chance nodes** - nodes indicating possible outcomes that are not under user's control\n",
       "* **Value function** - decision depends only on preferences (not numbers)\n",
       "* **Ordinal utility function** - decision depends only on preferences (not numbers)\n",
       "* **Preference elicitation** - observe preferences and compute utility function by presenting choices\n",
       "* **Normalized utilities** - normalized scale for presenting utility\n",
       "* **Risk averse** - prefer outcomes with low uncertainty, even if average outcome of higher risk is higher\n",
       "* **Risk seeking** - prefer outcomes with high uncertainty\n",
       "* **Certainty effect** - people are strongly attracted to certainty\n",
       "* **Ambiguity aversion** - people choose known probabilty over unknowns\n",
       "* **Framing effect** - wordings can influence decisions\n",
       "* **Anchoring effect** - judging based on some fixed anchor point\n",
       "\n",
       "\n",
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       "\n",
       "**CSP Definition**\n",
       "- 3 components:\n",
       "  - $X=\\{X_1, X_2, ..., X_n\\}$ where $X$ is a variable\n",
       "  - $D=\\{D_1, D_2, ..., D_n\\}$ where $D$ is a domain\n",
       "  - $C$ is a set of constraints that specify allowable combinations of values\n",
       "- Solving CSP is NP-complete\n",
       "\n",
       "- CSPs are an easy, natural representation for problems\n",
       "- Lots of development work in history\n",
       "- Prune lots of search space at a time\n",
       "\n",
       "- Simplest CSP is discrete, finite domains\n",
       "  - Coloring problem, scheduling, 8 queens problem\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       "\n",
       "Local consistency - enforcing local consistency in all parts of a graph leads inconsistent values to be eliminated\n",
       "\n",
       "**AC-3** = popular arc consistency algorithm\n",
       "- queue of arcs (initialized to all arcs)\n",
       "- pop off arbitrary arc ($X_i$, $X_j$) -> make $X_i$ arc consistent with $X_j$\n",
       "  - If domain doesn't change, then continue\n",
       "  - If domain changes, then add all arcs ($X_k$, $X_i$) where $X_k$ is a neighbor of $X_i$\n",
       "    - Changing $i$'s domain might change $k$\n",
       "  - If $i$'s new domain is empty, then report failure\n",
       "- Time: $O(cd^3)$ where $d$ is max domain size, $c$ is number of arcs\n",
       "\n",
       "**Path consistency** - Tighter set of binary constraints\n",
       "\n",
       "**K-consistency** - a consistent value can always be assigned to a $k$th variable for any set of $k-1$ variables\n",
       "\n",
       "Example of CSP - Sudoku\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       "\n",
       "- CSPs are **commutative**\n",
       "- Backtracking search can be improved using *domain-independent* heuristics to take advantage of CSPs\n",
       "\n",
       "**Strategies for assigning variable values**\n",
       "- Simplest is to go in order $\\{X_1,X_2,...\\}$. Next is to choose randomly. Neither is optimal\n",
       "- **Minimum-Remaining-Values** heuristic\n",
       "  - Chooses variable that is most constrained, pruning subtree\n",
       "  - If no legal moves remain, return FAILURE\n",
       "- **Degree heuristic**\n",
       "  - Tries to reduce the branching factor on future choices\n",
       "- Once a variable has been selected, use **least-constraining-value**\n",
       "  - Wants to leave maximum flexibility for subsequent variables\n",
       "\n",
       "**Search and inference**\n",
       "- **Forward checking** --> delete from $Y$'s domain all inconsistent values chosen for $X$\n",
       "- **Maintaining Arc Consistency**\n",
       "  - More powerful than forward checking\n",
       "  - Forward checking does not recursively propagate constraints when changes are made to domains, whereas MAC does\n",
       "\n",
       "**Backtracking**\n",
       "- Chronological backtracking is suboptimal/can be improved\n",
       "- Backjumping is an improvement\n",
       "  - Ie. conflict-directed backjumping\n",
       "\n",
       "**Constraint learning**\n",
       "- Minimum set of variables from conflict set is **no-good**\n",
       "  - Record no-good either by adding new constraint or keeping in cache\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       "\n",
       "**Min-conflicts** - heuristic to choose value that results in minimum number of future conflicts\n",
       "- N-queens problem\n",
       "  - Runtime of min-conflicts is independent of problem size\n",
       "- **Tabu search** - small list of visited states and forbidding algorithm from returning to them\n",
       "- Local search can be used in online settings where problems change\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       "\n",
       "Independence - finding connected components and solving independent subproblems\n",
       "\n",
       "All tree-structured CSPs can be solved in linear time with respect to number of variables\n",
       "- Directional arc consistency\n",
       "- Can be solved through topological ordering\n",
       "\n",
       "**Cutset conditioning algorithm**\n",
       "1. Find and select subset $S$ of variables so that graph becomes a tree after removal ($S$ is a cycle cutset)\n",
       "2. For each assignment of variables in $S$ that satisfies constraints,\n",
       "  - Remove all inconsistent values with assignment for $S$ from domains of remaining variables\n",
       "  - Return CSP solution with $S$'s assignment\n",
       "\n",
       "**Tree decomposition**\n",
       "- 3 requirements\n",
       "  - Each variable in the original problem shows up in at least one tree node\n",
       "  - Two variables connected by constraint in original problem must appear together in at least one tree node\n",
       "  - If a variable is in two tree nodes, must appear in every node along the path to those nodes\n",
       "- Solve in $O(nd^2)$ time where $n$ is number of tree nodes and $d$ is size of the largest domain\n",
       "- Efficient if tree width is small\n",
       "\n",
       "**Value symmetry**\n",
       "- Assign values interchangeably\n",
       "- Resolved by introducing **symmetry-breaking constraint**\n",
       "  - Ie. imposing arbitrary ordering\n",
       "\n",
       "\n",
       "## Module 6 Lecture Notes\n",
       "\n",
       "- Assumptions: single agent, deterministic, fully observed state, discrete state space\n",
       "- Planning: sequences of actions\n",
       "- Identification: assignments to variables\n",
       "\n",
       "- Formal declarative language to find solutions for *general purpose* problems\n",
       "\n",
       "**Varieties of CSPs**\n",
       "- Discrete variables\n",
       "  - finite domains\n",
       "    - $n$ variables, $d$ domain size --> $O(d^n)$ complete assignments\n",
       "  - infinite domains\n",
       "    - integers, strings, etc.\n",
       "- Continuous variables\n",
       "  - linear constraints solvable in polynomial time by linear programming\n",
       "\n",
       "**Improving backtracking**\n",
       "- Most constrained variable (MRV heuristic)\n",
       "  - \"fail as quickly as possible\"\n",
       "  - Most constraining variable (tiebreaker)\n",
       "    - Choose variable with most constraints on remaining variables\n",
       "    - Combination of the two heuristics lead to direct solution (no backtracking)\n",
       "- Least constraining value\n",
       "  - Given variable choose least constraining heurstic (fewest values remaining)\n",
       "- Forward checking\n",
       "  - Check remaining unassigned variable\n",
       "  - Terminate when any unassigned variable has no remaining legal values\n",
       "  - Use DS to keep track of remaining values for each variable\n",
       "  - Propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures\n",
       "\n",
       "**Interefence in CSP**\n",
       "- Local consistency (defined by two constraints)\n",
       "  - Node consistency: satisfies unary constraints\n",
       "  - Arc consistency: satisfies binary constraints\n",
       "    - arc (i,j) is consistent iff every value v on $X_i$ is consistent with some label on $Y_j$\n",
       "- **AC-3**\n",
       "  - Only need to examine those $X_i$ where at least one neighbor of $X_i$ has lost a value\n",
       "\n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Constraint satisfaction problem** - problem with sets of variables and values\n",
       "* **Consistent assignment** - assignment that does not break any of the contraints of a CSP\n",
       "* **Complete assignment** - every variable in a CSP is assigned a value\n",
       "* **Solution** - consistent, complete assignment for a CSP\n",
       "* **Partial assignment** - assignment that leaves some variables unassigned\n",
       "* **Partial solution** - consistent, partial assignment\n",
       "* **Precedence constraint** - constraint that $T_1$ must come before $T_2$\n",
       "* **Disjunctive constraint** - constraint that must not overlap\n",
       "* **Unary constraint** - a single variable's value is restricted ($SA \n",
       "eq green$)\n",
       "* **Binary constraint** - two variables values are restricted against each other ($SA \n",
       "eq NSW$)\n",
       "* **Binary csp** - CSP with only binary and unary constraints\n",
       "* **Global constraint** - constraint with arbitrary number of variables\n",
       "* **Preference constraints** - CSP constraints where solutions are preferred over others\n",
       "* **Constrained optimization problem** - CSP with preferences are solved with optimizations (ie. linear programs)\n",
       "* **Constraint propagation** - reduce the number of legal values for variable based on constraints\n",
       "* **Node-consistent** - all values in the variable'd domain satisfy unary constraints\n",
       "* **Arc-consistent** - all values satisfy binary constraints\n",
       "* **Strongly $k$-consistent** - k-consistent, (k-1)-consistent, ..., down to 1-consistent\n",
       "* **Resource constraint** - constraint in dedication of resources\n",
       "* **Bounds propagation** - managing upper and lower bounds for domains and adjusting as necessary\n",
       "* **Minimum-remaining-values (mrv)** - heuristic that chooses the variable with the fewest legal moves\n",
       "* **Least-constraining-value** - prefers value that rules out the fewest choices for neighbors\n",
       "* **Forward checking** - establishes arc consistency for variable $X$ when assigned (delete any inconsistent value in $Y$ from $X$)\n",
       "* **Chronological backtracking** - if search fails, back up and try different value\n",
       "* **Backjumping** - backtrack to most recent assignment in the conflict set\n",
       "* **Constraint learning** - finding minimum set of variables from set that causes problem\n",
       "* **Independent subproblems** - solutions to subproblems that when combined, yield solution for entire problem\n",
       "\n",
       "\n",
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       "\n",
       "- Knowledge-based agents don't care about implementation level\n",
       "  - Built by `TELL`ing what it needs to know\n",
       "  - From an empty knowledge base, repeatedly tell sentences until agent grows autonomous\n",
       "    - **Declarative** approach\n",
       "- Learning agent can be fully autonomous\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       "\n",
       "Wumpus World\n",
       "- **Performance Measure**: gold for leaving with gold, falling into pit or being eaten, actions taken, using arrow\n",
       "- **Environment**: 4x4 grid, walls surrounding, locations of gold and wumpus chosen randomly\n",
       "- **Actuators**: move, turn, grab gold, shoot, climb out of cave\n",
       "- **Sensors**: perceive Stench, perceive Breeze, perceive Glitter, perceive Bump, hear Scream\n",
       "- Must combine history of percepts to arrive at inferences\n",
       "- If conclusion is drawn from percepts, then guaranteed to be correct if percepts are correct\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       "\n",
       "- Standard logics: every sentence must be true or false (no in-between)\n",
       "- $M$ is a model of $\\alpha$ if $\\alpha$ is true for model $m$\n",
       "- $\\alpha \\models \\beta$ iff $M(\\alpha) \\subseteq M(\\beta)$\n",
       "- Meaning and truth of sentences/percepts comes from agent's sensors\n",
       "  - Used for general purpose learning (although fallible, provide some optimism)\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       "\n",
       "- Complex sentences are built by concatenating smaller sentences\n",
       "- Connected by logical connectives\n",
       "  - $\\neg$ (not) represents negation\n",
       "  - $\\land$ (and) represents conjuncction\n",
       "  - $\\lor$ (or) represents disjunction\n",
       "  - $\\implies$ (implies) represents implication (premise/antecedent $\\implies$ conclusion/consequent)\n",
       "  - $\\Leftrightarrow$ (if and only if) represents biconditional\n",
       "- Solving atomic sentences:\n",
       "  - $True$ is true in every model (same for $False$)\n",
       "  - Truth values must be specified directly\n",
       "- Solving complex sentences\n",
       "  - $\\neg P$ holds iff $P$ is false\n",
       "  - $P \\land Q$ holds iff both $P$ and $Q$ are true\n",
       "  - $P \\lor Q$ holds iff either $P$ or $Q$ are true\n",
       "  - $P \\implies Q$ holds unless $P$ is true and $Q$ is false\n",
       "  - $P \\Leftrightarrow Q$ holds iff $P$ and $Q$ are of the same parity\n",
       "\n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       "\n",
       "- $(\\alpha \\land \\beta) \\equiv (\\beta \\land \\alpha)$ - commutativity of $\\land$\n",
       "- $(\\alpha \\lor \\beta) \\equiv (\\beta \\lor \\alpha)$ - commutativity of $\\lor$\n",
       "- $((\\alpha \\land \\beta) \\land \\gamma) \\equiv (\\alpha \\land (\\beta \\land \\gamma))$ - associativity of $\\land$\n",
       "- $((\\alpha \\lor \\beta) \\lor \\gamma) \\equiv (\\alpha \\lor (\\beta \\lor \\gamma))$ - associativity of $\\lor$\n",
       "- $\\neg (\\neg \\alpha) \\equiv \\alpha$ - double-negation elimination \n",
       "- $(\\alpha \\implies \\beta) \\equiv (\\neg \\beta \\implies \\neg \\alpha)$ - contraposition\n",
       "- $(\\alpha \\implies \\beta) \\equiv (\\neg \\alpha \\lor \\beta)$ - implication elimination\n",
       "- $(\\alpha \\Leftrightarrow \\beta) \\equiv ((\\alpha \\implies \\beta) \\land (\\beta \\implies \\alpha))$ - biconditional elimination\n",
       "- $\\neg (\\alpha \\land \\beta) \\equiv (\\neg \\alpha \\lor \\neg \\beta)$ - De Morgan\n",
       "- $\\neg (\\alpha \\lor \\beta) \\equiv (\\neg \\alpha \\land \\neg \\beta)$ - De Morgan\n",
       "- $(\\alpha \\land (\\beta \\lor \\gamma)) \\equiv ((\\alpha \\land \\beta) \\lor (\\alpha \\land \\gamma))$ - distributivity of $\\land$ over $\\lor$\n",
       "- $(\\alpha \\lor (\\beta \\land \\gamma)) \\equiv ((\\alpha \\lor \\beta) \\land (\\alpha \\lor \\gamma))$ - distributivity of $\\lor$ over $\\land$\n",
       "\n",
       "- Monotonicity - set of entailed sentences can only *increase* when information is added\n",
       "- Forward chaining is sound and complete\n",
       "- Logic can serve as a general class of representations\n",
       "  - Defines semantics of sentences\n",
       "- $\\alpha \\models \\beta$ iff $M(\\alpha) \\subseteq M(\\beta)$\n",
       "  - $\\alpha$ is more specific than $\\beta$\n",
       "  - $\\beta$ = \"agent is a robot\", $\\alpha$ = \"agent is an astromech\"\n",
       "\n",
       "\n",
       "## Module 7 Lecture Notes\n",
       "\n",
       "- Component of knowledge based agent is a knowledge base\n",
       "- Single inference rule **resolution** which yields complete inference algorithm\n",
       "- Can eliminate complementary literals due to **unit resolution** (only applies to clauses)\n",
       "\n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge-based agents** - reasoning to decide actions, in combination with internal representations\n",
       "* **Knowledge representation language** - group of sentences expressed to represent something about the world\n",
       "* **Axiom** - sentence given without being derived\n",
       "* **Knowledge level** - specify only what the agent knows and its goals\n",
       "* **Model checking** - enumeration of possible models to check where $\\alpha$ is true in all models of $KB$\n",
       "* **Entailment** - sentence A follows logically from another sentence B\n",
       "* **Sound/truth-perserving** - does not make things up, only entailed sentences (highly desirable)\n",
       "* **Completeness** - can derive any sentence it has entailed\n",
       "* **Grounding** - connection between actual environment of an agent and logical reasoning\n",
       "* **Logical equivalence** - sentences are true in same set of models ($\\equiv$)\n",
       "* **Tautology** - valid sentence (necessarily true)\n",
       "* **Satisfiability** - true in some model (SAT) problem\n",
       "* **Modus ponens** - $\\alpha \\implies \\beta, \\alpha$ gives you $\\beta$\n",
       "* **And-elimination** - any conjuncts can be inferred from a conjunction\n",
       "* **Ground resolution theorem** - resolution closure is empty clause if set of clauses is unsatisfiable\n",
       "* **Definite clause** - disjunction of literals where 1 is positive\n",
       "* **Goal clause** - disjunction of literals where 0 are positive\n",
       "* **Horn clause** - disjunction of literals where at most 1 is positive (goal + definite)\n",
       "* **Forward chaining** - progressively using known premises to derive new conclusions - no specific query (data driven reasoning)\n",
       "* **Backward chanining** - progressively works backwards from query - goal directed reasoning\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "LJODXXD8NZvI"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "XIAO - FINAL Template_for CIS521_midterm notes.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
