5+5=6+4? Dots and Boxes
16 replies. Last post: 20071214
Reply to this topic Return to forum
wccanard at 20070703
I am still learning things about computing the values of loony endgames. I've been thinking about the problem on and off for a month but here is something that only occurred to me yesterday. If a position has two isolated 5chains (and a bunch of other stuff) and when neither player is looking, someone changes the board slightly so that one 5chain becomes a 6chain and the other becomes a 4chain, is the new game equivalent to the old one? The moral reason as to why this might be the case is that by the time either player is considering opening an isolated 4chain the rest of the game must be so simple that they must just be playing out the endgame. But I am not convinced by that argument and in fact am not convinced that 5+5 does equal 6+4 in this context. On the other hand I do wonder whether perhaps 50+50=60+40 in the sense that by the time someone is opening an isolated 40chain, surely the game is essentially over in some sense? If 50+50=60+40 but 5+5 doesn't equal 4+6 then a natural question would be to ask where the cutoff occurs. Also, I guess in the back of my mind I'm thinking about an arbitrary (finite) dots and boxes game, but it could perhaps be the case that 5+5 doesn't equal 6+4 in this generality but it does equal 6+4 on a 5x5 board?
Any ideas anyone?
wc

Carroll ★ at 20070703
Well I think you lack a nice game theory for D&B to tackle that.
If you had one where the value of the game could be describbed in terms of options: G=, and \G\=cv(G)=\\ could you write somehow that if Right has control and left lose at least n with option G1 (smallest chain?) the value of the game is \\ with n<=m<=…<=z ?
With this notation, let compare a sum of a loony game G with either 5+5 or 4+6 with the hypothesis that playing a chain, the smallest will be played :
\G+5+5\ = \\
where
\G+4+6\ = \\
by induction for each option Gi, Gi+5+5 = Gi+4+6 so there are reverting moves and you can remove these options.
all you have to prove now (or disprove) is that \G+2+53\=\G+2+62\ or
1+\G+2+5\=\G+2+6\ with a game G loony.
Is it flawed or simpler ?

Carroll ★ at 20070703
Args every < was removed as possible html tag, let me try again.
If you had one where the value of the game could be describbed in terms of options: G= {G1,…,Gi} and \G\=cv(G)= \{G1,…,Gi}\ could you write somehow that
if Right has control and left lose at least n with option G1 (smallest chain?) the value of the game is \{G1n,G2m…,Giz}\ with n<=m<=…<=z
With this notation, let compare a sum of a loony game G with either 5+5 or 4+6 with the hypothesis that playing a chain, the smallest will be played :
\G+5+5\ = \{G1+5+5,…,Gi+5+5,G+2+53}\
where
\G+4+6\ = \{G1+4+6,…,Gi+4+6,G+2+62}\
by induction for each option Gi, Gi+5+5 = Gi+4+6 so there are reverting moves and you can remove these options.
all you have to prove now (or disprove) is that \G+2+53\=\G+2+62\ or
1+\G+2+5\=\G+2+6\ with a game G loony.
Is it flawed or simpler ?

wccanard at 20070703
What I think you're saying is this: prove it by induction on the size of the game. There is a slightly stronger method that one can use—the “man in the middle” approach. The idea is that Grandmaster 1 (a perfect player) plays G+5+5 against me, and I play Grandmaster 2 (another perfect player) starting with position G+6+4. The trick of course is that I wait for one GM to play, and only then play against the other. If I can always get 50 percent of the boxes then we have a proof that 5+5=6+4. However what I am worried about is Grandmaster 2 opening the 4chain at some point. I then have to open the 5chain against GM1. I am then going to be 1 box down on average. Now can it possibly happen that later on it's GM1 that opens the remaining 5chain? Then I open the 6chain against GM2 and I will be two down, which is no good.
I think you can try and prove the result by induction (which is really all I am doing above, just presented in a different way somehow), but I don't quite see how you can reduce to the loony case, and even if you can then I don't see how to rule out the situation above. Somehow the problem is that v(H+5) and v(H+6) will differ by 1 but it's hard to say which is bigger.
Aah, I see! Perhaps it's not hard to say which is bigger if H is loony! Maybe this is going somewhere.
wc

wccanard at 20070707
Carroll said:
“all you have to prove now (or disprove) is that \G+2+53\=\G+2+62\ or
1+\G+2+5\=\G+2+6\ with a game G loony.”
Unfortunately life isn't so simple. If H is any game then one can prove
that \H+5\ (the value of H plus a disjoint 5chain) is either \H+6\+1
or \H+6\1 (use a maninthe middle argument) but it's very difficult to give nice conditions to decide which. For example if H=3+3+3+3+3+3+…+3 (say, 1000 3s) and 100<=n<=200 then \H+n\ is either 1 or 2 depending on whether n is even or odd. In particular \H+5\=\H+7\. So one needs to see a more subtle invariant
before one can push this argument through. Here's one question that would shed light on the matter:
Can there ever be a position in dots and boxes with two 5chains in, and an *optimal* play of the game from that position (i.e. both players play optimal moves at each stage until the end) in which one player opens one of the 5chains and the other player opens the other one?
wc

wccanard at 20070710
“Can there ever be a position in dots and boxes with two 5chains in, and an *optimal* play of the game from that position (i.e. both players play optimal moves at each stage until the end) in which one player opens one of the 5chains and the other player opens the other one?”
I've answered this now and unfortunately the answer is “yes”, which means that the question sheds no light on what I'm really interested in (can one mutate 5+5 to 6+4 without changing the value of the game). In fact there are even simple loony endgames (i.e. just isolated loops and chains) where control can change hands several times during an optimal play of the game. Consider for example the game 6+6+6+6+Q+Q (four disjoint 6chains and two quads). The controlled value of this game is 4 and so the value is 4, and player 1 can either open a 6chain or a quad (both moves are optimal) but if player 1 opens a 6chain then, because the value of 6+6+6+Q+Q is only 2, player 2 has the option of losing control whilst still playing optimally and if he does this then later on he'll open another 6chain—in fact in the position above control may even switch a second time: if the regions are opened in the order 6, quad, 6, 6, quad, 6 then on both moves 1 and 4 the controlling player has the option to switch.
wc

Carroll ★ at 20070710
Thanks for your nice example and your “yes” answer and I'm glad I did not post my “no” answer before…
G= 6 Q 6 6 Q 6
v= 4 2 6 4 2 6
now for
G= 5 Q 5 5 Q 5
v= 4 1 5 4 1 5
should the opening order be the same ?
or should you play:
G= Q Q 5 5 5 5
v= 0 4 8 7 6 5
or another order ?

wccanard at 20070711
@Carroll: Are you asking how to play 5Q55Q5?
Here's how I would work it out.
5+5+5+5+Q has controlled value 4 and hence value 4 [by a result stated in Berlekamp's book and proved in my notes, although it's not hard.]
Hence if player 1 opens a quad in the position 5+5+5+5+Q+Q, he will get as many boxes as player 2 (player 2 either accepts or declines the quad but the final score is the same), and this is clearly the best that player 1 can do.
So player 1 should open a quad—this is definitely an optimal move, and indeed his only optimal move because if he opens a 5chain then player 2 will score at least 3 more than him (because he takes 3 boxes before he has to make a decision).
In general, I proved by a brute force computer search that for simple loony endgames (i.e. just disjoint loops and long chains) with at most 50 boxes, if there is no 3chain then *one* optimal way to play is to open the smallest loop if there is one, and the smallest chain if not. This might be a general theorem for simple loony endgames.
There is a big difference between 6+6+6+6+Q+Q and 5+5+5+5+Q+Q; the controlled value of 6+6+6+6+Q+Q is greater than 1, so the value is the same as the controlled value and the correct way to play it is to always keep control unless player 1 “crashes the plane” in the language of BerlekampScott. In the example you wrote above (6Q66Q6) the value becomes 2, but it never gets as low as 1. If it gets as low as 1 then player 2 should lose control.
wc

Dvd Avins at 20070711
wccanard: I proved by a brute force computer search that for simple loony endgames (i.e. just disjoint loops and long chains) with at most 50 boxes, if there is no 3chain then *one* optimal way to play is to open the smallest loop if there is one, and the smallest chain if not.
Even if the smallest loop is at least 5 greater than the smallest chain?
I haven't read the book or anything else that lest me decipher your terminology with complete confidence, but if “open”, “chain”, “loop”, and “quad” mean what I think they do, and unless I'm otherwise confused,
 Opeining a chain of size n lets the other player retain control and return the position ot your turn with a net loss of n  4 (a negative number when n = 3) for yourself. (Or he could turn over control, handing you a loss of n in exchange for the control.)
 Opening a loop is the same, excpet that the net loss when the opponent retains control is n  8.
 A quad is simply a loop of size 4.

Carroll ★ at 20070711
Yes Dvd take the simple example of 3 + 9L (even if in standard D&B loops are even).
Opening order from left to right, value computed from right to left :
G= 3 9Lv= 8 9G= 9L 3v= 6 3player 2 will no keep control because he would give 4 in the loop to gain only 3 in the chain.

wccanard at 20070711
Dvd: if there is a very very large smallest loop and quite a small smallest chain then the intuitive move might be to open the chain but what is happening in practice is that by this point things have gone so badly wrong for the player not in control that it doesn't really matter what he does; his opponent will keep control whatever happens.
Here's another example on top of Carroll's: if there is a 4chain and a 10chain and a 100loop then it doesn't really matter what player 1 does; player 2 will keep control. The natural move is perhaps to open the 4chain but I'm asserting that opening the 100loop is no worse (in fact it's just the same). Let's say for the sake of argument that we do what you want and open the 4chain. After the 4chain is opened, player 2 will keep control (i.e. take 2 and leave 2), because he wants the big money (most if not all of the 100loop). Now there's a 10chain and a 100loop left, it's still player 1's move, and now in fact it's *definitely* better to open the loop than the chain, even though the chain is so short. The reason is that player 2's terminal bonus (the amount he gets on his last move when he is greedy and doesn't keep control but takes everything offered and finishes the game) will be less on the chain than on the loop. So with a 10chain and a 100loop the correct play for player 1 is to open the 100loop (and score 4 because player 2 will keep control) and then lose all of the 10chain, rather than opening the 10chain (where he'll only get 2 and then will lose all the 100loop).
Your assertions about my terminology are all correct, by the way. Did we unconfuse you yet?
wc

Dvd Avins at 20070711
Thank you, wccanard. Your post explained it well, even though I didn't understand Carroll's notation.

wccanard at 20070711
@dvd: I don't know an algorithm which *instantly* gives the value of a position, even a “simple loony” position (by which I mean just a disjoint collection of loops and long chains) (here a “long chain” is a chain of length 3 or more so you can do the allbuttwo trick, and a loop has length 4 or more so you can do the allbut4 trick). I know that the player not in control should be opening shorter loops rather than longer ones, and shorter chains rather than longer ones. But whether to open the shortest loop or the shortest chain in any given position can be a tricky problem, which seems best worked out by brute force in many cases.
On the other hand, if the players agree beforehand in what order they're going to open the loops and chains, but reserve the right to at each stage either take allbuttwo (or allbutfour in the loop case) or take the lot and lose control, then it's easy to work out the final scores. This is what Carroll is doing above. He's saying that if the players decide to open the 3chain then the 9loop then, working backwards, the 9loop is worth 9 so after opening the 3chain the player in control will take allbuttwo and win by 8. But if they decide to open the 9loop first then working backwards again the 3chain is only worth 3 so the player in control takes all of the 9loop when it's offered, rather than allbut4, because 4 is more than 3, giving him a net gain of only 6. So it's another, rather different, situation where player 1 should open the loop rather than the chain, even though the loop is much longer than the chain.
wc

wccanard at 20070729
*grumble* I am less sure that 5+5=6+4 but I still don't know the answer.
The reason I'm less sure is that I've found examples of games G such
that in G+4+6 opening the 4chain is an optimal move, but in G+5+5
opening a 5chain is not. The simplest example is just if G is a quad!
This doesn't prove that G+4+6 isn't the same as G+5+5 but it does prove
that the games sometimes “play differently”. It's not just because the numbers are small either—if G is 10 quads then G+40+42 and G+41+41 don't quite play the same either—opening the 40chain is a fine move in G+40+42 but opening a 41chain isn't in G+41+41; you lose two more boxes than you should.

wccanard at 20070805
*grin* I finally worked it out. It is true that 5+5=6+4; indeed 5+5=6+4=6.
More precisely, if you're playing a game of dots and boxes and there are two disjoint isolated 5chains in it, and if someone suddenly removed them and replaced them with a 6chain, then with best play the end result won't change, and, more precisely, with best play the differences between P1s score and P2s score will be the same in both games. Similarly if there's a completed isolated 6chain and a completed isolated 4chain then the value of the game doesn't change if you completely remove the 4chain.
So here's the proof that 5+5=6. It's a man in the middle argument. Imagine a game G and consider playing G+5+5 against one expert and G+6 against another. One of the experts will start one of the games, you will start the other one. The experts can choose which one will start. If I can show that I can always get at least 50 percent of the total number of boxes, this is a proof that G+5+5 and G+6 have the same value.
So here's the strategy; I'll only sketch it. If one player plays in G, I play the same move in G in the other game. If G completely finishes without the chains being touched, then one game has become 5+5 and the other has become 6, and both of these games have value 6, so I have got 50 percent of the boxes.
The big question is: what happens if someone opens a chain. If one of the experts opens one of the 5chains, I take 3 and give 2 back; I'm now one up and the worst that can happen is that the expert will later on open the other 5chain and I'll open the 6chain in the other game, losing one box in this exchange, and end up equal. So I'm still OK.
The last part of the argument is the most delicate. What happens if one expert opens the 6chain. What do I do in the other game? Here's the idea. If one expert has opened a 6chain in the game G+6 then we know that G+6 must be worth at least 4 points to me, because I take 4 boxes before deciding what to do next, and one of the two options open to me (take all 6, or leave 2) will give me half the remaining boxes. So G+6 must have value at least 4. So by a simple maninthemiddle argument which I'll omit, G+5 must have value at least 3. This means that if I open a 5chain in G+5+5, my opponent's best move is to take all but two, so he does this, I'm 1 up, and I then open the second 5chain and go back to copying, and lo and behold if you add it all up I still have half the total number of boxes.
This argument is the inductive step in
Theorem: in a position with a whole bunch of disjoint isolated chains of lengths a,b,c,…, all at least 4, the value of the game is unchanged if I replace all these chains with one long chain of length 4+(a4)+(b4)+…
The reason all those 4s are in the statement is because if you take all but two of an achain, your net gain is a4.
wc

wccanard at 20071214
I finally got to the bottom of this 5+5=6 business, and I wrote it up in a revised version of my notes, which I'll put up on my dots wiki after I've proofread it this evening.
This post is an attempt to reconcile my last two posts! Let G be any game. Say a move in a game is “optimal” if it's not a mistake, that is, it's one of the best moves available (there may be many optimal moves in a gives position). The value v(G) of a game G is (P2's score)  (P1's score) assuming the game is played optimally.
Here's what is true:
(i) v(G+5+5)=v(G+6), for any G
(ii) A move g in G is optimal in G+5+5 if and only if it is optimal in G+6
(iii) If opening the 6chain in G+6 is optimal, then opening a 5chain in G+5+5 is optimal.
(iv) There are examples of games G where opening a 5chain in G+5+5 is optimal but opening a 6chain in G+6 is not optimal.
An example of G for (iv) is a 1chain plus that “awkward 3x2”, the same one showing up in the example of the position posted recently in another thread where opening a 3chain is right but opening a 1chain is wrong. The point about the “awkward 3x2” is that after a premature sacrifice and subsequent chain threat, the controlling player finds himself 41 down. But for this to work there has to be another chain around, or else the premature sacrifice isn't premature enough.
I've said some more about these things in my soontoappear new version of my notes. Of course this has nothing to do with 5 and 6, the general result has any number of chains of length 4 or more replaced with one superlong chain of the appropriate length, as explained in my previous post in this thread.
wcc