WIXLIB

IntroductionTo GameTheory:Two-PersonGamesof PerfectInformationandWinningStrategies#1

Game?Theory?#2

Lecture Outline IntroductionProperties of GamesTic-ToeGame TreesStrategiesImpartial Games– Nim– Hackenbush Sprague-Grundy Theorem#3

Game Theory Game Theory is a branch of applied mathused in the social sciences (econ), biology,compsci, and philosophy. Game Theorystudies strategic situations in which oneagent's success depends on the choices ofother agents.#4

Broad Applicability Finding equilibria (Nash) – sets of strategieswhere agents are unlikely to change behavior. Econ: understand and predict the behavior offirms, markets, auctions and consumers. Animals: (Fisher) communication, gender Ethics: normative, good and proper behavior PolySci: fair division, public choice. Players arevoters, states, interest groups, politicians. Software: verifying interfaces can be viewed as atwo-player game between the program and theenvironment (e.g., Henzinger, .)#5

Game Properties Cooperative (binding contracts, coalitions) ornon-cooperative Symmetric (chess, checkers: changingidentities does not change strategies) orasymmetric (Axis and Allies, Soulcalibur) Zero-sum (poker: your wins exactly equal mylosses) or non-zero-sum (prisoner's dilemma:gain by me does not necessarily correspond toa loss by you)#6

Game Properties II Simultaneous (rock-paper-scissors: we alldecide what to do before we see otheractions resolve) or sequential (your turn,then my turn) Perfect information (chess, checkers, go:everyone sees everything) or imperfectinformation (poker, Catan: some hiddenstate) Infinitely long (relates to set theory) or finite(chess, checkers: add a “tie” condition)#7

Game Properties III Deterministic (chess, checkers, rock-paperscissors, tic-tac-toe: the “game board” isdeterministic, even if the players are not) vsnon-deterministic (Yahtzee, Monopoly, poker:you roll dice or draw lots) More later .#8

Game Representation We will represent games as trees– Tree of all possible game instances There is one node for every possible state ofthe game (e.g., every game boardconfiguration)– Initial Node: we start here– Decision Node: I have many moves– Terminal Node: who won? what's my score?#9

Introducing: Tic-Toe Tic-Toe is like Tic-Tac-Toe, but on a 2x2board where two-in-a-row wins (notdiagonal).– X goes first– Resolutions: X wins, tie , X loses Example game:.X.X.O.– Later: Can O ever win?– Later: Can O ever win if X is smart?XXO.X wins!#10

Tic-Toe Trees Partial game tree for Tic-Toe.X.X.O.XO.X.X.X.X.O#11

Tic-Toe Trees. More abstractlyX MovesX.X.O MovesXO.X MovesXOX .X.O.XXO .XO MovesX.OX MovesXO.X.X.X .OXX MovesX .X OX X. OX Wins O Moves X Wins O Moves X Wins X WinsXOOXXOOXTie!Tie!#12

More Definitions An instance of a game is a path through agame tree starting at the initial node andending in a terminal node. X's moves in a game instance P are the set ofedges along that path P taken from decisionnodes labeled “X moves”. A strategy for X is a function mappingdecision each node labeled “X moves” to asingle outgoing edge from that node.#13

Still Going! A deterministic strategy for X, a deterministicstrategy for O, and a deterministic game leaddeterministically to a single game instance– Example: if you always play tic-tac-toe by going inthe uppermost, leftmost available square, and Ialways play it by going in the lowermost,rightmost available square, every time we playwe'll have the same result. Now we can study various strategies and theiroutcomes!#14

Winning Strategies A winning strategy for X on a game G is astrategy S1 for X on G such that, for allstrategies S2 for O on G, the result of playingG with S1 and S2 is a win for X. Does X have a winning strategy for Tic-Toe? Does O have a winning strategy for Tic-Toe? Fact: If the first player in a turn-baseddeterministic game has a winning strategy,the second player cannot have a winningstrategy.– Why?#15

Impartial Games An impartial game has (1) allowable movesthat depend only on the position and not onwhich player is currently moving, and (2)symmetric win conditions (payoffs).– Only difference between Player1 and Player2 isthat Player1 goes first. This is not the case for Chess: White cannotmove Black's pieces– So I need to know which turn it is to categorizethe allowable moves. A game that is not impartial is partisan.#16

Nim Nim is a two-player game in which players taketurns removing objects from distinct heaps.– Non-cooperative, symmetric, sequential,perfect information, finite, impartial One each turn, a player must remove at leastone object, and may remove any number ofobjects provided they all come from the sameheap. If you cannot take an object, you lose. Similar to Chinese game “Jian-shizi” (“pickingstones” 捡石子 ); European refs in 16th century#17

Example Nim Start with heaps of 3, 4 and 5 objects:– AAA, BBBB, CCCCC Here's a game:– AAABBBBCCCCCI take 2 from A– ABBBBCCCCCYou take 3 from C– ABBBBCCI take 1 from B– ABBBCCYou take 1 from B– ABBCCI take all of A–BBCCYou take 1 from C–BBCI take 1 from B–BCYou take all of C–B–I take all of BYou lose! (you cannot go)#18

Real-Life Nim Demo I will now play Nim against audiencemembers. Starting Board: 3, 4, 7– AAA, BBBB, CCCCCCC You go first .#19

The Rats of NIM How did I win every time?– Did I win every time? If not, pick on memercilessly. Nim can be mathematically solved for anynumber of initial heaps and objects. There is an easy way to determine whichplayer will win and what winning moves areavailable.– Essentially, a way to evaluate a board anddetermine its payoff / goodness / winning-ness.#20

Analysis You lose on the empty board. Working backwards, you also lose on twoidentical singleton heaps (A, B)– You take one, I take the other, you're left withthe empty board. By induction, you lose on two identical heapsof any size (An, Bn)– You take x from heap A. I also take x from heap B,reducing it to a smaller instance of “two identicalheaps”.#21

Analysis II On the other hand, you win on a board with asingleton heap (C).– You take C, leaving me with the empty board.n You win with a single heap of any size (C ). What if we add these insights together?is a loss for the current player– (AA, BB)is a win for the current player– (C)– (AA, BB, C) is what?#22

Analysis III (AA, BB, C) is a win for the current player.– You take C, leaving me with (AA, BB) – which isjust as bad as leaving me with the empty board. When you take a turn, it becomes my turn– So leaving me with a board that would be a lossfor you, if it were your turn– . becomes a win for you! (AAA, BBB, C) – also a win for Player1. (AAAA, BBBB, CCCC) – also a win for Player1.#23

Generalize We want a way of evaluating nim heaps to seewho is going to win (if you play optimally). Intuitively . Two equal subparts cancel each other out– (AA, BB) is the same as the empty board ( , ) Win plus Loss is Win– (CC) is a win for me, (A,B) is a loss for me,(A,B,CC) is a win for me. What do we know that's kind of like additionbut cancels out equal numbers?#24

The Trick! Exclusive Or– XOR, , vector addition over GF(2), or nim-sum If the XOR of all of the heaps is 0, you lose!– empty board 0 lose– (AAA,BBB) 3 3 0 lose Otherwise, goal is to leave opponent with aboard that XORs to zero– (AAA,BBB,C) 3 3 1 1, so move to (AAA,BBB) or (AA,BBB,C) or (AAA,BB,C)#25

Real-Life Nim Demo II I played Nim against audience members. Starting Board: 3, 4, 7– AAA, BBBB, CCCCCCC The nim sum is 3 4 7 0– A loss for the first player! This time, I'll go first. You, the audience, must beat me. Muahaha!#26

Hackenbush Hackenbush is a two-player impartial gameplayed on any configuration of line segmentsconnected to one another by their endpointsand to a ground. On your turn, you “cut” (erase) a linesegment of your choice. Line segments nolonger connected to the ground are erased. If you cannot cut anything (empty board) youlose.#27

Hackenbush Example Eachis a line segment. Ignore color. Let's play! I'll go first.Ground#28

Hackenbush Subsumes Nim Consider (AAA, BBB, C) (3,3,1) in Nim Who wins this completely unrelatedHackenbush game?Ground#29

A Thorny Problem What about that Hackenbush tree? What value (nim-sum) does it have? Who wins?Ground#30

A Simple Twig Consider a simpler tree . What moves do you have?Ground#31

Twig Analysis Consider a simpler tree . What moves do you have?(empty)Ground#32

Maximum Excluded You can move to “2”, “2” or “0”. The minimal excluded of (2,2,0) is 1– mex(2,2,0) 1 value of that twigYes, this mex thingcame out of nowhere.(empty)Ground#33

Game Equivalence I've claimed that the twig has nim-sum 1How to prove that? When are games equal?We write G G' when G is equivalent to G'.Lemma 1. Iff G G' then for all H, G H G' H. Lemma 2. G G 0. Lemma 3. G G' if and only if G G' 0.– Restated: G G' iff G G' is a loss for Player 1.– If G G', then G G G G' (by Lemma 1).– Since G G 0 (by Lemma 2), we have 0 G G'.#34

Trivia: Games In 1995 Klaus Teuber published thismultiplayer game of trading, planning andresource management. The first German-styledesigner board game to obtain mainstreaminternational popularity, it popularizednotions such as simple rules, indirect playerinteraction, abstract components, strategyover luck, economy over military, andkeeping all players in the game the wholetime.#35

Trivia: Games In 1993 Richard Garfield earned his PhD incombinatorial mathematics from Penn, becoming amathematics professor in Washington. In the sameyear, he released this game, which was inducted into the Games Magazine hall of fame in 2003 as soonas the 10 year limit passed. Garfield was awarded apatent for “a novel method of game play and gamecomponents that in one embodiment are in the formof trading cards" including concepts such as changingthe orientation of a game component to indicate use– a patent which is not enforced against othercompanies.#36

A Simple Twig So twig 1 if twig 1 0 twig 1 0 means twig 1 is a first-player loss– You go first; two trials against me to verify .twigoneGround#37

Generalized Pruning Can replace any subtree above a singlebranch point with the XOR of those branches– Via similar game-equivalence argumentpruningpruning1 2 34 1 1 4GroundThe whole tree has value “5”.#38

Door Analysis What about cycles? What is the value (nim-sum) of this door?Ground#39

Door Analysis Well, what moves can you take from here?Ground#40

Door Analysis You can move to “0”, “2” or “2”.– mex(2,2,0) 1– Value of door 1(recall: minimal excluded)Ground#41

Fusion Principle We may replace any cycle with an equivalentsubgraph where all of the non-ground verticesof that cycle are fused into one vertex and allof the ground vertices of that cycle are fusedinto another vertex.FusingDoneGround#42

Fusion Principle We may replace any cycle with an equivalentsubgraph where all of the non-ground verticesof that cycle are fused into one vertex and allof the ground vertices of that cycle are fusedinto another vertex.Fusion ResultYou can't stop in the middle!Ground#43

Cold Fusion Let's boil the house down to somethingsimple!FusionFusionIs JustGroundThe whole house has value 1 1 0.How would I check that?#44

Hackenbush Example This board has value 5 0 1 4. You go first. Beat me. (Time permitting.)Tree 5House 0Door 1Ground#45

Why Do We Care? . about Nim and Hackenbush? Theorem (Sprague-Grundy, '35-'39). Everyimpartial game is equivalent to a nim sum. Proof: How?– Hint: what is the most important proof techniquein computer science?#46

Why Do We Care? . about Nim and Hackenbush? Theorem (Sprague-Grundy, '35-'39). Everyimpartial game is equivalent to a nim sum. Proof: By structural induction on the set(tree) representing the game.– Let G {G1, G2, ., Gk}. Gi is the game resulting ifthe current player takes move i.– By IH, each Gi is a nim sum, Gi Ni.– Let m mex(N1, N2, ., Nk). We'll show: G m.#47