¿Cómo puedo modelar y analizar matemáticamente un juego incremental como Cookie Clicker?

Question

Recientemente, me he interesado por la optimización del infame juego incremental Cookie Clicker .

Desde Wikipedia :

Al principio, el usuario hace clic en una cookie grande en la pantalla, ganando una cookie por clic. A continuación, puede gastar galletas en edificios, que producirán automáticamente galletas. Las actualizaciones pueden mejorar la eficiencia de los clics y los edificios, y otras mecánicas conducen a muchas otras formas en las que el usuario puede ganar galletas. Aunque el juego no tiene final, cuenta con cientos de logros, y los usuarios pueden aspirar a alcanzar números de galletas que marquen un hito.

El juego puede reducirse de forma simplista a nada más que la compra de edificios, para lo que crear una heurística de optimización no es excesivamente difícil ( especialmente cuando no se tienen en cuenta los resultados futuros ). Sin embargo, se complica mucho más cuando se introducen otras mecánicas como la venta de edificios para recuperar los costes y las mejoras de los edificios (que a menudo tienen múltiples predicados indirectos basados en otros edificios).

Tomemos un escenario extremadamente simplificado: ¿con qué rapidez podemos hornear 5000 galletas en total?

En esta simulación, asumo una generosa tasa de diez clics humanos por segundo, hago los cálculos como si las galletas hechas por el hombre no fueran discretas, y no tengo en cuenta la posibilidad de vender edificios por un 25% de retorno del coste.

Hay un total de tres edificios y tres mejoras (nombres abreviados para ser breves) que se pueden comprar por menos de 5000 galletas:

building | cost | Δcps |                    upgrade | cost | unlocked w/ |
---------|------|------|                    --------|------|-------------|
cursor   |   15 |  0.1 |                    C1      |  100 | 1 cursor    |
grandma  |  100 |    1 |                    C2      |  500 | 1 cursor    |
farm     | 1100 |    8 |                    G1      | 1000 | 1 grandma   |

Tenga en cuenta que el coste de los edificios es $\lceil c\times1.15^{n}\rceil$ donde $c$ es el coste base y $n$ es el número de ese tipo de edificio que ya se posee.

C1 y C2 duplican las galletas producidas por el ratón y los cursores, mientras que G1 duplica las galletas producidas por las abuelas.

Teniendo en cuenta estos parámetros, esta es la ruta "óptima" que mi simulación de fuerza bruta encontró, con un tiempo aproximado de 117,4 segundos:

time   | cps  | cost |
-------|------|------|
  0.00 |  10  |      | Begin clicking at 10 clicks per second (ergo 10 cookies per second).
  1.50 | 10.1 |   15 | Buy the first cursor. This unlocks C1 and C2.
 11.40 | 20.2 |  100 | Buy C1, doubling mouse/cursor production.
 36.15 | 40.4 |  500 | Buy C2, doubling mouse/cursor production.
 36.58 | 40.8 |   18 | Buy the second cursor.
 37.07 | 41.2 |   20 | Buy the third cursor.
 37.62 | 41.6 |   23 | Buy the fourth cursor.
 38.25 | 42.0 |   27 | Buy the fifth cursor.
 38.97 | 42.4 |   31 | Buy the sixth cursor.
 39.79 | 42.8 |   35 | Buy the seventh cursor.
 40.72 | 43.2 |   40 | Buy the eighth cursor.
 43.03 | 44.2 |  100 | Buy the first grandma. This unlocks G1.
 44.07 | 44.6 |   46 | Buy the ninth cursor.
 46.65 | 45.6 |  115 | Buy the second grandma.
 49.55 | 46.6 |  133 | Buy the third grandma.
 52.82 | 47.6 |  153 | Buy the fourth grandma.
 53.92 | 48.0 |   53 | Buy the tenth cursor.
 57.57 | 49.0 |  175 | Buy the fifth grandma.
 61.67 | 50.0 |  202 | Buy the sixth grandma.
 81.67 | 56.0 | 1000 | Buy G1, doubling grandma production. 
 85.80 | 58.0 |  232 | Buy the seventh grandma.
 90.39 | 60.0 |  267 | Buy the eighth grandma.
 95.49 | 62.0 |  306 | Buy the ninth grandma.
101.16 | 64.0 |  352 | Buy the tenth grandma.
107.48 | 66.0 |  405 | Buy the eleventh grandma.
114.53 | 68.0 |  466 | Buy the twelfth grandma.
115.42 | 68.4 |   61 | Buy the eleventh cursor.
116.44 | 68.8 |   70 | Buy the twelfth cursor.
117.39 | 68.8 |      | 5000 cookies baked! Question life choices.

(Es interesante que no se tengan en cuenta las explotaciones agrícolas. Han sido un edificio históricamente débil).

Sin embargo, sólo este pequeño microcosmos del juego real requirió unos 500 millones de intentos de fuerza bruta para generar esta estrategia. Evidentemente, esto no es práctico, es potencialmente subóptimo y, lo que es más importante, realmente insatisfactorio. Debe haber un enfoque matemático para optimizar este juego y otros sistemas que funcionan como éste, pero todavía no he encontrado tales modelos.

Answer 1

Suponga que tiene una secuencia de compras. Demuestre que el momento óptimo para comprar cada elemento de la secuencia es tan pronto como pueda pagarlo.

Con este lema en el banco, se puede considerar un conjunto de estados donde un estado es una tupla del número de cursores, granjas, mejoras de los cursores y mejoras de las granjas compradas. Forma un dígrafo donde cada estado tiene aristas hacia el estado con un cursor más, el estado con una abuelita más, etc. Por lo tanto, cada estado tiene hasta cinco aristas. Añade un nuevo vértice "Objetivo" y añade una arista desde cada estado hasta el objetivo. Da a las aristas pesos como el coste de la mejora dividido por la tasa de producción del estado de origen.

Entonces sólo tienes que hacer una búsqueda estándar del camino más corto (algoritmo de Dijkstra, A*, etc) en el gráfico. Esto debería ser mucho más eficiente que la fuerza bruta que describes.