ser*_*erg 6 algorithm game-theory
这将是一个很长的帖子,只是为了好玩,所以如果你没有太多时间去帮助人们更重要的问题:)
最近在xbox上发布了一款名为"Tower Bloxx"的游戏.游戏的一部分是以最佳方式在场地上放置不同颜色的塔,以最大化最有价值的塔的数量.我写了一个算法,可以确定最有效的塔位置,但它不是非常有效,而且几乎只是强制所有可能的组合.对于具有4种塔型的4x4油田,它可在约1小时内解决,5种塔型需要约40小时,这太多了.
以下是规则: 有5种类型的塔可以放置在一个场地上.有几种类型的字段,最简单的是4x4矩阵,其他字段有一些"空白",你无法构建.您的目标是尽可能多地在场地上放置最有价值的塔,以最大化场地上的总塔值(假设所有塔都是一次建造的,没有转弯).
塔型(按从少到最有价值的顺序):
这意味着,例如,绿色塔楼应该在北,南,西或东邻居单元中至少有1个红色塔和1个蓝色塔(对角线不计算).白塔应该被所有其他颜色包围.
这是我在4x4场上的4个塔的算法:
我想出的唯一优化是跳过不包含任何最有价值的塔的组合.它跳过一些处理,但我仍然遍历所有4 ^ 16组合.
有人想过如何改进这个？如果在java或php中,代码示例会很有用.
------- --------更新
添加更多非法状态后(黄色不能在角落中建造,白色不能建在角落和边缘,场地应至少包含一个类型的塔),意识到只有1个白色塔可能建在4x4场地上并优化java代码,总时间从40小时降至16小时.也许线程会将其降低到10小时,但这可能是暴力限制.
我发现这个问题很有趣,因为我自己在教Haskell,所以我决定尝试用这种语言实现解决方案.
我想到了分支机构,但是无法想出一个很好的方法来限制解决方案,所以我只是通过丢弃违反规则的板来做一些修剪.
我的算法通过以"空"板开始工作.它将塔的每种可能颜色放置在第一个空槽中,并且在每种情况下(每种颜色)然后递归地调用自身.递归调用尝试第二个插槽中的每种颜色,再次递归,直到电路板已满.
当每个塔被放置时,我检查刚刚放置的塔及其所有邻居,以验证他们是否遵守规则,将任何空的邻居视为外卡.因此,如果白塔有四个空的邻居,我认为它是有效的.如果展示位置无效,我不会对该展示位置进行递归,从而有效地修剪其下的整个可能性树.
编写代码的方式,我生成所有可能解决方案的列表,然后查看列表以找到最佳解决方案.实际上,由于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程序.我相信它可以更加优雅和简洁地完成.
更新:因为用5种颜色做5x5仍然非常耗时(我等了12个小时而且还没完成),我再看看如何使用边界来修剪更多的搜索树.
我的第一种方法是通过假设每个空单元都填充有白色塔来估计部分填充板的上限.然后,我修改了"解决方案"功能,以跟踪所看到的最佳分数,并忽略任何上限小于最佳分数的董事会.
这帮助了一些人,将4x4x5电路板从23s减少到15s.为了进一步改进,我修改了上限函数,假设每个Empty都填充了尽可能最好的塔,与现有的非空单元格内容一致.这有很大帮助,将4x4x5时间减少到2s.
在5x5x5上运行它需要2600s,给出以下板:
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分.
我可以进行另一次修改,让它找到所有最大得分板,而不仅仅是一个.