{
 "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": "04ad3b00-7639-4936-fd19-c62e39b22c77"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The example summary is 593 words long, so you could write an additional -93 words.\n"
     ]
    }
   ],
   "source": [
    "chapter_2_1_example = \"\"\"\n",
    "R 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.  \n",
    "- If the number of models is large but the length of the proof is short, then theorem proving can  be more efficient than model checking. \n",
    "- logical equivalence: two sentences α and β are logically equivalent if they are true in the same set of models. We write  this as α ≡ β.\n",
    "  - that ≡ is used to make claims about sentences, while ⇔ is used as part  of a sentence\n",
    "  - α ≡ β if and only if α |= β and β |= α.\n",
    "- deduction theorem:\n",
    "  - For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid. \n",
    "  - α |= β if and only if the sentence (α∧ ¬β) is unsatisfiable.\n",
    "  - every valid implication sentence describes a legitimate inference. \n",
    "- Inference and proof:\n",
    "  - Modus Ponens:\n",
    "    - ( α ⇒ β, α )/ β, whenever any sentences of the form α ⇒ β and α are given, then  the sentence β can be inferred.\n",
    "  - and elimination:\n",
    "    - (α∧β)/ α\n",
    "- proof as search:\n",
    "  - INITIAL STATE: the initial knowledge base.\n",
    "  - ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule.\n",
    "  - RESULT: the result of an action is to add the sentence in the bottom half of the inference  rule\n",
    "  - GOAL: the goal is a state that contains the sentence we are trying to prove\n",
    "- finding a proof can be more efficient because the proof can ignore irrelevant propositions, no  matter how many of them there are.\n",
    "- monotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base\n",
    "  - draw additional conclusions, but it cannot invalidate any conclusion α already inferred\n",
    "  - base—the conclusion of the rule must follow  regardless of what else is in the knowledge base. (since it must be true)\n",
    "- Proof by resolution:\n",
    "  - that yields a complete  inference algorithm when coupled with any complete search algorithm\n",
    "  - resolution simple form:\n",
    "    - ℓ1 ∨ ···∨ℓk, m / ℓ1 ∨ ··· ∨ℓi−1 ∨ℓi+1 ∨ ···∨ℓk \n",
    "  - general form\n",
    "    - ℓ1 ∨ ···∨ℓk, m1 ∨ ···∨ mn / ℓ1 ∨ ··· ∨ℓi−1 ∨ℓi+1 ∨ ···∨ℓk ∨ m1∨ ··· ∨ mj−1∨ mj+1 ∨ ··· ∨ mn \n",
    "  - eg .\n",
    "    - P1,1 ∨P3,1, ¬P1,1 ∨ ¬P2,2 / P3,1 ∨ ¬P2,2 \n",
    "    - P∨ ¬Q ∨R, ¬P∨ Q / ¬Q ∨ Q ∨R, \n",
    "- A resolution-based theorem prover can, for any sentences α  and β in propositional logic, decide whether α |= β.\n",
    "  - CNF\n",
    "    - every  sentence of propositional logic is logically equivalent to a conjunction of clauses. \n",
    "  - resolution algorithm:\n",
    "    - Each pair that contains complementary literals is resolved to produce a new clause, which is added to the set if it is not  already present.\n",
    "- completeness of resolution:\n",
    "  - ground resolution theorm: If a set of clauses is unsatisfiable, then the resolution closure of those clauses  contains the empty clause. \n",
    "  - \n",
    "\"\"\"\n",
    "\n",
    "length = len(chapter_2_1_example.split(\" \"))\n",
    "print(\"The example summary is {len} words long, so you could write an additional \\\n",
    "{remaining} words.\".format(len=length, remaining=(500-length)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "s3Uk9gQTevcj"
   },
   "source": [
    "## Example summary length\n",
    "\n",
    "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "8DvZ57A-djo1",
    "outputId": "da089cd8-1427-49a8-8dc3-edf0c1384d77"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length in words is 1\n",
      "The length in characters is 1\n"
     ]
    }
   ],
   "source": [
    "# This is an example of a 500 word placeholder\n",
    "placeholder = \"\"\"\n",
    "\"\"\"\n",
    "\n",
    "print(\"The length in words is\", len(placeholder.split(' ')))\n",
    "print(\"The length in characters is\", len(placeholder))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "5yG3-YncJfTB"
   },
   "source": [
    "# Permissions to use your summaries\n",
    "\n",
    "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
    "\n",
    "1. Please enter your name.  \n",
    "\n",
    "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
    "\n",
    "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "2RECnJArJew4"
   },
   "outputs": [],
   "source": [
    "name = \"\"\n",
    "permission = True\n",
    "anonymous = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GZZXyrV-xuAp"
   },
   "source": [
    "# Module 1 - Intro to AI"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "Y2NfE1CKxzS-"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
    "\n",
    "chapter1_1 = \"\"\"\n",
    "- Turing test：NLP, knowledge representation, automated reasoning, ML. total Turing test: CV, robotics(manipulation in real world)   <br />\n",
    "- Human thought: introspection, psychological experiment, brain imaging <br />\n",
    "- There are ways of acting rationally that cannot be said to involve inference - reflex action <br />\n",
    "- All the skills needed for turing test allow an agent to act rationally <br />\n",
    "- ratioal agent appraoch to AI has two advantages: 1. more general than laws of though, because correct inference is just one of several possible mechanisms for rationality. 2. it is more ameable for development as mathematically it is well defined and complete <br />\n",
    "- AI has focused on the study and construction of agents that do the right thing <br />\n",
    "- standard model may not be the right model to the future as standard model assumes that we will supply a fully specified objective to the machine viable. A system deployed with an incorrect objective will have negative consequences. Moreover, the more intelligent the system, the  more negative the consequences <br />\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",
    "- weak AI—the idea that Weak AI  machines could act as if they were intelligent\n",
    "- stronbg AI- do so are actually consciously thinking (not just simulating thinking).\n",
    "- The embodied cognition approach claims that it makes no sense to consider the brain  separately: cognition takes place within a body, which is embedded in an environment. We  need to study the system as a whole; the brain’s functioning exploits regularities in its environment, including the rest of its body.\n",
    "- suggested  that instead of asking whether machines can think, we should ask whether machines can pass  a behavioral test, which has come to be called the Turing test.\n",
    " \"\"\"\n",
    "chapter27_2 = \"\"\" \n",
    "- consciousness: awareness Consciousness  of the outside world, and of the self, and the subjective experience of living.\n",
    "- The technical  term for the intrinsic nature of experiences is qualia (from the Latin word meaning, roughly, “of what kind”).\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
    "chapter2_1 = \"\"\" \n",
    "- In general, an agent’s choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived.   <br />\n",
    "- construct this table by trying out all possible percept sequences and recording  which actions the agent does in response. The table is, of course, an external characterization of the agent. Internal, agent program.<br />\n",
    "- The agent function is an Agent program  abstract mathematical description; the agent program is a concrete implementation, running  within some physical system.<br />\n",
    "- agent is meant to be a tool for analyzing systems, not an absolute characterization that divides the world into  agents and non-agents.<br />\n",
    "- AI operates at (what the authors  consider to be) the most interesting end of the spectrum, where the artifacts have significant  computational resources and the task environment requires nontrivial decision making. \n",
    " \"\"\"\n",
    "chapter2_2 = \"\"\" \n",
    "- This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.<br />\n",
    "- We will see that some agent designs have an explicit representation of (a version of) the performance measure, while in other designs the performance measure is entirely implicit—the  agent may do the right thing, but it doesn’t know why.<br />\n",
    "- Performance measure could be +1 for correct move, -1 for incorrect move, etc\n",
    "- As a general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave.<br />\n",
    "- rationality is not the same as perfection. Rationality maximizes expected performance, while perfection maximizes actual performance.<br />\n",
    "- a rational agent not only to gather information but also to learn as Learning much as possible from what it perceives.<br />\n",
    "\"\"\"\n",
    "chapter2_3 = \"\"\" \n",
    "- task environment groups PEAS, can be physical or virtual<br />\n",
    "  - Construct agent function f that maximizes the expected value of the performance measure(math description)\n",
    "  - Design an agent program that implements f on a particular architecture(concrete implementation)\n",
    "- Properties of task environments:<br />\n",
    "<strong>Fully observable vs. partially observable</strong>: an agent’s sensors access to the complete state of the environment at each point in time, A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action<br />\n",
    "<strong>Single-agent vs. multiagent</strong>: An object or an agent, it is an agent if behavior is best described as maximizing a performance measure whose value depends on agent A’s behavior. Taxi example, avoid collision, cooperative agent; chess competitive.<br />\n",
    "<strong>Deterministic vs. nondeterministic</strong>: If the next state of the environment is completely determined by the current state and the action executed by the agent(s), deterministic.\\\n",
    "fully observable, deterministic environment, no worry about uncertainty. partially observable, however, could appear to be nondeterministic. Most real situations are nondeterm.<br />\n",
    "<strong>Episodic vs. sequential</strong>: In an episodic task environment, the agent’s experience is divided into atomic episodes. Many classification tasks are episodic.\\\n",
    "The next episode does not depend on the actions taken in previous episodes. Chess taxi are sequential.<br />\n",
    "<strong>Static vs. dynamic</strong>: If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent. \\\n",
    "semidynamic if the environment itself does not change with the  passage of time but the agent’s performance score does. taxi dynamic, chess semi, crossword static.<br />\n",
    "<strong>Discrete vs. continuous</strong>: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent. \\\n",
    "chess discrete, taxi continous<br />\n",
    "<strong>known vs. unknown</strong>: distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of  the environment. \\\n",
    "In a known environment, the outcomes for all actions are given. if the environment is unknown, the agent will have to learn how it works in order to make good decisions. \\\n",
    "observability does not interdepent on known\n",
    "\"\"\"\n",
    "chapter2_4 = \"\"\" \n",
    "- $agent = architecture + program$ <br />\n",
    "- The key challenge for AI is to find out how to write programs that, to the extent possible, produce rational behavior from a smallish program rather than from a vast table. <br />\n",
    "- <strong>simple reflex agent</strong>: These agents select actions on the basis of the current percept, ignoring the rest of the percept history.\n",
    "  - Simple reflex agents have the admirable property of being simple, but will work only if the correct decision can be made only if the environment is fully observable.\n",
    "  - random is usually not rational but it can be rational in some cases\n",
    "- <strong>Model-based reflex agents</strong>: to handle partial observability is for the agent to keep track of the part of the world it can’t see now. \\\n",
    "The agent should maintain some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved aspects of the current state.\n",
    "  - model based agent: transition model + sensor model\n",
    "  - not fully observable extactly, need possibility\n",
    "- <strong>Goal-based agents</strong>: Knowing something about the current state of the environment is not always enough to decide what to do. \\\n",
    "The agent needs some sort of goal information that Goal  describes situations that are desirable.\n",
    "  - the goal-based agent appears less efficient, it is more flexible because the knowledge that supports its decisions is represented explicitly and can be modified.\n",
    "- <strong>Utility-based agents</strong>:Goals alone are not enough to generate high-quality behavior in most environments. but some are quicker, safer, more reliable, or cheaper than others.\n",
    "   - An agent’s utility function is essentially an internalization of the performance measure.an agent that chooses actions to maximize its utility will be rational according to the external performance measure.\n",
    "- Learning has another advantage:\n",
    "  - operate in initially unknown environments and to become more competent than its initial knowledge alone might allow.\n",
    "- learning element, is responsible for making improvements\n",
    "- performance element, which is responsible for selecting external actions\n",
    "- problem generator, responsible Problem generator  for suggesting actions that will lead to new and informative experiences.\n",
    "- The design of the learning element depends very much on the design of the performance element.\n",
    "- if the agent is willing to explore a little and do some perhaps suboptimal actions in the short run, it might discover much better actions for the long run\n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module1_lecture_notes = \"\"\" \n",
    "- An agent is something that perceives and acts in an environment. The agent function  for an agent specifies the action taken by the agent in response to any percept sequence.  \n",
    "- The performance measure evaluates the behavior of the agent in an environment. A  rational agent acts so as to maximize the expected value of the performance measure,  given the percept sequence it has seen so far.  \n",
    "- A task environment specification includes the performance measure, the external environment, the actuators, and the sensors. In designing an agent, the first step must  always be to specify the task environment as fully as possible. \n",
    "- Task environments vary along several significant dimensions. They can be fully or partially observable, single-agent or multiagent, deterministic or nondeterministic, episodic  or sequential, static or dynamic, discrete or continuous, and known or unknown.  \n",
    "- In cases where the performance measure is unknown or hard to specify correctly, there  is a significant risk of the agent optimizing the wrong objective. In such cases the agent  design should reflect uncertainty about the true objective. \n",
    "- The agent program implements the agent function. There exists a variety of basic  agent program designs reflecting the kind of information made explicit and used in the  decision process. The designs vary in efficiency, compactness, and flexibility. The  appropriate design of the agent program depends on the nature of the environment. \n",
    "- Simple reflex agents respond directly to percepts, whereas model-based reflex agents  maintain internal state to track aspects of the world that are not evident in the current  percept. Goal-based agents act to achieve their goals, and utility-based agents try to  maximize their own expected “happiness.”  \n",
    "- All agents can improve their performance through learning. \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\" : \"is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators\",\n",
    "\"percept\":\"term percept to refer to the content an agent’s sensors are perceiving.\",\n",
    "\"percept sequence\":\"percept sequence is the complete history of everything the agent has ever perceived.\",\n",
    "\"rational agent\": \"For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure\",\n",
    "\"\":\" given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\",\n",
    "\"performance measure\":\"An objective criterion for success of an agent's behavior, given the evidence provided by the percept sequence.\",\n",
    "\"limited rationality\":\"acting when there is not enough time to do all the computation\",\n",
    "\"value alignment problem\": \"values or objectives put into the machine must aligned with thouse of the human\",\n",
    "\"agent function\":\"describes agent's behavior that maps any given percept sequence to an action\",\n",
    "\"agent program\":\"agent function for an artificial agent will be implemented by an agent program\",\n",
    "\"agent architecture\":\"the program run on some comptuing device with physical sensors and actuators\",\n",
    "\"consequentialism\": \"we evaluate an agent's behavior by its consequences\",\n",
    "\"omniscience\":\"an omniscient agent knows tha actual outcome of its action and can act accordingly, but omniscience is impossible in reality\",\n",
    "\"information gathering\":\"doing actions in order to modify future percepts\",\n",
    "\"autonomous\":\"it should learn what it can to compensate for partial or incorrect prior knowledge. \",\n",
    "\"task-environment\":\"the problems to which rational agents are the solutions.\",\n",
    "\"PEAS\":\"Performance, Environment, Actuators, Sensors\",\n",
    "\"stochastic\": \"nondeterministic\",\n",
    "\"tramsition model\":\"knowledge about “how the world works”—whether implemented in simple Boolean circuits or in complete scientific theories\",\n",
    "\"sensor model\":\"conditions where is knows from the sensor\",\n",
    "\"reflex agent\":\"select an action based on the current percept\",\n",
    "\"problem solving agent\":\"must plan ahead, consider a sequence of actions that form a path to a goal state, also know as search\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "elCCgY64spuq"
   },
   "source": [
    "## Preview of your notes for Module 1\n",
    "\n",
    "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "gYYeNcdM_maE",
    "outputId": "0a572f16-f111-4f1a-97c8-6e739f4640a0"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       "\n",
       "- Turing test：NLP, knowledge representation, automated reasoning, ML. total Turing test: CV, robotics(manipulation in real world)   <br />\n",
       "- Human thought: introspection, psychological experiment, brain imaging <br />\n",
       "- There are ways of acting rationally that cannot be said to involve inference - reflex action <br />\n",
       "- All the skills needed for turing test allow an agent to act rationally <br />\n",
       "- ratioal agent appraoch to AI has two advantages: 1. more general than laws of though, because correct inference is just one of several possible mechanisms for rationality. 2. it is more ameable for development as mathematically it is well defined and complete <br />\n",
       "- AI has focused on the study and construction of agents that do the right thing <br />\n",
       "- standard model may not be the right model to the future as standard model assumes that we will supply a fully specified objective to the machine viable. A system deployed with an incorrect objective will have negative consequences. Moreover, the more intelligent the system, the  more negative the consequences <br />\n",
       " \n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       "\n",
       "- weak AI—the idea that Weak AI  machines could act as if they were intelligent\n",
       "- stronbg AI- do so are actually consciously thinking (not just simulating thinking).\n",
       "- The embodied cognition approach claims that it makes no sense to consider the brain  separately: cognition takes place within a body, which is embedded in an environment. We  need to study the system as a whole; the brain’s functioning exploits regularities in its environment, including the rest of its body.\n",
       "- suggested  that instead of asking whether machines can think, we should ask whether machines can pass  a behavioral test, which has come to be called the Turing test.\n",
       " \n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       " \n",
       "- consciousness: awareness Consciousness  of the outside world, and of the self, and the subjective experience of living.\n",
       "- The technical  term for the intrinsic nature of experiences is qualia (from the Latin word meaning, roughly, “of what kind”).\n",
       "\n",
       "\n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       " \n",
       "- In general, an agent’s choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived.   <br />\n",
       "- construct this table by trying out all possible percept sequences and recording  which actions the agent does in response. The table is, of course, an external characterization of the agent. Internal, agent program.<br />\n",
       "- The agent function is an Agent program  abstract mathematical description; the agent program is a concrete implementation, running  within some physical system.<br />\n",
       "- agent is meant to be a tool for analyzing systems, not an absolute characterization that divides the world into  agents and non-agents.<br />\n",
       "- AI operates at (what the authors  consider to be) the most interesting end of the spectrum, where the artifacts have significant  computational resources and the task environment requires nontrivial decision making. \n",
       " \n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       " \n",
       "- This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.<br />\n",
       "- We will see that some agent designs have an explicit representation of (a version of) the performance measure, while in other designs the performance measure is entirely implicit—the  agent may do the right thing, but it doesn’t know why.<br />\n",
       "- Performance measure could be +1 for correct move, -1 for incorrect move, etc\n",
       "- As a general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave.<br />\n",
       "- rationality is not the same as perfection. Rationality maximizes expected performance, while perfection maximizes actual performance.<br />\n",
       "- a rational agent not only to gather information but also to learn as Learning much as possible from what it perceives.<br />\n",
       "\n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       " \n",
       "- task environment groups PEAS, can be physical or virtual<br />\n",
       "  - Construct agent function f that maximizes the expected value of the performance measure(math description)\n",
       "  - Design an agent program that implements f on a particular architecture(concrete implementation)\n",
       "- Properties of task environments:<br />\n",
       "<strong>Fully observable vs. partially observable</strong>: an agent’s sensors access to the complete state of the environment at each point in time, A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action<br />\n",
       "<strong>Single-agent vs. multiagent</strong>: An object or an agent, it is an agent if behavior is best described as maximizing a performance measure whose value depends on agent A’s behavior. Taxi example, avoid collision, cooperative agent; chess competitive.<br />\n",
       "<strong>Deterministic vs. nondeterministic</strong>: If the next state of the environment is completely determined by the current state and the action executed by the agent(s), deterministic.fully observable, deterministic environment, no worry about uncertainty. partially observable, however, could appear to be nondeterministic. Most real situations are nondeterm.<br />\n",
       "<strong>Episodic vs. sequential</strong>: In an episodic task environment, the agent’s experience is divided into atomic episodes. Many classification tasks are episodic.The next episode does not depend on the actions taken in previous episodes. Chess taxi are sequential.<br />\n",
       "<strong>Static vs. dynamic</strong>: If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent. semidynamic if the environment itself does not change with the  passage of time but the agent’s performance score does. taxi dynamic, chess semi, crossword static.<br />\n",
       "<strong>Discrete vs. continuous</strong>: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent. chess discrete, taxi continous<br />\n",
       "<strong>known vs. unknown</strong>: distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of  the environment. In a known environment, the outcomes for all actions are given. if the environment is unknown, the agent will have to learn how it works in order to make good decisions. observability does not interdepent on known\n",
       "\n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       " \n",
       "- $agent = architecture + program$ <br />\n",
       "- The key challenge for AI is to find out how to write programs that, to the extent possible, produce rational behavior from a smallish program rather than from a vast table. <br />\n",
       "- <strong>simple reflex agent</strong>: These agents select actions on the basis of the current percept, ignoring the rest of the percept history.\n",
       "  - Simple reflex agents have the admirable property of being simple, but will work only if the correct decision can be made only if the environment is fully observable.\n",
       "  - random is usually not rational but it can be rational in some cases\n",
       "- <strong>Model-based reflex agents</strong>: to handle partial observability is for the agent to keep track of the part of the world it can’t see now. The agent should maintain some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved aspects of the current state.\n",
       "  - model based agent: transition model + sensor model\n",
       "  - not fully observable extactly, need possibility\n",
       "- <strong>Goal-based agents</strong>: Knowing something about the current state of the environment is not always enough to decide what to do. The agent needs some sort of goal information that Goal  describes situations that are desirable.\n",
       "  - the goal-based agent appears less efficient, it is more flexible because the knowledge that supports its decisions is represented explicitly and can be modified.\n",
       "- <strong>Utility-based agents</strong>:Goals alone are not enough to generate high-quality behavior in most environments. but some are quicker, safer, more reliable, or cheaper than others.\n",
       "   - An agent’s utility function is essentially an internalization of the performance measure.an agent that chooses actions to maximize its utility will be rational according to the external performance measure.\n",
       "- Learning has another advantage:\n",
       "  - operate in initially unknown environments and to become more competent than its initial knowledge alone might allow.\n",
       "- learning element, is responsible for making improvements\n",
       "- performance element, which is responsible for selecting external actions\n",
       "- problem generator, responsible Problem generator  for suggesting actions that will lead to new and informative experiences.\n",
       "- The design of the learning element depends very much on the design of the performance element.\n",
       "- if the agent is willing to explore a little and do some perhaps suboptimal actions in the short run, it might discover much better actions for the long run\n",
       "\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       " \n",
       "- An agent is something that perceives and acts in an environment. The agent function  for an agent specifies the action taken by the agent in response to any percept sequence.  \n",
       "- The performance measure evaluates the behavior of the agent in an environment. A  rational agent acts so as to maximize the expected value of the performance measure,  given the percept sequence it has seen so far.  \n",
       "- A task environment specification includes the performance measure, the external environment, the actuators, and the sensors. In designing an agent, the first step must  always be to specify the task environment as fully as possible. \n",
       "- Task environments vary along several significant dimensions. They can be fully or partially observable, single-agent or multiagent, deterministic or nondeterministic, episodic  or sequential, static or dynamic, discrete or continuous, and known or unknown.  \n",
       "- In cases where the performance measure is unknown or hard to specify correctly, there  is a significant risk of the agent optimizing the wrong objective. In such cases the agent  design should reflect uncertainty about the true objective. \n",
       "- The agent program implements the agent function. There exists a variety of basic  agent program designs reflecting the kind of information made explicit and used in the  decision process. The designs vary in efficiency, compactness, and flexibility. The  appropriate design of the agent program depends on the nature of the environment. \n",
       "- Simple reflex agents respond directly to percepts, whereas model-based reflex agents  maintain internal state to track aspects of the world that are not evident in the current  percept. Goal-based agents act to achieve their goals, and utility-based agents try to  maximize their own expected “happiness.”  \n",
       "- All agents can improve their performance through learning. \n",
       " \n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators\n",
       "* **Percept** - term percept to refer to the content an agent’s sensors are perceiving.\n",
       "* **Percept sequence** - percept sequence is the complete history of everything the agent has ever perceived.\n",
       "* **Rational agent** - For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure\n",
       "* **** -  given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n",
       "* **Performance measure** - An objective criterion for success of an agent's behavior, given the evidence provided by the percept sequence.\n",
       "* **Limited rationality** - acting when there is not enough time to do all the computation\n",
       "* **Value alignment problem** - values or objectives put into the machine must aligned with thouse of the human\n",
       "* **Agent function** - describes agent's behavior that maps any given percept sequence to an action\n",
       "* **Agent program** - agent function for an artificial agent will be implemented by an agent program\n",
       "* **Agent architecture** - the program run on some comptuing device with physical sensors and actuators\n",
       "* **Consequentialism** - we evaluate an agent's behavior by its consequences\n",
       "* **Omniscience** - an omniscient agent knows tha actual outcome of its action and can act accordingly, but omniscience is impossible in reality\n",
       "* **Information gathering** - doing actions in order to modify future percepts\n",
       "* **Autonomous** - it should learn what it can to compensate for partial or incorrect prior knowledge. \n",
       "* **Task-environment** - the problems to which rational agents are the solutions.\n",
       "* **Peas** - Performance, Environment, Actuators, Sensors\n",
       "* **Stochastic** - nondeterministic\n",
       "* **Tramsition model** - knowledge about “how the world works”—whether implemented in simple Boolean circuits or in complete scientific theories\n",
       "* **Sensor model** - conditions where is knows from the sensor\n",
       "* **Reflex agent** - select an action based on the current percept\n",
       "* **Problem solving agent** - must plan ahead, consider a sequence of actions that form a path to a goal state, also know as search\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "from IPython.display import display, Markdown, Latex\n",
    "\n",
    "module1_sections = [\n",
    "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
    "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
    "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
    "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
    "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
    "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
    "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
    "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
    "]\n",
    "\n",
    "\n",
    "def length_check(sections):\n",
    "  warnings = \"\"\n",
    "  for section, summary in sections:\n",
    "    max_word_length = 500\n",
    "    max_character_length = 3000\n",
    "    if \"lecture\" in section.lower():\n",
    "      # It's OK to do longer summaries of the lectures\n",
    "      max_word_length = 2000\n",
    "      max_character_length = 12000  \n",
    "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
    "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
    "  return warnings\n",
    "\n",
    "def length_check_definitions(definitions):\n",
    "  warnings = \"\"\n",
    "  for concept, definition in definitions.items():\n",
    "    if(len(definition.split(' ')) > 20):\n",
    "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
    "  return warnings\n",
    "\n",
    "\n",
    "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
    "  markdown = \"\"\n",
    "\n",
    "  # Check summary lengths\n",
    "  warnings = length_check(sections)\n",
    "  if warnings != \"\":\n",
    "    markdown += \"## \" + warnings\n",
    "\n",
    "  # Check definition lengths\n",
    "  warnings = length_check_definitions(definitions)\n",
    "  if warnings != \"\":\n",
    "    markdown += \"## \" + warnings\n",
    "\n",
    "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
    "\n",
    "\n",
    "  for section, summary in sections:\n",
    "    if show_placeholder and summary == \" Your summary here \":\n",
    "      summary = placeholder\n",
    "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
    "  \n",
    "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
    "  for concept, definition in definitions.items():\n",
    "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
    "  return markdown\n",
    "\n",
    "\n",
    "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
    "display(Markdown(module1_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9xRbdqDox2zD"
   },
   "source": [
    "#Module 2 - Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "DpBvu7EMx7sy"
   },
   "outputs": [],
   "source": [
    "# No readings for this module.  Instead you can summarize the lecture instead.\n",
    "\n",
    "# Lecture notes \n",
    "module2_lecture_notes = \"\"\"\n",
    "- Strong Typing\n",
    "  - Every object has a fixed type, interpreter doesn’t allow things incompatible with\n",
    "    - that type (eg. “foo” + 2)\n",
    "  - python uses dynamic typing, Variables come into existence when first assigned\n",
    "  - If assigned again, type(var) is updated\n",
    "- String\n",
    "  - Creation\n",
    "    - Can use either single or double quotes, Triple quote for multiline string and docstring\n",
    "  - Concatenating strings\n",
    "    - By separating string literals with whitespace Special use of ‘+’\n",
    "  - Prefixing with r means raw.\n",
    "    - No need to escape special characters: r’\\n’\n",
    "  - String formatting\n",
    "    - Special use of ‘%’ (as in printf in C)\n",
    "  - Immutable\n",
    "- Reference and Mutability\n",
    "  - x = x.strip() # new obj\n",
    "  - == checks whether variables point to objects of the same value\n",
    "  - is checks whether variables point to the same object\n",
    "  - use y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value\n",
    "- Sequece Type\n",
    "  - Tuple\n",
    "    - A simple immutable ordered sequence of items of mixed types\n",
    "    - Immutable: a tuple cannot be modified once created\n",
    "    - Items can be of mixed types, including collection types\n",
    "  - Strings\n",
    "    - Immutable\n",
    "    - \"_\".join(words)\n",
    "  - List\n",
    "    - Mutable ordered sequence of items of mixed types\n",
    "- Dict\n",
    "  - Dictionaries are unordered & work by hashing, so keys must be immutable\n",
    "  - Constant average time add, lookup, update\n",
    "    - key: keys, values: value stored in key, items: list of (key,value) tuple\n",
    "- function\n",
    "  - Python allows you to multiple values with type tuple\n",
    "  - no overloading, specified by name alone\n",
    "  - operator overloading is possible in class\n",
    "  - can provide default value, so some argument can be optional\n",
    "  - can be called out of order with keyword specified\n",
    "  - *args accept a variable number of non-keyword arguments to your function.\n",
    "  - **kwargs a variable number of keyword arguments to your function.\n",
    "  - function are first class object\n",
    "- Class\n",
    "  - A class can extend the definition of another class\n",
    "  - To define a subclass, class AI_Student(Student): fav_class = \"CIS 521”\n",
    "  - Multiple inheritance is supported\n",
    "  - constructor __init__:\n",
    "    - Must be done explicitly\n",
    "    - method override\n",
    "- Genrator:\n",
    "  - Functions that contain the yield keyword automatically return a generator when called\n",
    "  - and then it stops and returns the value that was yielded resumes where it left off\n",
    "\"\"\"\n",
    "\n",
    "# Each definition should be at most 20 words long.\n",
    "module2_definitions = {\n",
    "\"mutability\" : \"can be changed after assign\",\n",
    "\"indentation\":\"tab space \"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "ydOK__lwWgdp",
    "outputId": "149607b1-43de-4ab4-aa01-b15506fe0664"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       "\n",
       "- Strong Typing\n",
       "  - Every object has a fixed type, interpreter doesn’t allow things incompatible with\n",
       "    - that type (eg. “foo” + 2)\n",
       "  - python uses dynamic typing, Variables come into existence when first assigned\n",
       "  - If assigned again, type(var) is updated\n",
       "- String\n",
       "  - Creation\n",
       "    - Can use either single or double quotes, Triple quote for multiline string and docstring\n",
       "  - Concatenating strings\n",
       "    - By separating string literals with whitespace Special use of ‘+’\n",
       "  - Prefixing with r means raw.\n",
       "    - No need to escape special characters: r’\n",
       "’\n",
       "  - String formatting\n",
       "    - Special use of ‘%’ (as in printf in C)\n",
       "  - Immutable\n",
       "- Reference and Mutability\n",
       "  - x = x.strip() # new obj\n",
       "  - == checks whether variables point to objects of the same value\n",
       "  - is checks whether variables point to the same object\n",
       "  - use y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value\n",
       "- Sequece Type\n",
       "  - Tuple\n",
       "    - A simple immutable ordered sequence of items of mixed types\n",
       "    - Immutable: a tuple cannot be modified once created\n",
       "    - Items can be of mixed types, including collection types\n",
       "  - Strings\n",
       "    - Immutable\n",
       "    - \"_\".join(words)\n",
       "  - List\n",
       "    - Mutable ordered sequence of items of mixed types\n",
       "- Dict\n",
       "  - Dictionaries are unordered & work by hashing, so keys must be immutable\n",
       "  - Constant average time add, lookup, update\n",
       "    - key: keys, values: value stored in key, items: list of (key,value) tuple\n",
       "- function\n",
       "  - Python allows you to multiple values with type tuple\n",
       "  - no overloading, specified by name alone\n",
       "  - operator overloading is possible in class\n",
       "  - can provide default value, so some argument can be optional\n",
       "  - can be called out of order with keyword specified\n",
       "  - *args accept a variable number of non-keyword arguments to your function.\n",
       "  - **kwargs a variable number of keyword arguments to your function.\n",
       "  - function are first class object\n",
       "- Class\n",
       "  - A class can extend the definition of another class\n",
       "  - To define a subclass, class AI_Student(Student): fav_class = \"CIS 521”\n",
       "  - Multiple inheritance is supported\n",
       "  - constructor __init__:\n",
       "    - Must be done explicitly\n",
       "    - method override\n",
       "- Genrator:\n",
       "  - Functions that contain the yield keyword automatically return a generator when called\n",
       "  - and then it stops and returns the value that was yielded resumes where it left off\n",
       "\n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Mutability** - can be changed after assign\n",
       "* **Indentation** - tab space \n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "\n",
    "module2_sections = [\n",
    "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
    "]\n",
    "\n",
    "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
    "display(Markdown(module2_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "46MQLR-Gx8dZ"
   },
   "source": [
    "#Module 3 - Search Problems"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "BN0b1eVYx-nd"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
    "chapter3_1 = \"\"\" \n",
    "- Problem-solving agents use atomic representations, states of the world are considered as wholes, with no internal structure visible to the  problem-solving algorithms.\n",
    "- Agents that use factored or structured representations of states  are called planning agents\n",
    "- For known environment\n",
    "  - Goal formulation \n",
    "  - Problem formulation\n",
    "  - Search\n",
    "  - Execution\n",
    "- It is an important property that in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions\n",
    "  - open loop for above situation\n",
    "  - closed loop if the evironment nondeterministic or model is incorrect\n",
    "- If is an important property that in a partially observable, nondeterministic environment, The solution must recommend different future actions depending on the what percepts it receives. This could be in the form of a branching strategy.\n",
    "- Search problem can be defined:\n",
    "  - A set of possible states that the environment can be in. We call this the state space.\n",
    "  - The initial state that the agent starts in.\n",
    "  - A set of one or more goal states, and check for goal.\n",
    "  - The actions available to the agent.\n",
    "  - A transition model, which describes what each action does.\n",
    "  - An action cost function, A problem-solving agent should use a cost function that  reflects its own performance measure\n",
    "\"\"\"\n",
    "chapter3_2 = \"\"\" \n",
    "- A standardized problem is intended to illustrate or exercise various problem-solving methods.\n",
    "  - grid world, vaccum world\n",
    "  - sliding-tile puzzle\n",
    "- A real-world problem, such as robot  navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic\n",
    "  - route finding\n",
    "  - VLSI layout\n",
    "  - Touring problem\n",
    "  - RObot navigation\n",
    "  - Assembly sequencing\n",
    "\"\"\"\n",
    "\n",
    "chapter3_3 = \"\"\" \n",
    "- strategy determines search process\n",
    "- <strong>state vs. nodes</strong>: \n",
    "  - state = physical configuration\n",
    "  - node = a data structure constitiing part of search tree\n",
    "- search algorithm takes a search problem as input and returns a solution, or an indication of failure.\n",
    "- Best-first search : generalized greedy best first, A* and dijkstra. with f(n)\n",
    "- Queue for search algo:\n",
    "  - priority queue: pop first minimal cost f(n), best-first\n",
    "  - FIFO: BFS\n",
    "  - LIFO: DFS\n",
    "- Redundant path, an algorithm that canbnot remember the past are doomed to repeat it:\n",
    "  - like best-fisrt, if we remember all the past states, we can detect redundant, and keep only the best path. Perferred when table of reaches states will fit in memory\n",
    "  - if it is impossible to have redudant then we save the memory and don't track\n",
    "    - <strong>graph search</strong> checks redundant\n",
    "    - <strong>tree-like search</strong> does not checks redundant\n",
    "- Algo performace measure:\n",
    "  - Completeness: guaranteed to find a solution when there is one, and to correctly report failure when there is not? \n",
    "  - Cost optimality: lowest path cost of all solutions?\n",
    "  - Time complexity: How long does it take to find a solution?\n",
    "  - Space complexity: How much memory is needed to perform the search?\n",
    "    - depth:d, number of action in an optimal solution\n",
    "    - braching factor:b, number of successor of a node that need to be considered\n",
    "  \"\"\"\n",
    "chapter3_4 = \"\"\" \n",
    "- exponentially complexity search problems cannot be solved by unifomed search for any but the smallest instances\n",
    "- <strong>BFS</strong>\n",
    "  - complete\n",
    "  - cost optimal for equal cost\n",
    "  - O(b^d)\n",
    "  - O(b^d)\n",
    "  - f(n) = depth of node \n",
    "  - can do early goal test\n",
    "  - always find a solution with minimal number of actions\n",
    "  - Memory requirements are a bigger problem for BFS than execution time\n",
    "- <strong>Dijkstra/ uniform-cost search</strong>:\n",
    "  - UCS = BFS with path cost\n",
    "  - complete, if action cost >0\n",
    "  - cost optimal\n",
    "  - O(b^(1+C*/e)), where C* = cpst of optimal solution, e = lower bound on the cost of each action \n",
    "  - O(b^(1+C*/e))\n",
    "  - (O(b^(d+1))) if action cost are equal, so similar to a BFS\n",
    "  - f(n) = action cost\n",
    "  - no redudant\n",
    "- <strong>DFS</strong>:\n",
    "  - not complete, can stuck in loop, complete if check for graph search\n",
    "  - not cost-optimal\n",
    "  - O(b^m)\n",
    "  - O(bm), where m is the maximum depth\n",
    "  - f(n) = negative of the depth\n",
    "  - DFS has much smaller need to memory, we don't track the reached table and the frontier is small\n",
    "  - Backtracking, expand one node at a time, if a solution not found back track to the previous node. space comlexity O(m)\n",
    "- <strong>depth limited search</strong>:\n",
    "  - imcomplete, if solution cannot be find with depth limit, l\n",
    "  - not optimal\n",
    "  - O(b^l)\n",
    "  - O(bl)\n",
    "  - set l to the diameter of the state-space, where diameter is the maximum allowable actions\n",
    "- <strong>iterative deepening search</strong>\n",
    "  - complete\n",
    "  - optimal if actional cost is 1\n",
    "  - O(b^d)\n",
    "  - O(bd)\n",
    "  - In general, iterative deepening is the preferred  uninformed search method when the search state space is larger than can fit in memory and  the depth of the solution is not known. \n",
    "- <strong>bidirectional search</strong>\n",
    "  - complete\n",
    "  - optimal\n",
    "  - O(b^(d/2))\n",
    "  - O(b^(d/2))\n",
    "- <strong>BFS vs DFS</strong>:\n",
    "  - Use BFS: possible infinite path, some solutions have short paths and can quickly discard unlikely path\n",
    "  - Use DFS: space is restricted, many possible solutions with long paths and wrong path are terminated quickly\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module3_lecture_notes = \"\"\"\n",
    "- Before an agent can start searching, a well-defined problem must be formulated.\n",
    "- A problem consists of five parts: the initial state, a set of actions, a transition model  describing the results of those actions, a set of goal states, and an action cost function.\n",
    "- The environment of the problem is represented by a state space graph. A path through  the state space (a sequence of actions) from the initial state to a goal state is a solution.\n",
    "- Search algorithms generally treat states and actions as atomic, without any internal  structure (although we introduced features of states when it came time to do learning).\n",
    "- Search algorithms are judged on the basis of completeness, cost optimality, time complexity, and space complexity.\n",
    "- Uninformed search methods have access only to the problem definition. Algorithms  build a search tree in an attempt to find a solution. Algorithms differ based on which  node they expand first:\n",
    "  - Best-first search selects nodes for expansion using to an evaluation function.\n",
    "  - Breadth-first search expands the shallowest nodes first; it is complete, optimal  for unit action costs, but has exponential space complexity.  \n",
    "  - Uniform-cost search expands the node with lowest path cost, g(n), and is optimal  for general action costs.  \n",
    "  - Depth-first search expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity. Depth-limited search adds a  depth bound.  \n",
    "  - Iterative deepening search calls depth-first search with increasing depth limits  until a goal is found. It is complete when full cycle checking is done, optimal for  unit action costs, has time complexity comparable to breadth-first search, and has  linear space complexity.  \n",
    "  - Bidirectional search expands two frontiers, one around the initial state and one  around the goal, stopping when the two frontiers meet. \"\"\"\n",
    "\n",
    "# Definitions of concepts from Module 3.\n",
    "# You can define any bolded term in the textbook, \n",
    "# but you most use your own words for the definitions.\n",
    "# Each definition should be at most 20 words long.\n",
    "module3_definitions = {\n",
    "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
    "\"State space\":\"the set of all states reachable from the initial state by any sequence of actions\",    \n",
    "\"path\":\"a sequence of actions\",\n",
    "\"solution\":\"a path from initial state to a goal state\",\n",
    "\"optimal solution\":\"the lowest path cost among all solutions.\",\n",
    "\"graph\":\"verticies are the state and edge are actions\",\n",
    "\"tree\": \"nodes are the state and edge are actions\",\n",
    "\"evaluation function\":\"f(n), cost + heuristic\",\n",
    "\"systematic\":\"explores an infinite state space, making sure eventually reach any state that is connected to the initial state. \",\n",
    "\"early goal test\":\"check whather a node is a solution as soon as it is generated for BFS\"\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "lvtN3p7ET3Tx",
    "outputId": "7a1e4e78-8148-405b-e00e-2d054d137de8"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       " \n",
       "- Problem-solving agents use atomic representations, states of the world are considered as wholes, with no internal structure visible to the  problem-solving algorithms.\n",
       "- Agents that use factored or structured representations of states  are called planning agents\n",
       "- For known environment\n",
       "  - Goal formulation \n",
       "  - Problem formulation\n",
       "  - Search\n",
       "  - Execution\n",
       "- It is an important property that in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions\n",
       "  - open loop for above situation\n",
       "  - closed loop if the evironment nondeterministic or model is incorrect\n",
       "- If is an important property that in a partially observable, nondeterministic environment, The solution must recommend different future actions depending on the what percepts it receives. This could be in the form of a branching strategy.\n",
       "- Search problem can be defined:\n",
       "  - A set of possible states that the environment can be in. We call this the state space.\n",
       "  - The initial state that the agent starts in.\n",
       "  - A set of one or more goal states, and check for goal.\n",
       "  - The actions available to the agent.\n",
       "  - A transition model, which describes what each action does.\n",
       "  - An action cost function, A problem-solving agent should use a cost function that  reflects its own performance measure\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       " \n",
       "- A standardized problem is intended to illustrate or exercise various problem-solving methods.\n",
       "  - grid world, vaccum world\n",
       "  - sliding-tile puzzle\n",
       "- A real-world problem, such as robot  navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic\n",
       "  - route finding\n",
       "  - VLSI layout\n",
       "  - Touring problem\n",
       "  - RObot navigation\n",
       "  - Assembly sequencing\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       " \n",
       "- strategy determines search process\n",
       "- <strong>state vs. nodes</strong>: \n",
       "  - state = physical configuration\n",
       "  - node = a data structure constitiing part of search tree\n",
       "- search algorithm takes a search problem as input and returns a solution, or an indication of failure.\n",
       "- Best-first search : generalized greedy best first, A* and dijkstra. with f(n)\n",
       "- Queue for search algo:\n",
       "  - priority queue: pop first minimal cost f(n), best-first\n",
       "  - FIFO: BFS\n",
       "  - LIFO: DFS\n",
       "- Redundant path, an algorithm that canbnot remember the past are doomed to repeat it:\n",
       "  - like best-fisrt, if we remember all the past states, we can detect redundant, and keep only the best path. Perferred when table of reaches states will fit in memory\n",
       "  - if it is impossible to have redudant then we save the memory and don't track\n",
       "    - <strong>graph search</strong> checks redundant\n",
       "    - <strong>tree-like search</strong> does not checks redundant\n",
       "- Algo performace measure:\n",
       "  - Completeness: guaranteed to find a solution when there is one, and to correctly report failure when there is not? \n",
       "  - Cost optimality: lowest path cost of all solutions?\n",
       "  - Time complexity: How long does it take to find a solution?\n",
       "  - Space complexity: How much memory is needed to perform the search?\n",
       "    - depth:d, number of action in an optimal solution\n",
       "    - braching factor:b, number of successor of a node that need to be considered\n",
       "  \n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       " \n",
       "- exponentially complexity search problems cannot be solved by unifomed search for any but the smallest instances\n",
       "- <strong>BFS</strong>\n",
       "  - complete\n",
       "  - cost optimal for equal cost\n",
       "  - O(b^d)\n",
       "  - O(b^d)\n",
       "  - f(n) = depth of node \n",
       "  - can do early goal test\n",
       "  - always find a solution with minimal number of actions\n",
       "  - Memory requirements are a bigger problem for BFS than execution time\n",
       "- <strong>Dijkstra/ uniform-cost search</strong>:\n",
       "  - UCS = BFS with path cost\n",
       "  - complete, if action cost >0\n",
       "  - cost optimal\n",
       "  - O(b^(1+C*/e)), where C* = cpst of optimal solution, e = lower bound on the cost of each action \n",
       "  - O(b^(1+C*/e))\n",
       "  - (O(b^(d+1))) if action cost are equal, so similar to a BFS\n",
       "  - f(n) = action cost\n",
       "  - no redudant\n",
       "- <strong>DFS</strong>:\n",
       "  - not complete, can stuck in loop, complete if check for graph search\n",
       "  - not cost-optimal\n",
       "  - O(b^m)\n",
       "  - O(bm), where m is the maximum depth\n",
       "  - f(n) = negative of the depth\n",
       "  - DFS has much smaller need to memory, we don't track the reached table and the frontier is small\n",
       "  - Backtracking, expand one node at a time, if a solution not found back track to the previous node. space comlexity O(m)\n",
       "- <strong>depth limited search</strong>:\n",
       "  - imcomplete, if solution cannot be find with depth limit, l\n",
       "  - not optimal\n",
       "  - O(b^l)\n",
       "  - O(bl)\n",
       "  - set l to the diameter of the state-space, where diameter is the maximum allowable actions\n",
       "- <strong>iterative deepening search</strong>\n",
       "  - complete\n",
       "  - optimal if actional cost is 1\n",
       "  - O(b^d)\n",
       "  - O(bd)\n",
       "  - In general, iterative deepening is the preferred  uninformed search method when the search state space is larger than can fit in memory and  the depth of the solution is not known. \n",
       "- <strong>bidirectional search</strong>\n",
       "  - complete\n",
       "  - optimal\n",
       "  - O(b^(d/2))\n",
       "  - O(b^(d/2))\n",
       "- <strong>BFS vs DFS</strong>:\n",
       "  - Use BFS: possible infinite path, some solutions have short paths and can quickly discard unlikely path\n",
       "  - Use DFS: space is restricted, many possible solutions with long paths and wrong path are terminated quickly\n",
       "\n",
       "\n",
       "## Module 3 Lecture Notes\n",
       "\n",
       "- Before an agent can start searching, a well-defined problem must be formulated.\n",
       "- A problem consists of five parts: the initial state, a set of actions, a transition model  describing the results of those actions, a set of goal states, and an action cost function.\n",
       "- The environment of the problem is represented by a state space graph. A path through  the state space (a sequence of actions) from the initial state to a goal state is a solution.\n",
       "- Search algorithms generally treat states and actions as atomic, without any internal  structure (although we introduced features of states when it came time to do learning).\n",
       "- Search algorithms are judged on the basis of completeness, cost optimality, time complexity, and space complexity.\n",
       "- Uninformed search methods have access only to the problem definition. Algorithms  build a search tree in an attempt to find a solution. Algorithms differ based on which  node they expand first:\n",
       "  - Best-first search selects nodes for expansion using to an evaluation function.\n",
       "  - Breadth-first search expands the shallowest nodes first; it is complete, optimal  for unit action costs, but has exponential space complexity.  \n",
       "  - Uniform-cost search expands the node with lowest path cost, g(n), and is optimal  for general action costs.  \n",
       "  - Depth-first search expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity. Depth-limited search adds a  depth bound.  \n",
       "  - Iterative deepening search calls depth-first search with increasing depth limits  until a goal is found. It is complete when full cycle checking is done, optimal for  unit action costs, has time complexity comparable to breadth-first search, and has  linear space complexity.  \n",
       "  - Bidirectional search expands two frontiers, one around the initial state and one  around the goal, stopping when the two frontiers meet. \n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "* **State space** - the set of all states reachable from the initial state by any sequence of actions\n",
       "* **Path** - a sequence of actions\n",
       "* **Solution** - a path from initial state to a goal state\n",
       "* **Optimal solution** - the lowest path cost among all solutions.\n",
       "* **Graph** - verticies are the state and edge are actions\n",
       "* **Tree** - nodes are the state and edge are actions\n",
       "* **Evaluation function** - f(n), cost + heuristic\n",
       "* **Systematic** - explores an infinite state space, making sure eventually reach any state that is connected to the initial state. \n",
       "* **Early goal test** - check whather a node is a solution as soon as it is generated for BFS\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module3_sections = [\n",
    "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
    "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
    "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
    "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
    "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
    "]\n",
    "\n",
    "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
    "display(Markdown(module3_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WHREsHSSyA-h"
   },
   "source": [
    "#Module 4 - Informed Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "tuFC8w7CyCns"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
    "chapter3_5 = \"\"\" \n",
    "- heuristic admissible if consistent, but not vice versa  \n",
    "-<strong>informed search strategy</strong>: search strategy—one that uses domain-specific hints about the location of goals—can find solutions more efficiently than an uninformed strategy.\n",
    "  - h(n) = estimated cost of the cheapest path from the state at node n to a goal state. \n",
    "- <strong>Greedy best-first search</strong>:\n",
    "  - f(n) = h(n)\n",
    "  - complete in finite SS\n",
    "  - not optimal\n",
    "  - O(|V|) worst case, O(bm) for good h(n)\n",
    "  - O(|V|) worst case, O(bm) for good h(n)\n",
    "- <strong>A* search</strong>:\n",
    "  - f(n) = g(n)+h(n)\n",
    "  - complete\n",
    "  - optimal if admissible heuristic\n",
    "  - O(|E|) worst case = O(b^d)\n",
    "  - O(|V|) worst case = O(b^d)\n",
    "  - prunes away nodes that are not necessary for an optimal solution\n",
    "  - if h(n) is admissible, A* with tree search is optimal\n",
    "- <strong>weighted A* search and inadmissible heuristics</strong>:\n",
    "  - stisficing solution: the solution is good enough\n",
    "  - f(n) = g(n) + W*h(n), W>1\n",
    "  - weighted A* can search much faster with slightly higher path cost\n",
    "  - some variants:\n",
    "    - bounded suboptimal search: look for a solution that is guaranteed to be within a constant factor W of the optimal cost.\n",
    "    - bounded-cost search: solution whose cost is less  than some constant C\n",
    "    - unbounded-cost search: we accept a solution of any cost, find it quickly.\n",
    "- <strong>memory-bounded search</strong>:\n",
    "  - Beam search:\n",
    "    - limit size of frontier, keep k of best f-score\n",
    "    - run faster, less memory, as it keeps and expands less frontiers\n",
    "    - suboptimal, incomplete\n",
    "  - Interative deepening A*:\n",
    "    - cut of f-score \n",
    "    - visit some states multiple times, but use less memory\n",
    "    - keep one value at a time\n",
    "  - recursive best -first search:\n",
    "    - RBFS resembles a recursive depth-  first search, but rather than continuing indefinitely down the current path, it uses the f limit  variable to keep track of the f-value of the best alternative path available from any ancestor  of the current node.\n",
    "    - more efficient that IDA, but still regenerate nodes\n",
    "    - linear memory use\n",
    "  - SMA*\n",
    "    - like A* drop worst leaf node if memory is full\n",
    "    - if f-score equal, drop the oldest\n",
    "    - optimal and complete is reachable\n",
    "    - become A* if infinite memeory\n",
    "    - memory limitations can make a problem intractable from the point of view of computation time\n",
    "- <strong>bidirectional search</strong>:\n",
    "  - no longer optimal with only f(n) even admissible\n",
    "\"\"\"\n",
    "chapter3_6 = \"\"\"\n",
    "- effective braching factor, b*: is the branching factor that a uniform tree of depth d would have to have in order to contain N +1 nodes.\n",
    "  - good h(n) will have b* close 1\n",
    "  - good heuritic will consistently alwawys better than bad one, \n",
    "    - good heuristic dominates bad heuristic,\n",
    "    - good h(n) will never expand more nodes than bad h(n)\n",
    "    - good h(n)>bad h(n)\n",
    "- On dominance:\n",
    "  - h*(n) = oracle heuristic, where h*(n)= c*\n",
    "  - h*(n)>=h(n)>=0\n",
    "- Generate h(n) from relaxed problems:\n",
    "  - a relaxed  problem: A problem with fewer restrictions on the actions\n",
    "  - any optimal solution in  the original problem is, by definition, also a solution in the relaxed problem\n",
    "  - relaxed problem may have better solutions if the added edges provide shortcuts. Hence, the cost of  an optimal solution to a relaxed problem is an admissible heuristic for the original problem. \n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module4_lecture_notes = \"\"\"\n",
    "- Informed search methods have access to a heuristic function h(n) that estimates the  cost of a solution from n. They may have access to additional information such as  pattern databases with solution costs. \n",
    "  - Greedy best-first search expands nodes with minimal h(n). It is not optimal but  is often efficient.  \n",
    "  - A∗ search expands nodes with minimal f(n) = g(n) + h(n). A∗ is complete and  optimal, provided that h(n) is admissible. The space complexity of A∗ is still an  issue for many problems.  \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 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 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",
    "- The performance of heuristic search algorithms depends on the quality of the heuristic  function. One can sometimes construct good heuristics by relaxing the problem definition, by storing precomputed solution costs for subproblems in a pattern database, by  defining landmarks, or by learning from experience with the problem class. \n",
    "\"\"\"\n",
    "\n",
    "# Definitions\n",
    "module4_definitions = {\n",
    "\"admissible heuristic\" : \"one that never  overestimates the cost to reach a goal.\",    \n",
    "\"optimistic\":\"admissible\",\n",
    "\"consistency\":\"every node n and every successor n' of n generated by an action a, we have: $h(n) \\leq c(n,a,n')+h(n')$ (tria,ineq)\",\n",
    "\"monotonic\":\"monotonic: the path cost always increases as you go along a path, if action costs are always positive.\",\n",
    "\"optimally efficient\":\"with consistent heuristic, expand once\",\n",
    "\"reference counts\":\"number of times a state has been reached\",\n",
    "\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "vqtEs0gHs9sO",
    "outputId": "c7c8c60a-c5f6-41ac-f3e1-ab6fa718f811"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       " \n",
       "- heuristic admissible if consistent, but not vice versa  \n",
       "-<strong>informed search strategy</strong>: search strategy—one that uses domain-specific hints about the location of goals—can find solutions more efficiently than an uninformed strategy.\n",
       "  - h(n) = estimated cost of the cheapest path from the state at node n to a goal state. \n",
       "- <strong>Greedy best-first search</strong>:\n",
       "  - f(n) = h(n)\n",
       "  - complete in finite SS\n",
       "  - not optimal\n",
       "  - O(|V|) worst case, O(bm) for good h(n)\n",
       "  - O(|V|) worst case, O(bm) for good h(n)\n",
       "- <strong>A* search</strong>:\n",
       "  - f(n) = g(n)+h(n)\n",
       "  - complete\n",
       "  - optimal if admissible heuristic\n",
       "  - O(|E|) worst case = O(b^d)\n",
       "  - O(|V|) worst case = O(b^d)\n",
       "  - prunes away nodes that are not necessary for an optimal solution\n",
       "  - if h(n) is admissible, A* with tree search is optimal\n",
       "- <strong>weighted A* search and inadmissible heuristics</strong>:\n",
       "  - stisficing solution: the solution is good enough\n",
       "  - f(n) = g(n) + W*h(n), W>1\n",
       "  - weighted A* can search much faster with slightly higher path cost\n",
       "  - some variants:\n",
       "    - bounded suboptimal search: look for a solution that is guaranteed to be within a constant factor W of the optimal cost.\n",
       "    - bounded-cost search: solution whose cost is less  than some constant C\n",
       "    - unbounded-cost search: we accept a solution of any cost, find it quickly.\n",
       "- <strong>memory-bounded search</strong>:\n",
       "  - Beam search:\n",
       "    - limit size of frontier, keep k of best f-score\n",
       "    - run faster, less memory, as it keeps and expands less frontiers\n",
       "    - suboptimal, incomplete\n",
       "  - Interative deepening A*:\n",
       "    - cut of f-score \n",
       "    - visit some states multiple times, but use less memory\n",
       "    - keep one value at a time\n",
       "  - recursive best -first search:\n",
       "    - RBFS resembles a recursive depth-  first search, but rather than continuing indefinitely down the current path, it uses the f limit  variable to keep track of the f-value of the best alternative path available from any ancestor  of the current node.\n",
       "    - more efficient that IDA, but still regenerate nodes\n",
       "    - linear memory use\n",
       "  - SMA*\n",
       "    - like A* drop worst leaf node if memory is full\n",
       "    - if f-score equal, drop the oldest\n",
       "    - optimal and complete is reachable\n",
       "    - become A* if infinite memeory\n",
       "    - memory limitations can make a problem intractable from the point of view of computation time\n",
       "- <strong>bidirectional search</strong>:\n",
       "  - no longer optimal with only f(n) even admissible\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       "\n",
       "- effective braching factor, b*: is the branching factor that a uniform tree of depth d would have to have in order to contain N +1 nodes.\n",
       "  - good h(n) will have b* close 1\n",
       "  - good heuritic will consistently alwawys better than bad one, \n",
       "    - good heuristic dominates bad heuristic,\n",
       "    - good h(n) will never expand more nodes than bad h(n)\n",
       "    - good h(n)>bad h(n)\n",
       "- On dominance:\n",
       "  - h*(n) = oracle heuristic, where h*(n)= c*\n",
       "  - h*(n)>=h(n)>=0\n",
       "- Generate h(n) from relaxed problems:\n",
       "  - a relaxed  problem: A problem with fewer restrictions on the actions\n",
       "  - any optimal solution in  the original problem is, by definition, also a solution in the relaxed problem\n",
       "  - relaxed problem may have better solutions if the added edges provide shortcuts. Hence, the cost of  an optimal solution to a relaxed problem is an admissible heuristic for the original problem. \n",
       "\n",
       "\n",
       "## Module 4 Lecture Notes\n",
       "\n",
       "- Informed search methods have access to a heuristic function h(n) that estimates the  cost of a solution from n. They may have access to additional information such as  pattern databases with solution costs. \n",
       "  - Greedy best-first search expands nodes with minimal h(n). It is not optimal but  is often efficient.  \n",
       "  - A∗ search expands nodes with minimal f(n) = g(n) + h(n). A∗ is complete and  optimal, provided that h(n) is admissible. The space complexity of A∗ is still an  issue for many problems.  \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 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 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",
       "- The performance of heuristic search algorithms depends on the quality of the heuristic  function. One can sometimes construct good heuristics by relaxing the problem definition, by storing precomputed solution costs for subproblems in a pattern database, by  defining landmarks, or by learning from experience with the problem class. \n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Admissible heuristic** - one that never  overestimates the cost to reach a goal.\n",
       "* **Optimistic** - admissible\n",
       "* **Consistency** - every node n and every successor n' of n generated by an action a, we have: $h(n) \\leq c(n,a,n')+h(n')$ (tria,ineq)\n",
       "* **Monotonic** - monotonic: the path cost always increases as you go along a path, if action costs are always positive.\n",
       "* **Optimally efficient** - with consistent heuristic, expand once\n",
       "* **Reference counts** - number of times a state has been reached\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module4_sections = [\n",
    "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
    "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
    "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
    "]\n",
    "\n",
    "module4_markdown = format_module(4, \"Informed Search\", \n",
    "                         module4_sections, \n",
    "                         module4_definitions)\n",
    "display(Markdown(module4_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F3FPMzG9yUls"
   },
   "source": [
    "#Module 5 - Adversarial Search and Games"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "id": "iEIOpL7vyWcc"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
    "chapter5_1 = \"\"\" \n",
    "- Stances toward multi-agent environments:\n",
    "  - where a large number of agents, to consider them in aggregate as an economy, eg pridit increasin gdemand without considering individual agent \n",
    "  - consider adversarial agent as just a part of the enviornmentr -a that makes the environment nondeterministic\n",
    "  - as game-tree search, which is covered\n",
    "- apply evaluation function to estimate who is einning based on feature of the game\n",
    "- Analogy of game to search:\n",
    "  - perfect information - fully observable\n",
    "  - move - action\n",
    "  - position - state\n",
    "  - result - transition model \n",
    "- Game tree:\n",
    "  - nodes: bopard position\n",
    "  - edge: legal moves\n",
    "  - All play is from max's advantage point\n",
    "  - Max moves attempt to max its outcome, min try to minimize\n",
    "    - even level: turn for max\n",
    "    - off level: turn for min\n",
    "- Evaluation function f assigns real-number scores to `board positions’ without reference to path\n",
    "  - how good a board position is\n",
    "  - based on feature alone\n",
    "    - f(n)>0 winning for max\n",
    "- Game definition:\n",
    "  - Initial state: state, which specifies how the game is set up at the start. \n",
    "  - TO_MOVE: the player whose turn it is to move in state s\n",
    "  - action, The set of legal moves in state s\n",
    "  - result: transition model, state resulting from taking action a in state s\n",
    "  - IS_terminal: a terminal trest, state where the game ends\n",
    "  - Utility: a utility function (objective function) where assign a value to the performace of the game\n",
    "- Initial states, action function and result function defines state space graph, a graph where the vertices are states\n",
    "\"\"\"\n",
    "chapter5_2 = \"\"\"\n",
    "- Minmax search:\n",
    "  - max strategy must be a conditional plan depends on each of min's move\n",
    "  - idesirable outcome must be guaranteed no matter what the other side does\n",
    "  - Minmax value:\n",
    "    - minmax value is the utility of being in that state assuming both players play optimally from there to the end of the game\n",
    "    - minmax value of a terminal state is just its utility\n",
    "  - minmax decision at the root is the optimal choice for Max because it leads to the state with the highest minimax value\n",
    "  - if other player does not play optimally, then it will do as well as if other play optimally\n",
    "    - but best minimax move is not the best move if play with suboptimal player\n",
    "- Minimax search algorithm:\n",
    "  - a variant of DFS\n",
    "  - time complexity: O(b^m), m is maximum depth of tree, b in # of legal moves\n",
    "  - space complexity: O(bm), for an algo that generate all actions at once, O(m) for algo generate action one at a time\n",
    "  - minimax has expponential complexity impractial for complex game.\n",
    "- Optimal decision in multi-player game:\n",
    "  - use vector value instead of minmax value\n",
    "  - For terminal states, this vector gives the utility of the state from each player’s  viewpoint.\n",
    "  - alliances could be a natural consequences of optimal stratgy\n",
    "- Alpha-beta pruning:\n",
    "  - The number of game states is exponential in the depth of the tree. alpha beta computing the correct  minimax decision without examining every state by pruning that make no difference to the outcome.\n",
    "  -  the value of the root and hence the minimax decision are independent of the  values of some leaves there fore can be pruned\n",
    "    - α =  the value of the best (i.e., highest-value) choice we have found so far at any choice point  along the path for MAX. Think: α = “at least.”  \n",
    "    - β = the value of the best (i.e., lowest-value) choice we have found so far at any choice point  along the path for MIN. Think: β = “at most.” \n",
    "  - dependent on the order in which the states are examined\n",
    "  - Best time complexity O(b^(m/2)), effective braching factor become sqrt(b)\n",
    "  - Random order generally has time complexity O(b^(3m/4))\n",
    "  - perfect ordering is not likely, but we can get close, to O(b^(m/2))\n",
    "- Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth, wide byt shallow\n",
    "- Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree. \n",
    "\"\"\"\n",
    "chapter5_3 = \"\"\"\n",
    "- apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal\n",
    "  - replace utility function with eval, that estimates a state's utility\n",
    "  - repalce terminal test with cutoff test\n",
    "  - eval(s,p) returns an estimates of expected utility of state s to player p\n",
    "    - for terminal state: eval = utility\n",
    "    - for other: utility(loss)<= eval <= utility(win)\n",
    "  - A good eval function\n",
    "    - easy to compute\n",
    "    - correlate with actual chances of winning (because we cut off  before we are able to determine the terminal state there will be uncertainty)\n",
    "  - Expected value = P(x)*x\n",
    "  - weighted linear function: a eval function, where is a score calculated based on material value\n",
    "- cut off search:\n",
    "  - first attempt:\n",
    "    - increment depth and return the eval function if a set depth is reached\n",
    "    - or use iteractive deepening search return the best result if computation time is reached\n",
    "    - but can lead to error due to uncertainty nature\n",
    "  - improved:\n",
    "    - evaluation function should be applied only to positions that are quiescent—that positions in which there is no pending move (such as a capturing the queen) that would wildly  swing the evaluation.\n",
    "    - horizon effect is more difficult to eliminate, arises when program program is facing  an opponent’s move that causes serious damage and is ultimately unavoidable, but can be  temporarily avoided by the use of delaying tactics.\n",
    "  - with singular extensions:\n",
    "    - moves that are “clearly better” than all other moves in a given position, even when the search would  normally be cut off at that point. contiune deepening the search. \n",
    "    - makes the tree  deeper, but because there are usually few singular extensions, the strategy does not add many  total nodes to the tree, and has proven to be effective in practice. \n",
    "- Forward pruning: prunes moves that appear to be poor moves, but might possibly be good Forward pruning  ones. will make error\n",
    "  - beam search: on each ply, consider  only a “beam” of the n best moves rather than considering all possible moves. but best moves may be pruned away\n",
    "  - late move reduction: works under the assumption that move ordering  has been done well, and therefore moves that appear later in the list of possible moves are  less likely to be good moves.\\\n",
    "  moves. But rather than pruning them away completely. can be revisited\n",
    "- search vs look up\n",
    "  - sometime human experience can be valuable we can look up in state space for best move\n",
    "  - can do first opening moves with look up and later with search\n",
    "\"\"\"\n",
    "chapter5_5 = \"\"\"\n",
    "- Uncertain outcomes controlled by chance, not an adversary\n",
    "- Stochastic games has unpredictability of real life by including a  random element, such as the throwing of dice.\n",
    "  - A game  tree in stochastic game must include chance nodes in addition to MAX and MIN nodes.\n",
    "  - expected value of a position: the weighted average over all Expected value  possible outcomes of the chance nodes.\n",
    "  - expectiminimax value for games with chance nodes, a generalization value  of the minimax value for deterministic games. (with the caveat that the legal moves for MAX and MIN will  depend on the outcome of the dice roll in the previous chance node )\n",
    "- expectiminimax:\n",
    "  - Values should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes\n",
    "    - Max nodes as in minimax search\n",
    "    - Chance nodes are like min nodes but the outcome is uncertain\n",
    "    - Calculate their expected utilities I.e. take weighted average (expectation) of children\n",
    "  - time complexity O(b^m n^m) because we need to consider the dice rolls, n number of distinct rolls\n",
    "  - no likely sequence of moves possibilities are multiplied enormously, and forming detailed plans of action becomes  pointless because the world probably will not play along.\n",
    "  - pruning is still possible by placing upper or lower bound on the utility values and prune away.\n",
    " \"\"\"\n",
    "\n",
    "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
    "chapter16_1 = \"\"\"\n",
    "- $ P(Result(a)=s')= \\sum_{s}^{} P(s)P(s'|s,a) $, which assumes epsidic\n",
    "- $ EU(a) = \\sum_{s'} P(Result(a)=s')U(s') $. expected utility\n",
    "- $ action = argmax EU(a) $, maximum expected utility, a prescription for intelligent behavior\n",
    "- All an  intelligent agent has to do is calculate the various quantities, maximize utility over its actions,  and away it goes. But this does not mean that the AI problem is solved by the definition!\n",
    "  - The MEU principle formalizes the general notion that an intelligent agent should “do the  right thing,” but does not operationalize that advice.\n",
    "  - percerption, learning and knowledge representaion, inference are also needed to compute,\n",
    "  - decision theory is not a panacea that solves the  AI problem—but it does provide the beginnings of a basic mathematical framework that is  general enough to define the AI problem. \n",
    "- 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",
    "chapter16_2 = \"\"\"\n",
    "- MEU is not the only rational way\n",
    "- basic preferences:\n",
    "  - $ (A\\succ B) $, agent prefers A over B\n",
    "  - $ (A \\sim B) $, no difference in perference\n",
    "  - $ (A \\succsim B) $, agent prefers A over B or no difference in perference\n",
    "- axioms of utility theory  list six constraints that we require any reasonable preference relation to obey: \n",
    "- <strong>Orderability</strong>, Given any two lotteries, a rational agent must either prefer one or else  rate them as equally preferable. That is, the agent cannot avoid deciding.\n",
    "  - Exactly one of $ (A\\succ B) $, $ (B \\succ A)$, or $ (A \\sim B) $ holds\n",
    "- <strong>Transitivity</strong>: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\n",
    "  - $ (A\\succ B) \\wedge (B \\succ C) \\Rightarrow (A \\succ C) $ holds\n",
    "- <strong>Continuity</strong>: 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.\n",
    "- <strong>Substitutability</strong>: 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\n",
    "- <strong>Monotonicity</strong>: 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). \n",
    "- <strong>Decomposability</strong>: Compound lotteries can be reduced to simpler ones using the laws of probability. it compresses two consecutive lotteries into a single equivalent lottery.\n",
    "- Rational preference lead to utility:\n",
    "- <strong>Existence of Utility Function</strong>:If an agent’s preferences obey the axioms of utility, then  there exists a function U such that U(A) > U(B) if and only if A is preferred to B, and  U(A) = U(B) if and only if the agent is indifferent between A and B. \n",
    "  - $U(A) > U(B) \\Leftrightarrow A \\succ B $  and  $ U(A) = U(B) \\Leftrightarrow A \\sim B$\n",
    "- <strong>Expected Utility of a Lottery</strong>: The utility of a lottery is the sum of the probability of  each outcome times the utility of that outcome. \n",
    "  - $ U([p_1,S_1;\\dots ; p_n,S_n]) = \\sum_{i} p_i U(S_i)$\n",
    "  - In other words, once the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined.\n",
    "  - Because the  outcome of a nondeterministic action is a lottery, agent can act rationally, consistently with its preferences—only by choosing an action that maximizes expected  utility\n",
    "\"\"\"\n",
    "chapter16_3 = \"\"\"\n",
    "- Normalized utilities: $ u_{bot} = 0, u_{top} = 1 $\n",
    "- standard lottery: $ [p,u_{top};(1-p),u_{bot}] $\n",
    "- expected monetary value (EMV):\n",
    "  - $ EMV = \\sum P(x)*Value(x)$\n",
    "  - Utility is not  directly proportional to monetary value, because the utility for your the momey you own is not the same\n",
    "  - utility of money plateaus at higher, deepening at lower\n",
    "- We will assume, kindly perhaps, that the estimates EU(a) are unbiased, but the real outcome will usually be significantly worse than we estimated,  even though the estimate was unbiased!\n",
    "- \n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module5_lecture_notes = \"\"\"\n",
    "- A game can be defined by the initial state (how the board is set up), the legal actions  in each state, the result of each action, a terminal test (which says when the game is  over), and a utility function that applies to terminal states to say who won and what the  final score is.\n",
    "- In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information, the minimax algorithm can select optimal moves by a depth-first enumeration  of the game tree. \n",
    "- The alpha–beta search algorithm computes the same optimal move as minimax, but  achieves much greater efficiency by eliminating subtrees that are provably irrelevant.\n",
    "- Usually, it is not feasible to consider the whole game tree (even with alpha–beta), so we  need to cut the search off at some point and apply a heuristic evaluation function that  estimates the utility of a state. \n",
    "- Many game programs precompute tables of best moves in the opening and endgame so  that they can look up a move rather than search.\n",
    "  - 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. \n",
    "- <strong>cont 16_2</strong>\n",
    "- The preceding theorems establish that (assuming the constraints on rational preferences)  a utility function exists for any rational agent. The theorems do not establish that the utility  function is unique.\n",
    "- As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal  utility function. \n",
    "- existence of a utility function that describes an agent’s  preference behavior does not necessarily mean that the agent is explicitly maximizing that  utility function in its own deliberations.\n",
    "  \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module5_definitions = {\n",
    "\"adversial search\":\"two or more agens have conflicting goals\",\n",
    "\"perfect information\" : \"fully observable\",\n",
    "\"zero sum\":\"one player wins the other one loses, no win win outcome\",\n",
    "\"game tree\":\"a search tree that follows every sequence of moves all the way to a terminal state.\",   \n",
    "\"ply\":\"unambiguously mean one move by one player, bringing us one level deeper in the game tree.\" ,\n",
    "\"killer move\":\"best move \",\n",
    "\"transposition\":\"different Transposition  permutations of the move sequence that end up in the same position\",\n",
    "\"cutoff\":\"replace terminal state cutoff test, return true if terminal, otherwise free to decide when to cut off the search\",\n",
    "\"feature\":\"categories and evaluates the equivalent class of the game, each class have the same value for each equivalent\",\n",
    "\"material value\": \"cost of each  pieces in chess\",\n",
    "\"lottery\":\"don't know what is coming\",\n",
    "\"preference elicitation\":\"involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\",\n",
    "\"risk-averse\":\"they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\",\n",
    "\"risk-seeking\":\"“desperate” region at large negative wealth, loss more money is fine\",\n",
    "\"normative theory\":\"describe how a rational agent should act.\",\n",
    "\"descriptive theory\":\"how a actual agent (human) would act\",\n",
    "\"certainty effect\":\"people are strongly attracted to gains that are certain\",\n",
    "\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "KUc_LgzDvWf-",
    "outputId": "fdcf8e36-06c5-4a30-fef9-1301ae01e5fe"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       " \n",
       "- Stances toward multi-agent environments:\n",
       "  - where a large number of agents, to consider them in aggregate as an economy, eg pridit increasin gdemand without considering individual agent \n",
       "  - consider adversarial agent as just a part of the enviornmentr -a that makes the environment nondeterministic\n",
       "  - as game-tree search, which is covered\n",
       "- apply evaluation function to estimate who is einning based on feature of the game\n",
       "- Analogy of game to search:\n",
       "  - perfect information - fully observable\n",
       "  - move - action\n",
       "  - position - state\n",
       "  - result - transition model \n",
       "- Game tree:\n",
       "  - nodes: bopard position\n",
       "  - edge: legal moves\n",
       "  - All play is from max's advantage point\n",
       "  - Max moves attempt to max its outcome, min try to minimize\n",
       "    - even level: turn for max\n",
       "    - off level: turn for min\n",
       "- Evaluation function f assigns real-number scores to `board positions’ without reference to path\n",
       "  - how good a board position is\n",
       "  - based on feature alone\n",
       "    - f(n)>0 winning for max\n",
       "- Game definition:\n",
       "  - Initial state: state, which specifies how the game is set up at the start. \n",
       "  - TO_MOVE: the player whose turn it is to move in state s\n",
       "  - action, The set of legal moves in state s\n",
       "  - result: transition model, state resulting from taking action a in state s\n",
       "  - IS_terminal: a terminal trest, state where the game ends\n",
       "  - Utility: a utility function (objective function) where assign a value to the performace of the game\n",
       "- Initial states, action function and result function defines state space graph, a graph where the vertices are states\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       "\n",
       "- Minmax search:\n",
       "  - max strategy must be a conditional plan depends on each of min's move\n",
       "  - idesirable outcome must be guaranteed no matter what the other side does\n",
       "  - Minmax value:\n",
       "    - minmax value is the utility of being in that state assuming both players play optimally from there to the end of the game\n",
       "    - minmax value of a terminal state is just its utility\n",
       "  - minmax decision at the root is the optimal choice for Max because it leads to the state with the highest minimax value\n",
       "  - if other player does not play optimally, then it will do as well as if other play optimally\n",
       "    - but best minimax move is not the best move if play with suboptimal player\n",
       "- Minimax search algorithm:\n",
       "  - a variant of DFS\n",
       "  - time complexity: O(b^m), m is maximum depth of tree, b in # of legal moves\n",
       "  - space complexity: O(bm), for an algo that generate all actions at once, O(m) for algo generate action one at a time\n",
       "  - minimax has expponential complexity impractial for complex game.\n",
       "- Optimal decision in multi-player game:\n",
       "  - use vector value instead of minmax value\n",
       "  - For terminal states, this vector gives the utility of the state from each player’s  viewpoint.\n",
       "  - alliances could be a natural consequences of optimal stratgy\n",
       "- Alpha-beta pruning:\n",
       "  - The number of game states is exponential in the depth of the tree. alpha beta computing the correct  minimax decision without examining every state by pruning that make no difference to the outcome.\n",
       "  -  the value of the root and hence the minimax decision are independent of the  values of some leaves there fore can be pruned\n",
       "    - α =  the value of the best (i.e., highest-value) choice we have found so far at any choice point  along the path for MAX. Think: α = “at least.”  \n",
       "    - β = the value of the best (i.e., lowest-value) choice we have found so far at any choice point  along the path for MIN. Think: β = “at most.” \n",
       "  - dependent on the order in which the states are examined\n",
       "  - Best time complexity O(b^(m/2)), effective braching factor become sqrt(b)\n",
       "  - Random order generally has time complexity O(b^(3m/4))\n",
       "  - perfect ordering is not likely, but we can get close, to O(b^(m/2))\n",
       "- Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth, wide byt shallow\n",
       "- Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree. \n",
       "\n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       "\n",
       "- apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal\n",
       "  - replace utility function with eval, that estimates a state's utility\n",
       "  - repalce terminal test with cutoff test\n",
       "  - eval(s,p) returns an estimates of expected utility of state s to player p\n",
       "    - for terminal state: eval = utility\n",
       "    - for other: utility(loss)<= eval <= utility(win)\n",
       "  - A good eval function\n",
       "    - easy to compute\n",
       "    - correlate with actual chances of winning (because we cut off  before we are able to determine the terminal state there will be uncertainty)\n",
       "  - Expected value = P(x)*x\n",
       "  - weighted linear function: a eval function, where is a score calculated based on material value\n",
       "- cut off search:\n",
       "  - first attempt:\n",
       "    - increment depth and return the eval function if a set depth is reached\n",
       "    - or use iteractive deepening search return the best result if computation time is reached\n",
       "    - but can lead to error due to uncertainty nature\n",
       "  - improved:\n",
       "    - evaluation function should be applied only to positions that are quiescent—that positions in which there is no pending move (such as a capturing the queen) that would wildly  swing the evaluation.\n",
       "    - horizon effect is more difficult to eliminate, arises when program program is facing  an opponent’s move that causes serious damage and is ultimately unavoidable, but can be  temporarily avoided by the use of delaying tactics.\n",
       "  - with singular extensions:\n",
       "    - moves that are “clearly better” than all other moves in a given position, even when the search would  normally be cut off at that point. contiune deepening the search. \n",
       "    - makes the tree  deeper, but because there are usually few singular extensions, the strategy does not add many  total nodes to the tree, and has proven to be effective in practice. \n",
       "- Forward pruning: prunes moves that appear to be poor moves, but might possibly be good Forward pruning  ones. will make error\n",
       "  - beam search: on each ply, consider  only a “beam” of the n best moves rather than considering all possible moves. but best moves may be pruned away\n",
       "  - late move reduction: works under the assumption that move ordering  has been done well, and therefore moves that appear later in the list of possible moves are  less likely to be good moves.  moves. But rather than pruning them away completely. can be revisited\n",
       "- search vs look up\n",
       "  - sometime human experience can be valuable we can look up in state space for best move\n",
       "  - can do first opening moves with look up and later with search\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       "\n",
       "- Uncertain outcomes controlled by chance, not an adversary\n",
       "- Stochastic games has unpredictability of real life by including a  random element, such as the throwing of dice.\n",
       "  - A game  tree in stochastic game must include chance nodes in addition to MAX and MIN nodes.\n",
       "  - expected value of a position: the weighted average over all Expected value  possible outcomes of the chance nodes.\n",
       "  - expectiminimax value for games with chance nodes, a generalization value  of the minimax value for deterministic games. (with the caveat that the legal moves for MAX and MIN will  depend on the outcome of the dice roll in the previous chance node )\n",
       "- expectiminimax:\n",
       "  - Values should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes\n",
       "    - Max nodes as in minimax search\n",
       "    - Chance nodes are like min nodes but the outcome is uncertain\n",
       "    - Calculate their expected utilities I.e. take weighted average (expectation) of children\n",
       "  - time complexity O(b^m n^m) because we need to consider the dice rolls, n number of distinct rolls\n",
       "  - no likely sequence of moves possibilities are multiplied enormously, and forming detailed plans of action becomes  pointless because the world probably will not play along.\n",
       "  - pruning is still possible by placing upper or lower bound on the utility values and prune away.\n",
       " \n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       "\n",
       "- $ P(Result(a)=s')= \\sum_{s}^{} P(s)P(s'|s,a) $, which assumes epsidic\n",
       "- $ EU(a) = \\sum_{s'} P(Result(a)=s')U(s') $. expected utility\n",
       "- $ action = argmax EU(a) $, maximum expected utility, a prescription for intelligent behavior\n",
       "- All an  intelligent agent has to do is calculate the various quantities, maximize utility over its actions,  and away it goes. But this does not mean that the AI problem is solved by the definition!\n",
       "  - The MEU principle formalizes the general notion that an intelligent agent should “do the  right thing,” but does not operationalize that advice.\n",
       "  - percerption, learning and knowledge representaion, inference are also needed to compute,\n",
       "  - decision theory is not a panacea that solves the  AI problem—but it does provide the beginnings of a basic mathematical framework that is  general enough to define the AI problem. \n",
       "- 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",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       "\n",
       "- MEU is not the only rational way\n",
       "- basic preferences:\n",
       "  - $ (A\\succ B) $, agent prefers A over B\n",
       "  - $ (A \\sim B) $, no difference in perference\n",
       "  - $ (A \\succsim B) $, agent prefers A over B or no difference in perference\n",
       "- axioms of utility theory  list six constraints that we require any reasonable preference relation to obey: \n",
       "- <strong>Orderability</strong>, Given any two lotteries, a rational agent must either prefer one or else  rate them as equally preferable. That is, the agent cannot avoid deciding.\n",
       "  - Exactly one of $ (A\\succ B) $, $ (B \\succ A)$, or $ (A \\sim B) $ holds\n",
       "- <strong>Transitivity</strong>: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\n",
       "  - $ (A\\succ B) \\wedge (B \\succ C) \\Rightarrow (A \\succ C) $ holds\n",
       "- <strong>Continuity</strong>: 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.\n",
       "- <strong>Substitutability</strong>: 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\n",
       "- <strong>Monotonicity</strong>: 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). \n",
       "- <strong>Decomposability</strong>: Compound lotteries can be reduced to simpler ones using the laws of probability. it compresses two consecutive lotteries into a single equivalent lottery.\n",
       "- Rational preference lead to utility:\n",
       "- <strong>Existence of Utility Function</strong>:If an agent’s preferences obey the axioms of utility, then  there exists a function U such that U(A) > U(B) if and only if A is preferred to B, and  U(A) = U(B) if and only if the agent is indifferent between A and B. \n",
       "  - $U(A) > U(B) \\Leftrightarrow A \\succ B $  and  $ U(A) = U(B) \\Leftrightarrow A \\sim B$\n",
       "- <strong>Expected Utility of a Lottery</strong>: The utility of a lottery is the sum of the probability of  each outcome times the utility of that outcome. \n",
       "  - $ U([p_1,S_1;\\dots ; p_n,S_n]) = \\sum_{i} p_i U(S_i)$\n",
       "  - In other words, once the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined.\n",
       "  - Because the  outcome of a nondeterministic action is a lottery, agent can act rationally, consistently with its preferences—only by choosing an action that maximizes expected  utility\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       "\n",
       "- Normalized utilities: $ u_{bot} = 0, u_{top} = 1 $\n",
       "- standard lottery: $ [p,u_{top};(1-p),u_{bot}] $\n",
       "- expected monetary value (EMV):\n",
       "  - $ EMV = \\sum P(x)*Value(x)$\n",
       "  - Utility is not  directly proportional to monetary value, because the utility for your the momey you own is not the same\n",
       "  - utility of money plateaus at higher, deepening at lower\n",
       "- We will assume, kindly perhaps, that the estimates EU(a) are unbiased, but the real outcome will usually be significantly worse than we estimated,  even though the estimate was unbiased!\n",
       "- \n",
       "\n",
       "\n",
       "## Module 5 Lecture Notes\n",
       "\n",
       "- A game can be defined by the initial state (how the board is set up), the legal actions  in each state, the result of each action, a terminal test (which says when the game is  over), and a utility function that applies to terminal states to say who won and what the  final score is.\n",
       "- In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information, the minimax algorithm can select optimal moves by a depth-first enumeration  of the game tree. \n",
       "- The alpha–beta search algorithm computes the same optimal move as minimax, but  achieves much greater efficiency by eliminating subtrees that are provably irrelevant.\n",
       "- Usually, it is not feasible to consider the whole game tree (even with alpha–beta), so we  need to cut the search off at some point and apply a heuristic evaluation function that  estimates the utility of a state. \n",
       "- Many game programs precompute tables of best moves in the opening and endgame so  that they can look up a move rather than search.\n",
       "  - 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. \n",
       "- <strong>cont 16_2</strong>\n",
       "- The preceding theorems establish that (assuming the constraints on rational preferences)  a utility function exists for any rational agent. The theorems do not establish that the utility  function is unique.\n",
       "- As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal  utility function. \n",
       "- existence of a utility function that describes an agent’s  preference behavior does not necessarily mean that the agent is explicitly maximizing that  utility function in its own deliberations.\n",
       "  \n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Adversial search** - two or more agens have conflicting goals\n",
       "* **Perfect information** - fully observable\n",
       "* **Zero sum** - one player wins the other one loses, no win win outcome\n",
       "* **Game tree** - a search tree that follows every sequence of moves all the way to a terminal state.\n",
       "* **Ply** - unambiguously mean one move by one player, bringing us one level deeper in the game tree.\n",
       "* **Killer move** - best move \n",
       "* **Transposition** - different Transposition  permutations of the move sequence that end up in the same position\n",
       "* **Cutoff** - replace terminal state cutoff test, return true if terminal, otherwise free to decide when to cut off the search\n",
       "* **Feature** - categories and evaluates the equivalent class of the game, each class have the same value for each equivalent\n",
       "* **Material value** - cost of each  pieces in chess\n",
       "* **Lottery** - don't know what is coming\n",
       "* **Preference elicitation** - involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\n",
       "* **Risk-averse** - they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\n",
       "* **Risk-seeking** - “desperate” region at large negative wealth, loss more money is fine\n",
       "* **Normative theory** - describe how a rational agent should act.\n",
       "* **Descriptive theory** - how a actual agent (human) would act\n",
       "* **Certainty effect** - people are strongly attracted to gains that are certain\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module5_sections = [\n",
    "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
    "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
    "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
    "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
    "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
    "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
    "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
    "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
    "]\n",
    "\n",
    "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
    "                         module5_sections, \n",
    "                         module5_definitions)\n",
    "display(Markdown(module5_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "qVSQhTVSyYYO"
   },
   "source": [
    "#Module 6 - \"Constraint Satisfaction Problems\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "Wm4mfW82yaRH"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
    "chapter6_1 = \"\"\"\n",
    "- The simplist CSP invovles variable that are discrete, finite, eg map color scheduling \n",
    "- discrete domain can be infinite\n",
    "- Represent the constraints that solutions must satisfy in a uniform declarative language\n",
    "- Find solutions by GENERAL PURPOSE search algorithms with no changes from problem to problem\n",
    "  - Just specify the problem in a formal declarative language, and a general-purpose algorithm does everything else!\n",
    "- CSP consist of:\n",
    "  - Finite set of variables\n",
    "  - Nonempty domain of possible values\n",
    "  - Finite set of constraints\n",
    "- Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP\n",
    "- benefit of CSP:\n",
    "  - Clean specification of many problems, generic goal, successor function & heuristics\n",
    "  - CSP “knows” which variables violate a constraint\n",
    "  - Automatically prune off all branches that violate constraints\n",
    "- constraint graph:\n",
    "  - nodes are variables\n",
    "  - arcs are constraints\n",
    "- CSP as search problem: a DFS, time space same as DFS\n",
    "  - Initial State: the empty assignment {}.\n",
    "  - Successor function: Assign value to any unassigned variable\n",
    "  - provided that there is not a constraint conflict.\n",
    "  - Goal test: the current assignment is complete.\n",
    "  - Path cost: a constant cost for every step.\n",
    "- forward checking:\n",
    "  - Keep track of remaining legal values for unassigned variables Terminate search when any unassigned variable has no remaining legal values\n",
    "\"\"\"\n",
    "chapter6_2 = \"\"\"\n",
    "- CSP solvers combine search and inference\n",
    "- local consistency: enforcing local  consistency in each part of the graph causes inconsistent values to be eliminated throughout  the graph.\n",
    "- node-consistent: node-consistent if all the  values in the variable’s domain satisfy the variable’s unary constraints.\n",
    "- arc consistency: if every value in its domain satisfies the variable’s  binary constraints.\n",
    "  - X -> Y is consistent iff for every value x of X there is some allowed y\n",
    "  - An arc (i,j) is arc consistent if and only if every value v on Xi is consistent with some label on Yj \n",
    "  -  To make an arc (i,j) arc consistent,for each value v on Xi ,if there is no label on Yj consistent with v, then remove v from Xi\n",
    "  - Given d values, checking arc (i,j) takes O(d^2) time worst case\n",
    "- AC3:reduce the domains of variables before we begin the search\n",
    "  - point, we are left  with a CSP that is equivalent to the original CSP—they both have the same solutions—but  the arc-consistent CSP will be faster to search because its variables have smaller domains. \n",
    "  - total arc O(n^2)\n",
    "  - Time complexity: O(d^2)\n",
    "  - worst time: O(nd^3), plannar -> O(nd^3)\n",
    "  - space O(e), where e is the number of arcs\n",
    "  - inefficiencies:\n",
    "    - At each iteration, we only need to examine those Xi where at least one neighbor of Xi has lost a value in the previous iteration.\n",
    "    - If Xi loses a value only because of arc inconsistencies with Yj, we don’t need to check Yj on the next iteration.\n",
    "- Path consistency: tightens the binary constraints by using implicit constraints  that are inferred by looking at triples of variables.\n",
    "  - A two-variable set {Xi ,Xj} is path-consistent with respect to a third variable Xm if, for  every assignment {Xi = a,Xj = b} consistent with the constraints (if any) on {Xi ,Xj}, there is  an assignment to Xm that satisfies the constraints on {Xi ,Xm} and {Xm,Xj}.\n",
    "- k consistent: for any set of k−1 variables and for any consistent assignment to those variables,  a consistent value can always be assigned to any kth variable.\n",
    "  - 2 consistent = arc consistent\n",
    "  - 3-consistent = path consistent\n",
    "- satrongly k-consistent: k-consistent and is also (k−1)-consistent, (k−2)-  Strongly  k-consistent  consistent,... all the way down to 1-consistent.\n",
    "   -time O(n^2d). for k = n  \n",
    "- global constraint: involving an arbitrary number of variables (but not  necessarily all variables).\n",
    "- resource constraint, sometimes called the Atmost constraint.\n",
    "- bounds propagation: domains are represented by upper and lower  bounds\n",
    "\"\"\"\n",
    "chapter6_3 = \"\"\"\n",
    "- commutativity: commutative if the order of application of any given set of actions does Commutativity  not matter.\n",
    "- back track can be improved with h(n)\n",
    "  - ordering: choose the  variables in order,\n",
    "    - minimum-remaining-values: choosing the variable with the fewest “legal” values\n",
    "    - degree heuristic: when initially all remaining are equal, branching factor on future choices by selecting the variable  that is involved in the largest number of constraints on other unassigned variables.(choose most connected)\n",
    "    - least-constraining-value: prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. (leave the  maximum flexibility for subsequent variable assignments)\n",
    "  - inference can be even more powerful during the course of a search:every time we make  a choice of a value for a variable, we have a brand-new opportunity to infer new domain  reductions on the neighboring variables. \n",
    "    - 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. \n",
    "    - MRV with forward checking improve effciency\n",
    "    - forward checking detects many inconsistencies, it does not detect all of them.  The problem is that it doesn’t look ahead far enough.\n",
    "    - Maintaining Arc Consistency) detects inconsistencies like this.\n",
    "  - intelligent back tracking\n",
    "    - chronological backtracking only look back one step\n",
    "    - it can be shown  that every branch pruned by backjumping is also pruned by forward checking.\n",
    "    - conflict directed backjumping: use conflict set to backjump multiple steps\n",
    "      - let Xj be the current variable, and let conf(Xj) be its conflict  set. If every possible value for Xj fails, backjump to the most recent variable Xi in conf(Xj)\n",
    "  - Constraint learning is  the idea of finding a minimum set of variables from the conflict set that causes the problem. Avoid into conflict set again\n",
    "\"\"\"\n",
    "chapter6_4 = \"\"\"\n",
    "- min-conflict h(n)\n",
    "  - Min-conflicts is surprisingly effective for many CSPs\n",
    "  - run time of min-conflicts is roughly  independent of problem size.\n",
    "- 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.\n",
    "- <strong> start early 6.5</strong>\n",
    "- decomposition of graph to trees:\n",
    "  - need to satisfy:\n",
    "    - Every variable in the original problem appears in at least one of the tree nodes.\n",
    "    - If two variables are connected by a constraint in the original problem, they must appear  together (along with the constraint) in at least one of the tree nodes.\n",
    "    - If a variable appears in two nodes in the tree, it must appear in every node along the  path connecting those nodes. \n",
    "      - The first two conditions ensure that all the variables and constraints are represented in the  tree decomposition. The third condition seems rather technical, but allows us to say that  any variable from the original problem must have the same value wherever it appears: the  constraints in the tree say that a variable in one node of the tree must have the same value as  the corresponding variable in the adjacent node in the tree.\n",
    "    - time complexity O(nd^2), where n is the number of tree nodes and d is the size of the largest domain. \n",
    "    - The tree width of a tree decomposition of a graph is one less than the size of the largest node\n",
    "    - If a graph has tree width w then the  problem can be solved in O(nd^(w+1)) time\n",
    "      - CSPs with constraint graphs of bounded tree width are solvable in polynomial time.\n",
    "\"\"\"\n",
    "chapter6_5 = \"\"\"\n",
    "- split to individual small problems\n",
    "  - independent subproblems: solution in which is independent from other solutions\n",
    "    - found by checking connected components of the constraint graph.\n",
    "  - Then there are n/c subproblems, each of which takes at most d^c work to solve, where d is the size of the domain.total work is O(d^c n/c), without the decomposition, the total  work is O(d^n), which is exponential in n.\n",
    "  - completely seperable case are rare\n",
    "  - example, a constraint graph is a tree when  any two variables are connected by only one path.\n",
    "    - any tree-structured CSP can be solved in time linear in the number of variables.\n",
    "    - directional arc consistency if under an ordering of variables X1,X2,...,Xn if and only if every Xi is arcconsistent with each Xj for j > i. \n",
    "    - O(n) steps to make it directed\n",
    "    - total time of O(nd^2).\n",
    "- Cutset condition\n",
    "  - assigning values to some variables  so that the remaining variables form a tree\n",
    "  - any solution for the CSP after assigning a value to a node and its constraints are removed will be consistent  with the value chosen for the removed node\n",
    "  - the value chosen for removed node could be the wrong one, so we would need to try each  possible value.\n",
    "  - cycle cutset: S where Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree  after removal of S\n",
    "  - run time O(d^c ·(n−c)d^2)\n",
    "  - Finding the smallest cycle  cutset is NP-hard\n",
    "  - The overall  algorithmic approach is called cutset conditioning\n",
    "- cutset vs decomposition:\n",
    "  - time consideration favors tree decomposition, but the advantage of  the cycle-cutset approach is that it can be executed in linear memory, while tree decomposition requires memory exponential in w. \n",
    "- value symmetry: question often has multiple valid solutions\n",
    "  - symmetry-breaking constraint. For our example, we might constraint  impose an arbitrary ordering constraint\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Lecture notes \n",
    "module6_lecture_notes = \"\"\"\n",
    "- Constraint satisfaction problems (CSPs) represent a state with a set of variable/value  pairs and represent the conditions for a solution by a set of constraints on the variables.  Many important real-world problems can be described as CSPs.\n",
    "- A number of inference techniques use the constraints to rule out certain variable assignments. These include node, arc, path, and k-consistency.\n",
    "- Backtracking search, a form of depth-first search, is commonly used for solving CSPs.  Inference can be interwoven with search. \n",
    "- The minimum-remaining-values and degree heuristics are domain-independent methods for deciding which variable to choose next in a backtracking search. The leastconstraining-value heuristic helps in deciding which value to try first for a given  variable. Backtracking occurs when no legal assignment can be found for a variable.  Conflict-directed backjumping backtracks directly to the source of the problem. Constraint learning records the conflicts as they are encountered during search in order to  avoid the same conflict later in the search. \n",
    "- Local search using the min-conflicts heuristic has also been applied to constraint satisfaction problems with great success\n",
    "- The complexity of solving a CSP is strongly related to the structure of its constraint  graph. Tree-structured problems can be solved in linear time. 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 tree width 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",
    "\n",
    "# Definitions\n",
    "module6_definitions = {\n",
    "\"CSP\" : \"A problem is solved when each variable  has a value that satisfies all the constraints on the variable.\",\n",
    "\"consistent\":\"An assignment Assignments  that does not violate any constraints\",\n",
    "\"complete assignment\":\"every variable is assigned a value\",\n",
    "\"solution to CSP\":\"a consistent, complete assignment \",\n",
    "\"partial assignment\":\"leaves some variables Solution  unassigned\",\n",
    "\"a partial solution\":\"a partial assignment that is consistent\",\n",
    "\"precedence constraints\":\"order in which the task need to be executed\",\n",
    "\"linear programming \":\"constraints must  be linear equalities or inequalities.\",\n",
    "\"unary constraint\":\"restricts  the value of a single variable\",\n",
    "\"binary constraint\":\"relates two variables\",\n",
    "\"preference constraints\":\"which solutions are preferred\",\n",
    "\"constraint  propagation\":\"using constraints to reduce number of legal values for a variable, reduce the legal values for another variable.\"\n",
    "\n",
    "\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "kKWbCsbfxL3R",
    "outputId": "b90d180f-2579-4869-b3e5-487feda52aa7"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       "\n",
       "- The simplist CSP invovles variable that are discrete, finite, eg map color scheduling \n",
       "- discrete domain can be infinite\n",
       "- Represent the constraints that solutions must satisfy in a uniform declarative language\n",
       "- Find solutions by GENERAL PURPOSE search algorithms with no changes from problem to problem\n",
       "  - Just specify the problem in a formal declarative language, and a general-purpose algorithm does everything else!\n",
       "- CSP consist of:\n",
       "  - Finite set of variables\n",
       "  - Nonempty domain of possible values\n",
       "  - Finite set of constraints\n",
       "- Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP\n",
       "- benefit of CSP:\n",
       "  - Clean specification of many problems, generic goal, successor function & heuristics\n",
       "  - CSP “knows” which variables violate a constraint\n",
       "  - Automatically prune off all branches that violate constraints\n",
       "- constraint graph:\n",
       "  - nodes are variables\n",
       "  - arcs are constraints\n",
       "- CSP as search problem: a DFS, time space same as DFS\n",
       "  - Initial State: the empty assignment {}.\n",
       "  - Successor function: Assign value to any unassigned variable\n",
       "  - provided that there is not a constraint conflict.\n",
       "  - Goal test: the current assignment is complete.\n",
       "  - Path cost: a constant cost for every step.\n",
       "- forward checking:\n",
       "  - Keep track of remaining legal values for unassigned variables Terminate search when any unassigned variable has no remaining legal values\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       "\n",
       "- CSP solvers combine search and inference\n",
       "- local consistency: enforcing local  consistency in each part of the graph causes inconsistent values to be eliminated throughout  the graph.\n",
       "- node-consistent: node-consistent if all the  values in the variable’s domain satisfy the variable’s unary constraints.\n",
       "- arc consistency: if every value in its domain satisfies the variable’s  binary constraints.\n",
       "  - X -> Y is consistent iff for every value x of X there is some allowed y\n",
       "  - An arc (i,j) is arc consistent if and only if every value v on Xi is consistent with some label on Yj \n",
       "  -  To make an arc (i,j) arc consistent,for each value v on Xi ,if there is no label on Yj consistent with v, then remove v from Xi\n",
       "  - Given d values, checking arc (i,j) takes O(d^2) time worst case\n",
       "- AC3:reduce the domains of variables before we begin the search\n",
       "  - point, we are left  with a CSP that is equivalent to the original CSP—they both have the same solutions—but  the arc-consistent CSP will be faster to search because its variables have smaller domains. \n",
       "  - total arc O(n^2)\n",
       "  - Time complexity: O(d^2)\n",
       "  - worst time: O(nd^3), plannar -> O(nd^3)\n",
       "  - space O(e), where e is the number of arcs\n",
       "  - inefficiencies:\n",
       "    - At each iteration, we only need to examine those Xi where at least one neighbor of Xi has lost a value in the previous iteration.\n",
       "    - If Xi loses a value only because of arc inconsistencies with Yj, we don’t need to check Yj on the next iteration.\n",
       "- Path consistency: tightens the binary constraints by using implicit constraints  that are inferred by looking at triples of variables.\n",
       "  - A two-variable set {Xi ,Xj} is path-consistent with respect to a third variable Xm if, for  every assignment {Xi = a,Xj = b} consistent with the constraints (if any) on {Xi ,Xj}, there is  an assignment to Xm that satisfies the constraints on {Xi ,Xm} and {Xm,Xj}.\n",
       "- k consistent: for any set of k−1 variables and for any consistent assignment to those variables,  a consistent value can always be assigned to any kth variable.\n",
       "  - 2 consistent = arc consistent\n",
       "  - 3-consistent = path consistent\n",
       "- satrongly k-consistent: k-consistent and is also (k−1)-consistent, (k−2)-  Strongly  k-consistent  consistent,... all the way down to 1-consistent.\n",
       "   -time O(n^2d). for k = n  \n",
       "- global constraint: involving an arbitrary number of variables (but not  necessarily all variables).\n",
       "- resource constraint, sometimes called the Atmost constraint.\n",
       "- bounds propagation: domains are represented by upper and lower  bounds\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       "\n",
       "- commutativity: commutative if the order of application of any given set of actions does Commutativity  not matter.\n",
       "- back track can be improved with h(n)\n",
       "  - ordering: choose the  variables in order,\n",
       "    - minimum-remaining-values: choosing the variable with the fewest “legal” values\n",
       "    - degree heuristic: when initially all remaining are equal, branching factor on future choices by selecting the variable  that is involved in the largest number of constraints on other unassigned variables.(choose most connected)\n",
       "    - least-constraining-value: prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. (leave the  maximum flexibility for subsequent variable assignments)\n",
       "  - inference can be even more powerful during the course of a search:every time we make  a choice of a value for a variable, we have a brand-new opportunity to infer new domain  reductions on the neighboring variables. \n",
       "    - 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. \n",
       "    - MRV with forward checking improve effciency\n",
       "    - forward checking detects many inconsistencies, it does not detect all of them.  The problem is that it doesn’t look ahead far enough.\n",
       "    - Maintaining Arc Consistency) detects inconsistencies like this.\n",
       "  - intelligent back tracking\n",
       "    - chronological backtracking only look back one step\n",
       "    - it can be shown  that every branch pruned by backjumping is also pruned by forward checking.\n",
       "    - conflict directed backjumping: use conflict set to backjump multiple steps\n",
       "      - let Xj be the current variable, and let conf(Xj) be its conflict  set. If every possible value for Xj fails, backjump to the most recent variable Xi in conf(Xj)\n",
       "  - Constraint learning is  the idea of finding a minimum set of variables from the conflict set that causes the problem. Avoid into conflict set again\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       "\n",
       "- min-conflict h(n)\n",
       "  - Min-conflicts is surprisingly effective for many CSPs\n",
       "  - run time of min-conflicts is roughly  independent of problem size.\n",
       "- 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.\n",
       "- <strong> start early 6.5</strong>\n",
       "- decomposition of graph to trees:\n",
       "  - need to satisfy:\n",
       "    - Every variable in the original problem appears in at least one of the tree nodes.\n",
       "    - If two variables are connected by a constraint in the original problem, they must appear  together (along with the constraint) in at least one of the tree nodes.\n",
       "    - If a variable appears in two nodes in the tree, it must appear in every node along the  path connecting those nodes. \n",
       "      - The first two conditions ensure that all the variables and constraints are represented in the  tree decomposition. The third condition seems rather technical, but allows us to say that  any variable from the original problem must have the same value wherever it appears: the  constraints in the tree say that a variable in one node of the tree must have the same value as  the corresponding variable in the adjacent node in the tree.\n",
       "    - time complexity O(nd^2), where n is the number of tree nodes and d is the size of the largest domain. \n",
       "    - The tree width of a tree decomposition of a graph is one less than the size of the largest node\n",
       "    - If a graph has tree width w then the  problem can be solved in O(nd^(w+1)) time\n",
       "      - CSPs with constraint graphs of bounded tree width are solvable in polynomial time.\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       "\n",
       "- split to individual small problems\n",
       "  - independent subproblems: solution in which is independent from other solutions\n",
       "    - found by checking connected components of the constraint graph.\n",
       "  - Then there are n/c subproblems, each of which takes at most d^c work to solve, where d is the size of the domain.total work is O(d^c n/c), without the decomposition, the total  work is O(d^n), which is exponential in n.\n",
       "  - completely seperable case are rare\n",
       "  - example, a constraint graph is a tree when  any two variables are connected by only one path.\n",
       "    - any tree-structured CSP can be solved in time linear in the number of variables.\n",
       "    - directional arc consistency if under an ordering of variables X1,X2,...,Xn if and only if every Xi is arcconsistent with each Xj for j > i. \n",
       "    - O(n) steps to make it directed\n",
       "    - total time of O(nd^2).\n",
       "- Cutset condition\n",
       "  - assigning values to some variables  so that the remaining variables form a tree\n",
       "  - any solution for the CSP after assigning a value to a node and its constraints are removed will be consistent  with the value chosen for the removed node\n",
       "  - the value chosen for removed node could be the wrong one, so we would need to try each  possible value.\n",
       "  - cycle cutset: S where Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree  after removal of S\n",
       "  - run time O(d^c ·(n−c)d^2)\n",
       "  - Finding the smallest cycle  cutset is NP-hard\n",
       "  - The overall  algorithmic approach is called cutset conditioning\n",
       "- cutset vs decomposition:\n",
       "  - time consideration favors tree decomposition, but the advantage of  the cycle-cutset approach is that it can be executed in linear memory, while tree decomposition requires memory exponential in w. \n",
       "- value symmetry: question often has multiple valid solutions\n",
       "  - symmetry-breaking constraint. For our example, we might constraint  impose an arbitrary ordering constraint\n",
       "\n",
       "\n",
       "## Module 6 Lecture Notes\n",
       "\n",
       "- Constraint satisfaction problems (CSPs) represent a state with a set of variable/value  pairs and represent the conditions for a solution by a set of constraints on the variables.  Many important real-world problems can be described as CSPs.\n",
       "- A number of inference techniques use the constraints to rule out certain variable assignments. These include node, arc, path, and k-consistency.\n",
       "- Backtracking search, a form of depth-first search, is commonly used for solving CSPs.  Inference can be interwoven with search. \n",
       "- The minimum-remaining-values and degree heuristics are domain-independent methods for deciding which variable to choose next in a backtracking search. The leastconstraining-value heuristic helps in deciding which value to try first for a given  variable. Backtracking occurs when no legal assignment can be found for a variable.  Conflict-directed backjumping backtracks directly to the source of the problem. Constraint learning records the conflicts as they are encountered during search in order to  avoid the same conflict later in the search. \n",
       "- Local search using the min-conflicts heuristic has also been applied to constraint satisfaction problems with great success\n",
       "- The complexity of solving a CSP is strongly related to the structure of its constraint  graph. Tree-structured problems can be solved in linear time. 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 tree width 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",
       "\n",
       "## Module 6 Definitions\n",
       "* **Csp** - A problem is solved when each variable  has a value that satisfies all the constraints on the variable.\n",
       "* **Consistent** - An assignment Assignments  that does not violate any constraints\n",
       "* **Complete assignment** - every variable is assigned a value\n",
       "* **Solution to csp** - a consistent, complete assignment \n",
       "* **Partial assignment** - leaves some variables Solution  unassigned\n",
       "* **A partial solution** - a partial assignment that is consistent\n",
       "* **Precedence constraints** - order in which the task need to be executed\n",
       "* **Linear programming ** - constraints must  be linear equalities or inequalities.\n",
       "* **Unary constraint** - restricts  the value of a single variable\n",
       "* **Binary constraint** - relates two variables\n",
       "* **Preference constraints** - which solutions are preferred\n",
       "* **Constraint  propagation** - using constraints to reduce number of legal values for a variable, reduce the legal values for another variable.\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module6_sections = [\n",
    "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
    "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
    "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
    "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
    "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
    "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
    "]\n",
    "\n",
    "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
    "                         module6_sections, \n",
    "                         module6_definitions)\n",
    "display(Markdown(module6_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RYESi2kMybL8"
   },
   "source": [
    "#Module 7 - Logical Agents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "id": "qIRJ4YYCzNHL"
   },
   "outputs": [],
   "source": [
    "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
    "\n",
    "chapter7_1 = \"\"\"\n",
    "- Each time the agent program is called:\n",
    "  - TELLs the knowledge  base what it perceives.\n",
    "  - ASKs the knowledge base what action it should perform.\n",
    "  - the agent  program TELLs the knowledge base which action was chosen, and returns the action so that  it can be executed. \n",
    "- Logic:Logic can 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, which we will often call a model.\n",
    "- The KB is false in models that contradict what the agent knows\n",
    "- Possible Worlds is the process of enumerating all Possible Worlds that are compatible with the KB. M(KB) ⊆ M(𝛂1 )\n",
    "- Entailment can be applied to derive conclusions, which is the process of logical inference\n",
    "\"\"\"\n",
    "chapter7_2 = \"\"\"\n",
    "- conclusion is guaranteed to be correct if the available information is correct.  This is a fundamental property of logical reasoning.\n",
    "- <strong>start early 7.5</strong>\n",
    "- Proof by resolution:\n",
    "  - that yields a complete  inference algorithm when coupled with any complete search algorithm\n",
    "  - resolution simple form:\n",
    "    - ℓ1 ∨ ···∨ℓk, m / ℓ1 ∨ ··· ∨ℓi−1 ∨ℓi+1 ∨ ···∨ℓk \n",
    "  - general form\n",
    "    - ℓ1 ∨ ···∨ℓk, m1 ∨ ···∨ mn / ℓ1 ∨ ··· ∨ℓi−1 ∨ℓi+1 ∨ ···∨ℓk ∨ m1∨ ··· ∨ mj−1∨ mj+1 ∨ ··· ∨ mn \n",
    "  - eg .\n",
    "    - P1,1 ∨P3,1, ¬P1,1 ∨ ¬P2,2 / P3,1 ∨ ¬P2,2 \n",
    "    - P∨ ¬Q ∨R, ¬P∨ Q / ¬Q ∨ Q ∨R, \n",
    "- A resolution-based theorem prover can, for any sentences α  and β in propositional logic, decide whether α |= β.\n",
    "  - CNF\n",
    "    - every  sentence of propositional logic is logically equivalent to a conjunction of clauses. \n",
    "  - resolution algorithm:\n",
    "    - Each pair that contains complementary literals is resolved to produce a new clause, which is added to the set if it is not  already present.\n",
    "- completeness of resolution:\n",
    "  - ground resolution theorm: If a set of clauses is unsatisfiable, then the resolution closure of those clauses  contains the empty clause. \n",
    "  - must be complete and sound\n",
    "- definite clause: disjunction of literals of which exactly one is positive: eg (¬B1,1 ∨P1,2 ∨P2,1) is not , (¬B1,1 ∨¬P1,2 ∨P2,1) is\n",
    "- horn clause: more general of definite, at most one is positive\n",
    "- all definite clauses are horn clauses\n",
    "- two horn clauses will resovle new horn clauses, closed \n",
    "- entailment with Horn clauses can be done in linear time with respect to the size of the KB.\n",
    "- forward / backward chaining\n",
    "  - forward chaining is sound and complete\n",
    "    - moreover, every definite clause in the original KB is  true in this model. \n",
    "    - a example of data-driven reasoning\n",
    "    - An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\n",
    "  - backward chaining: goal-directed reasoning. eg. what I should do\n",
    "    - Often, the cost  of backward chaining is much less than linear in the size of the knowledge base, because the  process touches only relevant facts. \n",
    "    - If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n",
    "\n",
    "\"\"\"\n",
    "chapter7_3 = \"\"\"\n",
    "- 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.\n",
    "- 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 α. \n",
    "- entailment between sentences—the idea that a sentence follows  logically from another sentence.\n",
    "  - α |= β <=> M(α) ⊆ M(β). \n",
    "  - α is a stronger assertion than β\n",
    "- KB ⊢i α, α is derived from KB by i\n",
    "- sound or truth preserving: inference algorithm that derives only entailed sentences\n",
    "- completeness: an inference algorithm is complete if  it can derive any sentence that is entailed.\n",
    "- grounding: the connection between logical reasoning processes and the real environment in which the agent exists. (how do we know if what we know is true)\n",
    "\"\"\"\n",
    "chapter7_4 = \"\"\"\n",
    "-syntax of propositional logic defines the allowable sentences.\n",
    "- atomic sentence:\n",
    "  - True is true in every model and False is false in every model. \n",
    "  - The truth value of every other proposition symbol must be specified directly in the  model. For example, in the model m1 given earlier, P1,2 is false. \n",
    "- For complex sentences:\n",
    "  - ¬P is true iff P is false in m.  \n",
    "  - P∧ Q is true iff both P and Q are true in m.\n",
    "  - P∨ Q is true iff either P or Q is true in m. \n",
    "  - P ⇒ Q is true unless P is true and Q is false in m. \n",
    "  - P ⇔ Q is true iff P and Q are both true or both false in m. \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—there are only finitely many models to examine. \n",
    "  - If KB and α contain n symbols  in all, then there are 2^n models.\n",
    "  - time complexity O(2^n)\n",
    "  - space complexity O(n)\n",
    "  - every known inference algorithm for propositional logic has a worst-case complexity that  is exponential in the size of the input. \n",
    "\"\"\"\n",
    "chapter7_5 = \"\"\"\n",
    "- 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.  \n",
    "- If the number of models is large but the length of the proof is short, then theorem proving can  be more efficient than model checking. \n",
    "- logical equivalence: two sentences α and β are logically equivalent if they are true in the same set of models. We write  this as α ≡ β.\n",
    "  - that ≡ is used to make claims about sentences, while ⇔ is used as part  of a sentence\n",
    "  - α ≡ β if and only if α |= β and β |= α.\n",
    "- deduction theorem:\n",
    "  - For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid. \n",
    "  - α |= β if and only if the sentence (α∧ ¬β) is unsatisfiable.\n",
    "  - every valid implication sentence describes a legitimate inference. \n",
    "- Inference and proof:\n",
    "  - Modus Ponens:\n",
    "    - ( α ⇒ β, α )/ β, whenever any sentences of the form α ⇒ β and α are given, then  the sentence β can be inferred.\n",
    "  - and elimination:\n",
    "    - (α∧β)/ α\n",
    "- proof as search:\n",
    "  - INITIAL STATE: the initial knowledge base.\n",
    "  - ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule.\n",
    "  - RESULT: the result of an action is to add the sentence in the bottom half of the inference  rule\n",
    "  - GOAL: the goal is a state that contains the sentence we are trying to prove\n",
    "- finding a proof can be more efficient because the proof can ignore irrelevant propositions, no  matter how many of them there are.\n",
    "- monotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base\n",
    "  - draw additional conclusions, but it cannot invalidate any conclusion α already inferred\n",
    "  - base—the conclusion of the rule must follow  regardless of what else is in the knowledge base. (since it must be true)\n",
    "\"\"\"\n",
    "\n",
    "# Lecture notes \n",
    "module7_lecture_notes = \"\"\"\n",
    "- Intelligent agents need knowledge about the world in order to reach good decisions.\n",
    "- Knowledge is contained in agents in the form of sentences in a knowledge representation language that are stored in a knowledge base.\n",
    "- A knowledge-based agent is composed of a knowledge base and an inference mechanism. It operates by storing sentences about the world in its knowledge base, using the  inference mechanism to infer new sentences, and using these sentences to decide what  action to take.\n",
    "- A representation language is defined by its syntax, which specifies the structure of  sentences, and its semantics, which defines the truth of each sentence in each possible  world or model.\n",
    "- The relationship of entailment between sentences is crucial to our understanding of  reasoning. A sentence α entails another sentence β if β is true in all worlds where  α is true. Equivalent definitions include the validity of the sentence α ⇒ β and the  unsatisfiability of the sentence α∧ ¬β. \n",
    "- Inference is the process of deriving new sentences from old ones. Sound inference algorithms derive only sentences that are entailed; complete algorithms derive all sentences  that are entailed.\n",
    "- Propositional logic is a simple language consisting of proposition symbols and logical  connectives. It can handle propositions that are known to be true, known to be false, or  completely unknown. \n",
    "- The set of possible models, given a fixed propositional vocabulary, is finite, so entailment can be checked by enumerating models. Efficient model-checking inference  algorithms for propositional logic include backtracking and local search methods and  can often solve large problems quickly. \n",
    "- Inference rules are patterns of sound inference that can be used to find proofs. The  resolution rule yields a complete inference algorithm for knowledge bases that are  expressed in conjunctive normal form. Forward chaining and backward chaining  are very natural reasoning algorithms for knowledge bases in Horn form. \n",
    "- resolution algo To show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable.\n",
    "  - First, convert (KB ⋀ ¬𝛂) into CNF\n",
    "  - Then apply the resolution rule to the resulting clauses.\n",
    "  - Resolve every pair that contains complementary literals to produce a new clause\n",
    "  - If that new clause isn’t already present, then add it to the set.\n",
    "  - Continue the process until one of two things happens:\n",
    "    - There are no new clauses that can be added. In this case, the KB does not entail 𝛂\n",
    "    - Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂\n",
    " \"\"\"\n",
    "\n",
    "# Definitions\n",
    "module7_definitions = {\n",
    "\"knowledge base\" : \"is a set of sentences\",\n",
    "\"setence\":\"expressed in a language called a knowledge representation language and represents some assertion about the world\",\n",
    "\"axiom\":\"When the sentence is taken as being given without being derived  from other sentences\",\n",
    "\"derived sentences\":\"a new sentence that is derived from others sentences\",\n",
    "\"inference\":\"deriving new sentences from old sentences is called\",\n",
    "\"background knowledge\":\"initial database\",\n",
    "\"syntax\":\"which specifies all the  sentences that are well formed\",\n",
    "\"semantics\":\"meaning of sentences, defines  the truth of each sentence with respect to each possible world. \",\n",
    "\"model checking \":\"checking entailment sentences, by propagating all possible combination of information\",\n",
    "\"atomic sentences\":\"consist of a single proposition symbol\",\n",
    "\"validity\":\"A sentence is valid if it is true in all models, eg P ∨ ¬P\",\n",
    "\"tautologies\":\"must be true\",\n",
    "\"satisfiability\":\"A sentence is satisfiable if it is true  in, or satisfied by, some model\",\n",
    "\"complementary literals\":\"one is the negation of the other\",\n",
    "\"clause\":\"a disjunction of literals—and a  literal and produces a new clause\",\n",
    "\"factoring\":\"factor the case of (A∨A)\",\n",
    "\"goal clause\":\"no positive literals\",\n",
    "}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "cellView": "form",
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "lXNcHuKjyNXa",
    "outputId": "ee98d49f-688e-4c58-9502-74b77b26e703"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       "\n",
       "- Each time the agent program is called:\n",
       "  - TELLs the knowledge  base what it perceives.\n",
       "  - ASKs the knowledge base what action it should perform.\n",
       "  - the agent  program TELLs the knowledge base which action was chosen, and returns the action so that  it can be executed. \n",
       "- Logic:Logic can 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, which we will often call a model.\n",
       "- The KB is false in models that contradict what the agent knows\n",
       "- Possible Worlds is the process of enumerating all Possible Worlds that are compatible with the KB. M(KB) ⊆ M(𝛂1 )\n",
       "- Entailment can be applied to derive conclusions, which is the process of logical inference\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       "\n",
       "- conclusion is guaranteed to be correct if the available information is correct.  This is a fundamental property of logical reasoning.\n",
       "- <strong>start early 7.5</strong>\n",
       "- Proof by resolution:\n",
       "  - that yields a complete  inference algorithm when coupled with any complete search algorithm\n",
       "  - resolution simple form:\n",
       "    - ℓ1 ∨ ···∨ℓk, m / ℓ1 ∨ ··· ∨ℓi−1 ∨ℓi+1 ∨ ···∨ℓk \n",
       "  - general form\n",
       "    - ℓ1 ∨ ···∨ℓk, m1 ∨ ···∨ mn / ℓ1 ∨ ··· ∨ℓi−1 ∨ℓi+1 ∨ ···∨ℓk ∨ m1∨ ··· ∨ mj−1∨ mj+1 ∨ ··· ∨ mn \n",
       "  - eg .\n",
       "    - P1,1 ∨P3,1, ¬P1,1 ∨ ¬P2,2 / P3,1 ∨ ¬P2,2 \n",
       "    - P∨ ¬Q ∨R, ¬P∨ Q / ¬Q ∨ Q ∨R, \n",
       "- A resolution-based theorem prover can, for any sentences α  and β in propositional logic, decide whether α |= β.\n",
       "  - CNF\n",
       "    - every  sentence of propositional logic is logically equivalent to a conjunction of clauses. \n",
       "  - resolution algorithm:\n",
       "    - Each pair that contains complementary literals is resolved to produce a new clause, which is added to the set if it is not  already present.\n",
       "- completeness of resolution:\n",
       "  - ground resolution theorm: If a set of clauses is unsatisfiable, then the resolution closure of those clauses  contains the empty clause. \n",
       "  - must be complete and sound\n",
       "- definite clause: disjunction of literals of which exactly one is positive: eg (¬B1,1 ∨P1,2 ∨P2,1) is not , (¬B1,1 ∨¬P1,2 ∨P2,1) is\n",
       "- horn clause: more general of definite, at most one is positive\n",
       "- all definite clauses are horn clauses\n",
       "- two horn clauses will resovle new horn clauses, closed \n",
       "- entailment with Horn clauses can be done in linear time with respect to the size of the KB.\n",
       "- forward / backward chaining\n",
       "  - forward chaining is sound and complete\n",
       "    - moreover, every definite clause in the original KB is  true in this model. \n",
       "    - a example of data-driven reasoning\n",
       "    - An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\n",
       "  - backward chaining: goal-directed reasoning. eg. what I should do\n",
       "    - Often, the cost  of backward chaining is much less than linear in the size of the knowledge base, because the  process touches only relevant facts. \n",
       "    - If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n",
       "\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       "\n",
       "- 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.\n",
       "- 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 α. \n",
       "- entailment between sentences—the idea that a sentence follows  logically from another sentence.\n",
       "  - α |= β <=> M(α) ⊆ M(β). \n",
       "  - α is a stronger assertion than β\n",
       "- KB ⊢i α, α is derived from KB by i\n",
       "- sound or truth preserving: inference algorithm that derives only entailed sentences\n",
       "- completeness: an inference algorithm is complete if  it can derive any sentence that is entailed.\n",
       "- grounding: the connection between logical reasoning processes and the real environment in which the agent exists. (how do we know if what we know is true)\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       "\n",
       "-syntax of propositional logic defines the allowable sentences.\n",
       "- atomic sentence:\n",
       "  - True is true in every model and False is false in every model. \n",
       "  - The truth value of every other proposition symbol must be specified directly in the  model. For example, in the model m1 given earlier, P1,2 is false. \n",
       "- For complex sentences:\n",
       "  - ¬P is true iff P is false in m.  \n",
       "  - P∧ Q is true iff both P and Q are true in m.\n",
       "  - P∨ Q is true iff either P or Q is true in m. \n",
       "  - P ⇒ Q is true unless P is true and Q is false in m. \n",
       "  - P ⇔ Q is true iff P and Q are both true or both false in m. \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—there are only finitely many models to examine. \n",
       "  - If KB and α contain n symbols  in all, then there are 2^n models.\n",
       "  - time complexity O(2^n)\n",
       "  - space complexity O(n)\n",
       "  - every known inference algorithm for propositional logic has a worst-case complexity that  is exponential in the size of the input. \n",
       "\n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       "\n",
       "- 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.  \n",
       "- If the number of models is large but the length of the proof is short, then theorem proving can  be more efficient than model checking. \n",
       "- logical equivalence: two sentences α and β are logically equivalent if they are true in the same set of models. We write  this as α ≡ β.\n",
       "  - that ≡ is used to make claims about sentences, while ⇔ is used as part  of a sentence\n",
       "  - α ≡ β if and only if α |= β and β |= α.\n",
       "- deduction theorem:\n",
       "  - For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid. \n",
       "  - α |= β if and only if the sentence (α∧ ¬β) is unsatisfiable.\n",
       "  - every valid implication sentence describes a legitimate inference. \n",
       "- Inference and proof:\n",
       "  - Modus Ponens:\n",
       "    - ( α ⇒ β, α )/ β, whenever any sentences of the form α ⇒ β and α are given, then  the sentence β can be inferred.\n",
       "  - and elimination:\n",
       "    - (α∧β)/ α\n",
       "- proof as search:\n",
       "  - INITIAL STATE: the initial knowledge base.\n",
       "  - ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule.\n",
       "  - RESULT: the result of an action is to add the sentence in the bottom half of the inference  rule\n",
       "  - GOAL: the goal is a state that contains the sentence we are trying to prove\n",
       "- finding a proof can be more efficient because the proof can ignore irrelevant propositions, no  matter how many of them there are.\n",
       "- monotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base\n",
       "  - draw additional conclusions, but it cannot invalidate any conclusion α already inferred\n",
       "  - base—the conclusion of the rule must follow  regardless of what else is in the knowledge base. (since it must be true)\n",
       "\n",
       "\n",
       "## Module 7 Lecture Notes\n",
       "\n",
       "- Intelligent agents need knowledge about the world in order to reach good decisions.\n",
       "- Knowledge is contained in agents in the form of sentences in a knowledge representation language that are stored in a knowledge base.\n",
       "- A knowledge-based agent is composed of a knowledge base and an inference mechanism. It operates by storing sentences about the world in its knowledge base, using the  inference mechanism to infer new sentences, and using these sentences to decide what  action to take.\n",
       "- A representation language is defined by its syntax, which specifies the structure of  sentences, and its semantics, which defines the truth of each sentence in each possible  world or model.\n",
       "- The relationship of entailment between sentences is crucial to our understanding of  reasoning. A sentence α entails another sentence β if β is true in all worlds where  α is true. Equivalent definitions include the validity of the sentence α ⇒ β and the  unsatisfiability of the sentence α∧ ¬β. \n",
       "- Inference is the process of deriving new sentences from old ones. Sound inference algorithms derive only sentences that are entailed; complete algorithms derive all sentences  that are entailed.\n",
       "- Propositional logic is a simple language consisting of proposition symbols and logical  connectives. It can handle propositions that are known to be true, known to be false, or  completely unknown. \n",
       "- The set of possible models, given a fixed propositional vocabulary, is finite, so entailment can be checked by enumerating models. Efficient model-checking inference  algorithms for propositional logic include backtracking and local search methods and  can often solve large problems quickly. \n",
       "- Inference rules are patterns of sound inference that can be used to find proofs. The  resolution rule yields a complete inference algorithm for knowledge bases that are  expressed in conjunctive normal form. Forward chaining and backward chaining  are very natural reasoning algorithms for knowledge bases in Horn form. \n",
       "- resolution algo To show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable.\n",
       "  - First, convert (KB ⋀ ¬𝛂) into CNF\n",
       "  - Then apply the resolution rule to the resulting clauses.\n",
       "  - Resolve every pair that contains complementary literals to produce a new clause\n",
       "  - If that new clause isn’t already present, then add it to the set.\n",
       "  - Continue the process until one of two things happens:\n",
       "    - There are no new clauses that can be added. In this case, the KB does not entail 𝛂\n",
       "    - Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂\n",
       " \n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge base** - is a set of sentences\n",
       "* **Setence** - expressed in a language called a knowledge representation language and represents some assertion about the world\n",
       "* **Axiom** - When the sentence is taken as being given without being derived  from other sentences\n",
       "* **Derived sentences** - a new sentence that is derived from others sentences\n",
       "* **Inference** - deriving new sentences from old sentences is called\n",
       "* **Background knowledge** - initial database\n",
       "* **Syntax** - which specifies all the  sentences that are well formed\n",
       "* **Semantics** - meaning of sentences, defines  the truth of each sentence with respect to each possible world. \n",
       "* **Model checking ** - checking entailment sentences, by propagating all possible combination of information\n",
       "* **Atomic sentences** - consist of a single proposition symbol\n",
       "* **Validity** - A sentence is valid if it is true in all models, eg P ∨ ¬P\n",
       "* **Tautologies** - must be true\n",
       "* **Satisfiability** - A sentence is satisfiable if it is true  in, or satisfied by, some model\n",
       "* **Complementary literals** - one is the negation of the other\n",
       "* **Clause** - a disjunction of literals—and a  literal and produces a new clause\n",
       "* **Factoring** - factor the case of (A∨A)\n",
       "* **Goal clause** - no positive literals\n"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#@title Preview of your summary\n",
    "#@markdown You don't need to modify anything in this cell. Just press play.\n",
    "module7_sections = [\n",
    "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
    "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
    "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
    "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
    "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
    "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
    "]\n",
    "\n",
    "module7_markdown = format_module(7, \"Logical Agents\", \n",
    "                         module7_sections, \n",
    "                         module7_definitions)\n",
    "display(Markdown(module7_markdown))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vX7lbnJd4sT5"
   },
   "source": [
    "# Your Exam Notes\n",
    "\n",
    "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
    "\n",
    "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
    "* Run the cell below. \n",
    "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
    "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
    "* In the print options, change the layout from Landscape to Portrait. \n",
    "* Clicking the Save, will save a PDF that you can then print.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "T3cm1WV542_a",
    "outputId": "6583c4f6-88b9-44bc-845b-5341804dc7a4"
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "# Module 1: Rational Agents and Task Environments\n",
       "## AIMA Chapter 1.1 What is AI?\n",
       "\n",
       "- Turing test：NLP, knowledge representation, automated reasoning, ML. total Turing test: CV, robotics(manipulation in real world)   <br />\n",
       "- Human thought: introspection, psychological experiment, brain imaging <br />\n",
       "- There are ways of acting rationally that cannot be said to involve inference - reflex action <br />\n",
       "- All the skills needed for turing test allow an agent to act rationally <br />\n",
       "- ratioal agent appraoch to AI has two advantages: 1. more general than laws of though, because correct inference is just one of several possible mechanisms for rationality. 2. it is more ameable for development as mathematically it is well defined and complete <br />\n",
       "- AI has focused on the study and construction of agents that do the right thing <br />\n",
       "- standard model may not be the right model to the future as standard model assumes that we will supply a fully specified objective to the machine viable. A system deployed with an incorrect objective will have negative consequences. Moreover, the more intelligent the system, the  more negative the consequences <br />\n",
       " \n",
       "\n",
       "## AIMA Chapter 27.1 The Limits of AI\n",
       "\n",
       "- weak AI—the idea that Weak AI  machines could act as if they were intelligent\n",
       "- stronbg AI- do so are actually consciously thinking (not just simulating thinking).\n",
       "- The embodied cognition approach claims that it makes no sense to consider the brain  separately: cognition takes place within a body, which is embedded in an environment. We  need to study the system as a whole; the brain’s functioning exploits regularities in its environment, including the rest of its body.\n",
       "- suggested  that instead of asking whether machines can think, we should ask whether machines can pass  a behavioral test, which has come to be called the Turing test.\n",
       " \n",
       "\n",
       "## AIMA Chapter 27.1 Can Machines Really Think?\n",
       " \n",
       "- consciousness: awareness Consciousness  of the outside world, and of the self, and the subjective experience of living.\n",
       "- The technical  term for the intrinsic nature of experiences is qualia (from the Latin word meaning, roughly, “of what kind”).\n",
       "\n",
       "\n",
       "\n",
       "## AIMA 2.1 Agents and Environments\n",
       " \n",
       "- In general, an agent’s choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn’t perceived.   <br />\n",
       "- construct this table by trying out all possible percept sequences and recording  which actions the agent does in response. The table is, of course, an external characterization of the agent. Internal, agent program.<br />\n",
       "- The agent function is an Agent program  abstract mathematical description; the agent program is a concrete implementation, running  within some physical system.<br />\n",
       "- agent is meant to be a tool for analyzing systems, not an absolute characterization that divides the world into  agents and non-agents.<br />\n",
       "- AI operates at (what the authors  consider to be) the most interesting end of the spectrum, where the artifacts have significant  computational resources and the task environment requires nontrivial decision making. \n",
       " \n",
       "\n",
       "## AIMA 2.2 Good Behavior: The Concept of Rationality\n",
       " \n",
       "- This notion of desirability is captured by a performance measure that evaluates any given sequence of environment states.<br />\n",
       "- We will see that some agent designs have an explicit representation of (a version of) the performance measure, while in other designs the performance measure is entirely implicit—the  agent may do the right thing, but it doesn’t know why.<br />\n",
       "- Performance measure could be +1 for correct move, -1 for incorrect move, etc\n",
       "- As a general rule, it is better to design performance measures according to what one actually wants to be achieved in the environment, rather than according to how one thinks the agent should behave.<br />\n",
       "- rationality is not the same as perfection. Rationality maximizes expected performance, while perfection maximizes actual performance.<br />\n",
       "- a rational agent not only to gather information but also to learn as Learning much as possible from what it perceives.<br />\n",
       "\n",
       "\n",
       "## AIMA 2.3 The Nature of Environments\n",
       " \n",
       "- task environment groups PEAS, can be physical or virtual<br />\n",
       "  - Construct agent function f that maximizes the expected value of the performance measure(math description)\n",
       "  - Design an agent program that implements f on a particular architecture(concrete implementation)\n",
       "- Properties of task environments:<br />\n",
       "<strong>Fully observable vs. partially observable</strong>: an agent’s sensors access to the complete state of the environment at each point in time, A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action<br />\n",
       "<strong>Single-agent vs. multiagent</strong>: An object or an agent, it is an agent if behavior is best described as maximizing a performance measure whose value depends on agent A’s behavior. Taxi example, avoid collision, cooperative agent; chess competitive.<br />\n",
       "<strong>Deterministic vs. nondeterministic</strong>: If the next state of the environment is completely determined by the current state and the action executed by the agent(s), deterministic.fully observable, deterministic environment, no worry about uncertainty. partially observable, however, could appear to be nondeterministic. Most real situations are nondeterm.<br />\n",
       "<strong>Episodic vs. sequential</strong>: In an episodic task environment, the agent’s experience is divided into atomic episodes. Many classification tasks are episodic.The next episode does not depend on the actions taken in previous episodes. Chess taxi are sequential.<br />\n",
       "<strong>Static vs. dynamic</strong>: If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent. semidynamic if the environment itself does not change with the  passage of time but the agent’s performance score does. taxi dynamic, chess semi, crossword static.<br />\n",
       "<strong>Discrete vs. continuous</strong>: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent. chess discrete, taxi continous<br />\n",
       "<strong>known vs. unknown</strong>: distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the “laws of physics” of  the environment. In a known environment, the outcomes for all actions are given. if the environment is unknown, the agent will have to learn how it works in order to make good decisions. observability does not interdepent on known\n",
       "\n",
       "\n",
       "## AIMA 2.4 The Structure of Agents\n",
       " \n",
       "- $agent = architecture + program$ <br />\n",
       "- The key challenge for AI is to find out how to write programs that, to the extent possible, produce rational behavior from a smallish program rather than from a vast table. <br />\n",
       "- <strong>simple reflex agent</strong>: These agents select actions on the basis of the current percept, ignoring the rest of the percept history.\n",
       "  - Simple reflex agents have the admirable property of being simple, but will work only if the correct decision can be made only if the environment is fully observable.\n",
       "  - random is usually not rational but it can be rational in some cases\n",
       "- <strong>Model-based reflex agents</strong>: to handle partial observability is for the agent to keep track of the part of the world it can’t see now. The agent should maintain some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved aspects of the current state.\n",
       "  - model based agent: transition model + sensor model\n",
       "  - not fully observable extactly, need possibility\n",
       "- <strong>Goal-based agents</strong>: Knowing something about the current state of the environment is not always enough to decide what to do. The agent needs some sort of goal information that Goal  describes situations that are desirable.\n",
       "  - the goal-based agent appears less efficient, it is more flexible because the knowledge that supports its decisions is represented explicitly and can be modified.\n",
       "- <strong>Utility-based agents</strong>:Goals alone are not enough to generate high-quality behavior in most environments. but some are quicker, safer, more reliable, or cheaper than others.\n",
       "   - An agent’s utility function is essentially an internalization of the performance measure.an agent that chooses actions to maximize its utility will be rational according to the external performance measure.\n",
       "- Learning has another advantage:\n",
       "  - operate in initially unknown environments and to become more competent than its initial knowledge alone might allow.\n",
       "- learning element, is responsible for making improvements\n",
       "- performance element, which is responsible for selecting external actions\n",
       "- problem generator, responsible Problem generator  for suggesting actions that will lead to new and informative experiences.\n",
       "- The design of the learning element depends very much on the design of the performance element.\n",
       "- if the agent is willing to explore a little and do some perhaps suboptimal actions in the short run, it might discover much better actions for the long run\n",
       "\n",
       "\n",
       "## Module 1 Lecture Notes\n",
       " \n",
       "- An agent is something that perceives and acts in an environment. The agent function  for an agent specifies the action taken by the agent in response to any percept sequence.  \n",
       "- The performance measure evaluates the behavior of the agent in an environment. A  rational agent acts so as to maximize the expected value of the performance measure,  given the percept sequence it has seen so far.  \n",
       "- A task environment specification includes the performance measure, the external environment, the actuators, and the sensors. In designing an agent, the first step must  always be to specify the task environment as fully as possible. \n",
       "- Task environments vary along several significant dimensions. They can be fully or partially observable, single-agent or multiagent, deterministic or nondeterministic, episodic  or sequential, static or dynamic, discrete or continuous, and known or unknown.  \n",
       "- In cases where the performance measure is unknown or hard to specify correctly, there  is a significant risk of the agent optimizing the wrong objective. In such cases the agent  design should reflect uncertainty about the true objective. \n",
       "- The agent program implements the agent function. There exists a variety of basic  agent program designs reflecting the kind of information made explicit and used in the  decision process. The designs vary in efficiency, compactness, and flexibility. The  appropriate design of the agent program depends on the nature of the environment. \n",
       "- Simple reflex agents respond directly to percepts, whereas model-based reflex agents  maintain internal state to track aspects of the world that are not evident in the current  percept. Goal-based agents act to achieve their goals, and utility-based agents try to  maximize their own expected “happiness.”  \n",
       "- All agents can improve their performance through learning. \n",
       " \n",
       "\n",
       "## Module 1 Definitions\n",
       "* **Agent** - is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators\n",
       "* **Percept** - term percept to refer to the content an agent’s sensors are perceiving.\n",
       "* **Percept sequence** - percept sequence is the complete history of everything the agent has ever perceived.\n",
       "* **Rational agent** - For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure\n",
       "* **** -  given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.\n",
       "* **Performance measure** - An objective criterion for success of an agent's behavior, given the evidence provided by the percept sequence.\n",
       "* **Limited rationality** - acting when there is not enough time to do all the computation\n",
       "* **Value alignment problem** - values or objectives put into the machine must aligned with thouse of the human\n",
       "* **Agent function** - describes agent's behavior that maps any given percept sequence to an action\n",
       "* **Agent program** - agent function for an artificial agent will be implemented by an agent program\n",
       "* **Agent architecture** - the program run on some comptuing device with physical sensors and actuators\n",
       "* **Consequentialism** - we evaluate an agent's behavior by its consequences\n",
       "* **Omniscience** - an omniscient agent knows tha actual outcome of its action and can act accordingly, but omniscience is impossible in reality\n",
       "* **Information gathering** - doing actions in order to modify future percepts\n",
       "* **Autonomous** - it should learn what it can to compensate for partial or incorrect prior knowledge. \n",
       "* **Task-environment** - the problems to which rational agents are the solutions.\n",
       "* **Peas** - Performance, Environment, Actuators, Sensors\n",
       "* **Stochastic** - nondeterministic\n",
       "* **Tramsition model** - knowledge about “how the world works”—whether implemented in simple Boolean circuits or in complete scientific theories\n",
       "* **Sensor model** - conditions where is knows from the sensor\n",
       "* **Reflex agent** - select an action based on the current percept\n",
       "* **Problem solving agent** - must plan ahead, consider a sequence of actions that form a path to a goal state, also know as search\n",
       "\n",
       "\n",
       "# Module 2: Python\n",
       "## Module 2 Lecture Notes\n",
       "\n",
       "- Strong Typing\n",
       "  - Every object has a fixed type, interpreter doesn’t allow things incompatible with\n",
       "    - that type (eg. “foo” + 2)\n",
       "  - python uses dynamic typing, Variables come into existence when first assigned\n",
       "  - If assigned again, type(var) is updated\n",
       "- String\n",
       "  - Creation\n",
       "    - Can use either single or double quotes, Triple quote for multiline string and docstring\n",
       "  - Concatenating strings\n",
       "    - By separating string literals with whitespace Special use of ‘+’\n",
       "  - Prefixing with r means raw.\n",
       "    - No need to escape special characters: r’\n",
       "’\n",
       "  - String formatting\n",
       "    - Special use of ‘%’ (as in printf in C)\n",
       "  - Immutable\n",
       "- Reference and Mutability\n",
       "  - x = x.strip() # new obj\n",
       "  - == checks whether variables point to objects of the same value\n",
       "  - is checks whether variables point to the same object\n",
       "  - use y = x[:] to get a (shallow) copy of any sequence, ie. a new object of the same value\n",
       "- Sequece Type\n",
       "  - Tuple\n",
       "    - A simple immutable ordered sequence of items of mixed types\n",
       "    - Immutable: a tuple cannot be modified once created\n",
       "    - Items can be of mixed types, including collection types\n",
       "  - Strings\n",
       "    - Immutable\n",
       "    - \"_\".join(words)\n",
       "  - List\n",
       "    - Mutable ordered sequence of items of mixed types\n",
       "- Dict\n",
       "  - Dictionaries are unordered & work by hashing, so keys must be immutable\n",
       "  - Constant average time add, lookup, update\n",
       "    - key: keys, values: value stored in key, items: list of (key,value) tuple\n",
       "- function\n",
       "  - Python allows you to multiple values with type tuple\n",
       "  - no overloading, specified by name alone\n",
       "  - operator overloading is possible in class\n",
       "  - can provide default value, so some argument can be optional\n",
       "  - can be called out of order with keyword specified\n",
       "  - *args accept a variable number of non-keyword arguments to your function.\n",
       "  - **kwargs a variable number of keyword arguments to your function.\n",
       "  - function are first class object\n",
       "- Class\n",
       "  - A class can extend the definition of another class\n",
       "  - To define a subclass, class AI_Student(Student): fav_class = \"CIS 521”\n",
       "  - Multiple inheritance is supported\n",
       "  - constructor __init__:\n",
       "    - Must be done explicitly\n",
       "    - method override\n",
       "- Genrator:\n",
       "  - Functions that contain the yield keyword automatically return a generator when called\n",
       "  - and then it stops and returns the value that was yielded resumes where it left off\n",
       "\n",
       "\n",
       "## Module 2 Definitions\n",
       "* **Mutability** - can be changed after assign\n",
       "* **Indentation** - tab space \n",
       "\n",
       "\n",
       "# Module 3: Search Problems\n",
       "## AIMA Chapter 3.1 Problem-Solving Agents\n",
       " \n",
       "- Problem-solving agents use atomic representations, states of the world are considered as wholes, with no internal structure visible to the  problem-solving algorithms.\n",
       "- Agents that use factored or structured representations of states  are called planning agents\n",
       "- For known environment\n",
       "  - Goal formulation \n",
       "  - Problem formulation\n",
       "  - Search\n",
       "  - Execution\n",
       "- It is an important property that in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions\n",
       "  - open loop for above situation\n",
       "  - closed loop if the evironment nondeterministic or model is incorrect\n",
       "- If is an important property that in a partially observable, nondeterministic environment, The solution must recommend different future actions depending on the what percepts it receives. This could be in the form of a branching strategy.\n",
       "- Search problem can be defined:\n",
       "  - A set of possible states that the environment can be in. We call this the state space.\n",
       "  - The initial state that the agent starts in.\n",
       "  - A set of one or more goal states, and check for goal.\n",
       "  - The actions available to the agent.\n",
       "  - A transition model, which describes what each action does.\n",
       "  - An action cost function, A problem-solving agent should use a cost function that  reflects its own performance measure\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.2 Example Problems\n",
       " \n",
       "- A standardized problem is intended to illustrate or exercise various problem-solving methods.\n",
       "  - grid world, vaccum world\n",
       "  - sliding-tile puzzle\n",
       "- A real-world problem, such as robot  navigation, is one whose solutions people actually use, and whose formulation is idiosyncratic\n",
       "  - route finding\n",
       "  - VLSI layout\n",
       "  - Touring problem\n",
       "  - RObot navigation\n",
       "  - Assembly sequencing\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.3 Search Algorithms\n",
       " \n",
       "- strategy determines search process\n",
       "- <strong>state vs. nodes</strong>: \n",
       "  - state = physical configuration\n",
       "  - node = a data structure constitiing part of search tree\n",
       "- search algorithm takes a search problem as input and returns a solution, or an indication of failure.\n",
       "- Best-first search : generalized greedy best first, A* and dijkstra. with f(n)\n",
       "- Queue for search algo:\n",
       "  - priority queue: pop first minimal cost f(n), best-first\n",
       "  - FIFO: BFS\n",
       "  - LIFO: DFS\n",
       "- Redundant path, an algorithm that canbnot remember the past are doomed to repeat it:\n",
       "  - like best-fisrt, if we remember all the past states, we can detect redundant, and keep only the best path. Perferred when table of reaches states will fit in memory\n",
       "  - if it is impossible to have redudant then we save the memory and don't track\n",
       "    - <strong>graph search</strong> checks redundant\n",
       "    - <strong>tree-like search</strong> does not checks redundant\n",
       "- Algo performace measure:\n",
       "  - Completeness: guaranteed to find a solution when there is one, and to correctly report failure when there is not? \n",
       "  - Cost optimality: lowest path cost of all solutions?\n",
       "  - Time complexity: How long does it take to find a solution?\n",
       "  - Space complexity: How much memory is needed to perform the search?\n",
       "    - depth:d, number of action in an optimal solution\n",
       "    - braching factor:b, number of successor of a node that need to be considered\n",
       "  \n",
       "\n",
       "## AIMA Chapter 3.4 Uninformed Search Strategies\n",
       " \n",
       "- exponentially complexity search problems cannot be solved by unifomed search for any but the smallest instances\n",
       "- <strong>BFS</strong>\n",
       "  - complete\n",
       "  - cost optimal for equal cost\n",
       "  - O(b^d)\n",
       "  - O(b^d)\n",
       "  - f(n) = depth of node \n",
       "  - can do early goal test\n",
       "  - always find a solution with minimal number of actions\n",
       "  - Memory requirements are a bigger problem for BFS than execution time\n",
       "- <strong>Dijkstra/ uniform-cost search</strong>:\n",
       "  - UCS = BFS with path cost\n",
       "  - complete, if action cost >0\n",
       "  - cost optimal\n",
       "  - O(b^(1+C*/e)), where C* = cpst of optimal solution, e = lower bound on the cost of each action \n",
       "  - O(b^(1+C*/e))\n",
       "  - (O(b^(d+1))) if action cost are equal, so similar to a BFS\n",
       "  - f(n) = action cost\n",
       "  - no redudant\n",
       "- <strong>DFS</strong>:\n",
       "  - not complete, can stuck in loop, complete if check for graph search\n",
       "  - not cost-optimal\n",
       "  - O(b^m)\n",
       "  - O(bm), where m is the maximum depth\n",
       "  - f(n) = negative of the depth\n",
       "  - DFS has much smaller need to memory, we don't track the reached table and the frontier is small\n",
       "  - Backtracking, expand one node at a time, if a solution not found back track to the previous node. space comlexity O(m)\n",
       "- <strong>depth limited search</strong>:\n",
       "  - imcomplete, if solution cannot be find with depth limit, l\n",
       "  - not optimal\n",
       "  - O(b^l)\n",
       "  - O(bl)\n",
       "  - set l to the diameter of the state-space, where diameter is the maximum allowable actions\n",
       "- <strong>iterative deepening search</strong>\n",
       "  - complete\n",
       "  - optimal if actional cost is 1\n",
       "  - O(b^d)\n",
       "  - O(bd)\n",
       "  - In general, iterative deepening is the preferred  uninformed search method when the search state space is larger than can fit in memory and  the depth of the solution is not known. \n",
       "- <strong>bidirectional search</strong>\n",
       "  - complete\n",
       "  - optimal\n",
       "  - O(b^(d/2))\n",
       "  - O(b^(d/2))\n",
       "- <strong>BFS vs DFS</strong>:\n",
       "  - Use BFS: possible infinite path, some solutions have short paths and can quickly discard unlikely path\n",
       "  - Use DFS: space is restricted, many possible solutions with long paths and wrong path are terminated quickly\n",
       "\n",
       "\n",
       "## Module 3 Lecture Notes\n",
       "\n",
       "- Before an agent can start searching, a well-defined problem must be formulated.\n",
       "- A problem consists of five parts: the initial state, a set of actions, a transition model  describing the results of those actions, a set of goal states, and an action cost function.\n",
       "- The environment of the problem is represented by a state space graph. A path through  the state space (a sequence of actions) from the initial state to a goal state is a solution.\n",
       "- Search algorithms generally treat states and actions as atomic, without any internal  structure (although we introduced features of states when it came time to do learning).\n",
       "- Search algorithms are judged on the basis of completeness, cost optimality, time complexity, and space complexity.\n",
       "- Uninformed search methods have access only to the problem definition. Algorithms  build a search tree in an attempt to find a solution. Algorithms differ based on which  node they expand first:\n",
       "  - Best-first search selects nodes for expansion using to an evaluation function.\n",
       "  - Breadth-first search expands the shallowest nodes first; it is complete, optimal  for unit action costs, but has exponential space complexity.  \n",
       "  - Uniform-cost search expands the node with lowest path cost, g(n), and is optimal  for general action costs.  \n",
       "  - Depth-first search expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity. Depth-limited search adds a  depth bound.  \n",
       "  - Iterative deepening search calls depth-first search with increasing depth limits  until a goal is found. It is complete when full cycle checking is done, optimal for  unit action costs, has time complexity comparable to breadth-first search, and has  linear space complexity.  \n",
       "  - Bidirectional search expands two frontiers, one around the initial state and one  around the goal, stopping when the two frontiers meet. \n",
       "\n",
       "## Module 3 Definitions\n",
       "* **Problem-solving agent** - an agent that can formulate a plan via search\n",
       "* **State space** - the set of all states reachable from the initial state by any sequence of actions\n",
       "* **Path** - a sequence of actions\n",
       "* **Solution** - a path from initial state to a goal state\n",
       "* **Optimal solution** - the lowest path cost among all solutions.\n",
       "* **Graph** - verticies are the state and edge are actions\n",
       "* **Tree** - nodes are the state and edge are actions\n",
       "* **Evaluation function** - f(n), cost + heuristic\n",
       "* **Systematic** - explores an infinite state space, making sure eventually reach any state that is connected to the initial state. \n",
       "* **Early goal test** - check whather a node is a solution as soon as it is generated for BFS\n",
       "\n",
       "\n",
       "# Module 4: Informed Search\n",
       "## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n",
       " \n",
       "- heuristic admissible if consistent, but not vice versa  \n",
       "-<strong>informed search strategy</strong>: search strategy—one that uses domain-specific hints about the location of goals—can find solutions more efficiently than an uninformed strategy.\n",
       "  - h(n) = estimated cost of the cheapest path from the state at node n to a goal state. \n",
       "- <strong>Greedy best-first search</strong>:\n",
       "  - f(n) = h(n)\n",
       "  - complete in finite SS\n",
       "  - not optimal\n",
       "  - O(|V|) worst case, O(bm) for good h(n)\n",
       "  - O(|V|) worst case, O(bm) for good h(n)\n",
       "- <strong>A* search</strong>:\n",
       "  - f(n) = g(n)+h(n)\n",
       "  - complete\n",
       "  - optimal if admissible heuristic\n",
       "  - O(|E|) worst case = O(b^d)\n",
       "  - O(|V|) worst case = O(b^d)\n",
       "  - prunes away nodes that are not necessary for an optimal solution\n",
       "  - if h(n) is admissible, A* with tree search is optimal\n",
       "- <strong>weighted A* search and inadmissible heuristics</strong>:\n",
       "  - stisficing solution: the solution is good enough\n",
       "  - f(n) = g(n) + W*h(n), W>1\n",
       "  - weighted A* can search much faster with slightly higher path cost\n",
       "  - some variants:\n",
       "    - bounded suboptimal search: look for a solution that is guaranteed to be within a constant factor W of the optimal cost.\n",
       "    - bounded-cost search: solution whose cost is less  than some constant C\n",
       "    - unbounded-cost search: we accept a solution of any cost, find it quickly.\n",
       "- <strong>memory-bounded search</strong>:\n",
       "  - Beam search:\n",
       "    - limit size of frontier, keep k of best f-score\n",
       "    - run faster, less memory, as it keeps and expands less frontiers\n",
       "    - suboptimal, incomplete\n",
       "  - Interative deepening A*:\n",
       "    - cut of f-score \n",
       "    - visit some states multiple times, but use less memory\n",
       "    - keep one value at a time\n",
       "  - recursive best -first search:\n",
       "    - RBFS resembles a recursive depth-  first search, but rather than continuing indefinitely down the current path, it uses the f limit  variable to keep track of the f-value of the best alternative path available from any ancestor  of the current node.\n",
       "    - more efficient that IDA, but still regenerate nodes\n",
       "    - linear memory use\n",
       "  - SMA*\n",
       "    - like A* drop worst leaf node if memory is full\n",
       "    - if f-score equal, drop the oldest\n",
       "    - optimal and complete is reachable\n",
       "    - become A* if infinite memeory\n",
       "    - memory limitations can make a problem intractable from the point of view of computation time\n",
       "- <strong>bidirectional search</strong>:\n",
       "  - no longer optimal with only f(n) even admissible\n",
       "\n",
       "\n",
       "## AIMA Chapter 3.6 Heuristic Functions\n",
       "\n",
       "- effective braching factor, b*: is the branching factor that a uniform tree of depth d would have to have in order to contain N +1 nodes.\n",
       "  - good h(n) will have b* close 1\n",
       "  - good heuritic will consistently alwawys better than bad one, \n",
       "    - good heuristic dominates bad heuristic,\n",
       "    - good h(n) will never expand more nodes than bad h(n)\n",
       "    - good h(n)>bad h(n)\n",
       "- On dominance:\n",
       "  - h*(n) = oracle heuristic, where h*(n)= c*\n",
       "  - h*(n)>=h(n)>=0\n",
       "- Generate h(n) from relaxed problems:\n",
       "  - a relaxed  problem: A problem with fewer restrictions on the actions\n",
       "  - any optimal solution in  the original problem is, by definition, also a solution in the relaxed problem\n",
       "  - relaxed problem may have better solutions if the added edges provide shortcuts. Hence, the cost of  an optimal solution to a relaxed problem is an admissible heuristic for the original problem. \n",
       "\n",
       "\n",
       "## Module 4 Lecture Notes\n",
       "\n",
       "- Informed search methods have access to a heuristic function h(n) that estimates the  cost of a solution from n. They may have access to additional information such as  pattern databases with solution costs. \n",
       "  - Greedy best-first search expands nodes with minimal h(n). It is not optimal but  is often efficient.  \n",
       "  - A∗ search expands nodes with minimal f(n) = g(n) + h(n). A∗ is complete and  optimal, provided that h(n) is admissible. The space complexity of A∗ is still an  issue for many problems.  \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 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 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",
       "- The performance of heuristic search algorithms depends on the quality of the heuristic  function. One can sometimes construct good heuristics by relaxing the problem definition, by storing precomputed solution costs for subproblems in a pattern database, by  defining landmarks, or by learning from experience with the problem class. \n",
       "\n",
       "\n",
       "## Module 4 Definitions\n",
       "* **Admissible heuristic** - one that never  overestimates the cost to reach a goal.\n",
       "* **Optimistic** - admissible\n",
       "* **Consistency** - every node n and every successor n' of n generated by an action a, we have: $h(n) \\leq c(n,a,n')+h(n')$ (tria,ineq)\n",
       "* **Monotonic** - monotonic: the path cost always increases as you go along a path, if action costs are always positive.\n",
       "* **Optimally efficient** - with consistent heuristic, expand once\n",
       "* **Reference counts** - number of times a state has been reached\n",
       "\n",
       "\n",
       "# Module 5: Adversarial Search and Games\n",
       "## AIMA Chapter 5.1 Game Theory\n",
       " \n",
       "- Stances toward multi-agent environments:\n",
       "  - where a large number of agents, to consider them in aggregate as an economy, eg pridit increasin gdemand without considering individual agent \n",
       "  - consider adversarial agent as just a part of the enviornmentr -a that makes the environment nondeterministic\n",
       "  - as game-tree search, which is covered\n",
       "- apply evaluation function to estimate who is einning based on feature of the game\n",
       "- Analogy of game to search:\n",
       "  - perfect information - fully observable\n",
       "  - move - action\n",
       "  - position - state\n",
       "  - result - transition model \n",
       "- Game tree:\n",
       "  - nodes: bopard position\n",
       "  - edge: legal moves\n",
       "  - All play is from max's advantage point\n",
       "  - Max moves attempt to max its outcome, min try to minimize\n",
       "    - even level: turn for max\n",
       "    - off level: turn for min\n",
       "- Evaluation function f assigns real-number scores to `board positions’ without reference to path\n",
       "  - how good a board position is\n",
       "  - based on feature alone\n",
       "    - f(n)>0 winning for max\n",
       "- Game definition:\n",
       "  - Initial state: state, which specifies how the game is set up at the start. \n",
       "  - TO_MOVE: the player whose turn it is to move in state s\n",
       "  - action, The set of legal moves in state s\n",
       "  - result: transition model, state resulting from taking action a in state s\n",
       "  - IS_terminal: a terminal trest, state where the game ends\n",
       "  - Utility: a utility function (objective function) where assign a value to the performace of the game\n",
       "- Initial states, action function and result function defines state space graph, a graph where the vertices are states\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.2 Optimal Decisions in Games\n",
       "\n",
       "- Minmax search:\n",
       "  - max strategy must be a conditional plan depends on each of min's move\n",
       "  - idesirable outcome must be guaranteed no matter what the other side does\n",
       "  - Minmax value:\n",
       "    - minmax value is the utility of being in that state assuming both players play optimally from there to the end of the game\n",
       "    - minmax value of a terminal state is just its utility\n",
       "  - minmax decision at the root is the optimal choice for Max because it leads to the state with the highest minimax value\n",
       "  - if other player does not play optimally, then it will do as well as if other play optimally\n",
       "    - but best minimax move is not the best move if play with suboptimal player\n",
       "- Minimax search algorithm:\n",
       "  - a variant of DFS\n",
       "  - time complexity: O(b^m), m is maximum depth of tree, b in # of legal moves\n",
       "  - space complexity: O(bm), for an algo that generate all actions at once, O(m) for algo generate action one at a time\n",
       "  - minimax has expponential complexity impractial for complex game.\n",
       "- Optimal decision in multi-player game:\n",
       "  - use vector value instead of minmax value\n",
       "  - For terminal states, this vector gives the utility of the state from each player’s  viewpoint.\n",
       "  - alliances could be a natural consequences of optimal stratgy\n",
       "- Alpha-beta pruning:\n",
       "  - The number of game states is exponential in the depth of the tree. alpha beta computing the correct  minimax decision without examining every state by pruning that make no difference to the outcome.\n",
       "  -  the value of the root and hence the minimax decision are independent of the  values of some leaves there fore can be pruned\n",
       "    - α =  the value of the best (i.e., highest-value) choice we have found so far at any choice point  along the path for MAX. Think: α = “at least.”  \n",
       "    - β = the value of the best (i.e., lowest-value) choice we have found so far at any choice point  along the path for MIN. Think: β = “at most.” \n",
       "  - dependent on the order in which the states are examined\n",
       "  - Best time complexity O(b^(m/2)), effective braching factor become sqrt(b)\n",
       "  - Random order generally has time complexity O(b^(3m/4))\n",
       "  - perfect ordering is not likely, but we can get close, to O(b^(m/2))\n",
       "- Type A strategy considers all possible moves to a certain depth in the search tree, and then uses a heuristic evaluation function to estimate the utility of states at that depth, wide byt shallow\n",
       "- Type B strategy ignores moves that look bad, and follows promising lines “as far as possible.” It explores a deep but narrow portion of the tree. \n",
       "\n",
       "\n",
       "## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n",
       "\n",
       "- apply a heuristic evaluation function to states, effectively treating nonterminal nodes as if they were terminal\n",
       "  - replace utility function with eval, that estimates a state's utility\n",
       "  - repalce terminal test with cutoff test\n",
       "  - eval(s,p) returns an estimates of expected utility of state s to player p\n",
       "    - for terminal state: eval = utility\n",
       "    - for other: utility(loss)<= eval <= utility(win)\n",
       "  - A good eval function\n",
       "    - easy to compute\n",
       "    - correlate with actual chances of winning (because we cut off  before we are able to determine the terminal state there will be uncertainty)\n",
       "  - Expected value = P(x)*x\n",
       "  - weighted linear function: a eval function, where is a score calculated based on material value\n",
       "- cut off search:\n",
       "  - first attempt:\n",
       "    - increment depth and return the eval function if a set depth is reached\n",
       "    - or use iteractive deepening search return the best result if computation time is reached\n",
       "    - but can lead to error due to uncertainty nature\n",
       "  - improved:\n",
       "    - evaluation function should be applied only to positions that are quiescent—that positions in which there is no pending move (such as a capturing the queen) that would wildly  swing the evaluation.\n",
       "    - horizon effect is more difficult to eliminate, arises when program program is facing  an opponent’s move that causes serious damage and is ultimately unavoidable, but can be  temporarily avoided by the use of delaying tactics.\n",
       "  - with singular extensions:\n",
       "    - moves that are “clearly better” than all other moves in a given position, even when the search would  normally be cut off at that point. contiune deepening the search. \n",
       "    - makes the tree  deeper, but because there are usually few singular extensions, the strategy does not add many  total nodes to the tree, and has proven to be effective in practice. \n",
       "- Forward pruning: prunes moves that appear to be poor moves, but might possibly be good Forward pruning  ones. will make error\n",
       "  - beam search: on each ply, consider  only a “beam” of the n best moves rather than considering all possible moves. but best moves may be pruned away\n",
       "  - late move reduction: works under the assumption that move ordering  has been done well, and therefore moves that appear later in the list of possible moves are  less likely to be good moves.  moves. But rather than pruning them away completely. can be revisited\n",
       "- search vs look up\n",
       "  - sometime human experience can be valuable we can look up in state space for best move\n",
       "  - can do first opening moves with look up and later with search\n",
       "\n",
       "\n",
       "## AIMA Chapter 5.5 Stochastic Games\n",
       "\n",
       "- Uncertain outcomes controlled by chance, not an adversary\n",
       "- Stochastic games has unpredictability of real life by including a  random element, such as the throwing of dice.\n",
       "  - A game  tree in stochastic game must include chance nodes in addition to MAX and MIN nodes.\n",
       "  - expected value of a position: the weighted average over all Expected value  possible outcomes of the chance nodes.\n",
       "  - expectiminimax value for games with chance nodes, a generalization value  of the minimax value for deterministic games. (with the caveat that the legal moves for MAX and MIN will  depend on the outcome of the dice roll in the previous chance node )\n",
       "- expectiminimax:\n",
       "  - Values should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes\n",
       "    - Max nodes as in minimax search\n",
       "    - Chance nodes are like min nodes but the outcome is uncertain\n",
       "    - Calculate their expected utilities I.e. take weighted average (expectation) of children\n",
       "  - time complexity O(b^m n^m) because we need to consider the dice rolls, n number of distinct rolls\n",
       "  - no likely sequence of moves possibilities are multiplied enormously, and forming detailed plans of action becomes  pointless because the world probably will not play along.\n",
       "  - pruning is still possible by placing upper or lower bound on the utility values and prune away.\n",
       " \n",
       "\n",
       "## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n",
       "\n",
       "- $ P(Result(a)=s')= \\sum_{s}^{} P(s)P(s'|s,a) $, which assumes epsidic\n",
       "- $ EU(a) = \\sum_{s'} P(Result(a)=s')U(s') $. expected utility\n",
       "- $ action = argmax EU(a) $, maximum expected utility, a prescription for intelligent behavior\n",
       "- All an  intelligent agent has to do is calculate the various quantities, maximize utility over its actions,  and away it goes. But this does not mean that the AI problem is solved by the definition!\n",
       "  - The MEU principle formalizes the general notion that an intelligent agent should “do the  right thing,” but does not operationalize that advice.\n",
       "  - percerption, learning and knowledge representaion, inference are also needed to compute,\n",
       "  - decision theory is not a panacea that solves the  AI problem—but it does provide the beginnings of a basic mathematical framework that is  general enough to define the AI problem. \n",
       "- 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",
       "\n",
       "## AIMA Chapter 16.2 The Basis of Utility Theory\n",
       "\n",
       "- MEU is not the only rational way\n",
       "- basic preferences:\n",
       "  - $ (A\\succ B) $, agent prefers A over B\n",
       "  - $ (A \\sim B) $, no difference in perference\n",
       "  - $ (A \\succsim B) $, agent prefers A over B or no difference in perference\n",
       "- axioms of utility theory  list six constraints that we require any reasonable preference relation to obey: \n",
       "- <strong>Orderability</strong>, Given any two lotteries, a rational agent must either prefer one or else  rate them as equally preferable. That is, the agent cannot avoid deciding.\n",
       "  - Exactly one of $ (A\\succ B) $, $ (B \\succ A)$, or $ (A \\sim B) $ holds\n",
       "- <strong>Transitivity</strong>: Given any three lotteries, if an agent prefers A to B and prefers B to C, then the agent must prefer A to C\n",
       "  - $ (A\\succ B) \\wedge (B \\succ C) \\Rightarrow (A \\succ C) $ holds\n",
       "- <strong>Continuity</strong>: 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.\n",
       "- <strong>Substitutability</strong>: 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\n",
       "- <strong>Monotonicity</strong>: 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). \n",
       "- <strong>Decomposability</strong>: Compound lotteries can be reduced to simpler ones using the laws of probability. it compresses two consecutive lotteries into a single equivalent lottery.\n",
       "- Rational preference lead to utility:\n",
       "- <strong>Existence of Utility Function</strong>:If an agent’s preferences obey the axioms of utility, then  there exists a function U such that U(A) > U(B) if and only if A is preferred to B, and  U(A) = U(B) if and only if the agent is indifferent between A and B. \n",
       "  - $U(A) > U(B) \\Leftrightarrow A \\succ B $  and  $ U(A) = U(B) \\Leftrightarrow A \\sim B$\n",
       "- <strong>Expected Utility of a Lottery</strong>: The utility of a lottery is the sum of the probability of  each outcome times the utility of that outcome. \n",
       "  - $ U([p_1,S_1;\\dots ; p_n,S_n]) = \\sum_{i} p_i U(S_i)$\n",
       "  - In other words, once the probabilities and utilities of the possible outcome states are specified, the utility of a compound lottery involving those states is completely determined.\n",
       "  - Because the  outcome of a nondeterministic action is a lottery, agent can act rationally, consistently with its preferences—only by choosing an action that maximizes expected  utility\n",
       "\n",
       "\n",
       "## AIMA Chapter 16.3 Utility Functions\n",
       "\n",
       "- Normalized utilities: $ u_{bot} = 0, u_{top} = 1 $\n",
       "- standard lottery: $ [p,u_{top};(1-p),u_{bot}] $\n",
       "- expected monetary value (EMV):\n",
       "  - $ EMV = \\sum P(x)*Value(x)$\n",
       "  - Utility is not  directly proportional to monetary value, because the utility for your the momey you own is not the same\n",
       "  - utility of money plateaus at higher, deepening at lower\n",
       "- We will assume, kindly perhaps, that the estimates EU(a) are unbiased, but the real outcome will usually be significantly worse than we estimated,  even though the estimate was unbiased!\n",
       "- \n",
       "\n",
       "\n",
       "## Module 5 Lecture Notes\n",
       "\n",
       "- A game can be defined by the initial state (how the board is set up), the legal actions  in each state, the result of each action, a terminal test (which says when the game is  over), and a utility function that applies to terminal states to say who won and what the  final score is.\n",
       "- In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information, the minimax algorithm can select optimal moves by a depth-first enumeration  of the game tree. \n",
       "- The alpha–beta search algorithm computes the same optimal move as minimax, but  achieves much greater efficiency by eliminating subtrees that are provably irrelevant.\n",
       "- Usually, it is not feasible to consider the whole game tree (even with alpha–beta), so we  need to cut the search off at some point and apply a heuristic evaluation function that  estimates the utility of a state. \n",
       "- Many game programs precompute tables of best moves in the opening and endgame so  that they can look up a move rather than search.\n",
       "  - 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. \n",
       "- <strong>cont 16_2</strong>\n",
       "- The preceding theorems establish that (assuming the constraints on rational preferences)  a utility function exists for any rational agent. The theorems do not establish that the utility  function is unique.\n",
       "- As in game-playing, in a deterministic environment an agent needs only a preference ranking on states—the numbers don’t matter. This is called a value function or ordinal  utility function. \n",
       "- existence of a utility function that describes an agent’s  preference behavior does not necessarily mean that the agent is explicitly maximizing that  utility function in its own deliberations.\n",
       "  \n",
       "\n",
       "## Module 5 Definitions\n",
       "* **Adversial search** - two or more agens have conflicting goals\n",
       "* **Perfect information** - fully observable\n",
       "* **Zero sum** - one player wins the other one loses, no win win outcome\n",
       "* **Game tree** - a search tree that follows every sequence of moves all the way to a terminal state.\n",
       "* **Ply** - unambiguously mean one move by one player, bringing us one level deeper in the game tree.\n",
       "* **Killer move** - best move \n",
       "* **Transposition** - different Transposition  permutations of the move sequence that end up in the same position\n",
       "* **Cutoff** - replace terminal state cutoff test, return true if terminal, otherwise free to decide when to cut off the search\n",
       "* **Feature** - categories and evaluates the equivalent class of the game, each class have the same value for each equivalent\n",
       "* **Material value** - cost of each  pieces in chess\n",
       "* **Lottery** - don't know what is coming\n",
       "* **Preference elicitation** - involves presenting choices to the human and using the observed preferences to pin down the underlying utility function\n",
       "* **Risk-averse** - they prefer a sure thing with a payoff that is less than the expected monetary value of a gamble.\n",
       "* **Risk-seeking** - “desperate” region at large negative wealth, loss more money is fine\n",
       "* **Normative theory** - describe how a rational agent should act.\n",
       "* **Descriptive theory** - how a actual agent (human) would act\n",
       "* **Certainty effect** - people are strongly attracted to gains that are certain\n",
       "\n",
       "\n",
       "# Module 6: Constraint Satisfaction Problems\n",
       "## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n",
       "\n",
       "- The simplist CSP invovles variable that are discrete, finite, eg map color scheduling \n",
       "- discrete domain can be infinite\n",
       "- Represent the constraints that solutions must satisfy in a uniform declarative language\n",
       "- Find solutions by GENERAL PURPOSE search algorithms with no changes from problem to problem\n",
       "  - Just specify the problem in a formal declarative language, and a general-purpose algorithm does everything else!\n",
       "- CSP consist of:\n",
       "  - Finite set of variables\n",
       "  - Nonempty domain of possible values\n",
       "  - Finite set of constraints\n",
       "- Solutions to CSPs can be found by a completely general purpose algorithm, given only the formal specification of the CSP\n",
       "- benefit of CSP:\n",
       "  - Clean specification of many problems, generic goal, successor function & heuristics\n",
       "  - CSP “knows” which variables violate a constraint\n",
       "  - Automatically prune off all branches that violate constraints\n",
       "- constraint graph:\n",
       "  - nodes are variables\n",
       "  - arcs are constraints\n",
       "- CSP as search problem: a DFS, time space same as DFS\n",
       "  - Initial State: the empty assignment {}.\n",
       "  - Successor function: Assign value to any unassigned variable\n",
       "  - provided that there is not a constraint conflict.\n",
       "  - Goal test: the current assignment is complete.\n",
       "  - Path cost: a constant cost for every step.\n",
       "- forward checking:\n",
       "  - Keep track of remaining legal values for unassigned variables Terminate search when any unassigned variable has no remaining legal values\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n",
       "\n",
       "- CSP solvers combine search and inference\n",
       "- local consistency: enforcing local  consistency in each part of the graph causes inconsistent values to be eliminated throughout  the graph.\n",
       "- node-consistent: node-consistent if all the  values in the variable’s domain satisfy the variable’s unary constraints.\n",
       "- arc consistency: if every value in its domain satisfies the variable’s  binary constraints.\n",
       "  - X -> Y is consistent iff for every value x of X there is some allowed y\n",
       "  - An arc (i,j) is arc consistent if and only if every value v on Xi is consistent with some label on Yj \n",
       "  -  To make an arc (i,j) arc consistent,for each value v on Xi ,if there is no label on Yj consistent with v, then remove v from Xi\n",
       "  - Given d values, checking arc (i,j) takes O(d^2) time worst case\n",
       "- AC3:reduce the domains of variables before we begin the search\n",
       "  - point, we are left  with a CSP that is equivalent to the original CSP—they both have the same solutions—but  the arc-consistent CSP will be faster to search because its variables have smaller domains. \n",
       "  - total arc O(n^2)\n",
       "  - Time complexity: O(d^2)\n",
       "  - worst time: O(nd^3), plannar -> O(nd^3)\n",
       "  - space O(e), where e is the number of arcs\n",
       "  - inefficiencies:\n",
       "    - At each iteration, we only need to examine those Xi where at least one neighbor of Xi has lost a value in the previous iteration.\n",
       "    - If Xi loses a value only because of arc inconsistencies with Yj, we don’t need to check Yj on the next iteration.\n",
       "- Path consistency: tightens the binary constraints by using implicit constraints  that are inferred by looking at triples of variables.\n",
       "  - A two-variable set {Xi ,Xj} is path-consistent with respect to a third variable Xm if, for  every assignment {Xi = a,Xj = b} consistent with the constraints (if any) on {Xi ,Xj}, there is  an assignment to Xm that satisfies the constraints on {Xi ,Xm} and {Xm,Xj}.\n",
       "- k consistent: for any set of k−1 variables and for any consistent assignment to those variables,  a consistent value can always be assigned to any kth variable.\n",
       "  - 2 consistent = arc consistent\n",
       "  - 3-consistent = path consistent\n",
       "- satrongly k-consistent: k-consistent and is also (k−1)-consistent, (k−2)-  Strongly  k-consistent  consistent,... all the way down to 1-consistent.\n",
       "   -time O(n^2d). for k = n  \n",
       "- global constraint: involving an arbitrary number of variables (but not  necessarily all variables).\n",
       "- resource constraint, sometimes called the Atmost constraint.\n",
       "- bounds propagation: domains are represented by upper and lower  bounds\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.3 Backtracking Search for CSPs\n",
       "\n",
       "- commutativity: commutative if the order of application of any given set of actions does Commutativity  not matter.\n",
       "- back track can be improved with h(n)\n",
       "  - ordering: choose the  variables in order,\n",
       "    - minimum-remaining-values: choosing the variable with the fewest “legal” values\n",
       "    - degree heuristic: when initially all remaining are equal, branching factor on future choices by selecting the variable  that is involved in the largest number of constraints on other unassigned variables.(choose most connected)\n",
       "    - least-constraining-value: prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph. (leave the  maximum flexibility for subsequent variable assignments)\n",
       "  - inference can be even more powerful during the course of a search:every time we make  a choice of a value for a variable, we have a brand-new opportunity to infer new domain  reductions on the neighboring variables. \n",
       "    - 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. \n",
       "    - MRV with forward checking improve effciency\n",
       "    - forward checking detects many inconsistencies, it does not detect all of them.  The problem is that it doesn’t look ahead far enough.\n",
       "    - Maintaining Arc Consistency) detects inconsistencies like this.\n",
       "  - intelligent back tracking\n",
       "    - chronological backtracking only look back one step\n",
       "    - it can be shown  that every branch pruned by backjumping is also pruned by forward checking.\n",
       "    - conflict directed backjumping: use conflict set to backjump multiple steps\n",
       "      - let Xj be the current variable, and let conf(Xj) be its conflict  set. If every possible value for Xj fails, backjump to the most recent variable Xi in conf(Xj)\n",
       "  - Constraint learning is  the idea of finding a minimum set of variables from the conflict set that causes the problem. Avoid into conflict set again\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.4 Local Search for CSPs\n",
       "\n",
       "- min-conflict h(n)\n",
       "  - Min-conflicts is surprisingly effective for many CSPs\n",
       "  - run time of min-conflicts is roughly  independent of problem size.\n",
       "- 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.\n",
       "- <strong> start early 6.5</strong>\n",
       "- decomposition of graph to trees:\n",
       "  - need to satisfy:\n",
       "    - Every variable in the original problem appears in at least one of the tree nodes.\n",
       "    - If two variables are connected by a constraint in the original problem, they must appear  together (along with the constraint) in at least one of the tree nodes.\n",
       "    - If a variable appears in two nodes in the tree, it must appear in every node along the  path connecting those nodes. \n",
       "      - The first two conditions ensure that all the variables and constraints are represented in the  tree decomposition. The third condition seems rather technical, but allows us to say that  any variable from the original problem must have the same value wherever it appears: the  constraints in the tree say that a variable in one node of the tree must have the same value as  the corresponding variable in the adjacent node in the tree.\n",
       "    - time complexity O(nd^2), where n is the number of tree nodes and d is the size of the largest domain. \n",
       "    - The tree width of a tree decomposition of a graph is one less than the size of the largest node\n",
       "    - If a graph has tree width w then the  problem can be solved in O(nd^(w+1)) time\n",
       "      - CSPs with constraint graphs of bounded tree width are solvable in polynomial time.\n",
       "\n",
       "\n",
       "## AIMA Chapter 6.5 The Structure of Problems\n",
       "\n",
       "- split to individual small problems\n",
       "  - independent subproblems: solution in which is independent from other solutions\n",
       "    - found by checking connected components of the constraint graph.\n",
       "  - Then there are n/c subproblems, each of which takes at most d^c work to solve, where d is the size of the domain.total work is O(d^c n/c), without the decomposition, the total  work is O(d^n), which is exponential in n.\n",
       "  - completely seperable case are rare\n",
       "  - example, a constraint graph is a tree when  any two variables are connected by only one path.\n",
       "    - any tree-structured CSP can be solved in time linear in the number of variables.\n",
       "    - directional arc consistency if under an ordering of variables X1,X2,...,Xn if and only if every Xi is arcconsistent with each Xj for j > i. \n",
       "    - O(n) steps to make it directed\n",
       "    - total time of O(nd^2).\n",
       "- Cutset condition\n",
       "  - assigning values to some variables  so that the remaining variables form a tree\n",
       "  - any solution for the CSP after assigning a value to a node and its constraints are removed will be consistent  with the value chosen for the removed node\n",
       "  - the value chosen for removed node could be the wrong one, so we would need to try each  possible value.\n",
       "  - cycle cutset: S where Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree  after removal of S\n",
       "  - run time O(d^c ·(n−c)d^2)\n",
       "  - Finding the smallest cycle  cutset is NP-hard\n",
       "  - The overall  algorithmic approach is called cutset conditioning\n",
       "- cutset vs decomposition:\n",
       "  - time consideration favors tree decomposition, but the advantage of  the cycle-cutset approach is that it can be executed in linear memory, while tree decomposition requires memory exponential in w. \n",
       "- value symmetry: question often has multiple valid solutions\n",
       "  - symmetry-breaking constraint. For our example, we might constraint  impose an arbitrary ordering constraint\n",
       "\n",
       "\n",
       "## Module 6 Lecture Notes\n",
       "\n",
       "- Constraint satisfaction problems (CSPs) represent a state with a set of variable/value  pairs and represent the conditions for a solution by a set of constraints on the variables.  Many important real-world problems can be described as CSPs.\n",
       "- A number of inference techniques use the constraints to rule out certain variable assignments. These include node, arc, path, and k-consistency.\n",
       "- Backtracking search, a form of depth-first search, is commonly used for solving CSPs.  Inference can be interwoven with search. \n",
       "- The minimum-remaining-values and degree heuristics are domain-independent methods for deciding which variable to choose next in a backtracking search. The leastconstraining-value heuristic helps in deciding which value to try first for a given  variable. Backtracking occurs when no legal assignment can be found for a variable.  Conflict-directed backjumping backtracks directly to the source of the problem. Constraint learning records the conflicts as they are encountered during search in order to  avoid the same conflict later in the search. \n",
       "- Local search using the min-conflicts heuristic has also been applied to constraint satisfaction problems with great success\n",
       "- The complexity of solving a CSP is strongly related to the structure of its constraint  graph. Tree-structured problems can be solved in linear time. 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 tree width 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",
       "\n",
       "## Module 6 Definitions\n",
       "* **Csp** - A problem is solved when each variable  has a value that satisfies all the constraints on the variable.\n",
       "* **Consistent** - An assignment Assignments  that does not violate any constraints\n",
       "* **Complete assignment** - every variable is assigned a value\n",
       "* **Solution to csp** - a consistent, complete assignment \n",
       "* **Partial assignment** - leaves some variables Solution  unassigned\n",
       "* **A partial solution** - a partial assignment that is consistent\n",
       "* **Precedence constraints** - order in which the task need to be executed\n",
       "* **Linear programming ** - constraints must  be linear equalities or inequalities.\n",
       "* **Unary constraint** - restricts  the value of a single variable\n",
       "* **Binary constraint** - relates two variables\n",
       "* **Preference constraints** - which solutions are preferred\n",
       "* **Constraint  propagation** - using constraints to reduce number of legal values for a variable, reduce the legal values for another variable.\n",
       "\n",
       "\n",
       "# Module 7: Logical Agents\n",
       "## AIMA Chapter 7.1 Knowledge-Based Agents\n",
       "\n",
       "- Each time the agent program is called:\n",
       "  - TELLs the knowledge  base what it perceives.\n",
       "  - ASKs the knowledge base what action it should perform.\n",
       "  - the agent  program TELLs the knowledge base which action was chosen, and returns the action so that  it can be executed. \n",
       "- Logic:Logic can 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, which we will often call a model.\n",
       "- The KB is false in models that contradict what the agent knows\n",
       "- Possible Worlds is the process of enumerating all Possible Worlds that are compatible with the KB. M(KB) ⊆ M(𝛂1 )\n",
       "- Entailment can be applied to derive conclusions, which is the process of logical inference\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.2 The Wumpus World\n",
       "\n",
       "- conclusion is guaranteed to be correct if the available information is correct.  This is a fundamental property of logical reasoning.\n",
       "- <strong>start early 7.5</strong>\n",
       "- Proof by resolution:\n",
       "  - that yields a complete  inference algorithm when coupled with any complete search algorithm\n",
       "  - resolution simple form:\n",
       "    - ℓ1 ∨ ···∨ℓk, m / ℓ1 ∨ ··· ∨ℓi−1 ∨ℓi+1 ∨ ···∨ℓk \n",
       "  - general form\n",
       "    - ℓ1 ∨ ···∨ℓk, m1 ∨ ···∨ mn / ℓ1 ∨ ··· ∨ℓi−1 ∨ℓi+1 ∨ ···∨ℓk ∨ m1∨ ··· ∨ mj−1∨ mj+1 ∨ ··· ∨ mn \n",
       "  - eg .\n",
       "    - P1,1 ∨P3,1, ¬P1,1 ∨ ¬P2,2 / P3,1 ∨ ¬P2,2 \n",
       "    - P∨ ¬Q ∨R, ¬P∨ Q / ¬Q ∨ Q ∨R, \n",
       "- A resolution-based theorem prover can, for any sentences α  and β in propositional logic, decide whether α |= β.\n",
       "  - CNF\n",
       "    - every  sentence of propositional logic is logically equivalent to a conjunction of clauses. \n",
       "  - resolution algorithm:\n",
       "    - Each pair that contains complementary literals is resolved to produce a new clause, which is added to the set if it is not  already present.\n",
       "- completeness of resolution:\n",
       "  - ground resolution theorm: If a set of clauses is unsatisfiable, then the resolution closure of those clauses  contains the empty clause. \n",
       "  - must be complete and sound\n",
       "- definite clause: disjunction of literals of which exactly one is positive: eg (¬B1,1 ∨P1,2 ∨P2,1) is not , (¬B1,1 ∨¬P1,2 ∨P2,1) is\n",
       "- horn clause: more general of definite, at most one is positive\n",
       "- all definite clauses are horn clauses\n",
       "- two horn clauses will resovle new horn clauses, closed \n",
       "- entailment with Horn clauses can be done in linear time with respect to the size of the KB.\n",
       "- forward / backward chaining\n",
       "  - forward chaining is sound and complete\n",
       "    - moreover, every definite clause in the original KB is  true in this model. \n",
       "    - a example of data-driven reasoning\n",
       "    - An agent can start with known data, adding premises as new percepts come in, and then incrementally apply the forward chaining algorithm to derive new conclusions. It doesn’t have to have a specific query in mind to do so.\n",
       "  - backward chaining: goal-directed reasoning. eg. what I should do\n",
       "    - Often, the cost  of backward chaining is much less than linear in the size of the knowledge base, because the  process touches only relevant facts. \n",
       "    - If the query is known to be true, then no work is needed. Otherwise, the algorithm finds implications in the KB whose conclusions is the query. If all the premises of one of those can be proved to be true (via backward chaining), then the query is true.\n",
       "\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.3 Logic\n",
       "\n",
       "- 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.\n",
       "- 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 α. \n",
       "- entailment between sentences—the idea that a sentence follows  logically from another sentence.\n",
       "  - α |= β <=> M(α) ⊆ M(β). \n",
       "  - α is a stronger assertion than β\n",
       "- KB ⊢i α, α is derived from KB by i\n",
       "- sound or truth preserving: inference algorithm that derives only entailed sentences\n",
       "- completeness: an inference algorithm is complete if  it can derive any sentence that is entailed.\n",
       "- grounding: the connection between logical reasoning processes and the real environment in which the agent exists. (how do we know if what we know is true)\n",
       "\n",
       "\n",
       "## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n",
       "\n",
       "-syntax of propositional logic defines the allowable sentences.\n",
       "- atomic sentence:\n",
       "  - True is true in every model and False is false in every model. \n",
       "  - The truth value of every other proposition symbol must be specified directly in the  model. For example, in the model m1 given earlier, P1,2 is false. \n",
       "- For complex sentences:\n",
       "  - ¬P is true iff P is false in m.  \n",
       "  - P∧ Q is true iff both P and Q are true in m.\n",
       "  - P∨ Q is true iff either P or Q is true in m. \n",
       "  - P ⇒ Q is true unless P is true and Q is false in m. \n",
       "  - P ⇔ Q is true iff P and Q are both true or both false in m. \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—there are only finitely many models to examine. \n",
       "  - If KB and α contain n symbols  in all, then there are 2^n models.\n",
       "  - time complexity O(2^n)\n",
       "  - space complexity O(n)\n",
       "  - every known inference algorithm for propositional logic has a worst-case complexity that  is exponential in the size of the input. \n",
       "\n",
       "\n",
       "## AIMA 7.5 Propositional Theorem Proving\n",
       "\n",
       "- 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.  \n",
       "- If the number of models is large but the length of the proof is short, then theorem proving can  be more efficient than model checking. \n",
       "- logical equivalence: two sentences α and β are logically equivalent if they are true in the same set of models. We write  this as α ≡ β.\n",
       "  - that ≡ is used to make claims about sentences, while ⇔ is used as part  of a sentence\n",
       "  - α ≡ β if and only if α |= β and β |= α.\n",
       "- deduction theorem:\n",
       "  - For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid. \n",
       "  - α |= β if and only if the sentence (α∧ ¬β) is unsatisfiable.\n",
       "  - every valid implication sentence describes a legitimate inference. \n",
       "- Inference and proof:\n",
       "  - Modus Ponens:\n",
       "    - ( α ⇒ β, α )/ β, whenever any sentences of the form α ⇒ β and α are given, then  the sentence β can be inferred.\n",
       "  - and elimination:\n",
       "    - (α∧β)/ α\n",
       "- proof as search:\n",
       "  - INITIAL STATE: the initial knowledge base.\n",
       "  - ACTIONS: the set of actions consists of all the inference rules applied to all the sentences that match the top half of the inference rule.\n",
       "  - RESULT: the result of an action is to add the sentence in the bottom half of the inference  rule\n",
       "  - GOAL: the goal is a state that contains the sentence we are trying to prove\n",
       "- finding a proof can be more efficient because the proof can ignore irrelevant propositions, no  matter how many of them there are.\n",
       "- monotonicity, which says that the set of entailed sentences can only increase as information is added to the knowledge base\n",
       "  - draw additional conclusions, but it cannot invalidate any conclusion α already inferred\n",
       "  - base—the conclusion of the rule must follow  regardless of what else is in the knowledge base. (since it must be true)\n",
       "\n",
       "\n",
       "## Module 7 Lecture Notes\n",
       "\n",
       "- Intelligent agents need knowledge about the world in order to reach good decisions.\n",
       "- Knowledge is contained in agents in the form of sentences in a knowledge representation language that are stored in a knowledge base.\n",
       "- A knowledge-based agent is composed of a knowledge base and an inference mechanism. It operates by storing sentences about the world in its knowledge base, using the  inference mechanism to infer new sentences, and using these sentences to decide what  action to take.\n",
       "- A representation language is defined by its syntax, which specifies the structure of  sentences, and its semantics, which defines the truth of each sentence in each possible  world or model.\n",
       "- The relationship of entailment between sentences is crucial to our understanding of  reasoning. A sentence α entails another sentence β if β is true in all worlds where  α is true. Equivalent definitions include the validity of the sentence α ⇒ β and the  unsatisfiability of the sentence α∧ ¬β. \n",
       "- Inference is the process of deriving new sentences from old ones. Sound inference algorithms derive only sentences that are entailed; complete algorithms derive all sentences  that are entailed.\n",
       "- Propositional logic is a simple language consisting of proposition symbols and logical  connectives. It can handle propositions that are known to be true, known to be false, or  completely unknown. \n",
       "- The set of possible models, given a fixed propositional vocabulary, is finite, so entailment can be checked by enumerating models. Efficient model-checking inference  algorithms for propositional logic include backtracking and local search methods and  can often solve large problems quickly. \n",
       "- Inference rules are patterns of sound inference that can be used to find proofs. The  resolution rule yields a complete inference algorithm for knowledge bases that are  expressed in conjunctive normal form. Forward chaining and backward chaining  are very natural reasoning algorithms for knowledge bases in Horn form. \n",
       "- resolution algo To show KB⊨𝛂 then we can show that KB ⋀ ¬𝛂 is unsatisfiable.\n",
       "  - First, convert (KB ⋀ ¬𝛂) into CNF\n",
       "  - Then apply the resolution rule to the resulting clauses.\n",
       "  - Resolve every pair that contains complementary literals to produce a new clause\n",
       "  - If that new clause isn’t already present, then add it to the set.\n",
       "  - Continue the process until one of two things happens:\n",
       "    - There are no new clauses that can be added. In this case, the KB does not entail 𝛂\n",
       "    - Two clauses resolve to yield the empty clause, in which case the KB does entail 𝛂\n",
       " \n",
       "\n",
       "## Module 7 Definitions\n",
       "* **Knowledge base** - is a set of sentences\n",
       "* **Setence** - expressed in a language called a knowledge representation language and represents some assertion about the world\n",
       "* **Axiom** - When the sentence is taken as being given without being derived  from other sentences\n",
       "* **Derived sentences** - a new sentence that is derived from others sentences\n",
       "* **Inference** - deriving new sentences from old sentences is called\n",
       "* **Background knowledge** - initial database\n",
       "* **Syntax** - which specifies all the  sentences that are well formed\n",
       "* **Semantics** - meaning of sentences, defines  the truth of each sentence with respect to each possible world. \n",
       "* **Model checking ** - checking entailment sentences, by propagating all possible combination of information\n",
       "* **Atomic sentences** - consist of a single proposition symbol\n",
       "* **Validity** - A sentence is valid if it is true in all models, eg P ∨ ¬P\n",
       "* **Tautologies** - must be true\n",
       "* **Satisfiability** - A sentence is satisfiable if it is true  in, or satisfied by, some model\n",
       "* **Complementary literals** - one is the negation of the other\n",
       "* **Clause** - a disjunction of literals—and a  literal and produces a new clause\n",
       "* **Factoring** - factor the case of (A∨A)\n",
       "* **Goal clause** - no positive literals\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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
