Optimal strategy for the Rope Climbing Game

Question

Define a two-player, turn-based climbing game as follows.

Each turn, players have the option to climb or tie a knot at his current position. If the player chooses to climb, there is a 50% chance that he advances his position by $1$, and a 50% that he falls down to the position of his highest knot. If the player chooses to tie a knot, he does so and remains at that position. The winner is the first player to climb to position $n$.

Details:

• This is a game of complete information, players can see each other's positions and the positions of their knots.

• Both players start at position $0$, with knots at position $0$.

Question. What is an optimal strategy for the rope climbing game?

The strategy should be a decision function based on five variables:

1. $x_1$ and $x_2$, the positions of the respective players

2. $k_1$ and $k_2$, the positions of the respective players' highest knots

3. the length of the rope, $n$

We can assume wlog that we're determining the strategy for player 1.

Elementary observations.

• Obviously whenever $x_1=k_1$ the decision should be to climb. For this reason, the strategy is always to climb when $n=1$. ($n=2$ and $n=3$ may be enlightening special cases.)

• As $x_1-k_1$ gets larger, climbing gets more risky. However, the smaller $n-x_2$ gets, the more worth it it is to take that risk.

Answer 1

Setting aside the game theoretic question, consider optimizing expected rate of climbing.

Strategy 1: Place a knot at every new position. The expected number of turns to climb one position is two, then one more turn to tie a knot, for 3 turns per position.

Strategy 2: Place a knot at every other new position. The expected number of turns to get two consecutive good results is 6 (see, e.g. here), plus one more to tie a knot, for 7 turns altogether.

Hence Strategy 1 takes 6 turns on average to climb two positions, while Strategy 2 takes 7. The pattern is that Strategy $k$ takes $2^{k+1}-1$ turns to climb $k$ positions, while Strategy 1 only takes $3k$, which is smaller.

Consequently, I think the best strategy is to use Strategy 1 almost all the time. The only exceptions are when your opponent is about to win and you're quite behind, so instead of maximizing average speed you need to maximize top speed. For example, if you're both one away from winning, but he's got a knot and you don't, you may wish to climb even without a knot. Half the time you will win or tie.

Answer 2

Sorry I haven't learned the formatting yet.

An answer for all n and all situations:

ASSUMPTIONS: A) The turns are not simultaneous

Every Turn

1. If X1 = K1 ............... CLIMB! (No sacrifice)

2. Otherwise if N-1=X1=X2 AND K1=K2..... CLIMB! (win at least 50% of the time)

3. Otherwise if N-2=X1=X2 AND K1=K2...... KNOT! (eventually win at least 50% of the time)

4. Otherwise consider your position:

4a) If you are still "winning" (that is X1>X2 OR (X1=X2 but K1>K2) .... KNOT! (NOTE: You will still be winning or tied, and you will have reduced your risk, but also see reasoning below)

4b) If you are still "tied" (X1=X2 AND K1=K2) ....... KNOT! (see reasoning below)

Now it gets tricky:

4c) If you are still "losing just a little" (X1=X2 BUT K2>K1) CLIMB! (50% you immediately catch up (because the following turn will be a KNOT for the other player anyway) or gain the lead, which is worth the 50% chance of remaining losing)

4d) If you are still "losing somewhat" (X1+1 =X2 AND K1=K2), you know player two will KNOT (4a), and you can only lose one position (considering 4e), so you might as well try to better your position to aim for 4c next time.

4e) If you are ever "losing by a lot" play the tortoise. KNOT whenever you aren't already on a knot. Now isn't the time for heroics. The larger N is, the better the tortoise.

Now for the promised reasoning below: For 1 player, the optimal speed is tortoise speed, KNOTing whenever achieving a new level. This example cited by another answer is instructive: Link

When N>>3, playing the hare when "losing by a lot" (Climbing without an adjacent knot), almost never wins because the distribution is heavily skewed to the right.

Let me give an example. Suppose you are 3 positions behind and N -X1 = 35. Flipping coins, the odds of getting 35 heads before 32 tails is less than 50% but is still quite common (tortoise). Compare this to getting 35 consecutive heads with one coin prior to getting 32 total tails on a second coin (Hare). Tortoise beats the hare. And thus a tortoise has the best chance of beating a tortoise.

Answer 3

Bare in mind with me here. I'm not truly a mathematician. However, I'm opinionated on failure cost and success. If you were to extract strictly and only the 50 50 at start point and compared a success with a fail. It's painfully obvious that failure truly costs you three times for one fail. If player1 succeeded. he is one unit up and player2 failed has gone nowhere. For player 2 to match if player one succeeded again, would have to win 3/1.

Basically, his schedule to of fail compensation would be stuck with the idea that the failure not only cost him the initial fail. But, also it costs him in catching up in accomplishing the one unit and what he could've accomplished if he had succeeded.

next consideration would be if it is worth his time to tie or attempt another jump. I would consider it a no brainer to tie as that failure compounded by the uncertainty of failing 2 units and compensating for it with an inkling of success would bring you down bellow the other by one unit.

player 1 would have a different thread of reasoning. Since player 2 failed, he would be wise to tie a knot. especially since this would secure a one unit advantage provide player 2 succeeded then tied a not with out consideration to player 1 attempts another jump as the result of a successful jump is invalid if failed. That reasoning is only a safety if he succeeds then he is 2 units ahead at risk of breaking into a tie with a second jump failed and the other player succeeding. if they ever tie, you're back at square one. wash, rinse repeat.

my conclusion would be if you succeed and the other fails, tie a knot since you're actions afforded for a 1 unit advantage even if the other succeeds the next time. again, attempt another jump without another knot. especially since your fail would only bring you favorably ahead since he should be smart enough to tie up to at the very least have a hope to win.