From jferry@[delete_this]uiuc.edu Tue Sep 4 17:37:32 CDT 2001 Article: 81133 of sci.math Path: news!husk.cso.niu.edu!vixen.cso.uiuc.edu!not-for-mail From: Jim Ferry X-Mailer: Mozilla 4.78 [en] (X11; U; SunOS 5.7 sun4u) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: sci.math,rec.puzzles Subject: Trivial Pursuit strategy Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 87 Message-ID: Date: Tue, 04 Sep 2001 16:41:31 -0500 NNTP-Posting-Host: 128.174.251.35 X-Complaints-To: abuse@uiuc.edu X-Trace: vixen.cso.uiuc.edu 999639581 128.174.251.35 (Tue, 04 Sep 2001 16:39:41 CDT) NNTP-Posting-Date: Tue, 04 Sep 2001 16:39:41 CDT Organization: University of Illinois at Urbana-Champaign Xref: news sci.math:81133 rec.puzzles:18911 I wrote a program to determine the optimal strategy for Trivial Pursuit, given the following assumptions: (a) one has a probability p of answering a question correctly, independent of category, and (b) one plays to minimize the expected number of turns one takes. I haven't yet simplified my data to produce a simple verbal description of which direction to move in a given situation, but I'll give a simple example to illustrate what I'm talking about. Note: except for during the beginning and ending of the game, we can pretend like the board consists of a ring of squares, ignoring the interior part. ---------- Example ---------- Suppose you have no pie pieces yet. By symmetry, there are four types of squares, which we label consecutively 0, 1, 2, and 3, where "0" is a pie square, "2" is a "Roll Again", etc. Clearly (from an intuitive, if not a mathematical standpoint) "0" is the best square to land on, and "2" is the second best. The astute player will have noticed that "3" is better to land on than "1" because of the high probability of landing on a "Roll Again" on the next turn. We now quantify how good it is to be on each type of square. Let ui be the expected number of moves until victory given that one is on square i but hasn't yet been asked a question. Let vi be the analogous quantity for the already-answered case. Finally, let w be the expected value upon gaining one's first pie piece. Then we have the following equations: u0 = p w + (1-p) (v0+1) u1 = v1 + (1-p), (because u1 = p v1 + (1-p) (v1+1) ) u2 = v2, ("Roll Again") u3 = v3 + (1-p), v0 = (u1 + u2 + u3) / 3, (a roll of 1 or 6 leads to "1", etc.) v1 = (u0 + u2 + u3) / 3, (assumes that one chooses "0" over "2", etc.) v2 = (u0 + u2 + u3) / 3, v3 = (u0 + 2 u2) / 3. Solving these equations leads to this equation for ui: (28/p + ci) (1-p)/12 + w, where c0 = -16, c1 = 5, c2 = -7, c3 = 2. For p = 1/2, this means that choosing square "1" over square "3" (when one has no pie pieces yet) is a blunder that costs one 1/8 of a move. ----------------------------- Things get more complicated in the general case. Here are the expected number of moves required for the whole game for p = 1, 3/4, 2/3, and 1/2: 1, 10.036232034655, 14.475866953518, 27.624738157405. (This assumes that a player wins by answering a question correctly on the center square.) Here are the exact values for the latter three cases. The size of their denominators suggest that a computer is indeed helpful in solving the equations involved. 3752437878205660602034618710811880678779584324184191241559237631702370885849 / 373889111496083841711613526881724378055813525133184496409271311284987494400 54865313819150900176678309076561681628611001336516135653637518126393220947 / 3790122829625503234283282250270370214681886301717659506224040540252405760 11936850525024996962990941123659305108454206215173964524054276767962402387 / 432107282139983338174256121050520171526563906845063334467895178297344000 Again, I don't have a verbal description of the optimal strategy yet (e.g., when is good to move away from your goal to land on a "Roll Again"?), but one thing (in addition to the "3" versus "1" distinction above) that the data clearly advises is to consider the total length you'd have to travel if you could march somewhere directly. For example, if you label the pie squares 0 through 5 consecutively, then if you have pieces 0 and 1, and have just earned piece 3, then it is better to head for 2 next, since 3-2-3-4-5 is shorter than 3-4-5-4-3-2. | Jim Ferry | Center for Simulation | +------------------------------------+ of Advanced Rockets | | http://www.uiuc.edu/ph/www/jferry/ +------------------------+ | jferry@[delete_this]uiuc.edu | University of Illinois |