Strategy for experts Dots and Boxes
59 replies. Last post: 20070614
Reply to this topic Return to forum
sam_nead at 20070401
Would some of the masters (2000 and up) please discuss opening and midgame strategy, with a view towards assisting the midlevel players (18001999)?
Thank you.

Carroll ★ at 20070402
Yes thanks Sam, it would be very interesting for the emerging players (1650+) too!
But is there really a theory of openings in D&B? I never came accross any reference except on 5x5.

wccanard at 20070608
I'm not sure I'm a “master”; I don't have too much experience on a 5x5
(meaning 5 boxes by 5 boxes, so 6x6 dots) board, but I am currently
rated just over 2000 so I'll make some comments about what I know
about dots and boxes—stuff that (AFAIK) isn't easy to find elsewhere,
and I'll make them quick before I drop back down below 2000 :). I hope at
least that my postings provoke some responses and comments.
For simplicity I'll divide my post up into bits. I should issue a general
warning: any comment I make of the form “x is true” is, hopefully, true
(in the sense that I think I can prove it, or I read it in Berlekamp).
But any comment of the
form “In my experience it's helpful to know x” might be wrong or
misguided because I've only been playing here a few weeks (and indeed I've
only been playing 5x5 for a few weeks) and a lot
of my games have been against people rated under 1600—in particular
I have very little experience indeed playing other players rated 2000+
so in some sense I know very little about how to play against them.
I should perhaps also say that I've got much more experience playing
on a 7x7 (i.e. 8x8 dots) board, at Richard's PBEM server (google it
to find it—it's an emailbased server; my userid there is buzzard).
Dots and boxes on a 7x7 board is much much much closer to nimstring than
on a 5x5 board. On a 7x7 board if you win the chain battle you've
essentially always won the game because the board is so big and there
are bound to be huge chains, so the game is almost always about sacrificing
to win the chain battle and that's it—the skill there is knowing how
to compute nimvalues of very complicated positions (possibly using
the theory of vines developed in Winning Ways—a skill that has proved
useless here!). If I make some statements below that people think are
inaccurate, this might be the source of my confusion.
wc.

wccanard at 20070608
1) Books and papers.
Conway, Berlekamp and Guy wrote a wonderful book about games called
“Winning Ways”. This was where I learnt how to play dots and boxes
(Chapter 16 covers dots and boxes, but you don't have to have read
the first 15 chapters to follow it). I cannot recommend Winning Ways enough.
Berlekamp also wrote a book called “The dots and boxes game
(sophisticated childs play)“, part of which is just copied verbatim
from Winning Ways (presumably he got away with this because he
was one of the authors of Winning Ways!). Both of these books contain
material that the other doesn't have. Both of these books also contain
a lot of material that is not available on the web. I guess one advantage
of Berlekamp's book is that it also attempts to explain the bits of the earlier
chapters of Winning Ways that you needed to know in order to read chapter 16,
but this is not really much. For me at least, reading and understanding
every last sentence in Chapter 16 of WW and Berlekamp's book was a big
target and trying to do this whilst playing at the PBEM server and here taught
me a lot. I still have not convinced myself of every assertion that
Berlekamp makes in his book—I'm certainly not saying he is wrong,
I just must have more things to learn.
One word of warning: some of the stuff that is talked about in these
books applies only to dots and boxes games played on other sized
boards—for example Winning Ways talks a lot about strategies for
the 2x2 and 3x3 boards, and some of the general theory only really
applies when the board is large (for example the results about
computing nimvalues of large vines doesn't seem to be of any use
at all for the 5x5 game, but really comes into its own by the time
you reach 7x7).
As well as those books there appears to be a 2000 UCBerkeley MSc thesis by
Katherine Scott which I have not yet seen (I would love to get
a copy!) and my guess is that some of the results in here will be
relevant to the 5x5 board. Scott makes a detailed analysis of some
dots and boxes endgames. I have proved some small results myself
about endgames but I strongly suspect that everything I've worked out
will be in Scott's thesis. If anyone from UCB is reading this, I bet
it would be easy to get your hands on this thesis. You could tell me
what was in it if you did!
There is also a paper by Berlekamp and Scott which makes some beautiful
observations about endgame play, but the theory developed there
only really applies on large boards again.
Now here comes a big caveat: I am not going to type in everything it
says in these books! If you really want to know what is in these
books I'm going to assume you are going to go and get your hands
on them. In particular, I will *sometimes* assume familiarity with the
basic concepts in these books (e.g. why a chain of length 3 is very very
different to a chain of length 2, what nimstring is and why it matters,
the two options you have when your opponent opens a long loop or chain,
and so on).

wccanard at 20070608
2) Nim.
Perhaps what separates the 1500+ players from the 1500 players is the
fact that the 1500+ players have realised that it's frequently all about parity
of long chains. On a 5x5 board player 1 is going for an even number of long
chains (that is, chains of length at least three), and player 2 is going
for an odd number. I guess there's a mild
caveat—player 1 probably doesn't want 0 long chains because then he
will probably lose anyway, but the chances of getting 0 long chains on
a “normallyplayed” 5x5 board are slim, in my experience at least.
The theory of nim, as explained in WW and Berlekamp's book, provides
a more robust way of getting the chain count right. For some games
of dots and boxes you don't need to know anything about nimvalues
of dots positions, but sometimes it is absolutely essential because
the theory of nim helps you get the timing just right when you're
in the middle of a very chainy position and are trying to get the
undecided regions resolved in your favour at just the right time.
My feeling is that it's hence essential to know how the theory applies
but Eugene Ventimiglia tells me that there is apparently very little about it
on the web in terms of simple articles explaining the basics
of how it works and how to compute nimvalues in practice.
As well as knowing how to compute nimvalues of simple positions,
I realised very quickly after arriving here and losing my first few
games that there are positions which are just a little too big to analyse
by hand (in terms of computing the nimvalue) but which come up
again and again and again. Explicit examples of this are the 2x3 and
the 3x3 icelandic corners, which seem to show up far more often
than they should! A “2x3 icelandic corner” is the following: make
a small rectangular board containing 2x3 boxes (i.e. 3x4 dots)
and then wall off the top and right hand side of it (i.e. draw
in 5 lines). It's a pain to compute by hand but the nimvalue of this
is 2, which means that the first player can bring the value down to
zero with one move. And after he has done that we have 6 boxes
and 11 lines still to play, and 6+11=17 which is odd, so this
means that the first player can force an odd number of chains
in this region (possibly after sacrificing). It turns out that
the first player can also force an even number of chains in
this position but, as aldiris pointed out to me, he might have to
sacrifice 5 boxes in doing so!
The 3x3 icelandic corner has nimvalue 0, which means in this case
that the second player can force the value to stay there, and if he
does this then there will be an odd number of long chains (almost
certainly 1) because the corner has 9+18=27 boxes+lines which is odd.
I don't know exactly how well the first player can do if he wants
to minimise the length of the chain in this region.
In short, nim is essential for winning chain battles and some, but not
all, games of dots and boxes are won in the chain battle stage, so learn
nim and how it applies to dots and boxes. But if you ask me “how” I'll
say “read a book” because to really learn it properly, in my experience
anyway, you really need to see a host of examples. Both the books
I mentioned do a complete analysis of the 2x2 icelandic corner (which
has nimvalue 2, by the way) and knowing or having access to this
analysis is very helpful sometimes. Anyone out there want to write
an accessible explanation of nimstring for nonexperts?

wccanard at 20070608
3) The preemptive sacrifice.
So, you're playing someone better than you, and you realise to your dismay
around move 16 that you have lost the chain battle :( You're player 1,
you wanted two long chains, but darn it, there are now three long
chains on the board, one at the top, one in the middle, and one at
the bottom (recall “long chain” means “at least 3”), there is no room
for getting a 4th chain in, and you're in trouble.
Or are you? Well, if those three chains have length 6, 7, and 8, then the
answer is “yes”. Even if you win the other 4 boxes then you'll have
to open the three chains, and your opponent will play the allbuttwo
trick on you the first two times, and then take the lot the 3rd time,
and you will only end up with 8 boxes in total.
But if the chains *currently* have lengths 3, 3, and 4, and they're
going to grow longer if you keep playing, and *IF YOU ARE ALREADY
A BIT AHEAD IN TERMS OF BOXES ALREADY CAPTURED*, then you might want to
consider opening some of those long chains right now before they get
any longer! If you don't then your opponent is going to spend all of the
rest of the game either countering minithreats of yours (when you try and
make a 4th long chain and he spoils it typically by sacrificing a box
or two) or just making those long chains even longer, because he knows
that those chains are his to keep. So give him them now before they
get too long.
*BUT*, and this is a big but, you have to be careful. Let's say
that no boxes have yet been taken and there are three chains of
lengths 3, 3, and 4, and a few short chains and no space for a 4th long
chain. If player 1 (the loser of the chain battle) opens a 3chain,
he is *guaranteed* to lose! Why? Because player 2 doesn't *have* to
do the allbuttwo trick. He can choose whichever option he prefers;
if he thinks that your premature sacrifice is a superstrong move, putting
you in a winning position if he takes all but two, he might
decide to “become you” by taking *all* the boxes you offered him,
instantly becoming several boxes richer, and then happily being
the loser of the chain battle and the winner of the game.
The rule of thumb is: if n is greater or equal to 3, and you
are *not* at least n1 boxes ahead, then opening a chain of length n
is always a losing move (in a dots and boxes game with an odd number
of boxes, at least). Similarly if you open an isolated loop of size n
you had better be at least n3 ahead. The proofs of these assertions
are simple strategystealing arguments and are nonconstructive, but
don't underestimate how much time I'm prepared to stare at a position
if I *know* I have a winning move :)
Because of that caveat, you have to make sure you're a long way ahead
before you start making premature sacrifices. Attempt to do this
by trying to force a small 4th chain somewhere—your opponent might
have to sacrifice a box or two to stop you.
The other side of the coin: if you know you have won the chain battle
then concentrate on making those chains longer! Every extra box you
add to a chain is a box that will be yours in the final count.
Footnote (for experts only, perhaps): Having said all that,
here's a funny paradox which I've never quite understood. Imagine
you are 5 boxes up but we're in the endgame, it's your move, and all that
is left is a 2chain and a nearlycompleted
6chain—i.e. (in nimstring language) draw a 6chain and then
a second string from one of the ends of the chain to the ground.
The nimvalue of that position is 1 so you have lost the chain battle.
If you have read the above then you might think “preemptive sac!“.
This loses by 1; your opponent takes all 5 boxes offered and then wins
the short chain endgame and you lose by 1. So start again. Your next
thought might be “don't lengthen the chain!“. So you open the 2chain
and this is even worse—your opponent takes all eight boxes and you
lose by 3. The unique winning move, even though you are losing the chain
battle, is to lengthen your opponents chain :) (assuming I got this
calculation right—something like this could have actually happened
in a game I played against Loic Boisnier, someone who has taught me
a great deal about dots and boxes by simply being prepared to play
against me a lot).

wccanard at 20070608
4) Openings.
The original poster asked about openings. A followup poster said
that they had only seen opening theory on the 5x5 board (by which I assume
they mean 5x5 dots, i.e. 4x4 boxes). Let me stick to my conventions
and call this a 4x4 board. The thing about the 4x4 board is that it
has been completely solved (by David Wilson, as far as I know, and
perhaps now also by others). With best play it is a draw and, as it turns
out, *any* move by the first player is optimal (in the sense that
with best play after an arbitrary first move it's still a draw). On the
3x3 board the score with best play is 63 to player 2 and again,
if I remember correctly at least, all moves by the first player
are equally good/bad in the sense that the score will still be 63
after an arbitrary move by the first player and perfect play thereafter.
Similarly on the 3x5 board with best play it's 87 to the 2nd player
and again all moves for player 1 are equally good/bad.
So one might *guess* that the same sort of thing is true on a 5x5 board.
The 5x5 board is too big to analyse completely at the minute (unless someone
comes up with a clever new algorithm) and this is why you can find “standard”
4x4 openings but nothing in the 5x5 case—in the 4x4 case you can really
write down the “correct” lines which lead to the draw and you can say
if certain moves are mistakes. For 5x5 we're not yet there. Take a look
at some games played in the top championships—experts start in the
middle, at the edge, everywhere. I get the feeling that there is no
real consensus, even about move 1.
On the other hand, even if there are no standard opening lines,
there seem to be general opening principles, well, I have formulated
some and I guess they're currently undergoing rigorous testing here :)
So let me try to explain what little I know about these principles.
I should say that these principles are really just my own thoughts
and I've yet to play enough 5x5 to see if they are really worth
recording. The overlying idea is: you know which player you are.
So you know how many chains you want. A small region like 2x2 might well
not turn into a chain. But a 3x2 region might well, and a 3x3 region
almost certainly will. Let's call a region “small” if it looks like
no chains will form there, “large” if it looks like one chain will form,
and “too large” if it's still a real possibility that more than one
chain will form there. Why not try and divide the board
up into large and small regions, such that the number of large regions
is the parity you want? Sometimes I play players rated 1500 and after
about 10 moves I realise I've almost surely won the game because the
board already has the right feeling: e.g. I'm player 1 and the board has
two large regions and the rest small—so I'm probably going to make two chains
without having to sacrifice anything and this is a very good start.
Be careful to distinguish “large” from “too large”
though—you only want 1 chain there, not 2.
For example after 0 moves the board definitely is not “one large region”!
It's “one toolarge region” about which we still can't say anything.
That's unfortunately all I know about openings :/
Oh—I guess there is one more thing: there is a trap. Try not to end up as
player 1 in a game with 180 degree rotational symmetry and with a chain of
length 3 or more going through the centre box. If this happens then as far
as I can see you're now in big trouble because player 2 can just copy
your moves with 180 degree
rotation and you'll be forced to make the first loony move with the
scores level, and if you do this then you will provably lose. On the other
hand if the position is symmetric and there is no long chain in the
centre then great! Make 1 long chain, hope that player 2 copies you
and makes another one, and then just sacrifice the central box and you've
won the chain battle: now just copy your opponent :)

wccanard at 20070608
5) Endgames.
By “endgame” I mean when the chain battle is won, when the chains have
grown to their full length, and when the sacrificing begins. On each
turn a player has to make the 3rd side of a box and his opponent will
surely take it on his turn and perhaps pick up some more as well, before
drawing in the 3rd side of another box, and so on.
The general mathematical theory of endgames is very very delicate.
Nimstring has nothing to do with this now; we know who will get
the long chains and the question is: is this enough to win the game.
It sometimes is and it sometimes isn't. In games with e.g. a chain
containing 13 boxes, the player who has won the chain battle will
get this chain and win the game and so really the game was over a long
time ago and was won with nimstring. On the other hand, if there are just
some 3chains around, and perhaps also some quads (4loops)
or 6loops, then the winner of the chain battle might find himself
only gaining a point or two, and he might have sacrificed more to
win the chain battle, so he may well be in trouble.
The bottom line, I've found, is that you want a simple way to analyse
endgames of this nature. One way is to try and make a huge treelike
analysis of every move and response. This would take forever in a complicated
position. One can do better. There are some basic principles, including
one which Berlekamp asserts and which I can't prove. Let me get that
one out of the way first.
*) Never open an isolated long chain if you can open an isolated short
chain instead.
I don't know why this is true. It might well be proved in Scott's MSc thesis.
Here are some I do understand.
*) If you're going to open a short chain, then choose a 1chain over a 2chain.
*) If you're going to open a long chain, then choose the shortest long
chain possible (i.e. open the 3chain rather than the 4chain).
The proofs of those two assertions are simple maninthemiddle arguments.
Berlekamp explains “maninthemiddle” in his book but never really
explains what it's used for. The principle is that if I'm playing two
chess experts and I'm white on 1 board and black on the other, i can
ensure at least 1 point out of 2 by just copying moves: I wait for
the expert who is white to play, and I copy the move on the other board,
and then copy the response, and so on. The proof of (open a 4chain
rather than a 3chain) now goes like this: you set up
two dots positions, you force expert 1 to start by opening the 4chain,
and you instead open the 3chain against expert 2. Now play out the games,
assuming that experts 1 and 2 are now playing optimally, and copy as much
as you can, and doing the sensible “nearcopying” alternative if you can't
copy exactly. You'll see that you always get at least 50 percent of the
boxes and sometimes more!
While I'm here I should say that a similar maninthemiddle argument
shows that two 1chains cancel: if there are two 1chains on the board
then you may as well assume that one player gets one of them and the
other player gets the other. So in your analysis you can just cross
these chains out. Similarly two 2chains cancel.
This is wonderful: we know how to play chainy endgames now. Imagine a
position which has decomposed into a disjoint
union of chains: three 1chains, three 2chains, four 3chains and a 4chain,
say. We now know that under optimal play the chains will get opened in order:
1,1,1,2,2,2,3,3,3,3,4. But that's not the end of the story! When we get
to the long chains we'll have to work out whether the person offered the
chain takes all of it, or allbuttwo. Let's see how this pans out.
Let's do the short chains first. The next player to play (call him Red)
will open a 1chain, which will be taken and promptly given back to him
via the second 1chain by the second player (call him Blue). We go through
the 1chains and the 2chains like this and we see that Blue is now one box
down, but he has control. Note that this (the controlling player losing
out on the short chains) is a general phenomenon: if you have won
the long chain battle, you will never win the short chain battle and this
battle might even cost you 2 boxes (if there is an odd number of 2chains
and an even number of 1chains), so the winner of the long chain battle
had better take this into account.
Now it's Red's turn, he's one box up, and he's faced with long chains
of lengths 3, 3, 3, 3 and 4. He's going to have to make a loony move.
But he is winning by 1 so he figures that the loony move *might* not be
the end of the world for him! Actually, a bit of thought and a
strategystealing argument tells you that it *is* the end of the world, but
now the issue becomes how to actually play the endgame, not abstract
results about who should win with best play—we want to see how to
play the game now. The principle I explained above says that
red should open a 3chain. Now should blue take all the boxes offered
or all but 2? This is not immediately obvious! (to me at least). Blue can
work it out by working backwards
from the end. Imagine the last but one move of the game: someone will open
the 4chain, the last chain, and it will be snapped up by his opponent.
So v(4), the game consisting of a 4chain, is 4 (i.e. a net gain of 4 boxes
for the player in control). Now go back a move. When someone opens the
last 3chain, will his opponent accept all 3 boxes? Well no, because
there's no point taking those last two boxes if you stand to lose all
the 4chain, so the 3chain will be politely declined and v(3+4)=3,
the optimal play being player 1 opening the 3chain and player 2 taking
all but two of it, so he's one down but the 4chain will be his.
Similarly v(3+3+4)=2 because if the game 3+4 is worth 3 then you should
sacrifice 2 to get at it.
Now v(3+3+3+4)=1. This is because when the 3chain is opened, the other
guy takes the first box and then he has to decide whether to sacrifice
2 in order to get the benefits of the game 3+3+4, and this game is
only worth 2, so it doesn't matter what he does, he'll just win by
the one box he just got.
Finally, v(3+3+3+3+4)=2 again! This is because v(3+3+3+4) was so small,
only worth 1, so when the first 3chain is opened, the guy who can take
the resulting boxes is going to take them! Why sacrifice 2 to only gain 1?
So we finally see that blue is going to win, by 1 box: red is currently
1 box up but his
best move is to open a 3chain and blue will grab them all and open
the next 3chain. It doesn't matter if red accepts or declines;
but after that decision the player in control will always stay in control,
and blue will win by 1.
One can analyse loopy endgames in the same way. After the short chain
battle it's always best to open the loops shortest first.
This section has been long so I'm going to draw it to a close with a
question. In general, even a simple endgame may be a disjoint union
of loops and chains, and after the short chains have gone
you have to decide whether to open the shortest long loop or the shortest
long chain. I know of no algorithm to decide what to do, short of
working out the entire recursive tree in each case [fortunately this
is not too hard because at each point you know that the optimal move
is either opening the shortest chain or the shortest loop]. The most disturbing
example I know is the following. In the game 3+3+3+4L (a disjoint
union of three 3chains and a 4loop) the value of the game is 1,
the controlled value is 1 for those of you that know about controlled
values (see Berlekamp's book), and the only optimal move is opening
a 3chain. However in the game 3+3+3+4L+8L, the value is still 1,
the controlled value is still 1, the game looks essentially the same as
the other one, as an 8loop is basically worth nothing, but the only optimal
move is opening the 4loop. All this is based on my calculations so it
might be wrong! Someone should check for me ;) When I found this
example I became convinced that I would never find a simple algorithm for
determining whether to play the shortest loop or the shortest chain (short
of grinding out the tree), even
in the simple alldisjointchainsandloops endgames which come up
so frequently on the 5x5 board.

wccanard at 20070608
6) Outro.
I hope that the comments here stimulate some discussion—and I would be
happy to hear of any errors or typos.
I have learnt a lot in my few weeks here and my thoughts above have
mostly been formulated after playing interesting games with you guys,
so thanks. Let me say particular thanks
to Trevor Green who (a) answered some basic questions I had about the
server when I first appeared here and (b) then proceeded to beat me
in my first ever game here, by letting me win the short chain battle
and winning the dots game anyway. It was only after that game that
I realised that the 5x5 game was very different to the 7x7 game, and
the game I played with him really motivated me into thinking about
how to play endgames on the 5x5 board, something that had never
really mattered on the 7x7 board.
wc.

aldiris at 20070611
Very nice read, although I knew most of it :)
I'll translate this text to Dutch somewhere this week, btw :)

sam_nead at 20070612
A very nice sequence of posts. It would be lovely if the other masters (and dare we hope, grandmasters) would also record their observations.
That said, I will contribute an answer to the “paradox” posed in part 3: WC asks “Suppose the score is 116 with the first player to move. All that remains on the board is a completed two chain and a six chain with one free move left. What should the first player do?”
WC worked out the correct answer by brute force: it is not too hard as there are only four moves to consider.
1. Making a loony move in the twochain.
2. Making a loony move in the “almost sixchain”.
3. Sacrificing the twochain.
4. Making the free move.
Move 1 is always bad – WC didn't even consider it. I'll try to explain why in a later post.
Let see if nimstring helps us: the twochain has one free move (move 3) and two “loony moves” (move 1). Nimstring ignores loony moves, so the twochain is a *1. Likewise the almost sixchain has one free move and 6 loony moves. So it is also *1. So the entire game is *1 + *1 = 0 and we (the first player) are out of control. Thus the second player has won the chain fight and is guaranteed at least 5 more boxes in the end game. (So in some sense, even though the score is 116 the game is actually tied. Whoever gets the twochain will win.)
WC suggests that move two is reasonable – after all, we don't want the second player's five box guaranteed payoff to grow to six boxes. This is is correct approach in the midgame – “If you are rich and out of control, go loony!” However, that doesn't work here. The reason why is that in the end game there are short chains and long chain, and loops. The player who is in control will get at least half of all the boxes in the long chains and loops. As a compensation the outofcontrol player will get the last of the short chains. Generally the outofcontrol player will get either zero, one, or two more boxes from the short chains than the controlling player does.
It follows that if we just lengthen the sixchain we have a guaranteed win: we get the last of the short chains and that gives us the twochain. So really there is no need to think further. However, we haven't yet answered the question: why is move 2 bad? Well, if we start the chain we are giving the second player a choice. EIther he can take all of the fivechain or he can decline the last two. If he takes all of the boxes he is _forcing_ us to take control: now there are zero chains! So he is out of control and will get the last of the short chains! That is, he gets the twochain, not us, and he wins. (Of course, if he doesn't take the last two boxes of the five chain then he keeps control and we get four more boxes, not just two. This is obviously very bad for him!)
So the rule of thumb is: if there cannot be any more chains or chain threats then the outofcontrol player cannot preemptively open the final chain.

sam_nead at 20070612
What I would really like to see is a discussion of the “halfquad”. This seems to come up all the time in expert games and never come up in say 1900 games. By “halfquad” I mean a quad which has two opposite corners walled off and the remaining two corners are open.
I suppose that there is a rule of thumb here: “halfquads tend to even the score”. If you are going to be out of control then make the “correct” number of quads – this insures that you get nearly half of the boxes in the long chains and loops _and_ you get the last of the short stuff. Conversely, if you are going to be in control then you face the painful prospect of sacking a box (out of four) in order to get a threechain….
Here is an easy exercise: If all that is left is 4L+4L+5+7 how many points do each of the players get? (That 7 chain sure looks good, doesn't it!)

sam_nead at 20070612
Crud. I already said something wrong. “If there cannot be any more chains or chain threats then the outofcontrol player cannot preemptively open the final chain.”
In fact, if the short stuff is balanced and there is only one long chain then it cannot hurt the outofcontrol player to preemptively open the long chain. In fact, if there are free moves available at both ends of the long chain then it definitely helps to preempt!
I suppose the correct rule of thumb is “The out of control player gets the last of the short stuff.” All of these other situations can be analysed using that rule.
Ok, I'll stop talking now.

wccanard at 20070613
I'll respond to some of sam's comments.
sam_nead: “I will contribute an answer to the “paradox” posed in part 3”
Thanks for the comments. The reason I got so “confused” by this situation is exactly the comment I made early on in my post—I have oodles of experience on a 7x7 board but very little on a 5x5 board, and on a 7x7 board this issue doesn't really arise in practice: the winner of the chain battle essentially always wins big in the dots game.
sam_nead: “Move 1 is always bad – WC didn't even consider it.”
This was with reference to a loony move in a 2chain. I didn't consider it because in some sense I didn't even notice it! Because a loony move in a 2chain gives your opponent strictly more options than the corresponding nonloony move, the “modified” game of dots and boxes where loony moves in 2chains are *illegal* is, from a game theory point of view, the same as normal dots and boxes, and I think that I must play the modified game in my head. Similar “illegal” moves in my head are: loony moves when you're not ahead, and opening big isolated chains/loops when there are smaller isolated chains/loops around. It doesn't mean that these moves are bad—indeed I may be ruling out winning moves—but I know that for each move I'm ruling out there is another that is at least as good. Readers of Berlekamp will know that I'm just trying to be a “canonical guru”.
sam_nead: “What I would really like to see is a discussion of the “halfquad”.”
This wouldn't be because of your supercomplicated game with Scot at all, would it? :)
sam_nead: “I suppose that there is a rule of thumb here: “halfquads tend to even the score””
Quads tend to even the score too, I guess. I didn't talk about quads at all—through lack of time mostly, and perhaps also because the quad is an animal that I've only recently come to terms with.
sam_nead “Crud. I already said something wrong.”
Yeah, the inability to edit posts here isn't so great, is it :) I would also like to make at least one minor change in the stuff I wrote above but don't think I can (when talking about the “paradox” I said “this has nimstring value 1”, a sentence which was at best ambiguous and at worst wrong; you have now done the nimanalysis of the position though so I'm less worried).
Your comments have got me thinking more about the preemptive sacrifice. So far we have two examples of positions with 1 long chain: a nearlycompleted 6=chain plus a 2chain, where we know that it's best not to preemptively sacrifice, and a twomovesawayfromcompletion 6chain (with one string of “extra grounding” at both ends), where it *is* best to preemptively sacrifice. On the other hand, in practice what do we seek here? We seek *practical algorithms for playing*, right? We want to be able to look at a position and then analyse it correctly using pen and paper. When there is only one chain left it's easy to analyse all possibilities, so in some sense there is no longer any need for rules. So here's a question: if I have lost control, the number of long chains has been completely resolved and there are, say, three long chains, then is the best move always to preemptively open the shortest? Somehow I would be surprised if things were so simple! Can you construct a counterexample?
Here's how I answer your exercise, Sam. Firstly I invoke
Theorem: in a loony dots and boxes endgame which is entirely isolated long chains and loops, if there are at most 25 boxes in the position and no 3chains then an optimal move is to open the shortest loop if there is a loop, and to open the shortest chain if not.
Proof: brute force computer search (didn't take long!). I don't know if the result is true in general. It might be—I'll try to remember to think about it.
Hence I know that one of the optimal ways to play your endgame above is first to open both quads, and then the 5chain and the 7chain. Now one can work backwards to compute the value of the position.
wc

Carroll ★ at 20070613
Thanks both for your enlighting posts.
open both quads, and then the 5chain and the 7chain
Subsidiary : then will player 2 accept or decline the two quads? :)
What is the rule of thumb for similar cases?

wccanard at 20070613
Whether to accept or decline the quad is the thing you find out at the very end of the calculation! As far as I know, you have to compute the values of the intermediate games; once you do this, you of course know what to do: you accept a quad if the value of what is left is less than 4, decline it if it's bigger, and do either if it's 4. But I don't know a rule of thumb and wonder if there is one.
More precisely: if the controlled value of the game is huge then of course the value is huge so you decline everything. The moment the controlled value becomes small, or even negative, the value is typically then also small (I checked by computer that for these simple loony endgames with only isolated chains and loops, and at most 25 boxes, if the controlled value was negative then the value was at most 4), but even in this situation the value can be as much as 4, so if your opponent opens a 3chain and the controlled value of the position with the 3chain removed is negative then I don't know a rule of thumb—I just explicitly work out the value of the position by analysing the tree.
Here's an example: in the position 3+4+4L+4L (isolated 3chain, isolated 4chain, two quads) the value is 3, the controlled value is 5, and the player not in control can open either the 3chain or a quad (both moves are optimal). If the 3chain is opened then the controlling player should keep control but if the quad is opened then the controlling player should lose control.
As you might be able to guess, I have written a short program to analyse these simple loony endgames, so if anyone has conjectures about how to play them, I can test them easily. I tried a few sample conjectures but nothing worked.
The main fault with my theorem above is that it doesn't say what to do if there are 3chains. The explicit examples I posted above (3+3+3+4L and 3+3+3+4L+8L)
were enough to convince me that finding “rules of thumb” to completely play these simply loony endings on autopilot might be hard. On the other hand, Berlekamp's observation that if you're going to open a loop/chain then it should be the shortest, at least pulls the analysis down to something which you can easily do in a few lines with pen and paper. So as far as I am concerned, how to play these simple (i.e. all chains are isolated) loony endgames is “a solved problem”, in the sense that on a 5x5 board I can analyse them easily using pen and paper only. Berlekamp and Scott analyse far more exotic loony endgames though, where they allow quads connected by long chains for example; here things are more subtle and I've not even begun to think about them. The reason things are harder is that basically you're forced to play the chain before the loop.
wc

wccanard at 20070613
Carroll: I do know a rule of thumb for loony endgame positions that *only* contain long loops. The rule of thumb for positions containing only long *chains* is given (without proof) in Winning Ways, although I did manage to construct a proof myself. First I'll remind you of what it says in Winning Ways: for positions containing just (a positive number of) disjoint long chains, there's a formula for the value of the game. First compute the controlled value (which, for a nonempty position, is 4+sum (length of chain4) where the sum is over the chains. If this is positive, then it's also the value. If however it's at most zero, then the value of the game is either 1 or 2 (in fact one knows which one it is because the value and controlled value are congruent mod 2). So now there's your algorithm: when your opponent opens a long chain, compute the value of what is left, decline the last two boxes if what is left has value less than 2, accept if value bigger than 2 and do either if value equals 2.
The analogous long loop rule is the following. In a position containing only (a positive number of) long loops, the controlled value is 8 + sum (length8) where the sum is over the loops. In a dots game this is always even. If the controlled value is 2 or more then the value equals the controlled value. If the controlled value is 0 or less and if there are no quads then the value is either 2 or 4, and the value is congruent mod 4 to the controlled value. Finally, if the controlled value is 0 or less and if there are quads then the value is either 0, 2 or 4, it's congruent mod 4 to the controlled value, and if the controlled value is 0 mod 4 then the value is 0 if there are an odd number of quads and 4 if there are an even number.
If someone else would like to check this, that would be great :) I don't know a published proof although I suspect it's in Scott's MSc thesis.
I had hoped that these results would be useful, but in practice it seems that most games I play here against people who know what they are doing tend to end up with endgames containing both loops and chains, so the results above aren't as useful as I had hoped.
wc.

Carroll ★ at 20070614
Very nice theorems, did you say you have a proof for long loop theorem ?
Can you explain where I'm wrong for the 3 quads case where controlled value is 812=4 and there is an odd number of quads so value should be 0 where it is in fact 4 ?

wccanard at 20070614
I'll write down the proof for the long loop “theorem” (not least because you just pointed out that a bit of it is wrong!). I'll write the proof I have and I'll see if I spot my mistake along the way. I suspect that the only false part of the result will be the determination of whether the value is 0 or 4 in that pesky situation with cv<=0 and cv=0 mod 4. Let's find out.
Basic Technique: If cv(G) is the controlled value of a game G, then v(G) will be at least cv(G) (because the controlling player can keep control) and it might be more. For a given position G which, say, comprises of just disjoint long loops, one way of proving that v(G)=cv(G) is to find a sequence of moves for the player not in control with the property at each stage, the value of (remainder of game minus loop just opened) is 4 or more; if we do this then the controlling player may as well stay in control at each stage by playing allbut4 and ends up winning only the controlled value.
In this post we're only considering positions which are a disjoint union of loops each of which has even length at least 4. Call such a position “loopy” because I'll need to refer to this notion again and again. Say a loop is _very long_ if it has length at least 8 and _notverylong_ otherwise.
Lemma: The controlled value of a nonempty loopy position is 8+sum(lengths  8).
Proof: the Fully controlled value is sum (lengths  8) but the player in control takes all of the last loop giving a swing of 8.
Corollary: if a nonempty loopy position has no notverylong loops then its controlled value is at least 8.
Proof: clear.
Corollary: if a nonempty loopy position has no notverylong loops then its controlled value equals its value.
Proof: whenever Left (the player not in control) opens a long loop, the controlled value of the game minus this long loop is at least 8 by the Lemma applied to the subgame, so the value of the subgame is at least 8, so Right stays in control. This argument works right up to the move when Left opens the last long loop, when the value of the subgame jumps to 0 but we don't care because Right was going to take it all anyway.
Proposition: If a nonempty loopy position has controlled value 2 or more, then its value equals its controlled value.
Proof: If the loopy position has no very long loops at all then the only possiilities are 4L,6L,4L+6L,6L+6L or 6L+6L+6L and in each case the value is easily computed to be the controlled value (probably this part of the argument can be subsumed into what comes later). So WLOG the position has some very long loops. We now prove the proposition by induction on the number of notverylong loops. The base case is covered by the corollary we just proved. The induction step is not hard either. Let G be a loopy position with some notverylong loops (and at least one verylong one). If Left plays in the shortest loop, this loop will have length t, which will be 4 or 6, so the controlled value of (G minus this loop) will be cv(G) + either 4 or 2, so it will be at least 4, so Right may as well stay in control, and this completes the inductive step.
Pause for breath.

wccanard at 20070614
Here we go again. Thanks for reading my “theorem” Carroll: I've spotted my mistake now—let me try and get this next version past you :)
Proposition. If G is nonempty and loopy, and has controlled value at most zero, and furthermore if there are no quads, then the value of the game is either 2 or 4, and the value and controlled value are congruent mod 4.
Proof. Again I'm a bit edgy about the special case where there are only 6loops (I don't like playing a move which changes the terminal bonus!), so perhaps I should start by saying that if the game is just a bunch of four or more 6loops then the Proposition is easily checked by induction in this case.
In the general case (where there is at least one very long loop) we do induction on the number of 6loops. We don't need to do the base case because there must be some 6loops seeing as the controlled value is nonpositive. The inductive step looks like this. Left plays a 6loop. Right has to now decide whether or not to stay in control. But the controlled value of the game has gone up by 2 so it's at most 2, so it is either 2 (in which case the proposition in the preceding post says that the value is 2) or it is still at most 0 (because it's even) and our inductive hypothesis says that the value is then either 2 or 4 and is congruent to the controlled value modulo 4. In either case the value is at most 4 so Right may as well lose control, so he takes all of the 6loop. Now look at the change in the value and controlled value as we move from the original game to the game minus the 6loop: The value has changed to 6 minus the old value, and the controlled value has gone up by 2, and it is easily checked that we've proved what we want.
So the mistake must be in the last step of my notes because I think I'm fine so far. Aah yes, now I see my mistake. The proposition I just proved is false if G is empty: its controlled value is 0 but its value is not 4. So I need to deal with the special case of “only quads”.
So in fact what I now think is true is
Theorem. Let G be a loopy endgame.
a) If G is empty or if cv(G) is at least 2, then v(G)=cv(G).
b) If G is nonempty and has controlled value at most 0 and no 4loops then v(G) is either 2 or 4, and v(G) = cv(G) mod 4 (this determines v(G) uniquely).
c) If G is a bunch of 4loops and nothing else, then its value is 0 if there are an even number of 4loops and 4 if there are an odd number [note: this was my mistake in my notes and in my previous post: this is a special case]
d) If G has at least one loop of size at least 6, and has controlled value at most 0, then v(G) is either 0, 2 or 4 and v(G) = cv(G) mod 4. Furthermore if cv(G) is 0 mod 4 then v(G) can be determined thus: it's 4 if there are an even number of 4loops and 0 if there are an odd number (note: other way around from part (c)).
Proof: We've done parts (a) and (b) already. Part (c) is easily checked by induction on the number of 4loops. It remains to check part (d) which we'll also do by induction on the number of 4loops. The base case of no 4loops at all is part (b) (note that it is crucial that G is nonempty! This was my original error). The inductive step: remove a 4loop and let H be what is left. Then cv(H)=cv(G)+4 which is at most 4, so by (a) and our inductive hypothesis the value is either 0, 2 or 4 and is congruent mod 4 to the controlled value. So Right may as well take all the quad and we see that v(G)=4v(H) and again unravelling shows that we're done. If I got it right this time :)
wc

Carroll ★ at 20070614
Waoh what a breath you have!
Thanks a lot for this groundbreaking work.
I can see no holes now but I will have to check more cases to be entirely convinced. I'm really amazed by the small set of special cases you spotted for cv 2 or more.

wccanard at 20070614
I don't think it's groundbreaking—in fact I strongly suspect I'm reinventing the wheel and all of these results are in Scott's MSc thesis. Furthermore the “all loops” and “all chains” results aren't so useful because in practice on a 5x5 board one seems to end up with both loops and chains.
Furthermore I *still* haven't got the last assertion in part (d) right! I am pretty confident about the following:
1) If cv geq 2 then v=cv
2) if cv leq 0 then v is 0, 2 or 4 and v=cv mod 4.
But all this extra faffing around is an attempt on my part to distinguish v=0 from v=4 in case 2. My first attempt was wrong, as you pointed out. I now see that my second attempt was also wrong: In the game 4L+4L+8L the value is 0 and part (d) predicts 4. I can see where my argument breaks down too. I think I should replace part (d) of the statement above by the weaker statement “If G has one loop of size at least 6, and controlled value at most 0, then the value is either 0, 2 or 4, and it's congruent to the controlled value mod 4, but at present I don't know a rule of thumb that tells you whether the controlled value is 0 or 4”. I am halfwondering whether the rule of thumb I'm seeking is too complicated to be a rule of thumb.
\\\*
If cv is 2 or more then in a simple loony endgame position (just disjoint long chains and loops) the value must equal the controlled value. This is stated without proof in Berlekamp's book but I wrote down a proof myself to convince myself. The only hard part is controlling the terminal bonus, which is sometimes a subtle beast. The key technique is that Left makes moves and has to check that he knows what has happened to the controlled value. He certainly knows what has happened to the fully controlled value but the terminal bonus can jump. For example if Left eats a 4chain, and it's the last long chain, when there are still some loops left, the terminal bonus jumps from 4 to 8. A more subtle phenomenon is when all chains are 3chains; the terminal bonus can then be 6 because there is this quirky endgame situation with one 3chain when Left opens the last loop and Right takes all of it and sacrifices the 3chain. It was only when I discovered this phenomenon that I understood why Berlekamp coyly explains the terminal bonus on p85 as what Right gets when he loses control on “the last or nexttolast loony move” rather than just “the last loony move”.
One might wonder whether in a general loony endgame the value and controlled value are equal if the controlled value is at least 2. But Berkelamp gives a stunning counterexample in his book: the disjoint union of (a 9chain) and (a pair of quads connected by an 11chain). The controlled value is 8: the 11chain gives you 7 and then you don't accept either quad, losing 8, because the 9chain has length more than 8. But the value is 10! If Left breaks the 11chain then Right accepts, scoring 11 and then losing 1 in the position 9+4L+4L.
Conversely, the main theorem of BerlekampScott says that if cv>=10 and some other mild assumptions, then v=cv. It's a clever result but unfortunately is of no help in 5x5 dots and boxes because if you are lucky enough to be in control in a position with controlled value 10 or more then you are probably going to win regardless :) Note also that the counterexample above also does not fit into a 5x5 board, so there are some open questions there about what the optimal result is on a 5x5 board but again the answers won't be useful in practice, I suspect.
wc

wccanard at 20070614
OK so here's a rule of thumb, and I believe that my arguments above prove everything in this post. I guess this is the definitive statement, although you'll have to dig around above to find the proofs.
The value of the empty game is 0. And in a nonempty loopy endgame G.
1) If cv(G) geq 2 then v(G)=cv(G).
2) If cv(G) leq 0 and if there are no quads then v(G) is either 2 or 4, and v(G)=cv(G) mod 4.
3) If cv(G) leq 0 and there are quads, then let H denote G minus all the quads. Parts (1) and (2) above enable you to compute v(H). If v(H) is 2 mod 4 then v(G)=2. If v(H) is 0 mod 4 then v(G) is either 0 or 4, and v(G)=v(H) mod 8.
The part I have continually messed up is that bit at the end about distinguishing 0 from 4 when cv=0 mod 4; but I am pretty sure that what I have here is right because I have just checked it by brute force on a computer for all loopy endgames with at most 100 coins.
wc

wccanard at 20070614
Heh, one last typo: last bit of 3 should say “…then v(G) is either 0 or 4, and v(G)=(v(H)+4*number of quads in G) mod 8.
I'll clean up the proof, write a pdf and post it somewhere. This inability to edit my own posts here in the forum is driving me nuts.

wccanard at 20070614
OK, I have written up the correct arguments in a pdf file, which will surely be easier to read than the mess I have created above. If anyone wants it then they could message me with their email address and I'll email it to them (it's 146K). Alternatively, if anyone could remind me of a good place to upload 146K files so that they are accessible to all I'd be happy to do that too.
wc

wccanard at 20070614
Carroll suggested wetpaint. So for a pdf file, go to
http://wccanard.wetpaint.com/
and click on the pdf file near the bottom of the page (under “attachments”)
to see a notyetcomplete collection of the notes I've made about dots and boxes since finishing Berlekamp's book and starting to play here.
NB don't rush to add comments to the wiki; I am unlikely to ever look at the page again :)

sam_nead at 20070614
WC  of the 2140 endgames you considered, would it be possible to list, say in lexicographic order, all of the ones which have a value \leq 2? If this is too many games then the lists for value \leq 1 or even = 0 would be useful. I think that the grandmasters must know how to play towards such “balanced” endgames; since lesser players are willing to sacrifice to win the chain battle such endgames are very safe! Even without a sacrifice such an endgame can win in the presence of the correct amount of short stuff.
I am guessing that there are not so many of these “balanced” endgames – a random game should have a few longish chains… Of course random here means randomly generated by the computer. They probably don't appear often in actual play.
Actually, an endgame database, ordered first by value and then by lex, would be cool to look at. If you fit two games on each line, and 50 lines on a page, then that clocks out at just over 21 pages.
Hmmm. I've thought a bit more – the ordering should be
1. Games with an even number of long chains come before games with an odd number
2. Games with a lower value come before games with higher
3. Games without loops come before games with loops
4. All else being equal, use lex. (All loops are after all chains).

wccanard at 20070614
(Sam is referring to a computation I mention on p9 of the pdf file I posted at wetpaint). I had initially intended to print out all 178 positions where opening the shortest loop is not right, and “get to know” them, but it seemed like a bit of a waste of time somehow—when I realised that either the shortest chain or the shortest loop was a canonical move, and that it was the shortest loop if there were no 3chains, this meant that to analyse a position with n isolated loops/chains would only take time 2^n at most, and given that n is at most 5 or 6 in practice, I realised that I had this sort of time to spare.
Note also that I am sticking to only loony endgames which are comprised of disjoint loops and isolated chains, so if you have a quad with a chain growing off it then the 21 pages are useless to you anyway.
In the statements below, “game” means “loony endgame comprising only of isolated chains of length at least 3 and isolated loops of even length at least 4, and with at most 25 boxes in total”. I included the empty game.
78 games have value 0, 251 have value 1 and 193 have value 2.
The smallest nonempty game with value 0 is 4L+4L, the smallest with value 1 is 3+4L and the smallest with value 2 is 4L+6L.
The mean value of a game is 14949/2140, which is just under 7. The biggest game is the 25chain with value 25; two games have value 24, the 24chain and the 24loop. The obvious pattern continues down to 22 but there are lots of games with value 21, namely the disjoint union of an ichain and a 25ichain for lots of values of i.
Do you still want to see this 21page list?
wc

wccanard at 20070614
What do you mean by “all else being equal, use lex. (All loops are after all chains).“? Who wins between 3+4+6L+6L and 3+4+6+6L, for example?
Hmm. I am going to interpret 3 and 4 thus. Sort by number of loops (games with fewer loops come first), then lex on loops (given two games with the same number of loops), then number of chains (games with fewer chains come first), then lex on chains. Is this what you mean?
Maybe I should just do the sort, upload the answer, and wait for you to say “no no no, I meant _this_!“.

wccanard at 20070614
Well, it's done; I uploaded the results to wccanard.wetpaint.com as a text file. Warning: long lines! (some are greater than 80 characters). Did I correctly guess your ordering intentions Sam? If not then I'm sure you can now sort the data yourself :) (or I can easily resort it).
wc

sam_nead at 20070614
3+4+6+6L comes before 3+4+6L+6L, because 6 comes before 6L.
So, for example, I would guess that the smallest game with value 2 is 3+3?
In a fixed parity and value, if G has no loops and H has a loop then G < H.
“Sort by number of loops (games with fewer loops come first), then lex on loops (given two games with the same number of loops), then number of chains (games with fewer chains come first), then lex on chains. Is this what you mean?”
No, no. Lexicographic ordering means dictionary ordering. But you know, I suppose it doesn't _really_ matter, as long as we short by parity and value first.
Also, I think that the 21 page list would be interesting! It will be a complete endgame book for the 5x5 game. That will be handy. Of course, it will contain many obvious things – I suppose that every game with a value larger than 12 is pointless. But that is why we order according to value.
Hmm. Perhaps I shouldn't have asked for the mean value of the games, as this can be biased by a few very high value games. What is the median (middle) value? How many have value 0, 1, 2, 3, 4, …, 25?
(By the way, if you look at your table you should see the answer to my question above: What is the value of 4L+4L+5+7? This was a possible endgame in my game against Scott.)

wccanard at 20070614
“Lexicographic ordering means dictionary ordering.“. Right! But words are sequences of letters and the set of letters is wellordered. Simple loony endgames are not a sequence of numbers, they are an ordered pair of sequences of numbers, and when push came to shove I couldn't quite interpret what you meant.
“Also, I think that the 21 page list would be interesting! It will be a complete endgame book for the 5x5 game.“. I guess I disagree with this statement on two counts. Firstly it's not a complete endgame book because it doesn't contain any of the endgames with “dippers” or “earmuffs” in Berlekamp's technology (i.e. loops with chains dangling off them etc). And secondly I'm sure you would agree that a text file containing a list of all the even numbers from 1 to 10000 together with what you get when you divide them by 2 would not be particularly interesting—my feeling is that given a simple loony endgame it is a relatively easy matter to compute its value.
Not that these objections stopped me from making you the list anyway :) Let me know if I've misunderstood you.
wc

wccanard at 20070614
As an example, here's how I would compute the value of 4L+4L+5+7. I know from general theory that the strings should be broken in the following order: quad,quad,5,7. Now I compute backwards: v(7)=7 hence v(5+7)=8 hence v(4L+5+7)=4 hence v(4L+4L+5+7)=0.
The number of simple loony endgames with value 0,1,2,3,…,25 is
[ 78, 251, 193, 144, 167, 160, 103, 113, 149, 167, 79, 87, 105, 109, 43, 41, 51,
49, 11, 11, 12, 11, 2, 1, 2, 1 ]
So the median is 7 if I got it right. [and my program is correct! etc etc]
wc

wccanard at 20070614
Lex: Aah I finally see your point! You want to consider a game as a sequence of elements of the set {1,2,3,4,….,1L,2L,3L,4L,…} ordered in that way (order type omega+omega). Probably that is different to what I did. Do you want me to resort?

sam_nead at 20070614
This is pretty cool! Certain things really pop out at me. For example v(3 + 3 + 4L + 4L) = 2 while v(3 + 9 + 4L + 4L) = 0…

sam_nead at 20070614
Also, a pair of quads really does even the score! Essentially every game containing at least a pair of quads has value < 6. How does this sound: if you can get 6 points, are out of control and can arrange a pair of quads then you win.

sam_nead at 20070614
“Complete book”: Ok you are correct here. But the earmuffs are rare on the 5x5 board, even in expert play. (I've seen Scott use them twice, I think.) Dippers are a bit more common, I suppose…
The lex list would be nicer, I think… Is it a lot of work to resort this way?

sam_nead at 20070614
“my feeling is that given a simple loony endgame it is a relatively easy matter to compute its value.”
Yes – that is true. I really just want to stare at the list and look for patterns!

wccanard at 20070614
Regarding the first of your two posts above: if the controlled value is negative then the value is oscillating from 0 to 4 and back as the chain grows, but when the controlled value becomes positive then the value starts going up. For example the value of n+4L+4L+4L as n increases from 3 to 20 is
[ 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
the last 0 occurring at n=12, the place where the controlled value is 0.
Regarding your second post—I can quite believe it. Of course there are games with a pair of quads and value bigger than 6, e.g. 17+4L+4L. But I think that there are no games with at most 20 dots, two quads and value 5 or more, so if you can even get 5 points and two quads then you're in very good shape; games like 12+4L+4L only have value 4.

wccanard at 20070614
Sam: the file sam2.txt at wetpaint is my next attempt at ordering the data in the manner you require.
wc

wccanard at 20070614
Try again. Sam: I am hoping that sam3.txt is the data you want in the correct order. If it isn't then can you give me two explicit lines that are not in the right order in your opinion, plus some explanation as to why they should be in the other order? Hope I got it right this time :)
wc

sam_nead at 20070614
The two lines
[ 6, 6 ],[ 4, 4 ],0,[ , k>, , l> ]
[ 3, 3, 3, 3, 3, 3, 3, 4 ],[],1,[ , k>, , l> ]
are out of order. (Every line with a threechain should come before any line where the smallest chain is a 4+ chain. Just like “every word starting with and 'a' comes before any word starting with the letter 'b' or 'c' or etc.)
Perhaps lex order is not so easy to implement in code? I've never thought about this! It seems like a very natural question, but perhaps tangential to our discussion. Hmmm.

wccanard at 20070614
The top one becomes first because it has value 0 and in your list of criteria “value” was before “lex”.

wccanard at 20070614
OK then I am cautiously optimistic that I have understood your sort criteria correctly :) Enjoy the data!
wc

sam_nead at 20070614
Ok, I'm confused. How about these two lines:
[],[ 4, 6, 6, 8 ],0,[ , k>, , l> ]
[ 3, 3 ],[ 4, 8 ],0,[ , k>, , l> ]
These are reversed because 3 < 4L.
I guess you lex sorted by chains and then lex sorted by loops? Everything else looks fine, I think.

sam_nead at 20070614
Right, here is another example
[ 3, 3 ],[ 6, 8 ],2,[ , k>, , k>, , l> ]
[ 3, 3, 3, 3 ],[ 4 ],2,[ , l>, , l> ]
These are out of order because 3 < 6L.

sam_nead at 20070614
Hmmm. This looks correct! But it still has a weird feel to it. For example the two lines
[ 3, 4, 5, 5 ],[ 4, 4 ],1,[ , k>, , l> ]
[ 3, 4 ],[ 4 ],1,[ , l> ]
are correctly sorted. But they feel odd: shouldn't a subposition appear before a superposition? I think that sam3.txt had this nice property…
Well, I will stop making requests and actually look at the data. Here, I can't resist posting my lexcode. Is it right?
/\* Suppose we have a ordered alphabet. Suppose we have two words, U and V, over this alphabet. I'll denote the i^th character of U by U[i], starting at zero. So if U = aabca then U[0] = a, U[2] = b, and so on. As a convention, I'll assume that U[length of U] is the “empty character” which is smaller than all other characters (including itself!). */
which_is_less(U, V)
{
i = 0;
while 0 == 0
{
if U[i] < V[i] return U;
if V[i] < U[i] return V;
i = i + 1;
}
}

wccanard at 20070614
In your code: I guess you should check U isn't equal to V at some point :)
You were barking up the wrong tree though—the problem was not in my lex implementation, it was typos (e.g. at one point I mistyped 2 for 1 and hence concatenated the chains in game 1 to the loops in game 2 by accident etc).
As for “weird feels”—as far as I'm concerned this is in the eye of the beholder :) If you can write a lex code then you can read a perl manual and go ahead and learn to manipulate the data to your hearts content :)

sam_nead at 20070614
“In your code: I guess you should check U isn't equal to V at some point :)”
Nope! If they are equal then the “empty character” at the end makes us return U. ;)

wccanard at 20070614
If you're happy with that behaviour then perhaps your function should be called “which_is_at_most” :)