Impartial Combinatorics in a Bowling Puzzle

Puzzle

I came across a game theory problem https://www.hackerrank.com/challenges/bowling-pins/problem where one has to find whether the game can be won, given a starting position. There are some constraints:

• Both players will play optimally

• The game cannot end in a draw

• There are finite moves to be played

This is a bowling setup; at every turn, each player can either knock down one pin or two adjacent pins.

Min-Max Analysis

By looking at the problem, I thought of a brute force solution to compute the gametree for all possible moves and then evaluate from the leaf node to the starting position. This is an exponential solution and did not run within the time limits. If the number of pins is N, then the time complexity is:

$$O(2^N)$$

I implemented a couple of optimizations, including pre-computing the Game-Tree up to 5 pieces on the board, memoization of the boards, and evaluating the mirror configuration of the board as the same. None of this helps.

Found a pattern for slightly modified rules; Irrelevant to the problem

I considered the following rule change: given a continuous chain of pins and the constraint that you can knock pin/s on the edge, who would win?

Let’s compute the series:

$$f(0) = 0$$

$$f(1) = 1 $$

$$f(2) = 1 $$

$$f(3) = 2$$

We see a pattern from here: for the starting player to win, the game must end in an odd number of moves. F(n) can be followed by F(n-1) or F(n-2), depending on the number of pins knocked. This would mean that for every F(3n), the game would end in a loss for the starting player if both players play optimally.

Sprague-Grundy Algorithm

I found this amazing playlist on Grundy Numbers applied on Chess - https://www.youtube.com/playlist?list=PLj6WGJe-RmYZ-yHrobuCZVjaKHpXTxZOJ

We can use Bouton’s theorem to rephrase the problem as a nim pile. A group of consecutive pins is a single nim pile, and once the sequence is broken, they become independent nim piles.

All we have to see is if the nimsum of the pile is not zero, and for that, we must evaluate the Grundy number of each pile, which can be done recursively or bottom to top.

The approach is similar to chess with the King piece only, where we compute the Grundy numbers starting from the terminal positions, which would have a value of 0.

Solution

This is the top submission, and it is elegant and simple.

#include <cmath>
#include <cstdio>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;

const int Maxn = 305;

int nim[Maxn];
int t;
int n;
char str[Maxn];

int main() {
    for (int i = 1; i < Maxn; i++) {
        set <int> S;
        for (int j = 0; j < i; j++)
            S.insert(nim[j] ^ nim[i - 1 - j]);
        for (int j = 0; j + 1 < i; j++)
            S.insert(nim[j] ^ nim[i - 2 - j]);
        while (S.find(nim[i]) != S.end()) nim[i]++;
    }  
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        scanf("%s", str);
        int res = 0;
        for (int i = 0; i < n; i++) if (str[i] == 'I') {
            int j = i;
            while (j < n && str[j] == 'I') j++;
            res ^= nim[j - i];
            i = j;
        }
        printf("%s\n", res? "WIN": "LOSE");
    }
    return 0;
}