Rules

Goofspiel, also called Game of Pure Strategy (GOPS) is a two person game. Take a standard 52 card deck and discard all of the cards of one suit. The cards of one suit are given to one player, the cards of another suit are given to the other player, and the cards in the remaining suit are shuffled and placed face down in the middle. The cards are valued from low to high as ace=1, 2, 3, ..., 10, jack=11, queen=12, and king=13. A round consists of turning up the next card from the middle pile and then the two players 'bet' on the upturned card, each player choosing one card and then simultaneously displaying it to the other player. The player showing the highest card wins the value of the upturned card. If both players display the same card, the point value is split between the two players. These three cards are then discarded. The game ends after 13 rounds and the winner is the person who obtained the most points (you need 46 or better to win).

Though the mechanics of the game are simple, the strategy is not. Suppose for example that the king is the upturned card in the first round. Further suppose that you choose to bet one (i.e. the ace). When you turn your card up, you found out that your opponent bet his king winning 13 points. You are happy with this result because you now have 12 more betting points which should more than make up for the lost 13 points. In fact, it is possible that you could win every remaining point by always betting one more than your opponent (of course you don't know what your opponent is going to bet). But you are taking a chance by betting only one. If your opponent had bet say a two or three, then your opponent would have won 13 points at almost no cost. When playing the game you are trying to outguess your opponent while your opponent is trying to outguess you. So you find yourself reasoning something like " my opponent is probably going to play X so I should play Y, but he may see through this and instead play Z to defeat Y so maybe I should play W instead. But maybe this is overanalyzing so ..."

To make use of game theory, use an equivalent scoring system where the player with the higher card wins the value of the upturned card from the opponent, or wins nothing in the event of a tie. The game is now a two-person zero-sum game. It's not hard to see that you should not choose a deterministic strategy. Every deterministic strategy A can be defeated as follows. (1) Use strategy A to find the card that my opponent is going to play. If my opponent is going to play a King, play the ace. Otherwise play the card that is one higher than my opponent's choice. This counterstrategy will win every round except one resulting in a trouncing. Instead your strategy should have some random variations where you play particular cards with some probability.

How difficult is it to analyze this game? Suppose the cards are valued from 1 through N. The number of distinct ways that middle suit could be ordered and the number of distinct betting sequences for each player is N factorial. Hence, the number of possible ways of playing out a game is f(N) = (N!)^3. These numbers quickly get too large to handle as seen by the following values.

f(5) =          1,728,000
f(6) =        373,248,000
f(7) =    128,024,064,000
f(8) = 65,548,320,768,000

To my knowledge, the game has never been previously analyzed beyond N=5. (see http://home.netcom.com/~goldkerr/gops.htm). But there is a way to signficantly reduce the number of games you need to analyze. Sheldon Ross ("Goofspiel: The Game of Pure Strategy," Journal of Applied Probability, Volume 8 no. 2 (1971), pp.621-25) describes a recursive rule where the value of a game depends on the values of smaller games. You can use this rule to come up with a dynamic programming solution that greatly reduces the amount of analysis required. Using this solution in a computer program, I've pushed the analysis up through N = 13.

The results don't get interesting until N is five, so I'll show the optimal strategies for the initial play for five through thirteen cards. In the following tables, the column labels are the initial top card and the row labels are the possible cards you could play. The entry in row i column j is the probability with which you should play card i when card j is the initial upturned card. When necessary, I've rounded the results to four places after the decimal point so the values for a particular column may not add up to exactly one.

N = 5
 12345
10.04700.18550.11820.12260.1123
20.832700.11880.073470.0241
30.12030.737500.19150
400.07700.76300.20430
50000.40810.8636

One potential pattern is that the most common card to play is always one more than the upturned card except when the 5 is up (there is nothing bigger than 5). But this pattern fails for each of N = 6 through 13.

N = 6
 123456
10.165000.06550.09800.02730
20.57740.32530.13150.04580.08650.1383
30.25760.18140.17000.173400.0062
400.49330.290700.34610
5000.34240.60810.02020
60000.07460.52000.8554

One curiousity here is the when 6 is the top card, you should *never* play a one, which is counterintuitive. Playing a one instead of a two would keep more betting points.

N = 7
 1234567
10.243100.12390.010000.05130.0632
20.40170.430100.10780.10170.02640.0010
30.35520.00660.3082000.10390.1084
400.563200.36140.267800.0395
5000.56880.02780.03100.31520
60000.49290.386300
700000.21320.50320.7880

The pattern seen in the N=5 case of playing one more than the upcard is maximally violated when the 3 is the upcard here. We should never play one more than the upcard!

N = 8
 12345678
10.30940.00550.127300.07640.032500
20.24990.221600.1160.000800.06760.0482
30.44070.16430.250900.13550.145600
400.34370.07880.294300.00850.16090.1479
500.26480.35550.03240.29870.19910.01760
6000.18740.391500.07920.21470
70000.16570.48850.298200
8000000.23690.53910.8039

It seems strange that we should play a 5 when a 2 is up more than 25% of the time. That seems like a rather large amount to bet for such a little card. Also, the counterintuitive strategy of never playing a 1, when the upcard is very big (as in 7 or 8) reappears here. It's also curious that the probability with which you match the largest possible upcard has increased over the n=7 case. I would have expected it to continue to decrease.

N = 9
 123456789
10.37290.122300.05450.064100.00810.02190.0231
20.11300.07720.1428000.08280.037800
30.51400.259100.18680.12600.02120.05150.09630.0807
400.18930.364800.04010.11520.06590.00600
500.352100.30790.18080.06690.09000.12880.1271
6000.49240.05730.10410.16370.10830.04290.2147
70000.39360.266700.15160.17720
800000.21830.54170.196500
9000000.00830.29030.52700.7475

The probabilities with which you should play a 5 or 6 when the initial card is a two or three again seems counterintuitively high. When 7 is the initial card, every possible bet should be played with a non-zero probability; this is the only time this happens in any table beyond N=5. Also, when 7 is the upcard, the higher the value, the higher the probability with which it should be played.

N = 10
 12345678910
10.41960.097500.063000.02290.0331000
20.010700.16260.01110.0965000.06440.06220.0446
30.56970.383200.133400.11610.08510.006300
4000.301300.1692000.08700.08320.0854
500.51930.04760.31030.03060.17230.15930.03430.02400
6000.36540.00930.21710.03340.01450.11670.10910.1286
7000.12310.377600.22400.20200.07340.05840.0197
80000.09530.48670.109300.16870.15160
9000000.32190.44580.155500
100000000.06030.29380.51140.7218

When the initial card is a 2, you should play a 5 over half the time. When the initial card is a 3, you should play a 6 or 7 nearly half the time. Again, these values seem counterintuitively high.

N = 11
 1234567891011
1.3583.1114.07040.0285.024900.00830.0207
200.0226.1332.02060.0549.05160.0331.0003
3.5592.3224.1590.0017.0845.100300.0742.0184.0463
4.0824.0516.0842.1764.0562.0156.1174.0982.0022.05020
50.3997.2266.0544.1244.1320.0089.0112.0946.0368.0942
60.1148.1508.2289.10090.1478.12470.07150
700.2864.1162.1748.278700.1733.0601.1216
8000.2892.16220.2802.2452.0089.1019.0234
90000.2480.3518.02320.2198.10080
1000000.0968.3676.3606.086000
110000000.1086.3327.5270.6935

 

N = 12
 123456789101112
100.03830.038800.0068.02090.00750
2.3834.17010.11020.0809.04670.0012.03570.0380
3.1520.0953.21160.1023.00000.0777.05120.0539.0015
4.4645.25130.18040.1078.1133.00260.07550.0515
50.1761.30080.19380.0027.0975.10800.07640
60.30710.2914.0130.1978.141200.1040.0142.0970
700.44550.23290.0317.1766.13450.09290
800.0038.38110.2510.176500.1570.0362.1179
9000.0370.4135.0486.0787.2235.21780.1208.0239
100000.0057.3141.23910.0285.2354.07470
11000000.1702.4153.2941.053900
1200000000.1437.3386.5234.6702

 

N = 13
 12345678910111213
100.0519.0309000000.01450.0100
2.4144.22660.0204.0558.07270.0338.0473.03610.03040
3.0897.0216.1784.0952.0357.0025.0694.0215.00150.04100.0370
4.4959.2991.0340.0610.0873.09850.0536.0648.06730.05610
50.0976.2301.1343.06670.1237.039500.08030.0655
60.3551.0929.1073.1242.18460.0767.1198.09850.08190
700.2740.1754.1014.0018.1675.0602.00120.1016.0080.0875
800.1386.1544.1654.2184.0209.1028.1422.1384.0156.09870
9000.2210.1481.0451.2021.0917.0295.0151.1229.0280.1262
100000.2155.26640.1436.1766.16960.1243.1288
1100000.1100.3967.15060.0635.2530.06460
120000000.2262.4171.2410.022800
13000000000.1704.3482.5081.6610

There are only a few general patterns in these tables. When the initial card is N and N is even, it seems that you should never bet a 1. Also, when the initial card is N, it seems that you should never bet N-1 nor N-2. Other than that each table bears very little resemblance to the others and that is perhaps the most surprising observation of all.

The results up through N=9 were obtained on my laptop. Dr. Laurent Bartholdi of the University of Gottingen in Germany ran my program on a research cluster to obtain the results for N=10, N=11, N=12, and N=13.

© 2011. Glenn C. Rhoads. All rights reserved.