Juego de adivinar números con respuestas caras

Question

Juego a adivinar números con enteros positivos y un límite superior constante conocido. Cada vez que adivino el número tengo que pagar 1 dólar, pero si mi compañero responde "Sí" tengo que pagar 9 más.

¿Cuál es la mejor estrategia para minimizar mi coste medio del juego (aparte de no jugar)?

¿Cambia la estrategia si tengo que pagar más/menos por los aciertos?

Answer 1

El orden no importa aquí, sólo el tamaño del espacio de búsqueda. Como cada pregunta es sí/no, divide el espacio en dos partes, y el único parámetro que importa para cada pregunta es cómo dimensionar esas partes. Esto nos permite calcular el coste esperado de forma recursiva. Definir $T(n)$ para ser el coste medio de hacer suficientes preguntas para determinar el número de un espacio de búsqueda de $n$ . Por definición $T(1)=0$ (técnicamente el juego no termina hasta que hayas adivinado el número, pero esto sólo añade $O(1)$ al coste, por lo que jugaré con esta distinción).

Para $n \ge 2$ el coste esperado de preguntar "es el número en un subconjunto dado de tamaño $k$ ?" y seguir jugando en el espacio de búsqueda restante es $1 + \frac{k}{n} (9 + T(k)) + \frac{n-k}{n} T(n-k)$ . Así que optimizamos esta cantidad sobre todas las $0 < k < n$ :

$$T(n) = \min_{0<k<n} 1 + \frac{k}{n} (9 + T(k)) + \frac{n-k}{n} T(n-k) = 1 + \frac1n \min_{0<k<n} (9k + kT(k) + (n-k)T(n-k)).$$

Esto da un valor óptimo de $T(100) = 26.5$ , sustancialmente mejor que CJ de la respuesta de buherator (suponiendo que estemos de acuerdo en el $O(1)$ convención). He calculado los costes y movimientos óptimos hasta $n=10000$ .

Una estrategia óptima para $n=10000$ cuesta alrededor de $52.1$ y la primera pregunta es "¿está el número en el rango $[1,1607]$ ?" Esto tiene un $0.1607$ posibilidad de coste $10$ más el coste de resolver el tamaño $1607$ problema (que es $\approx 41.956$ ), y un $0.8393$ posibilidad de coste $1$ más el coste de resolver el tamaño $8393$ problema (que es $\approx 51.127$ ).

Este ejemplo sugiere que el límite óptimo se encuentra aproximadamente donde los dos casos se equilibran en coste , al igual que en el caso simétrico. Si hacemos esta suposición, podemos hacer un buen trabajo de aproximación a la estrategia óptima. El valor de $T(n)$ está a priori entre $\log_2 n$ y $10 \log_2 n$ : hacemos el ansatz de que es asintótica a $c \log n$ para alguna constante $c$ . Entonces, el corte óptimo se produce cuando

$$9 + c \log k = c \log(n-k) \implies \frac{k}{n} = \frac{1}{1 + e^{9/c}}.$$

Por otro lado (siempre bajo la hipótesis clave) el coste también es igual al número de iteraciones que descienden a la mitad grande, por lo que $c = -1/\log(1-\epsilon)$ . Esto da dos ecuaciones en $\epsilon$ y $c$ :

$$\epsilon = \frac{1}{1 + e^{9/c}}, c = -1/\log(1-\epsilon),$$ que tiene la solución numérica $\epsilon \approx 0.164922, c \approx 5.548537$ . Así que yo conjeturaría que la estrategia óptima se acerca a "¿está el número en el primer 16,5% del rango actual?" La relación real parece ser bastante no monótona, variando hacia arriba y hacia abajo entre $0.14$ y $0.17$ como $n$ aumenta, incluso para grandes $n$ . Esto podría deberse a errores de redondeo en mi cálculo (podríamos estar comparando varios $k$ valores cuyas puntuaciones son realmente cercanas), pero si no es así entonces sugiere que la desviación entre el óptimo $k$ y $\epsilon n$ es algo más que redondear a un valor entero de $k$ .

Answer 2

Así que después de todo, armamos un pequeño ejemplo de script para la simulación:

https://gitorious.org/campzer0/numberguessing/

Aplicamos el enfoque lineal ingenuo y dos versiones modificadas de la búsqueda binaria:

• synalgo realiza una búsqueda binaria simple e intenta estimar el coste restante esperado. Si el coste esperado de seguir adelante con la búsqueda binaria es mayor que el coste esperado de la búsqueda lineal, vuelve a la búsqueda lineal
• cj realiza una búsqueda binaria modificada en la que el espacio de búsqueda se divide en la proporción de los costes de respuesta buena/respuesta mala - en el caso descrito en las preguntas el algoritmo siempre pregunta si el número está en el 1/10 inferior del intervalo actual. Este algoritmo también vuelve a la búsqueda lineal cuando el 1/10 del intervalo es inferior a 1

Tras 10000 ejecuciones con un límite superior de 100, los resultados son los siguientes:

naive average of 10000 runs: 59.8012 
synalgo average of 10000 runs: 32.9129 
cj average of 10000 runs: 30.9006

CJ suele ser un ~10% mejor que synalgo y ambos presentan buenos resultados en comparación con el enfoque ingenuo.

Por supuesto, estos algoritmos no han demostrado ser (casi) óptimos, pero proporcionan una eficiencia aceptable para mi problema actual. No obstante, ¡cualquier otra propuesta de optimización será bienvenida!