Report

Princess and the Roses Naomi Carrillo & Samantha Helstrom iCamp 2012 Background • Questions about Princess and the Roses are unsolved • Featured in Winning Ways for Your Mathematical Plays – Small number of bushes with large number of roses: “parity considerations are paramount” – Large number of bushes with few roses: “triality triumphs” • Concept- two princes fighting for the love of a princess by bringing her roses Game Description • 2 player game • n number of bushes with any number of roses in each bush • Notation- array of numbers Ex: [6,3,7,4,2] • Legal move: remove ONE rose from ONE bush or remove ONE rose from TWO different bushes • Person to remove last rose wins Game Example 1 2 3 Player 1 removed 2 roses from bush 1 and bush 2 1 2 3 Player 2 removed 2 roses from bush 2 and bush 3 1 2 3 Player 1 removed 1 rose from bush 2 1 2 3 Player 2 removed 2 roses from bush 1 and bush 2 1 2 3 Player 1 removed 2 roses from bush 1 and bush 3 1 2 3 Game classification • Determinate: win does not rely on chance • Zero-sum: one definite winner and loser • Symmetric: payoff of game depends on what strategy the player chooses • Perfect information: everything is known by both players • Sequential: players alternate turns • Normal: person to take last rose wins Questions for Investigation • Is the game fair or unfair? • Which player has the winning strategy for certain game states? • How many different game states exist for a starting game board? Combinatorics • How many game states? m = # of bushes ni = # of roses n1 . n2 . n3 . . . nm-1 . nm Multiply the number of roses in each bush by each other. Results for 1 bush game # of roses position 1 n 2 p 3 n 4 p 5 n The pattern continues… n- next player has winning strategy p- previous player has winning strategy Results for 2 bush game # of roses position (odd,odd) n (odd,even) n (even,even) p n- next player has winning strategy p- previous player has winning strategy winning strategy- make # of roses in both bushes EVEN on your turn Game Tree Example (2,3) (2,2) (1,2) (1,1) (0,1) (0,2) (1,1) (1,0) (0,0) (0,1) (0,0) (0,1) (0,0) (0,0) (0,0) (0,0) (0,2) (1,3) (1,2) (1,2) (0,3) (0,1) (0,2) (0,1) (0,1) (0,2) (1,1) (0,0) (0,2) (0,0) (0,1) (0,1)(0,0) (0,1) (0,0) (0,0) (0,0) (0,0) (1,1) (0,1) (0,0) (0,0) (1,0) (0,0) Results for 3 bush game # of roses position (odd,odd,odd) p (odd,even,even) n (odd,odd,even) n (even,even,even) p n- next player has winning strategy p- previous player has winning strategy winning strategy- make # of roses in all 3 bushes either ALL odd or ALL even on your turn Adaptive Learning Results (2,2,2) Player 2 has winning strategy Adaptive Learning Results (3,3,2) Player 1 has winning strategy Overall Results • Game is UNFAIR • Winning strategy depends on oddness and evenness of roses in each bush • Adaptive learning program can determine which player has winning strategy for any starting game board (as # of bushes and roses increases, the program takes longer) Future Work • Find winning strategy for a game of 4 bushes, 5 bushes, 6 bushes, etc. • Continue to work with the adaptive learning program Any Questions? Thank you!