Drop7 Solver

2012-12-19 : 7n - you know you want to!

Drop7 is a puzzle/strategy game for the iPhone that's like a cross between Tetris and Sudoku. It's fun, but what makes it project worthy is that it has a Sequence mode where the pieces come in the same order every time! There are only 7 possibilities per move, and the maximum number of moves is probably around 30. It starts getting hard around 20 moves in. Surely we can come up with some interesting results!

Good commentary.

2012-12-20 : In case you were wondering, no, I (still) can't count. The game is estimated to max out around 30 levels, not 30 moves. There are 2530 moves to complete first level alone; 310410 moves to complete level 20; 360475 moves to complete level 30. But, I can get 2971 points in 9 moves.

2013-03-04 : I've got the basics working pretty well. Now it's just entering data. Following the program's directions, I've resolved the first 110 moves and first four levels. Most amusingly, the program keeps discovering longer and longer combos. So far, it discovered a x15 chain in 22 moves. :)

˜ ™

2013-03-11 : My interest in this project is greatly diminished, and here's why.

One challenge was how to discover the unknown chips and enter them into the simulator. I've basically got that solved.

The first problem was that the chips move around as the game progresses, so when a chip is revealed, it's hard to tell exactly which move it came from. I solved that by adding an annotated mode so it keeps track of and displays the move corresponding to each chip. When a chip is revealed, I know exactly which "unknown" move it represents.

The next problem I had was that, following the simulator's chosen move sequence, it would arrive at a state where multiple chips were revealed. This often led to cascades, and it was hard to remember what happened so I could enter it. I solved this by adding a large score penalty for playing an unknown chip. This was a "guess and check" approach on my part, but it worked. It took me a while to figure out why it works, but here's my understanding. By putting in a large speed bump at that point, it forces the simulation to spend a lot of time looking at that move. Using the "expand the node with the best score" algorithn, the large score drop makes almost every sequence that doesn't contain that move more "interesting" that a sequence where that move occurs. By exploring around that move, it eventually finds a sequence where the unbroken unknown chip is revealed immediately when it is played, and a visible unknown chip aborts the search.

The next problem was that the revealed chips were about sixty moves into the game. The next revealed chip would would be almost exactly the same sequence of moves, except for the last three or four, so I would have to go back and replay all sixty moves. I solved this by being able to specify the initial sequence of moves before simulator was allowed to explore. That way I could force it to keep going with my current game in progress rather than starting all over. This has brought me to one hundred ten known chips. I also added a smaller continuous penalty for unknown chips to encourage it to solve the unknown chips pushed from the bottom on a new level. The UI could be prettied up but there's no more conceptual work to do here. There's just a lot of careful data entry - reaching level thirty requires four hundred seventy five moves.

The other challlenge is going for a high score. I've implemented breadth first and depth first searches. (Well, score greedy search but it's basically a slightly less dumb depth first). Depth first is fine for exposing the limits of the available game data, but because it's so easy to go deep it'll never get around to exploring changes early in the sequence. Using breadth first, I can easily explore eight moves in, and with some effort I'll probably be able to do nine and maybe maybe ten, but anything beyond that is not feasible.

The challenge is in improving that. I did a quick "by-hand" test where I ran the breadth-first algorithm for 8 moves, then fixed the first move and ran the BF algorithm for eight moves past that, then fixed the first two moves, and so on. This produced a pretty impressive score. I could automate this, but it's going to find one solution and giving it more time won't help.

I could use something like A* but I need a heuristic. Because of the way the game gets the biggest points when forming chains, the optimal sequence would be to fill up the board and then when placing the 49th chip on the board, set up a huge chain reaction that cleared the board. At the moment, I have no idea how to tell a board that is a "lost cause" from a board that has a good potential chain. Searching through the permutations of 49 chips (looking 49 moves ahead) is still infeasible; again, the max is about 9.

So, until I get some ideas for a heuristic, or the urge to do more data entry, or the urge to really read up on search strategies, I've plateaued on this project.

˜ ™

Also, this. At least it's contemporaneous. So clearly the whole level 30 rule of thumb is out the window. This video shows reaching level 104. The first 680 chips / 71 levels are available from the first link. Lots of data entry to reach 104. The first source shows a high score of 5,205,955 and still had lots of room left so clearly there's room to advance.

On the drop7 sequence mode global high scors are 1,000,144,303; 999,984,940; and 5,775,373. There's lots of scores in the 5M range, which seems plausible. I really wonder about the 1G scores. Seems like a huge jump. I wonder if there's some unknown game mechanic or if people are just hacking the high score server.

The Result

Source: https://latenighthacking.com:8443/svn/code_root/2012/Drop7Solver

C o m m e n t s :    
(nothing yet)
Edit