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: 
The constraints update the values of
where 
Just wow!
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.
Thank you very much for helping me spread the word. I appreciate it.
Brilliant
Pingback: Michael Trick’s Operations Research Blog : Running Farmville through Operations Reseach
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.
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.
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.
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.
Pingback: Sikuli – a scripting language based on screenshots « Sebastian Pokutta’s Blog
Pingback: 2010 in Review: How Did We Do? | O.R. by the Beach
Pingback: Big Bang Theory Party Planning | O.R. by the Beach