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 nim-value 2^n and a move in G which sacrifices no coins and changes the nim-value to zero, *and*

ii) There is a game H with nim-value 2^n such that the only moves which take the nim-value 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?

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?

Hi sam. No—this is the Berlekamp-Scott 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 5-3 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 3-chain. If I open the 3-chain 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

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 inter-library loan from the UCB library. You'll need access to an academic library. Here is the library record I found at

Pathfinder

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: non-circulating; Not checked out.

Math   QA3.A135.2000.S368

Hmmm. Perhaps non-circulating means you cannot check it out… I'll bet you can call the library and get a photocopy for a small fee, however.

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

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

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…

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 nim-value 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 nim-value 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!

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

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 as-yet undrawn line.

Then a long chain like

(starting and ending at the edge of the board)

has nim-value 0, a short one like

has nim-value *, 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 fixed-width-font window) has nim-value *2, and the sum of this

and a short chain has nim-value *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.

heh, the forum even eats the spaces :-) The *2 position is supposed to be a 3-chain with the down-arrow dangling off the middle.

Test:

Let me draw the *duals* of some positions---so a * represents a box and a linerepresents an as-yet undrawn line.Then a long chain like(starting and ending at the edge of the board)has nim-value 0, a short one likehas nim-value *, and something which is about to turn into either a long ora short one, like    |    v--------------more testing: &ltv^--------------

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

nim-value 0:*--*--*--*--*--**--*--*--*--*--*(with both ends going to the edge of the board)nim-value 1:*--*--*      |*--*  *(in the bottom left hand corner of the board)nim-value 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 nim-value 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 nim-value *9, so there are dots and boxes positions with nim-values up to *15 (and you can even make them connected, because long chains snap). Can anyone get to *16?

Funny that Sprouts can mimic Dawson's Kayles also, by nesting one-spot boundaries as Dan Hoey suggested.

Do you see an efficient way to do one-spot 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…)

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 ?

A mistake in top row :

*--*--*--*|        |*  *  *  *|  |  |  |*  *  *  *|  |  |  |*  *  *  *|  |  |  |*  *  *  *|  |  |  |*  *  *  *and *--*--*--*--*|           |*  *  *  *  *|  |  |  |  |*  *  *  *  *|  |  |  |  |*  *  *  *  *|  |  |  |  |*  *  *  *  *|  |  |  |  |*  *  *  *  *

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

So, how do you get the momospacing? Instruct us.

Crud: I meant “monospacing” of course.

use the tag

in combination with tag.

Ok, here is a quick test

*-*

\| \|

*-*

Ok, here is a quick test

 *-* | | *-*

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 1-step followers which are as big as *6.

Dang – It is hard to get the formatting right…

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 (m-1)(n-1) 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 (m-1)(n-1) showing up. This isn't a proof of their assertion though because non-disjoint 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 no-one 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