CS 470 Fall 2008

Final Exam Review

The final is comprehensive

You should bring a calculator, and you can bring one 8.5"x11" sheet of notes. Know the stuff from the previous two review sheets. New stuff is as follows:

Sequential Choice for Nondeterminstic Worlds

Markov decision processes: transition probability, discount factor, rewards
Nondeterministic consequences of choice

Instantaneous rewards
Next state

Definitions and terms

U(pi,s)
U(s)
Q(a,s)

Recursion relations
Value iteration

algorithm
philosophy
parameters

Policy iteration

algorithm
philosophy
parameters

Q-learning

weighted averages
algorithm
definition of "convergence"
conditions for convergence

Multi-Agent Choice

Framework: S, A₁, A₂, C, G₁, G_2, U₁, U_2,etc.
Payoff matrices: non-zero sum games, zero-sum games, general-sum games
Extensive-form games (turn taking)
Minimax

Value
Solution
Alpha-Beta pruning: know algorithm and be able to apply it

Evaluation functions
Definitions of a solution

Minimax
Nash equilibrium
Strategic dominance
Best response
Pareto dominance