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
Once all the heaps are below $k$ you are playing standard Nim and should use the usual strategy. In the $4,5,6$ case, the XOR of the three is $7$ and you should remove one stone from the $4$ heap, $3$ from the $5$ heap, or $5$ from the $6$ heap. For the whole game, you just count the parity of the number of $k$ moves that can be made because the order they are made doesn't matter. That tells you who goes first in the Nim game with all heaps less than $k$.