Estrategia óptima para el Juego de Escalar la Cuerda

Question

Define un juego de escalada entre dos jugadores por turnos de la siguiente manera.

En cada turno, los jugadores tienen la opción de escalar o atar un nudo en su posición actual. Si el jugador elige escalar, hay un 50% de probabilidad de que avance su posición en $1$, y un 50% de que caiga a la posición de su nudo más alto. Si el jugador elige atar un nudo, lo hace y permanece en esa posición. El ganador es el primer jugador en escalar a la posición $n$.

Detalles:

• Este es un juego de información completa, los jugadores pueden ver las posiciones uno del otro y las posiciones de sus nudos.

• Ambos jugadores comienzan en la posición $0$, con nudos en la posición $0$.

Pregunta. ¿Cuál es una estrategia óptima para el juego de escalada en cuerda?

La estrategia debe ser una función de decisión basada en cinco variables:

1. $x_1$ y $x_2$, las posiciones de los respectivos jugadores

2. $k_1$ y $k_2$, las posiciones de los respectivos nudos más altos de los jugadores

3. la longitud de la cuerda, $n$

Podemos asumir sin pérdida de generalidad que estamos determinando la estrategia para el jugador 1.

Observaciones elementales.

• Obviamente, cuando $x_1=k_1$ la decisión debería ser escalar. Por esta razón, la estrategia es siempre escalar cuando $n=1$. ($n=2$ y $n=3$ pueden ser casos especiales esclarecedores.)

• A medida que $x_1-k_1$ aumenta, escalar se vuelve más arriesgado. Sin embargo, cuanto más pequeño sea $n-x_2$, más vale la pena correr ese riesgo.

Answer 1

Dejando de lado la cuestión de la teoría de juegos, considera optimizar la tasa esperada de escalada.

Estrategia 1: Coloca un nudo en cada nueva posición. El número esperado de turnos para subir una posición es dos, luego un turno más para hacer el nudo, para un total de 3 turnos por posición.

Estrategia 2: Coloca un nudo en cada otra nueva posición. El número esperado de turnos para obtener dos resultados buenos consecutivos es 6 (ver, por ejemplo, aquí), más un turno adicional para hacer un nudo, para un total de 7 turnos en total.

Por lo tanto, la Estrategia 1 toma 6 turnos en promedio para subir dos posiciones, mientras que la Estrategia 2 toma 7. El patrón es que la Estrategia $k$ toma $2^{k+1}-1$ turnos para subir $k$ posiciones, mientras que la Estrategia 1 solo toma $3k$, que es menor.

En consecuencia, creo que la mejor estrategia es usar la Estrategia 1 casi todo el tiempo. Las únicas excepciones son cuando tu oponente está a punto de ganar y estás muy atrás, así que en lugar de maximizar la velocidad promedio necesitas maximizar la velocidad máxima. Por ejemplo, si ambos están a un paso de ganar, pero él tiene un nudo y tú no, puede que desees subir incluso sin un nudo. La mitad del tiempo ganarás o empatarás.

Answer 2

Lo siento, aún no aprendo el formato.

Una respuesta para todos los n y todas las situaciones:

ASUNCIONES: A) Las turnos no son simultáneos

Cada Turno

1. Si X1 = K1 ............... ¡SUBE! (Sin sacrificio)

2. De lo contrario, si N-1=X1=X2 Y K1=K2..... ¡SUBE! (ganar al menos el 50% de las veces)

3. De lo contrario, si N-2=X1=X2 Y K1=K2...... ¡ATAR! (eventualmente ganar al menos el 50% de las veces)

4. De lo contrario, considera tu posición:

4a) Si aún estás "ganando" (es decir, X1>X2 O (X1=X2 pero K1>K2) .... ¡ATAR! (NOTA: Seguirás ganando o empatado, y habrás reducido tu riesgo, pero también consulta el razonamiento a continuación)

4b) Si aún estás "empatado" (X1=X2 Y K1=K2) ....... ¡ATAR! (ver razonamiento a continuación)

Ahora se pone complicado:

4c) Si aún estás "perdiendo un poco" (X1=X2 PERO K2>K1) ¡SUBE! (50% alcanzas inmediatamente (porque el siguiente turno será un ATAR de todos modos para el otro jugador) o tomas la delantera, que vale la pena la probabilidad del 50% de seguir perdiendo)

4d) Si aún estás "perdiendo algo" (X1+1 =X2 Y K1=K2), sabes que el jugador dos ATARÁ (4a), y solo puedes perder una posición (considerando 4e), así que más vale intentar mejorar tu posición para apuntar a 4c la próxima vez.

4e) Si alguna vez estás "perdiendo por mucho" juega como la tortuga. ATAR cada vez que no estés ya en un ATAR. Ahora no es el momento para hazañas heroicas. Cuanto mayor sea N, mejor será la tortuga.

Ahora, el razonamiento prometido a continuación: Para 1 jugador, la velocidad óptima es la velocidad de la tortuga, ATANDO cada vez que se alcanza un nuevo nivel. Este ejemplo citado por otra respuesta es instructivo: Link

Cuando N>>3, jugar como la liebre cuando estás "perdiendo por mucho" (Subiendo sin un ATAR adyacente), casi nunca gana porque la distribución está muy sesgada hacia la derecha.

Déjame darte un ejemplo. Supongamos que estás 3 posiciones atrás y N -X1 = 35. Tirar monedas, las probabilidades de obtener 35 caras antes de 32 cruces son menos del 50% pero aún son bastante comunes (tortuga). Compara esto con obtener 35 consecutivas caras con una moneda antes de obtener 32 totales cruces en una segunda moneda (Liebre). La tortuga vence a la liebre. Y así, una tortuga tiene la mejor oportunidad de vencer a otra tortuga.

Answer 3

Mantente conmigo aquí. Realmente no soy un matemático. Sin embargo, tengo una opinión sobre el costo del fracaso y el éxito. Si solo extraerías el 50-50 en el punto de inicio y compararas un éxito con un fracaso. Es dolorosamente obvio que el fracaso realmente te cuesta tres veces por un fracaso. Si el jugador 1 tuvo éxito, está un punto arriba y el jugador 2 que fracasó no ha avanzado en absoluto. Para que el jugador 2 iguale si el jugador uno tuvo éxito nuevamente, tendría que ganar 3/1.

Básicamente, su plan de compensación por fracaso se vería atascado con la idea de que el fracaso no solo le costó el fracaso inicial. Sino también le cuesta ponerse al día en lograr el punto y lo que podría haber logrado si hubiese tenido éxito.

La siguiente consideración sería si vale la pena su tiempo empate o intentar otro salto. Consideraría que es obvio atar, ya que ese fracaso se ve agravado por la incertidumbre de fallar 2 puntos y compensarlo con una pizca de éxito te llevaría por debajo del otro por un punto.

El jugador 1 tendría un razonamiento diferente. Dado que el jugador 2 falló, sería sabio atar un nudo. Especialmente si esto asegura una ventaja de un punto proporcionada que el jugador 2 tenga éxito y luego ate un nudo sin considerar que el jugador 1 intente otro salto, ya que el resultado de un salto exitoso es inválido si falla. Ese razonamiento es solo una precaución si tiene éxito, entonces estará 2 unidades por delante con el riesgo de empatar con un segundo salto fallido y el otro jugador teniendo éxito. Si alguna vez se empatan, vuelves al punto de partida. Lava, enjuaga, repite.

Mi conclusión sería que si tienes éxito y el otro falla, ata un nudo ya que tus acciones te permitieron tener una ventaja de 1 unidad incluso si el otro tiene éxito la próxima vez. Nuevamente, intenta otro salto sin atarte otro nudo. Especialmente si tu fracaso solo te llevaría favorablemente adelante ya que él debería ser lo suficientemente inteligente para atar, como mínimo, para tener la esperanza de ganar.