{
 "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": "7c5cdea4-fab7-49d0-daab-45049c3068af"
   },
   "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": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "8DvZ57A-djo1",
    "outputId": "0fba2813-5f70-45b4-a740-0e496effad3c"
   },
   "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": 2,
   "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": 43,
   "metadata": {
    "id": "Y2NfE1CKxzS-"
   },
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-43-b50782e48ca4>, line 122)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-43-b50782e48ca4>\"\u001b[0;36m, line \u001b[0;32m122\u001b[0m\n\u001b[0;31m    \"consciousness\" : \"awareness of itself, environment, and experience\",\u001b[0m\n\u001b[0m                    ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
    "\n",
    "chapter1_1 = \"\"\"\n",
    "(1)Acting humanly: Alan Turing proposed the Turing test in 1950, which questions “Can a machine think”. \\\n",
    "The computer need four capabilities: natural language processing, knowledge representation, automated reasoning, and machine learning. \\\n",
    "A robot needs computer vision and robotics to pass the Total Turing Test, which requires interaction between objects and human.\\\n",
    "(2)Think humanly: Human think in three ways -> introspection, psychological experiments, and brain imaging. \\\n",
    "(3)Acting rationally: The rational-agent approach has two advantages: more general and more amenable. \\\n",
    "(4)Beneficial machine: value alignment problem: machines’ values and objectives must be aligned with human’s. \\\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",
    "The limits of AI: \\\n",
    "(1)The argument from informality: human behaviors is too complex to be captured by formal rules.\\\n",
    "(2)The argument from disability: “A machine can never do X” (e.g. be kind, resourceful).\\\n",
    "(3)Mathematical Objection: machines are formal systems that are limited by the incompleteness theorem — they cannot establish the truth of \\\n",
    "their own Godel sentence. \\\n",
    "(4)Measuring AI: we should ask whether machines can pass a behavioral test. \\\n",
    "\"\"\"\n",
    "chapter27_2 = \"\"\" \n",
    "Polite convention, Turing: everyone thinks. \\\n",
    "Chinese room, Searle 1990, rejects the polite convention. \\\n",
    "The big question is whether machines can have qualia, which is intrinsic nature of experiences.\\\n",
    "The additional project of making a machine conscious in \\\n",
    "exactly the way humans are is not one that we are equipped to take on. \\\n",
    "\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
    "chapter2_1 = \"\"\" \n",
    "Agent function: map given percept sequence to an action, which is an abstract mathematical description.\\\n",
    "Agent program: agent function will be implemented by an agent program, which is a concrete implementation, running within some \\\n",
    "physical system. \\\n",
    "An agent’s behavior is described by the agent function. \\\n",
    "Example: vacuum-cleaner\n",
    "\"\"\"\n",
    "chapter2_2 = \"\"\"\n",
    "AI stuck with consequentialism, which is evaluating an agent's behavior by its consequences.\\\n",
    "Performance measure evaluates any given sequence of environment states. \\\n",
    "As a general rule, it is better to design performance measures according to what one actually wants to be achieved \\\n",
    "in the environment. \\\n",
    "For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure. \\\n",
    "Omniscient agent: knows the actual outcomes and act accordingly. \\\n",
    "An important part of rationality is information gathering, which is doing actions to modify future percepts. \\\n",
    "The same agent would be irrational under different circumstances. \\\n",
    "A rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge. \\\n",
    "\n",
    "\"\"\"\n",
    "chapter2_3 = \"\"\"\n",
    "PEAS: Performance, Environment, Actuators, Sensors \\\n",
    "Task Environment: \\\n",
    "Fully observable, partially observable, unobservable. \\\n",
    "Single-agent; multiagent: competitive, operative. \\\n",
    "Communication often emerges as a rational behavior in multiagent environments. \\\n",
    "Deterministic, nondeterministic. \\\n",
    "Stochastic: explicitly deals with probabilities; \\\n",
    "nondeterministic: if the possibilities are listed without being quantified. \\\n",
    "Episodic vs. sequential: In sequential environments, on the other hand, the \\\n",
    "current decision could affect all future decisions. \\\n",
    "Static, dynamic, semidynamic .\\\n",
    "Discrete, continuous. \\\n",
    "Known, unknown: In a known environment, the outcomes for all actions are given. \\\n",
    "The hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown. \\ \n",
    "\"\"\"\n",
    "chapter2_4 = \"\"\"\n",
    "agent = architecture + program. \\\n",
    "The agent program takes the current percept as input, and the agent function \\\n",
    "may depend on the entire percept history. \\\n",
    "Four types of agent programs:\\\n",
    "(1)Simple reflex agent: select actions on the basis of the current percept,\\\n",
    "ignoring the rest of the percept history. \\\n",
    "(2)Model-based reflex agents: Updating the internal state information as time goes requires the knowledge about \\\n",
    "“how the world works” (transition model) and information about how the state of the world is reflected in the \\\n",
    "agent’s percepts (sensor model). The transition model and sensor model allow an agent to keep track of the state of \\\n",
    "the world.\\\n",
    "(3)Goal-based agent: As well as a current state description, the agent needs some sort \\\n",
    "of goal information. (e.g. Search and planning). Less efficient, but more flexible.\\\n",
    "(4)Utility-based agents: An agent’s utility function is an internalization of the performance measure. \\\n",
    "This is not the only way to be rational. \\\n",
    "A utility-based agent has many advantages in terms of flexibility and learning. \\\n",
    "Four components of a learning agent: learning element, performance element, critic, and problem generator.\n",
    "learning element: responsible for making improvements; \\\n",
    "performance element: responsible for selecting external actions; \\\n",
    "Critic: tells the learning element how well the agent is doing with respect to a fixed \\\n",
    "performance standard; \\\n",
    "Problem generators: responsible for suggesting actions that will lead to new and informative experiences. \\\n",
    "The structure of agent: \\\n",
    "Atomic representation: each state of the world is indivisible—it has no internal structure. \\\n",
    "Factored representation: splits up each state into a fixed set of variables or attributes, \\\n",
    "each of which can have a value. \\\n",
    "Structured representation: objects such as cows and trucks and their various and varying relationships \\\n",
    "can be described explicitly. \\\n",
    "Localist representation: If there is a one-to-one mapping between concepts and memory locations. \\\n",
    "Distributed representation: if the representation of a concept is spread over many memory locations, \\\n",
    "and each memory location is employed as part of the representation of multiple different concepts. \\\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module1_lecture_notes = \"\"\" \n",
    "When something behavior can best be described as having its own performance measure, \\\n",
    "then we should consider it to be an agent. \\\n",
    "A reflex agent: selects an action based on the current percept. \\\n",
    "A problem-solving agent must plan ahead. \\ \n",
    "Condition–action rule: INTERPRET-INPUT, RULE-MATCH, rule.ACTION\\\n",
    "The agent will work only if the correct decision can be made on the basis \\\n",
    "of just the current percept—that is, only if the environment is fully observable. \\\n",
    "Randomized behavior of the right kind can be rational in some multiagent environments. \\\n",
    "In single-agent environments, randomization is usually not rational. \\\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Definitions of concepts from Module 1.\n",
    "# You can define any bolded term in the textbook, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 20 words long.\n",
    "module1_definitions = {\n",
    "\"agent\" : \"anything that can perceive and act in an environment\",\n",
    "\"rational agent\": \"agent that pursue the best expected outcome\",\n",
    "\"percept\" : \"things that agent sensors perceive\",\n",
    "\"limited rationality\": \"if there is not enough time to do all computations, acting properly.\"\n",
    "\"consciousness\" : \"awareness of itself, environment, and experience\",\n",
    "\"qualia\": \"conscious experience\",\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 86\n",
      "The length in words is 69\n",
      "The length in words is 47\n",
      "The length in words is 41\n",
      "The length in words is 106\n",
      "The length in words is 91\n",
      "The length in words is 380\n"
     ]
    }
   ],
   "source": [
    "print(\"The length in words is\", len(chapter1_1.split(' ')))\n",
    "print(\"The length in words is\", len(chapter27_1.split(' ')))\n",
    "print(\"The length in words is\", len(chapter27_2.split(' ')))\n",
    "print(\"The length in words is\", len(chapter2_1.split(' ')))\n",
    "print(\"The length in words is\", len(chapter2_2.split(' ')))\n",
    "print(\"The length in words is\", len(chapter2_3.split(' ')))\n",
    "print(\"The length in words is\", len(chapter2_4.split(' ')))"
   ]
  },
  {
   "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": 45,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 725
    },
    "id": "gYYeNcdM_maE",
    "outputId": "0caad8dd-ad20-4626-cb91-923d00b0fbab"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       "\n",
       "Acting humanly: Turing Test, Alan Turing 1950, \"Can a Machine think\" natural language processing; knowledge representation; automated reasoning; machine learning. To pass the Total Turing Test, a robot need computer vision and robotics. Think humanly: introspection, psychological experiments, and brain imaging. Acting rationally: advantage to AI: more general and more amenable. AI has focused on the study and construction of agents that do the right thing. Value alignment problem: the values or objectives put into the machine must be aligned with those of the human. \n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       " \n",
       "Argument from informality of behavior: human behavior is far too complex to be captured by any formal set of rules.Disability: a machine can never do X. Machine can't be exacly human. Mathematical Objection: machines are formal systems that are limited by the incompleteness theorem — they cannot establish the truth of their own Godel sentence. Measuring AI: we should ask whether machines can pass a behavioral test. \n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       " \n",
       "Polite convention: everyone thinks. Chinese room, Searle 1990, rejects the polite convention. The big question is whether machines can have qualia. The additional project of making a machine conscious in exactly the way humans are is not one that we are equipped to take on. \n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       " \n",
       "An agent’s behavior is described by the agent function that maps any given percept sequence to an action. The agent function is an abstract mathematical description; the agent program is a concrete implementation, running within some physical system. Example: vacuum-cleaner\n",
       "\n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       "\n",
       "We evaluate an agent’s behavior by its consequences. Performance measure evaluates any given sequence of environment states. As a general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment. For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure. The same agent would be irrational under different circumstances. Rationality does not require omniscience, because the rational choice depends only on the percept sequence to date. A rational agent should be autonomous—it should learn what it can to compensate for partial or incorrect prior knowledge. \n",
       "\n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       "\n",
       "PEAS: Performance, Environment, Actuators, Sensors Fully observable, partially observable, unobservable Single-agent; multiagent: competitive, operative Communication often emerges as a rational behavior in multiagent environments Deterministic, nondeterministic Stochastic: explicitly deals with probabilities; nondeterministic: if the possibilities are listed without being quantified Episodic vs. sequential: In sequential environments, on the other hand, the current decision could affect all future decisions. Static, dynamic, semidynamic Discrete, continuous Known, unknown: In a known environment, the outcomes for all actions are given. The hardest case is partially observable, multiagent, nondeterministic, sequential, dynamic, continuous, and unknown. \\ \n",
       "\n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       "\n",
       "agent = architecture + program. The program we choose has to be one that is appropriate for the architecture.The agent program takes the current percept as input, and the agent function may depend on the entire percept history. Simple reflex agent: select actions on the basis of the current percept,ignoring the rest of the percept history. Model-based reflex agents: Updating the internal state information as time goes requires the knowledge about “how the world works” and information about how the state of the world is reflected in the agent’s percepts. The transition model and sensor model allow an agent to keep track of the state of the world.Goal-based agent: As well as a current state description, the agent needs some sort of goal information that describes situations that are desirable. Less efficient, more flexible. Utility-based agents: An agent’s utility function is essentially an internalization of the performance measure. This is not the only way to be rational. A utility-based agent has many advantages in terms of flexibility and learning. A rational utility-based agent chooses the action that maximizes the expected utility of the action outcomes. We also note that not all utility-based agents are model-based; A model-free agent can learn what action is best in a particular situation without ever learning exactly how that action changes the environment. A learning agent can be divided into four conceptual components: learning element, performance element, critic, and problem generator. learning element: responsible for making improvements; performance element: responsible for selecting external actions; Critic: tells the learning element how well the agent is doing with respect to a fixed performance standard; Problem generators: responsible for suggesting actions that will lead to new and informative experiences. The structure of agent: Atomic representation: each state of the world is indivisible—it has no internal structure. Factored representation: splits up each state into a fixed set of variables or attributes, each of which can have a value. Structured representation: objects such as cows and trucks and their various and varying relationships can be described explicitly. Localist representation: If there is a one-to-one mapping between concepts and memory locations. Distributed representation: if the representation of a concept is spread over many memory locations, and each memory location is employed as part of the representation of multiple different concepts. \n",
       "\n",
       "\n",
       "\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       " \n",
       "When something behavior can best be described as having its own performance measure, then we should consider it to be an agent. A reflex agent: selects an action based on the current percept. A problem-solving agent must plan ahead. \\ \n",
       "Condition–action rule: INTERPRET-INPUT, RULE-MATCH, rule.ACTIONThe agent will work only if the correct decision can be made on the basis of just the current percept—that is, only if the environment is fully observable. Randomized behavior of the right kind can be rational in some multiagent environments. In single-agent environments, randomization is usually not rational. \n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - anything that can perceive and act in an environment\n",
       "* **Rational agent** - agent that pursue the best expected outcome\n",
       "* **Percept** - things that agent sensors perceive\n",
       "* **Consciousness** - awareness of itself, environment, and experience\n",
       "* **Qualia** - conscious experience\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": 46,
   "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",
    "Magic Method: _cmp_: Define ==; \\\n",
    "Iterator Object: Iterators are objects with a __next__() method \\\n",
    "Generator: Generators are iterators. Creating Generators: yield \\\n",
    "Benefit: Less code than writing a standard iterator; \\\n",
    "Maintains local state automatically; \\\n",
    "Values are computed one at a time, as they’re needed; \\\n",
    "Avoids storing the entire sequence in memory; \\\n",
    "Good for aggregating items. One pass; \\\n",
    "Crucial for infinite sequences; \\\n",
    "Bad if you need to inspect the individual values; \\\n",
    "\"\"\"\n",
    "\n",
    "# Each definition should be at most 20 words long.\n",
    "module2_definitions = {\n",
    "\"mutability\" : \"your definition here\",\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 209
    },
    "id": "ydOK__lwWgdp",
    "outputId": "237a5fc3-0d0f-4240-8ebf-655b10675954"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       " \n",
       "Magic Method: _cmp_: Define ==; Iterator Object: Iterators are objects with a __next__() method Generator: Generators are iterators. Creating Generators: yield Benefit: Less code than writing a standard iterator; Maintains local state automatically; Values are computed one at a time, as they’re needed; Avoids storing the entire sequence in memory; Good for aggregating items. One pass; Crucial for infinite sequences; Bad if you need to inspect the individual values; \n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Mutability** - your definition here\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": 48,
   "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",
    "Four phase problem-solving process: Goal formulation, Problem formulation, Search, Execution. \\\n",
    "open-loop system: ignoring the percepts breaks the loop between agent and \\\n",
    "environment.\\\n",
    "A search problem can be defined as: state space, initial state, goal states, \\\n",
    "actions, transition model, action cost function. \\\n",
    "Abstraction: The process of removing detail from a representation. \\\n",
    "\"\"\"\n",
    "chapter3_2 = \"\"\" \n",
    "Example:\\\n",
    "Touring problems, traveling salesperson problem (TSP), VLSI layout, Robot navigation,\\\n",
    "Automatic assembly sequencing (protein design).\\\n",
    "\"\"\"\n",
    "chapter3_3 = \"\"\" \n",
    "A search algorithm: takes a search problem as input and returns a solution, or an indication of failure. \\\n",
    "Best-first Search: we choose a node, n, with minimum value of some evaluation function, f(n). \\\n",
    "We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if \\\n",
    "it does not check. The BEST-FIRST-SEARCH algorithm is a graph search algorithm.\\\n",
    "Evaluate an algorithm’s performance in four ways: Completeness, Cost Optimally, Time Complexity, \\\n",
    "and Space Complexity.\\\n",
    "To be complete, a search algorithm must be systematic in the way it explores an infinite state space, \\\n",
    "making sure it can eventually reach any state that is connected to the initial state. \\\n",
    "d: depth or number of actions in an optimal solution. \\\n",
    "m: the maximum number of actions in any path. \\\n",
    "b: the branching factor or number of successors of a node that need to be considered. \\\n",
    "\n",
    "\"\"\"\n",
    "chapter3_4 = \"\"\"\n",
    "Breadth-first search: implement as a call to BEST-FIRST-SEARCH where the evaluation function f(n)\\\n",
    "is the depth of the node. \\\n",
    "We can do an early goal test, checking whether a node is a solution as soon as it is generated, \\\n",
    "rather than the late goal test that best-first search uses, waiting until a node is popped off \\\n",
    "the queue. \\\n",
    "Dijkstra’s algorithm or uniform-cost search: can be implemented as a call to BEST-FIRST-SEARCH \\\n",
    "with PATH-COST as the evaluation function. Uniform-cost search is complete and is cost-optimal. \\\n",
    "Depth-first search: can be implemented as a call to BEST-FIRST-SEARCH where the evaluation function f \\\n",
    "is the negative of the depth. In cyclic state spaces it can get stuck in an infinite loop. A variant \\\n",
    "of depth-first search called backtracking search uses even less memory. Only one successor is generated \\\n",
    "at a time rather than all successors; each partially expanded node remembers which successor to \\\n",
    "generate next. In addition, successors are generated by modifying the current state description directly \\\n",
    "rather than allocating memory for a brand-new state. \\\n",
    "Depth-limited search: Depth-first search in which we supply a depth limit, l, and treat all nodes at depth l \\\n",
    "as if they had no successors. \\\n",
    "Iterative deepening search: solves the problem of picking a good value for l by trying all values until \\\n",
    "either a solution is found, or the depth-limited search returns the failure value rather than the cutoff value. \\\n",
    "Bidirectional search: simultaneously searches forward from the initial state and backwards from the goal \\\n",
    "state(s), hoping that the two searches will meet. \\\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module3_lecture_notes = \"\"\" \n",
    "Simple reflex agent: selects an action based only on the current percept. \\\n",
    "It ignores the rest of the percept history. \\\n",
    "Problem-solving agent: must plan ahead. It will consider a sequence of actions \\\n",
    "that form a path to a goal state. \\\n",
    "A fixed sequence of actions: if an environment is fully observable, deterministic, \\\n",
    "known environment.\\\n",
    "A branching strategy: if the environments are partially observable or nondeterministic. \\\n",
    "Definition of Search Problem: Initial states, actions, transition model, path cost, \\\n",
    "goal test.\\\n",
    "With n cells, there are n*2n states. \\\n",
    "States do not have parents, children, depth or path cost. \\\n",
    "Failure to detect repeated states can turn a linear problem into an exponential one. \\\n",
    "Solution: Graph Search, simple Mod from tree search, which checks to see if a node has \\\n",
    "been visited before adding to search queue. \\\n",
    "Uninformed search: All non-goal nodes in frontier look equally good. \\\n",
    "Informed search: Some non-goal nodes can be ranked above others. \\\n",
    "BFS: frontier is FIFO (First-In-First-Out) Queue. \\\n",
    "DFS: frontier is LIFO (Last-In-First-Out) Queue. \\\n",
    "Exponential complexity uninformed search problems cannot be solved for any but the smallest \\\n",
    "instances. \\\n",
    "Get the best of both: Depth-limited Search. \\\n",
    "Iterative deepening search: a general strategy to find best depth limit l.\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",
    "\"State space\" : \"the set of all states reachable by initial state\",  \n",
    "\"Path\" : \"a sequence of actions\",\n",
    "\"Frontier\": \"those states that are available for expanding\",\n",
    "\"Priority Queue\" : \"first pop with minimum cost\",\n",
    "\"FIFO queue\" : \"first in first out\",\n",
    "\"LIFO queue\" : \"late in first out\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 474
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "21b42a50-b270-439d-ac74-40c061bf0bde"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       "\n",
       "Four phase problem-solving process: Goal formulation, Problem formulation, Search, Execution. open-loop system: ignoring the percepts breaks the loop between agent and environment.A search problem can be defined as: state space, initial state, goal states, actions, transition model, action cost function. Abstraction: The process of removing detail from a representation. \n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       " \n",
       "Example:Touring problems, traveling salesperson problem (TSP), VLSI layout, Robot navigation,Automatic assembly sequencing (protein design).\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       " \n",
       "A search algorithm: takes a search problem as input and returns a solution, or an indication of failure. Best-first Search: we choose a node, n, with minimum value of some evaluation function, f(n). We call a search algorithm a graph search if it checks for redundant paths and a tree-like search if it does not check. The BEST-FIRST-SEARCH algorithm is a graph search algorithm.Evaluate an algorithm’s performance in four ways: Completeness, Cost Optimally, Time Complexity, and Space Complexity.To be complete, a search algorithm must be systematic in the way it explores an infinite state space, making sure it can eventually reach any state that is connected to the initial state. d: depth or number of actions in an optimal solution. m: the maximum number of actions in any path. b: the branching factor or number of successors of a node that need to be considered. \n",
       "\n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       "\n",
       "Breadth-first search: implement as a call to BEST-FIRST-SEARCH where the evaluation function f(n)is the depth of the node. We can do an early goal test, checking whether a node is a solution as soon as it is generated, rather than the late goal test that best-first search uses, waiting until a node is popped off the queue. Dijkstra’s algorithm or uniform-cost search: can be implemented as a call to BEST-FIRST-SEARCH with PATH-COST as the evaluation function. Uniform-cost search is complete and is cost-optimal. Depth-first search: can be implemented as a call to BEST-FIRST-SEARCH where the evaluation function f is the negative of the depth. In cyclic state spaces it can get stuck in an infinite loop. A variant of depth-first search called backtracking search uses even less memory. Only one successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next. In addition, successors are generated by modifying the current state description directly rather than allocating memory for a brand-new state. Depth-limited search: Depth-first search in which we supply a depth limit, l, and treat all nodes at depth l as if they had no successors. Iterative deepening search: solves the problem of picking a good value for l by trying all values until either a solution is found, or the depth-limited search returns the failure value rather than the cutoff value. Bidirectional search: simultaneously searches forward from the initial state and backwards from the goal state(s), hoping that the two searches will meet. \n",
       "\n",
       "## Module 3 Lecture Notes\n",
       " \n",
       "Simple reflex agent: selects an action based only on the current percept. It ignores the rest of the percept history. Problem-solving agent: must plan ahead. It will consider a sequence of actions that form a path to a goal state. A fixed sequence of actions: if an environment is fully observable, deterministic, known environment.A branching strategy: if the environments are partially observable or nondeterministic. Definition of Search Problem: Initial states, actions, transition model, path cost, goal test.With n cells, there are n*2n states. States do not have parents, children, depth or path cost. Failure to detect repeated states can turn a linear problem into an exponential one. Solution: Graph Search, simple Mod from tree search, which checks to see if a node has been visited before adding to search queue. Uninformed search: All non-goal nodes in frontier look equally good. Informed search: Some non-goal nodes can be ranked above others. BFS: frontier is FIFO (First-In-First-Out) Queue. DFS: frontier is LIFO (Last-In-First-Out) Queue. Exponential complexity uninformed search problems cannot be solved for any but the smallest instances. Get the best of both: Depth-limited Search. Iterative deepening search: a general strategy to find best depth limit l.\n",
       "\n",
       "\n",
       "## Module 3 Definitions\n",
       "* **State space** - the set of all states reachable by initial state\n",
       "* **Path** - a sequence of actions\n",
       "* **Frontier** - those states that are available for expanding\n",
       "* **Priority queue** - first pop with minimum cost\n",
       "* **Fifo queue** - first in first out\n",
       "* **Lifo queue** - late in first out\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": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 50\n",
      "The length in words is 15\n",
      "The length in words is 147\n",
      "The length in words is 254\n"
     ]
    }
   ],
   "source": [
    "print(\"The length in words is\", len(chapter3_1.split(' ')))\n",
    "print(\"The length in words is\", len(chapter3_2.split(' ')))\n",
    "print(\"The length in words is\", len(chapter3_3.split(' ')))\n",
    "print(\"The length in words is\", len(chapter3_4.split(' ')))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WHREsHSSyA-h"
   },
   "source": [
    "#Module 4 - Informed Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "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: a form of best-first search that expands first the node with the lowest h(n)\\\n",
    "value, so the evaluation function f (n) = h(n). \\\n",
    "Greedy best-first graph search is complete in finite state spaces, but not in infinite ones. The \\ \n",
    "worst-case time and space complexity is O(|V |). With a good heuristic function, however, the complexity \\\n",
    "can be reduced substantially, on certain problems reaching O(bm). \\\n",
    "A∗ search: a best-first search that uses the evaluation function f (n) = g(n) + h(n). \\\n",
    "A∗ search is complete. Whether A∗ is cost-optimal depends on certain properties of the heuristic. \\\n",
    "A key property is admissibility: an admissible heuristic is one that never overestimates the cost to reach a goal. \\\n",
    "A∗ search: g(n) + h(n) (W = 1)\\\n",
    "Uniform-cost search: g(n) (W = 0) \\\n",
    "Greedy best-first search: h(n) (W = ∞) \\ \n",
    "Weighted A∗search: g(n)+W×h(n)  (1<W<∞) \\\n",
    "Bidirectional A∗ search is sometimes more efficient than A∗ itself. \\\n",
    "IDA∗ (iterative deepening A∗ search) is an iterative deepening version of A∗, and thus adresses the space complexity issue. \\\n",
    "RBFS (recursive best-first search) and SMA∗ (simplified memory-bounded A∗) are robust, optimal search algorithms that \\\n",
    "use limited amounts of memory; given enough time, they can solve problems for which A∗ runs out of memory. \\\n",
    "Beam search puts a limit on the size of the frontier; that makes it incomplete and suboptimal, but it often \\\n",
    "finds reasonably good solutions and runs faster than complete searches. \\\n",
    "Weighted A∗ search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality. \\\n",
    "\"\"\"\n",
    "chapter3_6 = \"\"\" \n",
    "Two commonly used candidates: \\\n",
    "h1 = the number of misplaced tiles (blank not included). \\\n",
    "h2 = the sum of the distances of the tiles from their goal positions (Manhattan distance)\\\n",
    "One way to characterize the quality of a heuristic is the effective branching factor b∗.\\\n",
    "A well-designed heuristic would have a value of b∗ close to 1, allowing fairly large problems to be solved at reasonable \\\n",
    "computational cost. \\\n",
    "We say h2 dominates h1 if h2(n) >= h1(n). Hence, it is generally better to use a heuristic function with higher values, \\\n",
    "provided it is consistent and that the computation time for the heuristic is not too long. \\\n",
    "A problem with fewer restrictions on the actions is called a relaxed problem. \\\n",
    "h(n) = max{h1(n),...,hk(n)}.  h dominates all of its component heuristics. The only drawback is that h(n) takes longer to compute. \\\n",
    "The performance of heuristic search algorithms depends on the quality of the heuristic function. One can sometimes \\\n",
    "construct good heuristics by relaxing the problem defini- tion, by storing precomputed solution costs for subproblems \\\n",
    "in a pattern database, by defining landmarks, or by learning from experience with the problem class. \\\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module4_lecture_notes = \"\"\" \n",
    "A heuristic function h(n) takes a state n and returns an estimate of \\\n",
    "the distance from n to the goal.\\\n",
    "Greedy best-first search: select node for expansion with minimal evaluation \\\n",
    "function f(n), where f(n) is some function that includes estimate heuristic h(n) \\\n",
    "of the remaining distance to goal. Implement using priority queue. (not optimal) \\\n",
    "A* Search (best-known form of best-first search): avoid expanding paths that are \\\n",
    "already expensive, but expand most promising first. \\\n",
    "f(n)=g(n) + h(n) \\\n",
    "g(n) the actual cost (so far) to reach the node;\\\n",
    "h(n) estimated cost to get from the node to the goal;\\\n",
    "f(n) estimated total cost of path through n to goal. \\\n",
    "A heuristic h(n) is admissible if it never overestimates the cost to reach the goal;\\\n",
    "If h(n) is admissible, A* using Tree Search is optimal. \\\n",
    "A relaxed problem: a problem with fewer restrictions on the actions than the original.\\\n",
    "The cost of an optimal solution to a relaxed problem is an admissible heuristic for \\\n",
    "the original problem. \\\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module4_definitions = {\n",
    "\"strategy\" : \"order of tree expansion\",\n",
    "\"concept\" : \"definition\",    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 252\n",
      "The length in words is 189\n",
      "The length in words is 161\n"
     ]
    }
   ],
   "source": [
    "print(\"The length in words is\", len(chapter3_5.split(' ')))\n",
    "print(\"The length in words is\", len(chapter3_6.split(' ')))\n",
    "print(\"The length in words is\", len(module4_lecture_notes.split(' ')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 341
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "822c50fc-17b3-444f-d7dd-83cdfb49f6d9"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       "\n",
       "Greedy best-first search: a form of best-first search that expands first the node with the lowest h(n)value, so the evaluation function f (n) = h(n). Greedy best-first graph search is complete in finite state spaces, but not in infinite ones. The \\ \n",
       "worst-case time and space complexity is O(|V |). With a good heuristic function, however, the complexity can be reduced substantially, on certain problems reaching O(bm). A∗ search: a best-first search that uses the evaluation function f (n) = g(n) + h(n). A∗ search is complete. Whether A∗ is cost-optimal depends on certain properties of the heuristic. A key property is admissibility: an admissible heuristic is one that never overestimates the cost to reach a goal. A∗ search: g(n) + h(n) (W = 1)Uniform-cost search: g(n) (W = 0) Greedy best-first search: h(n) (W = ∞) \\ \n",
       "Weighted A∗search: g(n)+W×h(n)  (1<W<∞) Bidirectional A∗ search is sometimes more efficient than A∗ itself. IDA∗ (iterative deepening A∗ search) is an iterative deepening version of A∗, and thus adresses the space complexity issue. RBFS (recursive best-first search) and SMA∗ (simplified memory-bounded A∗) are robust, optimal search algorithms that use limited amounts of memory; given enough time, they can solve problems for which A∗ runs out of memory. Beam search puts a limit on the size of the frontier; that makes it incomplete and suboptimal, but it often finds reasonably good solutions and runs faster than complete searches. Weighted A∗ search focuses the search towards a goal, expanding fewer nodes, but sacrificing optimality. \n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       " \n",
       "Two commonly used candidates: h1 = the number of misplaced tiles (blank not included). h2 = the sum of the distances of the tiles from their goal positions (Manhattan distance)One way to characterize the quality of a heuristic is the effective branching factor b∗.A well-designed heuristic would have a value of b∗ close to 1, allowing fairly large problems to be solved at reasonable computational cost. We say h2 dominates h1 if h2(n) >= h1(n). Hence, it is generally better to use a heuristic function with higher values, provided it is consistent and that the computation time for the heuristic is not too long. A problem with fewer restrictions on the actions is called a relaxed problem. h(n) = max{h1(n),...,hk(n)}.  h dominates all of its component heuristics. The only drawback is that h(n) takes longer to compute. The performance of heuristic search algorithms depends on the quality of the heuristic function. One can sometimes construct good heuristics by relaxing the problem defini- tion, by storing precomputed solution costs for subproblems in a pattern database, by defining landmarks, or by learning from experience with the problem class. \n",
       "\n",
       "\n",
       "## Module 4 Lecture Notes\n",
       " \n",
       "Simple reflex agent: selects an action based only on the current percept. It ignores the rest of the percept history. Problem-solving agent: must plan ahead. It will consider a sequence of actions that form a path to a goal state. A fixed sequence of actions: if an environment is fully observable, deterministic, known environment.A branching strategy: if the environments are partially observable or nondeterministic. Definition of Search Problem: Initial states, actions, transition model, path cost, goal test.With n cells, there are n*2n states. States do not have parents, children, depth or path cost. Failure to detect repeated states can turn a linear problem into an exponential one. Solution: Graph Search, simple Mod from tree search, which checks to see if a node has been visited before adding to search queue. Uninformed search: All non-goal nodes in frontier look equally good. Informed search: Some non-goal nodes can be ranked above others. BFS: frontier is FIFO (First-In-First-Out) Queue. DFS: frontier is LIFO (Last-In-First-Out) Queue. Exponential complexity uninformed search problems cannot be solved for any but the smallest instances. Get the best of both: Depth-limited Search. Iterative deepening search: a general strategy to find best depth limit l.\n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Strategy** - order of tree expansion\n",
       "* **Concept** - definition\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\", module3_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": 54,
   "metadata": {
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
    "chapter5_1 = \"\"\" \n",
    "Two-player zero-sum games: deterministic, two-player, turn-taking, perfect information \\\n",
    "(fully observable), zero-sum games (what is good for one player is just as bad for the \\\n",
    "other). \\\n",
    "move as a synonym for “action” and position as a synonym for “state.” Complete game tree: \\\n",
    "a search tree that follows every sequence of moves all the way to a terminal state. \\\n",
    "\"\"\"\n",
    "chapter5_2 = \"\"\" \n",
    "The minimax value is the utility (for MAX) of being in that state, assuming that both \\\n",
    "players play optimally from there to the end of the game. \\\n",
    "The minimax algorithm performs a complete depth-first exploration of the game tree. \\\n",
    "If the maximum depth of the tree is m and there are b legal moves at each point, then \\\n",
    "the time complexity of the minimax algorithm is O(bm). The space complexity is O(bm) for \\\n",
    "an algorithm that generates all actions at once, or O(m) for an algorithm that generates \\\n",
    "actions one at a time. \\\n",
    "The number of game states is exponential in the depth of the tree. we can sometimes cut it \\\n",
    "in half, computing the correct minimax decision without examining every state by pruning \\\n",
    "large parts of the tree that make no difference to the outcome. The particular technique we \\\n",
    "examine is called alpha–beta pruning. \\\n",
    "The effectiveness of alpha–beta pruning is highly dependent on the order in which the states \\\n",
    "are examined. It might be worthwhile to try to first examine the successors that are likely \\\n",
    "to be best. If this could be done perfectly, alpha–beta would need to examine only O(b^m/2) \\\n",
    "nodes to pick the best move, instead of O(b^m) for minimax. \\\n",
    "\"\"\"\n",
    "\n",
    "chapter5_3 = \"\"\"\n",
    "Heuristic Alpha-Beta Search: we replace the UTILITY function with EVAL, which \\\n",
    "estimates a state’s utility. We also replace the terminal test by a cutoff test, which must \\\n",
    "return true for terminal states, but is otherwise free to decide when to cut off the search, \\\n",
    "based on the search depth and any property of the state that it chooses to consider. \\\n",
    "A heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of \\\n",
    "state s to player p. For terminal states, it must be that EVAL(s,p)=UTILITY(s,p) and for \\\n",
    "nonterminal states, the evaluation must be somewhere between a loss and a win: \\\n",
    "UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p). \\\n",
    "weighted linear function: EVAL(s) = w1 f1(s)+w2 f2(s)+···+wn fn(s) = ∑wi fi(s)\\\n",
    "Cutting off: replace the two lines in IS-TERMINAL with if game.IS-CUTOFF(state, depth) then \\\n",
    "return game.EVAL(state, player), null \"\"\"\n",
    "\n",
    "chapter5_5 = \"\"\"\n",
    "Stochastic games bring us a little closer to the unpredictability of real life\\ \n",
    "by including a random element. \\\n",
    "Games of chance can be handled by expectiminimax, an extension to the minimax algorithm that \\\n",
    "evaluates a chance node by taking the average utility of all its children, weighted by the \\\n",
    "probability of each child. \\\n",
    "A game tree in backgammon must include chance nodes in addition to MAX and MIN nodes. \\\n",
    "Positions do not have definite minimax values. So we can only calculate the expected value of \\\n",
    "a position: the average over all possible outcomes of the chance nodes. This leads us to the \\\n",
    "expectiminimax value for games with chance nodes, a generalization of the minimax value for \\\n",
    "deterministic games. Terminal nodes and MAX and MIN nodes work exactly the same way as before. \\\n",
    "The evaluation function must return values that are a positive linear transformation of the \\\n",
    "probability of winning. \\\n",
    "In minimax, O(b^m), where b is the branching factor and m is the maximum depth of the game tree. \\\n",
    "Because expectiminimax is also considering all the possible dice-roll sequences, it will take O(b^m n^m), \\\n",
    "where n is the number of distinct rolls. \"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
    "chapter16_1 = \"\"\" \n",
    "Probability theory describes what an agent should believe on the basis of evidence, utility theory\\\n",
    "describes what an agent wants, and decision theory puts the two together to describe what an agent \\\n",
    "should do. \\\n",
    "We can use decision theory to build a system that makes decisions by considering all possible actions \\\n",
    "and choosing the one that leads to the best expected outcome. Such a system is known as a rational agent. \\\n",
    "We’ll assume that the agent assigns a probability P(s) to each possible current state s. There may also \\\n",
    "be uncertainty about the action outcomes; the transition model is given by P(s′|s,a), the probability that \\\n",
    "action a in state s reaches state s′. P(RESULT(a)=s′), the probability of reaching s′ by doing a in the \\\n",
    "current state, whatever that is. P(RESULT(a)=s′) = ∑P(s)P(s′ |s,a). \\\n",
    "Utility function, U (s), which assigns a single number to express the desirability of a state. \\\n",
    "The expected utility of an action given the evidence, EU(a), is just the average utility value of the outcomes,\\\n",
    "weighted by the probability that the outcome occurs: EU(a) = ∑P(RESULT(a)=s′)U(s′). \\\n",
    "The principle of maximum expected utility (MEU) says that a rational agent should choose the action that\\\n",
    "maximizes the agent’s expected utility: action = argmax EU(a). \\\n",
    "If an agent acts so as to maximize a utility function that correctly reflects the performance measure, \\\n",
    "then the agent will achieve the highest possible performance score (averaged over all the possible environments).\\\n",
    "\"\"\"\n",
    "\n",
    "chapter16_2 = \"\"\" \n",
    "Six constraints that we require any reasonable preference relation to obey: \\\n",
    "(1)Orderability: Exactlyoneof(A≻B),(B≻A), or(A∼B)holds. \\\n",
    "(2)Transitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must \\\n",
    "prefer A to C. (A≻B)∧(B≻C) ⇒ (A≻C). \\\n",
    "(3)Continuity: If some lottery B is between A and C in preference, then there is some probability p for which \\\n",
    "the rational agent will be indifferent between getting B for sure and the lottery that yields A with \\\n",
    "probability p and C with probability 1 − p. A≻B≻C ⇒ ∃p [p,A; 1−p,C]∼B. \\\n",
    "(4)Substitutability: If an agent is indifferent between two lotteries A and B, then the agent is indifferent \\\n",
    "between two more complex lotteries that are the same except that B is substituted for A in one of them. \\\n",
    "This holds regardless of the probabilities and the other outcome(s) in the lotteries. \\\n",
    "A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B;1− p,C]. \\\n",
    "(5)Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A \\\n",
    "to B, then the agent must prefer the lottery that has a higher probability for A (and vice versa). \\\n",
    "A≻B ⇒ (p>q ⇔ [p,A; 1−p,B]≻[q,A; 1−q,B]). \n",
    "(6)Decomposability: Compound lotteries can be reduced to simpler ones using the laws of probability. \\ \n",
    "[p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C]. \\\n",
    "These constraints are known as the axioms of utility theory. \\\n",
    "\"\"\"\n",
    "chapter16_3 = \"\"\" \n",
    "preference elicitation: presenting choices to the human and using the observed \\\n",
    "preferences to pin down the underlying utility function. \\\n",
    "The agent exhibits a monotonic preference for more money. \\\n",
    "Decision theory is a normative theory: it describes how a rational agent should act. \\\n",
    "A descriptive theory, on the other hand, describes how actual agents—for example, \\\n",
    "humans— really do act. \"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module5_lecture_notes = \"\"\"\n",
    "The simple game environment: multiagent, static, discrete, fully observable, \\\n",
    "stragetic. \\\n",
    "Game as search: initial state, successor function, terminal test, utility \\\n",
    "function. \\\n",
    "Game Tree: Nodes represent ‘board positions’; edges represent legal moves.\\\n",
    "Adversarial Search: \\\n",
    "evaluation function: Zero-sum assumption lets us use one function to describe \\\n",
    "goodness for both players. \\\n",
    "Minimax: Make the best move for MAX assuming that MIN always replies with the \\\n",
    "best move for MIN. \\\n",
    "def max_value(state):\\\n",
    "   if terminal: \\\n",
    "       return utility \\\n",
    "    v = - infinity \\\n",
    "    for each successor in state: \\\n",
    "        v = max(v, min-value(successor)) \\\n",
    "def min_value(state):\\\n",
    "   if terminal: \\\n",
    "       return utility \\\n",
    "    v = infinity \\\n",
    "    for each successor in state: \\\n",
    "        v = min(v, max-value(successor)) \\\n",
    "Alpha-beta pruning: During Minimax, keep track of two additional values: \\\n",
    "alpha -> MAX’s current lower bound on MAX’s outcome. \\\n",
    "beta -> MIN’s current upper bound on MIN’s outcome. \\\n",
    "Expectimax: Uncertain outcomes controlled by chance, not an adversary! \\\n",
    "Expectimax Search: compute the average score under optimal play. \\\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module5_definitions = {\n",
    "\"random variable\" : \"an event with unknown outcome\",    \n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 59\n",
      "The length in words is 205\n",
      "The length in words is 139\n",
      "The length in words is 192\n",
      "The length in words is 236\n",
      "The length in words is 235\n",
      "The length in words is 60\n",
      "The length in words is 199\n"
     ]
    }
   ],
   "source": [
    "print(\"The length in words is\", len(chapter5_1.split(' ')))\n",
    "print(\"The length in words is\", len(chapter5_2.split(' ')))\n",
    "print(\"The length in words is\", len(chapter5_3.split(' ')))\n",
    "print(\"The length in words is\", len(chapter5_5.split(' ')))\n",
    "print(\"The length in words is\", len(chapter16_1.split(' ')))\n",
    "print(\"The length in words is\", len(chapter16_2.split(' ')))\n",
    "print(\"The length in words is\", len(chapter16_3.split(' ')))\n",
    "print(\"The length in words is\", len(module5_lecture_notes.split(' ')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 674
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "e9f5458e-82b4-4fa5-c56a-a0748aba7eaf"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       " \n",
       "Two-player zero-sum games: deterministic, two-player, turn-taking, perfect information (fully observable), zero-sum games (what is good for one player is just as bad for the other). move as a synonym for “action” and position as a synonym for “state.” Complete game tree: a search tree that follows every sequence of moves all the way to a terminal state. \n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       " \n",
       "The minimax value is the utility (for MAX) of being in that state, assuming that both players play optimally from there to the end of the game. The minimax algorithm performs a complete depth-first exploration of the game tree. If the maximum depth of the tree is m and there are b legal moves at each point, then the time complexity of the minimax algorithm is O(bm). The space complexity is O(bm) for an algorithm that generates all actions at once, or O(m) for an algorithm that generates actions one at a time. The number of game states is exponential in the depth of the tree. we can sometimes cut it in half, computing the correct minimax decision without examining every state by pruning large parts of the tree that make no difference to the outcome. The particular technique we examine is called alpha–beta pruning. The effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. It might be worthwhile to try to first examine the successors that are likely to be best. If this could be done perfectly, alpha–beta would need to examine only O(b^m/2) nodes to pick the best move, instead of O(b^m) for minimax. \n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       "\n",
       "Heuristic Alpha-Beta Search: we replace the UTILITY function with EVAL, which estimates a state’s utility. We also replace the terminal test by a cutoff test, which must return true for terminal states, but is otherwise free to decide when to cut off the search, based on the search depth and any property of the state that it chooses to consider. A heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state s to player p. For terminal states, it must be that EVAL(s,p)=UTILITY(s,p) and for nonterminal states, the evaluation must be somewhere between a loss and a win: UTILITY(loss, p) ≤ EVAL(s, p) ≤ UTILITY(win, p). weighted linear function: EVAL(s) = w1 f1(s)+w2 f2(s)+···+wn fn(s) = ∑wi fi(s)Cutting off: replace the two lines in IS-TERMINAL with if game.IS-CUTOFF(state, depth) then return game.EVAL(state, player), null \n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       "\n",
       "Stochastic games bring us a little closer to the unpredictability of real life\\ \n",
       "by including a random element. Games of chance can be handled by expectiminimax, an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children, weighted by the probability of each child. A game tree in backgammon must include chance nodes in addition to MAX and MIN nodes. Positions do not have definite minimax values. So we can only calculate the expected value of a position: the average over all possible outcomes of the chance nodes. This leads us to the expectiminimax value for games with chance nodes, a generalization of the minimax value for deterministic games. Terminal nodes and MAX and MIN nodes work exactly the same way as before. The evaluation function must return values that are a positive linear transformation of the probability of winning. In minimax, O(b^m), where b is the branching factor and m is the maximum depth of the game tree. Because expectiminimax is also considering all the possible dice-roll sequences, it will take O(b^m n^m), where n is the number of distinct rolls. \n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " \n",
       "Probability theory describes what an agent should believe on the basis of evidence, utility theorydescribes what an agent wants, and decision theory puts the two together to describe what an agent should do. We can use decision theory to build a system that makes decisions by considering all possible actions and choosing the one that leads to the best expected outcome. Such a system is known as a rational agent. We’ll assume that the agent assigns a probability P(s) to each possible current state s. There may also be uncertainty about the action outcomes; the transition model is given by P(s′|s,a), the probability that action a in state s reaches state s′. P(RESULT(a)=s′), the probability of reaching s′ by doing a in the current state, whatever that is. P(RESULT(a)=s′) = ∑P(s)P(s′ |s,a). Utility function, U (s), which assigns a single number to express the desirability of a state. The expected utility of an action given the evidence, EU(a), is just the average utility value of the outcomes,weighted by the probability that the outcome occurs: EU(a) = ∑P(RESULT(a)=s′)U(s′). The principle of maximum expected utility (MEU) says that a rational agent should choose the action thatmaximizes the agent’s expected utility: action = argmax EU(a). If an agent acts so as to maximize a utility function that correctly reflects the performance measure, then the agent will achieve the highest possible performance score (averaged over all the possible environments).\n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " \n",
       "Six constraints that we require any reasonable preference relation to obey: (1)Orderability: Exactlyoneof(A≻B),(B≻A), or(A∼B)holds. (2)Transitivity: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C. (A≻B)∧(B≻C) ⇒ (A≻C). (3)Continuity: If some lottery B is between A and C in preference, then there is some probability p for which the rational agent will be indifferent between getting B for sure and the lottery that yields A with probability p and C with probability 1 − p. A≻B≻C ⇒ ∃p [p,A; 1−p,C]∼B. (4)Substitutability: If an agent is indifferent between two lotteries A and B, then the agent is indifferent between two more complex lotteries that are the same except that B is substituted for A in one of them. This holds regardless of the probabilities and the other outcome(s) in the lotteries. A ∼ B ⇒ [p,A; 1− p,C] ∼ [p,B;1− p,C]. (5)Monotonicity: Suppose two lotteries have the same two possible outcomes, A and B. If an agent prefers A to B, then the agent must prefer the lottery that has a higher probability for A (and vice versa). A≻B ⇒ (p>q ⇔ [p,A; 1−p,B]≻[q,A; 1−q,B]). \n",
       "(6)Decomposability: Compound lotteries can be reduced to simpler ones using the laws of probability. \\ \n",
       "[p,A; 1− p,[q,B; 1−q,C]] ∼ [p,A; (1− p)q,B; (1− p)(1−q),C]. These constraints are known as the axioms of utility theory. \n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       " \n",
       "preference elicitation: presenting choices to the human and using the observed preferences to pin down the underlying utility function. The agent exhibits a monotonic preference for more money. Decision theory is a normative theory: it describes how a rational agent should act. A descriptive theory, on the other hand, describes how actual agents—for example, humans— really do act. \n",
       "\n",
       "## Module 5 Lecture Notes\n",
       "\n",
       "The simple game environment: multiagent, static, discrete, fully observable, stragetic. Game as search: initial state, successor function, terminal test, utility function. Game Tree: Nodes represent ‘board positions’; edges represent legal moves.Adversarial Search: evaluation function: Zero-sum assumption lets us use one function to describe goodness for both players. Minimax: Make the best move for MAX assuming that MIN always replies with the best move for MIN. def max_value(state):   if terminal:        return utility     v = - infinity     for each successor in state:         v = max(v, min-value(successor)) def min_value(state):   if terminal:        return utility     v = infinity     for each successor in state:         v = min(v, max-value(successor)) Alpha-beta pruning: During Minimax, keep track of two additional values: alpha -> MAX’s current lower bound on MAX’s outcome. beta -> MIN’s current upper bound on MIN’s outcome. Expectimax: Uncertain outcomes controlled by chance, not an adversary! Expectimax Search: compute the average score under optimal play. \n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Random variable** - an event with unknown outcome\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": 57,
   "metadata": {
    "id": "Wm4mfW82yaRH"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
    "chapter6_1 = \"\"\" \n",
    "Factored representation for each state: a set of variables, each of which has a value. \\\n",
    "CSP: A problem is solved when each variable has a value that satisfies all the constraints \\\n",
    "on the variable. \\\n",
    "CSP search algorithms take advantage: 1) use general rather than domain-specific heuristics \\\n",
    "to enable the solution of complex problems. 2) the actions and transition model can be \\\n",
    "deduced from the problem description. \\\n",
    "A constraint satisfaction problem consists of three components, X,D, and C: \\\n",
    "X is a set of variables, {X1,...,Xn}.\\\n",
    "D is a set of domains, {D1,...,Dn}, one for each variable.\\\n",
    "C is a set of constraints that specify allowable combinations of values. \\\n",
    "CSPs deal with assignments of values to variables, {Xi = vi , Xj = vj , ...}. \\\n",
    "An assignment that does not violate any constraints is called a consistent or legal \\\n",
    "assignment. A complete assignment is one in which every variable is assigned a value, \\\n",
    "and a solution to a CSP is a consistent, complete assignment. \\\n",
    "Precedence constraints: Whenever a task T1 must occur before task T2, and task T1 takes \\\n",
    "duration d1 to complete -> T1 + d1 ≤ T2 .\\\n",
    "Disjunctive constraint: e.g. must to overlap in time -> using or.\\\n",
    "The simplest kind of CSP involves variables that have discrete, finite domains. \\\n",
    "e.g. map-coloring, 8-queens problem.\\\n",
    "A discrete domain can be infinite, such as the set of integers or strings. \\\n",
    "With infinite domains, we must use implicit constraints like T1 + d1 ≤ T2 rather than \\\n",
    "explicit tuples of values. \\\n",
    "Constraint satisfaction problems with continuous domains are common in the real world. \\\n",
    "The best-known category of continuous-domain CSPs is that of linear programming problems, \\\n",
    "where constraints must be linear equalities or inequalities. \\\n",
    "Unary constrain: restricts the value of a single variable. \\\n",
    "Binary constraint: relates two variables. A binary CSP is one with only unary and \\\n",
    "binary constraints; it can be represented as a constraint graph.\\\n",
    "Global constraint: a constraint involving an arbitrary number of variables.\\\n",
    "Many real-world CSPs include preference constraints indicating which solutions are preferred. \\\n",
    "Constrained optimization problem: CSPs with preferences can be solved with optimization \\\n",
    "search methods, either path-based or local. \\\n",
    "\"\"\"\n",
    "chapter6_2 = \"\"\" \n",
    "A CSP algorithm has choices. It can generate successors by choosing a new variable \\\n",
    "assignment, or it can do a specific type of inference called constraint propagation: \\\n",
    "using the constraints to reduce the number of legal values for a variable, which in turn \\\n",
    "can reduce the legal values for another variable. \\\n",
    "Node consistency: A single variable is node-consistent if all the values in the variable’s \\\n",
    "domain satisfy the variable’s unary constraints. \\\n",
    "A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s \\\n",
    "binary constraints. \\\n",
    "The most popular algorithm for enforcing arc consistency is called AC-3. \\\n",
    "To make every variable arc-consistent, the AC-3 algorithm maintains a queue of arcs to \\\n",
    "consider. Initially, the queue contains all the arcs in the CSP. AC-3 then pops off an \\\n",
    "arbitrary arc (Xi,Xj) from the queue and makes Xi arc-consistent with respect to Xj. \\\n",
    "If this leaves Di unchanged, the algorithm just moves on to the next arc. But if this revises\\\n",
    "Di, then we add to the queue all arcs (Xk,Xi) where Xk is a neighbor of Xi. \\\n",
    "Assume a CSP with n variables, each with domain size at most d, and with c binary constraints\\\n",
    "(arcs). Each arc (Xk,Xi) can be inserted in the queue only d times because Xi has at most \\\n",
    "d values to delete. Checking consistency of an arc can be done in O(d^2) time, \\\n",
    "so we get O(cd^3) total worst-case time. \n",
    "Arc consistency tightens down the domains (unary constraints) using the arcs \\\n",
    "(binary constraints). Path consistency tightens the binary constraints by using implicit \\\n",
    "constraints that are inferred by looking at triples of variables. \\\n",
    "A CSP is k- consistent if, for any set of k − 1 variables and for any consistent assignment \\\n",
    "to those variables, a consistent value can always be assigned to any kth variable. The total \\\n",
    "run time is only O(n^2d). \\\n",
    "\"\"\"\n",
    "chapter6_3 = \"\"\"Commutativity is a crucial property of CSPs. A problem is commutative if the \\\n",
    "order of application of any given set of actions does not matter. \\\n",
    "Minimum-remaining-values (MRV)/most constrained variable heuristic: choosing the variable \\\n",
    "with the fewest “legal” values.\\\n",
    "The least-constraining-value heuristic is effective for deciding on the order in which to \\\n",
    "examine its values. It prefers the value that rules out the fewest choices for the neighboring \\\n",
    "variables in the constraint graph.\\\n",
    "Forward checking: Whenever a variable X is assigned, the forward-checking process establishes \\\n",
    "arc consistency for it: for each unassigned variable Y that is connected to X by a constraint,\\\n",
    "delete from Y ’s domain any value that is inconsistent with the value chosen for X. \\\n",
    "Chronological backtracking: when a branch of the search fails: back up to the preceding \\\n",
    "variable and try a different value for it. \\\n",
    "Constraint learning is the idea of finding a minimum set of variables from the conflict set \\\n",
    "that causes the problem. This set of variables, along with their corresponding values, \\\n",
    "is called a no-good. \\\n",
    "\"\"\"\n",
    "chapter6_4 = \"\"\" \n",
    "Local search using the min-conflicts heuristic has also been applied to constraint \\\n",
    "satisfaction problems with great success. \\\n",
    "Min-conflicts heuristic: select the value that results in the minimum number of conflicts \\\n",
    "with other variables—the min-conflicts heuristic. \\\n",
    "The run time of min-conflicts is roughly independent of problem size. \\\n",
    "Constraint weighting: aims to concentrate the search on the important constraints. Each \\\n",
    "constraint is given a numeric weight, initially all 1. At each step of the search, \\\n",
    "the algorithm chooses a variable/value pair to change that will result in the lowest total \\\n",
    "weight of all violated constraints. \\\n",
    "Another advantage of local search is that it can be used in an online setting when the \\\n",
    "problem changes. \\\n",
    "\"\"\"\n",
    "chapter6_5 = \"\"\" A constraint graph is a tree when any two variables are connected by \\\n",
    "only one path. Any tree-structured CSP can be solved in time linear in the number of \\\n",
    "variables. \\\n",
    "A CSP is defined to be directional arc-consistent under an ordering of variables \\\n",
    "X1,X2,...,Xn if and only if every Xi is arc- consistent with each X j for j > i. \\\n",
    "To solve a tree-structured CSP, first pick any variable to be the root of the tree, \\\n",
    "and choose an ordering of the variables such that each variable appears after its parent \\\n",
    "in the tree. Such an ordering is called a topological sort. \\\n",
    "Cutset conditioning can reduce a general CSP to a tree-structured one and is quite efficient \\\n",
    "(requiring only linear memory) if a small cutset can be found. Tree decomposition \\\n",
    "techniques transform the CSP into a tree of subproblems and are efficient if the tree\\\n",
    "width of the constraint graph is small; however they need memory exponential in the tree \\\n",
    "width of the constraint graph. Combining cutset conditioning with tree decomposition can \\\n",
    "allow a better tradeoff of memory versus time. \\\n",
    " \"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module6_lecture_notes = \"\"\" \n",
    "Assumptions: a single agent, deterministic actions, fully observed state, discrete \\\n",
    "state space.\\\n",
    "Planning: sequences of actions. \\\n",
    "Represent the constraints that solutions must satisfy in a uniform declarative language.\\\n",
    "A CSP consists of: finite set of variables, nonempty domain of possible values, finite \\\n",
    "set of constraints. \\\n",
    "A solution to a CSP is a complete, consistent assignment. Solutions to CSPs can be found \\\n",
    "by a completely general purpose algorithm, given only the formal specification of the CSP.\\\n",
    "Applications: Map coloring, scheduling problem, Sudoku. \\\n",
    "Benefits: Clean specification of many problems, generic goal, successor function and \\\n",
    "heuristics; “knows” which variables violate a constraint; Automatically prune off all \\\n",
    "branches that violate constraints. \\\n",
    "CSP as a search problem: initial state, successor function, goal state, path cost. \\\n",
    "Solution is always found at depth n, for n variables. Tree has n!*dn leaves.\\\n",
    "Backtracking Search: DFS for CSP with single-variable assignments. \\\n",
    "Heuristic: most constrained variable (fewest legal move), \\\n",
    "most constraining variable (most constraints on remaining variables), \\\n",
    "least constraining value (choose the least constraining value), \\\n",
    "forward checking (Keep track of remaining legal values for unassigned \\\n",
    "variables. Terminate search when any unassigned variable has no remaining \\\n",
    "legal values).\\\n",
    "Arc consistency: X->Y is consistent iff for every value x of X there is some allowed y. \\\n",
    "Given d values, checking arc (i,j) takes O(d^2) time worst case \\\n",
    "AC-3: \\\n",
    "function AC3 return the CSP:\\\n",
    "while queue is not empty:\\\n",
    "(Xi, Xj) <- queue.pop() \\\n",
    "if REMOVE-INCONSISTENT(Xi,Xj) then\\\n",
    "for each Xk in NEIGHBORS[Xi] - {Xj}:\\\n",
    "add (Xk, Xi) to queue\\\n",
    "function REMOVE-INCONSISTENT (Xi, Xj) return true iff we remove a value:\\\n",
    "removed <- false \\\n",
    "for each x in DOMAIN[Xi]:\n",
    "if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj \\\n",
    "delete x from DOMAIN[Xi] \\\n",
    "removed = True \\\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module6_definitions = {\n",
    "\"concept\" : \"definition\",    \n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 348\n",
      "The length in words is 309\n",
      "The length in words is 170\n",
      "The length in words is 114\n",
      "The length in words is 183\n",
      "The length in words is 277\n"
     ]
    }
   ],
   "source": [
    "print(\"The length in words is\", len(chapter6_1.split(' ')))\n",
    "print(\"The length in words is\", len(chapter6_2.split(' ')))\n",
    "print(\"The length in words is\", len(chapter6_3.split(' ')))\n",
    "print(\"The length in words is\", len(chapter6_4.split(' ')))\n",
    "print(\"The length in words is\", len(chapter6_5.split(' ')))\n",
    "print(\"The length in words is\", len(module6_lecture_notes.split(' ')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 541
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "f51aeef3-74ac-4ec6-b389-54aae53b8cbc"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       " \n",
       "Factored representation for each state: a set of variables, each of which has a value. CSP: A problem is solved when each variable has a value that satisfies all the constraints on the variable. CSP search algorithms take advantage: 1) use general rather than domain-specific heuristics to enable the solution of complex problems. 2) the actions and transition model can be deduced from the problem description. A constraint satisfaction problem consists of three components, X,D, and C: X is a set of variables, {X1,...,Xn}.D is a set of domains, {D1,...,Dn}, one for each variable.C is a set of constraints that specify allowable combinations of values. CSPs deal with assignments of values to variables, {Xi = vi , Xj = vj , ...}. An assignment that does not violate any constraints is called a consistent or legal assignment. A complete assignment is one in which every variable is assigned a value, and a solution to a CSP is a consistent, complete assignment. Precedence constraints: Whenever a task T1 must occur before task T2, and task T1 takes duration d1 to complete -> T1 + d1 ≤ T2 .Disjunctive constraint: e.g. must to overlap in time -> using or.The simplest kind of CSP involves variables that have discrete, finite domains. e.g. map-coloring, 8-queens problem.A discrete domain can be infinite, such as the set of integers or strings. With infinite domains, we must use implicit constraints like T1 + d1 ≤ T2 rather than explicit tuples of values. Constraint satisfaction problems with continuous domains are common in the real world. The best-known category of continuous-domain CSPs is that of linear programming problems, where constraints must be linear equalities or inequalities. Unary constrain: restricts the value of a single variable. Binary constraint: relates two variables. A binary CSP is one with only unary and binary constraints; it can be represented as a constraint graph.Global constraint: a constraint involving an arbitrary number of variables.Many real-world CSPs include preference constraints indicating which solutions are preferred. Constrained optimization problem: CSPs with preferences can be solved with optimization search methods, either path-based or local. \n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       " \n",
       "A CSP algorithm has choices. It can generate successors by choosing a new variable assignment, or it can do a specific type of inference called constraint propagation: using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable. Node consistency: A single variable is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints. A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints. The most popular algorithm for enforcing arc consistency is called AC-3. To make every variable arc-consistent, the AC-3 algorithm maintains a queue of arcs to consider. Initially, the queue contains all the arcs in the CSP. AC-3 then pops off an arbitrary arc (Xi,Xj) from the queue and makes Xi arc-consistent with respect to Xj. If this leaves Di unchanged, the algorithm just moves on to the next arc. But if this revisesDi, then we add to the queue all arcs (Xk,Xi) where Xk is a neighbor of Xi. Assume a CSP with n variables, each with domain size at most d, and with c binary constraints(arcs). Each arc (Xk,Xi) can be inserted in the queue only d times because Xi has at most d values to delete. Checking consistency of an arc can be done in O(d^2) time, so we get O(cd^3) total worst-case time. \n",
       "Arc consistency tightens down the domains (unary constraints) using the arcs (binary constraints). Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables. A CSP is k- consistent if, for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable. The total run time is only O(n^2d). \n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       "Commutativity is a crucial property of CSPs. A problem is commutative if the order of application of any given set of actions does not matter. Minimum-remaining-values (MRV)/most constrained variable heuristic: choosing the variable with the fewest “legal” values.The least-constraining-value heuristic is effective for deciding on the order in which to examine its values. It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.Forward checking: Whenever a variable X is assigned, the forward-checking process establishes arc consistency for it: for each unassigned variable Y that is connected to X by a constraint,delete from Y ’s domain any value that is inconsistent with the value chosen for X. Chronological backtracking: when a branch of the search fails: back up to the preceding variable and try a different value for it. Constraint learning is the idea of finding a minimum set of variables from the conflict set that causes the problem. This set of variables, along with their corresponding values, is called a no-good. \n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       " \n",
       "Local search using the min-conflicts heuristic has also been applied to constraint satisfaction problems with great success. Min-conflicts heuristic: select the value that results in the minimum number of conflicts with other variables—the min-conflicts heuristic. The run time of min-conflicts is roughly independent of problem size. Constraint weighting: aims to concentrate the search on the important constraints. Each constraint is given a numeric weight, initially all 1. At each step of the search, the algorithm chooses a variable/value pair to change that will result in the lowest total weight of all violated constraints. Another advantage of local search is that it can be used in an online setting when the problem changes. \n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       " A constraint graph is a tree when any two variables are connected by only one path. Any tree-structured CSP can be solved in time linear in the number of variables. A CSP is defined to be directional arc-consistent under an ordering of variables X1,X2,...,Xn if and only if every Xi is arc- consistent with each X j for j > i. To solve a tree-structured CSP, first pick any variable to be the root of the tree, and choose an ordering of the variables such that each variable appears after its parent in the tree. Such an ordering is called a topological sort. Cutset conditioning can reduce a general CSP to a tree-structured one and is quite efficient (requiring only linear memory) if a small cutset can be found. Tree decomposition techniques transform the CSP into a tree of subproblems and are efficient if the treewidth of the constraint graph is small; however they need memory exponential in the tree width of the constraint graph. Combining cutset conditioning with tree decomposition can allow a better tradeoff of memory versus time.  \n",
       "\n",
       "## Module 6 Lecture Notes\n",
       " \n",
       "Assumptions: a single agent, deterministic actions, fully observed state, discrete state space.Planning: sequences of actions. Represent the constraints that solutions must satisfy in a uniform declarative language.A CSP consists of: finite set of variables, nonempty domain of possible values, finite set of constraints. A solution to a CSP is a complete, consistent assignment. Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP.Applications: Map coloring, scheduling problem, Sudoku. Benefits: Clean specification of many problems, generic goal, successor function and heuristics; “knows” which variables violate a constraint; Automatically prune off all branches that violate constraints. CSP as a search problem: initial state, successor function, goal state, path cost. Solution is always found at depth n, for n variables. Tree has n!*dn leaves.Backtracking Search: DFS for CSP with single-variable assignments. Heuristic: most constrained variable (fewest legal move), most constraining variable (most constraints on remaining variables), least constraining value (choose the least constraining value), forward checking (Keep track of remaining legal values for unassigned variables. Terminate search when any unassigned variable has no remaining legal values).Arc consistency: X->Y is consistent iff for every value x of X there is some allowed y. Given d values, checking arc (i,j) takes O(d^2) time worst case AC-3: function AC3 return the CSP:while queue is not empty:(Xi, Xj) <- queue.pop() if REMOVE-INCONSISTENT(Xi,Xj) thenfor each Xk in NEIGHBORS[Xi] - {Xj}:add (Xk, Xi) to queuefunction REMOVE-INCONSISTENT (Xi, Xj) return true iff we remove a value:removed <- false for each x in DOMAIN[Xi]:\n",
       "if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraints between Xi and Xj delete x from DOMAIN[Xi] removed = True \n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Concept** - definition\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": 60,
   "metadata": {
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
    "\n",
    "chapter7_1 = \"\"\"\n",
    "The central component of a knowledge-based agent is its knowledge base, or KB. \\\n",
    "knowledge base: a set of sentences. \\\n",
    "knowledge representation language: Each sentence is expressed in a language.\\\n",
    "Axiom: When the sentence is taken as being given without being derived from other sentences. \\\n",
    "inference: deriving new sentences from old.\\\n",
    "Agent program does three things: First, it TELLs the knowledge base what it perceives. \\\n",
    "Second, it ASKs the knowledge base what action it should perform. \\\n",
    "Third, the agent program TELLs the knowledge base which action was chosen, \\\n",
    "and returns the action so that it can be executed. \\\n",
    "declarative approach: starting with an empty knowledge base, the agent designer can TELL \\\n",
    "sentences one by one until the agent knows how to operate in its environment. \\\n",
    "procedural approach: encodes desired behaviors directly as program code. \\\n",
    "\"\"\"\n",
    "\n",
    "chapter7_2 = \"\"\" \n",
    "In each case for which the agent draws a conclusion from the available information, \\\n",
    "that conclusion is guaranteed to be correct if the available information is correct. \\\n",
    "This is a fundamental property of logical reasoning. \\\n",
    "\"\"\"\n",
    "\n",
    "chapter7_3 = \"\"\" \n",
    "syntax of the representation language: specifies all the sentences that are well formed. \\\n",
    "semantics: the truth of each sentence with respect to each possible world.\\\n",
    "Use the term model in place of “possible world.” \\\n",
    "If a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α.\\\n",
    "We use the notation M(α) to mean the set of all models of α. \\\n",
    "Entailment: a sentence follows logically from another sentence. α|=β .\\\n",
    "If an inference algorithm i can derive α from KB, we write KB⊢i α, which is pronounced \\\n",
    "“α is derived from KB by i” or “i derives α from KB.”\\\n",
    "An inference algorithm that derives only entailed sentences is called sound or \\\n",
    "truth- preserving.  The property of completeness is also desirable: an inference algorithm \\\n",
    "is complete if it can derive any sentence that is entailed. \\\n",
    "If KB is true in the real world, then any sentence α derived from KB by a sound inference \\\n",
    "procedure is also true in the real world. \\\n",
    "Grounding: the connection between logical reasoning processes and the real environment in \\\n",
    "which the agent exists. \\\n",
    "KB may not be true in the real world, but with good learning procedures, there is reason \\\n",
    "for optimism. \\\n",
    "\"\"\"\n",
    "\n",
    "chapter7_4 = \"\"\" \n",
    "propositional logic: We describe its syntax and its semantics, from these, we derive a \\\n",
    "simple, syntactic algorithm for logical inference that implements the semantic notion \\\n",
    "of entailment. \\\n",
    "The atomic sentences consist of a single proposition symbol. Each such symbol stands for\\\n",
    "a proposition that can be true or false. \\\n",
    "Complex sentences are constructed from simpler sentences, using parentheses and operators \\\n",
    "called logical connectives. (¬, ∧, ∨, ⇒, ⇔)\\\n",
    "The semantics defines the rules for determining the truth of a sentence with respect to a\\\n",
    "particular model. \\\n",
    "Truth table:\\\n",
    "| P | Q | ¬ P | P ∧ Q | P ∨ Q | P ⇒ Q | P ⇔ Q | \n",
    "|:—-|:—-:|:—-:|:—-:|:—-:|:—-:|—-:|\n",
    "| false | false | true | false | false | true | true |\n",
    "| false | true | true | false | true | true | false |\n",
    "| true | false | false | false | true | false | false |\n",
    "| true | true | false | true | true | true | true |\n",
    "The algorithm is sound because it implements directly the definition of entailment, \\\n",
    "and complete because it works for any KB and α and always terminates. \\\n",
    "If KB and α contain n symbols in all, then there are 2^n models. Thus, the time complexity \\\n",
    "of the algorithm is O(2^n). (The space complexity is only O(n) because the enumeration is \\\n",
    "depth-first.) Unfortunately, propositional entailment is co-NP-complete (i.e., probably no \\\n",
    "easier than NP-complete) So every known inference algorithm for propositional logic has a \\\n",
    "worst-case complexity that is exponential in the size of the input. \\\n",
    "\"\"\"\n",
    "\n",
    "chapter7_5 = \"\"\" \n",
    "Determine entailment by model checking: enumerating models and showing that the sentence must\\\n",
    "hold in all models. \\\n",
    "Theorem proving: applying rules of inference directly to the sentences in our knowledge base \\\n",
    "to construct a proof of the desired sentence without consulting models. \\\n",
    "logical equivalence: two sentences α and β are logically equivalent if they are true in the \\\n",
    "same set of models. (α≡β)\\\n",
    "validity: A sentence is valid if it is true in all models. Valid sentences are also known \\\n",
    "as tautologies—they are necessarily true. \\\n",
    "deduction theorem: For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) \\\n",
    "is valid.  \\\n",
    "satisfiability: A sentence is satisfiable if it is true in, or satisfied by, some model. \\\n",
    "Validity and satisfiability are of course connected: α is valid iff ¬α is unsatisfiable; \\\n",
    "contrapositively, α is satisfiable iff ¬α is not valid. (α |= β if and only if the sentence\\\n",
    "(α ∧ ¬β) is unsatisfiable. )\\\n",
    "Resolution: yields a complete inference algorithm when coupled with any complete search \\\n",
    "algorithm. \\\n",
    "The completeness theorem for resolution in propositional logic is called the ground \\\n",
    "resolution theorem: If a set of clauses is unsatisfiable, then the resolution closure of \\\n",
    "those clauses contains the empty clause. \\\n",
    "So all definite clauses are Horn clauses, as are clauses with no positive literals; \\\n",
    "these are called goal clauses. Horn clauses are closed under resolution: if you resolve \\\n",
    "two Horn clauses, you get back a Horn clause. \\\n",
    "Every definite clause can be written as an implication whose premise is a conjunction of \\\n",
    "positive literals and whose conclusion is a single positive literal. \\\n",
    "Inference with Horn clauses can be done through the forward-chaining and backward-chaining \\\n",
    "algorithms.\\\n",
    "Deciding entailment with Horn clauses can be done in time that is linear in the size of the \\\n",
    "knowledge base.\\\n",
    "The forward-chaining algorithm determines if a single proposition symbol q—the query—is \\\n",
    "entailed by a knowledge base of definite clauses. \\\n",
    "Forward chaining is sound: every inference is essentially an appli- cation of Modus Ponens.\\\n",
    "Forward chaining is also complete: every entailed atomic sentence will be derived. \\\n",
    "Forward chaining is an example of the general concept of data-driven reasoning—that is, \\\n",
    "reasoning in which the focus of attention starts with the known data. \\\n",
    "The backward-chaining algorithm works backward from the query. If the query q is known to \\\n",
    "be true, then no work is needed. Otherwise, the algorithm finds those implications in the \\\n",
    "knowledge base whose conclusion is q. \\\n",
    "Backward chaining is a form of goal-directed reasoning. \\\n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module7_lecture_notes = \"\"\" \n",
    "Problem-solving agents have performed a search over states in order to find a plan. The \\\n",
    "representation of states has been atomic.\\\n",
    "Knowledge-based agents use a process of reasoning over an internal representation of \\\n",
    "knowledge to decide what action to take.\\\n",
    "A central component of a knowledge-based agent is a knowledge base or KB. A KB \\\n",
    "contains a set of sentence that are written in a knowledge representation language. \\\n",
    "Two kinds of sentence: Axioms (given sentence), Derived sentences (new sentence derived).\\\n",
    "In addition to asserting new knowledge into its KB, a knowledge-based agent can also \\\n",
    "query the KB and ask it to derive new knowledge in order to select what action it \\\n",
    "should take. \\\n",
    "Logic: serve as a general class of representations for knowledge-based agents.\\\n",
    "KB consists of sentences in the representation language; \\\n",
    "Representation language has a syntax that specifies sentences that are well-formed;\n",
    "A logic defines the semantics of the sentences, which is their meaning;\n",
    "The semantics defines the truth of each sentence with respect to a possible world, \\\n",
    "which we will often call a model. \\\n",
    "Models are mathematical abstractions that have a fixed set of truth values which are \\\n",
    "{true, false} for each sentence. If sentence 𝛂 is true in model m then we say \\\n",
    "m satisfies 𝛂, or m is a model of 𝛂. M(𝛂) means the set of all models of 𝛂. \\\n",
    "Logical reasoning involves the entailment relation between sentence. \\\n",
    "𝛂 entails sentence β (𝛂⊨β).\\ \n",
    "𝛂⊨β if and only if M(𝛂) ⊆ M(β), 𝛂 is more specific, or stronger than β.\\\n",
    "Entailment can be applied to derive conclusions, which is the process of logical \\\n",
    "inference. \\\n",
    "When an inference algorithm i allows us to conclude that 𝛂 is true, then we write \\\n",
    "KB⊢i 𝛂 (“𝛂 is derived from KB by i”) \\\n",
    "Sound: the inference algorithm should only derive entailed sentences. \\\n",
    "Complete: if an inference algorithm can derive all sentences that are entailed. \\\n",
    "Two sentences 𝛂 and β are logically equivalent if they are true in the same set of \n",
    "models. (𝛂≡β) if and only if 𝛂⊨β and β⊨𝛂.\\\n",
    "Biconditional Elimination: 𝛂⇔β == (𝛂 ⟹ β) ⋀ (β ⟹ 𝛂).\\\n",
    "And Elimination: 𝛂⋀β == 𝛂. \\\n",
    "Logical equivalence for contrapositives: (𝛂 ⟹ β) == (¬ β ⟹ ¬ 𝛂).\\\n",
    "Modus Ponens: 𝛂⟹β, 𝛂 == β. \\\n",
    "De Morgan’s Rule: ¬(𝛂 ⋁ β) == (¬𝛂 ⋀ ¬β). \\\n",
    "Monotonicity: if KB⊨𝛂 then KB⋀β⊨𝛂. If we add additional information to the KB, \\\n",
    "it doesn’t invalidate any other info that we’ve already inferred. \\\n",
    "Therefore it is sound it will only derive entailed sentences. \\\n",
    "Conjunctive Normal Form (CNF): 1) Eliminate ⇔ by replacing 𝛂⇔β with (𝛂⟹β)⋀(β⟹𝛂); \\\n",
    " 2) Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β; 3) Move ¬ inwards (eliminate double \\\n",
    " negation, and apply De Morgan’s rules; \\\n",
    " 4) Now the sentence will contain nested ⋀ and ⋁ operators applied to literals.\\\n",
    "Definite clause: disjunction of literals where exactly one is positive. \\\n",
    "Horn clause: disjunction of literals where at most one is positive. This includes definite \\\n",
    "clauses and clauses with no positive literals. \\\n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module7_definitions = {\n",
    "\"inference\" : \"deriving new sentences from old ones\",  \n",
    "\"entailment\" : \"a sentence follows another sentence logically\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 132\n",
      "The length in words is 37\n",
      "The length in words is 207\n",
      "The length in words is 257\n",
      "The length in words is 410\n",
      "The length in words is 493\n"
     ]
    }
   ],
   "source": [
    "print(\"The length in words is\", len(chapter7_1.split(' ')))\n",
    "print(\"The length in words is\", len(chapter7_2.split(' ')))\n",
    "print(\"The length in words is\", len(chapter7_3.split(' ')))\n",
    "print(\"The length in words is\", len(chapter7_4.split(' ')))\n",
    "print(\"The length in words is\", len(chapter7_5.split(' ')))\n",
    "print(\"The length in words is\", len(module7_lecture_notes.split(' ')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 541
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "fd406b8c-6eaa-4be5-be5f-3639d4b7fa43"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       "\n",
       "The central component of a knowledge-based agent is its knowledge base, or KB. knowledge base: a set of sentences. knowledge representation language: Each sentence is expressed in a language.Axiom: When the sentence is taken as being given without being derived from other sentences. inference: deriving new sentences from old.Agent program does three things: First, it TELLs the knowledge base what it perceives. Second, it ASKs the knowledge base what action it should perform. Third, the agent program TELLs the knowledge base which action was chosen, and returns the action so that it can be executed. declarative approach: starting with an empty knowledge base, the agent designer can TELL sentences one by one until the agent knows how to operate in its environment. procedural approach: encodes desired behaviors directly as program code. \n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       " \n",
       "In each case for which the agent draws a conclusion from the available information, that conclusion is guaranteed to be correct if the available information is correct. This is a fundamental property of logical reasoning. \n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       " \n",
       "syntax of the representation language: specifies all the sentences that are well formed. semantics: the truth of each sentence with respect to each possible world.Use the term model in place of “possible world.” If a sentence α is true in model m, we say that m satisfies α or sometimes m is a model of α.We use the notation M(α) to mean the set of all models of α. Entailment: a sentence follows logically from another sentence. α|=β .If an inference algorithm i can derive α from KB, we write KB⊢i α, which is pronounced “α is derived from KB by i” or “i derives α from KB.”An inference algorithm that derives only entailed sentences is called sound or truth- preserving.  The property of completeness is also desirable: an inference algorithm is complete if it can derive any sentence that is entailed. If KB is true in the real world, then any sentence α derived from KB by a sound inference procedure is also true in the real world. Grounding: the connection between logical reasoning processes and the real environment in which the agent exists. KB may not be true in the real world, but with good learning procedures, there is reason for optimism. \n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       " \n",
       "propositional logic: We describe its syntax and its semantics, from these, we derive a simple, syntactic algorithm for logical inference that implements the semantic notion of entailment. The atomic sentences consist of a single proposition symbol. Each such symbol stands fora proposition that can be true or false. Complex sentences are constructed from simpler sentences, using parentheses and operators called logical connectives. (¬, ∧, ∨, ⇒, ⇔)The semantics defines the rules for determining the truth of a sentence with respect to aparticular model. Truth table:| P | Q | ¬ P | P ∧ Q | P ∨ Q | P ⇒ Q | P ⇔ Q | \n",
       "|:—-|:—-:|:—-:|:—-:|:—-:|:—-:|—-:|\n",
       "| false | false | true | false | false | true | true |\n",
       "| false | true | true | false | true | true | false |\n",
       "| true | false | false | false | true | false | false |\n",
       "| true | true | false | true | true | true | true |\n",
       "The algorithm is sound because it implements directly the definition of entailment, and complete because it works for any KB and α and always terminates. If KB and α contain n symbols in all, then there are 2^n models. Thus, the time complexity of the algorithm is O(2^n). (The space complexity is only O(n) because the enumeration is depth-first.) Unfortunately, propositional entailment is co-NP-complete (i.e., probably no easier than NP-complete) So every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input. \n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       " \n",
       "Determine entailment by model checking: enumerating models and showing that the sentence musthold in all models. Theorem proving: applying rules of inference directly to the sentences in our knowledge base to construct a proof of the desired sentence without consulting models. logical equivalence: two sentences α and β are logically equivalent if they are true in the same set of models. (α≡β)validity: A sentence is valid if it is true in all models. Valid sentences are also known as tautologies—they are necessarily true. deduction theorem: For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid.  satisfiability: A sentence is satisfiable if it is true in, or satisfied by, some model. Validity and satisfiability are of course connected: α is valid iff ¬α is unsatisfiable; contrapositively, α is satisfiable iff ¬α is not valid. (α |= β if and only if the sentence(α ∧ ¬β) is unsatisfiable. )Resolution: yields a complete inference algorithm when coupled with any complete search algorithm. The completeness theorem for resolution in propositional logic is called the ground resolution theorem: If a set of clauses is unsatisfiable, then the resolution closure of those clauses contains the empty clause. So all definite clauses are Horn clauses, as are clauses with no positive literals; these are called goal clauses. Horn clauses are closed under resolution: if you resolve two Horn clauses, you get back a Horn clause. Every definite clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal. Inference with Horn clauses can be done through the forward-chaining and backward-chaining algorithms.Deciding entailment with Horn clauses can be done in time that is linear in the size of the knowledge base.The forward-chaining algorithm determines if a single proposition symbol q—the query—is entailed by a knowledge base of definite clauses. Forward chaining is sound: every inference is essentially an appli- cation of Modus Ponens.Forward chaining is also complete: every entailed atomic sentence will be derived. Forward chaining is an example of the general concept of data-driven reasoning—that is, reasoning in which the focus of attention starts with the known data. The backward-chaining algorithm works backward from the query. If the query q is known to be true, then no work is needed. Otherwise, the algorithm finds those implications in the knowledge base whose conclusion is q. Backward chaining is a form of goal-directed reasoning. \n",
       "\n",
       "## Module 7 Lecture Notes\n",
       " \n",
       "Problem-solving agents have performed a search over states in order to find a plan. The representation of states has been atomic.Knowledge-based agents use a process of reasoning over an internal representation of knowledge to decide what action to take.A central component of a knowledge-based agent is a knowledge base or KB. A KB contains a set of sentence that are written in a knowledge representation language. Two kinds of sentence: Axioms (given sentence), Derived sentences (new sentence derived).In addition to asserting new knowledge into its KB, a knowledge-based agent can also query the KB and ask it to derive new knowledge in order to select what action it should take. Logic: serve as a general class of representations for knowledge-based agents.KB consists of sentences in the representation language; Representation language has a syntax that specifies sentences that are well-formed;\n",
       "A logic defines the semantics of the sentences, which is their meaning;\n",
       "The semantics defines the truth of each sentence with respect to a possible world, which we will often call a model. Models are mathematical abstractions that have a fixed set of truth values which are {true, false} for each sentence. If sentence 𝛂 is true in model m then we say m satisfies 𝛂, or m is a model of 𝛂. M(𝛂) means the set of all models of 𝛂. Logical reasoning involves the entailment relation between sentence. 𝛂 entails sentence β (𝛂⊨β).\\ \n",
       "𝛂⊨β if and only if M(𝛂) ⊆ M(β), 𝛂 is more specific, or stronger than β.Entailment can be applied to derive conclusions, which is the process of logical inference. When an inference algorithm i allows us to conclude that 𝛂 is true, then we write KB⊢i 𝛂 (“𝛂 is derived from KB by i”) Sound: the inference algorithm should only derive entailed sentences. Complete: if an inference algorithm can derive all sentences that are entailed. Two sentences 𝛂 and β are logically equivalent if they are true in the same set of \n",
       "models. (𝛂≡β) if and only if 𝛂⊨β and β⊨𝛂.Biconditional Elimination: 𝛂⇔β == (𝛂 ⟹ β) ⋀ (β ⟹ 𝛂).And Elimination: 𝛂⋀β == 𝛂. Logical equivalence for contrapositives: (𝛂 ⟹ β) == (¬ β ⟹ ¬ 𝛂).Modus Ponens: 𝛂⟹β, 𝛂 == β. De Morgan’s Rule: ¬(𝛂 ⋁ β) == (¬𝛂 ⋀ ¬β). Monotonicity: if KB⊨𝛂 then KB⋀β⊨𝛂. If we add additional information to the KB, it doesn’t invalidate any other info that we’ve already inferred. Therefore it is sound it will only derive entailed sentences. Conjunctive Normal Form (CNF): 1) Eliminate ⇔ by replacing 𝛂⇔β with (𝛂⟹β)⋀(β⟹𝛂);  2) Eliminate ⟹ by replacing 𝛂 ⟹ β with ¬𝛂 ⋁ β; 3) Move ¬ inwards (eliminate double  negation, and apply De Morgan’s rules;  4) Now the sentence will contain nested ⋀ and ⋁ operators applied to literals.Definite clause: disjunction of literals where exactly one is positive. Horn clause: disjunction of literals where at most one is positive. This includes definite clauses and clauses with no positive literals. \n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Inference** - deriving new sentences from old ones\n",
       "* **Entailment** - a sentence follows another sentence logically\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": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 3366
    },
    "id": "T3cm1WV542_a",
    "outputId": "a929c6c6-b72b-4fd8-bd35-a014674c9230"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       " Chapter 1.1 summary. \n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       " Your summary here \n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       " Your summary here \n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       " Your summary here \n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       " Your summary here \n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       " Your summary here \n",
       "\n",
       "## Module 1 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - anything that can perceive and act in an environment\n",
       "* **Percept** - your definitions here\n",
       "* **Other concept** - your definitions here\n",
       "* **Etc.** - your definitions here\n",
       "\n",
       "\n",
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Mutability** - your definition here\n",
       "\n",
       "\n",
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       " Your summary here \n",
       "\n",
       "## Module 3 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "\n",
       "\n",
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       " Your summary here \n",
       "\n",
       "## Module 4 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       " Your summary here \n",
       "\n",
       "## Module 5 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       " Your summary here \n",
       "\n",
       "## Module 6 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 6 Definitions\n",
       "* **Concept** - definition\n",
       "\n",
       "\n",
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       " Your summary here \n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       " Your summary here \n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       " Your summary here \n",
       "\n",
       "## Module 7 Lecture Notes\n",
       " Your summary here \n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Concept** - definition\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))"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Copy of 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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
