5+5=6+4? Dots and Boxes

16 replies. Last post: 2007-12-14

5+5=6+4?
• wccanard at 2007-07-03

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 5-chains (and a bunch of other stuff) and when neither player is looking, someone changes the board slightly so that one 5-chain becomes a 6-chain and the other becomes a 4-chain, 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 4-chain 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 40-chain, 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 cut-off 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 2007-07-03

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+5-3\|=\|G+2+6-2\| or

1+\|G+2+5\|=\|G+2+6\| with a game G loony.

Is it flawed or simpler ?

• Carroll ★ at 2007-07-03

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 \|{G1-n,G2-m…,Gi-z}\| 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+5-3}\|

where

\|G+4+6\| = \|{G1+4+6,…,Gi+4+6,G+2+6-2}\|

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+5-3\|=\|G+2+6-2\| or

1+\|G+2+5\|=\|G+2+6\| with a game G loony.

Is it flawed or simpler ?

• wccanard at 2007-07-03

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 4-chain at some point. I then have to open the 5-chain 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 5-chain? Then I open the 6-chain 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 2007-07-07

Carroll said:

“all you have to prove now (or disprove) is that \|G+2+5-3\|=\|G+2+6-2\| 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 5-chain) is either \|H+6\|+1

or \|H+6\|-1 (use a man-in-the 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 5-chains 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 5-chains and the other player opens the other one?

wc

• wccanard at 2007-07-10

“Can there ever be a position in dots and boxes with two 5-chains 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 5-chains 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 6-chains and two quads). The controlled value of this game is 4 and so the value is 4, and player 1 can either open a 6-chain or a quad (both moves are optimal) but if player 1 opens a 6-chain 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 6-chain—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 2007-07-10

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 2007-07-11

@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 5-chain 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 3-chain 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 Berlekamp-Scott. 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 2007-07-11

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 3-chain 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 2007-07-11

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 2007-07-11

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 4-chain and a 10-chain and a 100-loop then it doesn't really matter what player 1 does; player 2 will keep control. The natural move is perhaps to open the 4-chain but I'm asserting that opening the 100-loop 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 4-chain. After the 4-chain 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 100-loop). Now there's a 10-chain and a 100-loop 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 10-chain and a 100-loop the correct play for player 1 is to open the 100-loop (and score 4 because player 2 will keep control) and then lose all of the 10-chain, rather than opening the 10-chain (where he'll only get 2 and then will lose all the 100-loop).

Your assertions about my terminology are all correct, by the way. Did we unconfuse you yet?

wc

• Dvd Avins at 2007-07-11

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

• wccanard at 2007-07-11

@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 all-but-two trick, and a loop has length 4 or more so you can do the all-but-4 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 all-but-two (or all-but-four 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 3-chain then the 9-loop then, working backwards, the 9-loop is worth 9 so after opening the 3-chain the player in control will take all-but-two and win by 8. But if they decide to open the 9-loop first then working backwards again the 3-chain is only worth 3 so the player in control takes all of the 9-loop when it's offered, rather than all-but-4, 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 2007-07-29

*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 4-chain is an optimal move, but in G+5+5

opening a 5-chain 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 40-chain is a fine move in G+40+42 but opening a 41-chain isn't in G+41+41; you lose two more boxes than you should.

• wccanard at 2007-08-05

*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 5-chains in it, and if someone suddenly removed them and replaced them with a 6-chain, 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 6-chain and a completed isolated 4-chain then the value of the game doesn't change if you completely remove the 4-chain.

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 5-chains, 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 5-chain and I'll open the 6-chain 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 6-chain. What do I do in the other game? Here's the idea. If one expert has opened a 6-chain 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 man-in-the-middle argument which I'll omit, G+5 must have value at least 3. This means that if I open a 5-chain 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 5-chain 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+(a-4)+(b-4)+…

The reason all those 4s are in the statement is because if you take all but two of an a-chain, your net gain is a-4.

wc

• wccanard at 2007-12-14

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 6-chain in G+6 is optimal, then opening a 5-chain in G+5+5 is optimal.

(iv) There are examples of games G where opening a 5-chain in G+5+5 is optimal but opening a 6-chain in G+6 is not optimal.

An example of G for (iv) is a 1-chain plus that “awkward 3x2”, the same one showing up in the example of the position posted recently in another thread where opening a 3-chain is right but opening a 1-chain is wrong. The point about the “awkward 3x2” is that after a premature sacrifice and subsequent chain threat, the controlling player finds himself 4-1 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 soon-to-appear 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 super-long chain of the appropriate length, as explained in my previous post in this thread.

wcc