0
$\begingroup$

I'm currently programming a game, and I have been stuck on the following problem for a while.

enter image description here

The above figure is a set of stacks. The end-goal is to sort all items by color in the least possible number of moves. For a gameboard like above, computing the solution doesn't take long at all. The problem occurs when the board grows in size, with the maximum board being 8X8 (8 stacks, and 7 colors, with one empty stack) The final solution doesn't need to be exact, the main goal I have is something that's fairly close to the minimum number of moves.

In the above, there would be 6 possible moves:
(1 -> 3) (2 -> 3) (4 -> 3) (2 -> 1) (3 -> 1) and (4 -> 1)

The algorithm I am currently using starts with all of the pieces sorted, and then works backwards to generate the game state.

I currently have a scoring function in place.

# The reversed order of the stacks, with R = Red, Y = Yellow, G = Green, and 0 = Empty
gameFinalState = Set( [R, 0, 0, 0], [Y, G, R, Y], [Y, Y, R, 0], [G, G, G, R] )

# The win state, which I will backtrack from (Also in reverse order)
gameCurrentState = Set ( [R, R, R, R], [Y, Y, Y, Y], [G, G, G, G], [0, 0, 0, 0] )

finalScore = 0

while numberOfStacksIn(gameCurrentState) > 0 {
    topScore = -1
    finalS = None
    currentS = None
    for each finalStack in gameFinalState {
        for integer i = 1 to numberOfItemsInStack(stack) {
            # Empty stacks have no score, and since they are in reverse order, 
            # if the first element is empty they all are empty
            if Set(stack_1, stack_2, ... stack_i) != Set(0) {
                for each currentStack in gameCurrentState {
                    # if there are i elements that are in the correct order of some finalStack
                    if [finalStack[1], ... finalStack[i]] == [currentStack[1], ... currentStack[i]] {
                        # If every element is in the right order
                        if i == numberOfItemsInStack {
                            # This is the highest possible score a stack can have
                            topScore = i
                            finalS = finalStack
                            currentS = currentStack    
                        } else {
                              # If the stack score is equal to the current highest scoring stack
                              if i == topScore {
                                  # A tiebreaker, that scores stacks that have the correct elements and 
                                  # empty spaces since it only takes 1 move to move the
                                  # "next correct piece" to the stack, and there is no additional move to
                                  # remove an incorrect piece
                                  if currentS[i+1] == 0 {
                                      topScore = i
                                      finalS = finalStack
                                      currentS = currentStack
                                  }
                                # If the stack score is greater than the highest scoring stack
                              } else if i > topScore {
                                     topScore = i
                                     finalS = finalStack
                                     currentS = currentStack
                              }
                        }
                   # If the top score is still -1 (every stack has the wrong bottom piece)
                   } else if topScore == -1 {
                       topScore = 0
                       finalS = finalStack
                       currentS = currentStack
                   }
                }
            }
        }
    }
    # Add the topScore to the final score
    finalScore = finalScore + topScore
    # Remove the state that corresponds to the topScore from the gameFinalState set
    gameFinalState = gameFinalState - finalS
    # Remove the state that correspons to the topScore from the gameCurrentState set
    gameCurrentState = gameCurrentState - currentS

    # If there is only one element left and it is the empty stack, remove the element
    if numberOfItemsIn(gameCurrentState) == 1  and Set(0) in gameCurrentState {
        gameCurrentState = gameCurrentState - Set(0)
    }
}

This assigns each specific game state a score. I start by generating every possible move from game state one. (From state one in a 4X4 playing field, this is 3 possible moves.)

Each move is scored, and then all of the top scoring moves go on to the next round, this doesn't always lead to a minimum score however, and sometimes it becomes cyclic. In order to combat this, I also take a random sample of ~50 game states from the next 3 highest scoring sets. For a 4X4 game, this works great, and runs in milliseconds. When the game increases in size, the time complexity grows exponentially.

Are there any edge-cases I'm missing that might speed this up, or perhaps some algorithm that already exists for solving this problem?

I think the approach I'm taking is decent, but the appearance of cycles has me wondering if I can translate this into a graph problem, and use something like Dijkstra's algorithm on it.

$\endgroup$
0
$\begingroup$

Yes, you can formulate this as an $s$-$t$ shortest path problem in a directed graph with a node for each state and an arc from node $i$ to node $j$ for each possible transition. The starting state is the source node $s$, but you have multiple ending states. Introduce a dummy sink node $t$, and for each ending state, introduce an arc to $t$. Now apply Dijkstra's algorithm.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Since there are no edge weights, this boils down to breadth-first search, which is going to have exponentially many nodes to consider even for relatively small instances of the problem... $\endgroup$ – Misha Lavrov Mar 24 at 2:16
  • $\begingroup$ Wouldn't creating a directed graph with a node for every state still be absurdly large? For 16 boxes with 4 items each you'd have 16!/(4!*4!*4!*4!) which is still 63,000,000 nodes for just the 4X4? $\endgroup$ – Tristen Mar 24 at 2:17
  • $\begingroup$ Yes, the number of nodes could be large. I guess you need only the nodes that are reachable from the source, but as @MishaLavrov mentioned, that could still be too big. $\endgroup$ – RobPratt Mar 24 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.