Informática geek, matemáticas, pensamiento crítico y alguna otra cosa de vez en cuando.

2015-02-23

Tangerine Tycoon - Fulliverse

Tangerine Tycoon is an online Flash game written by Gaz Thomas, where you start by clicking on a tangerine to earn one tangerine per click, and then you can purchase buildings to earn them at a certain rate, given by the number of buildings that you have of each kind. There are four sources of income (tangerines), not counting the "running start" perk: clicking on the tangerine, the buildings, the stock market, and gambling. After you buy at least one of each building, you're given the opportunity to jump to another universe, starting again from zero (but with an increased tangerines-per-second rate for the buildings) in order to score more achievements. It's similar to a bunch of games of the genre, and with a touch of humour. In my case, it was the first I've played through. The current version as of this writing is 1.26. The present analysis is based on that version.

If you haven't played it, but plan to, better stop reading now, as this post contains spoilers. You can always get back to this post later.

The achievements screen has 100 entries that you can unlock as you progress, each adding 1% to your current TpS. Some of them are much harder than others. There is one that is really, really hard to get. The title is "The Fulliverse", and the legend reads: "The universe can not hold any more tangerines". It's unlocked when you reach 10300 tangerines. That's close to the limit of a 64-bit float, which is about 1.797E+308 (hey, that's a float notation that the game lacks! I hope that's fixed in a later version). The author imposed a limit slightly below that, to avoid having infinite tangerines and being able to buy everything unlimitedly, I presume. With that limit, there's the paradox that some buildings can't be bought; for example, when the number of mutants is between 7055 and 7253, you'll see the price of each between 1.060E+300 and 1.663E+308. Mutants aren't the best example, I know, as you wouldn't buy them anyway, but it's one that you can easily see. At 7254 and above, the price of mutants is displayed as Infinity (the float overflows).

I'm not going into an analysis of the optimal number of buildings; there is already one except it doesn't specify the optimal strategy about the cat. The base TpS for a cat are 400. The actual TpS (for all, not just the cat) is the base TpS times the percentage resulting from the sum of all the bonuses plus 100 (universe + perks + achievements + 100). You need at least 3 machines to unlock the cat. If you're after all achievements, in the first universes it's always faster to unlock it, and get the achievement corresponding to not unlocking it at a later universe. In that case, you buy 3 machines, letting one of them break, then 5 cats. The time for the cat to appear is random.

When you have all the Improved Efficiency perks, it's usually faster to buy 18 tangerine machines and aim for the lab, skipping the cat, as unlocking it will happen too late most of the times. I often get my first tangerine lab even before the machine explodes. Since I have the Running Start perk maximized, however, I still unlock it, so it doesn't disturb in the next universe and I can get started faster, improving my times screen. My current best for 50K is 0:14.

As your TpS rate increases, the strategy towards the Mutants needs to be changed. Your tangerines grow quadratically when you buy the first Mutant (actually it's faster than quadratic until they reach a spawn rate 14, but that doesn't make a significant difference), but that's too slow when your TpS multiplier is high, and it's faster to get 12 ETs and buy a mutant when available, and from there, increase the heroics up to 25 and wait for the first 5D to be available. That's always assuming you don't use anything else than the main (buildings) screen.

The Tangerine Exchange

One of the greatest features of the game is the stock market. There are five commodities all with the same behaviour. You can buy and sell. When you buy, you have to spend either all your tangerines, or half your tangerines; when you sell, you always sell all the stock you have of that commodity. Their prices range between 10 and 100. Each commodity has a trend, which can be increasing or decreasing. When it is increasing, the next price is given by an increment which is a uniformly distributed random number between –3 and +5, and when it is decreasing, it is incremented by a random number between –5 and +3. The expected value of the price of a commodity with an increasing trend is thus the previous price + 1 on each market tick (ticks happen every 5.5 seconds more or less), and the previous price – 1 if the trend is decreasing. When the trend is increasing and the price is above 80 (that is, 81 or higher), it keeps the same trend for one more tick and then reverses; the same happens when it's decreasing and the price is below 30 (29 or lower). Due to random fluctuation, it can actually go down to 10 even when the trend is increasing, or up to 100 even when the trend is decreasing. The Insider Trading perks reveal the trends, one for each commodity, but you can also figure it out by watching the increments or decrements of the price: if it increases by 4 or 5, the trend is increasing, and if it decreases by 4 or 5, the trend is decreasing. That happens every 4.5 ticks on average.

The following PHP program demonstrates the behaviour of the Tangerine Exchange (the signs indicate the trend, they do not apply to the value):

<?php

function MarketTick(&$prices, &$trends)
{
    for ($i = 0; $i < 5; $i++)
    {
        $trend = $trends[$i];
        if ($trend < 0 && $prices[$i] < 30)
            $trends[$i] = 1;
        else if ($trend > 0 && $prices[$i] > 80)
            $trends[$i] = -1;

        do
        {
            $newprice = $prices[$i] + $trend + mt_rand(-4, 4);
        }
        while ($newprice < 10 || $newprice > 100);
        $prices[$i] = $newprice;
    }
}

$prices = array();
$trends = array();
for ($i = 0; $i < 5; $i++)
{
    $prices[$i] = mt_rand(30, 80);
    $trends[$i] = mt_rand(0, 1) * 2 - 1;
}

do
{
    $oldtrends = $trends;
    MarketTick($prices, $trends);
    for ($i = 0; $i < 5; ++$i)
        printf(" %+4d", $prices[$i] * $oldtrends[$i]);
    echo "\n";
    usleep(5500000);
}
while (true);

Trading at low prices has the advantage that the increments imply a higher percentage than at high prices; for example, an increase from 10 to 11 is a 10% gain (if you bought at 10), but from 99 to 100 it's about 1% gain (if you bought at 99). Buying at above 80 is not recommended because there's no guarantee that you will sell above that price without at least one full decrease-increase round. 80 itself is still safe, assuming it was never above 80 for this run.

Gambling

Trading is helpful, especially at the beginning, but for reaching a Fulliverse achievement, it's too slow. Buying at 25 (a safe-ish price without missing that train) and going up to 50 then repeating, assuming there's another commodity immediately available at 25, would take you an average of more than two minutes, to just duplicate your gains. That's about 7 minutes to multiply your gains by 10. You can be lucky at times and grab a faster train (e.g. 16 happens relatively often) to triplicate or even quadruplicate your gains, but that doesn't happen often enough as to be significant. Fortunately, it's possible to go faster than that by gambling.

Gambling is a double-or-nothing game: you either lose all you have, or get double of what you have. With 50% probability, the expected value of every game is to stay as you are; however, for a repeated game the probability of losing everything increases exponentially as you play, so the strategy of just playing repeatedly obviously leads nowhere, unless the probability of losing once is less than the probability of winning 1000 times in a row, which obviously doesn't happen with this game's limits.

You can increase your chance of winning in two ways: by buying it from the gambling screen (you can buy up to 15 increases; each costs 10x the previous and adds 1% to your chances), and by perks (each perk adds 1%, up to 10 times). At the maximum, the chance of winning is 75%.

How to gamble without losing everything? This part gets tricky. The trick is to use the "Purchase Volume: 50%" feature in the Tangerine Exchange so that you don't lose all you have, using it as a kind of bank. The Insider Trading perks help here, as you can use trending info to ensure that your investment will not result in a loss in average.

There is a possibility of using martingale as a strategy, betting the base amount after each win and using the stock market to double your bet on each loss, as described in the same post linked before. That's a poor strategy in this case, as it only grows your gains linearly, barely taking advantage of the increased win rate, and making it exponentially slow to double your tangerines.

Here's a better strategy. Choose a commodity with an increasing trend, and buy 50%. Go to the Gambling screen, and play. Whatever the outcome, go back to the market, and sell. Rinse, repeat. With careful timing, it's even possible to do it without the value changing, by waiting for the tick to happen between selling and buying, enabling us to use the strategy without caring about the trend.

The analysis of this strategy turns out to be somewhat difficult. At first I did a mistake calculating it. First, if your initial amount of tangerines is n, you invest n/2 in the Exchange, and gamble the other n/2 for double or nothing. Thus if you lose and sell your stock (disregarding gains or loses coming from the stock market), you end up with n/2; and if you win and immediately sell your stock, you end up with 2·(n/2)+n/2 = 1.5·n tangerines. The expected value for every game when the chance of winning is p is therefore p·1.5·n+(1–p)·0.5·n = n·(p+0.5). Therefore, the expected value for a 75% win probability is n·1.25, so our gains will be multiplied by 1.25 after every game, right?

Wrong! It's not so easy. With 75% probability, the win rate is 3 out of 4, so if your gains get multiplied by 1.5 when you win and by 0.5 when you lose, after 4 games your gains will be on average multiplied by 1.5·1.5·1.5·0.5 = 1.6875. That's not the same as 1.25·1.25·1.25·1.25 = 2.44140625 which would be the result if we followed the other reasoning. The actual average multiplier per game for a probability of winning p is 1.5 p·0.51–p, which for p = 0.75 equals 1.1397535 approximately.

With that in hand, we can calculate the minimum percentage at which to try this strategy. Note that, against intuition, it doesn't work for p = 0.5. The expected multiplier for each game with a 50% chance of winning is approximately 0.866025 (it's exactly 0.750.5), therefore you end up losing more than 13% per game on average. Starting with a 64% winning chance, things get better. For 64%, the expected multiplier is approximately 1.01, so you win 1% on average. With 63% or less, you always lose something. I wouldn't risk on a 1% winning probability, though. It would take a huge amount of bets for that 1% to be noticeable. It takes about 231 attempts on average to just double your gains; in the short term, bad streaks can ruin you.

So, for a 75% winning chance, which is the maximum, what is the expected number of games needed to multiply your savings by 10? That's obtained by solving for x in 1.1397535...x = 10, whose solution is x = log(10)/log(1.1397535...) which is approximately equal to 17.6. And to double them? The expected number of games is then slightly less than 5.3. If you time your games with the Exchange ticks as described above, then the time it takes to double your gains is almost 5 times faster when compared to the winnings that you would get using the Exchange alone in the optimistic scenario explained earlier.

Is it possible to do better than that? That's not easy to answer, but I think so. A different strategy is to gamble twice in a row each time, before selling your stock and buying again. At first sight it may seem to not make a significant difference, but once we make the calculations, reality tells us otherwise.

The probability of winning twice in a row for a winning probability of p is p². For p = 0.75 that probability is 0.75² = 0.5625, so more often than not you win twice in a row. Each time you lose you still get n/2 because your other half is safe during both games. But if you win both games, your total after selling your stock is 2·2·(n/2)+n/2 = 2.5·n.

So what's the expected multiplier after each pair of games? In this case, it's 2.5 ·0.51–, which for p = 0.75 equals 1.23635 approximately. Is that clearly better, or are the gains negligible with respect to the previous method? The answer seems to lie somewhere in between. The number of attempts it takes to double your gains is 3.26, which is more than half the 5.3 times it took with the previous method. And since it takes two gambles every time, it takes longer to play, but switching back and forth to the market also adds a constant time independent of how many times you gamble, reducing the relative importance of the increased number of games. So, does one thing compensate the other? I think it feels faster, but that's a personal appreciation and not based on quantitative data, which was too difficult to gather for me. The minimum percentage to make this system return gains raises to 66%.

Note that when you lose the first of the two gambles, you don't need to play the second. That's a timing advantage. Does that introduce bias? I don't think so, but I haven't really thought it through. Also, with this method you can forget about coordinating it with the Exchange ticks, because there isn't enough time. You need to use a commodity with an increasing trend, and hope for some luck. That's kind of a timing advantage too, because coordinating it takes time (to wait for the expected tick). Choosing an increasing trend is important, and more so when losing at gambling. After a win, the market percentage is applied over the n/2 that was invested in the Exchange; the n from the gambling is not affected, therefore the percentage affects only 1/5 of your final tangerines. But when you lose, it affects the total you have remaining. For example, after a decrease in a commodity price from 30 to 27, if you lose that's a 10% decrease, but if you win the overall loss is only 2%. I only waited for the price to raise again when I lost and the Exchange price was low.

And what about a strategy of gambling three times in a row, then? Let's see. The multiplier per win is 4.5·n, and per loss it's the usual n/2. The chance of winning three times in a row is p³, which equals 0.421875 when p = 0.75. The average multiplier for that p is 4.5 p³·0.51–p³ = 4.50.421875·0.50.578125 ≅ 1.2634. That takes about 2.96 cycles to double your gains, and 9.85 to multiply them by a factor of ten. I say negligible when compared to the 10.85 it takes with the two in a row method, considering you have to gamble once more, which also takes its time. The minimum percentage for it to start to be profitable is 69%.

And with a strategy of four times in a row? With the game's limit of 75%, it's not worth it. The gains per cycle for 75% are about 1.2254, which is lower than with the two in a row method. It starts to be profitable at 71%.

So I stuck with the twice in a row strategy to reach that achievement. How many cycles does it take? For a starting point of 1E+75 (reasonable when the Upgod perk is maximized), you need to multiply your gains by 1E+300/1E+75 = 1E+225. Solving for x in 1.23635...x = 1E+225 gives us an average number of trials x of approximately 2441. So it's still a long trip. My current best for 1E+100 is 30:14 (of them, 6:29 were used to get to the 5D's).

But it was fun. The best of it was to figure out all this, of course. I noticed my mistake by running the following simple program. I expected the result to be around 3096 (since 1.253096 equals 1.07E+300), but it was actually above 5000 most often, and never less than 4700. The actual expected number of games with the first strategy and a starting amount of 1 is about 5281, and unsurprisingly, the program output is around that.

<?php

$count = 0;

$money = 1;
do
{
    if (mt_rand(0, 99) < 75)
        $money *= 1.5;
    else
        $money *= 0.5;

    $count++;
}
while ($money < 1e300);

echo "It took $count attempts to reach the goal.\n";

What other strategies are there? Well, I haven't done the math, but there are some more that come to mind. One is to invest 50% in one commodity, and 50% of the remainder in another, so the total invested is 75% and you only gamble 25%. You can then choose how many times to gamble as above. Another more risky one is to do the same, but then sell the 50% one before gambling. Then you're gambling 75% and keeping 25% safe. And there are other possible strategies that don't involve selling the previous stock when you win, but to buy from a different stock, possibly selling the previous one afterwards. I'd like to know if someone does an analysis of them and finds one that gives better results than the ones presented here, or if someone presents some other strategy.

Acknowledgements

I am grateful to Otto Nyberg for pointing out where my error was and leading me in the right direction.

No comments: