explicit construction of positions with big nimvalues Dots and Boxes
26 replies. Last post: 20070605
Reply to this topic Return to forum
wccanard at 20070515
Can one find arbitrarily large positive integers n with both of the following properties:
i) There is a game G of strings and coins with nimvalue 2^n and a move in G which sacrifices no coins and changes the nimvalue to zero, *and*
ii) There is a game H with nimvalue 2^n such that the only moves which take the nimvalue down to zero sacrifice at least one coin?
If so then I feel that I can almost construct a counterexample to one of the assertions about canonical play in dots and boxes made in Berlekamp's book. In particular I am skeptical about the existence of such n. But I can't rule them out, and might have made a mistake anyway—help!
wc
PS does anyone have access to Katherine Scott's MSc thesis? Does this thesis deal with such questions?

sam_nead at 20070522
Dear wccanard –
I did a bit of Googling and found this:
www.msri.org/publications/books/Book42/files/beforcing.pdf
Is that what you are looking for?

wccanard at 20070522
Hi sam. No—this is the BerlekampScott paper in “more games of no chance”. This is a neat paper but doesn't really have any bearing on the 5x5 game—it is a clever way of playing a very close endgame on a veyr big board. What I would love to see is reference [Scott] from that paper. As an example of what is in [Scott], see comment 5 of the paper you just pointed out (on the last page of the paper). I tried to do some basic analysis of those common loony endgames and it is surprisingly complicated! For example imagine you're 53 up in a 5x5 game, but have lost control and are faced with two isolated chains of length 3 and 6, and two quads. My instinct would be to open a quad but in fact a brute force analysis shows that it's better to open the 3chain. If I open the 3chain then I win by 1 with best play, but if I open a quad then my opponent can take it all and win by 1. Rather than working out a general theory of how to play these simple endgames I thought I would first look at what was known. As another example of what is in there, As an example, it says in chapter 10 of Berlekamp's book that Scott proved that one should never open an isolated chain if there is a *smaller* (i.e. containing fewer boxes) loop (in the sense that the loop move can never be strictly worse than the chain move), and one can even say something about what to do when the smallest loop and the smallest chain have the same number of boxes in. I'd like to see what she proved before I waste too much time proving things myself.
The specific example I'd love to be explained to me is why a canonical player will never play in a long chain if there is a short chain available. This assertion is in Berlekamp's book and it's driving me nuts. I thought had a proof of this but my proof has an hole in it.
wc

sam_nead at 20070522
Dear wccanard –
That is an interesting position. I think that I agree with your analysis.
If you are interested in Scott's thesis, perhaps the thing to do is to email Prof Berlekamp. Either that or request it via interlibrary loan from the UCB library. You'll need access to an academic library. Here is the library record I found at
Title Loony endgames in dots and boxes / by Katherine Wells Scott.
Author Scott, Katherine Wells.Â
Date 2000.
Description ii, 21 leaves : ill. ; 28 cm.
Notes Thesis (M.A. in Mathematics)–University of California, Berkeley, Fall 2000.
Includes bibliographical references (leaf 21).
Subject Headings University of California, Berkeley. – Dept. of Mathematics – Dissertations.Â
Location(s): Main Stack Â 308t 2000 553
Loan period: noncirculating; Not checked out.
Math Â QA3.A135.2000.S368
Hmmm. Perhaps noncirculating means you cannot check it out… I'll bet you can call the library and get a photocopy for a small fee, however.

sam_nead at 20070522
Hmmm. After thinking about it, I feel sure that Prof Berlekamp must have a copy. He was her advisor, after all.

wccanard at 20070522
Sam—I emailed Berlekamp a while ago. His copy of her thesis is in a box in his office in Berkeley and he's away from Berkeley until September. That was why I asked here :)

Carroll ★ at 20070524
Wccanard, can you post examples of how you construct D&B positions with high Grundy value?
What are the CGT games which are known to have arbitrary high Grundy values (except Nim)?
For example I asked myself the question in Sprouts about existence of maximal Grundy value (highest known is 12, not counting 8+7) and I can't make my mind if my intuition is that there is a highest value. See records.
Maybe there is a way to mimic nimstring with Sprouts and get the same high values…

wccanard at 20070524
Carroll—I don't know how to construct D&B positions with high Grundy value! Let alone answer the question I raised above :) The “value” I've been talking about in the *other* threads I've started recently is the actual number of boxes that the game is worth—so e.g. a big chain with 100 boxes in has nimvalue 0 but “real world” value 100 because that's the score the second player is going to get.
In practice I'm not sure I've ever seen a connected dots and boxes position with nimvalue larger than 5 :) Of course by putting disjoint positions together I can get up to 7 but for all I know there could be a uniform bound, at least for positions that can arise in a game on a finite square grid. Interesting question!

sam_nead at 20070524
I'm curious as to what examples people have. What are the nice examples of 0, *, *2, *3, and so on? Also, what is the best way to display them in this forum? (The fonts are not monospaced!)

wccanard at 20070525
Sam—from looking at other threads here from over the years, I see that the problem of displaying dots positions in the forum has caused some trouble over the years! On the other hand if you want to see examples quickly you can just look in “Winning ways” which has plenty.
Let me draw the *duals* of some positions—so a * represents a box and a line
represents an asyet undrawn line.
Then a long chain like
(starting and ending at the edge of the board)
has nimvalue 0, a short one like
has nimvalue *, and something which is about to turn into either a long or
a short one, like
\
v
(probably illegible in this forum, so just cut and paste it into your
favourite fixedwidthfont window) has nimvalue *2, and the sum of this
and a short chain has nimvalue *3. But there are plenty of other relatively
natural examples that show up, at least on the 7x7 board (I have more experience
with larger boards, coming from Richard's PBEM server). In Winning Ways they
explain how some dots and boxes positions (or rather the corresponding nimstring positions) are equivalent to Kayles or Twopins positions, so it's easy to construct many more examples of things with all sorts of values. But not arbitrarily large (in the sense of *n with n large) ones, as far as I know.

wccanard at 20070525
heh, the forum even eats the spaces :) The *2 position is supposed to be a 3chain with the downarrow dangling off the middle.

ypercube ★ at 20070525
Test:
Let me draw the *duals* of some positionsso a * represents a box and a linerepresents an asyet undrawn line.Then a long chain like(starting and ending at the edge of the board)has nimvalue 0, a short one likehas nimvalue *, and something which is about to turn into either a long ora short one, like  vmore testing: <v^

wccanard at 20070525
Also testing. Let me actually draw the dots and boxes positions, rather
than the dual positions. So now * indicates a dot (rather than a box!)
nimvalue 0:************(with both ends going to the edge of the board)nimvalue 1:*** ** *(in the bottom left hand corner of the board)nimvalue 2:**** ** * *in the bottom left hand corner of the board (because the next player to move in that region will decide whether the chain is long)The nimvalue 5 position I know is from the end of Chapter 7 of Berlekamp'sbook (in the second printing at least)*** * * * * * ** * * * *again in the bottom left hand corner of the board.
Looking through the table of Dawson's Kayles values in Berlekamp's book, I see there is one with nimvalue *9, so there are dots and boxes positions with nimvalues up to *15 (and you can even make them connected, because long chains snap). Can anyone get to *16?

Carroll ★ at 20070525
Funny that Sprouts can mimic Dawson's Kayles also, by nesting onespot boundaries as Dan Hoey suggested.
Do you see an efficient way to do onespot nested boundaries out of ordinary spots?
How do you mimic Dawson's Kayles with D&Bs positions ?
(Dawson's Kayles is a game where the only valid move is to remove two adjacent pins, the one that can't move loses, example 10> 4,4 or 10>8 or 10>2,6 are valid moves of value *0, *, *2. The first *9 is at value 86 needing a big paper sheet but a nice *7 is at 33…)

Carroll ★ at 20070525
I found it :
****   * * * *   * * * *   * * * *   * * * *   * * * *is Dayson's Kayle DK1 (One inner corridor) of value *0*****    * * * * *    * * * * *    * * * * *    * * * * *    * * * * *is DK2 of value *
So you would only need a paper sheet of size 5x35 to get *7, any smaller one ?

Carroll ★ at 20070525
A mistake in top row :
**** * * * *   * * * *   * * * *   * * * *   * * * *and ***** * * * * *    * * * * *    * * * * *    * * * * *    * * * * *

wccanard at 20070525
Carroll—yes, you got it. Dots and Boxes in fact can also generalise Kayles (make those internal chains short rather than long, but not too short) and even Twopins.
I have no idea how nimmy a Twopins position can get: the standard periodicity results for Kayles and Dawsons Kayles don't really apply to Twopins because there are 2^{n connected positions of size n rather than 1}n :)

sam_nead at 20070604
So, I've been thinking about “nimstring on the side” positions.
For example:
Length 1 is:
^ *
Length 2 is:
^ ^ **
Length 3 is:
^ ^ ^ ***
and length 4 is:
^ ^ ^ ^ ****
and so on.
The table of length/nim values is
Length: 1 2 3 4 5 6 7 8 9 10Nim: 0 1 2 1 2 3 0 3 0 1
Not very impressive, eh?
But these positions do have connnected followers which are bigger. In particular I've seen 1step followers which are as big as *6.

wccanard at 20070605
Sam: this sequence is mentioned in Winning Ways (in the second edition,
at least) and I think also that Berlekamp raised the issue of what was going
on in this sequence in some article on open problems in game theory.
Winning Ways (p581, 2nd edition, Chapter 16 of course) gives the next nimber
in the sequence too (position 1' x 11 in their notation): they claim it is 2.
They don't give any more although I'm sure it's possible to go further. It's not clear to me that one would even expect the sequence to become ultimately periodic though, or even if one would expect any “simple structure” at all. In fact in Winning Ways they compute nimbers for all sorts of funny nimstring graphs, e.g. complete graphs on n vertices for small n! The only structure they spot is that the nimber of a complete bipartite graph K_{m,n} only seems to depend on the parity of (m1)(n1) for small m,n. My feeling is that this can be heuristically explained: a complete bipartite graph has no edges running to the ground so one might feel that if played out, the ensuing loony position will just be a bunch of disjoint loops. If this is the case then the nimber will be 0 or 1 depending only on the parity of the number of edges+vertices; there are m+n vertices and mn edges so indeed you see (m1)(n1) showing up. This isn't a proof of their assertion though because nondisjoint loops can behave in different ways. The heuristic is good though—it also explains the nimbers of K_5 and K_6: they claim that both have nimber 1 and both have an odd number
of (vertices+edges). Interestingly, they claim that K_3 has nimber 1 when it clearly has nimber 0.
The upshot though is that at present noone seems to know much about the sequence you mention above, and related sequences. It's the facts that the chains are “so” grounded and that so many distances are short that makes it complicated, I think.
wc