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.
Little Golem