Sprague–Grundy theorem / Game of nim / Bowlingpins hackerrank

I've been trying to solve this problem in HackerRank called Bowling Pins. Basically you have to code a program that predicts who will win and who will lose. The rules of the game are:

Bowling pins are position horizontally and they are represented as a string of capital i's --> "IIII" (4 pins)
You can either knock down one single pin "I" or two pins that are next to each other "II"
"X" will represent the pins that are knocked down
Last player to knock down wins

Given the string "XIIX", this is a win, since I can knock down the two middle pins.

Given the string "IXIX", is a lose, since the next player will make the last move

Now, I tried to get a basic understanding of combination game theorem. I know that I have to calculate the mex and grundy in order to know who wins and who loses without actually playing the game.

Now my question is if I have three pins "III" mex {1,2} = 0 , this means a lose. But what happens in the case that I knock down the single middle pin? The next player turns will look like this "IXI", he/she can either knock down the left or the right pin, regardless I get the last pin and win. right?

I'm very new to these concepts and I'm not sure if I'm implementing the Sprague–Grundy theorem correctly for this game. Can someone explain this to me?

Here's a link to the problem I'm trying to solve --> https://www.hackerrank.com/challenges/bowling-pins/problem

Solution

I think this document has a really good explanation of the relevant theory: https://web.mit.edu/sp.268/www/nim.pdf. Personally, it took me a bit to get through the document; at first I just tried reading, but I got much more out of it by writing some of the lemmas/theorems down and practicing a bit myself. I think the graphs under "From Games to Graphs" and "The Sprague-Grundy Function" sections were particularly helpful for this problem.

Here's how I started thinking about it: a set of pins is a game position. Each game position is either terminal or has followers, which are other game positions that can be moved to. Each game position can be assigned a Sprague-Grundy (SG) based on the SG values of its followers. Now try creating a graph of game positions:

The only terminal position is no pins left, which we can write as X or XX or however many X based on the number of pins you start with. This position has SG(X) = 0 because it's terminal.
The game position I can have one pin knocked down, which would make it X. So X is a follower of I, and SG(I) = mex{SG(X)} = mex{0} = 1
The game position II can have either one pin knocked down, making it XI == IX == I, or two, making it XX == X. So it has these two followers, and SG(II) = mex{SG(I), SG(X)} = mex{0, 1} = 2.
Now let's look at III, since this is where we get to start using some of the other information from the document. The followers are XII (SG of 2), XXI (SG of 1), and IXI. For this last one, we could see that it only has one follower and get the SG like that, OR we could use the Sprague-Grundy theorem. This says "the SG function for a sum of games on a graph is just the Nim sum of the SG functions of its components". For IXI, it has two games of I, each with SG of 1. When we take the nim sum (xor the binary representations), we get 0. So in conclusion, SG(III) = mex{2, 1, 0} = 3.

And you can keep going bottom to top to get other SGs by taking 1 or 2 II away at a time and calculating nim sums.