게임 내 최적의 타워 배치를 위한 알고리즘 구축 시도

https://stackoverflow.com/questions/1626189

06-07-2019
|

문제

이것은 단지 재미를 위한 긴 게시물이 될 것이므로 시간이 많지 않다면 대신 더 중요한 질문으로 사람들을 도와주는 것이 좋습니다 :)

최근 Xbox에 출시된 "Tower Bloxx"라는 게임이 있습니다.게임의 한 부분은 가장 가치 있는 타워의 수를 최대화하기 위해 가장 최적의 방식으로 필드에 다양한 색상의 타워를 배치하는 것입니다.나는 가장 효율적인 타워 배치를 결정하는 알고리즘을 작성했지만 그다지 효율적이지 않으며 가능한 모든 조합을 무차별 대입하는 것에 불과합니다.4개의 타워 유형이 있는 4x4 필드의 경우 약 1시간 안에 문제를 해결하고, 5개의 타워 유형은 약 40시간이 소요되는데 이는 너무 많은 시간입니다.

규칙은 다음과 같습니다.필드에 설치할 수 있는 타워는 5가지 유형이 있습니다.필드에는 여러 유형이 있습니다. 가장 쉬운 것은 4x4 행렬이고 다른 필드에는 작성할 수 없는 "공백"이 있습니다.귀하의 목표는 가능한 한 많은 가장 가치 있는 타워를 필드에 배치하여 필드의 총 타워 가치를 최대화하는 것입니다(모든 타워가 한 번에 건설되고 차례가 없다고 가정합니다).

타워형 (가장 가치가 낮은 것부터 순서대로):

파란색 - 어디에나 배치 가능, 값 = 10
빨간색 - 파란색 외에만 배치 가능, 값 = 20
녹색 - 빨간색과 파란색 외에 배치, 값 = 30
노란색 - 녹색, 빨간색, 파란색 외에 값 = 40
흰색 - 노란색, 녹색, 빨간색, 파란색 외에 값 = 100

이는 예를 들어 녹색 타워에는 북쪽, 남쪽, 서쪽 또는 동쪽 인접 셀에 빨간색 타워 1개와 파란색 타워 1개가 있어야 함을 의미합니다(대각선은 포함되지 않음).흰색 타워는 다른 모든 색상으로 둘러싸여 있어야 합니다.

4x4 필드의 4개 타워에 대한 알고리즘은 다음과 같습니다.

총 조합 수 = 4^16
[1..4^16]을 반복하고 타워 배치를 인코딩하기 위해 모든 숫자를 base4 문자열로 변환합니다. 따라서 4^16 = "3333 3333 3333 3333"은 타워 유형(0=파란색,..., 3=노란색)
타워 배치 문자열을 매트릭스로 변환합니다.
매트릭스의 모든 타워에 대해 이웃을 확인하고 요구 사항 중 하나라도 실패하면 전체 조합이 실패합니다.
모든 올바른 조합을 배열에 넣은 다음 이 배열을 사전순으로 문자열로 정렬하여 가능한 최상의 조합을 찾습니다(먼저 문자열의 문자를 정렬해야 함).

제가 생각해낸 유일한 최적화는 가장 가치 있는 타워가 포함되지 않은 조합을 건너뛰는 것입니다.일부 처리를 건너뛰지만 여전히 4^16 조합을 모두 반복합니다.

이것이 어떻게 개선될 수 있는지 생각해 보셨나요?Java 또는 PHP의 경우 코드 샘플이 도움이 될 것입니다.

-------업데이트--------

더 많은 불법 상태를 추가한 후(노란색은 모서리에 지을 수 없고 흰색은 모서리와 가장자리에 지을 수 없으며 필드에는 각 유형별로 최소 하나의 타워가 포함되어야 함) 4x4 필드에 흰색 타워 하나만 지을 수 있음을 깨달았습니다. Java 코드를 최적화하면 총 시간이 40시간에서 ~16시간으로 단축되었습니다.스레딩을 사용하면 10시간으로 단축될 수 있지만 이는 무차별 강제 제한일 수 있습니다.

해결책

나는 이 질문이 흥미로웠고, 하스켈을 독학하고 있기 때문에 그 언어로 솔루션을 구현해 보기로 결정했습니다.

Branch-and-Bound도 생각했지만 솔루션을 바인딩하는 좋은 방법이 떠오르지 않아 규칙을 위반하는 보드를 폐기하는 등의 가지치기 작업을 수행했습니다.

내 알고리즘은 "빈" 보드로 시작하여 작동합니다.타워의 가능한 각 색상을 첫 번째 빈 슬롯에 배치하고 각 경우(각 색상)에 대해 재귀적으로 자신을 호출합니다.반복 호출은 보드가 가득 찰 때까지 두 번째 슬롯의 각 색상을 다시 반복하여 시도합니다.

각 타워가 배치될 때 방금 배치된 타워와 모든 이웃을 확인하여 규칙을 준수하는지 확인하고 빈 이웃을 와일드 카드로 처리합니다.따라서 흰색 타워에 빈 이웃이 4개 있으면 타당하다고 생각합니다.배치가 유효하지 않은 경우 해당 배치를 반복하지 않고 그 아래의 전체 가능성 트리를 효과적으로 정리합니다.

코드가 작성되는 방식에 따라 가능한 모든 솔루션 목록을 생성한 다음 목록을 살펴보고 가장 적합한 솔루션을 찾습니다.실제로 Haskell의 지연 평가 덕분에 검색 기능에 필요한 목록 요소가 생성되고 다시 참조되지 않기 때문에 즉시 가비지 수집에 사용할 수 있게 되므로 5x5 보드의 경우에도 메모리 사용량이 상당히 적습니다. (2MB).

성능은 꽤 좋습니다.내 2.1GHz 노트북에서 프로그램의 컴파일된 버전은 하나의 코어를 사용하여 ~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

또한 이것이 나의 첫 번째 중요하지 않은 하스켈 프로그램이라는 것을 기억하십시오.훨씬 더 우아하고 간결하게 할 수 있을 거라 확신합니다.

업데이트:5가지 색상으로 5x5를 수행하는 것은 여전히 시간이 많이 걸리기 때문에(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점으로.

또 다른 수정을 하여 단 하나가 아닌 최대 점수 보드를 모두 찾도록 할 수 있습니다.

다른 팁

당신이*를하고 싶지 않다면, 분기 및 바운드 접근하다. 값 기능이 잘 정의되어 있기 때문에 문제는 비교적 쉽게 코딩해야합니다. 검색 공간의 거대한 부분을 상대적으로 쉽게 잘라낼 수 있다고 생각합니다. 그러나 검색 공간이 꽤 크기 때문에 여전히 시간이 걸릴 수 있습니다. 찾는 한 가지 방법 :)

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 Loop의 순서입니다. 올바른 순서로 조각을 시도하고 싶습니다. 즉, 최적의 솔루션이 가장 좋은 솔루션이거나 적어도 높은 점수를 가진 솔루션을 원합니다.

좋은 접근 방식은 흰색 타워로 시작한 다음 요구 사항에 따라 주위에 탑 세트를 만들어서 연동 타일로 작용할 수있는 가장 작은 색상의 모양 세트를 찾으려고 노력하는 것 같습니다.

나는 옹호하고 싶었다 정수 미지의 선형 프로그래밍, 그러나 바이너리 케이스에서도 NP-HARD라는 것이 밝혀졌습니다. 그러나 많은 유효한 솔루션이 있고 단순히 최고의 솔루션을 원합니다.

이런 종류의 문제에 대해 선형 프로그래밍은 기본적으로 많은 변수 (예 : 셀에 존재하는 빨간 타워 수)와 변수 간의 관계 (예 : 흰색 타워의 수 셀 (m, n)은 모든 이웃 중에서 가장 작은 흰색이 아닌 색상의 탑 수보다 작거나 동일해야합니다). 선형 프로그램을 작성하는 것은 일종의 고통이지만 몇 초 안에 실행되는 솔루션을 원한다면 아마도 최선의 방법 일 것입니다.

알고리즘 측면에 대한 많은 좋은 조언을 받았으므로 추가 할 것이 많지 않습니다. 그러나 Java를 언어로 가정하면 성능 향상을위한 몇 가지 명백한 제안이 있습니다.

4^16 루프 내부의 객체를 인스턴스화하지 않도록하십시오. JVM이 새로운 개체를 만드는 것보다 기존 객체를 재개하는 것은 훨씬 저렴합니다. 프리미티브의 배열을 사용하기에는 더 저렴합니다. :)
도와 줄 수 있다면 컬렉션 클래스에서 벗어나십시오. 그들은 당신이 필요로하지 않는 많은 오버 헤드를 추가 할 것입니다.
문자열을 연결하지 않도록하십시오. StringBuilder를 사용하십시오.
그리고 마지막으로 C에서 모든 것을 다시 작성하는 것을 고려하십시오.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow