The Misere Gamesman's Toolkit

The previous subsection was a success: our normal play stuff is working. We're ready to do the same thing for misere octal games.

Built-in games, optionLists, & showDef

In general, a MisereGame is a list of options:

Nim heaps n[0], n[1], n[2], etc.  For example, the optionList of n[3] is {n[0],n[1],n[2]}

Adders (cf Allemang's M.Sc. thesis; also in Winning Ways, the game "Adders").

For example, a[4] = {n[2],n[3]} = n[2]+n[2]

Abbreviated notation for games whose options are a[4] with some nim heaps:

The point of showDef is to show a definition of a game as its list of options, not to echo back its simplified form.
    
This next definition is a hack, putting the $ after 'MisereGame' here to stop evaluation we don't want.
There must be a better way to stop evaluation (using "Unevaluated", or "HoldFirst", which don't seem to do it??)

Misere Simplification Rules

The misere simplification rules.  

Here's a simple example:

Dynamic symbols and strong simplification

There are examples where RMS, applied to the top level of a formal sum, doesn't always succeed in finding a fully reduced form.

A stronger form of RMS would attack the "innermost" MisereGame's first, seeing if they can be simplified.

Maybe we can do this:

    Strong Simplification Algorithm:
    Input game G.
    
        1) Apply misereRules to G
        2) Are there any MisereGame[] expressions anywhere in the result?
            2a) If not, Strong Simplification is complete.  Exit.
        3) If so, try simple RMS on an innermost, as yet unconsidered MisereGame[].
        4) Did simple RMS simplify that game?
        5) If so, we've made some progress.  Replace the MisereGame[] by the simpler form and
              return to step 1, continuing the strong simplification by a recursive call to strongSimplify
        6) If not, we've found a new irreducible game form that we don't have a formal symbol for:
            6a) Create a formal symbol for it.
            6b) Augment the misereRules to reduce it automatically.
            6c) Augment the optionList algorithm to know about it.
            6d) In this way we 'cache' the fact that it is irreducible, so that if we see it again, we don't repeat work.
            6e) We also will obtain succinct representations of games
            6f) And we'll get an idea of game complexity by how many new definitions are entered.
        7) In any case, our hands are tied with this particular MisereGame subexpression. Return to step 2)

FIXME:  OUTPUT OF THIS FUNCTION?  
      IS IT NAMED CORRECTLY?
      WE NEED TO DRIVE IT EXTERNALLY.
      
Notes added 19 Jan 2003:
      
Currently strongSimplify is a sort of 'analyzer' of a game expression g:

    First, it checks if the given input expression g an be fully simplified using the current 'known' misere game reduction rules---  
    these rules are available as the 'misereRules.'  It tries the misereRules on g, and if no MisereGame symbols remain in the result,
    then strongSimplify is 'done' and it exits, returning that value.  The input game g is fully simplifiable to a symbol. No problem!
    
    If, on the other hand, a MisereGame expression still exists inside g after the misereRules are tried (this 'innermost' expression
    could in fact be g itself, or a subgame of h...
        strongSimplify first locates an "innermost" MisereGame h.
        It's already known a priori that h doesn't simplify under the existing misereRules.  
        However, it's not known whether h might simplify according to a reversible option simplification.
    
    So strongSimplify tries a reversible option search on h.  Then there are two possible outcomes:
    
        1) No simplification of h is found.  Then h is a new irreducible game.  [proof?] strongSimplify introduces a symbol
            for h, augments the misereRules & optionList functionality to capture this knowledge.  
            If the misereRules were now to be immediately applied to h, it will be found that at least the
            subgame h now reduces to a symbol.  In this subcase, strongSimplify can just exit, provided there is some
            'driver' function to make the subsequent call.
            
        2) A simplification is found.  Then h needs to be replaced by the simpler form just discovered.
        
            [This replacement is a bit of a headache because the appropriate logic seems to hinge on
            whether h is a subgame or alternatively g == h.  We introduced a crappy flag for that. ]
        
    SO:  given that, what should the return value of strongSimplify be?  What is this algorithm, anyway?
    
    WELL, there are three cases here:
    
        1) g fully reduces to symbol under existing misereRules.  
            Return the symbol.
        2) g has an irreducible subgame that strong simplify discovered and entered a definition for.  
            Return the game g back ["MisereGame..."].  The caller should call strongSimplify again.            
        3) g has a subgame that does simplify under reversible moves.  We should perform the
            simplification and return the result of the simplification.
            
    So, in each case, we return a game symbol.  It's up to the caller of strongSimplify to determine what to do:
    
        a) if returned value is a symbol, done.
        b) if returned value is a MisereGame, call StrongSimplify again.
        
    Not too bad!      

Note added 19 Jan 2003

We're ready to experiment with writing a function, dependent on StrongSimplify, that
will automatically will reduce a game to a simple form PROVIDED
it involves no internal summations as options.

Here it is:

STRONGSIMPLIFY SUBCASE 1 [STEP 4 IN THE ALGORITHM DESCRIBED ABOVE]

OK, here is a game that doesn't fully simplify.  By this we mean that

    a) the application of misereRules to it doesn't yield a symbol
    b) An innermost sub-MisereGame h, when searched for reversible moves, also doesn't simplify.

As a side effect of discovering that h  doesn't simplify, the function strongSimplify does the following:

    0) It concludes that h is in fact an irreducible subgame of the original input.
    1) Creates a new symbol dynamically to stand for the game h in all subsequent computations.
    2) Creates a new misereRule to be used in simplification of every later expression that contains h
    3) Creates a new optionList equation using SetDelayed to allow a lookup of its options of h from when they are needed.
    
NOW, if STRONGSIMPLIFY IS CALLED AGAIN, ON THE SAME INPUT, THERE WILL BE A DIFFERENT RESULT.

Check that things worked:
1. Proof in the pudding...do we simplify the new game to its dynamic symbol on encountering it later?

2.  Whatever that temporary symbol is, just above, does optionList work on it?  
[Note that the symbol typically changes between different runs of Mathematica...]

3. How about a complicated game that mentions the original complicated thing in more than one place?
It should simplify automatically to the new symbol everywhere it appears.

Here's another example.  On the first call to strongSimplify, no simplification, but a new symbol is created.  On the second call, the new symbol is substituted for in the result, as we want it to be.

Why stop there?  Let's fully reduce to a single game symbol

STRONGSIMPLIFY SUBCASE 2:

Here's an example of the other subcase in strongSimplify, where a simplification is found.  In this case, we want to do the simplification and then start at the beginning of strongSimplify again.  There is no need to define a new symbol.  

Genus Calculation

We can write genus calculation rules using an approach similar to what we've used for misere simplification.

We represent the genus(G) of a misere game G as a symbol  {g, {g_0, g_1, ..., g_n}} where g is the normal play nim heap equivalent,
g_0 is the misere play nim heap equivalent, g_1 is the misere nim heap equivalent of G+n[2], etc, just as described in Winning Ways
and ONAG.  We have n > 0 (and n=1 is possible).  The misere g_i values for i>n follow a period two pattern.  In our internal representations
we truncate a symbol to the simplest possible form; ie it can be assumed that the last two values repeat indefinitely.

First a little helper function lVal that extrapolates a misere genus sequence list to large values if necessary, based on the period two property.

The argument n needs to be 1, 2, 3, etc; it's the desired index sought.

The function genusFunc computes the genus of a game G, the genera of whose options are given in the input list.  It contains
the "meat" of the genus calculation algorithm and requires all the inputs need to be genus symbols here.
The tricky part is arranging genus computation to take place so that:
    
    1) genusFunc is only called when its arguments are already known genus symbols and NOT embedded games whose genera aren't yet known
    2) causing the evaluation to continue until only one genus symbol is obtained (the desired result).

The helper function chopLogic truncates a list of integers, such as is found in the exponent part of genus symbol,
and assumed to represent an infinite period two sequence, to its shortest possible representation.

A test from pg 411 of Winning Ways:

Another test from the same page:

Section added 27 Feb 2003:

We need to have a genus function that does not depend on finding the game form, since that can be very complicated for general games.

What we want is a function directGenus[octalcode, position] that will compute the genus of a general position.

In directGenus, the second argument is just a (sorted) list of heap sizes (or perhaps better, a vector representation of such a list).
It might be convenient to accept both types of argument.    

Because it's often more convenient to specify positions as a list of pile sizes, we also provide that interface as a front end to directGenus, called genusPosition:

The functions directGenus and genusPosition do the same thing---they calculate a <1,2> genus of an explicit position.  The only way they differ is the way they expect
the format of the position whose genus is to be computed.  For example, suppose it's desired that we compute the <1,2> genus of the position G consisting of a
single heap of pile 7 and two piles of size 3 for the octal game .45.  This could be done by either of these calls:

directGenus[{0,4,5},{0,0,2,0,0,0,1}]   --- ie vector weight representation of G in the second arg
genusPosition[{0,4,5},{3,3,7}]  -- ie explicit heap representation

All genusPosition does is convert its input to the vector weight representation and then call directGenus.

HERE's a useful function that prints out a genusTable, just as our exact-value routine misereTable does for values

We're often interested whether the individual heap sizes, even when they have non-adder genera individually, nevertheless play like
adders in when they're summed together. The function adderTwoFilter computes the genus of each sum i+j where i and j are less
than or equal to the input heapsize, and prints out sums that do not have a tame game genus (WW table 2, pg 402).  

We're also interested in whether a particular genus value corresponds to a nim tame genus, particularly when we're scouring a space of games, looking for interesting ones (our quaternary searches come to mind)

One time, throw-away function to look at genera in many quaternaries, looking for interesting game codes:

End of section added 27 Feb 2003

The function genusFromOptions

For example:

10 Feb 2003:  Our genus function seems to be working correctly.  
On the other hand, our function to simplify using genusRules leaves us a 'gx' expression like this:

What we need to do is write another function that takes a nested gx-expression as input, and applies the genus calculation algorithm "from the inside out".

This function will work in a fashion similar to strongSimplify (but hopefully it will be simpler).  It's more natural to start with a game g than a gx-expression,
which is really an internal format.