Heuristics help to move through a search space based on cost and perhaps enlightened greed (as in simulated annealing). Sometimes you don’t control the size of the search space, however, or there are winning configurations and losing configurations and nothing in between. In such cases, you might still do better than a brute force exhaustive search if there is structure in the winning configurations.
A field known as combinatorial design can help. The idea is that even if you don’t test the full search space, perhaps you can be systematic in some sense at least. For example, perhaps you can guarantee that every value of every parameter is tried at least once. Usually, that’s insufficient. Perhaps you can ensure that every combination of values of every pair of parameters is tried once. In this puzzle, we look for triplets.
Consider a special slot machine with five wheels. One has four different values. The others have three each.
wheel 1: apples, cherries, grapes, pears
wheel 2: cherries, grapes, pears
wheel 3: apples, grapes, pears
wheel 4: apples, cherries, pears
wheel 5: apples, cherries, grapes
In this machine, the player sets the wheel values, then pulls the lever. If it’s a winning combination, the payout is $500. Each pull of the lever costs $10. The winning combination depends on only three wheels. You don’t know which three, but you know that the first wheel is one of them. If you are lucky enough to find the correct values of the correct three wheels, the values in the remaining two wheels don’t matter. For example, suppose the winning combination is apples on wheel 1, grapes on wheel 3, and pears on wheel 4. If you set those values correctly, then the values on wheels 2 and 5 can be anything at all and you will receive the payout.
The house changes the winning combinations after either 15 attempts or a payout, whichever comes first. If each attempt costs $10 and the payout is $500, can you make this into a good game for the player?
In order to understand how to go about solving this problem, realize first that there are nine winning combinations since there are nine possible settings of the remaining wheels. The total number of combinations of all wheels is 4 × 3 × 3 × 3 × 3 = 324. So the odds of winning are 9/324 = 1/36. Because each pull of the lever costs $10 and the payout is $500, this is a good bet. That would be true even if the winning combination were changed after every attempt.
In fact, the odds are better than this, because each attempt reduces the search space. This increases the odds just as your chances of winning increase as the deck empties in black jack, if you keep track of the cards thrown.
Can you show how to guarantee to win in 36 lever pulls?
Notice that you want to combine each value of wheel 1 with every pair of values of every pairs of other wheels. For example, if the order of these fruits correspond to wheel numbers, then the three lever pulls
1,apples,pears,apples,pears,apples
2,apples,cherries,apples,apples,grapes
3,apples,grapes,apples,cherries,cherries
correspond to setting apples for wheel 1 and then testing all other wheels against apples for wheel 3. At the same time, we have tested pears vs. pears, cherries vs. apples, and grapes vs. cherries for wheels 2 and 4. So, for each setting of wheel 1, we can test many wheel-to-wheel pairs of the other wheels with just a few lever pulls. Keep track of value pairs that haven’t yet been tried and go through them systematically. That’s enough of a hint. You can program this.
Can you show how to guarantee to win in 36 lever pulls?
Here are the 36 lever pulls that will guarantee that every possible value of the first wheel is combined with every pair of values from each pair of other wheels.
num | wheel1 | wheel2 | wheel3 | wheel4 | wheel5 |
---|---|---|---|---|---|
1 | apples | pears | apples | pears | apples |
2 | apples | cherries | apples | apples | grapes |
3 | apples | grapes | apples | cherries | cherries |
4 | apples | cherries | grapes | cherries | apples |
5 | apples | cherries | grapes | cherries | apples |
6 | apples | cherries | pears | pears | cherries |
7 | apples | pears | grapes | apples | cherries |
8 | apples | grapes | pears | apples | apples |
9 | apples | grapes | grapes | pears | grapes |
10 | cherries | pears | apples | pears | apples |
11 | cherries | cherries | apples | apples | grapes |
12 | cherries | grapes | apples | cherries | cherries |
13 | cherries | cherries | grapes | cherries | apples |
14 | cherries | pears | pears | cherries | grapes |
15 | cherries | cherries | pears | pears | cherries |
16 | cherries | pears | grapes | apples | cherries |
17 | cherries | grapes | pears | apples | apples |
18 | cherries | grapes | grapes | pears | grapes |
19 | grapes | pears | apples | pears | apples |
20 | grapes | cherries | apples | apples | grapes |
21 | grapes | grapes | apples | cherries | cherries |
22 | grapes | cherries | grapes | cherries | apples |
23 | grapes | pears | pears | cherries | grapes |
24 | grapes | cherries | pears | pears | cherries |
25 | grapes | pears | grapes | apples | cherries |
26 | grapes | grapes | pears | apples | apples |
27 | grapes | grapes | grapes | pears | grapes |
28 | pears | pears | apples | pears | apples |
29 | pears | cherries | apples | apples | grapes |
30 | pears | grapes | apples | cherries | cherries |
31 | pears | cherries | grapes | cherries | apples |
32 | pears | pears | pears | cherries | grapes |
33 | pears | cherries | pears | pears | cherries |
34 | pears | pears | grapes | apples | cherries |
35 | pears | grapes | pears | apples | apples |
36 | pears | grapes | grapes | pears | grapes |