Considere el simple juego de defensa de la torre en los detalles. ¿Qué es un algoritmo / estrategia que minimizará la cantidad de torres destruidas? ¿Qué es un algoritmo / estrategia que maximizará el número de torres destruidas?

Answer 1

Definiciones:

El subíndice [math] t \ in \ mathbb {N} \ cup \ {0 \} [/ math] en [math] r_t [/ math], [math] s_t [/ math] y [math] p_t [/ matemática] designa el valor de esas variables en ese número redondo. Inicialmente hay [math] r_0 = [/ math] gameTowers torres y [matemáticas] s_0 = [/ matemáticas] juego Soldados soldados. Cada soldado comienza con [matemáticas] 1 [/ matemáticas] punto de vida (vida); en otras palabras, muere si le disparan al menos [matemáticas] 1 [/ matemáticas] tiempo. Cada soldado vivo puede disparar [matemáticas] 1 [/ matemáticas] tiempo por ronda, solo en una torre que estaba viva al comienzo de la ronda. Cada torre comienza con [math] h = [/ math] numHits puntos de vida (vida), por lo que el equipo de la torre comienza con [math] p_0 = r_0h [/ math] puntos de vida total. Cada torre viviente puede disparar [math] k = [/ math] numKills veces por ronda, solo a los soldados que estaban vivos al comienzo de la ronda. En cada ronda, primero todos los soldados atacan simultáneamente, luego todas las torres atacan simultáneamente.

Hay al menos cuatro casos a los que podría referirse esta pregunta, dependiendo de los objetivos del equipo de la torre [matemáticas] T [/ matemáticas] y el equipo de soldados [matemáticas] S [/ matemáticas].

Caso A:
[math] T [/ math] está tratando de minimizar el número de torres destruidas, mientras que [math] S [/ math] está tratando de maximizar el número de torres destruidas. Este parece ser el caso más natural.

Caso B:
Tanto [math] T [/ math] como [math] S [/ math] están tratando de maximizar el número de torres destruidas.

Caso C:
Tanto [math] T [/ math] como [math] S [/ math] están tratando de minimizar el número de torres destruidas.

Caso D:
[math] T [/ math] está tratando de maximizar el número de torres destruidas, mientras que [math] S [/ math] está tratando de minimizar el número de torres destruidas. Este parece ser el caso más antinatural.

Responder:

Estas son las estrategias óptimas para [matemáticas] T [/ matemáticas] y [matemáticas] S [/ matemáticas] en una ronda determinada. También se proporciona el conteo de la torre y el soldado en cada ronda si se emplean estas estrategias.

Caso A:
[matemáticas] T [/ matemáticas]:
No hay dos disparos de torre en el mismo soldado.
[matemáticas] S [/ matemáticas]:
Enfoca exactamente tantos disparos en la torre más débil como sea necesario para destruir la torre más débil. Con los disparos restantes, enfoca exactamente tantos disparos como sean necesarios para destruir la próxima torre más débil. Si la siguiente más débil también se destruye, concéntrate en la próxima torre más débil, y así sucesivamente.

[matemáticas] r_t = \ begin {cases} \ text {gameTowers} & \ text {,} t = 0 \\ \ lceil \ frac {p_t} {h} \ rceil & \ text {, de lo contrario} \ end {cases} [/matemáticas]
[matemáticas] s_t = \ begin {cases} \ text {gameSoldiers} & \ text {,} t = 0 \\ \ max {(0, s_ {t-1} -r_tk)} & \ text {, de lo contrario} \ end {cases} [/ math]
[matemáticas] p_t = \ begin {cases} r_0h & \ text {,} t = 0 \\ \ max {(0, p_ {t-1} -s_ {t-1})} & \ text {, de lo contrario} \ end {cases} [/ math]

Caso B:
[matemáticas] T [/ matemáticas]:
Todas las torres disparan al mismo soldado.
[matemáticas] S [/ matemáticas]:
Enfoca exactamente tantos disparos en la torre más débil como sea necesario para destruir la torre más débil. Con los disparos restantes, enfoca exactamente tantos disparos como sean necesarios para destruir la próxima torre más débil. Si la siguiente más débil también se destruye, concéntrate en la próxima torre más débil, y así sucesivamente.

[matemáticas] r_t = \ begin {cases} \ text {gameTowers} & \ text {,} t = 0 \\ \ lceil \ frac {p_t} {h} \ rceil & \ text {, de lo contrario} \ end {cases} [/matemáticas]
[matemáticas] s_t = \ begin {cases} \ text {gameSoldiers} & \ text {,} t = 0 \\ s_ {t-1} & \ text {,} r_t = 0 \\ \ max {(0, s_ {t-1} -1)} & \ text {, de lo contrario} \ end {cases} [/ math]
[matemáticas] p_t = \ begin {cases} r_0h & \ text {,} t = 0 \\ \ max {(0, p_ {t-1} -s_ {t-1})} & \ text {, de lo contrario} \ end {cases} [/ math]

Caso C:
[matemáticas] T [/ matemáticas]:
No hay dos disparos de torre en el mismo soldado.
[matemáticas] S [/ matemáticas]:
En general, distribuya los disparos de la manera más uniforme posible entre las torres (nunca debe haber más de [matemática] 1 [/ matemática] de diferencia de puntos de vida entre dos torres). Sin embargo, tan pronto como una torre llega a [matemáticas] 0 [/ matemáticas] puntos de golpe en una ronda, todos los disparos restantes en la ronda están en esa torre recién muerta.

[matemáticas] r_t = \ begin {cases} \ text {gameTowers} & \ text {,} t = 0 \\ p_t & \ text {,} s_ {t-1}> 0, r_ {t-1}> p_ {t-1} -s_ {t-1} \\ r_ {t-1} & \ text {, de lo contrario} \ end {cases} [/ math]
[matemáticas] s_t = \ begin {cases} \ text {gameSoldiers} & \ text {,} t = 0 \\ \ max {(0, s_ {t-1} -r_tk)} & \ text {, de lo contrario} \ end {cases} [/ math]
[matemáticas] p_t = \ begin {cases} r_0h & \ text {,} t = 0 \\ \ max {(0, r_ {t-1} -1)} & \ text {,} s_ {t-1} > 0, r_ {t-1}> p_ {t-1} -s_ {t-1} \\ \ max {(0, p_ {t-1} -s_ {t-1})} & \ text { , de lo contrario} \ end {cases} [/ math]

Caso D:
[matemáticas] T [/ matemáticas]:
Todas las torres disparan al mismo soldado.
[matemáticas] S [/ matemáticas]:
En general, distribuya los disparos de la manera más uniforme posible entre las torres (nunca debe haber más de [matemática] 1 [/ matemática] de diferencia de puntos de vida entre dos torres). Sin embargo, tan pronto como una torre llega a [matemáticas] 0 [/ matemáticas] puntos de golpe en una ronda, todos los disparos restantes en la ronda están en esa torre recién muerta.

[matemáticas] r_t = \ begin {cases} \ text {gameTowers} & \ text {,} t = 0 \\ p_t & \ text {,} s_ {t-1}> 0, r_ {t-1}> p_ {t-1} -s_ {t-1} \\ r_ {t-1} & \ text {, de lo contrario} \ end {cases} [/ math]
[matemáticas] s_t = \ begin {cases} \ text {gameSoldiers} & \ text {,} t = 0 \\ s_ {t-1} & \ text {,} r_t = 0 \\ \ max {(0, s_ {t-1} -1)} & \ text {, de lo contrario} \ end {cases} [/ math]
[matemáticas] p_t = \ begin {cases} r_0h & \ text {,} t = 0 \\ \ max {(0, r_ {t-1} -1)} & \ text {,} s_ {t-1} > 0, r_ {t-1}> p_ {t-1} -s_ {t-1} \\ \ max {(0, p_ {t-1} -s_ {t-1})} & \ text { , de lo contrario} \ end {cases} [/ math]

Answer 2

Los principales elementos estratégicos de los juegos normales de defensa de la torre son cosas como la colocación de la torre y las actualizaciones. Con la configuración simplificada que tiene aquí, el jugador de la torre no tiene que tomar ninguna decisión. Del mismo modo, dado que los soldados apuntan al azar, ese jugador no tiene que tomar decisiones, y el juego no tiene ninguna estrategia.

Si se permitiera a los soldados apuntar a los objetivos, entonces la estrategia óptima para el soldado-jugador sería tener exactamente el número de soldados disparando a cualquier objetivo por ronda. Si hay un resto ( rem ) en la división de los soldados del juego entre numHits y el daño se transfiere entre rondas, los soldados rem adicionales deben apuntar a la misma torre, que luego serán atacados por soldados (numHits – rem) en la próxima ronda. El objetivo es matar torres lo más rápido posible para minimizar la tasa de retorno de muerte infligida a los soldados.

Dependiendo de los valores de los parámetros iniciales, la peor estrategia para el soldado-jugador es distribuir el fuego de manera uniforme en todas las torres o concentrar todo el fuego en matar una sola torre. Lo peor es el que mata las torres más lentamente, lo que se puede determinar comparando numHits con la proporción de gameSoldiers a gameTowers.