Trying to build an algorithm for optimal placement of the tower in the game

Question

It will be a long post and just for fun, so if you do not have much time, it’s better to help people with more important questions :)

Recently released a game called "Tower Bloxx", released on the xbox. One part of the game is to place different colored towers on the field in the most optimal way to maximize the number of the most valuable towers. I wrote an algorithm that would determine the most efficient placement of the tower, but it is not very efficient and pretty much just roughly forces all possible combinations. For a 4x4 field with 4 types of towers, he solves it in about 1 hour, 5 types of towers take about 40 hours, which is too much.

Here are the rules: There are 5 types of towers that can be placed on the field. There are several types of fields, the simplest is just a 4x4 matrix, other fields have some “spaces” in which you cannot build. Your goal is to put as many of the most valuable towers on the field as possible in order to maximize the total cost of the tower on the field (let's assume that all towers are built at once, there are no turns).

Tower types (in order of less significant):

• Blue - can be placed anywhere, value = 10
• Red - only blue can be set, value = 20
• Green - except for red and blue, value = 30
• Yellow - except for green, red and blue, value = 40
• White - except yellow, green, red and blue, value = 100

This means that, for example, the green tower must have at least 1 red and 1 blue tower in the northern, southern, western or eastern neighboring cells (diagonals are not taken into account). The white tower should be surrounded by all other colors.

Here is my algorithm for 4 towers in a 4x4 field:

• Total number of combinations = 4 ^ 16
• Scroll through [1..4 ^ 16] and convert each number to base4 to encode the location of the tower, so 4 ^ 16 = "3333 3333 3333 3333", which will represent our tower types (0 = blue ..., 3 = yellow)
• Convert a column layout row to a matrix.
• For each tower in the matrix, check its neighbors, and if any of the requirements is not met, all this combination fails.
• Put all the correct combinations in an array, and then sort this array as strings in lexicographical order to find the best possible combination (first you need to sort the characters in the string).

The only optimization I've come across is to skip combinations that don't contain any of the most valuable towers. It skips some processing, but I'm still looking through all 4 ^ 16 combinations.

Any thought on how this could be improved? Code examples would be helpful if in java or php.

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

After adding more illegal states (yellow cannot be built in corners, white cannot be built in corners and edges, the field must contain at least one tower of each type), realizing that it is possible to build only 1 white tower in a 4x4 field and Java code optimization, the total time was reduced from 40 to ~ 16 hours. Maybe streaming will reduce it to 10 hours, but maybe it will be a rough enforcement limit.

Answer 1

I found this question intriguing, and since I teach myself Haskell, I decided to try my hand at implementing a solution in this language.

I was thinking about branching and snapping, but could not find a suitable way to bind solutions, so I just did the pruning, discarding boards that break the rules.

My algorithm works starting with an empty board. It puts every possible color of the tower in the first empty slot and in each case (each color), and then recursively calls itself. Recursive calls try each color in the second slot, again recursive, until the board is full.

As soon as each tower is located, I check the located tower and all its neighbors to make sure that they obey the rules, treating any empty neighbors as wild cards. Therefore, if the white tower has four empty neighbors, I consider this to be valid. If the placement is not valid, I am not recursing at that placement, effectively trimming the entire opportunity tree below it.

As the code is written, I generate a list of all possible solutions, and then look through the list to find the best one. In fact, thanks to Haskell's lazy evaluation, list items are generated as the search function needs them, and since they are never mentioned again, they immediately become available for garbage collection, so even using 5x5 memory is pretty small ( 2 MB).

Performance is pretty good. On my 2.1 GHz laptop, the compiled version of the program solves the 4x4 problem in ~ 50 seconds using a single core. I am now using the 5x5 example to find out how long it will take. Since functional code is fairly easy to parallelize, I will also experiment with parallel processing. There is a parallel Haskell compiler that not only extends the work to several cores, but also to several machines, and this is a very parallelizable problem.

Here is my code so far. I understand that you specified Java or PHP, and Haskell is completely different. If you want to play with it, you can change the definition of the variable "bnd" just above the bottom to set the size of the board. Just set it ((1,1), (x, y)), where x and y are the number of columns and rows, respectively.

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 blt ]) | 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 blt ]) 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 

Also, remember that this is my first Haskell non-trivial program. I am sure that this can be done much more elegantly and concisely.

Update . Since there was still a lot of time to make 5x5 with 5 colors (I waited 12 hours and it was not over yet), I looked again at how to use the restriction to trim more search trees.

My first approach was to evaluate the upper border of a partially filled board, assuming that each empty cell is filled with a white tower. Then I modified the solution function to track the best result and ignore any board whose upper bound is less than the best result.

This helped some by reducing the 4x4x5 board from 23 to 15 seconds. To improve it, I changed the function of the upper bound to assume that each Void is filled with the best possible tower in accordance with the existing non-empty contents of the cell. This helped a lot, reducing the 4x4x5 time to 2 seconds.

Running on 5x5x5 took 2600 seconds, providing the following board:

 GBGRB RBWYG YGRBR BWYGY GRBRB 

with a score of 730.

I can make one more modification and find all the boards with the maximum score, and not just one.

Answer 2

If you do not want to do A *, use a branch and anchor . The problem should be relatively easy to code because your value functions are well defined. I suggest that you should easily crop huge sections of the search space. However, since your search space is quite large, this may take some time. Only one way to find out :)

The wiki article is not the best in the world. Google can find you a ton of good examples and trees and more to illustrate this approach again.

Answer 3

One simple way to improve brute force is to study only legal conditions. For example, if you try to use all possible states, you will test many states where the upper right corner is the white tower. All of these states will be illegal. It makes no sense to generate and test all these states. Thus, you want to generate your states one block at a time and only go deep into the tree when you are really in a potentially valid state. This will shorten your search tree by many orders of magnitude.

There may be additional bizarre things you can do, but it's easy to see (hopefully) improving your current solution.

Answer 4

I think you will want to use an algorithm with branches and borders, because I think that coming up with a good heuristic for implementing A * will be difficult (but this is just my intuition).

Pseudocode for implementation with branch and border:

 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) 

The idea is that we look for all possible boards in order, but we keep track of the best that we have found so far (this is an estimate). Then, if we find that a partial board, which, as we know, will never be better than the best, until we stop working on this partial board: we trim this branch of the search tree.

In the code above, I am doing a check, assuming that all the spaces are filled with white shapes, since we cannot do better. I am sure that with a few thoughts you can come up with a tougher attachment.

Another place where you can try to optimize is the order of each cycle. You want to try the pieces in order. That is, optimally, you want the first solution found to be the best, or at least with a very high score.

Answer 5

It seems like a good approach would be to start with a white tower and then build around it many requirements-based towers, trying to find the smallest possible color set of shapes that can act as blocking tiles.

Answer 6

I wanted to defend linear programming with integers unknown , but it turns out that it is NP-hard even in the binary case. However, you can still make great strides in optimizing a problem like yours, where there are many valid solutions, and you just want the best.

Linear programming for this task basically boils down to the presence of a large number of variables (for example, the number of red towers present in the cell (M, N)) and the relationship between the variables (for example, the number of white towers in the cell (M, N) should be less or equal to the number of towers of non-white color with the smallest such number among all its neighbors). It's a pain to write a linear program, but if you want a solution that works in seconds, this is probably the best choice.

Answer 7

You got a lot of good advice on the algorithmic side of things, so I have nothing to add. But assuming Java as a language, here are some pretty obvious suggestions for improving performance.

• Make sure you are not creating objects inside this 4 ^ 16 loop. For the JVM, it is much cheaper to re-initialize an existing object than to create a new one. It's even cheaper to use arrays of primitives. :)
• If you can help, open collection classes. They will add a lot of overhead that you probably don't need.
• Make sure you do not concatenate strings. Use StringBuilder.
• And finally, consider rewriting all this in C.