4x4 puzzle Dots and Boxes
25 replies. Last post: 20070905
Reply to this topic Return to forum
michael at 20070824
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

michael at 20070824
5 +++++   4 + + + ++   3 ++++ +  2 +++ ++  1 + + ++ + a b c d e

michael at 20070824
5 +++++   4 + + + ++   3 ++++ + 2 +++ ++  1 + + ++ + a b c d e

michael at 20070824
5 +++++   4 + + + ++   3 ++++ + 2 +++ ++  1 + + ++ + a b c d e

wccanard at 20070824
5 +++++   4 + + + ++   3 ++++ + 2 +++ ++  1 + + ++ + a b c d e
maybe?
:)

wccanard at 20070824
hmm
5 +++++  4 + + + ++  3 ++++ + 2 +++ ++ 1 + + ++ + a b c d e
?

wccanard at 20070825
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.

wccanard at 20070825
OK so P1 is to play and he has to draw (tie). If we play the game out
lengthening the chains, we play a1b1,b1c1,e3e4 and d1e1
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 5chain, a 6chain
and a quad, which is worth (4) + (32) + 6 = 3 [P2 plays all but 4
of the quad and all but 2 of the 5chain] 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 preemptive 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 preemptive 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 43 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 allbuttwo.
Now he's 61 down and it's not his move, and player 2 comes up
with the amazing (but in fact rather natural) move b1b2, stopping
the last chain from growing to a 6chain, and now P1 loses the short chain
battle 31, giving a score of 92, 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 preemptive 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.

wccanard at 20070826
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 97.
Now what is left? Not many moves! There's b1c1 and e3e4. If P1 plays one of these then P2 plays the other and now the chains are both 5chains, 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 d3e3 and e2e3 are not worth considering, because they are dominated by e3e4 (why play d3e3 and lose a box and make a 4chain, when you could play e3e4 and make a 5chain; formally one uses a maninthemiddle argument to show that d3e3 can never be strictly better than e3e4).
Not much left now! We've just dealt with all moves in the top right. b1b2 loses to e3e4 (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. d1e1/e1e2 throws away a box! And a1a2/a1b1 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 noone else does.
wcc

wccanard at 20070826
So I don't have any time tonight to post much more, but I'll resolve the question raised in my previous post. The d1e1 move really _is_ pointless. It throws away a box and P2 just responds by lengthening a chain, for example b1c1. Now P1 is losing 10 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 nonloony move and the only ones left are lengthening chains again (or d3e3 etc, which is dominated by e4e3).
Hence if this puzzle has an answer, it must be a1a2 or a1b1 (both of these moves are the same from a gametheory 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

wccanard at 20070827
OK so so far we've seen that all moves for P1 tie apart from a1a2 and the equivalent a1b1. So let's play one (say a1a2) 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 d3e3 and e2e3 are both dominated by e3e4 so we don't have to check them, and similarly (recall we've played a1a2) a1b1 is dominated by b1c1, so we only have to check that the three moves for P2
1) b1c1
2) e3e4
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 preemptive sacrifice. It means that I might have got this bit wrong.
First let me deal with option 1: P2 plays b1c1. 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 preemptive 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 preemptive sac the controlling player should take all but 2, giving him a net gain of 51=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 6chain is clearly worth at least 4 because the controlling player takes 4 boxes before having to decide. Extending the 3chain to a 5chain 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 3chain 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 “3chain” replaced by “4chain” and “6chain” replaced by “5chain”, so I'll suppress it. Opening the 4chain is the move worth 4; opening the 5chain 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 3chain is worth exactly 3, lengthening the 3chain is worth 7, opening the 4chain is worth 3 and lengthening the 4chain 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

michael at 20070827
Probably cause I don't see it from a game theorist perspective. I find it peculiar that, with a 00 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.

wccanard at 20070828
Moving into a quad gives you more room. You can't preemptively 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 BerlekampScott aeroplane analogy you're giving the plane a bit more lift which makes it less likely to crash—you can perhaps now preemptively 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 6loop one move earlier, I would have won!
wcc

wccanard at 20070828
This one was particularly good because move 1 was so counterintuitive.
@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 54 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

sam_nead at 20070905
(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 79 loss. A can try to increase the number of small stuff by moving b1b2 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. d1e1 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 61 and can ensure a win 97 by moving b1b2. 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 b1b2. The obvious reply is at e3e3. So B gets 3+5 points in chains and one point of small stuff and wins 97.
So the only possible move for A is a1a2. Urk. I'll write more tomorrow.

sam_nead at 20070905
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!

wccanard at 20070905
@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 bchain than the achain, 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