CS 416 Artificial Intelligence Lecture Lecture 23 23 Making Making Complex Complex Decisions Decisions Chapter Chapter 17 17 Final Exam Reminder Reminder Final Final Exam Exam is is Tuesday Tuesday May May 66thth at at 77 p m p m Let Let me me know know ifif you you have have aa legitimate legitimate conflict conflict Zero sum games Payoffs Payoffs in in each each cell cell sum sum to to zero zero Morra Morra Two Two players players Odd Odd and and Even Even Action Action Each Each player player simultaneously simultaneously displays displays one one or or two two fingers fingers Evaluation Evaluation ff total total number number of of fingers fingers ifif ff odd odd Even Even gives gives ff dollars dollars go go to to Odd Odd ifif ff even even Odd Odd gives gives ff dollars dollars go go to to Even Even Optimal strategy von mixed von Neumann Neumann 1928 1928 developed developed optimal optimal mixed strategy strategy for for two player two player zero sum zero sum games games Because Because what what one one player player wins wins the the other other loses loses just just keep keep track track of of one one player s player s payoff payoff in in each each cell cell Even Even assume assume this this player player wishes wishes to to maximize maximize Maximin Maximin technique technique make make game game aa turn taking turn taking game game and and analyze analyze Maximin Change Change the the rules rules of of Morra Morra for for analysis analysis Force Force Even Even to to reveal reveal strategy strategy first first apply apply minimax minimax algorithm algorithm Odd Odd has has an an advantage advantage and and thus thus the the outcome outcome of of the the game game is is Even s Even s worst worst case case and and Even Even might might do do better better in in real real game game The The utility utility of of this this game game to to Even Even is is 3 3 Maximin Change Change the the rules rules of of Morra Morra for for analysis analysis Force Force Odd Odd to to reveal reveal strategy strategy first first Apply Apply minimax minimax algorithm algorithm Odd Odd would would always always select select one one to to minimize minimize Odd s Odd s loss loss Even Even would would always always select select one one to to maximize maximize Even s Even s gain gain This This game game favors favors Even Even The The utility utility of of this this game game to to Even Even is is 2 2 Combining two games Even s Even s combined combined utility utility EvenFirst Utility EvenFirst Utility Even s Utility Even s Utility OddFirst Utility OddFirst Utility 3 3 Even s Utility Even s Utility 22 Considering mixed strategies Mixed Mixed strategy strategy select select one one finger finger with with prob prob pp select select two two fingers fingers with with prob prob 11 pp IfIf one one player player reveals reveals strategy strategy first first second second player player will will always always use use aa pure pure strategy strategy expected expected utility utility of of aa mixed mixed strategy strategy U1 U1 pp uuone 1 p 1 p uutwo one two expected expected utility utility of of aa pure pure strategy strategy U2 U2 max max u uone utwo one u two U2 U2 is is always always greater greater than than U1 U1 Modeling as a game tree Because Because the the second second player player will will always always use use aa fixed fixed strategy strategy Still Still pretending pretending Even Even goes goes first first What is outcome of this game Player Player Odd Odd has has aa choice choice Always Always pick pick the the option option that that minimizes minimizes utility utility to to Even Even Represent Represent two two choices choices as as functions functions of of pp Odd Odd picks picks line line that that is is lowest lowest dark dark part part on on figure figure Even Even maximizes maximizes utility utility by by choosing choosing pp to to be be where where lines lines cross cross 5p 5p 33 44 7p 7p pp 7 12 7 12 E Eutility 1 12 1 12 utility Pretend Odd must go first Even s Even s outcome outcome decided decided by by pure pure strategy strategy dependent dependent on on q q Even Even will will always always pick pick maximum maximum of of two two choices choices Odd Odd will will minimize minimize the the maximum maximum of of two two choices choices Odd Odd chooses chooses intersection intersection point point 5q 5q 33 44 7q 7q qq 7 12 7 12 E Eutility 1 12 1 12 utility Final results Both Both players players use use same same mixed mixed strategy strategy ppone 7 12 7 12 one pptwo 5 12 5 12 two Outcome Outcome of of the the game game is is 1 12 1 12 to to Even Even Generalization Two Two players players with with nn action action choices choices mixed mixed strategy strategy is is not not as as simple simple as as p p 1 p 1 p itit is is p p11 pp22 ppn 1 1 p11 p p22 p pn 1 n 1 1 p n 1 Solving Solving for for optimal optimal pp vector vector requires requires finding finding optimal optimal point point in in n 1 n 1 dimensional dimensional space space lines lines become become hyperplanes hyperplanes some some hyperplanes hyperplanes will will be be clearly clearly worse worse for for all all pp find find intersection intersection among among remaining remaining hyperplanes hyperplanes linear linear programming programming can can solve solve this this problem problem Repeated games Imagine Imagine same same game game played played multiple multiple times times payoffs payoffs accumulate accumulate for for each each player player optimal optimal strategy strategy is is aa function function of of game game history history must must select select optimal optimal action action for for each each possible possible game game history history Strategies Strategies perpetual perpetual punishment punishment cross cross me me once once and and I ll I ll take take us us both both down down forever forever tit tit for for tat tat cross cross me me once once and and I ll I ll cross cross you you the the subsequent subsequent move move The design of games Let s Let s invert invert the the strategy strategy selection selection process process to to design design fair effective fair effective games games Tragedy Tragedy of of the the commons commons individual individual farmers farmers bring bring their their livestock livestock to to the the town town commons commons to to graze graze commons commons is is destroyed destroyed and and all all experience experience negative negative utility utility all