Winning at the Slots


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.

Warm-Up

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?

Solution to Warm-Up

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.

  1. 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.

Solution to Winning at the Slots

  1. 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.

Open table as spreadsheet

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




Puzzles for Programmers and Pros
Puzzles for Programmers and Pros
ISBN: 0470121688
EAN: 2147483647
Year: 2007
Pages: 81
Authors: Dennis Shasha

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net