The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » Math Topics » geometry.research

Topic: Another Sprouts Blunder
Replies: 1   Last Post: Sep 20, 1999 3:00 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Danny Purvis

Posts: 176
Registered: 12/6/04
Another Sprouts Blunder
Posted: Sep 13, 1999 10:37 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

I found another error in my previous sprouts postings. Let
"biosphere" denote a part of a sprouts position sealed off from the
remainder of the position. For many years I believed that: (The
Mystic Principle) if a given biosphere, played as a separate game,
produces n survivors both in normal and misere sprouts, then it must
produce n survivors with best play as a component of any game. I
reasoned that either player can force n survivors and that n must be
good for one or the other. This reasoning is apparently faulty,
however.

If a biosphere is played as a game both normally and in misere form,
there are 4 possible outcomes. I have an idiosyncratic naming
convention for this pattern:

Normal Play Misere

Null Player 2 wins Player 1 wins

Inverter Player 1 wins Player 2 wins

Trap Player 2 wins Player 2 wins

Switch Player 1 wins Player 1 wins


The next chart shows what a particular type of biosphere can become in
exactly one move. "1" means "can become"; "0" means "cannot become";
"*" is a wildcard, standing for "1" or "0".


N I T S

Null 0 0 0 0
0 1 0 *

Inverter 1 0 0 *

Trap 0 0 0 1

Switch 1 1 * *
0 1 1 *
1 0 1 *
0 0 1 *

Notice that 16 "varieties" of biopheres are distinguished, including
10 "varieties" of switches. The final 6 varieties of switches listed
- i.e. the final 3 lines of the chart - I call "pretraps".

Sprague-Grundy numbers are integers that can be used to determine
which biosphere needs to be altered. A biosphere which if played as a
normal game is lost for the first player has a Sprague-Grundy number
of 0. A biosphere which in exactly one move can become a biosphere
with Sprague-Grundy number m, such that m is any value from 0 to n but
not n+1, has Sprague-Grundy number n+1.

My faulty "Mystic Principle" amounted to an assertion that a null must
have a Sprague-Grundy number of 0 (which is true, by the way) and that
an inverter must have a Sprague-Grundy number of 1 (which is false).
So, let me apologize and correct any previous misstatements with the
following chart. I'll also promise not to post any more
sprouts-related things unless I run across more mistakes that I have
already posted. (Of course, the crash of my "Mystic Principle" might
impinge on some of the move by move analysis I posted previously.)


N I T S Sprague-Grundy

Null 0 0 0 0 0
0 1 0 * 0

Inverter 1 0 0 0 1
1 0 0 1 1 or greater

Trap 0 0 0 1 0

Switch 1 1 * 0 2
1 1 * 1 2 or greater
0 1 1 0 2
0 1 1 1 2 or greater
1 0 1 0 1
1 0 1 1 1 or greater
0 0 1 0 1
0 0 1 1 1 or greater





Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.