Types of equivalence

[Yper Cube]

   During March 2008, several equivalences were posted at the wgosa site. Some of them were old, taken from this group (and rewritten in GLOP-like format). Some were new. It was tried to categorise them in three types, as one (the .1. = .22. ) appeared to belong to a new type, never seen before, and another one ( the -aa- = -2- ) was widely used but not seen as an equivalence.
   Thinking more clearly, it seems that this is a better place for such posts, so we'll try a regrouping and a more formal definition of these 3 "types" of equivalences and we'll add - for sake of completeness - a fourth type of equivalence.
 
   We define four types of equivalences, namely "branch" (type 1), "boundary" (type 2), "partial position" (type 3) and "position" (type 4).

   We'll use the terms -K-, -L- (or just K, L) for branches (a part of a boundary), or a sequence of numbers and letters that signifies this part.
   We define -K-L- to be the branch that results after "gluing" the end of K to the start of the L branch.
   We define .K-L. to be the boundary that results after "gluing" the end of K to the start of L and the end of L to the start of K (thus making a boundary).

   We'll use the terms .M., .N. for boundaries, or a sequences of numbers and letters that signifies this boundary.
  (Note that .M. appears if we take the branch -M- and we "glue" its end to its start.)

   We'll use P, Q, R or P(A,B,...X), Q(A,B,...X), R(A,B,...X) to be partial positions with A,B,...X as parameters. (Partial positions will usually start and end with } , so with "partial position, we
   For two partial positions P, R (with the same number of parameters  A,B,...X), we define P#R to be the position (not partial) that results after "gluing" these two partial positions together.

  We'll use G, H and J for any positions (not partial). Note that J is usually (and in almost all known examples) the zero game *0 in which case it can be safely not written.
(and in a few examples J is the game *1).  

  Def.4 (type 4) : for two positions G, H, and a (position of an impartial game) J
           we define G == H + J if,
 G is equivalent to the game H + J (in Conway's notion), meaning that they have the same reduced tree and thus are completely equivalent in both normal and misere play.

  Def.3' (type 3) : for two partial positions Q, R (with the same number of parameters  A,B,...X),  and a position J
           we define Q == R + J if,
  for any partial position P (with the same number of parameters as Q, R),
   we have     P#Q  ==  P#R  + J

or (equivalently)

  Def.3 (type 3) : for two partial positions Q, R (with the same number of parameters  A,B,...X),  and a position J
           we define Q == R + J if,
  for any position G where  where Q appears (inside G) and position H that results if we replace (inside G)  Q with R ,
   we have   G  ==  H + J

  Def.2 (type 2) : for two boundaries .M., .N. , and a position J
           we define .M. == .N. + J  if,
  for any position G where .M. appears (inside G), and position H that results if we replace (inside G) .M. with .N. ,
   we have    G == H  + J

  Def.1 (type 1) : for two branches -K- , -L- , and a position J
           we define  -K- == -L- + J   if,
  for any position G where -K- appears (inside G), and position H that results if we replace (inside G) -K- with -L- ,
   we have    G == H  + J

The last two definitions are equivalent with these two:

 Def.2' : for two boundaries .M., .N. , and a position J  
           we define .M. == .N. + J  if,
  for any partial position Q where .M. appears (inside Q), and position R that results if we replace (inside Q .) M. with .N. ,
    we have    Q == R  + J

  Def.1' : for two brances -K- , -L- ,  and a position J
           we define  -K- == -L-  + J if,
  for any boundary .M. where -K- appears (inside .M.), and boundary .N. that results if we replace (inside .M.) -K- with -L- ,
    we have    .M. == .N.  + J

  Note that J is usually (and in almost all known examples) the zero game *0 in which case we can be safely write  G == H instead of  G == H + *0.
(There are a few examples where J is the game *1).  

  Also note that the branch and boundary definitions can easily be thought to include branch with parameters and boundary with parameters equivalences, but not any such equivalence has been found yet.

   The definitions that look more alike are the 4, 3, 2, 1 (so we'll keep those instead of the 3' , 2' , 1' ). In addition, it is not impossible that there may be examples of equivalences that are a mixture of two types (of 3, 2 and 1). These definitions can easily be further expanded to include such mixed types. Therefore, types 3, 2 and 1 can be thought to be as just cases of a general type (and type 4 as type 3 with zero parameters). If someone can make a more general definition that will include all these types, please do!

  A complete list of known equivalences of types 4 and 3 would unnecessary grow even more hugely this post, so we'll write only two or three examples of them. For types 2 and 1, the number of known equivalences is small, so here's a complete known list.

Type 4 (position) examples
  0.}]  ==  12.}]  ==  *0
  1.}]  ==  0.0.0.}]  ==  *1
  0.0.}]  ==  2+

Type 3 (partial position) examples
  }2A.}  ==  }0.A.}
  }22A.}  ==  }2A.}  +  *1

Type 2 (boundary) known list
  .1.  ==  .22.
  .abcabc.  ==  .abacbc.

Type 1 (branch) known list
  -aa-  ==  -2-
  -abab-  ==  -a2a-
  -abcacb-  ==  -abcbac-    (a recent find)

and here's an example of mixed 1 and 3 type:
  (  -A-  ,  }A.}  )   ==   (  -2-  ,  }}  )

which while has been in wide use for years, has never been recorded this way in our knowledge!
It would be really great if there were more findings of such mixed type equivalences.

    Ypercube

[Yper Cube]

One more generalization

If we change Def.4  from:

  Def.4 (type 4) : for two positions G, H, and a (position of an impartial game) J

           we define G == H + J if,
 G is equivalent to the game H + J (in Conway's notion), meaning that they have the same reduced tree and thus are completely equivalent in both normal and misere play.

to:

  Def.4n (type 4n) : for two positions G, H, and a (position of an impartial game) J
           we define  G  =n=  H + J  if,
 G has the same nim value with the game H + J when both are played in normal play,
or (equiv.)    n(G)  =  n(H+J)          (n(G) is the nim value of G, etc.)
or (equiv.)    n(G)  =  n(H)  +  n(J)    (this is nim-addition)

we can then continue to define types 3n, 2n and 1n (without any change in those definitions, except using =n= instead of == )!

It is possible that several equivalences exist that are true only in normal play (or not yet easy to prove for misere play), for example }2.2.2.2A.} =n= }2.2.2.2.2.2A.} may be true (still not easy but surely easier that the general one).

We can further add more variations of Def.4 (and following of 3, 2, 1):

  Def.4m (type 4m) : for two positions G, H, and a (position of an impartial game) J
           we define  G  =m=  H + J  if,
 G has the same misere Grundy value with the game H + J (when both are played in misere play).
or (equiv.)    n-(G)  =  n-(H+J)          (n-(G) is the misere nim value of G, etc.)


  Def.4nm (type 4nm) : for two positions G, H, and a (position of an impartial game) J
           we define  G  =nm=  H + J  if,
    G  =n=  H + J    and    G  =m=  H + J


  Def.4g (type 4g) : for two positions G, H, and a (position of an impartial game) J
           we define  G  =g=  H + J  if,
    G  and   H + J   have the same genus sequence.


  Def.4N (type 4N) : for two positions G, H, and a (position of an impartial game) J
           we define  G  =N=  H + J  if,
 (G is a win for the first player in normal play) iff (H + J is a win for the first player in normal play).


  Def.4M (type 4M) : for two positions G, H, and a (position of an impartial game) J
           we define  G  =M=  H + J  if,
   (G  =N=  H + J)    and    (G  =M=  H + J)


  Def.4NM (type 4NM) : for two positions G, H, and a (position of an impartial game) J
           we define  G  =NM=  H + J  if,
 (G is a win for the first player in both normal and misere play) iff (H + J is a win for the first player in both normal and misere play).


We can then easily prove that

(G == H)   =>  (G =g= H)  =>  (G =nm= H)  =>  (G =NM= H)
and
(G =nm= H) => (G =n= H) => (G =N= H)
and
(G =nm= H) => (G =m= H) => (G =M= H)
and
(G =NM= H) => (G =N= H)
and
(G =NM= H) => (G =M= H)

where G and H can be positions or partial positions or boundaries or branches.

It's not that i'm optimistic that we'll find soon any such equivalence, (except for the =n= case where i would be indeed optimistic) but it may be useful to have a way of stating them in a common format when (and if) we find some.

Ypercube 

[Yper Cube]

Correction for definitions 4M and 4NM:

  Def.4M (type 4M) : for two positions G, H, and a (position of an impartial game) J

           we define  G  =M=  H + J  if,

(G is a win for the first player in misere play) iff (H + J is a win for the first player in misere play).