Minimax para Bomberman

Estoy desarrollando un clon del juego Bomberman y estoy experimentando con diferentes tipos de IA. Primero, utilicé la búsqueda en el espacio de estado con A * y ahora quiero probar un enfoque diferente con el algoritmo Minimax. Mi problema es que todos los artículos de minimax que encontré suponían jugadores alternativos. Pero en Bomberman, cada jugador realiza alguna acción al mismo tiempo. Creo que podría generar todos los estados posibles para una marca de juego, pero con cuatro jugadores y 5 acciones básicas (4 movimientos y lugar de bomba) da 5 ^ 4 estados en el primer nivel del árbol del juego. Ese valor aumentará exponencialmente con cada próximo nivel. ¿Me estoy perdiendo de algo? ¿Hay alguna forma de implementarlo o debería usar un algoritmo totalmente diferente? Gracias por cualquier sugerencia

Los juegos de estrategia en tiempo real como el bombardero tienen dificultades con la IA. Quieres que sea inteligente, pero al mismo tiempo no puede ser perfecto.

Si la IA es perfecta, tus jugadores se sentirán frustrados. Ya sea porque siempre pierden o obtienes 0,3 cuadros por segundo.

Si no es lo suficientemente inteligente, tus jugadores se aburrirán.

Mi recomendación es tener dos funciones de IA, una que determine dónde va la IA, la otra que determina cuándo es mejor lanzar una bomba. Puede usar cosas como la predicción de movimiento para determinar si un enemigo se está moviendo hacia un lugar que será peligroso si se arroja una bomba en la ubicación actual.

Dependiendo de la dificultad, puede modificar estas funciones para mejorar o disminuir la dificultad.

Como habrás notado, Bomberman es demasiado complejo para ser simulado como un juego por turnos. Extrapolar cualquier posible decisión propia más todas las decisiones posibles de cualquier otro jugador simplemente no funciona.

En lugar de eso, debería usar un enfoque más estratégico.

Deberías preguntarte: ¿cómo toma decisiones un jugador humano mientras juega a bomberman? Por lo general, un jugador debe seguir cuatro prioridades básicas:

1. evitar áreas de explosión de bombas
2. colocar bombas para que otros no puedan evitar sus áreas de explosión
3. recoger powerups
4. colocar bombas para hacer estallar rocas

La primera prioridad se puede cumplir creando un "mapa de peligro". Cuando se coloca una bomba, todas las fichas cubiertas por ella deben marcarse como "peligrosas". Cuanto antes explote la bomba (¡tenga en cuenta las reacciones en cadena!), Mayor será el nivel de peligro. Cada vez que la IA se da cuenta de que está en un campo con un alto peligro, debe alejarse. Cuando traza un camino (por cualquier razón), los campos con un alto nivel de peligro deben evitarse (pueden implementarse agregando artificialmente un costo de camino más alto para ellos).

El cálculo del mapa de peligro se puede mejorar aún más para proteger a la IA de decisiones estúpidas (como entrar en áreas de las que es difícil escapar cuando hay otro jugador cerca).

Esto ya debería crear una IA defensiva razonable. Entonces, ¿qué pasa con la ofensa?

Cuando la IA se da cuenta de que es razonablemente segura en este momento, debe planear maniobras ofensivas: debe considerar cómo puede aumentar el mapa de peligro alrededor de los otros jugadores colocando bombas en sí. Al elegir un lugar para plantar una bomba, debe preferir lugares cercanos para que no tenga que moverse tan lejos. También debe ignorar las ubicaciones de las bombas cuando el mapa de peligro resultante no permita una ruta de escape razonable.

Creo que podría generar todos los estados posibles para una marca de juego, pero con cuatro jugadores y 5 acciones básicas (4 movimientos y lugar de bomba) da 5 ^ 4 estados en el primer nivel del árbol del juego.

¡Correcto! Debes buscar todas las acciones 5 ^ 4 (o incluso 6 ^ 4, ya que puedes caminar en 4 direcciones, detenerte y "poner una bomba") para cada tic del juego. PERO, cuando un jugador ya decidió moverse, lleva un tiempo hasta que se ejecuta el movimiento (por ejemplo, 10 ticks del juego). Durante este período, el número de posibilidades se reduce.

Ese valor aumentará exponencialmente con cada próximo nivel. ¿Me estoy perdiendo de algo? ¿Hay alguna forma de implementarlo o debería usar un algoritmo totalmente diferente?

Puede usar una tabla hash para calcular solo el mismo estado del juego "subárbol" una vez. Imagina que el jugador A sube y baja, mientras que todos los demás jugadores "esperan", terminas en el mismo estado de juego. Es lo mismo que para "izquierda-derecha" o "derecha-izquierda". También mover "arriba-luego-izquierda" y "izquierda-entonces-arriba" da como resultado el mismo estado. Usando una tabla hash puedes "reutilizar" la puntuación calculada para un estado del juego que ya ha sido evaluado. Esto reduce bastante la velocidad de crecimiento. Matemáticamente, reduce la base de su función de crecimiento exponencial. Para tener una idea de cuánto reduce la complejidad, veamos los movimientos posibles para un solo jugador en comparación con las posiciones alcanzables en el mapa (= estados de juego diferentes) si el jugador puede simplemente moverse hacia arriba / abajo / izquierda / derecha / detener .

profundidad 1: 5 movimientos, 5 estados diferentes, 5 estados adicionales para esta recursión

profundidad 2: 25 movimientos, 13 estados diferentes, 8 estados adicionales para esta recursión

profundidad 3: 6125 movimientos, 25 estados diferentes, 12 estados adicionales para esta recursión

Para visualizar eso, responda usted mismo: qué campos en el mapa se pueden alcanzar con un movimiento, dos movimientos, tres movimientos. La respuesta es: Todos los campos con una distancia máxima = 1, 2 o 3 desde la posición inicial.

Al usar una HashTable solo tiene que evaluar cada estado de juego accesible (en nuestro ejemplo 25 en profundidad 3) una vez. Mientras que sin una HashTable necesita evaluarlas varias veces, lo que significaría 6125 evaluaciones en lugar de 25 en el nivel de profundidad 3. Lo mejor: una vez que calculó una entrada de HashTable, puede reutilizarla en pasos de tiempo posteriores ...

También puede usar subárboles de "corte" de profundización incremental y poda alfa-beta que no valen la pena buscar en mayor profundidad. Para el ajedrez, esto reduce el número de nodos buscados a aproximadamente 1%. Una breve introducción a la poda alfa-beta se puede encontrar en un video aquí: http://www.teachingtree.co/cs/watch?concept_name=Alpha-beta+Pruning

Un buen comienzo para más estudios es http://chessprogramming.wikispaces.com/Search . La página está relacionada con el ajedrez, pero los algoritmos de búsqueda y optimización son muy parecidos.

Otro (pero complejo) algoritmo de IA, que sería más adecuado para el juego, es el "Aprendizaje de la diferencia temporal".

Saludos

Stefan

PD: Si reduce el número de posibles estados de juego (por ejemplo, un tamaño muy pequeño del mapa, solo una bomba por jugador, nada más), existe la posibilidad de calcular previamente una evaluación para todos los estados del juego.

--editar--

También puede usar resultados calculados sin conexión de los cálculos de minimax para entrenar una red neuronal. O podría usarlos para evaluar / comparar estrategias implementadas a mano. Por ejemplo, podría implementar algunas de las "personalidades" sugeridas y algunas heurísticas que detectan, en qué situaciones, qué estrategia es buena. Por lo tanto, debe "clasificar" las situaciones (por ejemplo, estados de juego). Esto también podría ser manejado por una red neuronal: capacite a una red neuronal para predecir cuál de las estrategias codificadas a mano está jugando mejor en la situación actual y ejecutarla. Esto debería producir decisiones extremadamente buenas en tiempo real para un juego real. Mucho mejor que una búsqueda de límite de baja profundidad que se puede lograr de otra manera, ya que no importa cuánto demoren los cálculos fuera de línea (son antes del juego).

- editar # 2 -

Si solo recalcula tus mejores movimientos cada 1 segundo, también podrías intentar hacer un mayor nivel de planificación. ¿Qué quiero decir con eso? Sabes cuántos movimientos puedes hacer en 1 segundo. Por lo tanto, puede hacer una lista de posiciones alcanzables (por ejemplo, si se tratara de 3 movimientos en 1 segundo, tendría 25 posiciones alcanzables). Entonces podría planear como: vaya a "posición x y coloque una bomba". Como algunos otros sugirieron, puede crear un mapa de "peligro", que se utiliza para el algoritmo de enrutamiento (¿cómo ir a la posición x? ¿Qué ruta debe preferirse [existen algunas variaciones posibles en la mayoría de los casos]). Esto consume menos memoria en comparación con una gran HashTable, pero produce resultados menos óptimos. Pero como usa menos memoria, podría ser más rápido debido a los efectos de almacenamiento en caché (mejor uso de sus memorias caché L1 / L2).

ADICIONALMENTE: Podrías hacer búsquedas previas que solo contienen movimientos para un jugador cada uno para clasificar las variaciones que resultan en pérdida. Por lo tanto, saque a todos los demás jugadores del juego ... Almacene qué combinaciones puede elegir cada jugador sin perder. Si solo hay movimientos que pierden, busca las combinaciones de movimientos donde el jugador permanece vivo el mayor tiempo. Para almacenar / procesar este tipo de estructuras de árbol, debe usar una matriz con punteros de índice como este:

class Gamestate {
  int value;
  int bestmove;
  int moves[5];
};

#define MAX 1000000
Gamestate[MAX] tree;

int rootindex = 0;
int nextfree = 1;

Cada estado tiene un "valor" de evaluación y se vincula a los siguientes estados de juego cuando se mueve (0 = detener, 1 = arriba, 2 = derecha, 3 = abajo, 4 = izquierda) almacenando el índice de matriz dentro del "árbol" en los movimientos [0 ] a movimientos [4]. Para construir su árbol recursivamente, esto podría verse así:

const int dx[5] = { 0,  0, 1, 0, -1 };
const int dy[5] = { 0, -1, 0, 1,  0 };

int search(int x, int y, int current_state, int depth_left) {
  // TODO: simulate bombs here...
  if (died) return RESULT_DEAD;

  if (depth_left == 0) {
    return estimate_result();
  }

  int bestresult = RESULT_DEAD;

  for(int m=0; m<5; ++m) {
    int nx = x + dx[m];
    int ny = y + dy[m];
    if (m == 0 || is_map_free(nx,ny)) {
      int newstateindex = nextfree;
      tree[current_state].move[m] = newstateindex ;
      ++nextfree;

      if (newstateindex >= MAX) { 
        // ERROR-MESSAGE!!!
      }

      do_move(m, &undodata);
      int result = search(nx, ny, newstateindex, depth_left-1);
      undo_move(undodata);

      if (result == RESULT_DEAD) {
        tree[current_state].move[m] = -1; // cut subtree...
      }

      if (result > bestresult) {
        bestresult = result;
        tree[current_state].bestmove = m;
      }
    }
  }

  return bestresult;
}

Este tipo de estructura de árbol es mucho más rápido, ya que la asignación dinámica de memoria es realmente muy lenta. Pero, almacenar el árbol de búsqueda también es bastante lento ... Así que esto es más una inspiración.

¿Sería útil imaginar que todos se turnan?

Técnicamente, en el sistema subyacente, en realidad lo hacen, pero dado que las cosas están entrelazadas y superpuestas, parecen estar ejecutándose simultáneamente.

También recuerda que no tienes que ejecutar AI después de cada cuadro de animación. Muchos juegos casuales exitosos solo ejecutan el algoritmo de IA una vez por segundo más o menos, proporcionando a los personajes controlados por AI información sobre dónde se supone que deben ir o qué se supone que deben hacer, luego esa información se usa para controlar los personajes de IA en los otros cuadros.