# How to think and deduce optimal strategy move for both Alice and Bob

Question:

Alice and Bob are playing a game on a one-dimensional number line. Initially, Alice is standing at coordinate $$x=a$$ (integer) and Bob is standing at $$x=b$$ (integer) .It is guaranteed that $$a. Alice starts the game by playing the first move. On a turn, a player chooses to move either 0, 2 or 3 units towards their opponent. However, the move must be different from the last move played by them. Both players have all three choices for their first move. The game ends when either:

• A player lands on the spot currently occupied by their opponent. The player is declared the winner in this case.
• A player crosses their opponent and lands beyond them. The opponent is declared the winner in this case.

Given the starting positions of Alice and Bob, determine who wins the game if both of them play optimally.

My progress: What I believed was that there might be a pattern on who might win the game giving a specific distance modulo some number. So let's say distance is $$d$$.

ALICE mindset: As Alice starts first, she wants to maximise all her chance of winning so she calculates all move possible in the beginning which would give her a better win chance. As I don't have a way to think of what will happen for all the possible cases, I started with a move by Alice as 0.

BOB mindset: Now since Bob too wants to maximise his chance of winning, so now he calculates all possible scenarios and consider the best move, I supposed he choosed also 0 . Now next move by Alice should be either 2 or 3. I now realized that if $$d$$ was 5, then surely Bob would win since Alice whatever she do, Bob can just do a move of $$5-$$the move Alice did. So I thought maybe this would be the case for all distances of form $$5k$$, but I don't have a proof. If $$d$$ was 4, then I think Bob would win surely since 2 can be the move for A then B would do 2 too. Similarily considering for $$d =1 ,2 ,3$$ but not sure how to generalize for $$d>5$$ .

In all, my query is how to think of what's the optimal strategy for each player to follow always and why so? Also explain why the strategy of yours is optimal too.

this problem was a part of this https://codeforces.com/gym/445869/problem/F i am just asking the mathematical portion.

like for the case of b-a being 1 its given bob wins as well as for the case of b-a being 5 and 6. but for b-a =94 its given that alice wins the site problem in case anyone needs:

"the move must be different from the last move played by them", this means they must play a move different from the last move played by them only as in if A plays 0 then in next move A can only play 2,3 , similarly for B too . as in if B move 2 then next it can only play among 0,3

**it seems like the answer is this : for d=1 Bob wins ;

for d==2 Alice wins;

for d>=3 and d is 3, 4congruent mod 5 then Alice wins ;

for d>=3 and rest cases Bob wins . ** can anyone prove this ?

• Try for low values of $d$ to get a grasp of the problem, you will quickly find the winning strategy. Also, you can use strategy stealing here, though it is not constructive and not needed here. Commented Jun 13, 2023 at 14:42
• @caduk what you meant by strategy stealing , can you please apply it here and write a answer based on that it will help me very much to know such methods exist . you may also provide a constructive approach if possible Commented Jun 13, 2023 at 21:12
• also i tried smaller cases whic you said above in the question Commented Jun 13, 2023 at 21:21
• "However, the move must be different from the last move played by them" - does "them" refer to the player or to their opponent. In example if A plays 2 and B responds by playing 3, what moves is A allowed to play next? Commented Jun 17, 2023 at 0:19
• not possible unless a account is created @Apass.Jack ,let me share ss above Commented Jun 17, 2023 at 6:48

# Disclaimer

This question is poorly written by the author(s), since it leaves room for interpretation of the rules. The first part of this answer is based on the interpretation that "the move must be different from the last move played by them" means that apart from both player's initial moves, no player is allowed to repeat what their opponent did last move. In a second part, I will adress the reading that "the move must be different from the last move played by them" means that apart from both player's initial moves, no player is allowed to repeat what they themselves did last move. Finally, in a third part, I will adress the case where both of these apply.

# Part I: no last-move copycat

Spoiler: Alice wins for $$d\in \{2,3\}$$, Bob wins for $$d\in \{1,4,5,...\}.$$

1. Implication of rules The qoq "best" way to think about this specific game is to understand the power of position, i.e. being the person to not act first, paired with the power of moving $$0$$, which Bob can always do turn 1, and Alice can never repeat as per rules. This is enough to deduce that Alice must win on turn 1, which is possible iff $$d=2$$ or $$d=3$$.

For all other values of $$d$$, Bob wins. Let's have a look at a few of them.

2. Discussion of first few cases
For $$d=1$$, Alice either overshoots with an initial $$A2$$ and $$A3$$, or prolongs her game by opening $$A0$$, when Bob in turn elects the play the sequence $$\{A0-B0-AX\}$$, forcing Alice to overshoot. (Note that from a strategical point of view, all of Alice's opening moves are optimal, as they all loose by force; practically however, $$A0$$ is preferable since it allows Bob to play suboptimally.)

For $$d=4$$, we have
$$\{A3-B0-AX\},$$ where Alice overshoots, or
$$\{A2-B2\}$$, where Bob lands, or
$$\{A0-B2-A0-B2\}$$ and $$\{A0-B2-AX\}$$. Bob wins.

For $$d=5$$, we have what you described, $$\{A0-B0-A2-B3\}$$ or $$\{A0-B0-A3-B2\}.$$

For $$d\gt5$$, the recurring scheme is that Bob can force Alice into a line described above.

F.e. for $$d=6$$, we have the simple $$\{A3-B3\}$$ for opener $$A3$$, $$\{A2-B2-AX\}$$ or $$\{A2-B2-A0-B2\}$$ for opener $$A2$$, and for opener $$A0$$ we have $$\{A0-B3-A2-B0-AX\}$$ or $$\{A0-B3-A0-B3\}$$. Bob wins.

For $$d=7$$, we either have prefix $$\{A0-B0-A2-B0-\}$$ and now $$d=5$$, with Alice to act and no $$0$$-move at hand, or we have prefix $$\{A0-B0-A3-B0-\}$$ and now $$d=4$$, again with Alice to act and no $$A0$$-move at hand. Alice may thus not open with $$A0$$. But opening with $$A2$$ brings herself directly into $$d=5$$, which is a win for Bob, since he can play $$B0$$, and opening $$A3$$ brings herself into $$d=4$$, which we saw earlier is also a win for Bob.

For $$d=8$$, which should be the last case of interest, since it's Alice's $$d=3(+5)$$, we have straight away that both $$A3$$ and $$A2$$ lead to $$d=5$$ and $$d=6$$ respectively, where Bob has a win as seen before. Again however, Alice cannot force Bob into such lines with roles reversed with $$A0$$, since Bob can answer with $$B0$$, effectively re-reversing roles.

3. Conclusion Alice can thus never force Bob into "her" two winning cases $$d=2$$ and $$d=3$$, because Bob can prevent this by playing $$B0$$. In fact, Bob can continuously play $$B0$$ and let Alice close the distance with $$A2$$ and $$A3$$ until $$4\le d\le 6$$ when Bob either snaps the win or forces Alice to overshoot as seen above. This is in line with the observation that Alice must win with her initial move, otherwise Bob has a win. So in short, Bob in last position can always move when they are in a Bob's endgame line and always pass otherwise, effectively revearsing roles, or strategy-stealing.

# Part II: no second-to-last-move copycat

Spoiler: Alice wins for $$d\in \{2,3,4\}$$ and in $$(d\equiv 4\mod5).$$ Bob wins for $$d\in \{1,5,6,7,8,10...\}.$$

This game is what the author(s) must have had in mind, since $$d=94$$ is indeed a win for Alice. Interestingly, it comes with a new strategic option for Bob, which is to reduce to $$d\in \{2,3\}$$ when Alice is prevented from finishing due to her last move having been what is required. This allows Bob to steer into wins when $$(d\equiv 2 \mod5, d\gt5)$$. Notably for $$(d\equiv 3,4\mod 5)$$ however, Alice wins.

1. Discussion of first few cases

For $$d=1$$, we have again $$\{A0-B0-AX\}$$, and Bob wins.

For $$d \in \{2,3\}$$, Alice wins turn $$1$$.

For $$d=4$$, Alice wins with $$\{A3-B0-A0-BX\}$$ where she forces Bob into overshooting.

For $$d=5$$, again no changes, still $$\{A0-B0-A3-B2\}$$ and $$\{A0-B0-A2-B3\}$$ for a win for Bob.

For $$d=6$$, we have the trivial $$\{A3-B3\}$$, so Alice can't open $$A3$$. For $$A2$$, we have $$\{A2-B3-A0-B0-AX\}$$ where Bob brings $$d$$ down to $$1$$ and forces Alice to overshoot. For $$A0$$ lastly, Bob repeats with $$B0$$, denying the revearsing of roles and forcing Alice to open into $$d \in \{3,4\}$$. Note that Bob didn't play $$B0$$ turn $$2$$ before, which validates the prefix $$\{A0-B0-...\}$$.

For $$d=7$$, we have $$\{A3-B3-A0-B0-AX\}$$ where Bob reduces to $$d=1$$, and $$\{A2-B3-A0-B2\}$$, where Bob reduces to $$d=2$$ at a time when Alice can't close the game with $$A2$$, as this was her last move. This is the above-mentioned strategical play for Bob in position, and it highlights the power of position. For the $$A0$$ opening, note again that Bob is safe playing $$B0$$, since his follow-up do not need him to play a second turn $$B0$$ again, validating the prefix $$\{A0-B0-...\}$$. So $$\{A0-B0-A2-B3-A0-B2\}$$ and $$\{A0-B0-A3-B3-A0-B0-AX\}.$$

For $$d=8$$, Alice wins with $$A2$$, reducing to $$d=6$$ while holding the option of $$A0$$ next turn. Against $$A2$$, if Bob plays $$B2$$ and reduces to $$d=4$$, Alice can force Bob to overshoot in sequence $$\{A2-B2-A3-B0-A0-BX\}.$$ Against Bob's $$B3$$, Alice wins immediately with $$\{A2-B3-A3\}.$$ Lastly, should Bob reply with $$B0$$, Alice is now in position to re-revearse with $$\{A2-B0-A0-B2-A3-B0-A0-BX\}$$ or $$\{A2-B0-A0-B3-A3\}.$$ So, Alice wins for $$d=8$$ and for all $$(d\equiv 3\mod5,d \gt5)$$
For $$d=9$$ and in fact all $$(d\equiv 4\mod 5)$$, Alice wins.

2. Conclusion
The interpretation that the players may not repeat their own last move, i.e. the second to last move overall, helps Bob in position, in that it opens Bob up to reduce to $$d \in \{2,3\}$$ exactly when Alice is forced by the rules to play a move different from what's required to land on Bob's spot. However, Alice wins for initial $$(d\equiv 3,4\mod 5)$$, as well as initial $$d \in \{2,3\}$$ where Alice wins turn $$1$$.

This result is in line with your assumption.

# Part III: neither second-to-last-move nor last move copycat

Spoiler: Alice wins for $$d\in\{2,3\}$$ and for $$(d\equiv 1,2 \mod 5, d\gt5)$$.

It should be clear that the game is the same as the first one for $$d \in \{1,2,3,4,5\}$$. So, what about $$d\gt5$$?

For $$d=6$$, trivial is $$\{A3-B3\}$$. Against $$A2$$ however, Bob loses by force with all his replies, $$\{A2-B3-A0-B2\},\{A2-B2-A0-B3\},\{A2-B0-A3-B2\}.$$
This now highlights that starting with Bob's first move, we have repeating $$3$$-cycles, reducing to $$d-5$$ over three plies. Alice wins games where $$(d \equiv 1 \mod 5, d \ge 2).$$

For $$d=7$$, we have the same when Alice reduces to $$d=4$$ again, now with $$A3$$. We have $$\{A3-B3-A0-B2\}$$ and Bob overshoots, $$\{A3-B2-A0-B3\}$$ also overshooting, $$\{A3-B0-A2-B3\}$$ again overshooting. Alice wins games where $$(d \equiv 2 \mod 5, d \ge 5).$$

For $$d=8$$, Bob wins by completing to $$5$$ in $$\{A3-B2-A0-B3\}$$ and in $$\{A2-B3-A0-B2-A3\}$$ where Alice overshoots. Alice also loses with an initial $$A0$$ on the base of prefix $$\{A0-B0-...\}$$. Bob wins games where $$(d \equiv 3 \mod 5, d \ge 5).$$

For $$d=9$$, Bob wins with $$\{A3-B3-A2-B0-AX\}$$ and $$\{A3-B3-A0-B2-AX\}$$ against $$A3$$, and against $$A2$$ with $$\{A2-B3-A0-B2-AX\}.$$ The prefix case $$\{A0-B0\}$$ splits into the trivial tail against $$A2$$ with $$\{A0-B0-A2-B3-A0-B2-AX\}$$ and into the restricted case of $$\{A0-B0-A3-B2-A0-B3-AX\}$$ where Bob could not play $$B3$$ turn $$2$$ as opposed to above, but still wins. Bob wins games where $$(d \equiv 4 \mod 5, d \ge 5).$$

Bob also wins games where $$d \equiv 0 \mod 5, d \ge 2$$, since he can simply complete to $$5$$ or play our double pass-prefix.

2. Conclusion Since the game turns into cycles from turn $$2$$, Bob can no more prevent Alice from revearsing roles; instead, Alice now has options to steer the game into favourable endgames. That is, Alice wins for $$d\in\{2,3\}$$ and for $$(d\equiv 1,2 \mod 5, d\gt5)$$, Bob wins the rest.

• what do you mean by qoq ? in first line?\ Commented Jun 13, 2023 at 21:19
• codeforces.com/gym/445869/problem/F also in this site for the case of alice at 6 and bob at 100 , its given that alice will win , is it wrong then ? Commented Jun 13, 2023 at 21:27
• Regarding your edit: Bob cannot continuously play B0 according to the rules. Commented Jun 13, 2023 at 22:15
• where i said that @Piita? Commented Jun 17, 2023 at 7:44
• oh my mistake it was a typo mistake Commented Jun 17, 2023 at 7:45

I'd suggest a solution but I'm not sure if it's correct as I'm just a 13 year old interested in maths. Let's make this game easier to understand: The distance between Alice and Bob is b-a, each time Alice or Bob moves, the distance shrinks by either 0, 2, or 3. Now, we can think of this as a Nim-based game, but with some modifications: if the move played makes the value b-a negative, it's a loss. And, if Alice plays a move, Bob can't play it, vice versa. So, we try to analyze this from the last move of the game till the first one. We get subcases: primarily, if the move played before was 0 or not. If a player finds themselves at 1, they can only play 0 to win, that is if their opponent hasn't played it before. Meaning whoever gets to 1 first automatically wins. This is true for 2 and 3 too. But for 4, we see that whoever reaches there first wins, because they can play 0, forcing their opponent to play either 2 or 3, which guarantees a win. Notice that whoever moves once by 2 or 3 loses, because their opponent can spam 0's and they'd be forced to move by 2 or 3, until they reach 1,2 or 3 where we can move accordingly to win. thus, reviewing the rules, both players have all the choices for their first move, thus when bob plays 0, Alice has to play 2 or 3 which makes her lose. Thus Bob wins for all $$b-a\in \{1,4,5\cdots\}$$. For $$b-a=2,3$$ first one to move wins by picking 2 or 3, thus Alice wins.

• well explained @john smith , but still i believe some more justification is needed since for b-a being 94 its being said that alice wins Commented Jun 16, 2023 at 18:26
• I've told my programmer friend about it and he programmed the game to find that for 94 Bob wins. It's really obvious, since bob can always play 0 and Alice is forced to move, and since they can't move more than 3, then we get three cases, if bob finds him self at two or three, he plays that number, or else, if he finds him self at 1, he plays 0. Commented Jun 16, 2023 at 19:58
• actually john you said that if alice playes a move , bob cannot play it , but thats not what question says , the questions means that if alice or bob plays a move then in next turn they are not allowed to play that same move . Commented Jun 17, 2023 at 6:58

Alice always wins.

Let's note a position $$(d, i)$$ where $$d$$ is the distance $$b-a$$ and $$i$$ is the last move. The losing positions are of the form $$(2k, 2)$$, $$(2k+1, 0)$$ except that $$(3, 0)$$ is winning and $$(3, 3)$$ is losing. By inspection, we clearly can't get from a losing position to a losing position, and from each winning position, we can get to a losing position (For each winning position $$(d, x)$$, just do the forbidden move of the corresponding losing position).

We could see that Alice always wins by strategy stealing. Basically, moving by $$0$$ is like passing its turn, but the opponent has one less choice of movement. Suppose by contradiction that Bob has a winning strategy. Alice starts by moving by $$0$$, and observes Bob's responses for every sequence of moves she does. So Alice can learn the winning strategy of Bob, and use it against him, which is a contradiction since only one of them can have a winning strategy. See strategy stealing for more details.

• will not the losing and winning depends on (d,i,j) where i is the last move played by first and j is the last move played by second ? as in the game it clearly matters what the players move are now possible they can make Commented Jun 17, 2023 at 7:14
• Yes, the statement of the problem was really unclear, but it appears I misunderstood it Commented Jun 17, 2023 at 12:58