algorithm - 尝试构建算法以在游戏中放置最佳塔

Question

这将是一篇很长的文章，只是为了好玩，所以如果你没有太多时间最好去帮助人们解决更重要的问题:)

xbox 上最近发布了一款名为“Tower Bloxx”的游戏。游戏的一部分是以最佳方式在 field 上放置不同颜色的塔，以最大限度地增加最有值(value)的塔的数量。我写了一个算法来确定最有效的塔放置，但它不是很有效，而且几乎只是强制所有可能的组合。对于具有 4 种塔类型的 4x4 field ，它在大约 1 小时内解决它，5 种塔类型将花费大约 40 小时，这太多了。

规则如下:有 5 种类型的塔可以放置在 field 上。有几种类型的字段，最简单的就是 4x4 矩阵，其他字段有一些您无法构建的“空白”。您的目标是在一 block field 上放置尽可能多的最有值(value)的塔，以最大化一 block field 上的总塔值(value)(假设所有塔都是一次 build 的，没有轮流)。

塔类型(按值(value)从低到高的顺序):

• 蓝色 - 可以放在任何地方，值 = 10
• 红色 - 只能放在蓝色旁边，值 = 20
• 绿色 - 放在红色和蓝色旁边，值 = 30
• 黄色 - 除了绿色、红色和蓝色，值 = 40
• 白色 - 除了黄色、绿色、红色和蓝色，值 = 100

这意味着例如绿塔在北、南、西或东相邻单元格中应至少有 1 个红色和 1 个蓝色塔(对角线不算)。白色塔应该被所有其他颜色包围。

这是我在 4x4 field 上的 4 座塔的算法:

1. 组合总数 = 4^16
2. 遍历 [1..4^16] 并将每个数字转换为 base4 字符串以对塔的位置进行编码，因此 4^16 = "3333 3333 3333 3333"将代表我们的塔类型(0=蓝色，. ..,3=黄色)
3. 将塔放置字符串转换为矩阵。
4. 对于矩阵中的每个塔检查其邻居，如果任何要求不合格，则整个组合将失败。
5. 将所有正确的组合放入一个数组中，然后将这个数组作为字符串按字典顺序排序，以找到可能的最佳组合(首先需要对字符串中的字符进行排序)。

我想出的唯一优化是跳过不包含任何最有值(value)的塔的组合。它跳过了一些处理，但我仍然遍历所有 4^16 组合。

想过如何改进吗？如果使用 java 或 php，代码示例会很有帮助。

--------更新--------

添加更多非法状态后(黄色不能建在角落里，白色不能建在角落和边缘上， field 应该至少包含每种类型的塔)，意识到只能 build 1 座白色塔在 4x4 领域和优化 java 代码上，总时间从 40 小时减少到 ~16 小时。也许线程会将其缩短到 10 小时，但这可能是暴力破解的极限。

Answer 1

我发现这个问题很有趣，而且由于我正在自学 Haskell，所以我决定尝试用该语言实现解决方案。

我想过分支定界，但想不出一个好的方法来绑定(bind)解决方案，所以我只是通过丢弃违反规则的板来进行一些修剪。

我的算法从一个“空”板开始工作。它将每种可能的塔颜色放在第一个空槽中，然后在每种情况下(每种颜色)递归调用自身。递归调用尝试第二个槽中的每种颜色，再次递归，直到棋盘已满。

在放置每个塔时，我会检查刚刚放置的塔及其所有相邻塔，以验证它们是否遵守规则，将任何空的相邻塔视为通配符。所以如果一个白塔有四个空的邻居，我认为它是有效的。如果某个位置无效，我不会对该位置进行递归，有效地修剪其下的整个可能性树。

按照代码的编写方式，我会生成一个包含所有可能解决方案的列表，然后查看该列表以找到最佳解决方案。实际上，由于 Haskell 的惰性计算，列表元素是在搜索功能需要它们时生成的，并且由于它们再也不会被引用，它们可以立即用于垃圾回收，所以即使是 5x5 的板，内存使用量也相当小(2 MB)。

性能还不错。在我的 2.1 GHz 笔记本电脑上，程序的编译版本使用一个内核在大约 50 秒内解决了 4x4 的情况。我现在正在运行一个 5x5 示例，看看需要多长时间。由于函数式代码很容易并行化，我也将尝试并行处理。有一个并行化的 Haskell 编译器，它不仅可以将工作分散到多个内核上，还可以分散到多台机器上，这是一个非常可并行化的问题。

到目前为止，这是我的代码。我意识到您指定了 Java 或 PHP，而 Haskell 则完全不同。如果你想玩它，你可以修改底部上方变量“bnd”的定义来设置棋盘大小。只需将其设置为 ((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 程序。我相信它可以做得更优雅、更简洁。

更新:由于做一个5x5的5色还是很费时间的(我等了12个小时还没做完)，我又看了看如何使用bounding to修剪更多的搜索树。

我的第一种方法是通过假设每个空单元格都填充有白色塔来估计部分填充板的上限。然后我修改了“解决方案”函数以跟踪看到的最佳分数并忽略任何上限小于该最佳分数的棋盘。

这对一些人有所帮助，将 4x4x5 板从 23 秒减少到 15 秒。为了进一步改进它，我修改了上限函数以假设每个 Empty 都填充了可能的最佳塔，与现有的非空单元格内容一致。这有很大帮助，将 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。

我可能会进行另一次修改，让它找到所有的最高得分板，而不仅仅是一个。