Free download Bubble Breaker 10 from Windows store.Press the bubble groups of the same color (from two bubbles of the same color), the goal is to have the highest score at the end of the game. Works on HoloLens.
For a mental exercise I decided to try and solve the bubble breaker game found on many cell phones as well as an example here:Bubble Break Game
- The random (N,M,C) board consists N rows x M columns with C colors
- The goal is to get the highest score by picking the sequence of bubble groups that ultimately leads to the highest score
- A bubble group is 2 or more bubbles of the same color that are adjacent to each other in either x or y direction. Diagonals do not count
- When a group is picked, the bubbles disappear, any holes are filled with bubbles from above first, ie shift down, then any holes are filled by shifting right
- A bubble group score = n * (n - 1) where n is the number of bubbles in the bubble group
The first algorithm is a simple exhaustive recursive algorithm which explores going through the board row by row and column by column picking bubble groups. Once the bubble group is picked, we create a new board and try to solve that board, recursively descending down
Some of the ideas I am using include normalized memoization. Once a board is solved we store the board and the best score in a memoization table.
I create a prototype in python which shows a (2,15,5) board takes 8859 boards to solve in about 3 seconds. A (3,15,5) board takes 12,384,726 boards in 50 minutes on a server. The solver rate is ~3k-4k boards/sec and gradually decreases as the memoization search takes longer. Memoization table grows to 5,692,482 boards, and hits 6,713,566 times.
What other approaches could yield high scores besides the exhaustive search?
I don't seen any obvious way to divide and conquer. But trending towards larger and larger bubbles groups seems to be one approach
Thanks to David Locke for posting the paper link which talks above a window solver which uses a constant-depth lookahead heuristic.
Gregory
GregoryGregory
7 Answers
According to this paper, determining if you can empty the board (which is related to the problem you want to solve) is NP-Complete. That doesn't mean that you won't be able to find a good algorithm, it just means that you likely won't find an efficient one.
David LockeDavid Locke
I'm thinking you could try a branch and bound search with the following idea:
- Given a state of the game S, you branch on S by breaking it up in m sets Si where each Si is the state after taking a legal move of all m legal moves given the state S
- You need two functions U(S) and L(S) that compute a lower and upper bound respectively of a given state S.For the U(S) function I'm thinking calculate the score that you would get if you were able to freely shuffle K bubbles in the board (each move) and arrange the blocks in such a way that would result in the highest score, where K is a value you choose yourself. When your calculating U(S) for a given S it should go quicker if you choose higher K (the conditions are relaxed) so choosing the value of K will be a trade of for quickness of finding U(S) and quality (how tight an upper bound U(S) is.)For the L(S) function calculate the score that you would get if you simply randomly kept click until you got to a state that could not be solved any further. You can do this several times taking the highest lower bound that you get.
Once you have these two functions you can apply standard Bound and Branch search. Note that the speed of your search is going to greatly depend on how tight your Upper Bound is and how tight your Lower Bound is.
ldogldog
To get a faster solution than exhaustive search, I think what you want is probably dynamic programming. In dynamic programming, you find some sort of 'step' that takes you possibly closer to your solution, and keep track of the results of each step in a big matrix. Then, once you have filled in the matrix, you can find the best result, and then work backward to get a path through the matrix that leads to the best result. The matrix is effectively a form of memoization.
Dynamic programming is discussed in The Algorithm Design Manual but there is also plenty of discussion of it on the web. Here's a good intro: http://20bits.com/articles/introduction-to-dynamic-programming/
I'm not sure exactly what the 'step' is for this problem. Perhaps you could make a scoring metric for a board that simply sums the points for each of the bubble groups, and then record this score as you try popping balloons? Good steps would tend to cause bubble groups to coalesce, improving the score, and bad steps would break up bubble groups, making the score worse.
stevehasteveha
You can translate this problem into problem of searching shortest path on graph. http://en.wikipedia.org/wiki/Shortest_path_problem
I would try whit A* and heuristics would include number of islands.
Luka RahneLuka Rahne
In my chess program I use some ideas which could probably adapted to this problem.
- Move Ordering. First find allpossible moves, store them in a list,and sort them according to someheuristic. The 'better' ones first,the 'bad' ones last. For example,this could be a function of the sizeof the group (prefer medium sizedgroups), or the number of adjacentcolors, groups, etc.
- Iterative Deepening. Instead ofrunning a pure depth-first search,cut of the search after a certaindeep and use some heuristic to assessthe result. Now research the treewith 'better' moves first.
- Pruning. Don't search moves whichseems 'obviously' bad, according tosome, again, heuristic. This involvesthe risk that you won't find theoptimal solution anymore, butdepending on your heuristics you willvery likely find it much earlier.
- Hash Tables. No need to store everyboard you come accross, just remembera certain number and overwrite olderones.
Gunther PiezGunther Piez
I'm almost finished writing my version of the 'solver' in Java. It does both exhaustive search, which takes fricking ages for larger board sizes, and a directed search based on a 'pool' of possible paths, which is pruned after every generation, and a fitness function used to prune the pool. I'm just trying to tune the fitness function now...
Update - this is now available at http://bubblesolver.sourceforge.net/
mreddinmreddin
This isn't my area of expertise, but I would like to recommend a book to you. Get a copy of The Algorithm Design Manual by Steven Skiena. This has a whole list of different algorithms, and once you read through it you can use it as a reference. If nothing else it will help you consider your options.
stevehasteveha
Not the answer you're looking for? Browse other questions tagged pythonalgorithmlanguage-agnostic or ask your own question.
Bubble Breaker (Шарики) is a game where you must select a color group of bubbles on a grid and click to destroy them.
The more bubbles you destroy with a single click, the higher your score will be.
Bubble Breaker involves more deep thinking and strategy instead of fast paced action.
It's very small (only 3 Mb) Bubble Breaker app !
It working on all devices with all screen resolution !
To enable/disable sound effects please use hardware button MENU or use long press in the game field.
If you like this app please do not forget to give a positive feedback !!!
Recently the rating this app fell 99% anonymously from 4.5 to 3.9 :-(
The more bubbles you destroy with a single click, the higher your score will be.
Bubble Breaker involves more deep thinking and strategy instead of fast paced action.
It's very small (only 3 Mb) Bubble Breaker app !
It working on all devices with all screen resolution !
To enable/disable sound effects please use hardware button MENU or use long press in the game field.
If you like this app please do not forget to give a positive feedback !!!
Recently the rating this app fell 99% anonymously from 4.5 to 3.9 :-(
Collapse
20,678 total
4
2
Read more