Hey. I am unable to find any program online to calculate nimber values. It seems like there is a working version somewhere (see http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=110&topic=8) but I cannot find it.

Can anyone give me a useful link? Also, would the usage of such a program be concidered cheating here? It is not hard to do by hand but it can take some time (but again, that could be said about solving chess too..)

I am quite unsure on what the rules of cheating are here. Bots are playing.

I would consider this as cheating. Well, sure, if everybody agrees on using it I'll do so as well, but currently I'm quite bad at nimber calculations (by hand, always) so I think being able to compute them in a “reasonable” amount of time (no matter what “reasonable” means viz. the time you spend on LG) should be a “rewarded” skill.

Yeah I guess you're right.

Nice to have an intelligent thread in the D&B forum!

Thnikkaman: I have that program. It's a relatively short C++ program. I think that computing nimbers is a pretty hard problem computationally (the naive algorithm will have exponential time and I have no evidence it's doing anything cleverer) so don't expect miracles from it.

But let me also make some other comments. When I was learning this game and making my way up the rankings here, there was a point where I thought that doing nimber calculations was really crucial. I also wrestled with the idea of computing nim-values of a given position using a computer. Like Antony, I decided that this would be cheating. HOWEVER, as my understanding of the game matured, I found that I wanted to calculate nimbers much less! I got a much better overview of the game and realised that in fact one only really needed to understand which “class” a region was in. Here are examples of regions.

1) There is no chain here, i.e. neither player can force one if the other one decides he doesn't want one. Then the nimber is either 0 or 1 depending on a parity condition, and you can easily compute it by just playing the region out until it vanishes and seeing whether an even or odd number of moves were played.

2) There is exactly one chain here, i.e. either player can force 1 chain even if the other player decides he doesn't want a chain. Again the nimber is 0 or 1 and again you just play it out until there are no more moves left and again it's a parity issue.

[More generally, (1) and (2) are special cases of the situation where there is a number n such that “the position is n chains” in the sense that if either player wants there to be n chains, the other cannot stop there being n chains. In all these situations the nimber is 0 or 1 and can be computed by simply counting the number of moves left (0 for an even number, 1 otherwise: note that parity of nimber is nothing to do with parity of n: nim is different to chain-counting and the reason it works is a global argument (Euler's formula basically)).]. This class of positions are the “decided” positions and their nim-value is easy to count.

3) The number of chains is undecided (i.e. the next player to move can force there to be an even number. Of course this is much more interesting, and where nimbers come into their own. But in fact, perhaps surprisingly, for most positions that come up on a 5x5 board (and I should stress that my experience is 100% coming from playing on the standard 5x5 board), **again computing nimbers is a parity issue**. For what happens in practice is that, almost always, the nimber of the position alternates between 2 and 3 as moves are made which keep the region undecided, until eventually there are no more “beating about the bush” moves and someone *has* to decide something (i.e. the next move turns the region from an undecided number of chains to a decided number). Then the nimber drops from 2 to either 0 or 1 (and which it is can be computed by a parity count as above). In particular, **the moment before the region is decided, it has nimber 2**. Take for example an Icelandic 2x2. This has nimber 2. When I was just learning about nimbers, I thought the proof of this was “do a long paper and pencil calculation”. But I now see that this region is *obviously* nimber 2 because for each move played in the region, either it decides the region (the standard corner move forces a chain, the sacrifice kills the chain) or it can be met with a response which does not decide the region but for which there are no waiting moves left.

In particular, for any undecided region, it almost always has nimber 2 or 3, and again this can be computed by hand by just counting the number of moves that can be made until someone _has_ to decide the region. For example in the Icelandic 2x2 you can squeeze 2 more moves in until someone has to make the key decision, so nimber is 2.

Now the disadvantage of this hugely easy method is that it basically assumes all nimbers are at most 3. This is not always true. But it is almost always true, and I simply learnt the very few regions that came up in practice which had nimber 4, which I discovered with the nimstring calculator when analysing games on a computer after they had finished. The most common example is an Icelandic 3x2 with the “middle” edge played.

nimber computing is I agree a science, and the C++ program will always get it right. What I am trying to suggest above is that there are much simpler methods that almost always work and that were good enough in practice for me. In particular the first skill you should try and learn is to be able to decide whether a given region has nimber in {0,1} or {2,3,4…}. This is crucial because it tells you whether you can assume, for the sake of chain counting, that the region is a fixed number of chains or not. I learnt how to do this by simply playing a lot and seeing the common regions that came up and learning the answer. After a while though it became pretty much second nature. And to be honest, to a large extent one doesn't really need to know nim-values after that. If one understands the interplay between nim and chain-counting (which is subtle but which I've just tried to outline above) then I think this is enough in practice.

Good to see you still actively contributing, bogbrush. If you monty-python your collapse of the 2-or-3 region enough times, such that you come up with 2 different parities, then I guess you presume it's nimber is 4 and draw no firm conclusion about its chaininess?

Hey Phil. I've been lurking a lot recently because it was the climax of dots and boxes ch1. Congratulations on being the unique person to beat the champ! Also congrats to michael for regaining his crown. I agree that if you can reduce the region to either 2 or 3, as well as being able to decide it, then the nim-value is at least 4. But somehow in practice, on a 5x5 board, we are now moving away from reality and into pathology. I guess what I'm saying is that perhaps some version of what you're saying really is true but in practice (a) it doesn't seem to happen much on a small board and (b) even when it happens it might not be that relevant. Somehow if a nim-value is at least 4, and nim is important, then it's almost vanishingly unlikely that there will be another nim-value of at least 4 on the board, so if it really is about nim then just decide the region with value at least 4!

@Thnikkaman: I think I wrote some things about nimbers at wccanard.wetpaint.com a while ago, but I'm not sure if I wrote some coherent explanation of the phenomenon above.

Another interesting dichotomy in dots and boxes is what happens when a region with value 2 gets decided. Again in practice, and I don't really understand why, it is often the case that there is a move that takes 2 to 0 and which does not involve a sacrifice, whereas the move taking 2 to 1 often does involve a sacrifice. I also found it helpful to remember the smallish list of positions I knew where this was not the case, the simplest example being: on a 5x5 board, draw in 5 lines to make a big vertical line of length 5 cutting off a 5x1 area. Now in this 5x1 area, draw in the second and third and 5th vertical line. The resulting region has nimber 2 but it's the sacrifice that takes it to 0. Somehow recognising when such a region was going to appear sometimes made calculations a bit easier. I've not played seriously for so long that I'm forgetting the tricks though :-(

An Edit to the above posts of mine:

“3) The number of chains is undecided (i.e. the next player to move can force there to be an even number.”

should say

“3) The number of chains is undecided (i.e. the next player to move can force there to be an even number, and can also force there to be an odd number.)”

A nimstring calculator is available from my dots and boxes page at

http://mysite.verizon.net/vze16nctz/DotsBoxes/db.html

I was wondering, in general, what the rules are on using outside resources on Little Golem. I've been assuming that we are allowed to use books like “38 Basic Joseki”, Batsford Chess Openings, and Winning Ways. But not chess computers. But what about things that are in between:

Can one look at databases of pro games? Databases of one's own games?

In particular, what about David Wilson's 4x4 D&B openings page:

http://wilson.engr.wisc.edu/boxes/result/4x4.html and the six pages that are linked from there.

I'd assume no, but only barely – and I can't justify it logically. And what if someone stored it as a pdf, or actually printed it beforehand?

In any case, I think there should be at least one FAQ on this subject.

Should we escalate this to the main forum page?

The are really no rules I think, since everyone just plays for fun. I am not saying that there shouldn't be rules, but I don't think there are any.

As I will have the Icelandic 3x2 with the middle edge in my game with aldiris I came back to this thread. I like to give an answer to William:

I think as a human player, playing turn based, it should be allowed to use every database u check manually. In my understanding u should be allowed to read everthing u like to and study as long as u want. U should not use any program to help in this process. Yeah bit strange: looking up the nim value in a book should be allowed, getting it by a calculator shouldn't.

Yes, we have no rules for that, Christian. And I think we donot need to. E.g. In Dvonn we had several Champions in the past using endgame calculators. They all vanished with the time. The fun only stays if u play completly on ur own.

I spend much more time for games I am weak in than for my better ones. In Dvonn or Amazones I never use more than a minute for a single move, but in connect6 or dots&boxes I try to burn my head via 10 minutes. Just because improving is the most fun imho.