Prova di costruire un algoritmo per il posizionamento ottimale della torre in un gioco

Question

Questo sarà un post lungo e solo per divertimento, quindi se non hai molto tempo meglio vai ad aiutare le persone con domande più importanti :)

Esiste un gioco chiamato " Tower Bloxx " recentemente rilasciato su xbox. Una parte del gioco consiste nel posizionare torri di diverso colore su un campo in modo ottimale per massimizzare il numero delle torri più preziose. Ho scritto un algoritmo che determinerebbe il posizionamento più efficiente della torre ma non è molto efficiente e praticamente solo forzando tutte le combinazioni possibili. Per il campo 4x4 con 4 tipi di torre lo risolve in circa 1 ora, 5 tipi di torre richiederebbero circa 40 ore, il che è troppo.

Ecco le regole: Esistono 5 tipi di torri che possono essere posizionate su un campo. Esistono diversi tipi di campi, il più semplice è solo una matrice 4x4, altri campi hanno alcuni "spazi vuoti". dove non puoi costruire. Il tuo obiettivo è mettere quante più torri più preziose su un campo per massimizzare il valore totale delle torri su un campo (supponiamo che tutte le torri siano costruite contemporaneamente, non ci sono curve).

Tipi di torre (in ordine dal meno prezioso al più prezioso):

• Blu: può essere posizionato ovunque, valore = 10
• Rosso: può essere posizionato solo oltre al blu, valore = 20
• Verde: posizionato oltre al rosso e al blu, valore = 30
• Giallo - oltre a verde, rosso e blu, valore = 40
• Bianco - oltre a giallo, verde, rosso e blu, valore = 100

Il che significa che, per esempio, la torre verde dovrebbe avere almeno 1 torre rossa e 1 blu nelle celle vicine nord, sud, ovest o est (le diagonali non contano). La torre bianca dovrebbe essere circondata con tutti gli altri colori.

Ecco il mio algoritmo per 4 torri su campo 4x4:

1. Numero totale di combinazioni = 4 ^ 16
2. Passa attraverso [1..4 ^ 16] e converti ogni numero in stringa base4 per codificare il posizionamento della torre, quindi 4 ^ 16 = "3333 3333 3333 3333 " che rappresenterebbe i nostri tipi di torre (0 = blu, ..., 3 = giallo)
3. Converti la stringa di posizionamento della torre in matrice.
4. Per ogni torre in una matrice controlla i suoi vicini e se uno qualsiasi dei requisiti fallisce, l'intera combinazione fallisce.
5. Metti tutte le combinazioni corrette in un array e quindi ordina questo array come stringhe nell'ordine lessicografico per trovare la migliore combinazione possibile (prima devi ordinare i caratteri in una stringa).

L'unica ottimizzazione che mi è venuta in mente è quella di saltare combinazioni che non contengono torri più preziose. Salta alcune elaborazioni ma continuo a scorrere tutte e 4 le 16 combinazioni.

Hai pensato a come migliorare? Esempi di codice sarebbero utili se in java o php.

Aggiornamento ------- --------

Dopo aver aggiunto altri stati illegali (il giallo non può essere costruito negli angoli, il bianco non può essere costruito negli angoli e sui bordi, il campo dovrebbe contenere almeno una torre di ogni tipo), rendendosi conto che potrebbe essere possibile costruire solo 1 torre bianca sul campo 4x4 e ottimizzando il codice java il tempo totale è stato ridotto da 40 a ~ 16 ore. Forse il threading lo ridurrebbe a 10 ore ma questo è probabilmente un limite di forzatura brutale.

Answer 1

Ho trovato questa domanda intrigante e, dato che sto insegnando a me stesso Haskell, ho deciso di provare a implementare una soluzione in quella lingua.

Ho pensato al branch-and-bound, ma non sono riuscito a trovare un buon modo per delimitare le soluzioni, quindi ho fatto un po 'di potatura scartando le board che violano le regole.

Il mio algoritmo funziona iniziando con un " vuoto " tavola. Posiziona ogni possibile colore della torre nel primo slot vuoto e in ogni caso (ogni colore) quindi si chiama ricorsivamente. Le chiamate ricorrenti provano ogni colore nel secondo slot, ripetendo nuovamente, fino a quando la scheda è piena.

Quando ogni torre viene posizionata, controllo la torre appena posizionata e tutti i suoi vicini per verificare che obbediscano alle regole, trattando i vicini vuoti come jolly. Quindi, se una torre bianca ha quattro vicini vuoti, la considero valida. Se un posizionamento non è valido, non ricerco su quel posizionamento, potando efficacemente l'intero albero di possibilità sotto di esso.

Il modo in cui viene scritto il codice, genera un elenco di tutte le possibili soluzioni, quindi guardo l'elenco per trovare la migliore. In realtà, grazie alla valutazione pigra di Haskell, gli elementi dell'elenco vengono generati quando la funzione di ricerca ne ha bisogno e, poiché non vengono mai più citati, diventano immediatamente disponibili per la garbage collection, quindi anche per un utilizzo della memoria della scheda 5x5 è abbastanza piccolo (2 MB).

Le prestazioni sono abbastanza buone. Sul mio laptop a 2.1 GHz, la versione compilata del programma risolve la custodia 4x4 in ~ 50 secondi, utilizzando un core. Sto eseguendo un esempio 5x5 in questo momento per vedere quanto tempo ci vorrà. Poiché il codice funzionale è abbastanza facile da parallelizzare, sto anche sperimentando l'elaborazione parallela. C'è un compilatore Haskell parallelizzato che non solo diffonderà il lavoro su più core, ma anche su più macchine, e questo è un problema molto parallelizzabile.

Ecco il mio codice finora. Mi rendo conto che hai specificato Java o PHP e Haskell è abbastanza diverso. Se vuoi giocarci, puoi modificare la definizione della variabile " bnd " appena sopra il fondo per impostare le dimensioni della scheda. Basta impostarlo su ((1,1), (x, y)), dove xey sono rispettivamente il numero di colonne e righe.

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

Inoltre, ricorda che questo è il mio primo programma Haskell non banale. Sono sicuro che può essere fatto in modo molto più elegante e succinto.

Aggiornamento : dato che era ancora molto tempo fare un 5x5 con 5 colori (ho aspettato 12 ore e non era ancora finito), ho dato un'altra occhiata a come usare il bounding per potare più dell'albero di ricerca.

Il mio primo approccio è stato quello di stimare il limite superiore di una tavola parzialmente riempita assumendo che ogni cella vuota fosse riempita con una torre bianca. Ho quindi modificato la funzione "soluzione" per tenere traccia del punteggio migliore visto e ignorare qualsiasi board il cui limite superiore sia inferiore al punteggio migliore.

Ciò ha aiutato alcuni, riducendo una scheda 4x4x5 da 23 a 15 secondi. Per migliorarlo ulteriormente, ho modificato la funzione del limite superiore per assumere che ogni vuoto sia riempito con la migliore torre possibile, coerentemente con il contenuto esistente di celle non vuote. Ciò ha aiutato moltissimo, riducendo il tempo di 4x4x5 a 2 secondi.

L'esecuzione su 5x5x5 ha richiesto 2600, dando la seguente scheda:

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 un punteggio di 730.

Potrei fare un'altra modifica e fare in modo che trovi tutte le schede con punteggio massimo, piuttosto che solo una.

Answer 2

Se non vuoi fare A *, usa un approccio branch and bound . Il problema dovrebbe essere relativamente semplice da codificare perché le funzioni del valore sono ben definite. Immagino che dovresti essere in grado di eliminare enormi sezioni dello spazio di ricerca con relativa facilità. Tuttavia, poiché lo spazio di ricerca è piuttosto grande, potrebbe richiedere del tempo. Solo un modo per scoprirlo :)

L'articolo wiki non è il migliore al mondo. Google può trovare un sacco di bei esempi, alberi e cose per illustrare ulteriormente l'approccio.

Answer 3

Un modo semplice per migliorare il metodo della forza bruta è esplorare solo stati legali. Ad esempio, se stai provando tutti i possibili stati, testerai molti stati in cui l'angolo in alto a destra è una torre bianca. Tutti questi stati saranno illegali. Non ha senso generare e testare tutti questi stati. Quindi vuoi generare i tuoi stati un blocco alla volta e approfondire l'albero solo quando sei effettivamente in uno stato potenzialmente valido. Ciò ridurrà il tuo albero di ricerca di molti ordini di grandezza.

Potrebbero esserci altre cose fantasiose che puoi fare, ma questo è un miglioramento (si spera) facile da capire della tua attuale soluzione.

Answer 4

Penso che vorrai usare un algoritmo branch-and-bound perché penso che trovare una buona euristica per un'implementazione A * sarà difficile (ma, questa è solo la mia intuizione).

Lo pseudo-codice per un'implementazione diramata è:

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)

L'idea è che cerchiamo tutte le schede possibili, in ordine, ma teniamo traccia di quella migliore che abbiamo trovato finora (questo è il limite). Quindi, se troviamo una tavola parziale che sappiamo che non sarà mai migliore della migliore finora, allora smettiamo di cercare di lavorare su quella tavola parziale: tagliamo quel ramo dell'albero di ricerca.

Nel codice sopra sto facendo il controllo supponendo che tutti gli spazi verrebbero riempiti dai pezzi bianchi, dato che non possiamo fare di meglio. Sono sicuro che con un po 'di pensiero puoi trovare un limite più stretto di così.

Un altro posto in cui puoi provare a ottimizzare è nell'ordine del ciclo for-each. Vuoi provare i pezzi nell'ordine corretto. Cioè, in modo ottimale, vuoi che la prima soluzione sia la migliore, o almeno una con un punteggio davvero alto.

Answer 5

Sembra che un buon approccio sarebbe iniziare con una torre bianca e quindi costruire una serie di torri attorno ad essa in base ai requisiti, cercando di trovare il più piccolo set di forme colorate possibile che possano fungere da tessere ad incastro.

Answer 6

Volevo sostenere programmazione lineare con incognite intere , ma risulta che è NP-difficile anche nel caso binario. Tuttavia, puoi comunque ottenere un grande successo nell'ottimizzare un problema come il tuo, dove ci sono molte soluzioni valide e vuoi semplicemente la migliore.

La programmazione lineare, per questo tipo di problema, equivale essenzialmente ad avere molte variabili (ad esempio, il numero di torri rosse presenti nella cella (M, N)) e relazioni tra le variabili (ad esempio, il numero di le torri bianche nella cella (M, N) devono essere inferiori o uguali al numero di torri del colore non bianco che ha il numero più piccolo, tra tutti i suoi vicini). Scrivere un programma lineare è una seccatura, ma se vuoi una soluzione che funzioni in pochi secondi, è probabilmente la soluzione migliore.

Answer 7

Hai ricevuto molti buoni consigli sul lato algoritmico delle cose, quindi non ho molto da aggiungere. Ma, supponendo che Java sia il linguaggio, ecco alcuni suggerimenti abbastanza ovvi per il miglioramento delle prestazioni.

• Assicurati di non creare istanze di oggetti all'interno di quel ciclo 4 ^ 16. È molto, molto più economico per la JVM reinizializzare un oggetto esistente piuttosto che crearne uno nuovo. Ancora più economico usare array di primitivi. :)
• Se puoi aiutarlo, allontanati dalle classi di raccolta. Aggiungeranno molte spese generali che probabilmente non ti serviranno.
• Assicurati di non concatenare alcuna stringa. Usa StringBuilder.
• E infine, considera di riscrivere il tutto in C.