Understanding the Bachet's game competition problem

Question

In lectures we were just solving the following problem :

So we have n stones and a set S that has given positive natural numbers. Two players take stones from the n stone pile and the one who takes the last stones wins the game. We need to find an algorithm that will tell us who wins it. (The number 1 is never in the set S). Players can only take the number of stones that they choose from set S.

So we have two players Stan and Ollie, where Stan always starts. We also have a set of numbers that never has $1$ in it, but it can have other numbers (that are picked by the program).

First we set all the elements in a list to False.

In the following code, the sequence is the set of moves that any of the two players can make. The i is the index from 1 to the number of stones which is n. However I do not understand how such a simple loop can solve such a problem. Can somebody explain the theory behind it, why does it work in such a way ?

wins=[False]
    i=1
    while i<=n:
        for s in sequence:
            if s>i:
                wins.append(False)
                break
            if not wins[i-s]:
                wins.append(True)
                break
        else:
            wins.append(False)
        i+=1
    if wins[-1]:
        print 'Stan wins'
    else:
        print 'Ollie wins'

So how I understand it is, that we have a list that has only False in it, and then if the index of stones is bigger than any of the moves(in the above code as s) we can make, then we say True for that index if the index that is on i-s is False. So in the end we get a list of True and False that is n long.

Can somebody explain the theory behind this, because I clearly do not understand it. I also found numerous solutions and all use the same technique.

Answer 1

I will use the example $S=\{2,3\}$ to explain.

Think about if you were trying to solve the game with paper and pencil. A good method is to solve the game for smaller pile sizes first. Obviously, the game is a win for Ollie when $n\in\{0,1\}$, since no moves are available, and it is a win for Stan when $n\in \{2,3\}$ since he can win in one move. We summarize the results so far in a table:

n	0	1	2	3	4	5
Outcome	O	O	S	S

Now, how do we determine the outcome for $n=4$? Consider the options available; from $4$, Stan can either remove $2$ and leave $2$, or remove $3$ and leave $1$. Obviously, removing $3$ is a winning move, so $4$ is a win for Stan. To make the logic crystal clear: $4$ should be labeled $S$ because it can reach a position which is labeled $O$.

Now, move on to $n=5$. This time, both options are to positions with $2$ and $3$ stones, which are both labeled $S$. Therefore, $5$ should be marked $O$.

The piece of code you have is doing exactly what we are doing in this post. The list wins represents this table, where False means Ollie wins and True means Stan wins. You check all available options from a position; if at least one is a win for Ollie, then that position is a win for Stan, and if all options are wins for Stan, the position is a win for Ollie.