endgame puzzle Dots and Boxes
13 replies. Last post: 2007-09-05Reply to this topic Return to forum
wccanard at 2007-08-10
Blue (Player 2) to play and win! He's 9-6 up but if that bottom region becomes a chain then the chain may well go to red.
6 + + +-+ + + | |b|5 +-+-+-+-+-+ |r|b|b|b|r|4 +-+-+-+-+-+ |r|b|b|r|b|3 +-+-+-+-+-+ |r|r|2 + + + +-+-+ |b|b|1 + + + +-+-+ a b c d e f
Remark: this puzzle is computer-generated (in particular, it's not related to an ongoing game on LG!). I'm just off on holiday but in a weeks' time I'll explain how I came across this puzzle and I'll answer it if some people have tried and failed.
sam_nead at 2007-08-12
In complete generality we have that
(moves made) - (boxes taken) + (double-crosses) = (turns completed)
M - B + D = T
That is, moves that take a box don't finish the turn. Double-crossing moves take two boxes at once and also do not finish the turn. Now WC has not been very polite, and hasn't told us the number of double-crosses so far. But using the formula we can still compute, as follows:
Unless I miscounted, there's been 41 moves made and 15 boxes taken. We are told that it is Blue's turn, so an odd number of turns have been completed. Mod 2 we have
1 + 1 + D = 1
so D must be odd. It follows that Blue (player 2) wants an even number of chains. For example, one loop and no chains ensures a win for blue. (Red will open the loop and Blue will take all four points.)
We also notice that the score is, in some sense, 11-8 Blue-Red as the four points in the north split evenly. It follows that if Red gets control then to win Blue needs only 2 points in the south.
So suppose that Blue moves to b2-b3. Red cannot permit a loop so must prevent the follow-up c1-d1. Sacking two boxes is not an option. The only possibility for Red is c1-c2, forcing a chain. Now Red has control. Blue moves b1-b2. This prevents the chain from growing. Since Blue gets two of the three short chains Blue wins 13-12.
(Probably there is another win for Blue starting at b1-b2.)
If I've made a counting error, and if there have been an even number of double-crosses then the problem is simpler: Blue wants an odd number of chains. He should try to force a chain in the lower corner is some simple fashion (eg b2-c2). If Red sacks, then Blue has won because he gets half of the four points to the north.
sam_nead at 2007-08-12
Hmmm. Perhaps a puzzle should also come with a strength: as in “For players with a rating between xxxx and yyyy.”
Marius Halsor at 2007-08-12
I think Blue could play f5-f6, and let red open the lower left area.
sam_nead at 2007-08-12
And how does Blue reply to Red's b2-c2?
michael at 2007-08-12
I'd say b3-b2, that way there are three 2x1 rectangles. Comebined with a 4-chain that gives 13-12 win for blue.
wccanard at 2007-08-17
@sam: I'll reply more fully when I get home, but your complaints above about how I didn't count the doublecrosses for you are in some sense clever but in some sense naive because they are overcomplicated. You're attempting to apply a formula about the total number of chains that each player is after but you seem to apply it to *a completely blank board*, and to do this you have to reverse-engineer the board and count all the moves, as you did. But the board I gave you is a disjoint union of three areas and surely you can see from the point of view of an abstract game that if you're doing a _sensible_ calculation, then all the moves *already played* are completely irrelevant—unless you demand to use some formula that applies to an empty board! The way to do the calculation you want to do is as follows: let the Euler characteristic formula apply to the board in question, not the initial board. Here's a simple way to do this: just let the game play itself out. Play 5 moves in the bottom left to make one long chain, and then play out the top region, and deduce immediately, without counting 41 lines or anything, that if the 3x2 becomes a chain then it'll be blue that will have to open it. That's what you need to know to work out the parity—and I *did* tell you that! What I'm saying is that you're working out the parity using a method that works but is very inefficient.
wccanard at 2007-08-18
@sam: here's a clearer way of making my point. If we were all used to playing dots and boxes on a 100x100 board, if that were the “standard size”, and if I had set “the same” problem, with the three unfinished areas in 3 of the corners of a 100x100 board, then would you have counted all of the 20,000 or so lines in the remainder of the board to work out what your best move should be?
wccanard at 2007-08-19
OK so I'm back and promised some comments.
So here's how this puzzle arose. I assumed, until about a month ago, that I “completely understood” 3x2 icelandic corners: the first player to play in the corner can force a chain, and his opponent can hold him to a chain of length 4, or he can, if he likes, force 0 chains but has to sacrifice 5 boxes to do so. What more does one need to know? Well, very occasionally, one really needs to know more. For example, in the above game, blue is basically going to have to let red form a 4-chain but he wants to guarantee that the two boxes left form a 2-chain rather than two 1-chains, because if they form a 2-chain he'll get them both and this is just enough to win.
OK so where did this position come from? What I did was I made a computer analysis of the following sixteen endgame positions: 3x2 icelandic plus some subset of
2x1 icelandic corner
[technical point: From a game-theory point of view a 2x1 icelandic corner is the same as a 2-chain and a “0-chain” so really I am analysing all possible short chain games here, and the 13-chain was just a random choice to mean that we're playing nimstring if we want. Really I think that for a complete analysis one has to do things like a 4-chain too, or two 3-chains, etc etc, but I didn't go this far]
I was a little bit disappointed with the results. In pretty much every case, the player whose turn it was, their best move was to play in the icelandic corner, and if he wanted a chain there he should be playing c1-c2 in order to maximise his score (in many cases other moves worked too) and if he didn't want one he should be playing c2-d2 or c2-c3. There were very few exceptions to this and even they were pretty “obvious”. The puzzle above was the only one that struck me as a little surprising (well, maybe one other was surprising, but there were several winning moves rather than just one). So that's where the puzzle came from.
OK so now the solution. Blue doesn't really want a chain but doesn't quite have the space to kill the chains, but he can get away with it—his *only* winning move is b2-b3. So Sam—there's a puzzle for you—you suggest b1-b2 but in fact red has a unique winning response! Can you find it? As Sam and Michael have both pointed out, the point is that then red gets his 4-chain but blue gets the 2-chain and the match.
wccanard at 2007-08-19
OK so now comments to specific points raised. I already attempted to counter Sam's accusations of impoliteness by suggesting that in fact the parity puzzle I'd left him with was easier to solve than he perhaps realised. The “suggested rating” idea is quite a good one though, isn't it! The problem with it is that of course the rating is a linear ordering on players that doesn't quite reflect specific abilities—e.g. there are some very strong dots and boxes players that will make elementary nimstring errors because they don't know nimstring—because “true” nimstring (i.e. carefully changing that region with nim-value 3 to nim-value 2, sort of thing) is *in practice* rarely of much importance—however it's easy to design puzzles where it is everything!
@Marius: Sam's response to you is right. If you play a “nothing” move in the top corner then b2-c2, and also a2-b2 and c2-c1, are all winning responses—the problem for blue now is that red will surely make a chain of length greater than 4 and win.
Michael is, as ever, succinct and correct.
I am tempted to analyse other regions in this way, although I don't quite know what other regions to do. Icelandic 2x2 seems so easy and Icelandic 4x2 somehow doesn't seem to come up so much. Does anyone have any requests??
wccanard at 2007-08-20
I just looked through all the 3x2 data again. Here's a summary of it. I'm only speaking about the 16 positions I analysed above.
When there's a very long chain, the player to move of course has to get the nim-value of the corner right. If he wants to make a chain then there are several ways to do this, but one thing I observed is that regardless of the state of the short chain game, c1-c2 (with 3x2 corner as in the position above) is always one of the best moves for P1 (in the sense that it makes the chain and furthermore maximises the number of boxes he'll get), and if he doesn't then, of course, sacrificing the box cd23 is always the best (of course—it's the unique winning nimstring move) and furthermore the “standard” line where P1 has to sacrifice 5 boxes is always one of the best lines for both players (in terms of maximising boxes), regardless of the state of the short chain game.
When there's no long chain (so I'm talking about the 8 positions Icelandic 3x2 plus some subset of (1-chain, 2-chain, 2x1 icelandic)), things are more subtle. The most interesting example, I already posted above—P1 has a unique winning move.
The only other examples I found in which one has to think a little are the following:
2x3 icelandic plus 2-chain: now player 1 (i.e. the player whose turn it is) is probably resigned to losing the chain battle but can pick up 3 of the remaining 8 boxes—there are two moves which ensure this and my feeling is that they are hard to find. So there's another puzzle (this was the other one I considered posting but the fact that there were 2 solutions made me prefer the one I posted). Of course b2-b3 is a disaster in this position because it essentially guarantees he'll only win two boxes.
Finally, 2x3 icelandic plus 1-chain: again P1 is probably resigned to losing the chain battle but there are four moves in the corner that he can play which will ensure he will get two of the seven remaining boxes, b2-b3 being one of them.
sam_nead at 2007-09-05
Blue b1-b2 gets the response Red a2-a3. This is the only winning reply, I think, so I don't feel _so_ bad.
wccanard at 2007-09-05
@sam: Yes! Well spotted. It is the only winning reply. It's a nice move too—it counters the threat of b1-c1 (the dreaded half-quad) by ensuring that the sacrifice guarantees a 5-chain.