COMP 590-096 Fall 2010
Midterm Review
Terms
Be able to define the following terms and answer basic questions about them:
- Agents and environments
- Rationality
- PEAS
- Environment characteristics: fully vs. partially observable, deterministic vs. stochastic, episodic vs. sequential, static vs. dynamic, discrete vs. sequential, single-agent vs. multi-agent, known vs. unknown
- Agent types: reflex, model-based reflex, goal-based, utility-based
- Search
- Search problem formulation: initial state, actions, transition model, goal state, path cost
- State space
- Search tree
- Evaluation of search strategies: completeness, optimality, time complexity, space complexity
- Uninformed search strategies: breadth-first search, uniform cost search, depth-first search, iterative deepening search
- Informed search strategies: greedy best-first, A*
- Heuristics: admissibility, dominance
- Local search: hill climbing, beam search, annealing
- Constraint satisfaction problems
- Backtracking search
- Heuristics: most constrained/most constraining variable, least constraining value
- Forward checking, constraint propagation, arc consistency
- Games
- Zero-sum games
- Game tree
- Minimax
- Alpha-beta pruning
- Evaluation function
- Quiescence search
- Horizon effect
- Game theory
- Normal form representation
- Dominant strategy
- Nash equilibrium (both pure and mixed strategy)
- Pareto optimality
- Logic
- Propositional logic
- Syntax and semantics
- Entailment
- Inference: soundness, completeness, inference rules
- Inference for definite clauses: forward chaining, backward chaining
- First order logic
- Propositionalization
- Substitution, unification
Example test questions
- Suppose you have to design an agent to play the game of Scrabble. Write a PEAS specification for the agent and characterize the task environment according to the seven relevant categories (list them first).
- Can an environment be both known and unobservable? Give an example.
- What is the distinction between a world state and a search tree node?
- Discuss the relative strengths and weaknesses of breadth-first search vs. depth-first search for AI problems.
- Explain why it is a good heuristic to choose the variable that is most constrained but the value that is least constraining in a CSP search.
- Suppose you have an oracle that correctly predicts the opponent’s move in any state. Using this, formulate the definition of a game as a single-agent search problem. Describe an algorithm for finding the optimal move.
- Consider the following game tree (MAX moves first):
- Write down the minimax value of every non-terminal node next to that node.
- How will the game proceed, assuming both players play optimally?
- Cross out the branches that do not need to be examined by alpha-beta search in order to find the minimax value of the top node, assuming optimal move ordering.
- Consider the following game:
PlayerA: Action 1 / Player A: Action 2
Player B: Action 1 / A = 2, B = -2 / A = -3, B = 3
Player B: Action 2 / A = -3, B = 3 / A= 4, B = -4
- Find dominant strategies (if any).
- Find pure strategy equilibria (if any).
- Find mixed strategy equilibria (if any).
- Use a truth table to prove De Morgan’s Law: ¬ () ¬ ¬
- According to some political pundits, a person who is radical (R) is electable (E) if he/she is conservative (C), but otherwise is not electable. Which of the following are correct representations of this assertion?
- (R E) C
- R (E C)
- R ((C E) E)
- Which of the following statements are correct?
- False |= True.
- True |= False.
- (A B) |= (A B).
- A B |= A B.
- A B |= A B.
- Which of the following are valid (necessarily true) sentences?
- (x x=x) (yz y=z).
- x P(x) P(x).
- x Smart(x) (x=x).
- Translate into first-order logic the following sentences:
- No two people have the same social security number.
- There is an agent who sells insurance policies only to people who are not insured.
- Politicians can fool some of the people all of the time, and they can fool all of the people some of the time, but they can’t fool all of the people all of the time.