Essayer de construire un algorithme pour un placement optimal de la tour dans un jeu

Question

Cela va être un long post et juste pour le plaisir, donc si vous n'avez pas beaucoup de temps, allez plutôt aider les gens avec des questions plus importantes à la place:)

Il existe un jeu appelé "Tower Bloxx". récemment publié sur xbox. Une partie du jeu consiste à placer différentes tours de couleurs différentes sur un champ de manière optimale afin de maximiser le nombre de tours les plus précieuses. J'ai écrit un algorithme qui déterminerait le placement de tour le plus efficace, mais il n'est pas très efficace et ne fait que forcer brutalement toutes les combinaisons possibles. Pour un champ 4x4 avec 4 types de tours, le temps de résolution est d'environ 1 heure, 5 types de tours prendraient environ 40 heures, ce qui est trop.

Voici les règles: Il existe 5 types de tours pouvant être placées sur un champ. Il existe plusieurs types de champs, le plus simple étant simplement la matrice 4x4, les autres champs ont des "blancs". où vous ne pouvez pas construire. Votre but est de placer le plus grand nombre possible de tours sur un champ afin de maximiser la valeur totale de la tour sur un champ (supposons que toutes les tours sont construites en même temps, il n’ya pas de virages).

Types de tours (dans l'ordre croissant):

• Bleu - peut être placé n’importe où, valeur = 10
• Rouge - peut être placé uniquement en plus du bleu, valeur = 20
• Vert - placé à côté du rouge et du bleu, valeur = 30
• Jaune - outre le vert, le rouge et le bleu, valeur = 40
• Blanc - à part le jaune, le vert, le rouge et le bleu, valeur = 100

Cela signifie que, par exemple, la tour verte doit avoir au moins une tour rouge et une tour bleue au niveau des cellules voisines nord, sud, ouest ou est (les diagonales ne comptent pas). La tour blanche doit être entourée de toutes les autres couleurs.

Voici mon algorithme pour 4 tours sur un champ 4x4:

1. Nombre total de combinaisons = 4 ^ 16
2. Parcourez [1..4 ^ 16] et convertissez chaque nombre en chaîne base4 afin de coder l’emplacement de la tour, donc 4 ^ 16 = "3333 3333 3333 3333". ce qui représenterait nos types de tour (0 = bleu, ..., 3 = jaune)
3. Convertissez la chaîne de placement de la tour en matrice.
4. Pour chaque tour d'une matrice, vérifiez ses voisins et si l'une des exigences échoue, toute la combinaison échoue.
5. Placez toutes les combinaisons correctes dans un tableau, puis triez ce tableau sous forme de chaînes dans l'ordre lexicographique pour trouver la meilleure combinaison possible (vous devez d'abord trier les caractères dans une chaîne).

La seule optimisation que j'ai proposée consiste à ignorer les combinaisons qui ne contiennent aucune des tours les plus précieuses. Certains traitements sont sautés mais je continue à parcourir les 4 ^ 16 combinaisons.

Avez-vous une idée de la façon dont cela pourrait être amélioré? Des exemples de code seraient utiles en Java ou en PHP.

------- Mettre à jour --------

Après l'ajout de plusieurs états illégaux (le jaune ne peut pas être construit dans les coins, le blanc ne peut pas être construit dans les coins et sur les bords, le champ doit contenir au moins une tour de chaque type), ce qui permet de ne créer qu'une seule tour blanche. sur le terrain 4x4 et en optimisant le code java, le temps total a été ramené de 40 à ~ 16 heures. Peut-être que le filetage le ramènerait à 10 heures, mais c'est probablement la limite du forçage brutal.

Answer 1

J'ai trouvé cette question intrigante et, comme je m'apprends à apprendre Haskell, j'ai décidé d'essayer de mettre en œuvre une solution dans cette langue.

Je pensais aux branches et aux liens, mais je ne pouvais pas trouver un bon moyen de relier les solutions, alors je me suis contenté d'élaguer en éliminant les planches enfreignant les règles.

Mon algorithme fonctionne en commençant par un "vide". planche. Il place chaque couleur possible de la tour dans le premier emplacement vide et dans chaque cas (chaque couleur) s’appelle alors de manière récursive. Les appels récursifs essaient chaque couleur du deuxième emplacement, récursant de nouveau, jusqu'à ce que le tableau soit plein.

Au fur et à mesure que chaque tour est placée, je vérifie la tour qui vient d'être placée et tous ses voisins pour vérifier qu'ils respectent les règles et traitent tous les voisins vides comme des wild cards. Donc, si une tour blanche a quatre voisins vides, je la considère comme valide. Si un placement est invalide, je ne récidis pas sur ce placement, élaguant effectivement tout l’arbre de possibilités qu’il contient.

À la façon dont le code est écrit, je génère une liste de toutes les solutions possibles, puis regarde dans la liste pour trouver la meilleure. En réalité, grâce à l'évaluation paresseuse de Haskell, les éléments de la liste sont générés au fur et à mesure que la fonction de recherche en a besoin, et comme ils ne sont jamais référencés, ils deviennent immédiatement disponibles pour la récupération de place. (2 Mo).

Les performances sont plutôt bonnes. Sur mon ordinateur portable à 2,1 GHz, la version compilée du programme résout le cas du 4x4 en environ 50 secondes, en utilisant un cœur. Je lance actuellement un exemple 5x5 pour voir combien de temps cela prendra. Comme le code fonctionnel est assez facile à mettre en parallèle, je vais également expérimenter le traitement en parallèle. Il existe un compilateur Haskell parallélisé qui non seulement répartira le travail sur plusieurs cœurs, mais également sur plusieurs machines. Il s'agit d'un problème très parallélisable.

Voici mon code jusqu'à présent. Je me rends compte que vous avez spécifié Java ou PHP, et Haskell est très différent. Si vous voulez jouer avec, vous pouvez modifier la définition de la variable " bnd " juste au-dessus du bas pour définir la taille du tableau. Il suffit de le définir sur ((1,1), (x, y)), où x et y représentent respectivement le nombre de colonnes et de lignes.

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

N'oubliez pas non plus qu'il s'agit de mon premier programme Haskell non trivial. Je suis sûr que cela peut être fait beaucoup plus élégamment et succinctement.

Mise à jour : comme il était encore fastidieux de faire un 5x5 avec 5 couleurs (j'ai attendu 12 heures et que je n'avais pas fini), j'ai jeté un nouveau regard sur l'utilisation de la liaison à élaguer davantage de l'arbre de recherche.

Ma première approche consistait à estimer la limite supérieure d’un tableau partiellement rempli en supposant que chaque cellule vide est remplie d’une tour blanche. J'ai ensuite modifié la fonction 'solution' pour suivre le meilleur score et ignorer tout tableau dont la limite supérieure est inférieure à ce meilleur score.

Cela a aidé certains, en réduisant une planche 4x4x5 de 23 à 15. Pour l'améliorer davantage, j'ai modifié la fonction de limite supérieure afin de supposer que chaque vide est rempli avec la meilleure tour possible, compatible avec le contenu des cellules non vides existantes. Cela a beaucoup aidé, en réduisant le temps 4x4x5 à 2 secondes.

L'exécuter sur 5x5x5 a pris 2600, donnant le tableau suivant:

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

avec un score de 730.

Je peux faire une autre modification et lui demander de trouver tous les tableaux affichant le score maximal, plutôt qu'un seul.

Answer 2

Si vous ne souhaitez pas exécuter A *, utilisez une approche branchée et liée . . Le problème devrait être relativement facile à coder, car vos fonctions de valeur sont bien définies. J'imagine que vous devriez être capable d'élaguer d'énormes sections de l'espace de recherche avec une relative facilité. Cependant, étant donné que votre espace de recherche est assez grand, cela peut prendre du temps. Un seul moyen de le savoir:)

L'article du wiki n'est pas le meilleur au monde. Google peut vous trouver une tonne de beaux exemples et d'arbres, entre autres, pour illustrer davantage l'approche.

Answer 3

Un moyen simple d’améliorer la méthode de la force brute est d’explorer uniquement les états juridiques. Par exemple, si vous essayez tous les états possibles, vous testerez de nombreux états dont le coin supérieur droit est une tour blanche. Tous ces états seront illégaux. Cela n'a aucun sens de générer et de tester tous ces états. Vous voulez donc générer vos états un bloc à la fois et ne vous plonger plus profondément dans l’arbre que lorsque vous vous trouvez dans un état potentiellement valide. Cela réduira votre arbre de recherche de plusieurs ordres de grandeur.

Vous pouvez peut-être faire davantage, mais il s’agit d’une amélioration facile à comprendre (espérons-le) par rapport à votre solution actuelle.

Answer 4

Je pense que vous voudrez utiliser un algorithme à branches et liaisons car je pense que trouver une bonne heuristique pour une implémentation de A * sera difficile (mais, ce n'est que mon intuition).

Le pseudo-code pour une implémentation avec branchement et liaison est:

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’idée est que nous cherchons dans l’ordre toutes les planches possibles, mais que nous gardons trace de la meilleure carte que nous avons trouvée jusqu’à présent (c’est la limite). Ensuite, si nous trouvons un tableau partiel dont nous savons qu’il ne sera jamais meilleur que le meilleur jusqu’à présent, nous cesserons de chercher à travailler sur ce tableau: nous coupons cette branche de l’arbre de recherche.

Dans le code ci-dessus, je vérifie si tous les blancs sont remplis par les pièces blanches, car nous ne pouvons pas faire mieux que cela. Je suis sûr qu'avec un peu de réflexion, vous pouvez arriver à une limite plus étroite que celle-là.

Un autre endroit où vous pouvez essayer d’optimiser est l’ordre de la boucle for-each. Vous voulez essayer des pièces dans le bon ordre. Autrement dit, vous voulez que la première solution soit la meilleure, ou au moins une avec un score vraiment élevé.

Answer 5

Il semble qu’une bonne approche consisterait à commencer par une tour blanche, puis à construire un ensemble de tours autour de celle-ci en fonction des besoins, en essayant de trouver le plus petit ensemble coloré possible de formes pouvant servir de dalles imbriquées.

Answer 6

Je voulais défendre la programmation linéaire avec des inconnues entières , mais il s'avère que c'est NP-difficile même dans le cas binaire. Cependant, vous pouvez toujours réussir à optimiser un problème comme le vôtre, qui offre de nombreuses solutions valables et que vous souhaitez tout simplement trouver la meilleure.

La programmation linéaire, pour ce genre de problème, revient essentiellement à avoir beaucoup de variables (par exemple, le nombre de tours rouges présentes dans la cellule (M, N)) et de relations entre les variables (par exemple, le nombre de tours). les tours blanches de la cellule (M, N) doivent être inférieures ou égales au nombre de tours de couleur non blanche dont le nombre est le plus petit parmi tous ses voisins). C'est un peu pénible d'écrire un programme linéaire, mais si vous voulez une solution qui fonctionne en quelques secondes, c'est probablement votre meilleur pari.

Answer 7

Vous avez reçu beaucoup de bons conseils en matière d’algorithmique, donc je n’ai pas grand chose à ajouter. Mais, en supposant que Java soit le langage utilisé, voici quelques suggestions assez évidentes pour améliorer les performances.

• Assurez-vous de ne pas instancier d'objets dans cette boucle 4 ^ 16. C'est beaucoup, beaucoup moins cher pour la JVM de réinitialiser un objet existant que d'en créer un nouveau. Encore moins cher d'utiliser des tableaux de primitives. :)
• Si vous pouvez l’aider, éloignez-vous des classes de la collection. Ils vont ajouter beaucoup de frais généraux dont vous n'avez probablement pas besoin.
• Assurez-vous de ne pas enchaîner de chaînes. Utilisez StringBuilder.
• Et enfin, envisagez de réécrire le tout en C.