Socratic Tutorial 1
Wingnut: This place seems to have been invaded by chess players.
Brenda: Chess players and physicists. It's weird. All the physicists in this town play chess and when they're not playing chess, they seem to spend their time trying to wring new meaning out of the quantum mechanical formalism.
Wingnut: I'm afraid chess and quantum mechanics are both too difficult for my limited brain. Plus, I don't own a set of tiny wrenches. Let's acquire mochas and discuss some sprouts.
Brenda: I've already ordered the mochas, and here they come now. Thanks, Linda. Sit down and let Wingnut teach us some sprouts theory.
Linda: With pleasure. Wingnut is never cuter than when he explicates his favorite game.
Wingnut: Okay, okay. Calm down girls. Now I'm going to take this napkin here and draw three spots. This is going to be a normal game, not a misere game. Brenda, what would be a good first move?
Brenda: I'm sure I don't know, but I hope Linda is taking notes.
Linda: Of course I am. Utilizing Conway notation, I've got Wingnut serving 3+.
Wingnut: Let's reason this out. We're starting with three spots. Three is an odd number. Does the player to move need an even or an odd number of survivors?
Brenda: An even number.
Linda: How do I know that?
Wingnut: Good question. Do you know what a cannibal is?
Linda: No sir.
Wingnut: A cannibal is a spot with zero or two lines attached.
Linda: So we are presently examining a position with three cannibals.
Wingnut: Correct. Any starting position and any exhausted position consists of all cannibals.
Linda: An exhausted position because...
Wingnut: A spot with exactly one line attached would always allow another move. And we're abstracting from dead spots.
Linda: Right. Okay.
Wingnut: Well, as you can work out for yourself, any move to a position always changes the parity of the number of cannibals. One or three cannibals are added, or a single cannibal is subtracted. The parity goes from odd to even to odd to even and so forth, or vice versa.
Linda: So the player to move in the position we are now examining needs the final position to contain an even number of cannibals (survivors). That eventuality will prove that he has made the final move, since the current position has an odd number of cannibals. I understand. You have explained that very clearly. Later, when I have some time, I will work out to my own satisfaction how the cannibal parity changes with each move.
Wingnut: Interestingly, the original Swarthmore post which purports to demonstrate that fact contains a blunder.
Brenda: Perhaps that is not so surprising, Wingnut, since the Swarthmore posts cannot be edited once posted. If I wanted to post a sprouts article I think I would just send it to the WGOSA website. I'm sure the guy running that would allow me to make changes as needed.
Wingnut: Speaking of whom, that's him over there.
Wingnut: See the old fat guy losing chess game after chess game?
Brenda: That man has been ogling me for the past 45 minutes!
Linda: Are you talking about the gentleman continually loading up on desserts?
Brenda: He buys another dessert every time he loses a chess game!
Wingnut: Well, he's the WGOSA president, or so I understand.
Brenda: Who told you that?
Wingnut: I overheard him say so. He seems to tell anyone who will listen.
Linda: Isn't that interesting.
Wingnut: Well, back to our sprouts position. Brenda, it's your move. You want an even number of survivors as we have just verified. Now what even number would that be? Zero, two, four?
Brenda: I don't suppose you could ever have zero survivors. I mean, any move involves adding back a cannibal.
Brenda: And I don't believe we could have more survivors than original spots. I think I heard that somewhere.
Wingnut: Correct again.
Linda: How would you prove that?
Wingnut: The proof is simple but would be distracting.
Brenda: It has something to do with pharisees, does it not?
Wingnut: I believe so.
Linda: What is a pharisee?
Wingnut: A pharisee is a dead spot which is not one of the two closest neighbors of any survivor.
Brenda: Yes, I'm beginning to recall the proof. The maximum number of dead spots would be 4n-2, which would occur in a position with a single survivor.
Linda: I'm not sure I understand.
Brenda: Each move adds a spot but uses up a liberty. A beginning position has 3n liberties, meaning a maximum of 3n extra spots, dead or alive, minus any survivors.
Linda: Each survivor will be an unplayed move.
Brenda: Right. Now, of the 4n-2 dead spots, two will be "closest neighbors" of the survivor. Let's call them guardians. So the number of pharisees in a position with one survivor is 4n - 4.
Brenda: The key to the proof is that each additional survivor reduces the number of pharisees by four.
Brenda: Yes. A survivor converts to four pharisees and vice versa. One less survivor means adding one to the total of dead points. And three dead points have to "change hats". Instead of a survivor and two guardians you have three more pharisees.
Linda: I'll have to think about that.
Brenda: An important point is that each survivor has her own guardians. If two survivors tried to share the same guardian, they would communicate and the game would not be over.
Linda: Okay, I see it. And every additional survivor reduces the number of pharisees by four, so there are a maximum of n-1 additional survivors, or n total survivors, maximum.
Brenda: That's it.
Brenda: What were we talking about?
Wingnut: We started out talking about actually playing sprouts.
Brenda: Okay, Mr. Grumpy, so I'm looking at your position. There are three unattached spots. I'm looking for a move. There are three cannibals. I need an even number of survivors. Two being the only possible even number of survivors, that's what I need. Okay, here is what I am going to play. It may not be right but at least I will assure that there will be at least two survivors.
Linda: In Conway notation, you played 1(4)1.
Wingnut: Absolutely correct. That move wins and there's no point in going farther. There will be a survivor inside the circle and a survivor outside the circle.
Brenda: But how do we know that there won't be two survivors inside the circle or two survivors outside the circle?
Wingnut: Each of those areas...
Brenda: We can call them spheres, right?
Wingnut: Right. Each of those spheres are too simple to yield more than one survivor. You have to analyze a little to see that at first. Later it's just experience. I believe, by the way, that WGOSA is looking for terminology for such spheres.
Linda: I would call such a sphere "hermitic".
Brenda: I would call it a "unicorn".
Wingnut: Either name sounds reasonable to me.
Brenda: So the game's over? That was too simple. Give me another!
Wingnut: Okay, I'll take another napkin. Now we'll start with five spots. Again, normal sprouts. How many survivors do you need?
Linda: I'm still making notes. In Conway notation we have 5+.
Brenda: Okay, there are five cannibals. I need an even number of survivors. Either two or four.
Wingnut: Good. But of two or four, which should you aim for from the start?
Brenda: I don't think I understand. Either two or four will do.
Wingnut: Yes, but you have to make a move, so you need a goal. Now, two is not many and four is a lot. You need to decide whether you're going to play for a little or a lot.
Brenda: I have no basis for making such a decision. Do I just choose arbitrarily?
Wingnut: No, no, no. Experience and knowledge must be brought to bear.
Wingnut: You will admit your cup is empty?
Brenda: I'm through thanks.
Wingnut: No, I mean, you're ready to learn something?
Brenda: Of course.
Wingnut: Okay, here is a pattern which has emerged through experience. You need to just memorize it. A game with zero spots has zero survivors. A game with one spot has one survivor. A game with two spots has two survivors. Then there's slippage. A game with three spots also has two survivors. A game with four spots has three survivors. A game with five spots has four survivors. Then there's slippage again. A game with six spots also has four survivors. A game with seven spots has five survivors. And so on, at least through n = 12. There's slippage every three games. I'm talking about normal sprouts, by the way.
Brenda: So a game with eight spots has six survivors. And a game with nine spots also has six survivors.
Linda: And a game with ten spots has seven survivors?
Wingnut: Correct. It's as if each additional spot added slightly less than one survivor. After every three games the discrepancy shows. There's an interesting article on the WGOSA website called "Sprouts Fault Lines". Games just before the slippage seem hardest to play and games after the slippage seem easiest. In the present postion, you need four survivors and that's rather a lot because the six spot game also yields four survivors with more spots to work with.
Brenda: So I need to maximize the number of survivors.
Wingnut: Right. You need a fecund, as opposed to a pharisaic, move.
Brenda: Here we go.
Linda: That's 1(6)1.
Wingnut: Good try, but no cigar. After 1(7@2)6 the sphere S(2) is a unicorn and the sphere S(3) yields two survivors.
Brenda: How do we know that the sphere S(3) yields two survivors?
Wingnut: We just discussed that. A position consisting of three unattached spots yields two survivors. I'll just take down another napkin, redraw the position, five spots, try again.
Brenda: The only other try I see is 1(6)1[2,3].
Wingnut: Ku-ching. Correctimundo.
Brenda: I don't see it.
Wingnut: Well, it comes down to analysis. But when you're trying to maximize survivors, think UT.
Linda: University of Tennessee?
Wingnut: Heavens no! Ubiquitous traps. Two unattached cannibals or two unattached cannibals plus a single attached cannibal which also communicates with at least one outside spot makes a UT.
Brenda: So the sphere S(2) and the sphere S(4) are both UTs.
Wingnut: Neither is now, because they each have two attached cannibals rather than a single attached cannibal, but either could become a UT very easily. And experience shows that the maximizer tends to like UTs. Well, I'm getting tired. Let's ride out to the lake. We'll continue this lesson another day.
Brenda: Cool. If you have the Cigarette boat I have the string bikini.
Back to World Game of Sprouts
Association Home Page