First player (A) to move and tie. It's only 4x4, but I find this an interesting position. Not only for the first tying move, but the very much for the sequal move A must play to hold for the tie. Hope I get the html right.

5 +-+-+-+-+  |   |    4 + + + +-+  |   |    3 +-+-+-+ +        |2 +-+-+ +-+        |  1 + + +-+ +  a b c d e

 5 +-+-+-+-+  |   |    4 + + + +-+  |   |    3 +-+-+-+ +        | 2 +-+-+ +-+        |  1 + + +-+ +  a b c d e

As u can see, html isn't my playground … just give me a D&B board !

5 +-+-+-+-+  |   |   4 + + + +-+  |   |   3 +-+-+-+ +        |2 +-+-+ +-+        | 1 + + +-+ +  a b c d e

5  +-+-+-+-+   |   |    4 + + + +-+   |   |    3 +-+-+-+ +        |2  +-+-+ +-+        |  1 + + +-+ +   a b c d e

god, I'll just never get it right. Just hope someone can figure it out :(

5 +-+-+-+-+  |   |   4 + + + +-+  |   |   3 +-+-+-+ +        |2 +-+-+ +-+        | 1 + + +-+ +  a b c d e

maybe?

:-)

*doh*

hmm

5 +-+-+-+-+  |   |4 + + + +-+  |   |3 +-+-+-+ +        |2 +-+-+ +-+        |1 + + +-+ +  a b c d e

?

Heh, now all that's left is to do the puzzle :-)

@michael: can you confirm that the non-wobbly board above is right?

[this is of course code for " I'm stuck " :-) ]

Ooh, no, I'm unstuck. I think that the last move I tried works :-) I'll post some analysis later this evening if the idea holds up.

OK so P1 is to play and he has to draw (tie). If we play the game out

lengthening the chains, we play a1-b1,b1-c1,e3-e4 and d1-e1

and this is 4 moves, which is even, so player 1 had better watch it:

he's losing the chain battle and indeed will lose the game with

the line above: he wins the short chain battle, which is the box

in the bottom right, and is then faced with a 5-chain, a 6-chain

and a quad, which is worth (-4) + (3-2) + 6 = 3 [P2 plays all but 4

of the quad and all but 2 of the 5-chain] so he'll gain 1 and lose 3,

so he'll lose.

Conclusion so far: P1 can't just let all the chains grow to their full length.

Now *usually* in this kind of situation, the best idea is to start

making pre-emptive sacrifices, because then P1 is throwing away

shorter chains which is better for him as he's going to lose the chains

anyway (well, all but 2 of them). So two natural moves to try would be

to open the chains in the top right and/or bottom left. But these

moves *cannot* tie the game, because in both cases P2 is ahead when

he has to make the “do I take all the chain or all but 2” decision,

and at least one of these will score at least 0, so P2 must have a win.

So opening either chain can't possibly work (assuming that there is a

solution to the puzzle at all!).

Next natural possibility, and looking _much_ more promising, is opening

the quad! This can also be viewed as a pre-emptive sacrifice because

after the quad is played, opening a chain might now be a possibility.

I assumed for a long time that this (opening the quad) must be a good

first move for P1 because every other move is “too quiet” and looks

like it's helping P2. But after a careful

analysis I realised to my surprise that opening the quad does not win,

because P2 throws the chain battle, takes all 4 of the quad, and the

opens the chain in the top right. Now what can P1 do? If he takes

all three of the chain then he's losing 4-3 and also losing the chain

battle so is going to lose the game heavily because he'll lose at least

4 more in the last chain. So better for him is to take all-but-two.

Now he's 6-1 down and it's not his move, and player 2 comes up

with the amazing (but in fact rather natural) move b1-b2, stopping

the last chain from growing to a 6-chain, and now P1 loses the short chain

battle 3-1, giving a score of 9-2, and even though he wins the last

five boxes in the long chain this isn't quite enough.

This was when I got stuck :-) All the pre-emptive sacrifices don't work

and all the other moves looked meaningless. But there is a clue in

the above as to what to do. I'll leave it there and come back to

this later on when I have some more time.

So let me crack on for a bit. In my previous post I showed that no sacrifice could possibly tie—opening a long chain will never tie if you're not already ahead, and opening the quad looked more plausible but loses 9-7.

Now what is left? Not many moves! There's b1-c1 and e3-e4. If P1 plays one of these then P2 plays the other and now the chains are both 5-chains, so the long chain battle is worth at least 2 and the short chain battle is worth at most 1, so P2 has won. Moves d3-e3 and e2-e3 are not worth considering, because they are dominated by e3-e4 (why play d3-e3 and lose a box and make a 4-chain, when you could play e3-e4 and make a 5-chain; formally one uses a man-in-the-middle argument to show that d3-e3 can never be strictly better than e3-e4).

Not much left now! We've just dealt with all moves in the top right. b1-b2 loses to e3-e4 (again because the chains are now too big). And now the two corners—the only moves we've not analysed.

The corner moves look so so pointless. d1-e1/e1-e2 throws away a box! And a1-a2/a1-b1 is a nothing move: it doesn't threaten anything and just lets P2 have a go, so he has a chance to lengthen his chains.

Anyone else want to take over? I'll probably add more this evening (UK time) if no-one else does.

wcc

So I don't have any time tonight to post much more, but I'll resolve the question raised in my previous post. The d1-e1 move really _is_ pointless. It throws away a box and P2 just responds by lengthening a chain, for example b1-c1. Now P1 is losing 1-0 and hence cannot make any loony moves at all (a loony move is one that opens a loop, or a chain of length 3 or more), because after any loony move by P1 there is a response which ensures at least half the remaining boxes for P2 (and hence, in this case, the game). So if P1 is trying to tie he'll have to play a non-loony move and the only ones left are lengthening chains again (or d3-e3 etc, which is dominated by e4-e3).

Hence if this puzzle has an answer, it must be a1-a2 or a1-b1 (both of these moves are the same from a game-theory point of view). Funny looking moves!

What we have to do now is to play one of them and then analyse the game from P2's point of view and prove he doesn't have a winning move. I'll have to do this later on.

wcc

OK so so far we've seen that all moves for P1 tie apart from a1-a2 and the equivalent a1-b1. So let's play one (say a1-a2) and now we have to check that P2 can't win. Well, fortunately we don't have to check any of the loony moves, because after a loony move P1 will always be able to get at least half the remaining boxes, and hence tie at least. The loony moves are the ones which open the loop or the long chains. Furthermore d3-e3 and e2-e3 are both dominated by e3-e4 so we don't have to check them, and similarly (recall we've played a1-a2) a1-b1 is dominated by b1-c1, so we only have to check that the three moves for P2

1) b1-c1

2) e3-e4

3) sacrifice the bottom right hand box

don't give him a win. In fact I claim that in all three cases P1 can respond by opening the quad, which is a bit disturbing because it means that I don't understand Michael's original comment about holding for a tie—opening the quad looks quite natural to me because it opens the door to a pre-emptive sacrifice. It means that I might have got this bit wrong.

First let me deal with option 1: P2 plays b1-c1. Then P1 opens the quad, and this will draw if and only if the value of the remaining position (without the quad) is worth exactly 4 to the second player.

To check that the value of a position is 4, it suffices to show that the value of 1 move is 4, and the value of all moves is at least 4. The move which has value 4 is of course the natural move, the pre-emptive sacrifice in the top right; after that chain has gone the long chain battle is worth 6, the short chain battle 1, so the game is worth 5, so after the pre-emptive sac the controlling player should take all but 2, giving him a net gain of 5-1=4. So there's the move that's worth 4.

And it's easy to check that all other moves are worth at least 4: opening the 6-chain is clearly worth at least 4 because the controlling player takes 4 boxes before having to decide. Extending the 3-chain to a 5-chain is a terrible move, the long chain battle is now worth 7 so the game is worth 6, and sacrificing the bottom right is equally lousy, the natural response is to extend the 3-chain and again the long chain battle is worth way more than 4.

To be honest, the argument for move 2 is formally pretty similar with “3-chain” replaced by “4-chain” and “6-chain” replaced by “5-chain”, so I'll suppress it. Opening the 4-chain is the move worth 4; opening the 5-chain must be worth at least 3 and hence at least 4 because its value is even :-)

All that is left is P2's sacrifice of the bottom left; to check this doesn't work we open the quad and check that the value of the remainder of the game is worth exactly 3; if this is the case then P1 will take all four of the quad and again it will be a tie. One checks without too much trouble that opening the 3-chain is worth exactly 3, lengthening the 3-chain is worth 7, opening the 4-chain is worth 3 and lengthening the 4-chain is worth 7. So in this case P2 should take the quad.

Go on then Michael, where did I slip up? I don't understand your comment about the sequel move.

wcc

Probably cause I don't see it from a game theorist perspective. I find it peculiar that, with a 0-0 score, moving into a quad while there are 'free moves' available results in a tie. On a 5x5 board this is always a loss.

Thank you for the thourough postings of your thinkingprocess, that's very interesting.

Moving into a quad gives you more room. You can't pre-emptively open a chain and hope to tie on a 4x4 board if you're level. But you can open a quad because you're sacrificing 0 before the parity decision has to be made, and in the Berlekamp-Scott aeroplane analogy you're giving the plane a bit more lift which makes it less likely to crash—you can perhaps now pre-emptively sacrifice on your next move. The only reason opening a quad when you're level on a 5x5 board always results in a loss is because there are an odd number of squares. A better analogy would be opening a quad when you're 1 up—this can sometimes just work, as you know. We just played a game in which exactly this situation occurred, right? If I had been able to complete the 6-loop one move earlier, I would have won!

wcc

I love these puzzles :)

This one was particularly good because move 1 was so counter-intuitive.

This one was particularly good because move 1 was so counter-intuitive.

@Michael: instead of formulating the puzzle as “try to tie this position on a 4x4 board”, why not add nine completed extra squares, to make it a 5x5 board, make the score 5-4 to P1 and say “try to win as P1”. This is logically the same problem (as P1 will never win the 4x4 game with best play), but now P1 is 1 box ahead so perhaps the quad looks like a more meaningful move to you now?

wcc

(NB I freely admit that I skimmed WC discussion. This is just my take on the problem, with the advantage of hindsight.)

Straight forward moves on A's part give a 7-9 loss. A can try to increase the number of small stuff by moving b1-b2 but that doesn't help – B loses a box from the southern chain and gets a box in the small stuff. A can't open the south or the east chains – B takes a box and then will definitely get at least half of the boxes remaining. d1-e1 makes the loss even worse.

Perhaps there is a tying move in the quad: Ok – suppose that A moves in the quad. If B takes all four boxes then I'll call B “player X” and A “player Y” or B declines. In the latter case A takes all four boxes and I'll call A “player X” and B “player Y”. In any case, Y has four points and is first to move in the rest of the game. How many more points can Y get?

Well, Y has a huge lead so can afford to to loony. Y should open shorter chains before longer, so the northeast is the correct place to go. If X only takes one point then Y leads 6-1 and can ensure a win 9-7 by moving b1-b2. If X takes three points then Y gets at least 4 more points in the southwest chain and definitely wins.

So A can't hope for a tie via opening the chains, the quad, or any short stuff. Extending chains is a mistake… that only leaves “stunting” chains and “waiting moves” in the southwest corner.

Ok, the only chain that can be “stunted” is the southwest at b1-b2. The obvious reply is at e3-e3. So B gets 3+5 points in chains and one point of small stuff and wins 9-7.

So the only possible move for A is a1-a2. Urk. I'll write more tomorrow.

Ack – the above post has many typos! In particular I switched X and Y midstream! The point was supposed to be that whoever takes the four boxes gets a new name “X” and moves first in the rest of the game. (But I called him Y…) Sorry!

@sam: I am intrigued by one of your comments—the one about taking shorter chains before longer. I can prove that if there are two disjoint isolated long chains of lengths a, b, with a less than b, then it's never better to open the b-chain than the a-chain, but my proof doesn't apply in cases where the chains are “unfinished”. Is it a general rule that, if you're going to prematurely sacrifice, then you should still open short chains before longer ones? My gut feeling is that this may not always be the case (it is the case in this problem though!).

wcc