Der Versuch Algorithmus für die optimale Platzierung Turm in einem Spiel zu bauen
https://stackoverflow.com/questions/1626189
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Das wird eine lange Post sein und nur zum Spaß, wenn Sie also viel Zeit besser nicht Leute gehen helfen mit wichtigeren Fragen statt:)
Es ist ein Spiel namens „Tower Bloxx“ vor kurzem auf der Xbox veröffentlicht. Ein Teil des Spiels ist es verschiedenfarbige Türme auf einem Feld in einer optimalen Art und Weise, um die Anzahl der wertvollsten Türme zu maximieren. Ich schrieb einen Algorithmus, der die effizienteste Turm Platzierung bestimmen würde, aber es ist nicht sehr effizient und ziemlich einfach Brute zwingen, alle möglichen Kombinationen. Für 4x4-Feld mit 4 Turm-Typen es sie in etwa 1 Stunde löst, 5 Turm-Typen würden etwa 40 Stunden, das ist zu viel.
Hier sind die Regeln: Es gibt 5 Arten von Türmen, die auf einem Feld platziert werden können. Es gibt verschiedene Arten von Feldern, die einfachste ist nur 4x4-Matrix, andere Felder haben einige „Rohlinge“, wo man nicht aufbauen können. Ihr Ziel ist es, so viele der wertvollsten Türme auf einem Feld wie möglich zu setzen Gesamt Turm Wert auf ein Feld zu maximieren (können davon ausgehen, dass alle Türme auf einmal gebaut werden, gibt es keine Umdrehungen).
Turmtypen (in der Reihenfolge von weniger wertvollsten):
- Blue - kann überall, Wert = 10 gesetzt werden
- Red - kann nur neben blau, Wert gelegt wird = 20
- Green - platziert neben Rot und Blau, Wert = 30
- Gelb - neben grün, rot und blau, Wert = 40
- White - neben gelb, grün, rot und blau, Wert = 100
Das bedeutet, dass zum Beispiel grüner Turm mindestens 1 roten und 1 blaue Türme entweder nach Norden, Süden, Westen oder Osten Nachbarzellen (Diagonalen zählen nicht) haben sollte. Weißer Turm sollte mit allen anderen Farben umgeben sein.
Hier ist mein Algorithmus für 4 Türme auf 4x4 Feld:
- Gesamtzahl der Kombinationen = 4 ^ 16
- Schleife durch [1..4 ^ 16] und konvertieren jede Zahl zu base4 Zeichenfolge um Turm Platzierung zu kodieren, so 4 ^ 16 = "3333 3333 3333 3333", die unsere Turmtypen darstellen würden (0 = blau ,. .., 3 = gelb)
- Konvertieren Turm Platzierung String in Matrix.
- Für jeden Turm in einer Matrix seine Nachbarn überprüfen und, wenn eine der Anforderungen nicht diese ganze Kombination ausfällt.
- Legen Sie alle richtigen Kombinationen in ein Array und dann dieses Array als Strings in lexikographische Reihenfolge sortieren bestmögliche Kombination zu finden (zuerst müssen Zeichen sortieren in einem String).
Die einzige Optimierung kam ich mit ist Kombinationen zu überspringen, die keine wertvollsten Türme nicht enthalten. Es überspringt einige Verarbeitung, aber ich immer noch eine Schleife durch alle 4 ^ 16 Kombinationen.
Jeder dachte, wie diese verbessert werden kann? Codebeispiele würden, wenn in Java oder PHP hilfreich sein.
------- -------- aktualisieren
Nach der Zugabe von mehr illegalen Staaten (gelb nicht in den Ecken gebaut werden kann, weiß nicht in Ecken und an den Rand gebaut werden, Feld sollte mindestens einen Turm jeden Typen enthält), dass nur 1 weißen Turm realisiert möglicherweise gebaut werden konnte auf 4x4 Feld und Optimierung von Java-Code wurde die Gesamtzeit von 40 bis ~ 16 Stunden gebracht. Einfädeln wäre es vielleicht zu 10 Stunden zu bringen, aber das wahrscheinlich ist Brute Grenze zu erzwingen.
Lösung
Ich fand diese Frage interessant, und da ich mich Haskell bin unterrichtet, habe ich beschlossen, meine Hand, um zu versuchen, eine Lösung in dieser Sprache zu implementieren.
Ich dachte über Branch-and-gebunden, konnte aber nicht mit einem guten Weg, um die Lösungen gebunden, so habe ich nur einige Beschneidung durch Bretter zu verwerfen, die die Regeln verletzen.
Mein Algorithmus funktioniert, indem sie mit einem „leeren“ Board zu starten. Sie stellt jede mögliche Farbe der Turm in der ersten leeren Schlitz und in jedem Fall (jede Farbe), dann ruft sich selbst rekursiv. Die rekursiv Anrufe versuchen, jede Farbe in dem zweiten Schlitz, Rekursion wieder, bis das Brett voll ist.
Wie jeder Turm platziert ist, überprüfe ich den gerade platzierte Turm und all seine Nachbarn zu überprüfen, ob sie die Regeln sind zu gehorchen, alle leeren Nachbarn als Wildcards zu behandeln. Also, wenn ein weißer Turm vier leere Nachbarn hat, halte ich es für gültig. Wenn eine Platzierung ungültig ist, verhindere die rekursive ich nicht auf dieser Platzierung, effektiv den gesamten Baum der Möglichkeiten unter ihm abgeschnitten wird.
Die Art und Weise der Code geschrieben ist, habe ich eine Liste aller möglichen Lösungen zu generieren, dann schauen Sie durch die Liste der am besten zu finden. In Wirklichkeit dank Haskells faul Auswertung werden die Listenelemente erzeugen, wie die Suchfunktion sie braucht, und da sie bezeichnete nie wieder sie für die Garbage Collection verfügbar ist sofort, so dass selbst für eine 5x5 Board Speichernutzung ist ziemlich klein (2 MB).
Die Leistung ist ziemlich gut. Auf meinem 2,1 GHz Laptop löst die kompilierte Version des Programms den 4x4 Fall in ~ 50 Sekunden einen Kern verwendet. Ich laufe jetzt ein 5x5 Beispiel zu sehen, wie lange es dauern wird. Da der Funktionscode ganz einfach parallelisieren ist, werde ich auch mit Parallelverarbeitung experimentieren. Es gibt eine parallelisierte Haskell Compiler, der die Arbeit auf mehrere Kerne nicht nur verteilt, sondern auf mehreren Rechnern als auch, und dies ist ein sehr parallelizable Problem.
Hier ist mein Code so weit. Ich weiß, dass Sie angegeben Java oder PHP, und Haskell ist ganz anders. Wenn Sie mit ihm spielen wollen, können Sie die Definition der Variablen „bnd“ ändern knapp über dem Boden, um die Größe der Leiterplatte zu setzen. Einfach einstellen zu ((1,1), (x, y)), wobei x und y die Anzahl der Spalten und Zeilen ist.
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
Auch denken Sie bitte daran dies mein erstes nicht-triviales Programm Haskell ist. Ich bin sicher, es kann viel mehr elegant und prägnant durchgeführt werden.
Aktualisieren : Da es noch sehr zeitaufwendig war ein 5x5 mit 5 Farben zu tun (I 12 Stunden gewartet und es hatte nicht beendet), nahm ich noch einen Blick auf, wie man verwenden begrenzt stutzt mehr des Suchbaumes.
Mein erster Ansatz war die Obergrenze eines teilweise gefülltes Bord zu schätzen, indem jede leere Zelle unter der Annahme ist mit einem weißen Turm gefüllt. Ich änderte dann die ‚Lösung‘ Funktion das beste Ergebnis gesehen zu verfolgen und jedes Board, deren obere Grenze zu ignorieren weniger als als das beste Ergebnis.
Das half einige, ein 4x4x5 Board von 23s bis 15s reduzieren. Zur Verbesserung weiter, modifizierte ich die obere Schranke Funktion anzunehmen, dass jeder Leer den besten Turm möglich, im Einklang mit der bestehenden nicht-leeren Zelle Inhalt gefüllt ist. Das half sehr viel, die 4x4x5 Zeit 2s verringert wird.
Beim Laufen auf 5x5x5 2600S nahm, das folgende Bord geben:
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
mit einer Punktzahl von 730.
Ich kann eine weitere Modifikation machen und sie haben alle die Maximalpunktetafeln, und nicht nur finden.
Andere Tipps
Wenn Sie nicht A * zu tun, verwenden Sie einen Branch and Bound Ansatz . Das Problem sollte relativ einfach zu codieren, weil Ihre Wertfunktionen sind klar definiert. Ich denke, Sie sollten mit relativer Leichtigkeit beschneiden aus großen Abschnitten des Suchraums können. Doch weil Ihr Suchraum ziemlich groß ist, kann es noch einige Zeit dauern. Nur ein Weg, um herauszufinden:)
Der Wiki-Artikel ist nicht die beste in der Welt. Google kann Ihnen eine Menge schöne Beispiele und Bäume und so weiter zu veranschaulichen den Ansatz finden.
Eine einfache Möglichkeit, die Brute-Force-Methode zu verbessern, ist nur Rechtsstaaten zu erkunden. wenn Sie alle möglichen Zustände zum Beispiel versuchen, werden Sie viele Staaten testen, wo die obere rechte Ecke ein weißer Turm. Alle diese Staaten werden illegal sein. Es macht keinen Sinn, zu erzeugen und alle diese Zustände zu testen. So möchten Sie Ihre Staaten einen Block zu einem Zeitpunkt, zu erzeugen, und geht nur tiefer in den Baum, wenn Sie tatsächlich an einem potentiell gültigen Zustand sind. Dies wird abgeholzt Ihren Suchbaum durch viele Größenordnung.
Es kann weiter Phantasie Dinge, die Sie tun können, aber das ist eine leicht zu verstehen (hoffentlich) Verbesserung Ihrer aktuelle Lösung.
Ich denke, dass Sie einen Zweig-and-Bound-Algorithmus verwendet werden sollen, weil ich mit einer guten Heuristik für ein A * Implementierung wird schwer sein, kommen denken (aber das ist nur meine intuitition).
Der Pseudo-Code für eine Zweig-and-Bound-Implementierung ist:
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)
Die Idee ist, dass wir alle möglichen Bretter, um suchen, aber wir verfolgen die besten, die wir bisher gefunden haben (dies ist die Grenze). Wenn wir dann eine Teilpension finden, die wir nie wissen, besser sein wird als die beste bisher, dann stoppen wir suchen auf diesem Teil Bord arbeiten. Wir diesen Zweig des Suchbaums trimmen
In dem obigen Code ich den Scheck tue, indem angenommen wird, dass alle Rohlinge von den weißen Steinen gefüllt werden würden, da wir nicht besser als das tun. Ich bin sicher, dass mit einem wenig Gedanken Sie mit einer festeren Bindung als die oben kommen können.
Ein weiterer Ort, an dem Sie versuchen können, ist die für-jede Schleife in der Reihenfolge zu optimieren. Sie wollen Stücke in der Reihenfolge richtigen Reihenfolge versuchen. Das heißt, Sie optimal die erste Lösung wollen, dass die besten oder zumindest eine mit einem sehr hohen Punktzahl gefunden werden.
Es scheint wie ein guter Ansatz mit einem weißen Turm beginnen würde und dann eine Reihe von Türmen um sie bauen auf den Anforderungen basiert, versuchen, eine möglichst kleine farbige Reihe von Formen zu finden, die als Falzziegel wirken kann.
Ich wollte lineare Programmierung befürworten mit ganzzahligen Unbekannten , aber es stellt sich heraus, dass es ist NP-schwer, auch im binären Fall. Sie können jedoch nach wie vor großen Erfolg bekommen ein Problem wie das Ihre zu optimieren, wo es viele gültigen Lösungen und Sie wollen einfach das Beste.
Die lineare Programmierung, für diese Art von Problem, beträgt im Wesentlichen eine Menge von Variablen (zum Beispiel der Anzahl der roten Türme in Zelle (M, N)) und die Beziehungen zwischen den Variablen (zum Beispiel der Anzahl des weißen Türme in der Zelle (M, N) muss kleiner als oder gleich die Anzahl der Türme der nicht-weißen Farbe, die die kleinste solche Zahl hat unter allen seinen Nachbarn). Es ist eine Art Schmerz ein lineares Programm zu schreiben, aber wenn Sie eine Lösung wollen, die in Sekunden laufen, ist es wahrscheinlich die beste Wahl.
Sie haben viele gute Beratung über die algorithmische Seite der Dinge erhalten haben, so habe ich nicht viel hinzuzufügen. Aber unter der Annahme, Java als Sprache, hier sind ein paar ziemlich offensichtlich Vorschläge zur Leistungsverbesserung.
- Stellen Sie sicher, dass Sie keine Objekte in dieser 4 ^ 16 Schleife instanziieren. Es ist viel, viel billiger für die JVM ein vorhandenes Objekt neu zu initialisieren, als einen neuen zu erstellen. Noch billiger Arrays von Primitiven zu verwenden. :)
- Wenn Sie ihm helfen können, aus den Sammelklassen Schritt weg. Sie werden eine Menge Aufwand hinzufügen, die Sie wahrscheinlich nicht brauchen.
- Stellen Sie sicher, dass Sie keine Strings verketten. Verwenden Stringbuilder.
- Und schließlich betrachtet die ganze Sache in C neu zu schreiben
