ゲームでの最適なタワー配置のためのアルゴリズムを構築しようとしています
https://stackoverflow.com/questions/1626189
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
これは長い投稿であり、ただの楽しみのためです。時間がない場合は、より重要な質問をする人々を助けてください：）
「Tower Bloxx」というゲームがあります。最近xboxでリリースされました。ゲームの一部は、さまざまな色の塔を最も最適な方法でフィールドに配置して、最も価値のある塔の数を最大化することです。最も効率的なタワーの配置を決定するアルゴリズムを作成しましたが、あまり効率的ではなく、可能なすべての組み合わせをブルートフォースするだけです。 4タワータイプの4x4フィールドの場合、約1時間で解決しますが、5タワータイプでは約40時間かかります。これは多すぎます。
ルールは次のとおりです： フィールドに配置できる5種類のタワーがあります。フィールドにはいくつかのタイプがありますが、最も簡単なものは4x4マトリックスだけです。他のフィールドにはいくつかの「空白」があります。構築できない場所。フィールドで最も価値のあるタワーをできるだけ多く配置して、フィールドの総タワー値を最大化することを目的としています（すべてのタワーが一度に構築され、ターンがないと仮定します）。
タワーの種類（価値の低いものから順に）：
- 青-どこにでも配置可能、値= 10
- 赤-青以外にのみ配置可能、値= 20
- 緑-赤と青以外に配置、値= 30
- 黄色-緑、赤、青のほか、値= 40
- 白-黄色、緑、赤、青のほか、値= 100
これは、たとえば、緑の塔に、北、南、西、または東の隣接セルに少なくとも1つの赤と1つの青の塔があることを意味します（対角線はカウントされません）。白い塔を他のすべての色で囲む必要があります。
4x4フィールドの4つの塔のアルゴリズムは次のとおりです。
- 組み合わせの総数= 4 ^ 16
- [1..4 ^ 16]をループし、すべての数値をbase4文字列に変換してタワーの配置をエンコードします。したがって、4 ^ 16 = "3333 3333 3333 3333"これはタワーのタイプを表します（0 = blue、...、3 = yellow）
- タワーの配置文字列をマトリックスに変換します。
- マトリックス内のすべてのタワーについて、その近隣をチェックし、要件のいずれかが失敗すると、この組み合わせ全体が失敗します。
- すべての正しい組み合わせを配列に入れてから、この配列を辞書式順序で文字列として並べ替えて、可能な限り最良の組み合わせを見つけます（最初に文字列内の文字を並べ替える必要があります）。
私が思いついた唯一の最適化は、最も価値のある塔を含まない組み合わせをスキップすることです。一部の処理はスキップされますが、4 ^ 16のすべての組み合わせをループします。
これをどのように改善できると考えましたか？コードサンプルは、javaまたはphpの場合に役立ちます。
-------更新--------
違法な状態を追加した後（黄色はコーナーに構築できず、白色はコーナーとエッジに構築できません、フィールドには少なくとも各タイプのタワーを1つ含める必要があります）、1つの白いタワーしか構築できない可能性があることに気付きます4x4フィールドおよびJavaコードの最適化では、合計時間が40時間から約16時間に短縮されました。スレッド化により10時間に短縮される可能性がありますが、それはおそらくブルートフォーシング制限です。
解決
この質問に興味をそそられました。Haskellを独学しているので、その言語でソリューションを実装することに挑戦しました。
ブランチアンドバウンドについて考えましたが、ソリューションをバインドする良い方法を思い付くことができなかったので、ルールに違反しているボードを破棄することでいくつかの整理を行いました。
「空」で開始することでアルゴリズムが機能します;ボード。タワーの可能な各色を最初の空のスロットに配置し、それぞれの場合（各色）に再帰的に呼び出します。再帰呼び出しは、ボードがいっぱいになるまで、2番目のスロットで各色を試し、再び再帰します。
各タワーが配置されると、配置されたばかりのタワーとそのすべての隣人をチェックして、ルールに従っていることを確認し、空の隣人をワイルドカードとして扱います。したがって、白い塔に4つの空の隣人がいる場合、それは有効であると考えます。プレースメントが無効な場合、そのプレースメントを再帰せず、その下にある可能性のツリー全体を効果的に枝刈りします。
コードの記述方法として、考えられるすべてのソリューションのリストを生成し、リストを調べて最適なソリューションを見つけます。実際には、Haskellの遅延評価のおかげで、リスト要素は検索関数が必要とするときに生成され、再び参照されることはないので、すぐにガベージコレクションに使用できるようになるため、5x5ボードのメモリ使用量もかなり少なくなります（2 MB）。
パフォーマンスはかなり良いです。私の2.1 GHzラップトップでは、プログラムのコンパイルされたバージョンが1つのコアを使用して、最大50秒で4x4のケースを解決します。今、5x5のサンプルを実行して、どれくらい時間がかかるかを確認しています。関数型コードは非常に簡単に並列化できるため、並列処理の実験も行います。並列化されたHaskellコンパイラがあり、複数のコアにまたがるだけでなく、複数のマシンにも作業を分散します。これは非常に並列化可能な問題です。
ここまでは私のコードです。 JavaまたはPHPを指定したことと、Haskellがまったく異なることを認識しています。試してみたい場合は、変数＆quot; bnd＆quot;の定義を変更できます。ボードサイズを設定するために底部のすぐ上に。 （（1,1）、（x、y））に設定するだけです。xとyはそれぞれ列と行の数です。
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
また、これが私の最初の重要なHaskellプログラムであることを忘れないでください。もっとエレガントで簡潔にできると確信しています。
更新：5色で5x5を行うにはまだ非常に時間がかかりました（12時間待って終了していませんでした）。検索ツリーをさらに整理します。
最初のアプローチは、空のセルがすべて白い塔で満たされていると仮定して、部分的に満たされたボードの上限を推定することでした。次に、「ソリューション」関数を変更して、表示された最高スコアを追跡し、上限が最高スコアよりも小さいボードを無視しました。
これにより、4x4x5のボードが23秒から15秒に短縮されました。それをさらに改善するために、上限関数を変更して、既存の空でないセルの内容と一致して、各空が可能な限り最高のタワーで満たされると仮定しました。これは非常に役立ち、4x4x5の時間を2秒に短縮しました。
5x5x5で実行するには2600秒かかり、次のボードが提供されました：
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
スコア730。
別の修正を加えて、1つだけではなく、すべての最大得点ボードを見つけさせることができます。
他のヒント
A *を行いたくない場合は、ブランチとバインドアプローチを使用します。値関数は明確に定義されているため、問題のコーディングは比較的簡単です。サーチスペースの大きなセクションを比較的簡単に削除できるはずです。ただし、検索スペースは非常に大きいため、まだ時間がかかる場合があります。見つける唯一の方法：）
wikiの記事は世界最高ではありません。 Googleは、このアプローチをさらに説明するために、たくさんの素敵な例や木などを見つけることができます。
ブルートフォース法を改善する簡単な方法の1つは、法的状態のみを調べることです。たとえば、可能なすべての状態を試している場合、右上隅が白い塔である多くの状態をテストします。これらの州はすべて違法です。これらの状態をすべて生成してテストすることは意味がありません。そのため、一度に1ブロックずつ状態を生成し、実際に潜在的に有効な状態にあるときにのみツリーの奥深くに移動します。これにより、検索ツリーが大幅に削減されます。
さらに高度なことができるかもしれませんが、これは現在のソリューションを理解するのに（できれば）簡単に理解できるものです。
A *実装の優れたヒューリスティックを思い付くのは難しいと思うので、分岐限定アルゴリズムを使用したいと思うでしょう（しかし、それは私の直観です）。
分岐限定実装の擬似コードは次のとおりです。
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)
考えは、すべての可能なボードを順番に検索することですが、これまでに見つかった最高のボードを追跡します（これが限界です）。次に、これまでで最高のものよりも決して良くならないことがわかっている部分的なボードが見つかった場合、その部分的なボードでの作業を停止します。検索ツリーのブランチをトリミングします。
上記のコードでは、すべての空白が白い部分で埋められると想定してチェックを行っていますが、それ以上のことはできません。少し考えてみれば、それよりもさらにきつくなると思います。
最適化を試みることができる別の場所は、for-eachループの順序です。正しい順序でピースを試してみたいと思います。つまり、最適なのは、最初に見つかった解決策が最良のもの、または少なくとも高得点の解決策であることです。
白い塔から始めて、要件に基づいてその周りに塔のセットを構築し、連動するタイルとして機能することができる最小の色付きの形状のセットを見つけようとするのが良い方法のようです。
整数不明の線形プログラミングを提唱したかったのですが、バイナリの場合でもNPハードです。ただし、多くの有効な解決策があり、単に最良の解決策が必要な場合など、自分のような問題の最適化に大きな成功を収めることができます。
この種の問題に対する線形プログラミングは、本質的に、多くの変数（たとえば、セル（M、N）に存在する赤い塔の数）と変数間の関係（たとえば、セル内の白い塔（M、N）は、すべての隣人の中で、そのような数が最も少ない非白色の塔の数以下でなければなりません。線形プログラムを作成するのは一種の苦痛ですが、数秒で実行されるソリューションが必要な場合は、おそらく最善の方法です。
あなたは物事のアルゴリズム面について多くの良いアドバイスを受けているので、追加することはあまりありません。しかし、Javaを言語と仮定して、パフォーマンスを改善するためのいくつかのかなり明白な提案を以下に示します。
- 4 ^ 16ループ内でオブジェクトをインスタンス化していないことを確認してください。 JVMが新しいオブジェクトを作成するよりも既存のオブジェクトを再初期化する方がはるかに安価です。プリミティブの配列を使用するとさらに安価です。 ：）
- 支援できる場合は、コレクションクラスから離れてください。おそらく不要な多くのオーバーヘッドが追加されます。
- 文字列を連結していないことを確認してください。 StringBuilderを使用します。
- 最後に、Cですべてを書き直すことを検討してください。
