Main Answer
In place of a explicit strategy, it suffices to give an efficient way to tell which positions are winning positions (from which the next player has a move that can force a win) and which are losing positions. Then the strategy is simply to move to a losing position when you are at a winning position (there are at most fourteen moves to check).
On the subject of whether this game can be called a variant of $\mathsf{Nim}_k$, that seems to me to be completely a matter of opinion. I'm personally fine what that.
Winning/Losing Positions
Through a bit of computer experimentation, we can see that for large enough heaps (say, when the largest two heaps have size at least $5$), the losing positions are precisely those where the sum of the heap sizes is a multiple of $3$. For smaller heaps, there are some sporadic exceptions to this, but there are still patterns based on the remainder upon division by $3$.
Certainly, if there is only one nonempty heap then the position is a losing position by definition. From now on, we will only consider positions with at least two nonempty heaps.
If the sum of the heap sizes is a multiple of $3$, then the position is a losing position unless the smallest three heap sizes (in increasing order) fall into one of the following eighteen cases:
$$\begin{matrix}
(0,0,1) & (0,0,2) & (0,1,1)\\
(0,1,2) & (0,1,3) & (0,2,2)\\
(0,2,3) & (1,1,1) & (1,1,2)\\
(1,1,3) & (1,2,2) & (1,2,3)\\
(1,2,4) & (1,3,3) & (2,2,2)\\
(2,2,3) & (2,2,4) & (2,3,3)
\end{matrix}$$
If the sum of the heap sizes is $1$ more than a multiple of $3$, then the position is a winning position unless the smallest three heap sizes are $(1,1,1)$. In other words, the only losing positions where the sum of the heap sizes is $1$ more than a multiple of $3$ are of the form $(1,1,1,3n+1)$ for some $n\ge0$ (or a reordering thereof).
If the sum of the heap sizes is $2$ more than a multiple of 3, then the position is a winning position unless the smallest three heap sizes fall into one of the following six cases:
$$\begin{matrix}
(0,1,2) & (0,2,2) & (1,2,2)\\
(1,2,3) & (2,2,2) & (2,2,3)
\end{matrix}$$
Proof
Notation
A position corresponds to the list of heap sizes, as $(n_1,n_2,n_3,n_4)$. And an "option" is a position that can be reached in one move.
Since a position is isomorphic (game tree) to the same position with the heap sizes reordered, it will be convenient to order the heap sizes. Using angle brackets, as in $\langle m_1,m_2,m_3,m_4\rangle$, will mean that this has already been done: $m_1\le m_2\le m_3\le m_4$. With this notation, we can say things like "The options from $\langle 2,2,2,2\rangle$ are $\langle 1,2,2,2\rangle$, $\langle 0,2,2,2\rangle$, and $\langle 1,1,2,2\rangle$." and "In the position $\langle1,2,3,x\rangle$, we know $x\ge 3$.".
Also, we will use the standard notation of $\mathcal N$- and $\mathcal P$-positions to denote the positions where the Next player to move has a winning strategy, and the ones where they do not (so Previous wins), respectively. For example, $\langle0,0,0,3\rangle$ is a $\mathcal P$-position since the player whose turn it is cannot make a move. $\langle0,0,1,7\rangle$ is an $\mathcal N$-position since the next player can win by moving to $\langle0,0,0,7\rangle$ (or $\langle0,0,0,6\rangle$). Finally, $\langle0,0,3,3\rangle$ is a $\mathcal P$-position since every move turns at least one of the nonzero heap sizes into $2$ or $1$, which the opponent can then eliminate to win.
Instead of "type of position" or "position type", we will use the standard term "outcome", as-in "the outcome of $(0,0,3,3)$ is $\mathcal P$. Of course, the winner under poor play may not match with the "outcome" in this sense.
Outline
The main idea is to calculate the outcomes of finitely many positions, and then prove a couple lemmas that say that the apparent patterns will continue forever. This is very similar to the idea and applications of the Octal Periodicity theorem, but this game is different from an Octal Game so the theorems are new.
As mentioned above, "most" positions are in a stable range following a very simple "typical" rule: $\mathcal P$ exactly when the sum is a multiple of $3$, so one lemma will say that that pattern propagates itself.
However, when the smallest three heaps are sufficiently small, there can be a different sporadic period-three pattern, which includes infinitely many counterexamples to the typical rule. We will need a separate theorem to reduce those patterns to finitely many base cases.
Preliminary Notes
Note that a position is an $\mathcal N$-position exactly when there is an option that is a $\mathcal P$-position. As a corollary, the outcome of a position is determined directly by the outcomes of its options. In the case where there are no options because there is only one nonzero heap, then there is certainly no $\mathcal P$-position option, and the position is still a $\mathcal P$-position.
As an aside, the original question post doesn't raise the issue of what type of position $(0,0,0,0)$ should be. The answer to that doesn't affect any of the other positions: $\langle 0,0,0,n+1\rangle$ is a $\mathcal P$-position by definition, and $\langle 0,0,1,1\rangle$ is an $\mathcal N$-position by virtue of having $\langle 0,0,0,1\rangle$ as an option.
Non-interference Note
For any $z\ge x_3+2$, the options of $\langle x_1,x_2,x_3,z\rangle$ are the same except for their largest heaps, which always have size $z-2$, $z-1$, or $z$. Furthermore, the only options of such a position with the same smallest three heaps are $\langle x_1,x_2,x_3,z-1\rangle$ and $\langle x_1,x_2,x_3,z-2\rangle$.
For a concrete example, if $z\ge5$, then starting from $\langle 1,3,3,z\rangle$, the options are always:
$$\begin{matrix}(0,3,3,z)\cong\langle 0,3,3,z\rangle & (0,3,3,z-1)\cong\langle 0,3,3,z-1\rangle \\(1,2,3,z)\cong\langle 1,2,3,z\rangle & (1,2,3,z-1)\cong\langle 0,3,3,z-1\rangle \\(1,3,2,z)\cong\langle 1,2,3,z\rangle & (1,3,2,z-1)\cong\langle 0,3,3,z-1\rangle \\(0,2,3,z)\cong\langle 0,2,3,z\rangle \\(0,3,2,z)\cong\langle 0,2,3,z\rangle \\(1,2,2,z)\cong\langle 1,2,2,z\rangle \\(1,1,3,z)\cong\langle 1,1,3,z\rangle & (1,3,3,z-1)\cong\langle 1,3,3,z-1\rangle \\(1,3,1,z)\cong\langle 1,1,3,z\rangle & (1,3,3,z-2)\cong\langle 1,3,3,z-2\rangle \end{matrix}$$
Stability Lemma
Suppose that all of the options of a position $G$ are known to follow the typical rule ($\mathcal P$ exactly if the sum is a multiple of $3$), and that $G$ has at least two heaps of size at least $2$. Then $G$ follows the typical rule as well.
Proof:
Note that the sum of the heap sizes decreases by $1$ or $2$ with each move. If the sum of the heap sizes of $G$ is a multiple of $3$, then it can only move to $\mathcal N$-positions, so is a $\mathcal P$-position. If the sum is not a multiple of $3$, then since $G$ has at least two heaps of size at least $2$, the next player can remove $1$ or $2$ from the total to reach a $\mathcal P$ position, so $G$ is an $\mathcal N$-position.
Stability Corollaries
Similarly to the non-interference note, for any $y,z$ with $x_2+2\le y\le z$, the only options of $\langle x_1,x_2,y,z\rangle$ with the same smallest two heaps would have smallest three heap sizes $(x_1,x_2,y-2)$ or $(x_1,x_2,y-1)$. (This is true even if $z=y$ or $z=y-1$.)
Because of this, we can specialize the assumptions of the stability lemma a bit. Suppose that:
- $0\le x_1\le x_2 \le x_3$
- Positions of the form $\langle x_1,x_2,x_3,a\rangle$ follow the typical rule.
- Positions of the form $\langle x_1,x_2,x_3+1,a\rangle$ follow the typical rule.
- For each nondecreasing pair $(z_1,z_2)$ that can be reached from $(x_1,x_2)$ by removing one or two items, $\langle z_1,z_2,x_3+2,a\rangle$ follows the typical rule.
- For each nondecreasing pair $(z_1,z_2)$ that can be reached from $(x_1,x_2)$ by removing one item, $\langle z_1,z_2,x_3+1,a\rangle$ follows the typical rule.
Then the positions of the form $\langle x_1,x_2,x_3+2,a\rangle$ follow the typical rule.
Corollary 1: In fact, we could apply this repeatedly to determine that all positions of the form $\langle x_1,x_2,b,a\rangle$ with $b\ge x_3+2$ follow the typical rule.
We can do similar things with shorter prefixes to get
Corollary 2: Under appropriate conditions, all positions of the form $\langle x_1,c,b,a\rangle$ with $c\ge x_2+2$ follow the typical rule.
Corollary 3: Under appropriate conditions, all positions of the form $\langle d,c,b,a\rangle$ with $d\ge x_1+2$ follow the typical rule.
Repetition Lemma
Suppose that:
- $0\le x_1\le x_2 \le x_3$
- $x_3+5\le y$
- $\langle x_1,x_2,x_3,y-1\rangle$ and $\langle x_1,x_2,x_3,y-4\rangle$ have the same outcome.
- $\langle x_1,x_2,x_3,y-2\rangle$ and $\langle x_1,x_2,x_3,y-5\rangle$ have the same outcome.
- For each nondecreasing triple $(z_1,z_2,z_3)$ that could be reached by removing one or two items from heaps of sizes $(x_1,x_2,x_3)$ and then reordering the heaps, the outcomes of positions of the form $\langle z_1,z_2,z_3,a\rangle$ are periodic with period $3$.
Then $\langle x_1,x_2,x_3,y\rangle$ has the same outcome as $\langle x_1,x_2,x_3,y-3\rangle$.
Proof:
By the non-interference note, since $x_3+2=x_3+5-3\le y-3,y$, this means that every option of $\langle x_1,x_2,x_3,y\rangle$ has a one-to-one corresponding option of $\langle x_1,x_2,x_3,y-3\rangle$ with the same smallest three heap sizes. And that the only options of either with smallest heap sizes $(x_1,x_2,x_3)$ are given by removing $1$ or $2$ from the largest heap.
By supposition 5 above, all options of $\langle x_1,x_2,x_3,y\rangle$ where the smallest three heaps do not have sizes $(x_1,x_2,x_3)$ have the same outcome as the corresponding options of $\langle x_1,x_2,x_3,y-3\rangle$. Suppositions 3 and 4 take care of the only options where the smallest three heaps do have sizes $(x_1,x_2,x_3)$, so all of the options of $\langle x_1,x_2,x_3,y\rangle$ have the same outcome as options of $\langle x_1,x_2,x_3,y-3\rangle$. As such, $\langle x_1,x_2,x_3,y\rangle$ itself has the same outcome as $\langle x_1,x_2,x_3,y-3\rangle$.
Repetition Corollary:
By applying the repetition lemma repeatedly, we can actually conclude that the outcomes of positions of the form $\langle x_1,x_2,x_3,a\rangle$ are periodic with period $3$.
Induction argument structure
We can now present a table that shows how the results above help us determine many outcomes from a finite collection of 220 outcomes that could be found by computer (or tedious human work).
Each column of the table corresponds to a largest heap size $z$ and each row corresponds to a trio of smallest heap values. The rows are presented in lexicographic order so that each position has options only in higher rows or to the left on the same row. To make following the patterns easier, the exceptional rows that do not follow the typical rule will have their label boxed. Also, to fit infinitely many rows together, variables other than $z$ are used and satisfy the inequalities that would provide new information: for example, $a\ge 5$, and $4\le e\le f$.
In the entries in the table below: $\def\x{\times}$
- $ \x $ indicates that no positions fit in that spot since the heaps wouldn't be written in increasing order.
- $\mathcal P$ or $\mathcal N$ indicate an outcome that would have to be calculated manually.
- $d$ indicates that the outcome is $\mathcal P$ by definition
- $r$ indicates that the outcomes are determined by the repetition corollary
- $s_1,s_2,s_3$ indicate that the outcomes will be determined by corresponding stability corollary once we justify that the hypotheses are satisfied later.
$$\begin{matrix}\text{min }3\backslash z & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
\boxed{\langle 0,0,0,z\rangle } & d &\cdots\\
\boxed{\langle 0,0,1,z\rangle } &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\boxed{\langle 0,0,2,z\rangle } &\x &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\langle 0,0,3,z\rangle &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 0,0,4,z\rangle &\x &\x &\x &\mathcal N &\mathcal P &\mathcal N &\mathcal N &\mathcal P & r &\cdots\\
\langle 0,0,a,z\rangle &\x &\x &\x &\x & s_{1} &\cdots\\
\boxed{\langle 0,1,1,z\rangle } &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\boxed{\langle 0,1,2,z\rangle } &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\boxed{\langle 0,1,3,z\rangle } &\x &\x &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\langle 0,1,4,z\rangle &\x &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 0,1,5,z\rangle &\x &\x &\x &\x &\mathcal N &\mathcal P &\mathcal N &\mathcal N &\mathcal P & r &\cdots\\
\langle 0,1,b,z\rangle &\x &\x &\x &\x &\x & s_{1} &\cdots\\
\boxed{\langle 0,2,2,z\rangle } &\x &\mathcal N &\mathcal N &\mathcal P &\mathcal N &\mathcal N & r &\cdots\\
\boxed{\langle 0,2,3,z\rangle } &\x &\x &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\langle 0,2,4,z\rangle &\x &\x &\x &\mathcal N &\mathcal N &\mathcal P &\mathcal N &\mathcal N & r &\cdots\\
\langle 0,2,5,z\rangle &\x &\x &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 0,2,c,z\rangle &\x &\x &\x &\x &\x & s_{1} &\cdots\\
\langle 0,3,3,z\rangle &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 0,3,4,z\rangle &\x &\x &\x &\mathcal N &\mathcal P &\mathcal N &\mathcal N &\mathcal P & r &\cdots\\
\langle 0,3,d,z\rangle &\x &\x &\x &\x & s_{1} &\cdots\\
\langle 0,e,f,z\rangle &\x &\x &\x & s_{2} &\cdots
\end{matrix}$$
$$\begin{matrix}
\boxed{\langle 1,1,1,z\rangle } &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\boxed{\langle 1,1,2,z\rangle } &\x &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\boxed{\langle 1,1,3,z\rangle } &\x &\x &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\langle 1,1,4,z\rangle &\x &\x &\x &\mathcal N &\mathcal N &\mathcal P &\mathcal N &\mathcal N & r &\cdots\\
\langle 1,1,5,z\rangle &\x &\x &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 1,1,g,z\rangle &\x &\x &\x &\x &\x & s_{1} &\cdots\\
\boxed{\langle 1,2,2,z\rangle } &\x &\mathcal N &\mathcal P &\mathcal N &\mathcal N &\mathcal P & r &\cdots\\
\boxed{\langle 1,2,3,z\rangle } &\x &\x &\mathcal N &\mathcal N &\mathcal P &\mathcal N &\mathcal N & r &\cdots\\
\boxed{\langle 1,2,4,z\rangle } &\x &\x &\x &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\langle 1,2,5,z\rangle &\x &\x &\x &\x &\mathcal N &\mathcal N &\mathcal P &\mathcal N &\mathcal N & r &\cdots\\
\langle 1,2,6,z\rangle &\x &\x &\x &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 1,2,h,z\rangle &\x &\x &\x &\x &\x &\x & s_{1} &\cdots\\
\boxed{\langle 1,3,3,z\rangle } &\x &\x &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\langle 1,3,4,z\rangle &\x &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 1,3,5,z\rangle &\x &\x &\x &\x &\mathcal N &\mathcal P &\mathcal N &\mathcal N &\mathcal P & r &\cdots\\
\langle 1,3,i,z\rangle &\x &\x &\x &\x &\x & s_{1} &\cdots\\
\langle 1,4,4,z\rangle &\x &\x &\x &\mathcal N &\mathcal N &\mathcal P &\mathcal N &\mathcal N & r &\cdots\\
\langle 1,4,5,z\rangle &\x &\x &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 1,4,j,z\rangle &\x &\x &\x &\x &\x & s_{1} &\cdots\\
\langle 1,k,\ell,z\rangle &\x &\x &\x &\x & s_{2} &\cdots
\end{matrix}$$
$$\begin{matrix}\boxed{\langle 2,2,2,z\rangle } &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\boxed{\langle 2,2,3,z\rangle } &\x &\x &\mathcal N &\mathcal P &\mathcal N &\mathcal N &\mathcal P & r &\cdots\\
\boxed{\langle 2,2,4,z\rangle } &\x &\x &\x &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\langle 2,2,5,z\rangle &\x &\x &\x &\x &\mathcal N &\mathcal P &\mathcal N &\mathcal N &\mathcal P & r &\cdots\\
\langle 2,2,6,z\rangle &\x &\x &\x &\x &\x &\mathcal N &\mathcal N &\mathcal P &\mathcal N &\mathcal N & r &\cdots\\
\langle 2,2,m,z\rangle &\x &\x &\x &\x &\x &\x & s_{1} &\cdots\\
\boxed{\langle 2,3,3,z\rangle } &\x &\x &\mathcal N &\mathcal N &\mathcal N &\mathcal N &\mathcal N & r &\cdots\\
\langle 2,3,4,z\rangle &\x &\x &\x &\mathcal N &\mathcal N &\mathcal P &\mathcal N &\mathcal N & r &\cdots\\
\langle 2,3,5,z\rangle &\x &\x &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 2,3,n,z\rangle &\x &\x &\x &\x &\x & s_{1} &\cdots\\
\langle 2,4,4,z\rangle &\x &\x &\x &\mathcal N &\mathcal P &\mathcal N &\mathcal N &\mathcal P & r &\cdots\\
\langle 2,4,5,z\rangle &\x &\x &\x &\x &\mathcal N &\mathcal N &\mathcal P &\mathcal N &\mathcal N & r &\cdots\\
\langle 2,4,o,z\rangle &\x &\x &\x &\x &\x & s_{1} &\cdots\\
\langle 2,p,q,z\rangle &\x &\x &\x &\x & s_{2} &\cdots\\
\langle 3,3,3,z\rangle &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 3,3,4,z\rangle &\x &\x &\x &\mathcal N &\mathcal P &\mathcal N &\mathcal N &\mathcal P & r &\cdots\\
\langle 3,3,r,z\rangle &\x &\x &\x &\x & s_{1} &\cdots\\
\langle 3,4,4,z\rangle &\x &\x &\x &\mathcal P &\mathcal N &\mathcal N &\mathcal P &\mathcal N & r &\cdots\\
\langle 3,4,5,z\rangle &\x &\x &\x &\x &\mathcal N &\mathcal P &\mathcal N &\mathcal N &\mathcal P & r &\cdots\\
\langle 3,4,s,z\rangle &\x &\x &\x &\x &\x & s_{1} &\cdots\\
\langle 3,t,u,z\rangle &\x &\x &\x & s_{2} &\cdots\\
\langle v,w,x,z\rangle &\x &\x &\x & s_{3} &\cdots
\end{matrix}$$
Justifying Stability
We will start by justifying all of the $s_1$s:
- $\langle 0,0,a,z\rangle$ for $a\ge5$: Since no items can be removed from the heaps of size $0$, it suffices to note that the rows for $\langle 0,0,3,z\rangle$ and $\langle 0,0,4,z\rangle$ are typical.
- $\langle 0,1,b,z\rangle$ for $b\ge6$: In addition to the rows for $\langle 0,1,4,z\rangle$ and $\langle 0,1,5,z\rangle$ being typical, note that $\langle 0,0,5,z\rangle$ and $\langle 0,0,6,z\rangle$ are typical, too.
- $\langle 0,2,c,z\rangle$ for $c\ge6$: In addition to the rows for $\langle 0,2,4,z\rangle$ and $\langle 0,2,5,z\rangle$ being typical, note that $\langle 0,1,5,z\rangle$ and $\langle 0,1,6,z\rangle$ and $\langle 0,0,6,z\rangle$ are typical, too.
- $\langle 0,3,d,z\rangle$ for $d\ge5$: In addition to the rows for $\langle 0,3,3,z\rangle$ and $\langle 0,3,4,z\rangle$ being typical, note that $\langle 0,2,4,z\rangle$ and $\langle 0,2,5,z\rangle$ and $\langle 0,1,5,z\rangle$ are typical, too.
- $\langle 1,1,g,z\rangle$ for $g\ge6$: We need to observe that each of the following rows is typical: $\langle 1,1,4,z\rangle$, $\langle 1,1,5,z\rangle$, $\langle 0,1,5,z\rangle$, $\langle 0,0,6,z\rangle$.
- $\langle 1,2,h,z\rangle$ for $h\ge7$: Observe that the following rows are typical: $\langle 1,2,5,z\rangle$, $\langle 1,2,6,z\rangle$, $\langle 0,2,6,z\rangle$, $\langle 1,1,6,z\rangle$, $\langle 0,2,7,z\rangle$, $\langle 1,1,7,z\rangle$, $\langle 0,1,7,z\rangle$.
- $\langle 1,3,i,z\rangle$ for $i\ge6$: Observe that the following rows are typical: $\langle 1,3,4,z\rangle$, $\langle 1,3,5,z\rangle$, $\langle 0,3,5,z\rangle$, $\langle 1,2,5,z\rangle$, $\langle 0,3,6,z\rangle$, $\langle 1,2,6,z\rangle$, $\langle 0,2,6,z\rangle$, $\langle 1,1,6,z\rangle$.
- $\langle 1,4,j,z\rangle$ for $j\ge6$: Observe that the following rows are typical: $\langle 1,4,4,z\rangle$, $\langle 1,4,5,z\rangle$, $\langle 0,4,5,z\rangle$, $\langle 1,3,5,z\rangle$, $\langle 0,4,6,z\rangle$, $\langle 1,3,6,z\rangle$, $\langle 0,3,6,z\rangle$, $\langle 1,2,6,z\rangle$.
- $\langle 2,2,m,z\rangle$ for $m\ge7$: Observe that the following rows are typical: $\langle 2,2,5,z\rangle$, $\langle 2,2,6,z\rangle$, $\langle 1,2,6,z\rangle$, $\langle 1,2,7,z\rangle$, $\langle 0,2,7,z\rangle$, $\langle 1,1,7,z\rangle$.
- $\langle 2,3,n,z\rangle$ for $n\ge6$: Observe that the following rows are typical: $\langle 2,3,4,z\rangle$, $\langle 2,3,5,z\rangle$, $\langle 1,3,5,z\rangle$, $\langle 2,2,5,z\rangle$, $\langle 1,3,6,z\rangle$, $\langle 2,2,6,z\rangle$, $\langle 0,3,6,z\rangle$, $\langle 1,2,6,z\rangle$.
- $\langle 2,4,o,z\rangle$ for $o\ge6$: Observe that the following rows are typical: $\langle 2,4,4,z\rangle$, $\langle 2,4,5,z\rangle$, $\langle 1,4,5,z\rangle$, $\langle 2,3,5,z\rangle$, $\langle 1,4,6,z\rangle$, $\langle 2,3,6,z\rangle$, $\langle 0,4,6,z\rangle$, $\langle 2,2,6,z\rangle$, $\langle 1,3,6,z\rangle$.
- $\langle 3,3,r,z\rangle$ for $r\ge5$: Observe that the following rows are typical: $\langle 3,3,3,z\rangle$, $\langle 3,3,4,z\rangle$, $\langle 2,3,4,z\rangle$, $\langle 2,3,5,z\rangle$, $\langle 1,3,5,z\rangle$, $\langle 2,2,5,z\rangle$.
- $\langle 3,4,s,z\rangle$ for $s\ge6$: Observe that the following rows are typical: $\langle 3,4,4,z\rangle$, $\langle 3,4,5,z\rangle$, $\langle 2,4,5,z\rangle$, $\langle 3,3,5,z\rangle$, $\langle 2,4,6,z\rangle$, $\langle 3,3,6,z\rangle$, $\langle 1,4,6,z\rangle$, $\langle 2,3,6,z\rangle$.
Next, we handle the $s_2$s:
- $\langle 0,e,f,z\rangle$ for $e\ge4$: Observe that the following groups of rows are typical: $\langle 0,2,c,z\rangle$ and $\langle 0,3,d,z\rangle$.
- $\langle 1,k,\ell,z\rangle$ for $k\ge5$: Observe that the following groups of rows are typical: $\langle 1,3,i,z\rangle$, $\langle 1,4,j,z\rangle$, $\langle0,5,\ell,z\rangle$ for $\ell\ge5$, and $\langle0,4,\ell,z\rangle$ for $\ell\ge5$.
- $\langle 2,p,q,z\rangle$ for $p\ge5$: Observe that the following groups of rows are typical: $\langle 2,3,n,z\rangle$, $\langle 2,4,o,z\rangle$, $\langle1,5,q,z\rangle$ for $q\ge5$, $\langle1,4,5,z\rangle$, $\langle1,4,j,z\rangle$ for $j\ge6$, and $\langle0,5,q,z\rangle$ for $q\ge5$.
- $\langle 3,t,u,z\rangle$ for $t\ge5$: Observe that the following groups of rows are typical: $\langle 3,3,r,z\rangle$, $\langle 3,4,s,z\rangle$, $\langle2,5,u,z\rangle$ for $u\ge5$, $\langle2,4,5,z\rangle$, $\langle2,4,o,z\rangle$ for $o\ge6$, and $\langle1,5,u,z\rangle$ for $u\ge5$.
Finally, we take care of the remaining positions ($s_3$). Any position with smallest heap at least size $4$ is typical since the following groups of rows are typical: $\langle 2,4,4,z\rangle$, $\langle 2,4,5,z\rangle$, $\langle 2,4,o,z\rangle$ for $o\ge6$, $\langle 2,p,q,z\rangle$ for $p\ge5$, $\langle 3,4,4,z\rangle$, $\langle 3,4,5,z\rangle$, $\langle 3,4,s,z\rangle$ for $s\ge6$, and $\langle 3,t,u,z\rangle$ for $t\ge5$.
Code for base cases
It remains to check the 220 base cases indicated in the table. One way to do this is with some Mathematica code seen at the following link: Try it online!
Summary
As presented at the beginning, a tidy list of the outcomes does not need to be this big. Since every row has period 3, we can use columns based on the remainder $R$ when the sum of the heap sizes is divided by 3.
$$\begin{matrix}
\text{min }3\backslash R & 0 & 1 & 2\\
\langle 0,0,0,z\rangle &\mathcal P &\mathcal P &\mathcal P\\
\langle 0,0,1,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\langle 0,0,2,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\langle 0,1,1,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\langle 0,1,2,z\rangle &\mathcal N &\mathcal N &\mathcal P\\
\langle 0,1,3,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\langle 0,2,2,z\rangle &\mathcal N &\mathcal N &\mathcal P\\
\langle 0,2,3,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\langle 1,1,1,z\rangle &\mathcal N &\mathcal P &\mathcal N\\
\langle 1,1,2,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\langle 1,1,3,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\langle 1,2,2,z\rangle &\mathcal N &\mathcal N &\mathcal P\\
\langle 1,2,3,z\rangle &\mathcal N &\mathcal N &\mathcal P\\
\langle 1,2,4,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\langle 1,3,3,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\langle 2,2,2,z\rangle &\mathcal N &\mathcal N &\mathcal P\\
\langle 2,2,3,z\rangle &\mathcal N &\mathcal N &\mathcal P\\
\langle 2,2,4,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\langle 2,3,3,z\rangle &\mathcal N &\mathcal N &\mathcal N\\
\text{else} &\mathcal P &\mathcal N &\mathcal N
\end{matrix}$$
Bonus: Sprague-Grundy Values
Preliminaries
"Sprague-Grundy values" arise in the study of "disjunctive sums" of games under "normal play". Briefly, if we followed the rule "you lose precisely when you have no move available on your turn", and played multiple games at once (choose one to move in on each turn), then the Sprague-Grundy theorem says that these values would be relevant.
To make this game into a normal play game, we just need to say that no moves are allowed from from a position with a single non-empty heap, and agree that $(0,0,0,0)$ is a $\mathcal P$-position.
Then the Sprague-Grundy values can be calculated inductively as the mex (minimal excludant) of the values of the options. It is not hard to show by induction that the value is $0$ precisely when the outcome is $\mathcal P$, so this information just tells us about how the various $\mathcal N$-positions act in combinations of games.
Lemma transfer
The repetition lemma carries over directly to the setting of Sprague-Grundy values: the function of the values of the options used doesn't affect those arguments.
For stability, the situation is the same, except that the typical values are $0$ if the sum of the heap sizes is a multiple of $3$, $2$ for remainder $1$, and $1$ for remainder $2$. Since $\mathrm{mex}(\{2,1\})=0$, $\mathrm{mex}(\{1,0\})=2$, and $\mathrm{mex}(\{0,2\})=1$, this version of the stability lemma holds.
Result
After some computer calculations, it appears that the values are given by the following table.
$$\begin{matrix}\text{min }3\backslash R & 0 & 1 & 2\\
\langle 0,0,0,z\rangle & 0 & 0 & 0\\
\langle 0,0,1,z\rangle & 2 & 3 & 1\\
\langle 0,0,2,z\rangle & 2 & 3 & 1\\
\langle 0,0,3,z\rangle & 0 & 3 & 1\\
\langle 0,1,1,z\rangle & 2 & 3 & 1\\
\langle 0,1,2,z\rangle & 2 & 3 & 0\\
\langle 0,1,3,z\rangle & 2 & 3 & 1\\
\langle 0,1,4,z\rangle & 0 & 3 & 1\\
\langle 0,2,2,z\rangle & 1 & 3 & 0\\
\langle 0,2,3,z\rangle & 2 & 3 & 4\\
\langle 0,2,4,z\rangle & 0 & 3 & 4\\
\langle 0,3,3,z\rangle & 0 & 3 & 4\\
\langle 1,1,1,z\rangle & 2 & 0 & 1\\
\langle 1,1,2,z\rangle & 2 & 3 & 1\\
\langle 1,1,3,z\rangle & 2 & 3 & 1\\
\langle 1,1,4,z\rangle & 0 & 3 & 1\\
\langle 1,2,2,z\rangle & 2 & 3 & 0\\
\langle 1,2,3,z\rangle & 2 & 3 & 0\\
\langle 1,2,4,z\rangle & 2 & 3 & 1\\
\langle 1,2,5,z\rangle & 0 & 3 & 1\\
\langle 1,3,3,z\rangle & 2 & 3 & 1\\
\langle 1,3,4,z\rangle & 0 & 3 & 1\\
\langle 2,2,2,z\rangle & 1 & 3 & 0\\
\langle 2,2,3,z\rangle & 1 & 3 & 0\\
\langle 2,2,4,z\rangle & 2 & 3 & 4\\
\langle 2,2,5,z\rangle & 0 & 3 & 4\\
\langle 2,3,3,z\rangle & 2 & 3 & 4\\
\langle 2,3,4,z\rangle & 0 & 3 & 4\\
\langle 3,3,3,z\rangle & 0 & 3 & 4\\
\text{else} & 0 & 2 & 1
\end{matrix}$$
Proof sketch
I haven't checked the hypotheses of the stability corollaries very carefully here, but I suspect the $290$ cases produced by the following code would be enough to prove the Sprague-Grundy values for all positions.
Putting that code into the Wolfram Cloud Sandbox should show a lot of supporting data for the result claimed above. You can also just Try it online!
Best Answer
I’ll call the sum of the binary pile sizes performed mod $k+1$ in each digit the “$k$-sum” for short.
The task is to show that if the $k$-sum is non-zero we can always reduce at most $k$ piles such that the $k$-sum becomes $0$, and conversely if the $k$-sum is $0$ it’s impossible to reduce at most $k$ piles and leave the $k$-sum unchanged.
To get a feel for how this works, recall how it works for Nim$_1$ (a.k.a. Nim). The $1$-sum is the XOR of all the binary pile sizes. There is at least one pile that has a $1$ in the highest digit in which the $1$-sum has a $1$. Form the XOR of that pile’s size with the $1$-sum to determine how many stones to leave in it. Since these two numbers both have a $1$ in the highest digit, the resulting number has a $0$ in that digit and is thus less than the current number, so it can indeed be achieved by taking away some number of stones.
Now for Nim$_k$. We will select up to $k$ piles to take stones from and construct the number of stones they should be left with as we go along. Let $d$ be the highest non-zero digit in the $k$-sum. Select any $d$ piles that have a $1$ in that digit. (They must exist, since the sum has $d$ in that digit.) Set that digit to $0$ in the binary sizes of those piles. Now the $k$-sum has a $0$ in that digit. Note that in the following we can modify the remaining binary digits of the selected piles in whatever way we want, since the resulting size will always be less than the current size because it lacks the $1$ in the highest digit. (This is the same argument as the one for Nim above.)
Let the next lower digit in the $k$-sum be $e$. Say $m$ of the $d$ piles we selected have a $0$ in this digit and $n=d-m$ have a $1$. Then by modifying these digits we can deal with $e\in[-m,n]\bmod k+1$, since we can add up to $m$ $1$s or subtract up to $n$ $1$s. To deal with the remaining cases with $e\in[n+1,k-m]$, we need to select $e-n$ further piles that have a $1$ in the present digit. Since $m+n=d$ and $e\le k-m$, we have $d+e-n\le k$, so we’re allowed to select $e-n$ further piles; also, since the present digit is $e$, there must be at least $e$ piles with a $1$ in this digit, and since that includes only $n$ of the piles selected so far, there must be at least $e-n$ left to select. Now set the present digit to $0$ in the $n$ previously selected and the $e-n$ newly selected piles, thus bringing this digit to $0$ in the $k$-sum. Again, note that in the following we can modify the remaining digits of the newly selected piles in whatever way we want, since the resulting size will always be less than the current size because it lacks the $1$ in the present digit. That may not be the highest digit for these piles, but the higher digits remain unchanged.
We can continue like this, descending through the digits. In each step, we’ve already selected $d\le k$ piles whose remaining digits we can modify arbitrarily; this allows us to deal with $d+1$ cases of the present digit, and the remaining $k-d$ cases can be dealt with by selecting an admissible number of new piles that have $1$ in the present digit.
Note that if the $k$-sum is already $0$ to begin with, the algorithm would lead us to select $0$ piles, and indeed any modification of up to $k$ piles will change the $k$-sum, since the highest digit modified can only be changed from a $1$ to a $0$ (otherwise the pile size would increase), and changing up to $k$ $1$s to $0$s changes the $k$-sum in that digit.
Let’s apply this algorithm to the given example. We have $k=2$ and the pile sizes $01111_2$, $00011_2$, $01000_2$ and $10010_2$. The $2$-sum is $12102_3$. The highest digit is $1$, so we need to select one pile with a $1$ in that digit. There’s only one to select, namely $10010_2$. We set its highest digit to $0$, yielding $00010_2$.
For the next digit, we have $m=1$ and $n=0$, so we can deal with $e\in[-1,0]\bmod3$ using the one pile selected so far. Indeed the next digit is $e=2\equiv-1\bmod3$, so we set this digit to $1$ in the selected pile, yielding $01010_2$. Now there are three $1$s in this digit, so the $2$-sum is $0$ in this digit as required.
For the next digit, we again have $m=1$ and $n=0$, so we could again deal with $e\in[-1,0]\bmod3$, but now we have $e=1$, so we need to select another pile that has a $1$ in this digit. Again, there’s only one choice, $01111_2$. (The reason we only have one choice in each case is that those digits didn’t “wrap around” in the $2$-sum, so the number of piles with a $1$ is exactly the value of the digit.) We set the present digit to $0$ in the newly selected pile, yielding $01011_2$ and bringing the present digit to $0$ in the $2$-sum. So we’ve now selected $2$ piles, as many as we’re allowed to select, and we’ve changed their sizes to $01010_2$ and $01011_2$, respectively. From now on, we can deal with all cases by further modifying the piles already selected.
The next digit in the $2$-sum is already $0$, so no modification required there.
The last digit is $2$, so we have to either turn one $0$ into a $1$ or two $1$s into $0$s; exactly one of these must be possible. Indeed, we have a $0$ in $01010_2$; we set it to $1$, yielding $01011_2$ and bringing the final digit in the $2$-sum to $0$.
The end result is that we’ve modified $10010_2$ to $01011_2$ and $01111_2$ to $01011_2$, so we need to take $18-11=7$ and $15-11=4$ stones from those piles, respectively. The resulting pile sizes are $01011_2$, $00011_2$, $01000_2$ and $01011_2$, and their $2$-sum is $0$ as required.