Help me analyse this game
February 1, 2015 3:50 AM
I've been playing a computer game called Puzzle & Dragons where you "fight" monsters by moving jewels around on a grid to create rows of three or more. I want to know if there's any way to work out a good series of moves other than by brute force. Details below:
The Puzzle & Dragons grid is six (horizontal) by five (vertical). At the start of a turn it is filled with different colors of jewels - usually six, but special levels may have as many as nine or as few as three.
The player's turn starts when he or she clicks on a jewel and drags it around the grid. The selected jewel pushes other jewels out of the way. I.e. if the jewel the player drags is represented by an asterisk, and the player drags it three steps to the right, the position *ABCD will become ABC*D. You can "undo" a move by moving the jewel back the way it came, with no penalty. The player's turn is over when he or she releases the jewel that was being dragged, or after a few seconds - usually around four or five. A middling player, with practice, can drag a jewel around thirty places in that time without too much difficulty, more if the jewel is being dragged in straight lines.
After the player's turn is over, all matched lines of three or more similar jewels are removed. You can have two or more intersecting lines that are each three-or-more in length: one common case is five jewels in the shape of a cross. Once all matched jewels are removed, the remaining jewels "fall" to the bottom of the grid, filling any holes, and more jewels "fall" from above to replace the gaps at the top. This may create more matches, which are added to your total, and the cascase continues until no more matches are made.
The optimal set of moves depend on your strategy for the level: you may want many matches, or only a few, matches of particular colors, or particular lengths. You may not be trying to get matches, but simply rearrange the grid for a subsequent move.
Ideally, you would be able to specify a layout that maximises your score for a given set of jewels (for instance: seven red, eight yellow, fifteen blue). There are programs that claim to solve layouts in this game, but they seem to work by brute-forcing a solution - and they sometimes fail to give the best answer.
Q: If we start with a randomised original layout, how "hard" is it to calculate the minimum set of moves necessary to achieve an ideal layout?
Q:If this is too "hard", can we determine whether the minimal set of moves is greater than a certain number?
Q: If that's too hard, are there better algorithms than simply trying to brute-force a solution that is less than, e.g., thirty moves?
Q: If there are no better alternatives, how can the tree of possible moves be pruned to make the search as quick as possible?
The Puzzle & Dragons grid is six (horizontal) by five (vertical). At the start of a turn it is filled with different colors of jewels - usually six, but special levels may have as many as nine or as few as three.
The player's turn starts when he or she clicks on a jewel and drags it around the grid. The selected jewel pushes other jewels out of the way. I.e. if the jewel the player drags is represented by an asterisk, and the player drags it three steps to the right, the position *ABCD will become ABC*D. You can "undo" a move by moving the jewel back the way it came, with no penalty. The player's turn is over when he or she releases the jewel that was being dragged, or after a few seconds - usually around four or five. A middling player, with practice, can drag a jewel around thirty places in that time without too much difficulty, more if the jewel is being dragged in straight lines.
After the player's turn is over, all matched lines of three or more similar jewels are removed. You can have two or more intersecting lines that are each three-or-more in length: one common case is five jewels in the shape of a cross. Once all matched jewels are removed, the remaining jewels "fall" to the bottom of the grid, filling any holes, and more jewels "fall" from above to replace the gaps at the top. This may create more matches, which are added to your total, and the cascase continues until no more matches are made.
The optimal set of moves depend on your strategy for the level: you may want many matches, or only a few, matches of particular colors, or particular lengths. You may not be trying to get matches, but simply rearrange the grid for a subsequent move.
Ideally, you would be able to specify a layout that maximises your score for a given set of jewels (for instance: seven red, eight yellow, fifteen blue). There are programs that claim to solve layouts in this game, but they seem to work by brute-forcing a solution - and they sometimes fail to give the best answer.
Q: If we start with a randomised original layout, how "hard" is it to calculate the minimum set of moves necessary to achieve an ideal layout?
Q:If this is too "hard", can we determine whether the minimal set of moves is greater than a certain number?
Q: If that's too hard, are there better algorithms than simply trying to brute-force a solution that is less than, e.g., thirty moves?
Q: If there are no better alternatives, how can the tree of possible moves be pruned to make the search as quick as possible?
« Older And to those of you listening in the year 2100, | Give me your experience of keratin hair... Newer »
This thread is closed to new comments.
You could start from easier grid-based problems (i.e.: Sudoku) and work you way up.
posted by KMB at 4:36 AM on February 1, 2015