endgame puzzle Dots and Boxes
13 replies. Last post: 20070905
Reply to this topic Return to forum
wccanard at 20070810
Blue (Player 2) to play and win! He's 96 up but if that bottom region becomes a chain then the chain may well go to red.
6 + + ++ + +  b5 ++++++ rbbbr4 ++++++ rbbrb3 ++++++ rr2 + + + +++ bb1 + + + +++ a b c d e f
Remark: this puzzle is computergenerated (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.
wc

sam_nead at 20070812
In complete generality we have that
(moves made)  (boxes taken) + (doublecrosses) = (turns completed)
M  B + D = T
That is, moves that take a box don't finish the turn. Doublecrossing 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 doublecrosses 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, 118 BlueRed 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 b2b3. Red cannot permit a loop so must prevent the followup c1d1. Sacking two boxes is not an option. The only possibility for Red is c1c2, forcing a chain. Now Red has control. Blue moves b1b2. This prevents the chain from growing. Since Blue gets two of the three short chains Blue wins 1312.
(Probably there is another win for Blue starting at b1b2.)
If I've made a counting error, and if there have been an even number of doublecrosses 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 b2c2). If Red sacks, then Blue has won because he gets half of the four points to the north.

sam_nead at 20070812
Hmmm. Perhaps a puzzle should also come with a strength: as in “For players with a rating between xxxx and yyyy.”

michael at 20070812
I'd say b3b2, that way there are three 2x1 rectangles. Comebined with a 4chain that gives 1312 win for blue.

wccanard at 20070817
@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 reverseengineer 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.
wc

wccanard at 20070818
@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?
wc

wccanard at 20070819
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 4chain but he wants to guarantee that the two boxes left form a 2chain rather than two 1chains, because if they form a 2chain 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
isolated 1chain
isolated 2chain
2x1 icelandic corner
isolated 13chain
[technical point: From a gametheory point of view a 2x1 icelandic corner is the same as a 2chain and a “0chain” so really I am analysing all possible short chain games here, and the 13chain 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 4chain too, or two 3chains, 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 c1c2 in order to maximise his score (in many cases other moves worked too) and if he didn't want one he should be playing c2d2 or c2c3. 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 b2b3. So Sam—there's a puzzle for you—you suggest b1b2 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 4chain but blue gets the 2chain and the match.

wccanard at 20070819
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 nimvalue 3 to nimvalue 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 b2c2, and also a2b2 and c2c1, 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??
wc

wccanard at 20070820
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 nimvalue 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, c1c2 (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 (1chain, 2chain, 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 2chain: 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 b2b3 is a disaster in this position because it essentially guarantees he'll only win two boxes.
Finally, 2x3 icelandic plus 1chain: 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, b2b3 being one of them.

sam_nead at 20070905
Blue b1b2 gets the response Red a2a3. This is the only winning reply, I think, so I don't feel _so_ bad.

wccanard at 20070905
@sam: Yes! Well spotted. It is the only winning reply. It's a nice move too—it counters the threat of b1c1 (the dreaded halfquad) by ensuring that the sacrifice guarantees a 5chain.