Other Solved Games
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.
Filed under: game theory, probability, randomness | 2 Comments