# Algorithm for token replacement game

I'm having problems finding an algorithm to the following problem:

A and B take turns replacing a number $$n$$ of tokens with either $$floor((n+1)/2)$$ or $$n-1$$. The player who makes one token remain wins. We want to know, if there is a way for B to win the game no matter the moves of A. A begins the game.

My idea is the following:

Is n = 1 -> No way for B to win the game

We try all moves of first A then B and check for 1 -> There is a way for B to win

But this does not incorporate the "no matter the moves of A" criteria.

I'd check what happens for some small(ish) values of initial $$n$$, working up. If you know who wins if there are at most $$n$$ on the table, working out what happens with $$n + 1$$ is easy.
• @BastianHofmann, you really don't need the full tree. If you know the answers for all $n$ up to $N$, the answer for $N + 1$ is either the one for $N$ or $\lfloor (N + 2) / 2 \rfloor$, both of which you computed before. – vonbrand Jan 28 at 17:43