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 I'm thinking you could try a branch and bound search with the following idea: ![]() Thanks to David Locke for posting the paper link which talks above a window solver which uses a constant-depth lookahead heuristic. But trending towards larger and larger bubbles groups seems to be one approach I don't seen any obvious way to divide and conquer. What other approaches could yield high scores besides the exhaustive search? Memoization table grows to 5,692,482 boards, and hits 6,713,566 times. The solver rate is ~3k-4k boards/sec and gradually decreases as the memoization search takes longer. A (3,15,5) board takes 12,384,726 boards in 50 minutes on a server. ![]() I create a prototype in python which shows a (2,15,5) board takes 8859 boards to solve in about 3 seconds. Once a board is solved we store the board and the best score in a memoization table. Some of the ideas I am using include normalized memoization. Once the bubble group is picked, we create a new board and try to solve that board, recursively descending down 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. A bubble group score = n * (n - 1) where n is the number of bubbles in the bubble group.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 is 2 or more bubbles of the same color that are adjacent to each other in either x or y direction.The goal is to get the highest score by picking the sequence of bubble groups that ultimately leads to the highest score.The random (N,M,C) board consists N rows x M columns with C colors. ![]() 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
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |