Facebook’s Farmville: What’s the Fastest Way to Get Rich?

One can’t help but notice that a lot of people have been playing Farmville on Facebook lately. Some of my relatives, friends, students and co-workers have taken the plunge. I don’t have time to play Farmville, but I thought it would be interesting to study it. It’s a simple and fun game, easy to explain, and apparently addictive.

You begin the game with a 12 by 12 piece of land. That gives you 144 one by one squares in which to plant crops. To simplify the explanation, I’m going to (1) restrict my attention to the four crops initially available (strawberries, eggplant, wheat, and soybeans); (2) assume crops will be harvested as soon as they are ripe (that is, ignore wilting); (3) disregard the random bonuses and gifts that show up every now and then. Blogger Mark Newheiser has a nice post about Farmville in which he includes a useful table. The cost column includes the cost of plowing the land (15 coins) plus the cost of purchasing the seeds. Because the harvest times of all four crops are multiples of four hours, we can think in terms of 4-hour periods.

Question: What’s the largest amount of cash one can obtain in 6 days? (need to rest on the 7th day).

You initially have 200 coins, one ripe and one half-grown square of strawberries, one ripe and one half-grown square of eggplant. By harvesting the two ripe squares, your fortune grows to 323 coins. I’ll also go ahead and clean (delete) the two half-grown squares so that we can begin with a clean slate. It turns out that the answer to the above question is to plant strawberries only, and as much as you can. Here’s the planting schedule:

Period Strawberry Squares
0 12
1 17
2 24
3 34
4 47
5 66
6 92
7 129

At period 8 (after 32 hours), you’ll have enough money to fill all your 144 squares with strawberries and you just continue to plow, plant and harvest them all every 4 hours. After 6 days (36 four-hour periods), you’ll have 44,913 coins (adjusted to take into account that 4 squares were already plowed at time zero). This solution is not very exciting and, moreover, easy to predict. Taking a second look at the cost table, we can see that the profit per hour of strawberries, eggplant, wheat, and soybeans are 2.5, 1, 0.903, and 1.375, respectively. This fact, combined with the fact that strawberries are the fastest to grow, yields the above result. As one progresses through the game, other crops become available and strawberries’ dominance goes away. However, we can show that things can get very complicated by changing the numbers a little bit. If we increase the cost of strawberries to 31 (including plowing), their profit per hour changes to 1 (worse than soybeans). Here’s the new optimal planting schedule for 6 days, which yields a profit of 15,725 coins:

Period Strawberry Squares Soybean Squares
0 2 8
1 3
6 1 15
7 7 1
8 6 2
9 7
12 5 26
13 8
14 13
15 29
16 25 8
17 2 27
18 57
22 16
23 75
24 69
29 16 59
30 85
35 59

Note that the best course of action now is to mix strawberries and soybeans and, at least to me, the proper way of doing it isn’t so obvious (hence the value of using Operations Research). If you’re now wondering whether there would be a situation in which the best idea is to use three different crops, the answer is yes! If we decrease the cost of eggplant to 19 (including plowing), for instance, the optimal planting schedule results in a profit of 18,157 coins and looks like this:

Period Strawberry Squares Soybean Squares Eggplant Squares
0 17
12 1 37 18
13 1
14 1 1
15 1
16 1
17 2
18 123
24 18
26 1
27 1
28 1
29 3
30 123
35 3

In conclusion, I believe that Farmville is a rich decision-making environment that can be used to illustrate some of the analytical techniques from the field of Operations Research. This simple example shows how complicated things can become, even with only four crops!

One possibility of extending this analysis would be to consider that one isn’t willing to log in every 4 hours or so in order to harvest crops, so here’s another question:

Question: Given a schedule of off-line hours (i.e. not available for harvesting), how much money can you make in 6 days?

Finally, I haven’t actually answered the question that appears in the title of this blog post: what’s the fastest way to obtain X coins? I’ll leave these last two questions as an exercise.

Technical Details:

This section of the post is dedicated to those who want to know more about how this analysis was conducted. I used an integer programming model written in AMPL (I think dynamic programming would work too). My variables are: P_{it} = number of squares planted with crop i in period t , H_{it} = number of squares of crop i harvested in period t , A_t = area in use in period t , M_t = money available in period t . Periods go from 0 to T (in our example, T=36 ). So we are interested in maximizing M_T .

The constraints update the values of A_t and M_t based on what you do in period t . Here they are (I’m omitting the details of boundary conditions):

\displaystyle A_t = A_{t-1} + \sum_{i} P_{it} - \sum_{i} H_{it} \enspace \forall \; t

\displaystyle M_t = M_{t-1} - \sum_{i} c_i P_{it} + \sum_{i} r_i H_{it} \enspace \forall \; t

where c_i and r_i are, respectively, the cost and revenue of crop i . Because we don’t consider wilting, H_{it}=P_{i(t-g_i)} , where g_i is the time it takes crop i to grow and ripen. Therefore, the H_{it} variables can be eliminated. Finally, we require M_t \geq 0 and 0 \leq A_t \leq 144 . Here’s the mixed-integer programming (MIP) model in AMPL in case anyone wants to play with it. When it is optimal to use more than one crop, the MIP can get pretty hard to solve, considering its size.

12 Comments

Filed under Applications, Exam Fun, Facebook, Farmville, Integer Programming, Modeling, Teaching

12 responses to “Facebook’s Farmville: What’s the Fastest Way to Get Rich?

  1. Brilliant post. The idea of using games to promote OR is great. I posted the article up here http://www.reddit.com/r/sysor/
    to hopefully get more people to see it. Kudos again.

  2. orbythebeach

    Thank you very much for helping me spread the word. I appreciate it.

  3. Pingback: Michael Trick’s Operations Research Blog : Running Farmville through Operations Reseach

  4. Carlos Forster

    I chose to use an algorithm based on trees, instead. Such algorithm doesn’t maximize my profit, but will let me play farmville more sparsely. And it is a very simple algorithm, with three unnested loops.

    Step 1 – While available(gift) do accept(gift); use(gift); end;

    Step 2 – While available(fruit) do harvest(fruit) end;

    Step 3 – If available(money) then goto step 4 else terminate;

    Step 4 – Buy and plant a tree;

    Step 5 – Goto step 3;

    Step 6 – Invite more friends;

    Ah yes. Step 6 is occasionally unreachable.

  5. Sebastian

    Your model can be run under GLPK, which implements GNU MathProg, a subset of AMPL. As the language is somewhat stricter, the following changes are necessary:

    1. remove the two option lines,
    2. use param T := 36 instead of T = 36,
    3. move the solve line and every line after it just before the data block, and
    4. add an “end;” line to the end of the file.

    Then running “glpsol –math farmville.mod” will solve your model.

  6. orbythebeach

    Thanks, Sebastian. The AMPL model I posted is small enough to run with the free student version of AMPL, but it’s nice to have a GLPK version if one wants to play with larger instances.

  7. Peter Hall

    There are good number of applications for this problem in the real world which would require a few extensions to the AMPL model you have proposed.

    An example would be any type of product mix problem with capacity constraints with shelf-life or re-seeding constraints. ‘Shelf life’ constraints would limit the number of times that a product could be made within the entire horizon and ‘Re-seeding’ constraints would limit the time after harvesting/production that any/all/specific products could be made on the resource where the harvesting/production took place.

    Spaces on the farming grid could actually be any type of resource that has finite production and capacity constraints.

    Another extension to this problem could be sequencing problems where we can only ‘grow’ certain product within a certain number of ‘spaces’ of each other.

    Anyhow, nice application of MILP to a simple and fun problem.

  8. Pingback: Sikuli – a scripting language based on screenshots « Sebastian Pokutta’s Blog

  9. Pingback: 2010 in Review: How Did We Do? | O.R. by the Beach

  10. Pingback: Big Bang Theory Party Planning | O.R. by the Beach

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s