# Applying dynamic programming to a simple two-person game of perfect information

A natural number n represents the initial position in the game. When it is a players turn he/she is allowed to

I)  Subtract 2 from n
II) Subtract 3 from n
III)    Subtract 5 from n


We call the player who begin the game Adam and the other player Berta. The players alternate by applying on of the three rules to the number 0 or a negative number his/her opponent. If a player manages to produce the number 0 or a negative number he/she wins the game.

Here is an example of a game played by Adam and Berta (for n=15)

15 is given to Adam. He decides to subtract 5 leaving 15-5 = 10 to Berta
10 is given to Berta. She decides to subtract 3 leaving 11-3=8 to Beta
8 is given to Adam. He decides to subtract 2 leaving 8-2=6 to Berta
6 is given to Berta. She decides to subtract 2 leaving 6-2=4 to Adam
4 is given to Adam. He decides to subtract 5 producing -1 a negative number, Adam wins!


b) we define a one dimensional array X(1), X(2),X(3),..,X(n)

i)  X(j) =1 if Adam has a method to win when given the number j
ii) X(j)=0 if Adam has no method that guarantees that he wins when the given the number k


Calculate X(1),X(2),X(3)….,X(23),X(25)

What is X(8), X(13) and X(24)? Answer should be of the form boolean boolean boolean so if X(8)=0 , X(13)=1 and X(24)=1 the correct answer is 011 Thus the correct answer is one of the following 000 001 010 011 100 101 110 111

My attempt is

n=8
Berta: 3-3 =0
Berta wins  0

n=13
Berta: 8-3=5

I get really stuck with 24, so far I have 01


Is there a method for this type of problem, i have been stuck on it for ages now. Thanks in advance

• You're supposed to express $X(i)$ in terms of $X(i-2), X(i-3), X(i-5)$, then go from $1$ to $25$, applying the rule, not just using brute force. – Karolis Juodelė Nov 16 '13 at 21:39
• why X(i) in terms of X(i−2),X(i−3),X(i−5) ? – joker Nov 16 '13 at 22:01
• You're right, there should be more terms in that expression. – Karolis Juodelė Nov 16 '13 at 22:10
• Thanks for replying, but is there a rule which states it must be X(i-2) ? why 2? What does i represent in this case? – joker Nov 16 '13 at 22:12
• What have you tried? Where did you get stuck? We expect you to make a serious effort before asking. This is a nice exercise -- but you should do it for yourself. (If you have us solve it for you, you won't learn the material for yourself.) What chapter in your textbook are you studying now? What topic are you studying in your class? Does that give you any hints on how you might approach this problem? Can you see how to solve it, if you could use exponential time? That would be a good start... – D.W. Nov 17 '13 at 1:35

Since you want to calculate $X(1), X(2), X(3)$,... and not just some $X(i)$, you can start from $X(1)$. Let's denote the case where there is a winning strategy for first player by $1$ and the other case by $0$.
Clearly, value of $X(i)$ for $i \in \{1,2,3,4,5\}$ is $1$. Let's store the values of $X(i)$ that we computed in an array. For $i>5$, if at least one of the values of $X(i-2), X(i-3), X(i-5)$ is $0$, then the value of $X(i)$ will be $1$. If none of them is $0$, then the value of $X(i)$ will be $0$.
Hint: A position with $n \leq 5$ is a win for the first player (the player to go); let's call such a position P1. If any move from a given position leads to a P1 position, then the position is a win for the second player (the player not to go); let's call such a position P2. If there is a move from a given position to a P2 position, then it's a P1 position. Use dynamic programming to determine who wins for given $n$.
More generally, you can compute the Sprague-Grundy function. That will tell you who wins in the simultaneous game when there are several positions $n_1,\ldots,n_k$, and each turn each player selects a position and makes a move there; a player who can't make a move (all $n_i$ are negative or zero) loses.