Farmville | O.R. by the Beach

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.