Conference rusure::math

>	What is the outcome if both players play optimally?

What are the possible outcomes? What is the object of the game? Did I miss 
something?

        I would guess it is like checkers ... if it is your turn
        to play and you don't have a legal move, you lose.
        
        Dan

    Ah, yes, the object of the game is to leave your opponent without a
    legal move.
    
    
    				-- edp

Summary:	Out of 46 possible positions (43 accessible from the starting
position), I believe 8 are wins, 5 are losses, and 33 (including the starting 
position) are draws.   I worked it through by hand, using symmetries to
minimize the chance of making an untrappable error in my calculations.

Details:
	Let's see how far we can get just by thinking a little.   There are
clearly three kinds of position:

	E]	Where the centre space is empty
	[o]	Where the centre space contains counter o (o not to move)
	[X]	Where the centre space contains counter X (X to move)

	From each position of form E], X (the player to move) can go to
1,2,3 or 4 possible positions of form [o].   

	From each position of form [o], X can go to 0,1 or 2 possible 
positions of form [X].

	From each position of form [X], X can go to a position of form E], and
to 0,1 or 2 possible positions of form [o].

	There's also a duality between the positions of form [o] [X].   If
we label the positions o01, o02,..., X01, X02, we can pick the labelling such
that om -> Xn iff on -> Xm.   Similarly, if Xm -> on, then Xn -> om.   

	Most of the E positions are there own duals, but E3 and E4 are duals
of one another.   If Em' denotes the dual to Em, then we can say that:
if Em -> on, then Xn -> Em'.   The converse of the second does not 
apply, since Em -> on is prohibited if it involves the movement of a buried 
counter.   However, for checking purposes we can verify that if Xn -> Em, then 
either Em' -> on, or Em' cannot move to on due to buried counter.

	What are the positions, modulo all rotations and reflections?

-------------------------------------------------------------------------------

E01	E]XXXXoooo	o01	[o]ooXXXXo	X01	[X]XXooooX
E02	E]XXXoXooo	o02	[o]oXoXXXo	X02	[X]XoXoooX
E03	E]XXXooXoo	o03	[o]oXXoXXo	X03	[X]XooXooX
E04	E]XXoXXooo
E05	E]XXooXXoo	o04	[o]oooXXXX	X04	[X]XXXoooo
E06	E]XXoXoXoo	o05	[o]ooXoXXX	X05	[X]XXoXooo
E07	E]XXoXooXo	o06	[o]ooXXoXX	X06	[X]XXooXoo
E08	E]XoXoXoXo	o07	[o]ooXXXoX	X07	[X]XXoooXo
			o08	[o]oXooXXX	X08	[X]XoXXooo
			o09	[o]oXoXoXX	X09	[X]XoXoXoo
			o10	[o]oXoXXoX	X10	[X]XoXooXo
			o11	[o]oXXooXX	X11	[X]XooXXoo
			o12	[o]oXXoXoX	X12	[X]XooXoXo
			o13	[o]oXXXooX	X13	[X]XoooXXo
	
			o14	[o]XoooXXX	X14	[X]oXXXooo
			o15	[o]XooXoXX	X15	[X]oXXoXoo
			o16	[o]XooXXoX	X16	[X]oXXooXo
			o17	[o]XoXooXX	X17	[X]oXoXXoo
			o18	[o]XoXoXoX	X18	[X]oXoXoXo
			o19	[o]XXoooXX	X19	[X]ooXXXoo

-------------------------------------------------------------------------------

	o01-o03 are the lost positions, since there are no ways out of them.
Dually, X01-X03 are Eden positions, and cannot be reached from any other
position.   o01-o03 can only be reached from X positions since moves from
E positions would be with buried counters.   From X01-X03, there are three
legal moves, 2 to o positions, and 1 to a P position.

	o04-o13 have 1 legal move, and derive from 1 legal E position and
one legal X position each.   X04-X13 admit one move to an E position,
and one to an o position, and each have a unique predecessor.

	o14-o19 have 2 legal moves to X positions, and derive from a unique
E position each.   X14-X19 admit one move, to an E position, and can derive
from 2 o positions.

	Examining the E positions, we can say that for all except E3 & E4,
the number of ways of moving, is the same as the number of ways of moving out.

	In practice, the number of links may be reduced by symmetries, but
the duality will be preserved.

	This is about as much as we can say without actually getting down to
the hard work of solving the game.

-------------------------------------------------------------------------------
Position		Comes from		Goes to		   
-------------------------------------------------------------------------------

E01			X01, X04		o04		   
E02			X02, X05, X07, X14	o05, o07, o14	   
E03			X08, X13		o06, o19	   
E04			X03, X06, X19		o08, o13
E05			X11			o11
E06			X09, X12, X16, X17	o09, o12, o16, o17
E07			X10, X15		o10, o15
E08			X18			o18

o01			X01, X04		-
o02			X05, X07		-
003			X06			-

X01			-			E01, o01, o04
X02			-			E02, o05, o07
X03			-			E04, o06

o04			E01, X01		X14
o05			E02, X02		X15
o06			E03, X03		X16
o07			E02, X02		X13
o08			E04, X13		X17
o09			E06, X12		X18
o10			E07, X10		X12
o11			E05, X11		X16
o12			E06, X09		X10
o13			E04, X08		X07

X04			o14			E01, o01
X05			o15			E02, o02
X06			o16			E04, o03
X07			o13			E02, o02
X08			o17			E03, o13
X09			o18			E06, o12
X10			o12			E07, o10
X11			o16			E05, o11
X12			o10			E06, o09
X13			o07			E03, o08

o14			E02			X04, X19
o15			E07			X05, X17
o16			E06			X06, X11
o17			E06			X08, X15
o18			E08			X09
o19			E03			X14

X14			o04, o19		E02
X15			o05, o17		E07
X16			o06, o11		E06
X17			o08, o15		E06
X18			o09			E08
X19			o14			E04

-------------------------------------------------------------------------------

	Building backwards from the lost positions, I don't think that many
of the positions are decidable.   Below, Ln denotes that the position loses
in n moves, Wn denotes a win in n moves.   /pos denotes that move loses.
>pos denotes that move wins.

	Only thirteen positions are decidable, the other thirty-three,
including E01, which is the starting position, are draws.   We know this
becuase from none of the 33 is any player ever forced to play to one of the
8 known winning positions.   However, I haven't computed the drawing cycles
that the players could chose.

E01			X01, X04		o04		   
E02			X02, X05, X07, X14	o05, o07, /o14	   
E03			X08, X13		o06, o19	   
E04	W2		X03, X06, X19		o08, >o13
E05			X11			o11
E06			X09, X12, X16, X17	o09, o12, o16, o17
E07			X10, X15		o10, o15
E08			X18			o18

o01	L0		X01, X04		-
o02	L0		X05, X07		-
003	L0		X06			-

X01	W1		-			E01, >o01, o04
X02			-			E02, o05, o07
X03			-			/E04, o06

o04			E01, X01		X14
o05			E02, X02		X15
o06			E03, X03		X16
o07			E02, X02		X13
o08			E04, X13		X17
o09			E06, X12		X18
o10			E07, X10		X12
o11			E05, X11		X16
o12			E06, X09		X10
o13	L1		E04, X08		/X07

X04	W1		o14			E01, >o01
X05	W1		o15			E02, >o02
X06	W1		o16			/E04, >o03
X07	W1		o13			E02, >o02
X08	W2		o17			E03, >o13
X09			o18			E06, o12
X10			o12			E07, o10
X11			o16			E05, o11
X12			o10			E06, o09
X13			o07			E03, o08

o14	W3		E02			/X04, >X19
o15			E07			/X05, X17
o16			E06			/X06, X11
o17			E06			/X08, X15
o18			E08			X09
o19			E03			X14

X14			o04, o19		E02
X15			o05, o17		E07
X16			o06, o11		E06
X17			o08, o15		E06
X18			o09			E08
X19	L2		o14			/E04

Andrew

        re 1457.0 by edp ...
        
>>    Consider arrangements of objects in m positions.  There are n0
>>    identical objects of one type, n1 of another type, n2 of a third, and
>>    so on up to nk.  The sum of the n's is m.  There are
>>    
>>    	m!/(n0!n1!n2!...nk!)
>>    
>>    such arrangements.  Call this number N.
>>[...]    
>>    The specific case I am considering at the moment is 9 positions with 4,
>>    4, and 1 objects.
        
        re 1461.0 by edp ...
        
>>    I just discovered a game of Maori origin.  It was marketed under the
>>    name "Squeeze Play" but the original name is apparently "Mu-Torere".
        
        "Just discovered"?  Ha!  It looks like you knew about it
        way back in topic 1457. :-) :-)
        
        Dan

re 1461.5:

>>        re 1457.0 by edp ...
        
>>>>    Consider arrangements of objects in m positions.  There are n0
>>>>    identical objects of one type, n1 of another type, n2 of a third, and
>>>>    so on up to nk.  The sum of the n's is m.  There are
>>>>    
>>>>    	m!/(n0!n1!n2!...nk!)
>>>>    
>>>>    such arrangements.  Call this number N'.
>>>>[...]    
>>>>    The specific case I am considering at the moment is 9 positions with 4,
>>>>    4, and 1 objects.

	This is not precisely the problem.   There are many symmetries which
mean that the number of distinct positions in this game is much less than N'.
To be precise, for (4,4,1) as discussed, N'=630, where there are 46 distinct
positions.   To compute the number of different positions systematically, we
can use the technology of 1010.14.

	Here, X = a set of nine locations
	      Y = {E,o,x}
	      G = D8 (symmetry group of octagon)

	And we restrict ourselves to considering those 630 elements of Y^X
"containing" 4 x's, 4 o's and 1 E.   This restriction complicates the counting
slightly.   So F(�) denotes the number of elements within this subset of Y^X
which are fixed by �.

	N = 1/|G| sum(� in G) |F(�)|

	Let a in D8 be a rotation by pi/4.   Let b in D8 be a reflection
which fixes two vertices.

cases:	F(I) = N'= 630	(since the identity fixes everything)
	F(a) = 0	(and similiarly for odd powers of a)
	F(a�) = F(a^6) = 2
	F(a^4) = 6
	F(b) = 18	(and similarly for all 4 reflections in D8 which fix
2 vertices)
	F(ab) = 6	(and similarly for all 4 reflections in D8 which don't
fix 2 vertices)

	Adding this lot up, we get N = 736/16 = 46.


btw, I wonder who wins the game if you play on a decagon instead of an octagon,
with 5 counters each.   Or what happens if on the octagon, one player has 5
and the other 3 counters?   It's not clear a priori whether having more or
less counters is an advantage.


Andrew.

re 1461.5:

>>        re 1457.0 by edp ...
        
>>>>    Consider arrangements of objects in m positions.  There are n0
>>>>    identical objects of one type, n1 of another type, n2 of a third, and
>>>>    so on up to nk.  The sum of the n's is m.  There are
>>>>    
>>>>    	m!/(n0!n1!n2!...nk!)
>>>>    
>>>>    such arrangements.  Call this number N'.
>>>>[...]    
>>>>    The specific case I am considering at the moment is 9 positions with 4,
>>>>    4, and 1 objects.

	This is not precisely the problem.   There are many symmetries which
mean that the number of distinct positions in this game is much less than N'.
To be precise, for (4,4,1) as discussed, N'=630, where there are 46 distinct
positions.   To compute the number of different positions systematically, we
can use the technology of 1010.14.

	Here, X = a set of nine locations
	      Y = {E,o,x}
	      G = D8 (symmetry group of octogon)

	And we restrict ourselves to considering those 630 elements of Y^X
"containing" 4 x's, 4 o's and 1 E.   This restriction complicates the counting
slightly.   So F(�) denotes the number of elements within this subset of Y^X
which are fixed by �.

	N = 1/|G| sum(� in G) |F(�)|

	Let a in D8 be a rotation by pi/4.   Let b in D8 be a reflection
which fixes two vertices.

cases:	F(I) = N'= 630	(since the identity fixes everything)
	F(a) = 0	(and similiarly for odd powers of a)
	F(a�) = F(a^6) = 2
	F(a^4) = 6
	F(b) = 18	(and similarly for all 4 reflections in D8 which fix
2 vertices)
	F(ab) = 6	(and similarly for all 4 reflections in D8 which don't
fix 2 vertices)

	Adding this lot up, we get N = 736/16 = 46.


btw, I wonder who wins the game if you play on a decagon instead of an octogon,
with 5 counters each.   Or what happens if on the octogon, one player has 5
and the other 3 counters?   It's not clear a priori whether having more or
less counters is an advantage.


Andrew.

    Re .4, .6:
    
    Yes, I figured it was a draw as well.  I also checked for 4, 6, 10, 12,
    14, and 16 spaces around the center; they are all draws.  The game is
    sort of interesting; it would be nice to find a variation or extension
    that resulted in challenging play.
    
    
    				-- edp

    Re .7:
    
    > btw, I wonder who wins the game if you play on a decagon instead of
    > an octogon, with 5 counters each.   Or what happens if on the octogon,
    > one player has 5 and the other 3 counters?   It's not clear a priori
    > whether having more or less counters is an advantage.
    
    I tried those variations; they are all draws.  With 2 and 6 counters,
    it is a win for the player with more counters, regardless of who
    starts.
    
    Maybe there are interesting variations with more complicated boards
    (e.g., more than one center space).
    
    
    				-- edp