The following problems are composed by J.P. Grossman.  Problem 3
earned 2nd prize the clobber problem composition contest.

---------------------------------------------------------------------
PROBLEMS
---------------------------------------------------------------------

In the following problems x is Left, and each problem has x to move and win.

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

Problem 1

5   xxo
4   o x
3   ooo
2 oxx
1   ooxo

  abcdef

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

Problem 2

4    oxx
3 oooxxx
2 oo ox
1  x

  abcdef

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

Problem 3

6    o
5   oo o o
4 x oxxooo
3 xx  o x
2 ox  ox
1 ooo  o

  abcdefgh

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

Problem 4

6  xx
5  xxx
4  oox
3   oxoxo
2  oo  oo
1 xooo

  abcdefg

---------------------------------------------------------------------
SOLUTIONS
---------------------------------------------------------------------

Lemma
-----

Suppose a connected clobber position P consists of exacly one 'o' and at least
one 'x'.  Let k be the smallest number of moves that o can make before either:

a) There are no more moves

or

b) o can make 1 or 2 more moves, after which there are no more moves
   
Then the position has atomic weight k-1.

Proof
-----

Our proof is by induction on the number of x's; as is often the case in
game theory proofs our base cases are implied.  Denote far star by F*.  Note 
that from a connected position P with one 'o' and at least one 'x' the only 
left option is 0, and applying the induction hypothesis the atomic weights of
the right options are all integers >= -1.  It follows that the atomic weight 
of P is:

    -1    if P + F* < 0
    0     if P + F* || 0
    n+1   if P + F* > 0, where n is the smallest right-option atomic weight

First suppose that o can end the game in a single move.  There are two cases:
either o can also end the game in two moves, so that k = 0, or any move that
does not immediately end the game requires at least two more moves to end the
game, so that k = 1.

In the first case we claim that P + F* < 0.  First, o can win by moving to
P + *, for x must move to 0 in one component and o wins by moving to 0 in the
other component.  Next, x has no winning move: if x moves to F* or to P then o
moves to 0, if x moves to P + *m for m > 1 then o moves to P + *, and if x 
moves to P + * then o moves to P' + * where o can end the game P' in a single 
move, so as before x has no winning move.  Hence P + F* < 0, so the atomic 
weight of P is -1.

In the second case we claim that P + * = 0.  First, x has no winning move, as
before.  Next, if o moves to P or * then x moves to 0.  Finally, if o moves to
P' + * then x moves to P' and wins since o requires at least two moves to end
the game from P'.  Hence P = * and the atomic weight of P is 0.

Now suppose that o can end the game in two moves but not one.  We again 
consider two cases: k = 1 and k = 2.  

In the first case we claim that P + F* || 0.  First, x can win by moving to
P.  Next, o can move to P' + F* where P' has k = 0: from the previous 
arguments P' + F* < 0 so o wins.  Thus P + F* || 0, so the atomic weight of P
is 0.

In the second case we claim that P + F* > 0.  Again, x wins by moving to P.
If o moves to P + *m (m > 0) then x moves to P, if o moves to P then x moves
to 0, and if o moves to P' + F* then x moves to either P' or P' + * depending
on o's choice of P'.  Specifically, if o can end P' in a single move then
we know from before that P' = * (since k = 2, in this case, no option P' 
exists from which o can end the game in either one or two moves) so x wins by 
moving to P' + *.  If o cannot end P' in a single move then x wins by moving 
to P'.  Hence P + F* > 0, so the atomic weight of P is one greater than the 
smallest right-option atomic weight, which is 0 by induction (all right 
options have k >= 1 and at least one has k = 1), so the atomic weight 
of P is 1.

Finally, if o requires at least three moves to end the game we claim that
P + F* > 0.  First, x can win by moving to P.  Next, if o moves to P + *m
(m > 0) then x moves to P.  If o moves to P then x moves to 0.  Finally if
o moves to P' + F* then x moves to P' and wins since o requires at least two
moves to end the game from P'.  Hence the atomic weight of P is one greater
than the smallest right-option atomic weight, which is k-2 by induction, so
the atomic weight of P is k-1, and our induction is complete.

Of course if x's and o's are reversed then the atomic weight is 1-k.

In the following solutions we will also use the facts that ox^n = (n-1)^ + n*,
oxoo = ^*, {^^*|*} = ^, and {^|^} = ^^*.

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

Solution 1

5   xxo
4   o x
3   ooo
2 oxx
1   ooxo

  abcdef

c2c3 splits the position into three components:

5   xxo
4   o x
3   xoo
2 ox
1   ooxo

  abcdef

The top component is rotationally anti-symmetric, hence it has value 0 (the 
second player wins by playing symmetrically).  The middle component has value 
*, and the bottom component has value ^*.  Hence the entire position has value
^, so it is a win for x.

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

Solution 2

4    oxx
3 oooxxx
2 oo ox
1  x

  abcdef

d3d2 splits the position into two components:

4    oxx
3 ooo xx
2 oo xx
1  x

  abcdef

Using the lemma, the left component has k = 2 (x moves up twice), so the 
atomic weight is -1.  The right component has k = 4, so the atomic weight 
is 3.  Hence the overall atomic weight is 2, so x wins.  d3d4 would be an
error as then the right component would have k = 3 and atomic weight 2.

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

Solution 3

6    o
5   oo o o
4 x oxxooo
3 xx  o x
2 ox  ox
1 ooo  o

  abcdefgh

e4f4

6    o
5   oo o o
4 x ox xoo
3 xx  o x
2 ox  ox
1 ooo  o

  abcdefgh

This moves splits the position into four components.  First consider the 
bottom left component.  There are three x options: a3a2, b2a2, and b2b1. It is
fairly easy to see that the first two options are 0.  The third option is:

4 x 
3 xx
2 o 
1 oxo

  abc

We claim that this position P is *.  Consider the sum P + *.  First, x has no 
winning move: if x moves to P then o moves to 0 (c1b1), if x moves b1c1 (0) 
then o moves in * to 0, if x moves b1a1 then o moves a2a3 to *+*=0, and if x 
moves a3a2 then o moves a1a2 to *+*=0.  Next, o has no winning move: if o 
moves to P then x moves to 0 (b1c1), if o moves a2a3 then x move a4a3 to 
*+*=0, if o moves a1b1 then x moves in * leaving ^, and if o moves c1b1 then 
x moves in * to 0.  Hence P + * = 0, so P = *.

The left options are therefore 0, *.  But the position is symmetric (we can
rewrite it as):

 xxoo
xxoo

so the right options are also 0, *, and this component has value *2.

Next, using the lemma the top component has k = 1 (d4d5), so the atomic 
weight is 0, and the bottom component has k = 0, so the atomic weight is 1.

Finally, consider the rightmost component.  The left options are xooo = vv*, 
xxoo = 0, and oxxoo = {0,v|^*,*} = {0|*} = ^, so ^ dominates.  The right
options are 0, * and

  o
ooo
 x

which by the lemma has k = 1 and atomic weight 0.  Hence, all the right 
options have atomic weight 0, and the dominant left option has atomic weight 
1.  It follows that the atomic weight of this component P is 0 or 1 depending
on whether or not the component is greater than F*.  The combined atomic 
weight of the three components on the right is therefore >= 1.  Furthermore, 
no position of any of these components has value *2, so 
*2 + (other three components) >= 0 and hence x wins.

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

Solution 4

6  xx
5  xxx
4  oox
3   oxoxo
2  oo  oo
1 xooo

  abcdefg

1. d3c3

6  xx
5  xxx
4  oox
3   x oxo
2  oo  oo
1 xooo

  abcdefg

x is threatening 2. c3c4.  Taking on a1 or f3 does not help o.  

If o plays 1. ... c4c3 the resulting position is:

6  xx
5  xxx
4  o x
3   o oxo
2  oo  oo
1 xooo

  abcdefg

The top component has k = 4 and thus atomic weight 3, the bottom component
has k = 2 (a1b1, b1c1) and thus atomic weight -1, and the right component
has k = 1 and thus atomic weight 0, so the entire position has atomic weight
2 and therefore x wins.

If o plays 1. ... c2c3 then x plays 2. a1b1 and the position is:

6  xx
5  xxx
4  oox
3   o oxo
2  o   oo
1  xoo

  abcdefg

It is easy to check that neither player has a winning move in the top
component, so this component has value 0.  The bottom component has value
^* and the right component has value *, so the entire position has value ^
and x wins.

If o plays 1. ... c4c5 then x plays 2. d5c5, and if o plays 1. ... c4d4
then x plays 2. d5d4.  In both cases the resulting position is:

6  xx
5  xx 
4  o x
3   x oxo
2  oo  oo
1 xooo

  abcdefg

The component on the right has value *, and the component on the top has
value 3^.  By symmetry, the bottom component has only one left option:

     ox
A = xooo

A has three left options:

 ox                 x                  o
 xoo = {0|v} = *,  xooo = {0|0} = *,  xoxo = {^,0,v|*,0,v} = {^|*,v}

The last option is dominated by * because left has no winning move in 
{^|*,v} + *: if left moves in * then right moves to v and wins, and if left 
moves to ^ + * then right moves to * + * = 0 and wins.  A has three
right options:

  ox           o           oo
 o oo = ^*,  xooo = vv*,  xo o = vv*

Hence A = {*|vv*} = v.  Next, again by symmetry the bottom component has only
one right option:

     o
B = xooo = {^*|0}

Hence the value of the bottom component is {A|B} = {v|{^*|0}}.  But B is 
reversible because left has no winning move in v* + {A|B}: if left moves
to v* + A = vv* then right wins, and if left moves in v* leaving {A|B} then 
right moves to B, left moves to ^* and again right wins.  Hence the value
of the bottom component is {v|0} = vv*, so the value of the entire position
is * + 3^ + vv* = ^ so x wins.

Finally, if o plays 1. ... b4b5 then x plays 2. c3c2 and the position is:

6  xx
5  oxx
4   ox
3     oxo
2  ox  oo
1 xooo

  abcdefg

The component on the right has value *, and we saw previously that the bottom
component (A) has value v.

The top component has left options ^ and 

     x
C = xxx
     ox

^ dominates because x has no winning move in v + C: If x moves in C leaving v
then o moves to 0, and if x moves in v to * then o moves up in C to * + v* = v
and wins.  The right options of the top component are

    ox        xx
D =  xx,  E =  ox
     ox        ox

D has left options ^^* and *, so ^^* dominates.  The right options of D are
oxxxo = {^|0} = *, oxoxx = {^,0|0} = *, and

 o
 xx = {^,0|0} = *.
 ox

Hence D = {^^*|*} = ^.  E has left options ^^*, * and v*, so ^^* dominates. 
The right options of E are ^*, * and xxoxo = *, so * dominates and 
E = {^^*|*} = ^.  Hence the top component has value {^|^} = ^^*.

The value of the entire position after 2. c3c2 is therefore * + v + ^^* = ^
so again x wins.