Tentando construir algoritmo para melhor posicionamento da torre em um jogo

Question

Este vai ser um longo post e apenas por diversão, por isso, se você não tem muito tempo caras ajudam a melhor ir com questões mais importantes em vez disso:)

Existe um jogo chamado "Tower Bloxx", recentemente lançado no Xbox. Uma parte do jogo é colocar torres coloridas diferentes em um campo em uma forma mais adequada, a fim de maximizar o número de maioria torres valiosos. Eu escrevi um algoritmo que iria determinar a colocação torre mais eficiente, mas não é muito eficiente e praticamente só força bruta todas as combinações possíveis. Para o campo de 4x4 com 4 tipos de torres ele resolve-lo em cerca de 1 hora, 5 tipos de torres levaria cerca de 40 horas, que é muito.

Aqui estão as regras: Existem 5 tipos de torres que poderia ser colocado em um campo. Existem vários tipos de campos, o mais fácil é apenas 4x4 matriz, outros campos têm alguns "espaços em branco", onde você não pode construir. Seu objetivo é colocar como muitos o maior número de torres valiosos em um campo possível para maximizar o valor total de torre em um campo (vamos supor que todas as torres são construídas ao mesmo tempo, não há voltas).

tipos Torre (em ordem do menos para o mais valioso):

• Blue - pode ser colocado em qualquer lugar, valor = 10
• Red - podem ser colocados apenas além azul, valor = 20
• Green - colocado além vermelho e azul, valor = 30
• Yellow - além de verde, vermelho e azul, valor = 40
• White - além de amarelo, verde, vermelho e azul, valor = 100

O que significa que, por exemplo torre verde deve ter pelo menos 1 vermelho e 1 torres azuis em ambos norte, sul, células vizinhas leste a oeste ou (diagonais não contam). Torre branca deve ser cercado com todas as outras cores.

Aqui está o meu algoritmo para 4 torres no campo 4x4:

1. Número total de combinações = 4 ^ 16
2. Percorre [1..4 ^ 16] e converter cada número para string base4, a fim de colocação torre de codificar, de modo 4 ^ 16 = "3333 3333 3333 3333", que representaria nossos tipos de torres (0 = blue ,. .., 3 = amarelo)
3. string Convert torre colocação na matriz.
4. Para cada torre em uma matriz de verificar os seus vizinhos e se algum dos requisitos falhar esta combinação toda falha.
5. Coloque todas as combinações corretas em uma matriz e em seguida, classificar essa matriz como strings em ordem lexicográfica para encontrar melhor combinação possível (primeira necessidade de caracteres de classificação em uma string).

A única otimização eu vim com é pular combinações que não contêm quaisquer maioria das torres valiosos. Ele ignora algum processamento, mas eu ainda percorrer todos os 4 ^ 16 combinações.

Qualquer pensamento como isso pode ser melhorada? Exemplos de código seria útil se em Java ou PHP.

------- -------- Atualização

Após a adição de estados mais ilegais (amarelo pode não ser construída nos cantos, branco não podem ser construídos em cantos e nas arestas, campo deve conter, pelo menos, uma torre de cada tipo), percebendo que apenas uma torre branco poderia ser possivelmente incorporada no campo de 4x4 e optimizar código Java o tempo total foi reduzido de 40 para ~ 16 horas. Talvez enfiar iria trazê-lo para baixo para 10 horas, mas isso é provavelmente por força bruta limite.

Answer 1

Eu encontrei esta questão intrigante, e desde que eu estou me ensinando Haskell, eu decidi tentar a minha mão a implementação de uma solução nesse idioma.

Eu pensei sobre branch-and-bound, mas não conseguiu chegar a uma boa maneira de vinculados as soluções, então eu apenas fiz alguma poda, descartando placas que violam as regras.

As minhas algoritmo funciona começando com uma placa de "vazio". Ele coloca cada possível cor da torre no primeiro slot vazio e em cada caso (cada cor), em seguida, de forma recursiva chama a si mesmo. As chamadas recursed tentar cada cor no segundo slot, recursão novamente, até que o tabuleiro está cheio.

Como cada torre é colocado, eu verifico a torre recém-colocado e tudo isso de vizinhos para verificar se eles estão obedecendo as regras, tratando os vizinhos vazios como cartões selvagens. Então, se uma torre branca tem quatro vizinhos vazios, considero válido. Se um canal não é válido, eu não recurse em que a colocação de, efetivamente podar a árvore inteira de possibilidades sob ele.

A forma como o código é escrito, eu gerar uma lista de todas as soluções possíveis, então olhar através da lista para encontrar o melhor. Na realidade, graças a avaliação preguiçosa de Haskell, os elementos da lista são gerados como a função de pesquisa precisa deles, e uma vez que eles nunca são referidos mais uma vez eles se tornam disponíveis para a coleta de lixo de imediato, por isso mesmo para um uso de memória tabuleiro de 5x5 é bastante pequeno (2 MB).

O desempenho é muito bom. No meu laptop 2,1 GHz, a versão compilada do programa resolve o caso 4x4 em ~ 50 segundos, usando um núcleo. Estou correndo um exemplo 5x5 agora para ver quanto tempo vai demorar. Desde código funcional é bastante fácil de paralelizar, eu também vou experimentar com processamento paralelo. Há um compilador Haskell parallelized que não só irá difundir o trabalho em vários núcleos, mas em várias máquinas, bem como, e isto é um problema muito paralelizável.

Aqui está o meu código até agora. Eu percebo que você especificou Java ou PHP, e Haskell é bastante diferente. Se você quiser jogar com ele, você pode modificar a definição da variável "BND" pouco acima do fundo para definir o tamanho da placa. Basta configurá-lo para ((1,1), (x, y)), onde x e y são o número de colunas e linhas, respectivamente.

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

Além disso, lembre-se este é o meu primeiro programa Haskell não-trivial. Tenho certeza de que isso pode ser feito muito mais elegante e sucinta.

Atualizar : Desde que era ainda muito para fazer um 5x5 com 5 cores (I esperou 12 horas e não tinha terminado) demorado, eu levei um outro olhar para como usar delimitadora para podar mais da árvore de busca.

A primeira abordagem foi a de estimar o limite superior de uma placa parcialmente preenchido, assumindo cada célula vazia é preenchido com uma torre branco. Eu, então, modificado a função 'solução' para rastrear a melhor pontuação visto e ignorar qualquer placa cujo limite superior é inferior do que melhor pontuação.

Isso ajudou um pouco, reduzindo uma placa de 4x4x5 de 23s a 15s. Para melhorar ainda mais, que modificou a função de limite superior para assumir que cada vazio é enchido com o melhor possível torre, de acordo com o conteúdo da célula não vazios existentes. Isso ajudou um grande negócio, reduzindo o tempo de 4x4x5 para 2s.

executando-o em 5x5x5 levou 2600s, dando o seguinte conselho:

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

com uma pontuação de 730.

Eu posso fazer outra modificação e tê-lo encontrar todas as placas de máxima pontuação, em vez de apenas um.

Answer 2

Se você não quer fazer A *, use uma href="http://en.wikipedia.org/wiki/Branch_and_bound" rel="nofollow noreferrer"> ramo e limite abordagem

O artigo wiki não é o melhor do mundo. Google pode encontrar uma tonelada de exemplos e árvores agradáveis ??e coisas para ilustrar ainda mais a abordagem.

Answer 3

Uma maneira fácil de melhorar o método de força bruta é explorar estados só legais. Por exemplo, se você está tentando todos os estados possíveis, você estará testando muitos estados onde o canto superior direito é uma torre branca. Todos estes estados será ilegal. Não faz sentido para gerar e testar todos esses estados. Então você quer gerar seus estados um bloco de cada vez, e só ir mais fundo na árvore quando você está realmente em um estado potencialmente válido. Isto irá reduzir a sua árvore de pesquisa por várias ordens de magnitude.

Pode haver mais extravagantes coisas que você pode fazer, mas este é um fácil melhoramento de entender (espera-se) para sua solução atual.

Answer 4

Eu acho que você vai querer usar um algoritmo de limite branch-and-porque eu acho que chegar com uma boa heurística para um A * implementação será difícil (mas, isso é apenas minha intuitition).

O pseudo-código para uma implementação branch-and-bound é:

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)

A idéia é que buscamos todas as placas possíveis, em ordem, mas nós acompanhar a melhor que encontrei até agora (este é o limite). Então, se encontrarmos uma placa parcial que sabemos nunca será melhor do que o melhor até agora, então, parar de olhar trabalhando nisso bordo parcial:. Que cortar esse ramo da árvore de pesquisa

No código acima eu estou fazendo a verificação, assumindo que todos os espaços em branco seria preenchido por as peças brancas, como não podemos fazer melhor do que isso. Estou certo de que com um pouco de pensamento você pode vir até com um apertado ligado do que isso.

Outro lugar onde você pode tentar otimizar está na ordem do para-cada loop. Você quer tentar peças na ordem correta ordem. Isto é, de forma otimizada desejar que a primeira solução encontrada para ser o melhor, ou pelo menos um com uma pontuação muito alta.

Answer 5

Parece uma boa abordagem seria começar com uma torre branca e, em seguida, construir um conjunto de torres em torno dele com base nos requisitos, tentando encontrar o menor conjunto de cor possível de formas que podem agir como bloqueio telhas.

Answer 6

Eu queria defender linear programação com incógnitas inteiros , mas verifica-se que é NP-difícil, mesmo no caso binário. No entanto, você ainda pode obter grande sucesso na otimização de um problema como a sua, onde existem muitas soluções válidas e você simplesmente querem o melhor.

programação linear, para este tipo de problema, no essencial, em que tem uma série de variáveis ??(por exemplo, o número de torres vermelha presente na célula (M, N)) e as relações entre as variáveis ??(por exemplo, o número de torres brancas na célula (M, N) deve ser menor do que ou igual ao número de torres da cor não branca que tem o menor número tal, entre todos os seus vizinhos). É uma espécie de dor para escrever um programa linear, mas se você quer uma solução que é executado em segundos, é provavelmente a sua melhor aposta.

Answer 7

Você recebeu um monte de bons conselhos sobre o lado algorítmica das coisas, então eu não tenho muito a acrescentar. Mas, supondo que Java como linguagem, aqui estão algumas sugestões bastante óbvias para melhoria do desempenho.

• Certifique-se de que você não está instanciar todos os objetos dentro desse loop 4 ^ 16. É muito, muito mais barato para a JVM para re-inicializar um objeto existente do que criar um novo. Mesmo mais barato usar matrizes de primitivos. :)
• Se você pode ajudá-lo, passo das classes de coleção. Eles vão adicionar um monte de sobrecarga que você provavelmente não precisa.
• Certifique-se que você não está concatenando quaisquer cordas. Use StringBuilder.
• E por último, considere re-escrever a coisa toda em C.