Getting Stuck: The Stone Game That Wouldn’t Let Me Go

One quiet evening, I found myself thinking about a very old type of problem in computer science and mathematics: two-player impartial games. The idea is simple — players take turns making moves until no move is possible, and the one who can’t move loses.

I thought: Let me write some code to analyze one of these games. How hard could it be?

The Setup

I picked a variation of the Stone Game:

There’s a pile of N stones.
Two players alternate removing stones.
On each turn, a player can remove 1, 3, or 4 stones.
The player who takes the last stone wins.

A classic "take-away" game.

My goal was to write a program that, given N, tells me whether the first player has a winning strategy.

Attempt 1: Brute Force Recursion

I started with recursion. Define a function win(n) that returns True if the current player can force a win from a pile of size n.

def win(n):
    if n == 0:
        return False
    for move in [1, 3, 4]:
        if n - move >= 0 and not win(n - move):
            return True
    return False

for i in range(1, 11):
    print(i, win(i))

It worked beautifully for small n. The output alternated in an interesting way:

1 True
2 False
3 True
4 True
5 True
6 False
7 True
8 True
9 True
10 False

So some positions were winning, others losing. I thought I’d cracked it.

Then I tried n = 50.

The recursion slowed to a crawl.

Attempt 2: Memoization

The problem was obvious — overlapping subproblems. I slapped on memoization.

from functools import lru_cache

@lru_cache(maxsize=None)
def win(n):
    if n == 0:
        return False
    for move in [1, 3, 4]:
        if n - move >= 0 and not win(n - move):
            return True
    return False

Suddenly, n = 1000 was trivial. Nice.

But then I asked myself a deeper question: Is there a pattern? Can I characterize all losing positions without brute force?

The Red Herring: Looking for Modular Arithmetic

From earlier exposure to Nim, I suspected the answer was something like: The losing positions are those where n mod k == r for some k and r.

I tried plotting the losing positions up to 50:

2, 6, 10, 14, 18, ...

They looked evenly spaced! Every 4 steps. So I conjectured:

Losing positions are exactly those where n % 4 == 2.

I quickly wrote a checker:

losing = [i for i in range(1, 51) if not win(i)]
print(losing)

But the output shattered my guess:

[2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50]

Wait — that is n % 4 == 2. My guess was correct!

So why did I feel uneasy? Because I realized I’d gotten lucky. In general, the move set [1, 3, 4] happens to give a clean modular pattern. With [1, 4, 5], the sequence looked chaotic, no obvious periodicity at all.

I was stuck again: how do we generalize this?

Attempt 3: Sprague–Grundy Theory

After circling around for a while, I remembered something from combinatorial game theory: Sprague–Grundy values.

The rule is:

Each position is assigned a Grundy number (a nonnegative integer).
Terminal positions (no moves) get 0.
A position’s Grundy number is the mex (minimum excluded value) of its children’s Grundy numbers.
A position is losing if its Grundy number is 0.

So I rewrote my code:

def grundy(n):
    if n == 0:
        return 0
    moves = [1, 3, 4]
    next_states = [grundy(n - m) for m in moves if n - m >= 0]
    g = 0
    while g in next_states:
        g += 1
    return g

for i in range(15):
    print(i, grundy(i))

The output was fascinating:

The zeros matched the losing positions perfectly!

The Breakthrough

Suddenly everything clicked:

My recursive brute force was really just computing Grundy numbers implicitly.
The memoization speedup was essentially dynamic programming.
The modular pattern I noticed was a special case of a deeper periodicity in Grundy sequences.

By reframing the problem in game theory terms, I wasn’t just coding a solver — I was rediscovering the mathematical structure beneath the game.

Reflection

This was one of the hardest “Getting Stuck” journeys I’ve had:

I started with naive recursion and hit performance walls.
I was seduced by modular arithmetic patterns (which only sometimes work).
I nearly drowned in brute force again.
Only by recalling Sprague–Grundy theory did I escape the loop and see the general solution.

That’s the beauty of these puzzles. They lure you in with toy examples but force you into deeper theory.

And once again, getting stuck was the only way I could really learn.

Arya’s Algorithms

Search This Blog