Post navigation

← Previous

During the holidays, my niece introduced me to a “bottle match” game, variants of which have apparently made the rounds online for a while now, but it was new to me. She secretly arranges seven wooden bottle-shaped pegs, each of a different color, in a row. I then make a series of guesses of the ordering of the colors (arranging a second set of seven bottles visible to everyone), with each guess scored with a number indicating how many bottles are in the correct position. The objective is to get all seven bottles in the correct order in as few guesses as possible.

This is very similar to the board game Mastermind: one player arranges a secret “code,” and another player makes a series of guesses, with scores providing partial information about how close each guess is to the solution.

Watching family members play the bottle match game, I wondered how inefficient we were being in our guesses. Our exploration of the space of possible solutions seemed pretty timid, making “small” single-transposition changes to the arrangement of bottles at each step, even backtracking to previous guesses at times just to confirm remembered scores.

With bottles, a coarse lower bound of at least guesses are necessary in the worst case. How close to this bound can we get?

I wrote a program to try to answer this question, taking advantage of the similarity to Mastermind to analyze both games in the process. The resulting ~100 lines of Python code are on GitHub.

The greedy heuristic strategy used for both games is that described by Knuth (2): at each turn, make a guess that minimizes the maximum number of possible secret codes that might remain, over all possible scores that the guess might receive. Break any ties by first preferring codes that are *possible *(so that we have a chance of winning on the next move)… and in the case of the bottle match game, prefer a code that is “closest” to the previous guess, in the sense of requiring the least amount of additional shifting bottles around to turn the previous guess into the new guess.

This distance metric on permutations can be hard to compute, depending on what sort of shifting operations are allowed. The “block interchange” metric described by Christie (1) seems reasonably realistic for this problem, while being efficiently computable: one operation involves taking two “blocks” of consecutive bottles and swapping them, as shown in the example in the figure below.

Example of a single block interchange operation, swapping the block of 3 bottles in the gray box with the block of 2 bottles in the black box.

As a sanity check, evaluating the resulting strategy for the Mastermind game across all possible secret codes, replicates the results in Knuth’s paper: an expected number of guesses of 5801/1296, or about 4.476, never requiring more than a maximum of 5 guesses.

For the bottle match game, we can guess the secret code in 34169/5040, or about 6.78 guesses on average, never requiring more than a maximum of 8 guesses. It’s interesting how often it is advantageous– at least in this greedy heuristic minimax sense– to guess a code that is *not *consistent with the scores observed so far, as shown in the example output below.

>>> import mastermind
>>> game = mastermind.ColorMatch()
>>> game.play((6, 5, 4, 3, 2, 1, 0), show=True)
Guess (0, 1, 2, 3, 4, 5, 6) in 5040 remaining: score 1
Guess (2, 3, 4, 5, 6, 1, 0) not in 1855 remaining: score 3
Guess (2, 5, 0, 1, 6, 3, 4) not in 106 remaining: score 1
Guess (4, 3, 0, 1, 6, 5, 2) not in 31 remaining: score 0
Guess (2, 1, 4, 5, 0, 3, 6) not in 8 remaining: score 1
Guess (6, 5, 4, 3, 2, 1, 0) in 2 remaining: score 7

References:

1. Christie, D., Sorting permutations by block-interchanges, Information Processing Letters, 60(4) November 1996, p. 165-169.
2. Knuth, D., The Computer as Master Mind, Journal of Recreational Mathematics, 9(1) 1976-77.