Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 Danny Purvis Posts: 176 Registered: 12/6/04
Another Sprouts Blunder
Posted: Sep 13, 1999 10:37 AM
 Plain Text 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

Date Subject Author
9/13/99 Danny Purvis
9/20/99 Danny Purvis

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