A short problem

This math problem had me going for a bit. Looked at from a distance, it looked like one thing; and when I had the occasion to sit down and hash it out, it was quite another.

A student submitted a project that was of her game which was played with just two dice. If you roll a 2 or 12 you win; but if you roll any sum from 5 to 9 you lose; and if you roll a 3, a 4, a 10, or an 11, you survive to another round. You are limited to a maximum of three turns to roll a winning total.

It was not the normal Bernoulli trial, since this doesn’t just have the two states of success and failure; but it introduces a third state, which we will call “survival”. While you don’t “win” if you survive, you can still play again, but you can’t go past 3 turns. Three survivals in a row gets you nothing. You need to get a 2 or a 12 in three turns or less.

P(2 or 12) = \frac{1}{18}, the probability of winning on your first try. Even though there are three states, we can still discuss wait time. In this context, it can be 0, 1, or 2. With a wait time of 1, P(2 or 12) = P(3, 4, 10, or 11)\times (\frac{1}{18})=(\frac{5}{18})\times(\frac{1}{18}) \approx 0.015432.

It means that to even make it to the second turn you can only get there with a 3, 4, 10, or 11. If you got 2 or 12 on the first try, there would be no need for a second turn. Similarly, to get to the third turn, you needed to survive twice and win the third time: (\frac{5}{18})^2\times(\frac{1}{18}) \approx 0.00428669.

It made sense, but I still wasn’t sure about this. What about the probability of losing completely? Those are the numbers from 5 to 9, which has a probability of \frac{2}{3}. Why wasn’t I making use of that information?

I don’t think it was necessary in computing the probabilities I did, since the winning conditions preclude rolling any sum between 5 and 9. But it can come in handy as a check. A good indicator that I am on the right track is to see if expectations of winning and losing for 1000 trials, add up to 1000. For winning, I need to add up the probabilities for all 3 wait times: \frac{1}{18} + \frac{5}{324}+\frac{25}{5832} = \frac{439}{5832}\approx 0.0752743. For 1000 games, the wait time of winning is: 75.2743 games.

The expectation of losing is similarly calculated, based on a single-turn probability of 2/3: \frac{2}{3} + \frac{2}{3}\times \frac{5}{18} + \frac{2}{3}\times \left(\frac{5}{18}\right)^2 = \frac{439}{486}\approx 0.9033. This means you will lose, on average 903 out of every 1000 games, or an expectation of 903.3. Notice that for 1000 games, the winning and losing conditions don’t add to 1000. What we didn’t add was survival until the third turn: \left(\frac{5}{18}\right)^3 = \frac{125}{5832}\approx 0.02143. This means that you will “survive” (but not win)21.43 out of every 1000 games. With enough decimal precision, we do indeed get 1000 games when we add all these numbers up, or at the very least add the expectation using the fractions: 1000 \times \left(\frac{439}{5832} + \frac{439}{486} + \frac{125}{5832}\right) = 1000 \times \left(\frac{439}{5832} + \frac{5268}{5832} + \frac{125}{5832}\right) = 1000.

2048 still unsolved, but I beat 16384 on my first try

Below, the obligatory screenshot to show what my board looked like well past the time of the win.

Winning at 16384 has now been declared “possible”, but it did take a long time. Note that, IMO, the board looks pretty sloppy if you know what a “good board” is supposed to look like. And I still won.

I won this game on my first attempt, played off and on over two days. Warning: This is one hell of a long, repetitive game.

The original game 2048, and other similar games, are from open source, and have been placed on GitHub. The Java program seems to run from a large number of different websites.  Some allow you to save and reload, and others don’t. Google Chrome has both 2048 and 16384 as an app that the user can run from the browser.

The original 2048 game, played on a 4×4 game board, is a much quicker game, but in my opinion, exponentially more difficult to win. I have been trying over the past 4 or so days, no luck. Some web sites allow you to save a favourable board in mid-play so that if you lose, you can pick up from that point later. Even with that feature, it would still take several tries to get past my first “1024” tile, saving several times, just in case luck runs against me early on.

Now that I have won the game, I don’t exactly feel that euphoric about it. There is an element of luck, and what strategy there is, is repetitive. The screen you see above would likely lose the game on 2048. But the strategy I used is supposed to work in both.

Strategy used. This strategy was influenced by a website blog article whose name escapes me, which suggested that one keeps all their high numbers in a contiguous group and avoid trapping “2”s and other low numbers inside of high numbers, the theory being that it will be difficult to combine the “2” with another tile, being so surrounded. On my screen, the two “4”s at the top of the board are vulnerable, and have been there for quite a while and are indeed hard to get rid of. The checkerboarding of 2s and 4s on the right side was also an emerging problem, as the checkerboarding prevents the tiles from being matched and combined.

The blog article suggests that to prevent isolated low tiles and checkerboarding, the player should sweep in one direction (say, left) repetitively until you can’t sweep anymore, then sweep in the opposite direction (right). This might work the first couple of times, but then you might find you missed some tile combinations by not sweeping up or down. But the general effect, if luck works with you, that the high numbers accumulate in the layers toward the edge, and the low numbers are away from the edge toward the center of the board, waiting to be added to new-coming tiles.

Ideally, you are supposed to have the highest tiles in one of the corners. The further away from the corner, the lower-value the tiles should be. You risk losing this if you do a 90-degree change in direction of your arrow keypresses (or sweeping gesture if you are on an android).

16384_pb
This game goes on, I think, as long as you want it to. This one, played off and on over 2 days with a nice-looking (but not great-looking) tile arrangement has a score of 1.5 million with no end in sight.

Many bloggers and video bloggers have said to go down and to the left until you get no more new tiles. Then, switch to down and right for a move, then down and left again. For a lengthy game like 16384, this is utterly tedious, and I believe it is in the tedium that mistakes are made. And it doesn’t take much to get the tiles all out of order.

Because randomness is involved in the value and placement of new tiles, every decision has risks involved, with the potential of making your tiles less than optimal.

An ideal strategy is demonstrated by an AI algorithm better than I can describe it, at: http://maartenbaert.github.io/2048/.  While this is done on a board for 2048, the strategy for 16384 would be the same, although, the large board means that mistakes are less fatal.

If you want to save key moments of the game for you to continue from later, this link gets you to the only version of the game I know of that can do that: http://www.2048tile.co/