Experiment 17: Let’s Rock - Make: More Electronics (2014)

Make: More Electronics (2014)

Chapter 17. Experiment 17: Let's Rock!

Rock, Paper, Scissors is a truly ancient, international game, but just in case you have somehow never played it, I will recap the rules. Two opponents face each other, and on a count of three, each of them makes a hand gesture. The gesture can consist of:

§ A fist, to represent a rock

§ A flat palm, to represent paper

§ Two fingers to indicate scissors

Comparisons determine the winner. Rock blunts scissors, scissors cut paper, and paper wraps rock.

There’s an obvious similarity, here, to the Telepathy Test, because two people are facing each other, trying to sense each other’s intentions. However, there are some differences which will affect an electronic version of the game. First, each player has three choices instead of two. Second, if both players make the same choice, the game is a tie. Third, if they make different choices, one of them wins while the other loses.

Background: Probability

Let’s assume for a moment that telepathy doesn’t exist. Does this mean that Rock, Paper, Scissors is a game of pure chance?

No, because two human beings will be playing the game, and their choices will not be entirely random. In fact, many people have irrational ideas about randomicity.

For instance, it’s a common belief that if you’re tossing a coin, and heads comes up ten times in a row, tails will be more likely to come up next. This is known as the Monte Carlo fallacy, named after a casino in Monte Carlo where black came up twenty-six times in succession on one of its roulette wheels on August 18, 1913. A lot of people lost a lot of money midway through that streak by betting on red. After all, if black had come up ten times, or fifteen times, or even twenty times, red just had to come up next—or so they believed.

The belief is a fallacy because a roulette wheel has no memory. Nor does a coin. If you have thrown heads a dozen times in a row, the coin doesn’t know that. Consequently, the odds of heads coming up on the next throw are still exactly the same as before.

People, however, are different. They do remember what they’ve done, and their memories influence their decisions. If someone playing Rock, Paper, Scissors knows that he has made a rock on three consecutive turns of the game, he’s more likely to try something else on the next turn. He’ll probably feel that to behave unpredictably, he shouldn’t keep repeating himself. Therefore he becomes more likely to choose paper or scissors on the next turn.

You can take advantage of this by making scissors. This way, you’ll either tie or win. Either way, you won’t lose.

The trouble is, if you’re playing against an experienced opponent, he may realize that you won’t expect him to repeat himself. Consequently, he may repeat himself just to defy your expectations.

But what if you know him well enough to expect this? Once again, you can anticipate his behavior and modify your strategy accordingly—but if he picks up on that, he will modify his.

This recursive process in which people keep trying to second-guess each other is a common theme in the fascinating field of game theory, a branch of mathematics that became so influential in the 1960s, it affected US foreign policy and the nuclear arms race.

Background: Game Theory

Game theory was established as a discipline in 1944 when computer genius John von Neumann published Theory of Games and Economic Behavior with Oskar Morgenstern. The concepts were refined in the early 1950s and quickly became popular among theorists in RAND, the think tank in Washington, DC.

Game theory can describe any situation where two (or more) “players” are seeking a strategy to acquire an advantage but do not have complete information about each other, or cannot trust each other. In a game of poker, for instance, a player may bluff, while other players must try to figure out if the person is bluffing, and if so, how to respond. The response can then feed back to affect the player who chose to bluff, until finally the cards are revealed, and one player wins.

A military confrontation can likewise involve bluffing, challenges, and attempts to second-guess the opponent. This led RAND advisors such as Herman Kahn to argue that it might be “rational” under some circumstances for the Soviet Union to launch a first strike against the United States. Therefore both nations should build a capability to launch a second strike after suffering a first strike, since this would act as a deterrent to the first strike.

At http://www.gametheory.net you will find a simple description of some of the assumptions of game theory. One of them is that players will behave rationally to maximize their self interest. Yet would any statesman really decide that it was “rational” to kill hundreds of millions of people in another nation, and turn it into a radioactive wasteland, to gain an advantage?

Maybe not—but game theory said that you couldn’t be sure of that. Therefore the United States spent billions of dollars to develop the hydrogen bomb and deploy missiles in silos that were designed to survive a preemptive attack.

This may seem a long way from a game such as Rock, Paper, Scissors, but really the only differences are the scale, the number of variables, and the seriousness of the outcome.

The Logic

How should we represent the logic for a Rock, Paper, Scissors game? If you followed the steps to develop the Telepathy Tester, this shouldn’t be too hard. The basic logic for Player A is shown in Figure 17-1. Annabel and Boris are now playing this game under their previous identities as Player A and Player B, and each of them has a choice of three pushbuttons labelled Rock, Paper, and Scissors. For convenience I have abbreviated Annabel’s pushbuttons as AR, AP, and AS, while Boris has BR, BP, and BS.

This network of logic gates will display a “Win” message in response to any of the three winning combinations for Player A in the Rock, Paper, Scissors game.

Figure 17-1. This network of logic gates will display a “Win” message in response to any of the three winning combinations for Player A in the Rock, Paper, Scissors game.

If Annabel presses the Rock button while Boris presses the Scissors button, Annabel wins, because rock blunts scissors. If A presses Paper and B presses Rock, A wins again, because paper wraps rock. If A presses Scissors while B presses Paper, A still wins, as scissors cut paper. These three winning options are shown in the figure, as you’ll see if you trace out the connections.

Boris, of course, has his own three winning options, and then there are three possible ties if Annabel and Boris happen to press the same-labelled buttons. This is all summarized in Figure 17-2.

Three logic networks to give appropriate messages for each of the winning switch combinations and the tie combinations in the Rock, Paper, Scissors game.

Figure 17-2. Three logic networks to give appropriate messages for each of the winning switch combinations and the tie combinations in the Rock, Paper, Scissors game.

Pretty simple, so far. But as always the problems begin when we consider issues such as playability of the game and cheating.

Who’s On?

As in the Telepathy Test, each player’s set of pushbuttons must be hidden from the other player. But this means that at the end of each round, there is no visual confirmation of which button each player actually pressed. We only have three indicators saying that “Player A Wins,” “Player B Wins,” or “Tied Game.”

Really an LED should light up beside each button that is pressed—but only after both players have made their choices. How can this be done? Well, let’s spell out the logic.

First we have to wait until the game has ended, with Player A winning OR Player B winning OR the game ending in a tie. If I use a three-input OR gate to represent this, I can tap into the three game outcomes shown in Figure 17-2. The result will look like Figure 17-3. The three game outcomes feed into the three-input OR gate, and when it has a high output, this signals that the game has ended one way or another. The output is ANDed with each button, as a prerequisite to allow the button to light an LED. The LEDs are shown as yellow circles to save space in the diagram. Each LED is identified with the same two-letter abbreviation as the button that lights it.

A logic network that prevents an LED from lighting beside any switch until after a game has reached an end point.

Figure 17-3. A logic network that prevents an LED from lighting beside any switch until after a game has reached an end point.

Who’s Cheating?

This is beginning to look complicated (again). But the worst is still to come (again) because of the cheating problem. How can we signal if someone breaks the rules by pressing two buttons at once? In the Telepathy Tester, an XOR gate was helpful for this purpose because it has a high output if one input is high and the other is low, but it has a low output if both inputs go high. In the Telepathy Tester, a high input from an XOR meant that a player had made a move and was not cheating.

But XORs are usually restricted to two inputs, and in Rock, Paper, Scissors, we have three buttons for each player. This is a problem!

Spelling it out always helps. Annabel is cheating if AR AND AP are both pressed, OR if AP AND AS are both pressed, OR if AS AND AR are both pressed. (She is also cheating if she presses all three buttons, but we don’t need to test for that, because pressing three buttons must always entail pressing two buttons, and we are already testing for every combination of two buttons.)

Cheating should light an alarm indicator and should also suppress any normal outcome from the game. The same thing should occur if Boris cheats. In other words, if Annabel cheats OR Boris cheats, the outputs to the “Win” indicators and the “Tied Game” indicator should all be suppressed.

It’s certainly possible to implement this feature. We just need three more AND gates for each player to test each pair of buttons; and an OR gate for the outputs from the ANDs; and a NOR gate that gives a high output only if both players are not cheating; and then the NOR gate supplies another AND gate for each legal outcome of the game. But this doesn’t sound very easy to build.

Background: Gate Arrays

As early as the 1970s, manufacturers were marketing chips that contained programmable arrays of logic gates. All the designs had the same basic goal of allowing a “generic” array of gates to be programmed with connections for a specific application to create a customized logic circuit on a chip. Many methods were used to achieve this, in devices with acronyms such as PLA, PAL, GAL, and CPLD (all of which you can look up online, if you’re interested). Ultimately, field-programmable gate arrays (FPGAs) were developed, containing not only logic gates but more sophisticated capabilities that can be chosen by the end user.

Unfortunately, programming an FPGA requires a hardware description language, appropriate software (usually licensed by the chip manufacturer), and some appropriate hardware. This is not the kind of thing to set up in a home workshop, and so, for our purposes, we’re stuck with old-fashioned chips.

Or are we? I would really prefer a simpler option than a logic diagram with more gates than will fit on a page—and fortunately, that option exists.