Matthew Mullin
2521 King Road
Trenton, MI 48183
mdmullin@alumni.princeton.edu
-------------------------------------------------------
We calculate what the optimal strategy is for any number of starting
stones and any maximum allowed move.

We start by recognizing that all that matters is the number of
remaining stones in the position, and the parity of the current
players stones (even or odd, or 0 or 1).  Since the total number
of stones is odd, we can tell what parity the opponents stone have:
    remaining stones+players stones+opponents stones = 1 (mod 2)
so:
    opponents stones = 1+remaining stones+players stones (mod 2)

Now we represent the position by [r,p] where r is the number of
remaining stones, and p is the parity of the current players stones.
We can calculate q, the parity of the opponents stones, by
q = 1+p+r (mod 2).  A position is a winning position for the current
player if and only if he can make some move so that his opponent will
be in a losing position; if there is no such move, then anything that
the player does will give the opponent a winning position.  In symbols
we can say:
    [r,p]=W iff [r-m,q]=L for some max >= m >= 1
We construct a table for some values of max and for early values of r
and look for repetition and patterns.  We can simplify the beginning of
these tables by recognizing that if we there are at least 2 and at most
max stones left, we can win by taking all the stones but 0 or 1 such that
we have an odd number ourselvesr.  If there are 0 stones left, the game ends
and we win; if there is 1 stone, our opponent has to take it and lose.

Table for max=2:               Period=4
p r 0 1 2 3 4 5 6 7 8 9        0 1 2 3
0   L W W L L W W L L W        L W W L
1   W L W W W L W W W L        W L W W

Table for max=3:
                        1 1 1 1 1 1 1 1 1       Period=8
p r 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8       0 1 2 3 4 5 6 7
0   L W W W W L W W L W W W W L W W L W W       L W W W W L W W
1   W L W W L W W W W L W W L W W W W L W       W L W W L W W W

Table for max=4:
                        1 1 1 1 1 1 1 1 1       Period=6
p r 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8       0 1 2 3 4 5
0   L W W W W L L W W W W L L W W W W L L       L W W W W L
1   W L W W W W W L W W W W W L W W W W W       W L W W W W

etc for greater max

It might not be obvious just from the above, but (and it can be shown)
the period=max+2 for max even, and the period=2*max+2 for max odd.
In fact, the losing positions can be simply listed as follows:
    for max even: [0,0],[max+1,0],[1,1]
    for max odd:  [0,0],[max+2,0],[1,1],[max+1,1]
where the first coordinates are considered mod the period.

In the program, we construct an array of the losing positions:
    max even:  @losers = ([0,$maximum_at_once+1],[1]);
    max odd:   @losers = ([0,$maximum_at_once+2],[1,$maximum_at_once+1]);
Then we get a list of losing positions to aim to put the opponent in:
    @targets = @{$losers[opponents_stones]};
We use a grep command to filter out any positions that are less than
max stones from the current positions.  If there are no targets that
meet that criteria, we are in a losing position and we just return a
random move; if there are targets left (no more than 2), we return a
random one from the target list.

With the above strategy and implementation, the function will return
a winning move when possible for all values of the arguments, up to
the limits of Perl's arithematic.  Similar games with different moves
or winning conditions could be solved with a similar function by
changing the @losers array (and changing the strategy for small numbers).