Voltorb Flip – Move Recommendations

Safety

The first step to recommending a move is to filter by safety; safety overrides all other factors when deciding which move to take. For each tile, I simply check that tile in every solution; the tile(s) that have the fewest solutions giving them voltorbs are the safest.

Value

The next filter is by estimated value; this is done by going through each solution for each tile, and seeing which tile averages the highest value across all the solutions (in the actual code, I don’t use averages, I just use sums, because the relative magnitude of the averages is the same as the relative magnitude of the sums, since they all divide by the same number).

Helpfulness

So far we’ve found the safest tiles, and within those tiles, found the ones that are likeliest to be high. Now there’s a third filter, which hasn’t yet been built in to the released code. This filter determines how much the tiles are likely to help the computer. Basically, it looks at each tile, and determines which tiles will most reduce the number of remaining solutions (if it takes out half the remaining solutions, then we’ll be that much more accurate with future calculations).

So we look through each remaining tile, and find the one that maximizes the average number of reductions by putting it into the formula

avg_reductions = P1 * R1 + P2 * R2 + P3 * R3, where P is the probability of an event, and R is the amount of reduction it gives. P can also be expressed as N/T, where N is the number of solutions that have that specific number, and T is the total number of solutions.

Further Math For Efficiency’s Sake

Since the amount of reductions R for any given value is (T –N), this leads to a formula I prefer:

avg_reductions = (N1/T)(T – N1) + (N2/T)(T – N2) + (N3/T)(T – N3)

or

avg_reductions = (Tsum(N1..N3)-sum(N1^2..N3^2))/T

Since all the tiles are going through the formula using the same T, and we only care about relative magnitude, we can forget about the division by T altogether, and it ends up being much simpler to calculate overall.

Voltorb Flip – Optimizations

The Simple Optimization
The simplest optimization to explain is as follows: because empty tiles are filled in order when solving the board, I don’t have to recheck all the ones that have already been solved. Basically, I just save the row and column every time I recurse into the solve function, so it starts at the last tile solved, rather than looking through the beginning.

The “Move” Optimization
My original method essentially said:

1. Solve the board
2. Get the user’s move, and store it in the board
3. Go to step 1

This was time-consuming, and I soon realized that there was a nice alternative: rather than re-solving the board, I could simply go through the previous listed of solutions from before, and remove the ones that didn’t include the move the user entered. This came with problems, however. First of all, you should know that there are three main ways to store a list of solutions inside a program:

1. Using a vector; vectors allow for constant-time random-access, and linear-time removal/insertion at any place but the end
2. Using a list; lists allow for linear-time random-access, but constant-time removal/insertion
3. Using a deque, which is similar in efficiency to a vector

Now, solving a board is technically exponential time, so any of those options is better, but I wanted the best one. I then remembered a beautiful little trick wowus showed me, which was that, when removing from an unsorted vector, you can do it in constant time by swapping the element you want to remove with the last element, and then removing the last element (which can be done in constant time). Voila! I implemented this, and now the whole simplification runs in linear time, as does random access. I realized later that I never actually access randomly, but only iterate, so a list could have done just as well as a vector. Oh well.

The Solver Optimization
This is a hugely important optimization, despite the fact that it’s very few lines of code. First of all, realize that in a 25-tile board, where each tile can be 4 possible things, there are 4^25 permutations. Now, if we try each one, and then try to check if each one is valid, this would take an unfathomable amount of time (4^25 is like the number of characters you could store in .TXT files in a 1,000,000 GB hard drive).

What can be done, however, is after a tile is modified, no matter which tile it is, recheck the row and column that tile was in. If the row/column is no longer valid, we don’t need to try and solve the rest of the board (none of the solutions will be valid, because they contain some impossible row/column), we can simply move on to the next step without recursing.

Now, how does one check if a row/column is valid? It’s actually quite easy. First of all, we check if the sum of all the tiles in the row/column exceeds the sum the board tells us for that row/column; if it’s too big, it’s invalid. Next, we check if the number of voltorbs exceeds the number the board tells us for that row/column; if it’s too big, it’s invalid.

Now it gets a little trickier. We take the number of unknown tiles left in the row/column, and we subtract the number of voltorbs we have yet to find in that row/column. That gives us the number of tiles that actually have values. We multiply the number of valuable tiles by 3 (the maximum possible value), and add it to whatever sum we already have for that row/column. If it’s less than the sum the board tells us for that row/column, it’s invalid. In other words, this just assumes the rest of the tiles are all 3s, so if you can’t hit the required sum with all 3s, then there’s no way it can be valid.

I lied a little on the Solver blog post; it's not quite as simple as what I wrote; there's that extra validation step every time you change a tile.

Voltorb Flip – Solver

About half of the Voltorb Flip Solver is.. well, the solver. When you get down to it, the Solver follows a very simple idea: it tries every permutation with every different state of every tile until it’s tried them all. The basic algorithm is as follows:

1. Find the first empty tile (left-right, top-down, start at top-left)
2. If none are found, you’re done; otherwise, continue to step 3.
3. Pretend the tile’s a voltorb
4. Try and solve the rest of the board
5. If the rest of the board was solved, add the solution to our list of possible solutions
6. If the rest of the board was unsolvable, ignore it
7. Repeat step 3 for all possible tile states (voltorb, 1, 2, and 3)

That’s basically it. You’ll notice that this algorithm is recursive, that is, the function contains itself (step 4).
As for steps 5 and 6, when I say the board was solved, I mean it was solved correctly; that is, all the rows and columns added up to what they should have, and contained all the voltorbs they should have.
So that’s it! I’ll post again shortly, detailing some of the optimizations I made in the above algorithm, and the recommendation algorithm.

Voltorb Flip - Update History

Version 2.0 is now up and running. It no longer uses .TXT files as input/output, so it should be a little quicker and less of a hassle to use. It's not very thoroughly tested, but I've run through a couple of times and it's working fine.

Version 2.1 wasn't really published. It was a very temporary update just patching the giant memory leak (and subsequent crashing) of version 2.0

Version 2.2 is up now. I took the speed optimization of 2.0, the non-crashing of 2.1, mixed them together, and got 2.2. For those of you who are interested, the crashing was an issue with recursive member function calls, a vector which was a member of the thing it was copying, and a copy constructor.

Version 2.3 includes a speed fix for 2.2, which may be going slowly for some people. It also includes a title bar-type thing, so now you can be sure of what version you're running. Also made some minor formatting/text changes and cleaned up the code a little.

Version 2.4 includes some minor text/formatting changes and yet another speed fix. This fix only applies to moves after the initial board setup, but it should be a rather noticeable jump. However, it's a little hard to test whether or not it still works; it's a simple change, and it seems to work at a glance and basic use, but if it does strange things, then let me know!

Version 2.4.2 fixed two bugs in version 2.4. Both are giving inaccurate data and 2.4.0 is crashing. If you downloaded 2.4 before 11:30 EST 17/07/2010, then redownload.

Version 2.5.0 has a few formatting changes (XX is used instead of OO for recommended moves, and -- is used for unknown tiles). It also introduces a simple, quick system that will automatically include all the tiles that are guaranteed to be 1 or a voltorb, and it will no longer recommended tiles that are guaranteed 1s.

Version 2.5.1 has a few formatting changes (V for voltorb) and also adds a relatively important patch for 2.5.0. 2.5.0 was having issues with getting new solutions after moves, so it was getting messed up on probability and value predictions.

Voltorb Flip - Current & Future Work

Current Work
Rewriting it. When I first created the program, I wasn't even sure it could be done realistically, and so I was just trying to get it to work. I have continued development on that initial program, but as the few of you know who have downloaded the source, it's really abysmal coding. To that end, I'm rewriting the entire thing from scratch (it's under 1000 lines of code, so it's not too bad), and trying to do it nicely this time. That being said, it will probably be a while until the next release, but when it is released, the source will be pushed on GitHub.

Output changes. I'm also making slight changes to the output. The program used to give an average value estimate simply by averaging out the values of the tile in each solution, but that's not accurate; you could get an average value of 2 with only solutions of 1 and 3. I'm planning to change it to display the odds of each value (along with the odds of voltorbs) to give the user a slightly better idea of what's going on. This will also give rise to a slightly more sophisticated tile-recommendation system, as I will now be able to recommend tiles based on how many possible solutions they exclude.

For people interested, I will be posting a few blog entries on some of the math and algorithms behind voltorb flip (including the absolutely beautiful constant-time removal of an element from an unsorted vector/array, which is usually linear-time)

Pending Updates

• A speed patch for after you move to a voltorb or a already-flipped tile
• Allowing for taking back moves
• Better error handling
• More cost-benefit analysis when recommending tiles
• A GUI