Tuesday 22 October 2013

                 Addicted to Logic


There are two types of computer users: those who are addicted to a computer game and those who have a life. At the moment, I count myself in the second group, but I confess to several computer-game infatuations in my sordid past. Every addict surely knows the anguish of hearing an unexpected knock on the door, just when you are at a critical moment of the game. What should you do? Answer the door, or lie low and finish the game? Now, players of the computer game Minesweeper can open the door with a clear conscience. They can say they were just practicing their logical reasoning skills.
At the January meeting of the Mathematical Association of America in San Antonio, Patti Frazer Lock of St. Lawrence University explained how Minesweeper gives her students a better sense of what proofs are all about. "Students accept that when you play a game, you have to play by certain rules and take only what those rules give you," Lock says. The same is true in mathematics, but her students' earlier math courses leave them with conflicting ideas of what the rules are. So she starts out her sophomore courses with a look at Minesweeper, where the rules are clear.
Example of a starting position
The game, which comes as an accessory on any Windows 3.1- or Windows 95/98-based computer, is played on a gray, rectangular grid of squares. Concealed within the grid are a number of "land mines," and the object of the game is to "flag" each square that contains a mine without ever "stepping on" one. If you step on a mined square, of course, you lose. When you step on a safe square, the computer reveals how many mines—between 1 and 8—are adjacent to that cell. Or, if there are none, the computer automatically uncovers all the squares around it, because they are all safe as well. That's the way the game normally begin—with a little island of safe cells surrounded by a sea of unknown hazards, as in the picture below.
After her students have played a few games for practice, Lock gives them a position like this one and asks them to tell which squares are definitely safe and which are definitely mined. Typically, the discussion will begin with D6.
ALICE: It has to be mined, because there are so many 1s around it.
BOB: No, it doesn't. What if D7 were mined instead? That would explain the 1s on E6 and E7.
CLARA: Doh! Look at E5, dude! It has a 1, and D6 is the only square next to it that we don't know is safe. So D6 has to have a mine.
Clara is right, of course, but all three comments represent typical stages of mathematical discovery. Alice has made a correct conjecture based on plausible evidence, but without a convincing proof. Bob has tried to disprove Alice's conjecture by offering an alternative possibility, which mathematicians call a counterexample. Finally, Clara has settled the discussion with an argument based on the rules of the game and the known information.
The position after square D6 is flagged.Click to Enlarge Image
Now that we know D6 is mined, we can "flag" it. This conclusion leads to further consequences.
DAVID: D7 is safe, because it's next to E6 and we know E6 has only one mine next to it.
ERNEST: So C6 is safe, too!
FRANCES: And B4, B5, and B6!
BOB: Wait a minute, you're going too fast for me. Why are B4, B5, and B6 safe?
FRANCES: Because C5 has a 1, and there's a mine next to it at D6. So that means all the other squares next to C5 are safe.
Working their way around, the students conclude that B3 is mined; B2, C2, D2 are safe; E2 is mined; and F2, far from where the action began, is safe.
"Often the students will say, 'Wow, I would never have guessed you could say anything about that cell,'" Lock says. "This teaches them several things. The idea that mathematicians have hypotheses, which are just the rules of the game, and they try to push them as far as they can. The idea that you can use one result to prove a later result. And they really come to believe that it's good to write things down carefully."
Serious Minesweeper addicts soon discover and learn to use facts about whole classes of positions. Here is one, which I call the "Corner-Turning Theorem": If a rectangular island of safety ends with two 1s side by side (e.g., B7 and C7 in the following example) then you can "turn the corner" and determine the status of every square on the long side of the rectangle. Thus, all the squares A1 to A8 can be predicted. (For starters, A6 through A8 are safe because there is a mine at B8 or C8, which must be the only one adjacent to B7.)
An island of safety with two 1s on the right.
Mathematicians love finding patterns like this. Amazingly, the students love it, too. "I've had them not want to leave the classroom at the end of the hour," Lock says.
Lock borrowed the idea of Minesweeper as a pedagogical tool from Allan Struthers of Michigan Technological University in Houghton, who wrote about it in the June 1995 issue ofPrimus. Struthers explains, "Putting a flag on a square is a theorem—you know there's a bomb there." The same reasoning techniques that students develop for Minesweeper, such as counterexamples and proofs by contradiction, can be used when they prove other theorems later in the course.
The man who wrote the code for Minesweeper never intended it as a teaching tool or even as a novelty. A similar computer game had existed before, in which the goal was simply to find a clear path from one corner to the other. Robert Donner of Microsoft wrote a program for that game one Saturday afternoon, but his friends assumed the goal was to find all the mines, not just a clear path. So Donner rewrote the program accordingly, adding a few cute graphical touches. A few years later, Minesweeper was on every new operating system Microsoft sold.

Donner says that the most frequently asked question about Minesweeper is, "What's the best time?" He doesn't keep records—with one noteworthy exception. "The only official time I remember is when Bill Gates sent me a message stating he just completed beginner level in 4 seconds, and left the game sitting on a machine if I wanted to verify it." Even the richest businessman in the world, it seems, can be addicted to logic.

No comments:

Post a Comment