Nim problem?

Can player1 win this game:

http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5

he is one off, and three chains are forming...

can he play Nim here as there are no quads?

"At the request of the survivors, the names have been changed. Out of respect for the dead, the rest has been told exactly as it occurred."

Link:

http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5

17.c2?

18.b9 shouldnt work due to 19.c10

nevermind, i was too hasty. 19.c10 doesnt work because of 20.g8.

i'll take a better look at it once i get home.

You are right on 19.c10 being an answer to 18.b9 and no 20.g8 sacrifice is a bit too costly.

Oh yeah, took me a while to see why 20.g8 doesn't win.

I guess that 18.b11, a move that changes nim-values similarly to b9, is winning after c2, since 19.c10 doesn't work here as it builds a chain and 19.d11 doesn't seem to work either due to 20.i2 forcing many sacrifices.

Okay, my next guess is 17.h1

http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5h1a8a2k2c10d11i2g2d1f1b1g8f9i8h11g10i10b7b9a4k10b11a10b3c4c2f3e4e2a6c6d7d9f11e10j11

http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5h1a8a2e2f1d7c6d9c10b7b9a6j7i6h5j3i4f9g8j9i8f11e10d11g10b3

http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5h1g2i2c2b9c10g8f9i8f11f1h11g10e10i10d11d9c6d7j9j7i6h5j3i4b3a2b1j1k2k10j11b11a10b7a8a6a4

http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5h1g2i2c2b11a8f1a10b9c10b7d11g8f9i8a6c6d7e10d9j9j7i6h5j3i4h11g10f11i10b3a2b1k10j11k2j1d1

I'd be lying if I said that I expect this to be right, I just need a break from analysing since this took me a while so here's some results from in between.

Okay, I noticed that 17.h1 is like the most stupid line possible since it renders both a2 and c2 useless which is exactly what happens to the top left region when 18.j9 is played (b11 and b9 become useless due to c10 just like before) so that isn't making any sense at all.

I'm getting some Dextro Energy and then try again ._.

I tried to narrow it down:

a6, b7, a4, b3 // build chains which is not an option

g8, d7, e4 // are sacrifices = probably dumb

c2 -> b11 // already gone through

b11 -> c2 // already gone through

h1 -> j9 // already gone through

j9 -> h1 // already gone throughg2 -> e10 // trivial

e10 -> g2 // trivial

b9 -> j9 // c10 or e10 vs h1 or i2

i2 -> b11 // same reason why c2 loses

a2 -> b11 // same reason why c2 loses

f1 -> j9 // f1 prevents a2/c2/i2 which is why j9 should win

c10 -> h1 // http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5c10h1b9e2g8f9i8g2i2d7d9c6i10g10h11c4e4f1f3a2b3a4k2k10b11a10e10d11f11b7a8a6c2b1d1j11

d11 -> h1 // http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5d11h1c2f1g8i8f9g2i2d7d9c6a8b7b9a6b11c10a10e10

a8 -> h1 // http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5a8h1c2f1

d1 -> j9 // b9, b11 useless even though necessary

Alright, I checked all these (although not quite elaborately) and I think they all lose. That means it's probably one of these: f11, g10, h11, i10, j11, k2, "no solution exists". These seem hard to disprove though and I'm tired for now ._.

What a work!

I agree with your analysis, except for :

17.b9 18.j9 what after 20.e2 ?

and of course that was 19.e2:

http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5b9j9e2

Oh, this is interesting. I noticed that I totally forgot to take a look at e2 and now that you have shown me the move I feel like that's most probably the one winning move which is funny, because it was indeed absolutely coincidental that I forgot to analyse e2 and never really took a look at it.

Ok, so maybe this is a good time to explain what I was actually doing the whole time. I was mostly trying to categorize all moves (sacrificing and chain building moves not included) into two different groups and this is how I classified them:

Group 1 contains: a8, c10, d11, j9 from the top area and d1, f1, h1 from the bottom area.

Group 2 contains: b9, b11 from the top area and a2, c2 and i2 from the bottom area.

and then I had a leftover group for everything else:

Leftover-Group contains: e10, g2, f11, g10, h11, i10, j11, k2 and I would have put e2 into it as well if I hadn't overlooked it.

So my theory was that if 17th move was from Group 1 then the 18th move had to be from Group 1 as well, but from the other area, so if you look at all these counters to the moves I have tried to prove wrong then you will see they are all from the same group as the move they counter, e.g. I wrote "f1 -> j9 // f1 prevents a2/c2/i2 which is why j9 should win" and f1 and j9 are from the same group.

The one exception where I didn't do that was b9. b9 and j9 are not from the same group so I'm not really surprised that this is the one move I've failed to disprove correctly. Now the reason why I didn't choose a counter from the same group as b9 was that 17.c2 18.b9 was winning for player 1 (see post 3) and this kinda confused me and then I went crazy trying other things not related to my theory so somehow I chose 18.j9 to counter it. The reason why I chose j9 was that I wanted to neutralize the effect of b9 (and yes there was no reason to do that, but I did it anyways since I went crazy as mentioned). After 17.b9 18.j9 there is the moves c10/d11 and e10 which determine the "nim-type" and c10/d11 are from Group 1 while e10 is in that position from Group 2 so we still have that decision of "from what Group do we want to play a move in the top" just like before 17.b9 — and that's actually the trait of the moves from the Leftover-Group too: after playing a move from the Leftover-Group there's still moves from both Groups playable. Well anyways, after 17.b9 18.j9 we get a kind of similar position as the one before those two moves and you just told me that 19.e2 is winning here so I think you kind of served me the solution on a silver platter since that makes it most likely that e2 is also winning in the position with 16 moves.

Ok, so I said I would put e2 into the Leftover-Group and as I mentioned before the trait of the moves from the Leftover group was that you could still play moves from both Groups afterwards. After 17.e2 you can play 18.i2 which is from group 2, but you can also play f1 which is a move from group 1, so that's why I would've put it into the leftover group. Based on that I would try to counter e2 with e10 since it's also from the leftover-group but after playing it out you kind of notice that it's not quite working:

http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5e2e10f11h11j9j11k2c2d1b1

Player 2 has to play the determining move here and loses.

So yeah, that Leftover-group doesn't seem to work that well since it seems there is many moves that don't fit in group 1 or 2 but are still very different from each other. I already knew this though: my not-on-math-but-visual-traits-based approach to nim sucks when it comes to regions with higher nimvalues :D.

And now I would be very embaressed if 17.e2 is not the winning move after all. xD

Thanks a lot for sharing your thought process, this is very interesting to classify moves into equivalent or pseudo-equivalent categories and I think it works well for low nim values. Here the nim values are huge with *14 for initial position and even some options with value *15.I will try to post a drawing with the values of all the options, even if it is not so meaningful as some non-zero options can be played because their *0 option is a costly sacrifice which can't be played by player1 which is already one box back and the chains will be too short for keeping control to give a win.

17.e2 of nim value *12 is not a solution because of 18.a6,for example: http://www.trmph.com/dnb/board#5,f5d5f7h7g4e8e6g6k4j5k6c8d3h9k8h3b5e2a6d11h1a4j11j7, 18.a6 is not an *0 but the only *0 answer is the sacrifice 19.e4

The other question which is still unanswered is :if the answer to 17.b9 is not 18.j9 (because of 19.e2), what could be a possible answer?

On 17.b9 I would try c2 which we know doesn't work and i2 as well as a2. So my next quick guess would be i2 and if that doesn't work I'd try a2 next. Again, because these are from the same group as b9... although I feel like my theory has been shattered a little bit.

After 17.b9, 18.i2 will not work because of 19.d11, but 18.a2 is all right, so is 18.j11 from the leftover group.

Oh wow, I made a very crucial mistake in how I classified 17.b9... that move doesn't belong to Group 2 but to the Leftover-Group. I thought b9 was doing the same thing as b11 regarding nim but due to d11 that's not true (b11 is not affected by d11 since that's building a chain but after b9 it doesn't). Hm, I don't think this affects any other move but I'll revise my classifications just in case... I might try to split the leftover group as well.

It's also funny that 18.a2 wins after 17.b9 because I originally thought that would win in a game of nim where captured boxes don't matter, but now it turns out it doesn't (because of 19.d11), but still wins.

The shark has an opinion:

Player 2 is winning.

After 17. e2, 18. a6 and player 2 is ahead by 3 points.

Program time? Okay, I recreated those equivalence-groups with the help of a program and they look like this:

Group 1 contains: a8, d11, j9, h11 | d1, f1, h1

Group 2 contains: b11 | a2, c2, i2

Group 3 contains: e10, i10 | g2

Group 4 contains: c10 | e2

Group 5 contains: b9 |

Group 6 contains: g8 | h11, j11, k2

Group 7 contains: a6, b7 | a4, b3

Group 8 contains: d7, f11, g10 | e4

So basically if 17th move is on the left side of the "|" then 18th move must be from the same group but on the right side of the "|" in order to win Nim (where captured boxes don't matter) and the other way around.

As someone who isn't very good with nimvalues in the form of actual numbers but would still like to widen his understanding I was wondering if moves from the same group also result in positions with equal nimvalue? (I don't have a program that calculates concrete nim-values)

What about h11 which I put into two different groups?

Here are the nim values of the options:

I just want to say, that you guys are awesome! I love your work towards the game, and the work that you put into it. I'd love to learn what you do in your analysis, and how to figure out the best possible move. My playstyle is based purely on board control. I just like to play by the chain rule and work loops to my advantage. I've just started to remember how I used to play, and it's all coming back to me. Anything you guys can teach me, I'd love to listen. Thanks again guys, you're great.

Think you for the comment and the_Shark analysis which I d'id not even bothered to do.

The questions posed by that problem were more about the efficiency of nim analysis of innocuous looking positions where no quads nor 6-loops are present.

How is it that the Grundy number is so high here being *14 ?

How is it that the *0 answer b9 is countered by a move of high value like j11 ?

How is it that Purgency without software managed to group positions on their similar flavor (Grundy value ?) and that these options have similar groups of answers?

Can there be on 5x5 positions of values greater than *15 ?

Think -> Thank

I just brought out my nimstring calculator, and I can answer some of Caroll's questions.

First, I believe there is an inaccuracy in his diagram and that d11 should be "4" instead of "3" can anyone verify this?  (Actually, purgency already did.)

The first thing to notice is that the top and bottom can be computed separately, since a play on the chain which connects them is loony, and will never be played, except by the losing player.  (Note that this is not necessarily true in dots and boxes, but is true for computing the nim value.)

1.  The top half has a nim-value of *9, while the bottom has a nim-value of *7.  (To compute the nim-value of a position in the top half, add *7 to it.  To compute the nim-value of a position in the bottom half, add *9 to it.  Knowing that it is *9 and *7 -- as opposed to *8 and *6 -- required the use of software).  The nim-sum of these two values is *14.

2.  I don't know.  That's a question for philosophy..... (Although it is worth noting that it is also countered by the relatively low numbered b11 and h11, as well as b1, f1, g2, and j1).

3.  For his second break-down, he did use software.

To answer his question about h11, I note first that every other group consists of playing the top to some value and responding by playing the bottom to the same value (or vice versa), such that the nim-sum is zero.

If a play is made in the top, it is, at least sometimes, possible to play again on the top so as to reach a value of *7.  In the case of playing the top to *8 (j11), the response must be in the top, as there is no way to play the bottom to *8. g8 + h11 is the only other pair of moves which results in a *7.

4.  I'm not sure.  I know that I was amazed be the nimber possible in 3x3.  I think it is *13!

Therefore, I suspect *16 is possible, but I couldn't even find a reference to the value 3x3.