-- Review 1 handout: old final exam. -- A fun problem -->> FINAL is on FRIDAY. 8:30-11:30. Open book + 1 sheet of notes -->> Q/A session on Wednesday at noon in this room. -->> I (Avrim) will be away and out of email contact starting tomorrow night, so send email to your recitation instructor or to Seth. REVIEW ------ Course has been about: program design -- the ideas that you need to work out when designing a program to solve a problem efficiently. - algorithms - data structures and ADTs - running time and correctness - implementing all this in a well-written program General topics: programming techniques - pointers, memory allocation - recursion - Abstract Data Types - classes, member functions - inheritance, class heirarchies - loop invariants Specific ADTs: - stacks - queues - priority queues - dictionaries / tables, and variations. - graphs Data structures / concepts - trees: tree traversals, binary search trees, balanced search trees (2-3, tree rotations) - array representations of trees - heaps - hashing: hash functions and collision resolution methods: separate chaining, linear probing, double hashing - representations of graphs as adjacency lists, adj matrices. Algorithms - divide and conquer - memoizing - dynamic programming: knapsack, shortest paths. - Sorting (insertion, quick, merge, heap, radix) - game tree search. - graph-searching methods: DFS, BFS, PFS application to shortest paths, Min Spanning Tree - algs on adjacency matrices. - Finite automata, regular expressions. Analysis techniques: - O,Theta, Omega notation - invariants - recurrences ============================================================================= Two person zero-sum Games aka Matrix Games ------------------------------------------- Here's a game: A and B each hide either a nickel or a dime behind their backs. Then they reveal their coins. If match, then A gets both. Else, B gets both. This is an example of a 2-person zero-sum game. Zero-sum means that what A wins = what B loses, and vice versa. Is this a fair game? (who would you rather be?) What's a good strategy? E.g., What if A always hides a nickel? -> loses 5 cents per round What if A picks randomly? Say that B knows that A is picking randomly What's a good strategy for B? B always hides a nickel. 1/2 of time A gets 5 cents, 1/2 of time A loses 10 cents. This kind of game is often called a MATRIX GAME: Payoff matrix (payoff to A) 5 -5 -10 10 row-player picks a row and column-player picks a column, and you get payoff. "Pure strategy" -> deterministic choice of row(column) "Mixed strategy" -> probabilistic choice. For a given (pure or mixed) strategy S_A of A and S_B of B, the value V(S_A, S_B) of the game to A is A's expected winning per round, given that both players follow this strategy. E.g., if S_A is "A picks randomly" and S_B is "B always hides a nickel", then V() = -2.5 cents. For a given S_A, what is min V(S_A, S_B)? What does this mean? S_B Can think of this as the value of the game if A uses S_A, and announces this to B, who can then use this information to pick his best strategy S_B. In fact, if A announces his strategy, then B can pick a pure (non-randomized) strategy? Why? This is like the problem of selecting stocks when you know the future -- there's no reason to diversify. For a given S_B, what does max V(S_A, S_B) mean? S_A Can think of this as the value of the game if B uses S_B, and announces this to A, who can then use this information to pick his best strategy S_A. Suppose that someone has to announce their strategy first. Which would you rather be? Amazing theorem (Minimax theorem) first proven by von Neumann max min V(S_A, S_B) = min max V(S_A, S_B) S_A S_B S_B S_A Let's solve the left-hand side for this game. I.e., what's the best strategy S_A for A if A has to announce it first? Say A puts p prob on nickel and (1-p) prob on dime. If B chooses first column, then A gets expected 5p - 10(1-p) = 15p - 10 If B chooses second column, then A gets expected -5p + 10(1-p) = -15p + 10 Higher p makes first one go up, lower p makes second go up. So, best for A is to make these equal: 30p = 20, p = 2/3. Value of game is....0. (So, yes, it's a fair game). Now, let's solve right-hand side for this game. Say B puts prob q on nickel and (1-q) on dime. If A chooses first row, then A gets expected 5q - 5(1-q) = 10q - 5 If A chooses second row, then A gets expected -10q + 10(1-q) = -20q + 10 set to equality... 30q = 15, q = 1/2. Value of game is....0. The Minimax theorem is very similar to some other amazing theorems, like one called the "max-flow min-cut theorem" and is a special case of an even more amazing theorem called "linear programming duality". ============================================================================= If need to kill some time, describe Simple-Poker 3 card deck: {1,2,3}, 2 players A and B. Each player antes $1. Then each player gets 1 card. Then, starting with A, can pass, bet $1 or fold. if nobody folds, they reveal their cards and the higher card wins. Specifically, the possibilities are: A passes and B passes: winner wins $1 (the other guy's ante). A bets and B folds: A wins $1. A bets, B calls: winner wins $2 A passes, B bets, A folds: B wins $1 A passes, B bets, A calls: winner wins $2 E.g., Based on A's card, A has 3 options: 1. pass and fold if B bets. (weakest - no reason to do if have a 3) 2. pass and call if B bets. (medium, but no reason to do if have a 1) 3. Bet. (strongest) Can solve. What's the optimal strategy? Turns out it's: If A has a 1 then with 5/6 prob use strategy 1, with 1/6 prob use strategy 3 2 then with 1/2 prob use strategy 1, with 1/2 prob use strategy 2 3 then with 1/2 prob use strategy 2, with 1/2 prob use strategy 3 Value of game is -1/18. I.e., it's better to be B. (which is weird but true...)