Midterm ReviewCH1 Summary: IntroCH2 Summary: Intelligent AgentsCH3 Summary: Problem SolvingCH4 Summary: Informed SearchCH5 Summary: Constraint SatisfactionCH 6 Summary: Adversarial SearchCH7 Summary: Logical AgentsCH 8, 9 Summary: FOLConstraint SatisfactionConstraint Satisfaction ProblemCSP as a Search ProblemQuestionsAdversarial SearchSpecific Setting Two-player, turn-taking, deterministic, fully observable, zero-sum, time-constrained gameChoosing an Action: Basic IdeaMinimax AlgorithmAlpha-Beta PruningExampleSlide 20Alpha-Beta AlgorithmLogical Representations and Theorem ProvingA Small Knowledge BaseSlide 24Following Material is Extrabut sometimes just doing random resolutions doesn’t work so hot….Resolution StrategiesExample (Set-of-Support)Slide 29Resolution HeuristicsExample (Shortest-Clause)Slide 32Slide 33Example (Pure Literal)Review: 2 Important PropertiesMidterm ReviewMidterm Review CMSC421 – Fall 2006CH1 Summary: IntroAI Definitions: dimensionshuman/rationalthink/actThree Major Components of AI AlgorithmsRepresentationReasoningLearningWhat makes AI hard:Problem FormulationComputational ComplexityCH2 Summary: Intelligent AgentsAn agent perceives and acts in an environment, has an architecture, and is implemented by an agent program. Task environment – PEAS (Performance, Environment, Actuators, Sensors)The most challenging environments are inaccessible, nondeterministic, dynamic, and continuous.An ideal agent always chooses the action which maximizes its expected performance, given its percept sequence so far.An agent program maps from percept to action and updates internal state. Reflex agents respond immediately to percepts. simple reflex agentsmodel-based reflex agentsGoal-based agents act in order to achieve their goal(s). Utility-based agents maximize their own utility function. All agents can improve their performance through learning.CH3 Summary: Problem Solving Problem Formulation: state space, initial state, successor function, goal test, path cost Search tree  state space Evaluation of strategies: completeness, optimality, time and space complexity Uninformed search strategies: breadth-first, depth-first, and variants Avoiding repeated statesCH4 Summary: Informed SearchCH4 Summary: Informed SearchHeuristicsBest-first Search AlgorithmsGreedy SearchA* Admissible heuristicsConstructing Heuristic functionsLocal Search AlgorithmsCH5 Summary: Constraint SatisfactionCSPs are a special kind of problem: states defined by values of a fixed set of variables, goal test defined by constraints on variable valuesBacktracking=depth-first search with one variable assigned per nodeVariable ordering and value selection heuristics help significantlyForward checking prevents assignments that lead to failure.Constraint propagation does additional work to constrain values and detect inconsistencies.The CSP representation allows analysis of problem structure.Tree structured CSPs can be solved in linear time.Local Search, e.g., min-conflicts, is often effective in practice.CH 6 Summary: Adversarial CH 6 Summary: Adversarial SearchSearchGames illustrate several important points about AIPerfection is unattainable -> approximationGood idea what to think about what to think aboutHeuristics can helpProblem Formulation: Game treeMinimax procedureAlpha-beta procedureCH7 Summary: Logical AgentsKnowledge-based agentsPropositional and first-order logicInference, validity, equivalence and satisfiabilityReasoning patterns ResolutionForward/backward chainingCH 8, 9 Summary: FOLSyntax - terms, WFF, quantifiersNew Inference rules for quantifiersUnification Horn clauses - FC, BCResolution RefutationConverting to clausal formConstraint SatisfactionConstraint Satisfaction Constraint Satisfaction ProblemProblemSet of variables {X1, X2, …, Xn}Each variable Xi has a domain Di of possible valuesUsually Di is discrete and finiteSet of constraints {C1, C2, …, Cp}Each constraint Ck involves a subset of variables and specifies the allowable combinations of values of these variablesGoal: Assign a value to every variable such that all constraints are satisfiedCSP as a Search ProblemCSP as a Search Problem Initial state: empty assignment Successor function: a value is assigned to any unassigned variable, which does not conflict with the currently assigned variables Goal test: the assignment is complete Path cost: irrelevantQuestionsQuestions1. Which variable X should be assigned a value next?1. Minimum Remaining Values/Most-constrained variable2. In which order should its domain D be sorted?1. least constrained value3. How should constraints be propagated?1. forward checking2. arc consistencyAdversarial SearchSpecific Setting Two-player, turn-taking, deterministic, fully observable, zero-sum, time-constrained game State spaceInitial state Successor function: it tells which actions can be executed in each state and gives the successor state for each actionMAX’s and MIN’s actions alternate, with MAX playing first in the initial stateTerminal test: it tells if a state is terminal and, if yes, if it’s a win or a loss for MAX, or a drawAll states are fully observableChoosing an Action: Basic Idea1) Using the current state as the initial state, build the game tree uniformly to the maximal depth h (called horizon) feasible within the time limit2) Evaluate the states of the leaf nodes3) Back up the results from the leaves to the root and pick the best action assuming the worst from MIN Minimax algorithmMinimax Algorithm1. Expand the game tree uniformly from the current state (where it is MAX’s turn to play) to depth h2. Compute the evaluation function at every leaf of the tree3. Back-up the values from the leaves to the root of the tree as follows:a. A MAX node gets the maximum of the evaluation of its successorsb. A MIN node gets the minimum of the evaluation of its successors4. Select the move toward a MIN node that has the largest backed-up valueAlpha-Beta PruningExplore the game tree to depth h in depth-first mannerBack up alpha and beta values whenever possiblePrune branches that can’t lead to changing the final decisionExampleThe beta value of a MINnode is an upper bound onthe final backed-up value.It can never increase1 = 12Example = 1The alpha value of a MAXnode is a lower bound onthe final backed-up value.It can never decrease1 = 12Alpha-Beta AlgorithmUpdate the alpha/beta value