Пытаюсь построить алгоритм оптимального размещения башни в игре.

StackOverflow https://stackoverflow.com/questions/1626189

  •  06-07-2019
  •  | 
  •  

Вопрос

Это будет длинный пост и просто для развлечения, поэтому, если у вас мало времени, лучше помогите людям с более важными вопросами :)

Недавно на Xbox вышла игра под названием Tower Bloxx.Одна часть игры состоит в том, чтобы расположить башни разного цвета на поле наиболее оптимальным образом, чтобы максимизировать количество наиболее ценных башен.Я написал алгоритм, который определяет наиболее эффективное размещение башни, но он не очень эффективен и по сути просто перебор всех возможных комбинаций.Для поля 4х4 с 4 типами башен задача решается примерно за 1 час, 5 типов башен займут около 40 часов, что слишком много.

Вот правила:На поле можно разместить 5 типов башен.Есть несколько типов полей, самое простое — это просто матрица 4х4, в других полях есть «пустышки», куда нельзя строить.Ваша цель — разместить на поле как можно больше самых ценных башен, чтобы максимизировать общую ценность башен на поле (предположим, что все башни построены одновременно, ходов нет).

Типы башен (в порядке от менее к наиболее ценному):

  • Синий — можно разместить где угодно, значение = 10.
  • Красный - можно размещать только помимо синего, значение = 20
  • Зеленый – размещается рядом с красным и синим, значение = 30.
  • Желтый — помимо зеленого, красного и синего, значение = 40.
  • Белый — помимо желтого, зеленого, красного и синего, значение = 100.

Это означает, что, например, зеленая башня должна иметь как минимум 1 красную и 1 синюю башню в соседних северных, южных, западных или восточных ячейках (диагонали не учитываются).Белая башня должна быть окружена всеми остальными цветами.

Вот мой алгоритм для 4 башен на поле 4х4:

  1. Общее количество комбинаций = 4^16.
  2. Пройдите через [1..4^16] и преобразуйте каждое число в строку base4, чтобы закодировать расположение башни, поэтому 4^16 = "3333 3333 3333 3333", что будет представлять наши типы башен (0 = синий,..., 3=желтый)
  3. Преобразуйте строку размещения башни в матрицу.
  4. Для каждой башни в матрице проверяйте ее соседей, и если какое-либо из требований не выполняется, вся комбинация терпит неудачу.
  5. Поместите все правильные комбинации в массив, а затем отсортируйте этот массив как строки в лексикографическом порядке, чтобы найти наилучшую возможную комбинацию (сначала необходимо отсортировать символы в строке).

Единственная оптимизация, которую я придумал, — это пропуск комбинаций, в которых нет наиболее ценных башен.Он пропускает некоторую обработку, но я все равно перебираю все 4 ^ 16 комбинаций.

Есть мысли, как это можно улучшить?Примеры кода были бы полезны, если бы они были в Java или php.

-------Обновлять--------

После добавления большего количества незаконных состояний (желтый нельзя построить по углам, белый нельзя построить по углам и по краям, поле должно содержать хотя бы одну башню каждого типа), понимая, что на поле 4х4 можно построить только 1 белую башню. и оптимизация Java-кода общее время сократилось с 40 до ~ 16 часов.Возможно, потоковая обработка сократит это время до 10 часов, но это, вероятно, предел грубого принуждения.

Это было полезно?

Решение

Этот вопрос показался мне интригующим, и, поскольку я изучаю Haskell, я решил попробовать реализовать решение на этом языке.

Я думал о методе ветвей и границ, но не смог придумать хороший способ связать решения, поэтому я просто провел некоторую обрезку, отбрасывая доски, нарушающие правила.

Мой алгоритм работает, начиная с «пустой» доски.Он помещает каждый возможный цвет башни в первый пустой слот и в каждом случае (каждый цвет) затем рекурсивно вызывает себя.Рекурсивные вызовы пробуют каждый цвет во втором слоте, повторяясь снова, пока доска не заполнится.

При размещении каждой башни я проверяю только что установленную башню и всех ее соседей, чтобы убедиться, что они подчиняются правилам, рассматривая любых пустых соседей как подстановочные знаки.Поэтому, если у белой башни есть четыре пустых соседа, я считаю это допустимым.Если размещение недействительно, я не возвращаюсь к нему, фактически отсекая все дерево возможностей под ним.

Код написан так, что я генерирую список всех возможных решений, а затем просматриваю его, чтобы найти лучшее.На самом деле, благодаря ленивой оценке Haskell, элементы списка генерируются по мере необходимости функции поиска, и, поскольку к ним больше никогда не обращаются, они сразу же становятся доступными для сборки мусора, поэтому даже для платы 5x5 использование памяти довольно мало. (2 МБ).

Производительность довольно хорошая.На моем ноутбуке с частотой 2,1 ГГц скомпилированная версия программы решает случай 4х4 примерно за 50 секунд, используя одно ядро.Прямо сейчас я запускаю пример 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 часов, а работа так и не была завершена), я еще раз взглянул на то, как использовать ограничение, чтобы сократить большую часть дерева поиска.

Мой первый подход состоял в том, чтобы оценить верхнюю границу частично заполненного поля, предполагая, что каждая пустая клетка заполнена белой башней.Затем я изменил функцию «решение», чтобы отслеживать лучший результат и игнорировать любую доску, верхняя граница которой меньше этого лучшего результата.

Некоторым это помогло: на доске 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.

Я могу сделать еще одну модификацию и заставить ее найти все доски с максимальным количеством очков, а не только одну.

Другие советы

Если вы не хотите делать A*, используйте ветвь и граница подход.Задачу должно быть относительно легко написать, поскольку ваши функции значений четко определены.Я полагаю, что вы сможете относительно легко отсекать огромные участки пространства поиска.Однако, поскольку пространство поиска довольно велико, это может занять некоторое время.Есть только один способ выяснить :)

Статья в Wiki не самая лучшая в мире.Google может найти вам массу хороших примеров, деревьев и прочего для дальнейшей иллюстрации подхода.

Один из простых способов улучшить метод грубой силы — исследовать только допустимые состояния.Например, если вы пробуете все возможные состояния, вы будете тестировать множество состояний, в которых верхний правый угол представляет собой белую башню.Все эти состояния будут незаконными.Нет смысла генерировать и тестировать все эти состояния.Итак, вы хотите генерировать свои состояния по одному блоку за раз и углубляться в дерево только тогда, когда вы действительно находитесь в потенциально допустимом состоянии.Это сократит ваше дерево поиска на много порядков.

Могут быть и другие интересные вещи, которые вы можете сделать, но это легкое для понимания (надеюсь) улучшение вашего текущего решения.

Я думаю, вам захочется использовать алгоритм ветвей и границ, потому что я думаю, что придумать хорошую эвристику для реализации 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 гораздо дешевле повторно инициализировать существующий объект, чем создавать новый.Еще дешевле использовать массивы примитивов.:)
  • Если вы можете помочь, отойдите от классов коллекций.Они добавят много накладных расходов, которые вам, вероятно, не понадобятся.
  • Убедитесь, что вы не объединяете строки.Используйте Стрингбилдер.
  • И, наконец, рассмотрите возможность переписать все это на C.
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top