Game on a string

Question

I am interested if one can design an efficient (polynomial) algorithm telling whether the first player has a winning strategy for a game described below.

The board is a string consisting of only pluses and minuses, for example: ---+--+. There are two players. The players make moves alternately. In each move a player replaces two neighboring minuses with pluses, for example: --+--- -> --+-++. If a player can't do any move then he wins.

Are there any papers on this problem?

Answer 1

From the Wikipedia article on octal games I posted in my comments above, I think your game is known as "Dawson's Kayles".

In case the mapping is not clear, a string of minuses and pluses should be interpreted as a set of heaps of continuous minuses.

Your example string of ---+--+ is thus a game position consisting of one heap of size 3 and one heap of size 2.

A move that replaces two neighboring minuses with two pluses removes exactly two tokens from the corresponding heap, say of size $n$ and divides it into either 0, 1, or 2 heaps (the sum of whose sizes is equal to $n-2$).

In your example move, --+--- is a position with a heap of size 2 and a heap of size 3. The replacement of the last two minuses with two pluses removes two tokens from the heap of size 3 and results in a single heap of size 1; as you can see from --+-++, the result is a heap of size 2 and a heap of size 1.

While Dawson's Kayles has a complete analysis under normal play, under misère play (as you described in your question) it seems not to be fully understood yet, so I think nobody yet knows if there is an efficient algorithm of the kind you ask for.

From a quick google search, you can find more information and references in this note of Plambeck's, though if you are unfamiliar with combinatorial game theory you may wish to start with some of the book references in the Wikipedia pages. There's also discussion in this math.stackexchange question.