Berkeley MBA 211 - A Brief Introduction to Game Theory

Unformatted text preview:

CHECKMATE! A Brief Introduction to Game TheoryWelcome!Game Theory: Economic or Combinatorial?Why study games?Combinatorial Game Theory HistoryWhat is a combinatorial game?What games are out, what are in?Combinatorial Game Theory The Big PictureClassification of GamesNim : The Impartial Game pt. INim: The Impartial Game pt. IINim: The Impartial Game pt. IIIDomineering: A partisan gameSlide 14What do we want to know about a particular game?Combinatorial Game Theory The Basics I - Game definitionCombinatorial Game Theory The Basics II - Examples: 0Combinatorial Game Theory The Basics II - Examples: *Combinatorial Game Theory The Basics II - Examples: 1Combinatorial Game Theory The Basics II - Examples: –1Combinatorial Game Theory The Basics II - ExamplesCombinatorial Game Theory The Basics III - Outcome classesCombinatorial Game Theory The Basics IV - Negatives & SumsSlide 24Slide 25Slide 26Slide 27Slide 28Combinatorial Game Theory The Basics IV - Values of gamesCombinatorial Game Theory The Basics V - Final thoughts“Computational” Game Theory (for non-normal play games)Computational Game TheoryGAMESMAN Analysis: TacTix, or 2-D NimGAMESMAN Analysis: Tic-Tac-ToeGAMESMAN Tic-Tac-Toe VisualizationExciting Game Theory Research at BerkeleyExciting Game Theory Research ChessExciting Game Theory Research Solving gamesSummaryCHECKMATE!A Brief Introductionto Game TheoryDan GarciaUC BerkeleyQuickTime™ and aAnimation decompressorare needed to see this picture.The WorldKasparovQuickTime™ and aQuickDraw decompressorare needed to see this picture.A Brief Introduction to Game Theory2/39Welcome!•Introduction•Topic motivation, goals•Talk overview◊Combinatorial game theory basics w/examples◊“Computational” game theory◊Analysis of some simple games◊Research highlightsA Brief Introduction to Game Theory3/39Game Theory:Economic or Combinatorial?•Economic◊von Neumann and Morgenstern’s 1944 Theory of Games and Economic Behavior◊Matrix games◊Prisoner’s dilemma◊Incomplete info, simultaneous moves◊Goal: Maximize payoff•Combinatorial◊Sprague and Grundy’s 1939 Mathematics and Games◊Board (table) games◊Nim, Domineering◊Complete info, alternating moves◊Goal: Last moveA Brief Introduction to Game Theory4/39Why study games?•Systems design◊Decomposition into parts with limited interactions•Complexity Theory •Management◊Determine area to focus energy / resources•Artificial Intelligence testing grounds•“People want to understand the things that people like to do, and people like to play games” – Berlekamp & WolfeA Brief Introduction to Game Theory5/39Combinatorial Game TheoryHistory•Early Play◊Egyptian wall painting of Senat (c. 3000 BC)•Theory◊C. L. Bouton’s analysis of Nim [1902]◊Sprague [1936] and Grundy [1939] Impartial games and Nim◊Knuth Surreal Numbers [1974] ◊Conway On Numbers and Games [1976]◊Prof. Elwyn Berlekamp (UCB), Conway, & Guy Winning Ways [1982]A Brief Introduction to Game Theory6/39What is a combinatorial game?•Two players (Left & Right) move alternately•No chance, such as dice or shuffled cards•Both players have perfect information◊No hidden information, as in Stratego & Magic•The game is finite – it must eventually end•There are no draws or ties•Normal Play: Last to move wins!A Brief Introduction to Game Theory7/39What games are out, what are in?•In◊Nim, Domineering, Dots-and-Boxes, Go, etc.•In, but not normal play◊Chess, Checkers, Othello, Tic-Tac-Toe, etc. ◊ All card games◊ All dice games•OutA Brief Introduction to Game Theory8/39Combinatorial Game TheoryThe Big Picture•Whose turn is not part of the game•SUMS of games◊You play games G1 + G2 + G3 + …◊You decide which game is most important◊You want the last move (in normal play)◊Analogy: Eating with a friend, want the last biteA Brief Introduction to Game Theory9/39Classification of Games•Impartial◊Same moves available to each player◊Example: Nim•Partisan◊The two players have different options◊Example: DomineeringA Brief Introduction to Game Theory10/39Nim : The Impartial Game pt. I•Rules:◊Several heaps of beans◊On your turn, select a heap, and remove any positive number of beans from it, maybe all •Goal◊Take the last bean•Example w/4 piles: (2,3,5,7)3572A Brief Introduction to Game Theory11/39Nim: The Impartial Game pt. II•Dan plays room in (2,3,5,7) Nim•Pair up, play (2,3,5,7)◊Query:•First player win or lose?•Perfect strategy?◊Feedback, theories?•Every impartial game is equivalent to a (bogus) Nim heap3572A Brief Introduction to Game Theory12/39Nim: The Impartial Game pt. III•Winning or losing?1011101111◊ Binary rep. of heaps11◊ Nim Sum == XOR3572◊ Zero == Losing, 2nd P win• Winning move?◊ Find MSB in Nim Sum◊ Find heap w/1 in that place◊ Invert all heap’s bits from sum to make sum zero01100A Brief Introduction to Game Theory13/39Domineering: A partisan game•Rules (on your turn):◊Place a domino on the board◊Left places them North-South◊Right places them East-West•Goal◊Place the last domino•Example game•Query: Who wins here?Left (bLue)Right (Red)A Brief Introduction to Game Theory14/39Domineering: A partisan game•Key concepts◊By moving correctly, you guarantee yourself future moves.◊For many positions, you want to move, since you can steal moves. This is a “hot” game.◊This game decomposes into non-interacting parts, which we separately analyze and bring results together.Left (bLue)Right (Red)=+++++A Brief Introduction to Game Theory15/39What do we want to know about a particular game?•What is the value of the game?◊Who is ahead and by how much?◊How big is the next move?◊Does it matter who goes first?•What is a winning / drawing strategy?◊To know a game’s value and winning strategy is to have solved the game◊Can we easily summarize strategy?A Brief Introduction to Game Theory16/39Combinatorial Game TheoryThe Basics I - Game definition•A game, G, between two players, Left and Right, is defined as a pair of sets of games:◊G = {GL | GR }◊GL is the typical Left option (i.e., a position Left can move to), similarly for Right.◊GL need not have a unique value◊Thus if G = {a, b, c, … | d, e, f, …}, GL means a or b or c or … and GR means d or e or f or ...A Brief Introduction to Game Theory17/39Combinatorial Game TheoryThe Basics II - Examples: 0•The simplest game, the Endgame, born day


View Full Document
Download A Brief Introduction to Game Theory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A Brief Introduction to Game Theory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Brief Introduction to Game Theory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?