move - An alteration of a game situation done in accordance with the game rules.
normal game - A game in which the winner is the last player able to make a move.
misere game - A game in which the winner is the first player unable to make a move.
nim - An impartial game in which a move consists of removing one or more tokens from some heap.
Misere nim is easy, but misere impartial games in general are fantastically difficult. This observation leads to the project (hereafter called the "misere project") of finding conditions, as least restrictive as possible, under which a misere impartial game is easy.
component - A "subgame". A game consists of one or more components such that any move played in the game affects exactly one component.
component scheme - A set of components for a game such that any move played in the game affects exactly one component. In terms of a given component scheme, call the components the "elements".
There can often be multiple schemes for breaking a game into components. The famous algorithm for perfect normal play has practical applicability only in games in which a component scheme can be found such that each element can be assigned a Sprague-Grundy number (hereafter "SGN") with relative ease. We will supplement the SGN tool with another analytical technique, again under the understanding that this technique will have practical value only in cases in which the technique can be applied to each element of a component scheme without too much trouble.
null - A component which, played as a game, is a loss for the first player to move in normal play and is a win for the first player to move in misere play.
inverter - A component which, played as a game, is a win for the first player to move in normal play and is a loss for the first player to move in misere play.
trap - A component which, played as a game, is a loss for the player to move both in normal and misere play.
switch - A component which, played as a game, is a win for the player to move both in normal and misere play.
It follows from these definitions that any null or trap has an SGN = 0 and any inverter or switch has an SGN > 0. In fact, a given inverter or switch can have an SGN of any integral value > 0. (SGN = 0 means that the component, played as a game, is a loss for the player to move in normal play. SGN = n + 1 means that the component can be transformed in one move to a component of any SGN from 0 to n, but not to n + 1.)
It also follows from these definitions that any switch can be transformed in one move to a trap or else to an inverter. (We will use this fact in our algorithm.)
higher inverter - An inverter with SGN > 1.
gremlin - A switch with SGN = 1.
higher switch - A switch with SGN > 1
R1 game - An impartial game for which (in any position) there is a component scheme in which (1) there can be no higher inverters, (2) any higher switch can be transformed in one move to a null or else to a gremlin, and (3) no null can be transformed in one move to a gremlin.
Algorithm for a correct move in any R1 game (assuming we have a winning position): (1) If there are one or more traps or two or more higher switches or one or more gremlins, make the move you would make in the normal game. (Return nim-sum to 0; in other words, make the move which will cause there to be an even number of 1's in each column of the SGN's of all the elements when converted to binary and right-aligned.) (2) If there are no traps and one higher switch and no gremlins and an even number of inverters, then convert the switch to a trap or to an inverter. (3) If there are no traps and one higher switch and no gremlins and an odd number of inverters, then convert the switch to a null or to a gremlin. (4) If there are no traps and no switches and an even number of inverters, convert a null to an inverter or an inverter to a null.
These four cases cover all positions that win for the player to move. The prescription for each case transforms the winning position to a position that loses for the next player to move. (A position with nim-sum = 0 and in which there are traps or switches loses for the player to move. A position with no traps or switches and with an odd number of inverters also loses for the player to move. A single move played to either of these two types of losing positions must create a position covered by one of the four cases of the algorithm.)
Nim is an R1 game. Let the heaps be elements. A heap with 0 tokens is a null. A heap with 1 token is an inverter. All other heaps are switches.
My analysis, even if correct, is only a provisional contribution toward the misere project. My understanding is that the game called "kayles" is not an R1 game but does have an algorithm for perfect misere play. R1 is evidently too restricted.