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.