play in a short chain rather than a long one? Dots and Boxes
26 replies. Last post: 20071210
Reply to this topic Return to forum
wccanard at 20070508
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**

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

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

michael at 20070702
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.

wccanard at 20070703
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 3chain and an isolated 1chain. 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 3chain or 1chain rather than some completely obvious move in the rest of the game). Can playing the 3chain _ever_ be strictly better than playing the 1chain? (i.e. opening the 3chain wins but opening the 1chain loses). Berlekamp asserts that this can never happen, if I understood him correctly.

wccanard at 20070703
@arjan: “I assume both a and b are independent of any other chains too?” Right—the achain and the bchain 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

Feen at 20070703
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.

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

wccanard at 20070703
@arjan: Yes. You can prove this by a maninthemiddle argument. I wrote some very brief notes on maninthemiddle 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.

flipster at 20071209
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.

wccanard at 20071209
No: if both chains are at least 3 then a maninthemiddle 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…

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

wccanard at 20071209
OK, I think this one checks out.
6 + + + + + +  5 ++ + +++ 4 ++++++3 ++++++ bbbbb2 ++++++ brrrr1 ++++++ a b c d e f
Blue to play. If blue opens the 1chain with a5a6 then red takes
the box and then plays d6e6 and is winning a seriously important
chain battle; blue's best line (well, one of them) is simply to
sacrifice with d5d6; then it's a straightforward endgame and
blue loses 1411 with best play.
But if blue opens isolated the 3chain then he wins 1312 with best play!
Say red takes one box and leaves blue the other two; then blue
plays f4f5. This move really hurts, because red wants the 5chain
so takes all but two and then blue plays d6e6 and now red has
to sacrifice 2 to keep control, and blue wins 1312.
Youch!
wcc

flipster at 20071209
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 2chain). 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.

wccanard at 20071209
No! I'm not talking about the preemptive sac: I'm talking about opening the isolated 3chain. I'll give you another example.

wccanard at 20071209
+ + + + + +  ++ + +++  +++++ + bb++ ++++ bbb++++++brrrr++++++
Blue's unique winning move in this position is to open the isolated 3chain.
[note: by “isolated” I mean that it can't grow any more!] Opening the isolated 1chain 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 3chain is *always* at least as good as opening an isolated 4chain, 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

wccanard at 20071209
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 3chain on the top left is isolated, and the one on the right isn't. Berlekamp's assertion is about isolated chains.

flipster at 20071209
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 2chain is the unique winning move. Maybe it's possible, but I don't know how.

wccanard at 20071209
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 3chain than an isolated 1chain] 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 3chains and so on, the game is usually completely humananalysable (in practice).

flipster at 20071209
yeah that's what I was thinking. The assertion makes very little sense if you ask me. Basically Berlekamp is saying that in a nonendgame 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?

wccanard at 20071209
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 1chains 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).

wccanard at 20071209
Aah, I see, t is how much you're leading by? Then t had better be at least n1 (on a board with an odd number of squares). And the general case is easy: if the position is G and an nchain, and you're t points ahead, then opening the nchain is going to win for you if and only if t+n2 (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 nchain wins if and only if t is greater than 4nv(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.

wccanard at 20071209
EDIT: sorry. It should be t+2n, not t+n2, so I want
t+2n greater than v(G)  2
and
t+2n greater than 2v(G)
for opening the nchain to be a winning move.
That is, t greater than v(G)4+n and also greater than nv(G). So you're using the same conventions as me :)

flipster at 20071210
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 1chains 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 1chains change anything at all? I don't think it matters when deciding whether to open an isolated chain or not.

wccanard at 20071210
“Also, how does adding two 1chains 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 1chain). That's why I said it might be hard to get a nice criterion for when opening a chain is the _only_ winning move.