Other Solved Games

25Jul07

I was reading a book called “Luck, Logic & White Lies” over the weekend, to prepare to teach a game theory course next term. It pointed out a couple of other “solved” games of a different nature.

Checkers is a game with no hidden information and no simultaneous moves. Any game of this sort always has deterministic optimal strategies for both players: in essence, from any given point in the game, there is always a well-defined best move (or several). A common game without these properties is Mastermind, where one player picks a code and the other one has to “guess” the code; the game has hidden information (namely, the only move of the code maker is initially hidden from the guesser). It is easy to see that this game no longer has an optimal deterministic strategy; what I mean is that if the code maker always picks “red blue yellow yellow” as her strategy (the code), then obviously the guesser (perhaps after playing a few games to notice this) can always win in 1 guess.

In a zero-sum 2-player game with hidden information or simultaneous moves, optimal strategies exist, but they may need to be randomized. Here is a short list of games for which optimal strategies for both players are known:

  • Rock-Paper-Scissors (folklore): each player, on each turn, should choose rock with probability 1/3, paper with probability 1/3, scissors with probability 1/3; neither player has an expected loss of money.
  • Mastermind, where the guesser has to pay $1 to the codemaker for each guess (Wiener, 1995): the code-maker should pick one of the 1290 non-monochromatic codes uniformly at random, and I won’t describe the complicated guessing strategy; on average, the code-maker wins $560/129 = $4.341 per game.
  • Baccarat (solved about 30 years ago): in casinos, the dealer has to follow a fixed set of deterministic rules when they play (e.g., one would be “draw from a 5”) which gives a house advantage of 1.06% (i.e., if the bet is $1, they expect to win 1.06 cents per game in the long run). But there is an even better randomized strategy for the dealer (e.g., “draw from a 5 with probability 9/11”) which gives them a 1.28% advantage.


2 Responses to “Other Solved Games”

  1. 1 kats

    Chess also falls into the deterministic category, right? The only difference is that the search space is a few orders of magnitude larger.

    Also, I see you’ve got my pictures of geese migration up🙂 I saw another set of geese trying to get across the path through north campus this morning.. I should have taken a photo of those too.

  2. Yes indeedy, chess is as deterministic as dropping buttered toast and whether the geese will use the sidewalk or grass for their personal toilet. Another one is Othello; apparently the people who solved checkers think that will be the next “common” game to be solved.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: