Would some of the masters (2000 and up) please discuss opening and midgame strategy, with a view towards assisting the midlevel players (1800-1999)?

Thank you.

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.

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 email-based 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 nim-values 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.

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 nim-values 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).

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 “normally-played” 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 nim-values

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 nim-values in practice.

As well as knowing how to compute nim-values 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 nim-value) 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 nim-value 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 nim-value 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 nim-value 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 non-experts?

3) The pre-emptive 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 all-but-two

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 mini-threats 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 3-chain,

he is *guaranteed* to lose! Why? Because player 2 doesn't *have* to

do the all-but-two trick. He can choose whichever option he prefers;

if he thinks that your premature sacrifice is a super-strong 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 n-1 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 n-3 ahead. The proofs of these assertions

are simple strategy-stealing arguments and are non-constructive, 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 2-chain and a nearly-completed

6-chain—i.e. (in nimstring language) draw a 6-chain and then

a second string from one of the ends of the chain to the ground.

The nim-value of that position is 1 so you have lost the chain battle.

If you have read the above then you might think “pre-emptive 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 2-chain

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).

4) Openings.

The original poster asked about openings. A follow-up 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 6-3 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 6-3

after an arbitrary move by the first player and perfect play thereafter.

Similarly on the 3x5 board with best play it's 8-7 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 too-large 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 :-)

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 3-chains around, and perhaps also some quads (4-loops)

or 6-loops, 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 tree-like

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 1-chain over a 2-chain.

*) If you're going to open a long chain, then choose the shortest long

chain possible (i.e. open the 3-chain rather than the 4-chain).

The proofs of those two assertions are simple man-in-the-middle arguments.

Berlekamp explains “man-in-the-middle” 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 4-chain

rather than a 3-chain) now goes like this: you set up

two dots positions, you force expert 1 to start by opening the 4-chain,

and you instead open the 3-chain 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 “near-copying” 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 man-in-the-middle argument

shows that two 1-chains cancel: if there are two 1-chains 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 2-chains 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 1-chains, three 2-chains, four 3-chains and a 4-chain,

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 all-but-two. 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 1-chain, which will be taken and promptly given back to him

via the second 1-chain by the second player (call him Blue). We go through

the 1-chains and the 2-chains 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 2-chains

and an even number of 1-chains), 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

strategy-stealing 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 3-chain. 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 4-chain, the last chain, and it will be snapped up by his opponent.

So v(4), the game consisting of a 4-chain, 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 3-chain, 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 4-chain, so the 3-chain will be politely declined and v(3+4)=3,

the optimal play being player 1 opening the 3-chain and player 2 taking

all but two of it, so he's one down but the 4-chain 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 3-chain 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 3-chain 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 3-chain and blue will grab them all and open

the next 3-chain. 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 3-chains and a 4-loop) 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 3-chain. 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 8-loop is basically worth nothing, but the only optimal

move is opening the 4-loop. 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 all-disjoint-chains-and-loops endgames which come up

so frequently on the 5x5 board.

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.

THANKZ A LOT!

Very nice read, although I knew most of it :)

I'll translate this text to Dutch somewhere this week, btw :)

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 11-6 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 two-chain.

2. Making a loony move in the “almost six-chain”.

3. Sacrificing the two-chain.

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 two-chain has one free move (move 3) and two “loony moves” (move 1). Nimstring ignores loony moves, so the two-chain is a *1. Likewise the almost six-chain 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 11-6 the game is actually tied. Whoever gets the two-chain will win.)

WC suggests that move two is reasonable – after all, we don't want the second player's five box guaranteed pay-off to grow to six boxes. This is is correct approach in the mid-game – “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 out-of-control player will get the last of the short chains. Generally the out-of-control 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 six-chain we have a guaranteed win: we get the last of the short chains and that gives us the two-chain. 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 five-chain 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 two-chain, 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 out-of-control player cannot preemptively open the final chain.

What I would really like to see is a discussion of the “half-quad”. This seems to come up all the time in expert games and never come up in say 1900- games. By “half-quad” 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: “half-quads 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 three-chain….

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!)

Crud. I already said something wrong. “If there cannot be any more chains or chain threats then the out-of-control 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 out-of-control 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.

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 2-chain. I didn't consider it because in some sense I didn't even notice it! Because a loony move in a 2-chain gives your opponent strictly more options than the corresponding non-loony move, the “modified” game of dots and boxes where loony moves in 2-chains 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 “half-quad”.”

This wouldn't be because of your super-complicated game with Scot at all, would it? :-)

sam_nead: “I suppose that there is a rule of thumb here: “half-quads 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 nim-string value 1”, a sentence which was at best ambiguous and at worst wrong; you have now done the nim-analysis of the position though so I'm less worried).

Your comments have got me thinking more about the pre-emptive sacrifice. So far we have two examples of positions with 1 long chain: a nearly-completed 6=chain plus a 2-chain, where we know that it's best not to pre-emptively sacrifice, and a two-moves-away-from-completion 6-chain (with one string of “extra grounding” at both ends), where it *is* best to pre-emptively 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 pre-emptively 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 3-chains 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 5-chain and the 7-chain. Now one can work backwards to compute the value of the position.

wc

Thanks both for your enlighting posts.

open both quads, and then the 5-chain and the 7-chain

Subsidiary : then will player 2 accept or decline the two quads? :)

What is the rule of thumb for similar cases?

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 3-chain and the controlled value of the position with the 3-chain 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 3-chain, isolated 4-chain, two quads) the value is 3, the controlled value is -5, and the player not in control can open either the 3-chain or a quad (both moves are optimal). If the 3-chain 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 3-chains. 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

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 non-empty position, is 4+sum (length of chain-4) 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 (length-8) 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.

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 8-12=-4 and there is an odd number of quads so value should be 0 where it is in fact 4 ?

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 all-but-4 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 _not-very-long_ otherwise.

Lemma: The controlled value of a non-empty 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 non-empty loopy position has no not-very-long loops then its controlled value is at least 8.

Proof: clear.

Corollary: if a non-empty loopy position has no not-very-long 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 non-empty 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 not-very-long 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 not-very-long loops (and at least one very-long 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.

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 non-empty 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 6-loops (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 6-loops 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 6-loops. We don't need to do the base case because there must be some 6-loops seeing as the controlled value is non-positive. The inductive step looks like this. Left plays a 6-loop. 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 6-loop. Now look at the change in the value and controlled value as we move from the original game to the game minus the 6-loop: 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 non-empty and has controlled value at most 0 and no 4-loops 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 4-loops and nothing else, then its value is 0 if there are an even number of 4-loops 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 4-loops 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 4-loops. It remains to check part (d) which we'll also do by induction on the number of 4-loops. The base case of no 4-loops at all is part (b) (note that it is crucial that G is non-empty! This was my original error). The inductive step: remove a 4-loop 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)=4-v(H) and again unravelling shows that we're done. If I got it right this time :-)

wc

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.

I don't think it's groundbreaking—in fact I strongly suspect I'm re-inventing 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 half-wondering 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 4-chain, 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 3-chains; the terminal bonus can then be 6 because there is this quirky endgame situation with one 3-chain when Left opens the last loop and Right takes all of it and sacrifices the 3-chain. 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 next-to-last 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 9-chain) and (a pair of quads connected by an 11-chain). The controlled value is 8: the 11-chain gives you 7 and then you don't accept either quad, losing 8, because the 9-chain has length more than 8. But the value is 10! If Left breaks the 11-chain then Right accepts, scoring 11 and then losing 1 in the position 9+4L+4L.

Conversely, the main theorem of Berlekamp-Scott 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

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 non-empty 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

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.

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

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 not-yet-complete 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 :-)

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).

(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 3-chains, 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 non-empty 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 25-chain with value 25; two games have value 24, the 24-chain and the 24-loop. The obvious pattern continues down to 22 but there are lots of games with value 21, namely the disjoint union of an i-chain and a 25-i-chain for lots of values of i.

Do you still want to see this 21-page list?

wc

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_!“.

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

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.)

“Lexicographic ordering means dictionary ordering.“. Right! But words are sequences of letters and the set of letters is well-ordered. 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

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

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?

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…

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.

“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?

“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!

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.

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

wc

Um, hold up, that attempt was definitely not right :-)

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

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 three-chain 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.

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

Ack! I forgot to check the value! These lines are fine.

Let me look again. Sorry about this!

OK then I am cautiously optimistic that I have understood your sort criteria correctly :-) Enjoy the data!

wc

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.

That's a slip. I'll sort it out.

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.

I've written some pseudo-code for lex, if you like.

Try sam4.txt.

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 lex-code. 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;

}

}

Ack! The forum ate the formatting!

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 :-)

Thanks for the files. I will now bathe in the data.

“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. ;)

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