How to maximize chances to win?

Question

Let's say I have $n$ stacks of coins such as the $i$-th stack contains $c_i$ coins at the beginning of a game.

The game is simple. The players have to take any number of coins from one stack (and only one) during their turn.

The person taking the last coin loses the game.

Is there a good strategy to win or is the game too prone to randomness ?

Answer 1

This is the misère version of Nim; it is very well studied, and the winning strategies for both the regular and the misère versions are described (and their correctness proved) in the linked article.

Answer 2

This is an example of nim. I would recommend Conway's On Numbers And Games (ISBN: 1568811276) if you want a terrific read on the subject and much, much more.

I'll present the typical strategy, though I won't prove it (and I would post this as a comment, but I'm afraid I'm not allowed...):

Suppose we have a stack of $3$, one of $6$ and one of $7$. We now wish to find the value of this position. We do this by first converting the sizes of the stacks to binary ($011, 110$ and $111$), and then add them without carrying:

\begin{align*} &011 \\ &110 \\ +&111 \\ -&-- \\ &010 \end{align*}

So the value of our position is $2$. Now, to find a winning move, we add $2$ to one stack at a time, in the same manner as before. In doing so we get $001, 100$ and $101$, respectively. Pick any one of those alternatives that are legal (meaning they reduce the size of the given stack. In this case all of them are) and you'll be giving your opponent a position of value $0$, meaning it's a losing position.

For example, $001, 110$ and $111$, or $1, 6$ and $7$:

\begin{align*} &001 \\ &110 \\ +&111 \\ -&-- \\ &000 \end{align*}

Answer 3

This is the game of Nim. There is no randomness and the strategy is well studied.