Trying to build algorithm for optimal tower placement in a game

This is going to be a long post and just for fun, so if you don't have much time better go help folks with more important questions instead :)

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

Here are the rules: There are 5 types of towers that could be placed on a field. There are several types of fields, the easiest one is just 4x4 matrix, others fields have some "blanks" where you can't build. Your aim is to put as many the most valuable towers on a field as possible to maximize total tower value on a field (lets assume that all towers are built at once, there is no turns).

Tower types (in order from less to most valuable):

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

Which means that for example green tower should have at least 1 red and 1 blue towers at either north, south, west or east neighbor cells (diagonals don't count). White tower should be surrounded with all other colors.

Here is my algorithm for 4 towers on 4x4 field:

1. Total number of combinations = 4^16
2. Loop through [1..4^16] and convert every number to base4 string in order to encode tower placement, so 4^16 = "3333 3333 3333 3333" which would represent our tower types (0=blue,...,3=yellow)
3. Convert tower placement string into matrix.
4. For开发者_如何学Python every tower in a matrix check its neighbors and if any of requirements fails this whole combination fails.
5. Put all correct combinations into an array and then sort this array as strings in lexicographic order to find best possible combination (first need to sort characters in a string).

The only optimization I came up with is to skip combinations that don't contain any most valuable towers. It skips some processing but I still loop through all 4^16 combinations.

Any thought how this can be improved? Code samples would be helpful if in java or php.

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

After adding more illegal states (yellow cannot be built in the corners, white cannot be built in corners and on the edges, field should contain at least one tower of each type), realizing that only 1 white tower could be possibly built on 4x4 field and optimizing java code the total time was brought down from 40 to ~16 hours. Maybe threading would bring it down to 10 hrs but that's probably brute forcing limit.

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

I thought about branch-and-bound, but couldn't come up with a good way to bound the solutions, so I just did some pruning by discarding boards that violate the rules.

My algorithm works by starting with an "empty" board. It places each possible color of tower in the first empty slot and in each case (each color) then recursively calls itself. The recursed calls try each color in the second slot, recursing again, until the board is full.

As each tower is placed, I check the just-placed tower and all of it's neighbors to verify that they're obeying the rules, treating any empty neighbors as wild cards. So if a white tower has four empty neighbors, I consider it valid. If a placement is invalid, I do not recurse on that placement, effectively pruning the entire tree of possibilities under it.

The way the code is written, I generate a list of all possible solutions, then look through the list to find the best one. In actuality, thanks to Haskell's lazy evaluation, the list elements are generated as the search function needs them, and since they're never referred to again they become available for garbage collection right away, so even for a 5x5 board memory usage is fairly small (2 MB).

Performance is pretty good. On my 2.1 GHz laptop, the compiled version of the program solves the 4x4 case in ~50 seconds, using one core. I'm running a 5x5 example right now to see how long it will take. Since functional code is quite easy to parallelize, I'm also going to experiment with parallel processing. There's a parallelized Haskell compiler that will not only spread the work across multiple cores, but across multiple machines as well, and this is a very parallelizable problem.

Here's my code so far. I realize that you specified Java or PHP, and Haskell is quite different. If you want to play with it, you can modify the definition of the variable "bnd" just above the bottom to set the board size. Just set it to ((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 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

Also, please remember this is my first non-trivial Haskell program. I'm sure it can be done much more elegantly and succinctly.

Update: Since it was still very time-consuming to do a 5x5 with 5 colors (I waited 12 hours and it hadn't finished), I took another look at how to use bounding to prune more of the search tree.

My first approach was to estimate the upper bound of a partially-filled board by assuming every empty cell is filled with a white tower. I then modified the 'solution' function to track the best score seen and to ignore any board whose upper bound is less than than that best score.

That helped some, reducing a 4x4x5 board from 23s to 15s. To improve it further, I modified the upper bound function to assume that each Empty is filled with the best tower possible, consistent with the existing non-empty cell contents. That helped a great deal, reducing the 4x4x5 time to 2s.

Running it on 5x5x5 took 2600s, giving the following board:

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

with a score of 730.

I may make another modification and have it find all of the maximal-scoring boards, rather than just one.

If you don't want to do A*, use a branch and bound approach. The problem should be relatively easy to code up because your value functions are well defined. I imagine you should be able to prune off huge sections of the search space with relative ease. However because your search space is pretty large it may still take some time. Only one way to find out :)

The wiki article isn't the best in the world. Google can find you a ton of nice examples and trees and stuff to further illustrate the approach.

One easy way to improve the brute force method is to explore only legal states. For example, if you are trying all possible states, you will be testing many states where the top right corner is a white tower. All of these states will be illegal. It doesn't make sense to generate and test all of those states. So you want to generate your states one block at a time, and only go deeper into the tree when you are actually at a potentially valid state. This will cut down your search tree by many orders of magnitude.

There may be further fancy things you can do, but this is an easy to understand (hopefully) improvement to your current solution.

I think you will want to use a branch-and-bound algorithm because I think coming up with a good heuristic for an A* implementation will be hard (but, that's just my intuitition).

The pseudo-code for a branch-and-bound implementation is:

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 search all possible boards, in order, but we keep track of the best one we have found so far (this is the bound). Then, if we find a partial board which we know will never be better than the best one so far then we stop looking working on that partial board: we trim that branch of the search tree.

In the code above I am doing the check by assuming that all the blanks would be filled by the white pieces, as we can't do better than that. I am sure that with a little bit of thought you can come up with a tighter bound than that.

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

It seems like a good approach would be to start with a white tower and then build a set of towers around it based on the requirements, trying to find the smallest possible colored set of shapes which can act as interlocking tiles.

I wanted to advocate linear programming with integer unknowns, but it turns out that it's NP-hard even in the binary case. However, you can still get great success at optimizing a problem like yours, where there are many valid solutions and you simply want the best one.

Linear programming, for this kind of problem, essentially amounts to having a lot of variables (for example, the number of red towers present in cell (M, N)) and relationships among the variables (for example, the number of white towers in cell (M, N) must be less than or equal to the number of towers of the non-white color that has the smallest such number, among all its neighbors). It's kind of a pain to write up a linear program, but if you want a solution that runs in seconds, it's probably your best bet.

You've received a lot of good advice on the algorithmic side of things, so I don't have a lot to add. But, assuming Java as the language, here are a few fairly obvious suggestions for performance improvement.

• Make sure you're not instantiating any objects inside that 4^16 loop. It's much, much cheaper for the JVM to re-initialize an existing object than to create a new one. Even cheaper to use arrays of primitives. :)
• If you can help it, step away from the collection classes. They'll add a lot of overhead that you probably don't need.
• Make sure you're not concatenating any strings. Use StringBuilder.
• And lastly, consider re-writing the whole thing in C.