Intentando construir un algoritmo para la colocación óptima de la torre en un juego

StackOverflow https://stackoverflow.com/questions/1626189

  •  06-07-2019
  •  | 
  •  

Pregunta

Esta será una publicación larga y solo por diversión, así que si no tienes mucho tiempo mejor, ayuda a las personas con preguntas más importantes :)

Hay un juego llamado "Tower Bloxx" lanzado recientemente en xbox. Una parte del juego es colocar torres de diferentes colores en un campo de la manera más óptima para maximizar el número de torres más valiosas. Escribí un algoritmo que determinaría la ubicación más eficiente de la torre, pero no es muy eficiente y prácticamente solo obliga a todas las combinaciones posibles. Para un campo 4x4 con 4 tipos de torre, lo resuelve en aproximadamente 1 hora, 5 tipos de torre tomarían aproximadamente 40 horas, lo que es demasiado.

Estas son las reglas: Hay 5 tipos de torres que se pueden colocar en un campo. Hay varios tipos de campos, el más fácil es solo una matriz 4x4, otros campos tienen algunos espacios en blanco. donde no puedes construir. Su objetivo es poner tantas torres más valiosas en un campo como sea posible para maximizar el valor total de la torre en un campo (supongamos que todas las torres se construyen a la vez, no hay giros).

Tipos de torre (en orden de menor a mayor valor):

  • Azul: se puede colocar en cualquier lugar, valor = 10
  • Rojo: solo se puede colocar además del azul, valor = 20
  • Verde: colocado además de rojo y azul, valor = 30
  • Amarillo: además de verde, rojo y azul, valor = 40
  • Blanco: además de amarillo, verde, rojo y azul, valor = 100

Lo que significa que, por ejemplo, la torre verde debe tener al menos 1 torres rojas y 1 azules en las celdas vecinas norte, sur, oeste u este (las diagonales no cuentan). La torre blanca debe estar rodeada de todos los demás colores.

Aquí está mi algoritmo para 4 torres en campo 4x4:

  1. Número total de combinaciones = 4 ^ 16
  2. Pase por [1..4 ^ 16] y convierta cada número en una cadena base4 para codificar la ubicación de la torre, por lo que 4 ^ 16 = & 3333 3333 3333 3333 " que representaría nuestros tipos de torre (0 = azul, ..., 3 = amarillo)
  3. Convierta la cadena de colocación de la torre en matriz.
  4. Para cada torre en una matriz, verifique sus vecinos y si alguno de los requisitos falla, toda esta combinación falla.
  5. Coloque todas las combinaciones correctas en una matriz y luego ordene esta matriz como cadenas en orden lexicográfico para encontrar la mejor combinación posible (primero debe ordenar los caracteres en una cadena).

La única optimización que se me ocurrió es omitir combinaciones que no contienen las torres más valiosas. Se salta un poco de procesamiento, pero sigo recorriendo las 4 ^ 16 combinaciones.

¿Alguna idea de cómo se puede mejorar esto? Los ejemplos de código serían útiles si están en java o php.

-------Update--------

Después de agregar más estados ilegales (el amarillo no se puede construir en las esquinas, el blanco no se puede construir en las esquinas y en los bordes, el campo debe contener al menos una torre de cada tipo), dándose cuenta de que solo se podría construir una torre blanca En el campo 4x4 y optimizando el código Java, el tiempo total se redujo de 40 a ~ 16 horas. Tal vez el enhebrado lo reduciría a 10 horas, pero ese es probablemente el límite de fuerza bruta.

¿Fue útil?

Solución

Encontré esta pregunta intrigante, y dado que me estoy enseñando a mí mismo Haskell, decidí intentar implementar una solución en ese idioma.

Pensé en bifurcar y enlazar, pero no pude encontrar una buena manera de enlazar las soluciones, así que hice una poda descartando tableros que violan las reglas.

Mi algoritmo funciona comenzando con un " vacío " tablero. Coloca cada color posible de la torre en la primera ranura vacía y en cada caso (cada color) se llama recursivamente. Las llamadas recurrentes prueban cada color en la segunda ranura, recurriendo nuevamente, hasta que el tablero esté lleno.

A medida que se coloca cada torre, verifico la torre recién colocada y todos sus vecinos para verificar que están obedeciendo las reglas, tratando a los vecinos vacíos como comodines. Entonces, si una torre blanca tiene cuatro vecinos vacíos, lo considero válido. Si una ubicación no es válida, no recurro en esa ubicación, podando efectivamente todo el árbol de posibilidades debajo de ella.

La forma en que se escribe el código, genero una lista de todas las soluciones posibles, luego busco en la lista para encontrar la mejor. En realidad, gracias a la evaluación perezosa de Haskell, los elementos de la lista se generan cuando la función de búsqueda los necesita, y dado que nunca se hace referencia a ellos nuevamente, están disponibles para la recolección de basura de inmediato, por lo que incluso para un uso de memoria de placa 5x5 es bastante pequeño (2 MB).

El rendimiento es bastante bueno. En mi computadora portátil de 2.1 GHz, la versión compilada del programa resuelve el caso 4x4 en ~ 50 segundos, usando un núcleo. Estoy ejecutando un ejemplo de 5x5 en este momento para ver cuánto tiempo llevará. Dado que el código funcional es bastante fácil de paralelizar, también voy a experimentar con el procesamiento paralelo. Hay un compilador paralelo de Haskell que no solo distribuirá el trabajo en múltiples núcleos, sino también en varias máquinas, y este es un problema muy paralelo.

Aquí está mi código hasta ahora. Me doy cuenta de que especificó Java o PHP, y Haskell es bastante diferente. Si quieres jugar con él, puedes modificar la definición de la variable " bnd " justo encima de la parte inferior para establecer el tamaño del tablero. Simplemente configúrelo en ((1,1), (x, y)), donde x e y son el número de columnas y filas, respectivamente. 

import Array
import Data.List

-- Enumeration of Tower types.  "Empty" isn't really a tower color,
-- but it allows boards to have empty cells
data Tower = Empty | Blue | Red | Green | Yellow | White
             deriving(Eq, Ord, Enum, Show)

type Location = (Int, Int)
type Board = Array Location Tower

-- towerScore omputes the score of a single tower
towerScore :: Tower -> Int
towerScore White = 100
towerScore t     = (fromEnum t) * 10

-- towerUpper computes the upper bound for a single tower
towerUpper :: Tower -> Int
towerUpper Empty = 100
towerUpper t = towerScore t

-- boardScore computes the score of a board
boardScore :: Board -> Int
boardScore b = sum [ towerScore (b!loc) | loc <- range (bounds b) ]

-- boardUpper computes the upper bound of the score of a board
boardUpper :: Board -> Int
boardUpper b = sum [ bestScore loc | loc <- range (bounds b) ]
    where
      bestScore l | tower == Empty = 
                      towerScore (head [ t | t <- colors, canPlace b l t ])
                  | otherwise = towerScore tower
                  where 
                    tower = b!l
                    colors = reverse (enumFromTo Empty White)

-- Compute the neighbor locations of the specified location
neighborLoc :: ((Int,Int),(Int,Int)) -> (Int,Int) -> [(Int,Int)]
neighborLoc bounds (col, row) = filter valid neighborLoc'
    where
      valid loc = inRange bounds loc
      neighborLoc' = [(col-1,row),(col+1,row),(col,row-1),(col,row+1)]

-- Array to store all of the neighbors of each location, so we don't
-- have to recalculate them repeatedly.
neighborArr = array bnd [(loc, neighborLoc bnd loc) | loc <- range bnd]

-- Get the contents of neighboring cells
neighborTowers :: Board -> Location -> [Tower]
neighborTowers board loc = [ board!l | l <- (neighborArr!loc) ]

-- The tower placement rule.  Yields a list of tower colors that must
-- be adjacent to a tower of the specified color.
requiredTowers :: Tower -> [Tower]
requiredTowers Empty  = []
requiredTowers Blue   = []
requiredTowers Red    = [Blue]
requiredTowers Green  = [Red, Blue]
requiredTowers Yellow = [Green, Red, Blue]
requiredTowers White  = [Yellow, Green, Red, Blue]

-- cellValid determines if a cell satisfies the rule.
cellValid :: Board -> Location -> Bool
cellValid board loc = null required ||
                      null needed   ||
                      (length needed <= length empties)
    where
      neighbors = neighborTowers board loc
      required  = requiredTowers (board!loc)
      needed    = required \\ neighbors
      empties   = filter (==Empty) neighbors

-- canPlace determines if 'tower' can be placed in 'cell' without
-- violating the rule.
canPlace :: Board -> Location -> Tower -> Bool
canPlace board loc tower =
    let b' = board // [(loc,tower)]
    in cellValid b' loc && and [ cellValid b' l | l <- neighborArr!loc ]

-- Generate a board full of empty cells       
cleanBoard :: Array Location Tower
cleanBoard = listArray bnd (replicate 80 Empty)

-- The heart of the algorithm, this function takes a partial board
-- (and a list of empty locations, just to avoid having to search for
-- them) and a score and returns the best board obtainable by filling
-- in the partial board
solutions :: Board -> [Location] -> Int -> Board
solutions b empties best | null empties = b
solutions b empties best = 
    fst (foldl' f (cleanBoard, best) [ b // [(l,t)] | t <- colors, canPlace b l t ])
    where
      f :: (Board, Int) -> Board -> (Board, Int)
      f (b1, best) b2  | boardUpper b2 <= best = (b1, best)
                       | otherwise = if newScore > lstScore
                                     then (new, max newScore best)
                                     else (b1, best)
                       where
                         lstScore = boardScore b1
                         new      = solutions b2 e' best
                         newScore = boardScore new
      l = head empties
      e' = tail empties

colors = reverse (enumFromTo Blue White)

-- showBoard converts a board to a printable string representation
showBoard :: Board -> String
showBoard board = unlines [ printRow row | row <- [minrow..maxrow] ]
    where
      ((mincol, minrow), (maxcol, maxrow)) = bounds board
      printRow row = unwords [ printCell col row | col <- [mincol..maxcol] ]
      printCell col row = take 1 (show (board!(col,row)))

-- Set 'bnd' to the size of the desired board.                          
bnd = ((1,1),(4,4))

-- Main function generates the solutions, finds the best and prints
-- it out, along with its score
main = do putStrLn (showBoard best); putStrLn (show (boardScore best))
       where
         s = solutions cleanBoard (range (bounds cleanBoard)) 0
         best = s

Además, recuerde que este es mi primer programa Haskell no trivial. Estoy seguro de que se puede hacer de manera mucho más elegante y sucinta.

Actualización : Dado que todavía era mucho tiempo hacer un 5x5 con 5 colores (esperé 12 horas y no había terminado), eché otro vistazo a cómo usar el límite para pode más del árbol de búsqueda.

Mi primer enfoque fue estimar el límite superior de un tablero parcialmente lleno asumiendo que cada celda vacía está llena de una torre blanca. Luego modifiqué la función 'solución' para rastrear el mejor puntaje visto e ignorar cualquier tablero cuyo límite superior sea menor que ese mejor puntaje.

Eso ayudó a algunos, reduciendo una placa 4x4x5 de 23 a 15 años. Para mejorarlo aún más, modifiqué la función de límite superior para suponer que cada Vacío se llena con la mejor torre posible, de acuerdo con el contenido de celda no vacío existente. Eso ayudó mucho, reduciendo el tiempo de 4x4x5 a 2 segundos.

Ejecutarlo en 5x5x5 tomó 2600s, dando la siguiente placa: 

G B G R B
R B W Y G
Y G R B R
B W Y G Y
G R B R B

con una puntuación de 730.

Puedo hacer otra modificación y hacer que encuentre todos los tableros de puntuación máxima, en lugar de solo uno.

Otros consejos

Si no desea hacer A *, utilice un enfoque bifurcación y enlace . El problema debería ser relativamente fácil de codificar porque sus funciones de valor están bien definidas. Me imagino que deberías poder eliminar grandes secciones del espacio de búsqueda con relativa facilidad. Sin embargo, debido a que su espacio de búsqueda es bastante grande, aún puede tomar algo de tiempo. Solo una forma de averiguarlo :)

El artículo wiki no es el mejor del mundo. Google puede encontrar un montón de buenos ejemplos y árboles y cosas para ilustrar aún más el enfoque.

Una manera fácil de mejorar el método de fuerza bruta es explorar solo los estados legales. Por ejemplo, si está probando todos los estados posibles, probará muchos estados donde la esquina superior derecha es una torre blanca. Todos estos estados serán ilegales. No tiene sentido generar y probar todos esos estados. Por lo tanto, desea generar sus estados un bloque a la vez, y solo profundizar en el árbol cuando realmente se encuentre en un estado potencialmente válido. Esto reducirá su árbol de búsqueda en muchos órdenes de magnitud.

Puede haber más cosas elegantes que puede hacer, pero esta es una mejora fácil de entender (con suerte) para su solución actual.

Creo que querrá usar un algoritmo de ramificación y vinculación porque creo que encontrar una buena heurística para una implementación de A * será difícil (pero, esa es solo mi intuición).

El pseudocódigo para una implementación de bifurcación es: 

board = initial board with nothing on it, probably a 2D array

bestBoard = {}

function findBest(board)
  if no more pieces can be added to board then
     if score(board) > score(bestBoard) then
       bestBoard = board
     return
  else
    for each piece P we can legally add to board
      newBoard = board with piece P added
      //loose upper bound, could be improved
      if score(newBoard) + 100*number of blanks in newBoard > score(bestBoard)
        findBestHelper(newBoard)

La idea es que busquemos todos los tableros posibles, en orden, pero hacemos un seguimiento del mejor que hemos encontrado hasta ahora (este es el límite). Luego, si encontramos un tablero parcial que sabemos que nunca será mejor que el mejor hasta el momento, entonces dejamos de trabajar en ese tablero parcial: recortamos esa rama del árbol de búsqueda.

En el código anterior, estoy haciendo la verificación suponiendo que todos los espacios en blanco se llenarían con las piezas blancas, ya que no podemos hacer nada mejor que eso. Estoy seguro de que con un poco de pensamiento puede llegar a un límite más estricto que eso.

Otro lugar donde puede intentar optimizar es en el orden del ciclo for-each. Desea probar piezas en el orden correcto. Es decir, de manera óptima, desea que la primera solución sea la mejor, o al menos una con una puntuación realmente alta.

Parece que un buen enfoque sería comenzar con una torre blanca y luego construir un conjunto de torres a su alrededor en función de los requisitos, tratando de encontrar el conjunto de formas de color más pequeño posible que puedan actuar como mosaicos entrelazados.

Quería recomendar programación lineal con incógnitas enteras , pero resulta que es NP-hard incluso en el caso binario. Sin embargo, aún puede obtener un gran éxito al optimizar un problema como el suyo, donde hay muchas soluciones válidas y simplemente desea la mejor.

La programación lineal, para este tipo de problema, equivale esencialmente a tener muchas variables (por ejemplo, el número de torres rojas presentes en la celda (M, N)) y las relaciones entre las variables (por ejemplo, el número de las torres blancas en la celda (M, N) deben ser menores o iguales al número de torres del color no blanco que tiene el menor número, entre todos sus vecinos). Escribir un programa lineal es una molestia, pero si desea una solución que se ejecute en segundos, probablemente sea su mejor opción.

Has recibido muchos buenos consejos sobre el lado algorítmico de las cosas, así que no tengo mucho que agregar. Pero, suponiendo que Java sea el lenguaje, aquí hay algunas sugerencias bastante obvias para mejorar el rendimiento.

  • Asegúrese de que no está creando instancias de ningún objeto dentro de ese bucle 4 ^ 16. Es mucho, mucho más barato para la JVM reinicializar un objeto existente que crear uno nuevo. Incluso más barato usar matrices de primitivas. :)
  • Si puedes evitarlo, aléjate de las clases de colección. Agregarán muchos gastos generales que probablemente no necesite.
  • Asegúrese de no concatenar ninguna secuencia. Utilice StringBuilder.
  • Y, por último, considere volver a escribir todo en C.
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top