Optimal strategy for the Rope Climbing Game
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:
$x_1$ and $x_2$, the positions of the respective players
$k_1$ and $k_2$, the positions of the respective players' highest knots
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.
Solution 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.