Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
AC:NH turnip price calculator
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
// munged from https://github.com/simontime/Resead
namespace sead
{
class Random
{
public:
void init();
void init(uint32_t seed);
void init(uint32_t seed1, uint32_t seed2, uint32_t seed3, uint32_t seed4);
uint32_t getU32();
uint64_t getU64();
void getContext(uint32_t *seed1, uint32_t *seed2, uint32_t *seed3, uint32_t *seed4) const;
private:
uint32_t mContext[4];
};
void Random::init()
{
init(42069);
}
void Random::init(uint32_t seed)
{
mContext[0] = 0x6C078965 * (seed ^ (seed >> 30)) + 1;
mContext[1] = 0x6C078965 * (mContext[0] ^ (mContext[0] >> 30)) + 2;
mContext[2] = 0x6C078965 * (mContext[1] ^ (mContext[1] >> 30)) + 3;
mContext[3] = 0x6C078965 * (mContext[2] ^ (mContext[2] >> 30)) + 4;
}
void Random::init(uint32_t seed1, uint32_t seed2, uint32_t seed3, uint32_t seed4)
{
if ((seed1 | seed2 | seed3 | seed4) == 0) // seeds must not be all zero.
{
seed1 = 1;
seed2 = 0x6C078967;
seed3 = 0x714ACB41;
seed4 = 0x48077044;
}
mContext[0] = seed1;
mContext[1] = seed2;
mContext[2] = seed3;
mContext[3] = seed4;
}
uint32_t Random::getU32()
{
uint32_t n = mContext[0] ^ (mContext[0] << 11);
mContext[0] = mContext[1];
mContext[1] = mContext[2];
mContext[2] = mContext[3];
mContext[3] = n ^ (n >> 8) ^ mContext[3] ^ (mContext[3] >> 19);
return mContext[3];
}
uint64_t Random::getU64()
{
uint32_t n1 = mContext[0] ^ (mContext[0] << 11);
uint32_t n2 = mContext[1];
uint32_t n3 = n1 ^ (n1 >> 8) ^ mContext[3];
mContext[0] = mContext[2];
mContext[1] = mContext[3];
mContext[2] = n3 ^ (mContext[3] >> 19);
mContext[3] = n2 ^ (n2 << 11) ^ ((n2 ^ (n2 << 11)) >> 8) ^ mContext[2] ^ (n3 >> 19);
return ((uint64_t)mContext[2] << 32) | mContext[3];
}
void Random::getContext(uint32_t *seed1, uint32_t *seed2, uint32_t *seed3, uint32_t *seed4) const
{
*seed1 = mContext[0];
*seed2 = mContext[1];
*seed3 = mContext[2];
*seed4 = mContext[3];
}
} // namespace sead
uint32_t pf(float f) {
return *((uint32_t *)&f);
}
struct TurnipPrices
{
int32_t basePrice;
int32_t sellPrices[14];
uint32_t whatPattern;
int32_t tmp40;
void calculate();
// utility stuff for testing
sead::Random rng;
bool randbool()
{
return rng.getU32() & 0x80000000;
}
int randint(int min, int max)
{
return (((uint64_t)rng.getU32() * (uint64_t)(max - min + 1)) >> 32) + min;
}
float randfloat(float a, float b)
{
uint32_t val = 0x3F800000 | (rng.getU32() >> 9);
float fval = *(float *)(&val);
return a + ((fval - 1.0f) * (b - a));
}
int intceil(float val)
{
return (int)(val + 0.99999f);
}
};
void TurnipPrices::calculate()
{
basePrice = randint(90, 110);
int chance = randint(0, 99);
// select the next pattern
int nextPattern;
if (whatPattern >= 4)
{
nextPattern = 2;
}
else
{
switch (whatPattern)
{
case 0:
if (chance < 20)
{
nextPattern = 0;
}
else if (chance < 50)
{
nextPattern = 1;
}
else if (chance < 65)
{
nextPattern = 2;
}
else
{
nextPattern = 3;
}
break;
case 1:
if (chance < 50)
{
nextPattern = 0;
}
else if (chance < 55)
{
nextPattern = 1;
}
else if (chance < 75)
{
nextPattern = 2;
}
else
{
nextPattern = 3;
}
break;
case 2:
if (chance < 25)
{
nextPattern = 0;
}
else if (chance < 70)
{
nextPattern = 1;
}
else if (chance < 75)
{
nextPattern = 2;
}
else
{
nextPattern = 3;
}
break;
case 3:
if (chance < 45)
{
nextPattern = 0;
}
else if (chance < 70)
{
nextPattern = 1;
}
else if (chance < 85)
{
nextPattern = 2;
}
else
{
nextPattern = 3;
}
break;
}
}
whatPattern = nextPattern;
/*
if (checkGlobalFlag("FirstKabuBuy")) {
if (!checkGlobalFlag("FirstKabuPattern")) {
setGlobalFlag("FirstKabuPattern", true);
whatPattern = 3;
}
}
*/
for (int i = 2; i < 14; i++)
sellPrices[i] = 0;
sellPrices[0] = basePrice;
sellPrices[1] = basePrice;
int work;
int decPhaseLen1, decPhaseLen2, peakStart;
int hiPhaseLen1, hiPhaseLen2and3, hiPhaseLen3;
float rate;
switch (whatPattern)
{
case 0:
// PATTERN 0: high, decreasing, high, decreasing, high
work = 2;
decPhaseLen1 = randbool() ? 3 : 2;
decPhaseLen2 = 5 - decPhaseLen1;
hiPhaseLen1 = randint(0, 6);
hiPhaseLen2and3 = 7 - hiPhaseLen1;
hiPhaseLen3 = randint(0, hiPhaseLen2and3 - 1);
// high phase 1
for (int i = 0; i < hiPhaseLen1; i++)
{
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
}
// decreasing phase 1
rate = randfloat(0.8, 0.6);
for (int i = 0; i < decPhaseLen1; i++)
{
sellPrices[work++] = intceil(rate * basePrice);
rate -= 0.04;
rate -= randfloat(0, 0.06);
}
// high phase 2
for (int i = 0; i < (hiPhaseLen2and3 - hiPhaseLen3); i++)
{
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
}
// decreasing phase 2
rate = randfloat(0.8, 0.6);
for (int i = 0; i < decPhaseLen2; i++)
{
sellPrices[work++] = intceil(rate * basePrice);
rate -= 0.04;
rate -= randfloat(0, 0.06);
}
// high phase 3
for (int i = 0; i < hiPhaseLen3; i++)
{
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
}
break;
case 1:
// PATTERN 1: decreasing middle, high spike, random low
peakStart = randint(3, 9);
rate = randfloat(0.9, 0.85);
for (work = 2; work < peakStart; work++)
{
sellPrices[work] = intceil(rate * basePrice);
rate -= 0.03;
rate -= randfloat(0, 0.02);
}
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
sellPrices[work++] = intceil(randfloat(1.4, 2.0) * basePrice);
sellPrices[work++] = intceil(randfloat(2.0, 6.0) * basePrice);
sellPrices[work++] = intceil(randfloat(1.4, 2.0) * basePrice);
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
for (; work < 14; work++)
{
sellPrices[work] = intceil(randfloat(0.4, 0.9) * basePrice);
}
break;
case 2:
// PATTERN 2: consistently decreasing
rate = 0.9;
rate -= randfloat(0, 0.05);
for (work = 2; work < 14; work++)
{
sellPrices[work] = intceil(rate * basePrice);
rate -= 0.03;
rate -= randfloat(0, 0.02);
}
break;
case 3:
// PATTERN 3: decreasing, spike, decreasing
peakStart = randint(2, 9);
// decreasing phase before the peak
rate = randfloat(0.9, 0.4);
for (work = 2; work < peakStart; work++)
{
sellPrices[work] = intceil(rate * basePrice);
rate -= 0.03;
rate -= randfloat(0, 0.02);
}
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * (float)basePrice);
sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);
rate = randfloat(1.4, 2.0);
sellPrices[work++] = intceil(randfloat(1.4, rate) * basePrice) - 1;
sellPrices[work++] = intceil(rate * basePrice);
sellPrices[work++] = intceil(randfloat(1.4, rate) * basePrice) - 1;
// decreasing phase after the peak
if (work < 14)
{
rate = randfloat(0.9, 0.4);
for (; work < 14; work++)
{
sellPrices[work] = intceil(rate * basePrice);
rate -= 0.03;
rate -= randfloat(0, 0.02);
}
}
break;
}
sellPrices[0] = 0;
sellPrices[1] = 0;
}
int main(int argc, char **argv)
{
TurnipPrices turnips;
if (argc == 3)
{
turnips.whatPattern = atoi(argv[1]);
turnips.rng.init(atoi(argv[2]));
}
else
{
printf("Usage: %s <pattern> <seed>\n", argv[0]);
return 0;
}
turnips.calculate();
printf("Pattern %d:\n", turnips.whatPattern);
printf("Sun Mon Tue Wed Thu Fri Sat\n");
printf("%3d %3d %3d %3d %3d %3d %3d\n",
turnips.basePrice,
turnips.sellPrices[2], turnips.sellPrices[4], turnips.sellPrices[6],
turnips.sellPrices[8], turnips.sellPrices[10], turnips.sellPrices[12]);
printf(" %3d %3d %3d %3d %3d %3d\n",
turnips.sellPrices[3], turnips.sellPrices[5], turnips.sellPrices[7],
turnips.sellPrices[9], turnips.sellPrices[11], turnips.sellPrices[13]);
return 0;
}
@furmandev

This comment has been minimized.

Copy link

@furmandev furmandev commented Apr 1, 2020

Thanks for this!

Can you explain the input parameters a bit for me?

What are the possible values for pattern and seed and how are they determined by the game?

edit: I think I understand pattern, it can be 0, 1, 2, 3, and if the input is 4 or more its actual value is determined by chance?
edit2: actually, pattern is calculated by chance, unless input is 4 or more then it is 2.

@itsbluething

This comment has been minimized.

Copy link

@itsbluething itsbluething commented Apr 1, 2020

I'm guessing the whatPattern >= 4 case is there for sanity in case atoi has some weird input that converts to an int greater than three. nextPattern is calculated by chance based on the current pattern.

@jdharms

This comment has been minimized.

Copy link

@jdharms jdharms commented Apr 1, 2020

I'm trying to work out heuristics for recognizing each pattern in the wild. Ran across this one that's kind of curious:

brave:workspace jdharms$ ./sim 0 17
Pattern 3:
Sun  Mon  Tue  Wed  Thu  Fri  Sat
107   79   72   62  131  193   75
      76   67  148  175  191   69

Didn't realize from my first readthrough of the code that the "decreasing spike decreasing" pattern could have the first number in the "spike" be larger than the second number in the spike. The code that generates these is:

    sellPrices[work++] = intceil(randfloat(0.9, 1.4) * (float)basePrice);
    sellPrices[work++] = intceil(randfloat(0.9, 1.4) * basePrice);

rate in the first decreasing phase is capped at 0.9, so I think that the first price larger than the previous one marks the first item in the spike. You should sell on the fourth price of the spike.

What I haven't figured out quite yet are easy ways of recognizing when you're in which pattern. Preferably easier than doing floating point math using your buy price and first few sell prices, but that might not be possible.

@itsbluething

This comment has been minimized.

Copy link

@itsbluething itsbluething commented Apr 2, 2020

What I haven't figured out quite yet are easy ways of recognizing when you're in which pattern. Preferably easier than doing floating point math using your buy price and first few sell prices, but that might not be possible.

Totally spitballing here, but what if you normalize it on base price and do k-means on a size 12 vector of all the prices for the week? Definitely fits the problem space for some kind of regression or clustering alg.

@mikebryant

This comment has been minimized.

Copy link

@mikebryant mikebryant commented Apr 3, 2020

@jdharms I've actually built a predictor based on this code: https://mikebryant.github.io/ac-nh-turnip-prices/index.html
It just tries all possible combinations and prunes by whether your values match

@chengluyu

This comment has been minimized.

Copy link

@chengluyu chengluyu commented Apr 5, 2020

🥳 I just built a online version of this algorithm (not prediction): https://turnip-price.now.sh/

I also made it a npm package. Check out the project: https://github.com/chengluyu/turnip-price

@elxris

This comment has been minimized.

Copy link

@elxris elxris commented Apr 6, 2020

@mikebryant you inspired me to make this other calculator!
https://elxris.github.io/Turnip-Calculator/
@Treeki thanks for this! ❤️

@nanoNago

This comment has been minimized.

Copy link

@nanoNago nanoNago commented Apr 7, 2020

I made a python library for turnip prediction, in case that's still interesting to anyone even though there's website calculators up :)

https://gitlab.com/nanoNago/turnips

@orta

This comment has been minimized.

Copy link

@orta orta commented Apr 7, 2020

you all are doing great work! Thanks

@Neomania

This comment has been minimized.

Copy link

@Neomania Neomania commented Apr 7, 2020

Great work on this, thanks! I know a write-up is forthcoming, but I noticed that it seems the value of whatPattern at the beginning of calculate determines the probability of what nextPattern will be.

  • Does the whole whatPattern / nextPattern thing imply that the probability of your next pattern depends on the previous week's pattern? I haven't seen much discussion of this, but it sounds like something that would be pretty useful when predicting a strategy for the next week.
  • Since this probably wasn't initially a command-line program, I'm assuming you added on main for usage. Since whatPattern is initialized to argv[1], which is then used when selecting nextPattern, does this mean that the program doesn't generate prices for the pattern arg, and instead generates one for if the previous pattern was pattern (which could be any of 0, 1, 2, 3, depending on what RNG selects)?
@rafalexhawx

This comment has been minimized.

Copy link

@rafalexhawx rafalexhawx commented Apr 7, 2020

Alright I get the whole idea of pattern and seed but how do you get those values from your game?

@Vankog

This comment has been minimized.

Copy link

@Vankog Vankog commented Apr 8, 2020

Great work on this, thanks! I know a write-up is forthcoming, but I noticed that it seems the value of whatPattern at the beginning of calculate determines the probability of what nextPattern will be.

  • Does the whole whatPattern / nextPattern thing imply that the probability of your next pattern depends on the previous week's pattern? I haven't seen much discussion of this, but it sounds like something that would be pretty useful when predicting a strategy for the next week.

Yes, in previous installations of the game, the chance to have pattern x was determined by last weeks pattern. See for example the table in https://nookipedia.com/wiki/White_turnip#Price_patterns

It should definitely go into consideration for price predictions. But has only real consequences when calculating the chances for particular prices on each given day etc.

@jacob1

This comment has been minimized.

Copy link

@jacob1 jacob1 commented Apr 9, 2020

Tried writing a bruteforcer, but it seems like this code isn't a 100% exact representation of the actual game's code. It could be something to do with buying turnips my first week, although I think I bought on my island last week.

https://gist.github.com/jacob1/e13d220d174f390777bf8b747c3ac64d

Theoretically, if you input last week's pattern, this week's sell price, and as many buy prices as you can get, this should find your exact seed (trying all between 0 and UINT32_MAX). I ran it for two people though, and it wasn't able to find any matches. The third person I ran it for, there wasn't enough data to narrow it down to a seed.
So either I did something wrong, or there's possibly some missing rand() call throwing things off.

Edit: For anyone that wants to try bruteforcing, mine is significantly (at least 20x) faster than the one below, because it short circuits if the patterns don't match. I tested it and it produces the same results as mine. I'm still not confident in bruteforcers working, but it is lining up fairly nicely for my sister's prices this week, it couldn't predict anything else.

@smcvey

This comment has been minimized.

Copy link

@smcvey smcvey commented Apr 9, 2020

Brute forcer. https://gist.github.com/smcvey/6f9ef90c5947544050dad44e374a7fd5

I've taken Treeki's code and modified it. It will run through 0 to UINT32_MAX. Format to run it is:

./BruteForcer <base price> <monday am> <monday pm> <tuesday am> <tuesday pm> <wednesday am> <wednesday pm> <thursday am> <thursday pm> <friday am> <friday pm> <saturday am> <saturday pm>

If you don't know the price (or if it's the unknown ones at the end of the week), just put a 0. Arguments aren't optional and I'm not sure I can be bothered to make that possible.

It should list the prices, the pattern it suspects, and the seed. Reason I wrote it is to see if you get the same seed every week (and therefore, make a lot of money in the game).

More data you can put into the command line, the better, as these filter out possibilities. Takes a long time to run, I'm sure it can be improved.

@Edricus-Hub

This comment has been minimized.

Copy link

@Edricus-Hub Edricus-Hub commented Apr 9, 2020

Hi there. Thanks for posting this. I just wanted to link here a write up I did on this code on reddit for the community last week. Figured this might be a good place to put it for people coming here and future reference.

This is the reddit thread that contains the paper as well.

@mstksg

This comment has been minimized.

Copy link

@mstksg mstksg commented Apr 10, 2020

Wonder if it's worth making some sort of efficient trie structure to look up patterns. probably can't get around storing 4 billion values, but at least would make lookup very fast after the initial computation/memory cost.

@KevinMiller77

This comment has been minimized.

Copy link

@KevinMiller77 KevinMiller77 commented Apr 13, 2020

I'm currently making a mobile app that will have a feature incorporating this. The main purpose of it will really be just keeping track of your prices if you forget them by Thursday AM (like me). But hey, if you have that information why not project the best weekly price at the same time?

@erebusmaster

This comment has been minimized.

Copy link

@erebusmaster erebusmaster commented Apr 13, 2020

I can't tell without the rest of the code, but is the "FirstKabuBuy" flag set to true if one buys turnips on a friend's island? I know the price for the week is determined only by the base/sell price on the local island, but I'm wondering if someone who just bought turnips at a friend's island will set this flag to true and produce the first-buy "Small Spike" pattern. Not sure how that would interact with time-skipping if it does.

@Treeki

This comment has been minimized.

Copy link
Owner Author

@Treeki Treeki commented Apr 14, 2020

Since it wasn't clear from the original code, I should note a couple of things:

  • The seed input is mostly useful for the sake of simulating turnip prices and performing statistical analysis on the results - there is no way to determine what seed is used, as it gets re-generated from a hash over the savefile
  • There is an unknown amount of calls to sead::Random::getU32() performed in the process before the turnip code runs

Some of the other update processes pull a 32-bit value from the global RNG and then use it as a seed for a new context. On the other hand, turnip prices simply pull directly from the global RNG so it'll be harder to predict.

@erebusmaster No, that flag only gets set when you buy on your own island - this occurs inside the EventFlow script that handles Daisy Mae. The path taken when visiting is completely different and doesn't set the same flags.

@jacob1

This comment has been minimized.

Copy link

@jacob1 jacob1 commented Apr 14, 2020

If it pulls from global RNG, that's too bad ):

There could be thousands of RNG calls to that before it generates the turnip prices, and it probably varies every week. I guess bruteforcing is out the window then. The statistical analysis is great though. I've still been consulting this code and online tools to determine my patterns.

@jsettlem

This comment has been minimized.

Copy link

@jsettlem jsettlem commented Apr 14, 2020

Since it seems bruteforcing will be impractical that means I won't have reason to use this name, so I'll leave it here in the hopes someone can find it a better home:

Joan the Ripper

@jdharms

This comment has been minimized.

Copy link

@jdharms jdharms commented Apr 14, 2020

Not sure why you folks think it's not brute-forceable? There's only, what, 16 billion possibilities? The thing to do with this isn't to try to figure out your seed somehow and use that to predict prices, but to compare your week so far (Sunday buy price, all sell prices to-date) to the possibilities (all of them) and figure out where you week might go from there.

@smcvey's brute-forcer above looks great, and @elxris' tool posted above is what I've been personally using to chart out my town's possibilities based on current data.

@jsettlem

This comment has been minimized.

Copy link

@jsettlem jsettlem commented Apr 14, 2020

If I understand correctly:

The only reason it appeared bruteforceable was because this code inits the RNG, meaning you can bruteforce over all 2^32 possibilities for the seed, which is only about 4 billion. Now Ninji has clarified that that's not how the actual game code works. In actuality, the game seeds the RNG at some earlier point and calls it some unknown and likely variable number of times before getting to the turnip generation code. So you'd have to bruteforce over not just the seed, but the variable number of RNG calls, an order of magnitude more possibilities.

And to clarify, the two bruteforcers that have been posted don't work (at least with the numbers I've tried), and all other prediction tools are based on statistical analysis.

@jdharms

This comment has been minimized.

Copy link

@jdharms jdharms commented Apr 14, 2020

@jsettlem I'm not understanding your point. Even if the seed is randomized some number of times, it is still constrained to a uint32 value.

@jsettlem

This comment has been minimized.

Copy link

@jsettlem jsettlem commented Apr 14, 2020

@jdharms Read Ninji (@Treeki)'s comment again. He says:

Some of the other update processes pull a 32-bit value from the global RNG and then use it as a seed for a new context. On the other hand, turnip prices simply pull directly from the global RNG so it'll be harder to predict.

Other update processes reseed at the start of the process, so those could theoretically be bruteforced by just guessing random seeds. The turnip code just uses the current state of the global RNG, which is four uints (mContext in the code above). In actuality the entropy is probably considerably less than that, but it's still orders of magnitude more than 2^32.

@jdharms

This comment has been minimized.

Copy link

@jdharms jdharms commented Apr 14, 2020

@jsettlem I think I understand now, thank you for your patience. I wonder (idly) how many possibilities exist outside of the set produced by the 2^32 possibilities for the seed in this code.

I admit I hadn't taken the time to execute the bruteforcer posted above.

@jacob1

This comment has been minimized.

Copy link

@jacob1 jacob1 commented Apr 14, 2020

Although the rng is seeded at the start with a single 32 bit value, it uses that seed to generate 4 32 bit values. See the Random::init(uint32_t seed) function. These rotate around during each getU32() call, using the value we just ate to regenerate a new 4th 32 bit value. After hundreds of RNG calls, who knows what these 4 32 bit values are. There's so many combinations. (2^32^4, I think that's 2^128?).

But effectively if you know that there's somewhere between 500 and 600 getU32 calls before the turnip prices are generated, you could scan just 2^32 * 100 values, calling get32() between 500 and 600 times before running the code. So I did try modifying my bruteforcer last night to scan through all 2^32 values after calling getU32() a fixed number of times. I think it made it to 14 getU32() calls after each rng init before I killed it. This method is kind of outrageous and slow, who knows how many rng calls are made before generating turnip prices. The amount of getU32() calls probably varies each week, it would be almost entirely useless for predicting large spikes. There would be too many possibilities.

So basically, @jsettlem said it perfectly.

@jdharms

This comment has been minimized.

Copy link

@jdharms jdharms commented Apr 14, 2020

Yup, their final comment cleared it up for me. I had already forgotten the fact that the random context is 4 32 bit values.

@jsettlem

This comment has been minimized.

Copy link

@jsettlem jsettlem commented Apr 14, 2020

@jacob1 I actually tried the same thing. It's still running, but it gets slower over time as it has to do more and more calls. Currently up to 146, but I'm not expecting much from it.

I'm curious when the prices actually get generated, though, compared to when the RNG is initialized. Is it when you start the game on Sunday? I poked around the code a bit in Ghidra and the surrounding code seems to reference things like "FirstPlayAfterShopBuilt2Flag," which to me implies that that's the case, but this was just a cursory glance and I don't really know what I'm doing in that regard. Ninji's the expert here :)

Anyway, if that is the case, maybe that technique is possible? It would certainly be a slower bruteforce but if you could narrow the range of calls to within a few dozen or so you could potentially run the bruteforcer in a reasonable amount of time. I'm not hopeful, though. I imagine even if you could manage to bruteforce possible seeds, by the time you have enough information to narrow the seed possibilities down enough to be more informative than statistical analysis, it'll be too late in the week to make use of (if that makes sense; I think that's what you were saying, anyway).

It's also theoretically possible that there's some other angle of attack? I know people go to extraordinary lengths to do RNG manipulation in Pokemon. Perhaps there's some other system governed by the same RNG that could somehow be analyzed to help narrow down the RNG state? Just speculation, of course.

All this to say, I think for now the best approach to cornering the Stalk Market is going to be refining the statistical analysis methods.

@fxbri

This comment has been minimized.

Copy link

@fxbri fxbri commented Apr 18, 2020

Ist hier jemand wo deutsch kann? Ich würde das gerne brauchen aber versteh es leider nicht ganz... Kann es mir jemand erklären??

@Leanny

This comment has been minimized.

Copy link

@Leanny Leanny commented Apr 19, 2020

I dumped my prices after they were generated on boot and run the bruteforcer on it (I wrote a gpu version for it) and got to 3.5k getU32 calls before the procedure. Still no results unfortunately and now it takes quite some time for each further iteration... So maybe instead we can try to use something like z3 to deduce a seed state for us that result in the weekly turnip curve 🤔

@jsettlem

This comment has been minimized.

Copy link

@jsettlem jsettlem commented Apr 19, 2020

@Leanny It's also worth noting that running the code on a different platform may also lead to sightly different floating point behavior wrt things like rounding. I'm not sure how common floating point errors would be, but even running ninji's code vs the code I extracted using ghidra I ran into floating point mismatches (albeit about 1 in 10,000,000 times).

I was thinking of experimenting with running the turnip code in an arm emulator to see it if actually makes a difference but I've gotten sidetracked with other projects (and persona :D).

You should share your gpu implementation though, I'd love to play around with it.

@Leanny

This comment has been minimized.

Copy link

@Leanny Leanny commented Apr 19, 2020

@jsettlem Enjoy the probably worst piece of code you have ever seen :D I wrote it in c# using Alea.GPU. Requires Alea.3.0.4 and FSharp.Core.4.7.1 NuGet packages.

https://gist.github.com/Leanny/dfde4f885631c51318c7f145e45a7e83

Small comments:
The lib does not support working with external classes or struct, hence I unrolled everything with an regex find and replace... which is why the code looks the way it does

@Treeki

This comment has been minimized.

Copy link
Owner Author

@Treeki Treeki commented Apr 19, 2020

@Leanny It's also worth noting that running the code on a different platform may also lead to sightly different floating point behavior wrt things like rounding. I'm not sure how common floating point errors would be, but even running ninji's code vs the code I extracted using ghidra I ran into floating point mismatches (albeit about 1 in 10,000,000 times).

I was thinking of experimenting with running the turnip code in an arm emulator to see it if actually makes a difference but I've gotten sidetracked with other projects (and persona :D).

You should share your gpu implementation though, I'd love to play around with it.

I actually did this using Unicorn Engine, and comparing ~100k outputs between that and my own implementation got me a bunch of small rounding errors that I worked around by rearranging the way operations are performed, which is the reason for some of the weird constructs like subtracting a number and then subtracting a random factor afterwards rather than baking that base number into the random call.

That said, it's possible there could be variance across compilers too; I did this with the stock clang 11.0.0 on OS X 10.14

@melondonkey

This comment has been minimized.

Copy link

@melondonkey melondonkey commented Apr 29, 2020

dumb question not a c++ programmer -- does randfloat() here return a random float between the two arguments or does it return one of the two arguments randomly?

@jvstech

This comment has been minimized.

Copy link

@jvstech jvstech commented Apr 30, 2020

@melondonkey It returns a value between the two arguments.

@waterworld8

This comment has been minimized.

Copy link

@waterworld8 waterworld8 commented Apr 30, 2020

Hi there. Let me contribute from a probability perspective. I found it interesting to analyze the probabilistic statements from lines 327--329 of Pattern 3. I derived

  1. The probability distribution of the price of the 2nd best session (I saw a similar result in the source code of https://turnipprophet.io/), and
  2. The posterior distribution of the price of the best session given the observed price of the 2nd best session.
    Qualitatively, both results tell us that we are more likely to end up with a lower rate.

I've given closed-form expressions of the distributions and their (conditional) expectations. I also provided figures so that it's easier for readers to get intuitions behind. The figures related to result 2 can help get a feeling of what you will get if you have observed the price of the 2nd best session of Pattern 3. (I use Excel to record numbers and to preprocess the data before the figures can be used.)

The results and figures are put in the form of a homework assignment to (hopefully) give my students some fun. Please ignore the HW aspect and directly look for the results and figures:
https://people.engr.ncsu.edu/cwong9/ece792-41_20Fall/homework/hw0.pdf

Cheers!

@TACIXAT

This comment has been minimized.

Copy link

@TACIXAT TACIXAT commented May 3, 2020

Is context unique to turnips or is it used as a global RNG state?

@TACIXAT

This comment has been minimized.

Copy link

@TACIXAT TACIXAT commented May 3, 2020

Started writing a solver for the state, haven't looked to see if this will even be possible (since we're only getting a few bits per week). I'll look at the calculate function more later in the week, writing the implies, etc. If someone else wants to grab it, feel free. Some reference code here if you're not so familiar with z3.

from z3 import *

# Implemented from https://gist.github.com/Treeki/85be14d297c80c8b3c0a76375743325b
# @cyberingcc

ctx1, ctx2, ctx3, ctx4 = BitVecs('ctx1 ctx2 ctx3 ctx4', 32)
context = [
	ctx1,
	ctx2,
	ctx3,
	ctx4,
]

tmpcnt = 0

def sym_u32(context):
	n = context[0] ^ (context[0] << 11)
	context[0] = context[1]
	context[1] = context[2]
	context[2] = context[3]
	context[3] = n ^ LShR(n, 8) ^ context[3] ^ LShR(context[3], 19)
	return context[3]

def sym_rand_bool(context):
	return sym_u32 & 0x80000000

def sym_rand_int(context, low, high):
	tmp = Bitvecs('tmp{}'.format(tmpcnt), 64)
	tmpcnt += 1
	tmp *= 0
	rand = sym_u32(context)
	tmp |= rand
	return  LShR(tmp * (high - low + 1), 32) + low

def sym_rand_float(context, af, bf):
	val = 0x3F800000 | LShR(sym_u32(context), 9)
	fval = fpBVToFP(val, Float32())
	# https://z3prover.github.io/api/html/namespacez3py.html
	# TODO: check RNE vs RNA in docs
	rm = RNE()
	return fpAdd(rm, a, fpMul(rm, fpSub(rm, fval, 1.0), b-a))

def sym_calc(context):
	base = sym_rand_int(context, 90, 110)
	chance = sym_rand_int(0, 99)
	# TODO: the rest of the fucking owl
@shawenyao

This comment has been minimized.

Copy link

@shawenyao shawenyao commented May 4, 2020

Thanks Treeki for the script! I am using it in my turnip portfolio analysis. If anyone is looking for a simple strategy that delivers the highest expected return, Wed a.m. seems to be best time to sell.

https://www.shawenyao.com/Modern-Portfolio-Theory-a-Case-Study-on-Turnips/

@Zathki

This comment has been minimized.

Copy link

@Zathki Zathki commented May 5, 2020

Thanks so much Treeki and Edricus! I took my own stab at a high level price prediction app based on your data and analysis. https://nookdb.io/stalks

@lsapan

This comment has been minimized.

Copy link

@lsapan lsapan commented May 5, 2020

Thanks so much for everyone's hard work on this! It has been instrumental for stalks.io.

On that note, stalks.io has amassed a pretty large dataset of real in-game weeks that could potentially be useful for further research. I'm happy to anonymize it and send it to any folks that are interested! 😄

@melondonkey

This comment has been minimized.

Copy link

@melondonkey melondonkey commented May 6, 2020

@lsapan Although stalks.io is my favorite site for turnips, I don't think the odds calculations are correct. I am in decreasing mode now. I ran a full monte carlo inference based on the code above (I'll try to post an gist in R later) and there is a ~50% probability I'm in decreasing pattern conditioning on my current data points. However, stalks.io shows me as 71% to get 200 bells which is clearly not right. Are you conditioning your odds on the chance that the person is the pattern?

@lsapan

This comment has been minimized.

Copy link

@lsapan lsapan commented May 6, 2020

@melondonkey Thanks for looking into it! I am factoring in the likelihood of each pattern, but to be honest it's quite possible there's something else going on with the odds calculation. I'm planning to make the predictions/odds aspect open source soon, and it'd be awesome if you could give it a look over once it is!

@shawenyao

This comment has been minimized.

Copy link

@shawenyao shawenyao commented May 8, 2020

Thanks Treeki for the script! I am using it in my turnip portfolio analysis. If anyone is looking for a simple strategy that delivers the highest expected return, Wed a.m. seems to be best time to sell.

https://www.shawenyao.com/Modern-Portfolio-Theory-a-Case-Study-on-Turnips/

Apart from above, I also want to add that any turnip price beyond 660 bells is simply impossible based on what we know so far, which falsifies a few circulating screenshots that suggest it can go as high as 999 bells.

@jayfinx

This comment has been minimized.

Copy link

@jayfinx jayfinx commented May 9, 2020

On that note, stalks.io has amassed a pretty large dataset of real in-game weeks that could potentially be useful for further research. I'm happy to anonymize it and send it to any folks that are interested! 😄

@lsapan, I'd love to use the anonymized data! This would be a fun thing to bring in to my classes (I teach programming for finance majors)... would be cool to show students what user trading behavior looks like in a controlled environment when the distribution of risk is known ex ante.

@yamatchan

This comment has been minimized.

Copy link

@yamatchan yamatchan commented May 9, 2020

Hi.
Your source code is great.
I created a turnip price prediction tool based on your code.
I am very grateful.
Thank you.

https://doumori-tool.net/

@terenceodonoghue

This comment has been minimized.

Copy link

@terenceodonoghue terenceodonoghue commented May 10, 2020

@lsapan likewise here, I'd love get the anonymised data as well, if you're willing. I've been gathering data of my own to try it out in a machine learning project, but it's slow going obviously. 😁

@jacob1

This comment has been minimized.

Copy link

@jacob1 jacob1 commented May 11, 2020

Instead of getting anonymized data, you could just run the code here for tens of thousands of rng seeds and get a more accurate sample of the possibilities.

@nikukyugamer

This comment has been minimized.

Copy link

@nikukyugamer nikukyugamer commented May 15, 2020

@yamatchan
Awesome.

@trickytank

This comment has been minimized.

Copy link

@trickytank trickytank commented May 21, 2020

I had assumed that basePrice is what Daisy Mae sells at. Is that correct? I have somebody claiming they haven't had a Sunday under 130 for their first 3 weeks of the game, but the above limits this from 90 to 110 bells.

@jacob1

This comment has been minimized.

Copy link

@jacob1 jacob1 commented May 21, 2020

That isn't possible. It's always between 90 and 110 (my own experiences also confirm this)

@Denimbeard

This comment has been minimized.

Copy link

@Denimbeard Denimbeard commented May 24, 2020

Question: how hard would it be to estimate how much money Daisy Mae would take home every Sunday, all islands combined?

@shawenyao

This comment has been minimized.

Copy link

@shawenyao shawenyao commented May 24, 2020

Question: how hard would it be to estimate how much money Daisy Mae would take home every Sunday, all islands combined?

Good question. This can be further decomposed into 1) how many players are actively investing in turnips every Sunday; 2) how many turnips each player buys per week; 3) what the purchase price is. The global sales of the game so far (13.41 million) should give us some sense of the upper bound for 1) and we have a very good idea of what 3) is given the work done here (uniform between 90 and 110). That said, I am having a hard time estimating 2), not to mention the correlation among all 3 factors.

@lsapan

This comment has been minimized.

Copy link

@lsapan lsapan commented May 24, 2020

As @shawenyao pointed out, it’s really a question of buyer behavior. Thankfully, I have some insights from stalks.io that may help:

From the data I have, ruling out insane outliers, each player purchases around 5,267.48 turnips per week. The average buy price for those turnips is 97.90 bells (bear in mind that factors in that many folks buy from cheaper islands).

That fills in data points #2 and #3 from above, which just leaves determining what percentage of the active player base purchases turnips a week!

@nonopolarity

This comment has been minimized.

Copy link

@nonopolarity nonopolarity commented Jun 6, 2020

How is the code obtained? It doesn't look like it is dis-assembled from machine code and then back into C++...

That's because there are meaningful variable names such as hiPhaseLen1

It seems somehow there is source code leak?

@jdharms

This comment has been minimized.

Copy link

@jdharms jdharms commented Jun 6, 2020

@Joapfel

This comment has been minimized.

Copy link

@Joapfel Joapfel commented Jul 3, 2020

I made a python library for turnip prediction, in case that's still interesting to anyone even though there's website calculators up :)

https://gitlab.com/nanoNago/turnips

Are you interested in releasing a pip package ? I also opened an issue on your GitLab project in regards to that idea with some more details :)

@nonopolarity

This comment has been minimized.

Copy link

@nonopolarity nonopolarity commented Aug 25, 2020

In the old days, having the INPUT and the OUTPUT specified was very important. That's like the Interface. As with API or the interface of OOP, we know they are very important.

In this case, the OUTPUT is ok... it is just some text. But for the input, we are having people guessing what they are, and then with some edit and then you can read the other 50 comments to find out more... and then we can also read the code to find whatPattern can be 0 to 3 and when it is 4 or greater (4, 5, 6, 7, ...), then nextPattern becomes 2... and the switch statement doesn't get executed, so it looks like what matters is nextPattern only, as the switch statement sets it and seem to be the main purpose. And the next line is whatPattern = nextPattern so it does look like what really matters is 0 to 3 only. Line 233 and on, it only checks for values between 0 and 3.

Actually, from https://turnipprophet.io/index.html it seems "last week's pattern" matters, and I think this is what the initial whatPattern is about... the code generates a nextPattern which is the pattern for the upcoming week. So Line 233 is the real material, and then for the high spike, Line 281 and on is the real deal.

I have a junior coworker hacking out code every day, not knowing exactly what is happening, day after day. And the manager doesn't know what is going on much either. And the funny thing is, when the manager sees the junior coworker typing in line after line, command after command what the manager doesn't understands, he poses himself as the judge and offers, "What you are doing is GOOD work".

But if somebody understand things very clearly, explains to the manager exactly what is going on and simple and easy to understand, now the manager thinks the work should be done in 20 minutes. (because he can understand it). And so the choice next time would be to present something to the manager so that he doesn't understand.

And I think the manager thinks that coworker is worth his salary and worth his respect, because he is doing things that the manager cannot understand. And so that coworker is indispensable. And if you present thing in a simple and easy to understand way to the manager, the manager thinks you are not worth the salary and not worth his respect, because he can understand exactly what you are doing and he can do it himself and you can be gone the next day.

And the manager himself doesn't write any docs or specs down either. I suppose because now he is the docs. He cannot be easily fired. He can even use abusive behavior at work and since he cannot be easily fired, he can keep doing it. Are we doing software engineering or are we doing "I cannot be easily fired"?

And people do things they don't understand. Our testing platform with Gerrit is randomly failing. Run the test and one hour later, it says it is failing and so you try again, and it fails and you try again, and the third time it finally succeeds. Nobody knows what's happening. Sometimes they do but the explanation is because of this and that and this and that, so they tell you just to keep trying. We have a team of SRE hacking things every day, and we have to find what is going on, what might be breaking what, in a jungle of Slack messages, some might be 5 days old, some might be 4 months old.

Anyway... at least, say what the INPUT is. Add some comments. But for the above code, the pattern on the command line doesn't really matter a whole lot, as a new pattern is generated anyway... the comment could have said line 233 is really the "meat" of the program.

Programs must be written for people to read, and only incidentally for machines to execute. - Harold Abelson, Structure and Interpretation of Computer Programs

@jdharms

This comment has been minimized.

Copy link

@jdharms jdharms commented Aug 25, 2020

Excuse me sir, this is a Wendy's.

@nonopolarity

This comment has been minimized.

Copy link

@nonopolarity nonopolarity commented Aug 25, 2020

The surprising thing is, you can go into a Fortune 500 or Fortune 50 tech company, and it is still a Wendy's.

@nonopolarity

This comment has been minimized.

Copy link

@nonopolarity nonopolarity commented Aug 25, 2020

whatever pattern you give to the program, it still may get changed to a different pattern due to random number (according to the seed) (line 129), and if the final pattern is a 1, that is the high spike pattern. See line 233.

Example:

$  ./a.out 0 326
Pattern 1:
Sun  Mon  Tue  Wed  Thu  Fri  Sat
110   96  137  660  152   65   82
      91  200  180   91   63   80

$  ./a.out 0 291879
Pattern 1:
Sun  Mon  Tue  Wed  Thu  Fri  Sat
110   99  181  186   50   75   68
     106  660  120   86   60   55

For folks not familiar with the following C++ code:

  int randint(int min, int max)
  {
    return (((uint64_t)rng.getU32() * (uint64_t)(max - min + 1)) >> 32) + min;
  }
  float randfloat(float a, float b)
  {
    uint32_t val = 0x3F800000 | (rng.getU32() >> 9);
    float fval = *(float *)(&val);
    return a + ((fval - 1.0f) * (b - a));
  }

note that randint(a, b) returns something inclusive of a and b, and randfloat(a, b) returns something inclusive of a but exclusive of b.

You will see code which is randfloat(0.9, 0.85), and it is almost the same as randfloat(0.85, 0.9), except the first case is exclusive 0.85, while is second case is exclusive 0.9.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.