Tame game conjecture

[Josh Purinton]

Is the conjecutre below true? If so, it would provide an efficient way to test for tameness, analagous to the way we now compute the misere Grundy number of G by computing o-(G+*0), o-(G+*1), o-(G+*2), etc. stopping when the outcome class is P.

 

Definition. "G is R-indistinguishable from H" if and only if for all games K in ruleset R, o+(G+K) = o+(H+K) and o-(G+K) = o-(H+K).

 

Definition. "G is tame" if and only if G is nim-indistuingishable from some sum of nim heaps.

 

Definition. "max-size-k nim" is the game of nim in which the size of each heap is at most k.

 

Conjecture. Given a game G, let k = max(Grundy+(G), Grundy-(G)) + 1. Then "G is tame" if and only if G is max-size-k-nim-indistinguishable from some sum of nim-heaps, each of which is of size at most k. 

 

--
Josh Purinton <josh.p...@gmail.com>

[Josh Purinton]

On Fri, Mar 21, 2008 at 5:42 PM, Aaron Siegel <aaron.n...@gmail.com> wrote:

Is the conjecutre below true? If so, it would provide an efficient way to test for tameness, analagous to the way we now compute the misere Grundy number of G by computing o-(G+*0), o-(G+*1), o-(G+*2), etc. stopping when the outcome class is P.

There is a vastly more efficient way to compute the misere Grundy value of G: use the recursion g-(0) = 1;  g-(G) = mex{G'}, where G' ranges over all options of G.

 

Aunt Beast initially used the recursive algorithm you describe. But in order to compute the Grundy number of G, this algorithm has to generate and traverse the entire game tree beginning with G.

 

Clearly, o-(G) is cheaper to compute than Grundy-(G), because as soon as you discover one P option a game, you don't have to examine any of its other options. Using this fact, the iterative algorithm is usually able to compute the Grundy value by looking at a small fraction of the game tree.

 

Definition. "G is tame" if and only if G is nim-indistuingishable from some sum of nim heaps.

I'm fairly certain this is false.  That is, there exists a game G such that G is Nim-indistinguishable from a sum of Nim-heaps, but G itself is not tame. 

 

Can you give me an idea of how you might come up with such a G? I should have mentioned that I'm trying to make my definition of "tame" equivalen to the WW definition.


--
Josh Purinton <josh.p...@gmail.com>