In Berlekamp's book on dots and boxes, he asserts that a canonical dots and boxes player will never play in an independent chain if there is a shorter one available. By this he means (I think!) that if there are two independent chains of lengths a **br>

I had imagined that the proof of this assertion would be rather easy. If a>=3 or b<=2 then it is, but if one chain is short and one is long then the argument seems to me to become much more subtle. Am I right (it is subtle) or am I missing something simple?

wc**

Apologies for the multiple post: I've been caught out by html tags (this is my first time in the forum). The garbled part of the post above is supposed to say

…if there are two independent chains of lengths a and b, with a less than b, then there is no situation where opening the chain of length b is a winning move, but opening the chain of length a is a losing move.

I assume both a and b are independent of any other chains too?

Wouldn't it be better to move into the longer chain first in a situation like this:

*--*  *--*  *|  |  |      *--*  *  *--*      |  |  |*--*--*  *--*|  |  |  |*--*--*  *  *|  |  |  *--*--*--*  *

ok, forget that bad example. But i'm sure there are situations where it's better to move into the long chain. Especialy if chains end in quads or loops.

Michael—I agree that if chains end in quads or loops it's a more complicated matter. Berlekamp is talking about **isolated** chains though—ones that run from and to the ground with no quads or little “fiddly bits” at the ends, like in your example. For example imagine a 1x1 icelandic corner within a 2x2 icelandic corner :-) That's an isolated 3-chain and an isolated 1-chain. Now put anything you like in the other 21 squares, except that perhaps I should *perhaps* demand that there are no “free” capturable squares and also that the position isn't loony (I didn't think about it—but I am looking for practical applications, where one really might consider playing the 3-chain or 1-chain rather than some completely obvious move in the rest of the game). Can playing the 3-chain _ever_ be strictly better than playing the 1-chain? (i.e. opening the 3-chain wins but opening the 1-chain loses). Berlekamp asserts that this can never happen, if I understood him correctly.

@arjan: “I assume both a and b are independent of any other chains too?” Right—the a-chain and the b-chain are completely isolated from each other and from the rest of the board, and both are complete chains running from the ground (i.e. the edge of the board) to the ground.

Sorry if I didn't make this clear.

wc

quote michael: “Especialy if chains end in quads or loops.”

Can I state that it is always better to play a loony move in a chain that is connected to a loop than play your move in that loop? Cause playing in the loop would make the total a chain.

EDIT: This is for the case where there are no other loops or chains connected to them…

@arjan: Yes. You can prove this by a man-in-the-middle argument. I wrote some very brief notes on man-in-the-middle at wccanard.wetpaint.com (notesforgolem.pdf). I don't explain it too clearly but I give examples of what one can prove. I don't do this example but here's the heart of the argument. Say you're playing Grandmaster 1 and Grandmaster 2 and you are trying to do the trick where you copy the moves of one grandmaster in the game with the other one, so they are really playing each other. Say a region forms in the games which is a chain with a loop at the end (and nothing else: the other end of the chain goes to the ground). Now imagine a grandmaster (say GM1) makes a mistake and opens the loop. You don't copy—you open the chain in the game against GM2. If the second grandmaster takes all but two, you take all but two against GM1, and if he takes all, you take all against GM1. You are now winning on average. The worst that can happen is that you lose all the loop later on against GM1 but even then you are level. This is a proof that opening the loop is never strictly better than opening the chain.

I'm sorry to bring up this old topic, but I'm a bit confused. You are talking about 2 isolated chains a and b, and a is less than b. Are both chains at least 3? Or could one of them be 1 or 2.

No: if both chains are at least 3 then a man-in-the-middle argument shows that opening the longer one is never better than opening the shorter one (although there are plenty of cases where it's just the same). Similarly if both chains are 1 or 2, then open the shortest one first. The one case I've never been able to resolve is when one is short and one is long. I spent a lot of time trying to prove the assertion; maybe I should spend some time trying to find a counterexample! My understanding of Berlekamp's book is that Berlekamp asserts that opening the longer chain is never better than opening the shorter one…

That didn't take long! The assertion is just plain wrong! Had I tried to actually *disprove* it earlier, maybe I wouldn't have wasted so many hours of my life trying to prove it!

I'll post a counterexample in a few minutes.

OK, I think this one checks out.

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

Blue to play. If blue opens the 1-chain with a5-a6 then red takes

the box and then plays d6-e6 and is winning a seriously important

chain battle; blue's best line (well, one of them) is simply to

sacrifice with d5-d6; then it's a straightforward endgame and

blue loses 14-11 with best play.

But if blue opens isolated the 3-chain then he wins 13-12 with best play!

Say red takes one box and leaves blue the other two; then blue

plays f4-f5. This move really hurts, because red wants the 5-chain

so takes all but two and then blue plays d6-e6 and now red has

to sacrifice 2 to keep control, and blue wins 13-12.

Youch!

wcc

Yes, of course, but that's just a preemptive sacrifice. There are quite a lot of positions where a preemptive sacrifice is the unique winning move (which means it's better than opening a 1- or 2-chain). I'm pretty sure Berlekamp is fully aware of that. I think his assertion was meant for endgames, positions where no free moves are available.

No! I'm not talking about the pre-emptive sac: I'm talking about opening the isolated 3-chain. I'll give you another example.

+ + + + + +  | |+-+ + +-+-+    |     |+-+-+-+-+ +    |b|b|+-+ +-+-+-+    |b|b|b|+-+-+-+-+-+|b|r|r|r|r|+-+-+-+-+-+    

Blue's unique winning move in this position is to open the isolated 3-chain.

[note: by “isolated” I mean that it can't grow any more!] Opening the isolated 1-chain loses heavily. I'm pretty sure Berlekamp is not talking about the endgame: his other assertions are correct independent of where we are in the game—for example opening an isolated 3-chain is *always* at least as good as opening an isolated 4-chain, whatever the remainder of the position is. Of course, if you're right and he _is_ talking about a position where “no chains can grow any further” then, modulo a rigorous definition of this, I'm pretty sure it's not hard to prove.

wcc

Clarification to flipster: by an “isolated” or “independent” chain, I mean one running from the ground to the ground. So for example in the first position I posted above, the 3-chain on the top left is isolated, and the one on the right isn't. Berlekamp's assertion is about isolated chains.

You're right, technically that move isn't a preemptive sacrifice. But it is in the sense that you open a chain when there are free moves available, and you know you lost the chain battle.

Also, I noticed that in both examples, after opening the isolated chain, a preemptive sacrifice follows immediately. I'm not sure what that means, but it's something to think about.

Alright, let's assume Berlekamp is not talking about the endgame. I can't think of a position with free moves available where opening an isolated 1- or 2-chain is the unique winning move. Maybe it's possible, but I don't know how.

Berlekamp isn't making any assertions about uniqueness. I only put the uniqueness in “because I could”, as it were. This problem [whether it's ever better to open an isolated 3-chain than an isolated 1-chain] has been bugging me for months so I'm grateful that you turned my attention back to it! It's kind of a useless observation in practice though, because when you're thinking about opening 3-chains and so on, the game is usually completely human-analysable (in practice).

yeah that's what I was thinking. The assertion makes very little sense if you ask me. Basically Berlekamp is saying that in a non-endgame position, opening an isolated chain is never the best move. You just proved that is wrong. Congratulations!

Now what can we say about positions where opening an isolated chain is a winning move? Or even better, what can we say about positions where it's the unique winning move? I think it's kinda interesting to know that.

This is what I came up with:

Let's call the isolated chain n, and the position without the isolated chain G.

I'm pretty sure the same rules apply for this kind of positions as they do for preemptive sacrifices. So you need to be ahead in boxes by at least 2 boxes (on a board with an odd amount of dots) (so t is at least 2)

Also (if there are no loops) I think the following statement is correct:

v(G) - 4 + n < t

What do you think? Is it useful to analyse this some more, or are such positions too rare to bother?

1) What's t?

2) It might be difficult to give an abstract condition equivalent to “opening this

chain is the only best move”. The problem is that you can add two 1-chains to a game, and barely change it at all (in the sense that you change almost none of the natural invariants attached to the game, like its value).

Aah, I see, t is how much you're leading by? Then t had better be at least n-1 (on a board with an odd number of squares). And the general case is easy: if the position is G and an n-chain, and you're t points ahead, then opening the n-chain is going to win for you if and only if t+n-2 (the amount of points you'll be ahead

when your opponent makes the decision) is greater than \|v(G)-2\| (which is the amount of points he'll get if he makes the correct decision about whether to take all but two or not). So opening the n-chain wins if and only if t is greater than 4-n-v(G) and also greater than v(G)-n. Convention: v(G) is how much the game G is worth to your *opponent*! This might sound crazy, but it's not, because you frequently are applying the notation to a game G with only loony moves left, so if you had the obvious convention then v(G) would almost always be negative.

EDIT: sorry. It should be t+2-n, not t+n-2, so I want

t+2-n greater than v(G) - 2

and

t+2-n greater than 2-v(G)

for opening the n-chain to be a winning move.

That is, t greater than v(G)-4+n and also greater than n-v(G). So you're using the same conventions as me :-)

I'm glad we agree about that!

“It might be difficult to give an abstract condition equivalent to “opening this

chain is the only best move”. The problem is that you can add two 1-chains to a game, and barely change it at all (in the sense that you change almost none of the natural invariants attached to the game, like its value). "

I think it's possible to set some guidelines, so it becomes easier to find more examples.

Also, how does adding two 1-chains change anything at all? I don't think it matters when deciding whether to open an isolated chain or not.

“Also, how does adding two 1-chains change anything at all?“. It doesn't really change much at all. But it might change a position where the *unique* winning move is opening a chain, to a position where there are other winning moves! (namely opening the 1-chain). That's why I said it might be hard to get a nice criterion for when opening a chain is the _only_ winning move.