I've been looking at a variant of NIM.

You can skip this bit where I'll describe NIM as usually described:

There's a starting position with some number of piles of counters and two players alternate taking any number of counters from any single pile. In "normal play" the player who takes all of the last non-empty pile wins. In "misère play" the player forced to take the last pile loses. That pile will always be of size one, since otherwise a perfect player would take all but one counter from the last pile and force the other player to take the lone pile of one.

A "P-position" in a game is one where the previous player has a forced win, and the person playing next from that position will lose against a player executing the strategy without error.

The variation I'm exploring is to broaden the winning conditions into "the first player to reach any one of a set of positions." In other words, there's a specified set of "seed" P-positions.

The classical normal game seed set for three piles can be recast as {[0,0,0]}; the winning player is the one to reach the state where all the piles are empty. The classical misère game seed set is {[1,0,0],[0,1,0],[0,0,1]}. Plays that make no win possible are not legal: So for example, if {[1,4,2],[3,5,3]} were the two target winning positions, a move from [17,21,5] to [17,3,5] would be illegal.

Both classical normal and classical misère NIM have perfect strategies that are fairly compact to describe, but looking at other sets of seed P-positions, that seems to be a rarity.

Given a game with some set of seed P-positions, what is that set of all P-positions for that game?

Has this already been studied?

Even the set of P-positions for {[0,0,0],[1,0,0]} looks chaotic. The solid edges are [0,n,n], [n+1,0, n], and [n, n+1, 0]. Those are all P-positions.

NIM P-positions for up to 64 counters and targets {[0,0,0],[1,0,0]}.

For {[0,0,0],[1,0,0]} the set of P-positions looks like a hollow tetrahedron, with the sides slightly caved in. Cross-sections of the P-positions with the same number of counters thus look like slightly caved-in sparse triangles. The dense and sparse regions are somewhat coherent as the number of counters changes, but the seeds remain fixed. This makes the whole set of P-positions look like a collection of fans, rooted at [0,0,0].

This is a cross-section of the tetrahedron, showing all the P-positions with 250 counters and targets {[0,0,0],[1,0,0]}.

NIM P-positions for exactly 250 counters in three or fewer piles and targets {[0,0,0],[1,0,0]}.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.