Encontrar un algoritmo para el problema dado

Question

Vamos a suponer que tenemos un PVP escena de la pelea, en la que el 1 o 2 de los héroes, están luchando con 3 monstruos.

Los monstruos que los héroes están luchando son los siguientes:

Esqueleto (2 de este monstruo)

Salud: 1
Defensa: 0
Ataque: 1

Caballero de la muerte (1 de este monstruo)

Salud: 4
Defensa: 1
Ataque: 3

Cada vez que un héroe de los ataques, la defensa del monstruo es la reducción de los daños que el héroe ofertas.

Los héroes son los mismos, se puede utilizar uno de los dos ataques, un ataque, que se ocupa del 1 de daño a todos los enemigos, o un ataque, que se ocupa 3 de daño a un solo enemigo.

El objetivo de los héroes van a mantener como pocos daño como sea posible de los monstruos.

Si un solo héroe se enfrenta a esta amenaza, el óptimo sería, utilizar el ataque en masa, para matar a los dos Esqueletos primero con un disparo, y luego matar al Caballero de la Muerte en las siguientes dos vueltas, de esta manera mantener un daño total de: (3)+(3)=6. (si el único héroe intenta matar al Caballero de la Muerte en primer lugar, se necesita de dos vueltas para hacerlo, así que sostendrá (3+1+1)+(1+1)=7 los daños

Pero si dos héroes están presentes, sería más sabio de los héroes, a los pandilleros en el Caballero de la Muerte en primer lugar, con dos ataques(que eliminar de él) y, a continuación, desactive la esqueletos con un solo ataque en masa, o con dos simples ataques. De esta manera el total de los daños sufridos sería (1+1)=2. (si claro los Esqueletos con un solo ataque en masa, y el otro héroe ataca al Caballero de la Muerte, que podría sostener un total de (3)=6 daños, ya que aún se necesita una segunda vuelta para matar al Caballero de la Muerte.)

NOTA: el parantheses son los daños sufridos en un turno

¿Cómo puedo encontrar un algoritmo, que diría a mis héroes, que el ataque es más costo-digno para ellas? Yo podría tratar de fuerza bruta, pero en los grandes escenarios (es decir: 4 héroes vs 9 diferentes monstruos) es demasiado intensiva de recursos para lograr.

Esto podría ser utilizado en un pequeño script, lo que hace que algunos cálculos para mí, el cual será utilizado para el equilibrio de un juego de mesa que estoy en el progreso de decisiones. Si este no es el correcto de la pila sitio para mi pregunta, por favor, me apunte en la dirección correcta. Nota: sólo necesito un algoritmo, la cual debo usar, sin necesidad de programación asesoramiento necesario para la realización de la secuencia de comandos.

EDIT 1: Basado en este ejemplo, yo podría decir que el movimiento correcto es siempre el uno, que mata a la mayoría de los monstruos en un solo caso, pero esto no es correcto, si aumentamos los Caballeros de la Muerte de daño, por lo que el movimiento correcto debe tener una puntuación que se calcula mediante el ataque de monstruos, y el número de monstruos que pueden ser eliminados en un solo turno. Estoy en lo cierto al suponer esto?

Answer 1

El algoritmo depende de la definición de "mejor", es decir, algún tipo de rentabilidad de la función sobre la base del resultado de la batalla. En su ejemplo, la negativa de la rentabilidad es el número de rondas antes de que todos los enemigos están muertos; los buenos chicos/chicas intentan minimizar esa función y de los enemigos tratan de maximizar (que puede no ser el mismo que el trato tanto daño como sea posible).

En la misma línea, un "movimiento" no consiste de un solo jugador de atacar a otro jugador, pero todos los jugadores de una de las partes de ejecutar un ataque de cada uno, seguido por el resto de jugadores de la contraparte en la ejecución de un ataque de cada uno. Debido a un ataque de no alterar el estado de sus compañeros, el orden en el que cada uno de estos ataques por la misma parte que se ejecuta es inmaterial (pero se puede pre-optimizar la estrategia, evitando movimientos que involucran a atacar a un rival que acaba de morir durante la misma ronda).

Si hay un solo movimiento que mata a todo el resto de los oponentes, que es, obviamente, la mejor jugada; podríamos decir que se tiene de la pena de 1, porque se suma 1 al número total de movimientos necesarios para exterminar al enemigo.

En general, el precio de una mudanza es el máximo, a lo largo de todo posible enemigo contramovimientos, el precio de nuestra mejor respuesta a esa countermove.

Esta definición recursiva de los resultados en un algoritmo que está garantizado para terminar porque cada movimiento estrictamente disminuye el total de defensa del enemigo, que era finito, para empezar. Es probablemente a lo que te refieres como "fuerza bruta" y el nombre técnico es minimax para lo que deberían ser obvias razones.

La implementación más popular de este algoritmo contiene una optimización llamados alfa-beta de la poda. Se basa en la observación de que el ataque de fuerza bruta efectivamente se ejecuta a través de un árbol (todas las evoluciones posibles de la batalla), y que elimina ciertas ramas del árbol (evitando tener que correr a través de ellos), basado en la observación de que estas ramas están garantizados para no dar mejores resultados que las ramas que ya han sido examinados.

El WP artículo que el comentarista Michael Medvinsky se refiere a las menciones de nuevas mejoras.

Si el total de defensa de los enemigos es grande, entonces hay una heurística que va a dar un resultado inmediato, casi siempre óptima o casi óptima, sin recursividad: elegir los ataques que infligir el máximo daño a todos los enemigos combinado. Entre tales movimientos que causan igual al total de los daños, privilegio de los que "nivel" de la puntuación por la disminución tanto como sea posible, la más alta de defensa de la puntuación de un enemigo (por lo que su posterior multi-objetivo de los ataques siguen siendo más eficiente).

Este heurístico puede ser usada para cortar el árbol a una cierta profundidad.

Answer 2

Desea utilizar la clase de algoritmos como Minimax (https://en.wikipedia.org/wiki/Minimax). Lo que básicamente quiero hacer es hacer un árbol de todas las posibles juego de los estados que surgen en los próximos 2 o 3 turnos. Que le permite decidir qué mueve a hacer. Si hay un elemento de azar o aleatoriedad, usted puede usar una variante llamada Expectimax.

Algoritmos como estas son muy utilizadas frecuentemente en tic-tac-dedo del pie o de juego de ajedrez softwares (con un montón de cambios para mejorar la eficacia)