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.