Maximizing Win Probability in the Game of Farkle

povray six dice
Image by Matt Busche using modified povray source by Piotr Borys

Neller and Presser modeled a simple dice game called pig as a Markov Decision Process (MDP) and used value iteration to find the optimal game winning strategy1. Inspired by their approach, I've constructed a variant of an MDP which can be used to calculate the strategy that maximizes the chances of winning 2-player farkle. Due to the three consecutive farkle penalty, an unfortunate or foolish player can farkle repeatedly to achieve an arbitrarily large negative score. For this reason the number of game states is unbounded and a complete MDP model of farkle is not possible. To bound the problem, a limit on the lowest possible banked score is enforced. The calculated strategy is shown to converge exponentially to the optimal strategy as this bound on banked scores is lowered.

Each farkle turn proceeds by iteratively making a pre-roll banking decision, a (contingent) roll of the dice, and a post-roll scoring decision. I modified the classic MDP to include a secondary (post-roll) action to fit this turn model. A reward function that incentivizes winning the game is applied. A similarly modified version of value-iteration (that maximizes the value function for both the pre-roll banking decision, and the post-roll scoring decision) is then used to find an optimal farkle strategy.

With a lower bound of -2500 points for banked scores, there are 423,765,000 distinct game states and so it is not convenient to share the entire strategy in printed form. Instead, I provide some general characterizations of the strategy. For example, if both players use this same strategy, the player going first will win 53.487% of the time. I also provide samples of complete single-turn strategies for various initial banked scores. Currently, only the strategy for Facebook Farkle has been calculated, but the strategy for other scoring variants of farkle could easily be deduced using the same software.


The Rules of Farkle

Farkle rules differ only slightly from the rules of Zilch, but are provided here for completeness.

Farkle is played with two or more players and six six-sided dice. Each player takes turns rolling the dice. The dice in a roll can be worth points either individually or in combination. If any points are available from the roll, the player must set aside some or all of those scoring dice, adding the score from those dice to their point total for the turn. After each roll, a player may either re-roll the remaining dice to try for more points or may bank the points accumulated this turn (though you can never bank less than 300 points). When a player banks his points, the player's turn is ended and the dice are passed to the next player.

If no dice in a roll score, then the player loses all points accumulated this turn and their turn is ended. This is called a farkle, a sorrowful event indeed.

If all dice in a roll score, the player gets to continue his turn with all six dice. This is called hot dice and is guaranteed to brighten your day.

A player may continue rolling again and again accumulating ever more points until he either decides to bank those points or loses them all to a farkle.

If a player ends three consecutive turns with a farkle, they not only lose their points from the turn but also lose 500 points from their banked game score. (This is the only way to lose banked points.) After a triple farkle, your consecutive farkle count is reset to zero so you're safe from another triple farkle penalty for at least three more turns.

The game ends when one player has banked a total of 10,000. Unlike zilch, other players do not get a final turn.

Scoring is as follows:

  • Each 1 is worth 100 points.
  • Each 5 is worth 50 points.
  • A set of three 1s is worth 1000 points.
    A set of three 2s is worth 200 points.
    A set of three 3s is worth 300 points.
    A set of three 4s is worth 400 points.
    A set of three 5s is worth 500 points.
    A set of three 6s is worth 600 points.
    Unlike zilch, each extra die in a set increases the value of the set by a like amount. So four 4s are worth 800 points, five 5s are worth 1500, and six 1s are worth 4000.
  • Three pair is worth 750 points. Unlike Zilch, a set of four 2s and two 4s may not be scored as three pairs.
  • A six die straight is worth 1500 points.
  • Each die can only be used once when scoring. (If you roll two 1s, two 2s, and two 3s you can either count the two 1s for 200 or use all six dice for three-pair and 1500 points — you can't use the ones both ways for 1700 points.)

Markov Decision Processes and Value Iteration

Note: those familiar with MDPs may find the non-standard variable names I use to present this standard subject distracting. My aim is to use variable names most meaningful in the final value-iteration equation. I beg your indulgence. As a courtesy, I've included mouse-hover popups where each such non-standard variable name is introduced (highlighted in blue) explaining the motivation for the change.

A Markov Decision Process (MDP)2 is a system having a finite set of states $S$. For each state $s \in S$, there are a set of actions that may be taken $A(s)$. For each action $a \in A(s)$, there is a set of transition probabilities $P_a(s, s')$ defining the probability of transitioning from $s$ to each state $s' \in S$ given that action $a$ was taken while in state $s$. When action $a$ is taken from state $s$, the MDP responds by randomly moving to a new state $s'$ as governed by the transition probabilities $P_a(s, s')$ and then assigning the decision maker a reward $D_a(s, s')$.

The objective is to find a strategy function $G(s)$ that returns the particular action at each state $s \in S$ that will maximize the expected cumulative reward given by:

$$\sum_{k=0}^{\infty} \gamma^k D_{a_k}(s_k, s_{k+1})$$

where $k$ is a discreet time variable, $s_k$ is the game state at time $k$, $a_k$ is the player action taken from from state $s_k$, and $\gamma \in [0,1)$ is a constant discount factor for future rewards. The expectation must be taken over all possible state transition paths, and maximized over all possible choices for the actions $a_k$ taken in each state $s_k$. Then $G(s)$ will be defined by the $a_k$ taken from each state $s_k$ that maximizes this expectation.

One technique for solving this problem is value iteration. With this technique, each state $s$ is given a decimal value $W(s)$ which is an estimate of the expected discounted sum of all future rewards gained from state $s$. The estimate for $W(s)$ is iteratively refined for all $s$ by applying this update equation sequentially to all states $s$: $$W_{i+1}(s) := \max_{a \in A(s)} \left[ \sum_{s'} P_a(s, s')(D_a(s, s') + \gamma W_i(s'))\right]$$

Note that at each state $s$, the action which provides maximum total reward is selected. So not only is the estimate of $W(s)$ iteratively refined, but the best action $a$ taken for each state $s$ is also simultaneously improved. Iteration continues until $W_{i+1}(s)$ and $W_i(s)$ converge for all $s$, and $G(s)$ is then the set of actions $a$ selected for each state $s$ in the final iteration.

Extending the MDP to support Farkle

During a farkle turn, a player must iteratively

  1. decide whether to bank his current points,
  2. then, if he decides not to bank, roll the dice,
  3. then decide how to score the dice.
So that's potentially two decisions (actions) for each state transition: a pre-roll banking decision (to bank, or to roll), and a post-roll scoring decision (how to score the dice just rolled). But an MDP (as described above) consists of only one action followed by a random transition. So one may reasonably ask if farkle can even be modeled with an MDP.

To fit farkle to an MDP model, one need only consider the result of a roll as part of the game state, and then reorder the turn sequence to that of a combined scoring-and-bank/roll action followed by either an end-of-turn-event or another random-roll-event. But this increases the number of game states by at least a few orders of magnitude and makes the problem unsolvable without a commensurate increase in computer resources.

Alternatively, the roll-decision could be splintered to include any conceivable combination of scoring instructions, directing the MDP how to score each potential roll before the roll is even made, thereby allowing the state machine to transition without additional input from the player once the roll is made. Aside from being a painful way of thinking about the problem, the number of possible scoring instructions is enormous, and the approach is again not feasible.

Rather than forcing the game to fit the MDP model, I instead define an extended MDP (EMDP) to more naturally model the game. Like an MDP, an EMDP has a finite set of states $S$. For each state $s \in S$, there are a set of primary actions that may be taken $A(s)$. For each primary action $a \in A(s)$, there are a set of sets of secondary actions $R_a(s)$. Once primary action $a$ is taken, one set of secondary actions $r \in R_a(s)$ is selected randomly by the EMDP according to a probability distribution $P_a(s)$. So instead of transitioning, the EMDP responds to action $a$ by offering a randomly chosen set of secondary actions that may be taken. For each secondary action $c \in r$, a deterministic transition state $s'$ is defined by a transition matrix $s' = X_{a,c}(s)$. Selection of action $c$ causes the EMDP to transition to $s'$ and reward $D_{a,c}(s, s')$ is granted.

Because there are two actions to be taken in a turn, the optimal strategy also has two parts: $G_A(s)$ is the optimal primary action in state $s$, and $G_C(s, r)$ is the optimal secondary action to take in state $s$ given that secondary action set $r$ was randomly offered by the EMDP in response to action $a$.

Value iteration processing is also extended to account for the secondary action: $$W_{i+1}(s) := \max_{a \in A(s)} \left[ \sum_{r \in R_a(s)} P_{a,r}(s) \max_{c \in r} \Big[ D_{a,c}(s, s') + \gamma W_i(s') \Big] \right]$$

Neller and Presser chose a reward function to incentivize winning the game1. For any transition from a non-winning game state $s$ to a winning game state $s_w$, $D_{a,c}(s, s_w) = 1$ (where $s_w$ is any state where the player's banked points plus his turn points meets or exceeds the game goal of 10,000 points, and where his turn points meets or exceeds the minimum banking threshold). For transitions to any other non-winning state $s_v$, $D_{a,c}(s, s_v) = 0$. Because all game winning states $s_w$ are terminal, all future rewards from such states must be zero, so $W(s_w) = 0$. Because $W$ is known for all game winning states $s_w$, $W(s_w)$ is never updated during value iteration. (I.e., although a game winning state can appear on the right side of the value iteration update equation, it never appears on the left.)

Normally for an MDP, $0 \le \gamma < 1$, but we do not wish to value a game you win in 30 turns, less than a game you win in 10. Following Neller and Presser's approach, I instead set $\gamma = 1$. In general this can prevent value iteration from converging, but it does not cause a problem for farkle. (I think this is because there is no circular state transition path offering unbounded rewards, and because only the player that gets to a game winning state first actually wins, which ensures that the optimal strategy can't be attracted to some infinitely long path to a game winning state.) With $\gamma = 1$, $W(s)$ converges to the probability of winning from any non-terminal state $s$ when using an optimal strategy; the $a$ selected in the $\max_a$ operation converges to the optimal banking strategy from state $s$: $a = G_A(s)$; and the $c$ selected by the $\max_c$ operation converges to the optimal scoring strategy from state $s$ given that roll $r$ was thrown: $c = G_C(s,r)$.

Given that $\gamma = 1$, simplifications can be achieved if you move the reward for transitions to a game winning state out of the reward function, and into the value function for those same game winning states. That is, instead of defining $W(s_w) = 0$, define $W(s_w) = 1$, and set $D_{a,c}(s, s') = 0$ everywhere, allowing the reward function to be completely eliminated from the update equation. This definition also results in $W(s)$ consistently being the probability of winning the game from any state $s$ (including terminal game winning states).

Applying the simplifications of $\gamma = 1$, $D_{a,c}(s, s') = 0$, and $W(s_w) = 1$ reduces the extended value iteration update formula to:

$$W_{i+1}(s) := \max_{a \in A(s)} \left[ \sum_{r \in R_a(s)} P_{a,r}(s) \max_{c \in r} W_i(s') \right]$$

This general approach for finding the optimal play strategy for games having both pre-roll and post-roll actions, is further detailed for the specifics of 2-player farkle in the sections below.

Game State Characterization

The current game state $s$ is characterized by six component state variables:

$$s = (t, n, b, d, f, e)$$

where $t$ is the number of points accumulated only from your current turn. Once $b + t \gt 9950$ (which means you've hit the goal of 10,000 points) and you've met the minimum requirement to bank $t > 250$, the game is over, so for non-terminal game states we have:

$$t \in \{0, 50, 100, ..., \max [250, 9950-b]\}\text{.}$$

$n$ is the number of dice you have to roll

$$n \in \{1, 2, 3, 4, 5, 6\}\text{,}$$

$b$ is your banked score for which I enforce a lower bound $L$

$$b \in \{L, L+50, ..., -100, -50, 0, 50, 100, ..., 9950\}\text{,}$$

$d$ is your opponent's banked score which is also lower bounded to $L$

$$d \in \{L, L+50, ..., -100, -50, 0, 50, 100, ..., 9950\}\text{,}$$

$f$ is your consecutive farkle count (from previous turns)

$$f \in \{0, 1, 2\}\text{, and}$$

$e$ is your opponent's consecutive farkle count

$$e \in \{0, 1, 2\}\text{.}$$

The Farkle Value Iteration Equation

In this section we apply the farkle component state variables and rules defined in previous sections to the EMDP value iteration equation:

$$W_{i+1}(s) := \max_{a \in A(s)} \left[ \sum_{r \in R_a(s)} P_{a,r}(s) \max_{c \in r} W_i(s') \right]$$

Let's detail $A(s)$ first. For farkle, $A(s)$ is the set of available banking actions having at most two members: BANK and ROLL. For game states where you have so far accumulated less than 300 points, you have only one pre-roll (primary) action available to you: ROLL the dice. But for all other game states you have two pre-roll actions available: BANK, or ROLL. This yields:

\begin{equation} W_{i+1}(s) := \left\{ \begin{array}{ll} \sum\limits_{r \in R_{\text{ROLL}}(s)} P_{{\text{ROLL}},r}(s) \max\limits_{c \in r} W_i(s'), & \text{if $t < 300$}.\\ \\ \max \bigg[\sum\limits_{r \in R_{\text{BANK}}(s)} P_{{\text{BANK}},r}(s) \max\limits_{c \in r} W_i(s'), \\ \hspace{30pt} \sum\limits_{r \in R_{\text{ROLL}}(s)} P_{{\text{ROLL}},r}(s) \max\limits_{c \in r} W_i(s') \bigg], & \text{if $t \ge 300$}.\\ \\ \end{array} \right. \end{equation}

In the case of a bank action the equation collapses. $R_{\text{BANK}}(s)$ has only one entry: $r_{\text{BANK}}$. There's only one member of the probability distribution: $P_{{\text{BANK}}, r_{\text{BANK}}}(s) = 1$. Also, $r_{\text{BANK}}$ has only one entry: $c_{\text{BANK}}$. So for the case of $t \ge 300$ , the first member of the outer max operation reduces to just $W_i(s')$. All the mathematical machinery in this case is flexible enough to handle the banking case, but is entirely unnecessary. But what exactly is $s'$ after you bank?

Looking back at the game state characterization from the previous section, there is no variable that encodes whose turn it is. Everything I've written so far is from the perspective of the player who controls the dice, and there is no $s'$ expressible in terms of our six component state variables that identifies your state after a banking operation. (This is by design and is consistent with Neller and Presser's approach for optimizing pig game play strategy.) After you bank, it is your opponent's turn who we assume is also playing the optimal strategy, and we can express his state after you bank. If your game state just before you banked was $s = (t, n, b, d, f, e)$, then your opponent's state after you bank will be $o' = (0, 6, d, b + t, e, 0)$. To be clear, after you bank your opponent will have 0 turn points, 6 dice to roll, a banked score of $d$, an opponent's banked score of $b + t$ (which is your new banked score), $e$ consecutive farkles, and his opponent will have $0$ consecutive farkles (your farkle count reverting to zero having just banked). Your opponent's win probability is $W(o')$, which means our win probability after the bank must be: $W_i(s') = 1 - W_i(o') = 1 - W_i(0, 6, d, b + t, e, 0)$, which yields: \begin{equation} W_{i+1}(s) := \left\{ \begin{array}{ll} \sum\limits_{r \in R_{\text{ROLL}}(s)} P_{{\text{ROLL}},r}(s) \max\limits_{c \in r} W_i(s'), & \text{if $t < 300$}.\\ \\ \max \bigg[\Big(1 - W_i(0,6,d,b+t,e,0)\Big), \\ \hspace{30pt} \sum\limits_{r \in R_{\text{ROLL}}(s)} P_{{\text{ROLL}},r}(s) \max\limits_{c \in r} W_i(s') \bigg], & \text{if $t \ge 300$}.\\ \\ \end{array} \right. \end{equation}

In the case of a ROLL action, $R_{\text{ROLL}}(s)$ corresponds to the set of all possible rolls of the dice from state $s$. More precisely, each roll $r$ is defined as a set of possible scoring decisions for some permutation of thrown dice. The $\sum_r$ operation is summing over each possible roll $r \in R_{\text{ROLL}}(s)$. $P_{\text{ROLL},r}(s)$ is the probability of making roll $r$ from game state $s$. And each $c \in r$ is one possible scoring decision given that roll $r$ was thrown. Given scoring decision $c$, the new game state $s'$ is determined. The $\max_c$ operation maximizes the expected win probability $W_i(s')$ given that roll $r$ was thrown over these possible scoring decisions.

First note that the set of potential rolls from game state $s = (t, n, b, d, f, e)$ is only dependent on the number of dice you are rolling, so:

$$R_{\text{ROLL}}(s) = R_{\text{ROLL}}(n)$$

Second note that

$$P_{\text{ROLL},r}(s) = {1 \over {6^n}}$$

Third, because the expression for $W_i(s')$ is fundamentally different for the case of farkling rolls vs. scoring rolls, it is convenient to partition $R_{\text{ROLL}}(n)$ into two subsets: the subset of all farkling rolls $R_{\text{FARKLE}}(n)$, and the subset of all scoring rolls $R_{\text{SCORE}}(n)$:

$$R_{\text{ROLL}}(n) = R_{\text{FARKLE}}(n) \bigcup R_{\text{SCORE}}(n)$$

Fourth, if roll $r$ is a farkle, then $r$ will have only one member: a zero point farkle scoring decision and the $max_c$ operation can be dropped.

Applying these four observations gives:

\begin{equation} \begin{array}{rl} \sum\limits_{r \in R_{\text{ROLL}}(s)} P_{{\text{ROLL}},r}(s) \max\limits_{c \in r} W_i(s') &= \sum\limits_{r \in R_{\text{FARKLE}}(n)} {1 \over {6^n}} W_i(s') + \sum\limits_{r \in R_{\text{SCORE}}(n)} {1 \over {6^n}} \max\limits_{c \in r} W_i(s') \\ &= {1 \over {6^n}} \sum\limits_{r \in R_{\text{FARKLE}}(n)} W_i(s') + {1 \over {6^n}} \sum\limits_{r \in R_{\text{SCORE}}(n)} \max\limits_{c \in r} W_i(s') \end{array} \end{equation}

After a farkle, it becomes your opponent's turn and there is again no expression for the new game state. We again instead express $W_i(s')$ in terms of your opponents win probability after your farkle:

$$W_i(s') = 1 - W_i(0, 6, d, b', e, f')$$

where $b'$ is your new banked score after your farkle, which may have decreased due to the three consecutive farkle penalty, but is enforced to always be at least $L$ to keep the problem tractable:

$$b' = \max [ L, b - Y_f ]\text{;}$$ where $Y_f$ is the number of points you lose from your banked score when you farkle while already having $f$ consecutive farkles

$$\begin{align*} Y_0 &= 0 \\ Y_1 &= 0 \\ Y_2 &= 500\text{;} \end{align*}$$

and where $f'$ is your new consecutive farkle count which normally just increments, but is reset back to zero if you just had your third consecutive farkle

$$f' = (f+1) \mod 3\text{.}$$

Note also that for all farkling rolls the expression inside the sum is the same, so we can replace the sum with a multiplicative factor equaling the number of ways to roll a farkle with $n$ dice. Combining that count with the ${1 \over {6^n}}$ simplifies to the probability of farkling with $n$ dice3:

$$\begin{align*} F_1 &= 2/3 \\ F_2 &= 4/9 \\ F_3 &= 5/18 \\ F_4 &= 17/108 \\ F_5 &= 25/324 \\ F_6 &= 5/216 \\ \end{align*}$$

Combining the above observations gives this substitution:

$${1 \over {6^n}} \sum\limits_{r \in R_{\text{FARKLE}}(n)} W_i(s') = F_n (1 - W_i(0,6,d,b',e,f'))$$

To detail the expression for the case of scoring rolls, first let $C_T(c)$ be the number of points taken with scoring combination $c$, and let $C_N(c)$ be the number of dice used with scoring combination $c$. So after rolling roll $r \in R_{\text{SCORE}}(n)$ and selecting scoring action $c \in r$ the state transitions from $s = (t, n, b, d, f, e)$ to

$$s' = (t', n', b, d, f, e)$$


$$ \begin{align*} t' &= t+C_T(c) \\ n' &= h(n-C_N(c)) \end{align*} $$

and where $h(x)$ is a hot-dice function for resetting the number of available dice back to $6$ when all dice are successfully scored:

$$h(n)=\begin{cases}6, & \text{for $n = 0$.} \\ n, & \text{otherwise.}\end{cases}$$

This gives our final value iteration equation, where (below) I repeat all the supporting equations for convenience:

$$ W_{i+1}(t,n,b,d,f,e) := \left\{ \begin{array}{ll} F_n (1 - W_i(0,6,d,b-Y_f,e,f')) + \\ \hspace{30pt} {1 \over 6^n} \sum\limits_{r \in R_{\text{SCORE}}(n)} \max\limits_{c \in r} \left[ W_i(t',n',b,d,f,e)\right], & \text{if $t < 300$}.\\ \\ \max \bigg[ \Big(1 - W_i(0,6,d,b+t,e,0)\Big), \\ \hspace{30pt} \Big( F_n (1 - W_i(0,6,d,b',e,f')) + \\ \hspace{60pt} {1 \over 6^n} \sum\limits_{r \in R_{\text{SCORE}}(n)} \max\limits_{c \in r} \left[ W_i(t',n',b,d,f,e) \right] \Big) \bigg], & \text{if $t \ge 300$}. \end{array} \right. $$


$$ \begin{align*} b' &= \max [ L, b - Y_f ] \\ f' &= (f+1) \mod 3 \\ t' &= t+C_T(c) \\ n' &= h(n-C_N(c)) \\ h(n) &=\begin{cases}6, & \text{for $n = 0$.} \\ n, & \text{otherwise.}\end{cases} \\ Y_0 &= 0 \\ Y_1 &= 0 \\ Y_2 &= 500 \\ F_1 &= 2/3 \\ F_2 &= 4/9 \\ F_3 &= 5/18 \\ F_4 &= 17/108 \\ F_5 &= 25/324 \\ F_6 &= 5/216 \\ \end{align*} $$


With a lower bound of $L=-2500$ there are 423,765,000 game states. Each state is modeled with a double precision floating point number requiring 8 bytes, so the entire state matrix requires 3.39012 billion bytes of RAM (plus some array overhead). With game goal $g$ the number of states grows as $(g-L)^3$. Lowering $L$ from -2500 to, say, -10,000 (to eliminate all reasonable doubt that you'll ever venture into portions of the calculated strategy that are non-optimal) will increase the number of game states to over 1.7 billion and memory requirements to 14 GB (which is more than I have on any of my computers).

The value iteration software to solve the optimal farkle problem was written in C++. Obvious optimizations were made. For example, I don't actually iterate over possible rolls, but only over a precalculated set of unique score sets (which is orders of magnitude smaller in count than rolls), and weighting each score set by the number of rolls that share that same set. I let the program iterate over all game states until the maximum relative change over all states from one iteration to the next was less than 1 part in a billion. (I.e., iterations continued until no state had a change in value from one iteration to the next of more than 1 part in a billion, so that even those states with extremely small win probabilities were calculated with precision.) With the floor set to -2500 points, it took 62 iterations for the matrix to converge. Using one core of a dual-core Intel I3 4130T, the software performed 1.30 million state updates per second, each pass of the matrix taking 5 minutes 26 seconds, and convergence taking 5 hours 37 minutes.

The Strategy

It is not practical to list the win probabilities and banking rules for all of the half billion game states in two player farkle. Here I provide only a limited view into the complete strategy by means of five examples. Each of the five subsections below provide a 2 dimensional slice of the 6 dimensional strategy matrix, sufficient for optimal play of a single turn for a particular start-of-turn game state.

Optimal Strategy Case: $b = 0, d = 0, f = 0, e = 0$

Table 1 shows the win probabilities and banking actions needed to play an opening turn optimally. Each cell shows the win probability for different turn scores (starting at $t=0$ in the top row and increasing down the page) and/or different number of dice to roll (starting at $n=6$ in the first column and decreasing as you move to the right). For all entries in this table, the other four component state variables are fixed: your banked score (b) is fixed at 0 points, your opponent's banked score (d) at 0 points, your consecutive farkle count (f) at 0, and your opponent's consecutive farkle count (e) at zero. States shaded green are states from which your optimal banking action is to roll. States shaded red are states from which your optimal banking action is to bank. States with an asterisk are inaccessible and can be ignored (although the software still calculates your win probability in-, and optimal play out of- these states which would be useful if, say through a disruption in the laws of the universe, you somehow find yourself in such a state).

Table 1. Win probabilities and banking actions for optimal turn play for b=0, d=0, f=0, and e=0.


The game begins in the upper left cell at $t=0$ and $n=6$. The win probability listed here means that if both players play optimally, the player going first wins 53.487% of the time. To play a turn, first you must choose your banking action. Since cell (t=0, n=6) is green, the optimal banking action is to roll.

Second, you roll the dice. Let's say for your opening roll, you throw:

$$6, 5, 3, 3, 3, 2$$

Third, you must choose how to score the dice. Here you have three choices:

  • take the 5 for 50 points,
  • take the three 3 for 300 points, or
  • take the 5 and the three 3 for 350 points.

To determine your optimal scoring choice, you must look at the win probabilities from the three states corresponding to each scoring option:

$$ \begin{align*} W(t=50, n=5) &= 0.511005\\ W(t=300, n=3) &= 0.506680\\ W(t=350, n=2) &= 0.509711 \end{align*} $$

So in this case, you should score only the 5 since it moves you to the state with the best probability of ultimately winning the game. This ends one primary-action, random-response, secondary-action sequence effecting one state change in the EMDP. This process is then simply repeated (starting with another banking decision from the new state (t=50, n=5) until you either roll a farkle, or end in a state where you're supposed to bank.

It is interesting to see how the optimal play strategy for the opening turn differs from the strategy that simply maximizes your expected farkle turn score. To maximize expected score you wouldn't bank with 6 dice available to roll unless you had 16,400 or more points on the turn. In contrast, to optimize your chances of winning a game, you would bank 5000 or more points on your opening turn even when you have six dice available to roll. The banking threshold for 5 dice is similarly reduced from 3050 to a more conservative 2500. The banking threshold for other available dice counts do not differ.

Note that if you manage to bank 1000 points on your opening turn, your chances of winning increase to almost 60%; banking 1850 points on your first turn leaves you with better than 70% chance of ultimately winning; bank 2750 points and your chances of winning are above 80%; and manage to put up 3900 points on the opening turn and you're win probability is over 90%.

Optimal Strategy Case: $b = 6000, d = 8000, f = 0, e = 0$

As a second example, consider the case of Table 2 which shows how to optimally play a turn where you start with 6000 points and are 2000 points behind to your opponent who has 8000 points.

Table 2. Win probabilities and banking actions for optimal turn play for b=6000, d=8000, f=0, and e=0.


Given your 2000 point defecit, it is interesting to see how much more agressively this turn should be played compared to an opening turn: the banking thresholds here for 6, 5, 4, 3, 2 and 1 dice are, respectively, 4000, 3350, 1750, 600, 400, and 500 points. Compare that to the banking thresholds for an opening turn at 5000, 2500, 1000, 350, 300, and 300 points.

Another interesting observation about this strategy is that although you should bank between 3300 and 3850 points when you have 5 dice to roll, you should instead roll if you have 3900 to 3950 points (because you have such a high probability of closing out the game).

Optimal Strategy Case: $b = 8000, d = 6000, f = 0, e = 0$

Now consider the reverse of the situation in the previous example. Table 3 shows how to optimally play a turn where you start with 8000 points and are 2000 points ahead of your opponent who has 6000 points.

Table 3. Win probabilities and banking actions for optimal turn play for b=8000, d=6000, f=0, and e=0.


In this example, you have a 2000 point lead and are yourself only 2000 points from winning the game. It is interesting to see how much more conservatively this turn should be played compared to an opening turn: the banking thresholds here for the different number of dice to throw are 1650, 1250, 650, 300, 300, and 300 points. Compare that to the banking thresholds for an opening turn at 5000, 2500, 1000, 350, 300, and 300 points.

As in the previous example, there is another banking rule inversion in this table, but this time for the case of 6 dice, where at point values above 1750 it again becomes advantageous to roll to try to end the game.

Optimal Strategy Case: $b = 9000, d = 9500, f = 0, e = 0$

As a fourth example, consider the case of Table 4 which shows how to optimally play a turn where you start with 9000 points and are 500 points behind your opponent who has 9500 points.

Table 4. Win probabilities and banking actions for optimal turn play for b=9000, d=9500, f=0, and e=0.


I find it interesting that the only time you should bank during such a turn is if you have exactly 3 dice to roll and either 700 or 750 points on the turn. Why does it make sense to roll just 1 or 2 dice with those same number of points? And why does it make sense to roll three dice when you have 800 or more points?

To answer the first question, observe that it's easier to ultimately hot-dice (score all dice thrown) when you are rolling only 1 or 2 dice than when you are rolling 3. If you can manage to get back to 6 dice, your chances of ending the game this turn increase dramatically. Furthermore, any additional game points you gain by rolling 3 dice are meaningless unless you hot-dice. If only 1 or 2 of the 3 thrown dice score, you will still find yourself below the game goal and (if you then decide to bank these few extra points) will not have even reduced the number of points you have to accumulate on your subsequent turn due to the minimum banking threshold.

To answer the second question, note that it's possible to reach 10,000 points without hot-dice: in particular there's a 7% chance of rolling two ones and a third non-scoring die. These rolls end the game if you have 9800 points.

Optimal Strategy Case: $b = 9500, d = 9000, f = 0, e = 0$

Now consider the reverse of the situation in the previous example. Table 3 shows how to optimally play a turn where you start with 9500 points and are 500 points ahead of your opponent who has 9000 points.

Table 5. Win probabilities and banking actions for optimal turn play for b=9500, d=9000, f=0, and e=0.


Here I found it surprising that even though you have a 500 point lead and control of the dice, the optimal strategy requires that you never bank until you've reached the game-winning 500 points. This is surprisingly more aggressive play than on an opening turn where the score is tied. I would have guessed that banking 300 points when faced with rolling 1 or 2 dice would have been better to avoid the high-probability farkle, then allow your opponent a chance to force his way to a 1000 point turn, and assuming he fails, follow up with a high-probability minimum bank turn to win. It turns out if your opponent plays perfectly, he has about a 1/3 chance of reaching 1000 points to steal the win, and so playing a little more aggressively to attempt to end the game and deny him that possible steal is advantageous.

Also note how for many point totals, you are better off with fewer dice. This is often the case when playing turns where your best play is to try to reach 10,000 points and end the game, and also in cases where you are just really far behind an opponent that is fast approaching a game winning score.

Strategy Validation

In this section I share the efforts I've made to sanity check the calculated strategies for reasonableness, and to determine the deviation between the calculated strategy and the truly optimal strategy. This section definitely gets into the weeds and is not for the faint of heart, but may be of interest to skeptics or the particularly nerdy (of which I am both).

Comparison to strategy that maximizes expected turn score

Strategies that maximize expected turn score for farkle variants have been independently calculated with consistent results4,5,6. These strategies do not consider your current banked score, your opponent's banked score or farkle count, or the end of game scoring goal. Still, one would expect that for an opening turn (where the score is tied at zero and where the end-of-game scoring goal is distant) that the game winning strategy documented here and the strategy that maximizes expected turn score would be similar for low turn score states. Furthermore, the two strategies should converge if the game scoring goal is increased from 10,000 points towards infinity. Unfortunately, the 10,000 point goal was already stretching both the memory limits and processing power of my computer. To reduce the size of the state space, I eliminated the three consecutive farkle penalty. This effectively eliminates the f and e state variables, reducing the size of the state space by a factor of 9, and also eliminates the need to model banked score states of less than 0 points, which shrinks things even more.

My Farkle Strategy Generator (FSG)6 produces farkle strategies that maximize expected turn score. The FSG outputs strategy tables that prioritize each turn state with a sequential preference number. Those states associated with higher expected turn scores have a higher preference number. To follow the strategy, you score thrown dice to move to the state with the highest number. This is exactly the same process you use to follow the game winning strategy presented in this document: you score your dice to move to the state with the highest probability of winning. By indexing the states from lowest win probability to highest, the two strategies can easily be compared.

First compare the two strategies for the case of a 10,000 point goal. Table 6W shows the strategy that maximizes your chances of winning the game (produced by value iteration) for an opening turn. Table 6E shows the strategy that maximizes expected turn score (produced by the FSG). Turn scores in both cases are truncated to a maximum of 1500. States with different preference numbers are highlighted. There are numerous slight differences, but they are obviously very similar: the banking thresholds are almost identical, and the state preference numbers deviate only slightly.

Table 6W. Preferred states for strategy that maximizes win probability for an opening turn of a 2-player game with a 10,000 point goal. Descrepancies with the strategy that maximizes expected score (shown in Table 6E) are highlighted.
Table 6E. Preferred states for strategy that maximizes expected score. Descrepancies with the strategy that maximizes win probability for an opening turn of a 2-player game with a 10,000 point goal (shown in Table 6W) are highlighted.



Tables 7W and 7E compare these same two strategies but with the scoring goal increased to 30,000 points. Here the two strategies are seen to be almost identical for these low turn score states. The two strategies do appear to be converging as the scoring goal increases. While this doesn't assure strategy correctness, it offers convincing evidence of correctness in at least this limiting case.

Table 7W. Preferred states for strategy that maximizes win probability for an opening turn of a 2-player game with a 30,000 point goal. Descrepancies with the strategy that maximizes expected score (shown in Table 7E) are highlighted.
Table 7E. Preferred states for strategy that maximizes expected score. Descrepancies with the strategy that maximizes win probability for an opening turn of a 2-player game with a 30,000 point goal (shown in Table 7W) are highlighted.



Effects of the banked score lower bound

The calculated strategy is non-optimal when playing in regions of the state space where either your banked score, or your opponent's banked score is near the lower bound. This discrepancy between the calculated strategy and the truly optimal strategy is further exacerbated as the consecutive farkle count associated with a banked score near the bound increases.

To estimate the extent of the discrepancy, I lowered the bound on banked scores from -2500 to -3000 and regenerated the strategy matrix. One expects the relative deviation between the win probabilities of corresponding states in the two strategies to decrease as the minimum of the player's banked scores increases. To see the rate of convergence, for each possible banking score $B$ ($-2500 <= B < 10,000$), I found the maximum relative deviation between win probabilities (calculated as ${{2|w1-w2|}\over{w1+w2}}$) over all game states satisfying $min(b,d) >= B$. Table 8 lists selected results. Note that each time B increases by 500 points (which just happens to be the triple farkle penalty), the maximum relative deviation consistently decreased by 2 orders of magnitude (with one of those two orders of magnitude coming with the last 50 point increase). Given this exponential convergence rate, for any given $B$, the maximum relative deviation between the strategies for $L=-2500$ and $L=-\infty$ must be only slightly greater (on the order of 1%) than the maximum relative deviation between the strategies for $L=-2500$ and $L=-3000$.

Table 8. For two different farkle strategies calculated with $L=-2500$ and $L=-3000$, the maximum relative deviation of win probabilities over all states satisfying $min(b,d) >= B$ is shown.

BMaximum Relative Deviation

Note that the state win probabilities for two calculated strategies do not have to be identical for the rules about when to bank, and when to roll, and how to score the dice in each situation to be to be identical. So how close do the calculated win probabilities and the optimal win probabilities need to be to make it likely we are playing with a truly optimal strategy? Using state preference charts like those shown in the previous section, I compared complete turn strategies for all combinations of state variables $b$, $d$, $f$, and $e$. If two state preference charts are identical, then the strategies are identical. Once I found a bizarre state preference discrepancy associated with a relative difference in win probability on the same order as the convergence threshold for the entire state matrix. I ignored this and any others like it that might be lurking in the tables. Table 9 shows the banked score and consecutive farkle count thresholds above which no more strategy discrepancies otherwise appeared. So for example if both you and your opponent have at most 1 consecutive farkle, and you both have banked scores of at least -1500 points, then there are no discrepancies between the two strategies.

So although there's no way to pick a lower bound $L$ that will assure all turn strategies will be truly optimal for a given working range of banked scores and consecutive farkle counts, driving the maximum relative deviation down to within about 1 part in 108 seems to assure that the vast majority of turn strategies (and likely all of them) are optimal. Given the convergence rate seen above, this means that as long as both players are about 2000 points above the lower bound on banked scores, all turn strategies are likely to be optimal.

Table 8. When both players banked scores and consecutive farkle counts satisfy the listed constraints the two strategies that maximize win probability for -2500 and -3000 point lower bound on banked scores are identical. The maximum relative deviation over all game states satisfying these constraints is also listed.

Minimum Banked ScoreMaximum Farkle CountMaximum Relative Deviation


Extended forms of a Markov Decision Process (MDP) and value iteration were devised that allow more efficient modeling of 2-player Farkle than is possible with a standard MDP. Using this model, the strategy that maximizes win probability using Facebook scoring rules has been determined under the constraint that banked scores are lower bounded to a large negative score. The strategy is shown to be unaffected by this bound in regions where banked scores are at least 2000 points above the bound. The strategy appears to converge (as expected) to the strategy that maximizes expected turn score as the end-of-game scoring goal is increased.

With nearly a half billion game states, and so many different dice rolls and scoring options possible from each of these different states, it wasn't immediately obvious whether the problem was solvable with a home computer. I was quite pleased when I saw the first value iteration update complete, and even more pleased when I saw the matrix was actually converging! It was a nice problem in the sense that it's complexity puts finding the solution at the limits of what can be done with a home computer (or at least at the limits of what I can do with a home computer).

The optimal strategy showed many expected behaviors including more aggressive play when behind, and more conservative play when ahead. But it also showed many behaviors that were unexpected to me, such as playing aggressively even with a sizable lead when nearing the game goal of 10,000 points. Numerous times I was convinced I had discovered a flaw in the strategy (and therefore either a bug in my code or an error in my analysis) only to realize later that the strategy was actually reasonable.

Next Steps

The very limited view I've offered into the game winning strategy is unsatisfying. Time permitting, I intend to develop a web page that will allow you to explore the gargantuan optimal Farkle strategy in detail, and perhaps even play a game of farkle against a perfect computer opponent. I am motivated by your interest, so please leave a comment if you'd like to see it.

A Facebook Farkle game is won by the first player to bank 10,000 or more points, but there are other variations to end-of-game rules. In Zilch, for example, the other player always gets a final go at the dice. Some people like to assure that both players get the same number of turns. In this latter case, the optimal strategies played by the two players are not even the same — with the player going second clearly having a strategic advantage. I think any of these could be modeled, but they are each very different, and not currently supported by my solver. These are ickier problems, and I don't intend to work on them anytime soon.


  1. T Neller and C Presser, "Optimal Play of the Dice Game Pig," The UMAP Journal 25(1) (2004), pp. 25-47.
  2. R. E. Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, 1957.
  3. Cap Khoury, Multinomial Coefficients and Farkle, Jul. 2009.
  4. M Busche, Maximizing Expected Scores in the Game of Zilch, Matt's Maniacal Musings, Aug. 2010.
  5. E Farmer, Analysis of Farkle, Possibly Wrong, Apr. 2013.
  6. Farkle Strategy Generator, Matt's Maniacal Musings.

About matt

I live in Lakewood, Colorado with my wonderful wife Tammy and three fine children Aaron, Becky and Cate. I'm an electrical engineer by education, but worked as a software developer for about 20 years. I recently took a promotion to full time care giver, but will likely return to the grind once the kids are a little older. I coach basketball, sing in two different church choirs, tutor mathematics and physics at a local high school, and spend what other time I can find pursuing home improvement projects and several pet software projects.
This entry was posted in Uncategorized. Bookmark the permalink.

9 Responses to Maximizing Win Probability in the Game of Farkle

  1. Martin says:

    I would love to see a website with all the statistics available!!
    I love delving into these kind of games! 😀

    • matt says:

      One of the problems is that everyone plays with slightly different rules. It takes several hours of computation time to solve for a single rule set, and with a half billion game states, each solution would eat up 4 gigs of my server’s hard disk too. I guess I could dedicate a couple of terra-byte hard drives to storing (and backing up) solutions to various game rules.

  2. David Klausa says:

    Does the 53.487 percent to win for the first player take into account the second player’s rebuttal after the first passes 10,000 points?

    • matt says:

      No. The first player to bank 10,000 or more points wins in this version of the game (consistent with Facebook Farkle game rules).

      It would be fairly straight-forward, however, to analyze the game rule variant you describe. It’s something I’ve thought about doing for some time. The best way, I think, is to start by precalculating the chance of a “rebuttal” succeeding for all possible point deficits that must be overcome in a single (final) turn. If, for example, the first player banks 10,200 points whilst the second player had 9,000 points, then you are interested in the probability of the second player (given a final turn) to successfully walk the safest path to 1,250 or more points in a single turn. (Incidentally, my FSG can be configured to do this — I describe how in one of my other comments on this website somewhere.) Do this for all possible deficits from 100, to something absurdly large (although a few thousand points would probably be sufficient as it is surely suboptimal to continue rolling with 15,000 points, so higher point game states would never be explored by an optimal player).

      Then the win probability matrix would then be extended to include game states at and above 10,000 points for the active player (i.e., the player whose turn it is). And the win probability associated with banking in these states would be fixed with the rebuttal probabilities we just calculated. The win probability for these super-10,000 point game states could be calculated in a single downward pass (since the win probabilities for banking from each them are fixed and known).

      So, anyway, I think this would be fairly straight-forward to do; and would require computation time that is negligible compared to what’s already being done. It’s a flexibility I’ve thought about adding to my Farkle analysis tools, but haven’t, as yet, had sufficient motivation to pursue it.

  3. kasi says:

    Just a heads up to anyone else who’s confused by this:

    There’s an error below “Optimal Strategy Case: b=0,d=0,f=0,e=0”, where the win probabilities are listed as:

    I felt really stupid when I couldn’t figure out how n could be 5 for all three actions, but I looked up the numbers in the table and it’s simply supposed to be:

  4. kiss says:

    So in conclusion, I do what?

    • matt says:

      If what you’re asking is, “how the devil am I supposed to use all this to improve my farkle game play?”, then you’re right: although this article may be technically interesting to some, it is not terribly accessible if you’re interest is improving your farkle play.

      Todd Neller and I wrote about a technique where you can closely approximate a maximum scoring strategy. For the rule set we used, the technique actually perfectly reproduces the maximum scoring strategy. Depending on the scoring rules, I suspect our technique may sometimes introduce small deviations from the true maximum scoring strategy, but these will certainly be rare, and can only introduce small reductions in expected score when they occur.

      See section 4 of our article on optimal farkle play. Skip down to the paragraph that starts, “We have devised a means by which a human can play the maximum scoring
      strategy perfectly…” That table V(n,t) provided is only good for the simple (and rarely used) rules described in our paper. But you can use my farkle strategy generator to generate max-score-strategies for your exact rule set. Then click on the button E(S,N). The table revealed is the same table as V(n,t) described in our paper, except that is tuned for your rule set. To generate the estimation table, simply round each entry UP to the next 50-point score point. So for example if E(S,N) is 139.951, round it up to 150. Replace all banking states with the value 0. Then as you scan down each column, write down the scores where the value changes from one 50 point value to the next. These are the break points you have to memorize. Put this information in the same layout as described in our paper, memorize that table and follow the instructions we give there.

      This will easily let you play the max-score strategy (or at least something very close to it). In our paper, we also describe go-for-it regions where you or you’re opponent are so close to going out, that it pays to just keep rolling until you’ve won or you’ve farkled. I currently do not provide a tool to identify these regions for you. I could possibly work on this if there’s significant interest, but my time is currently very limited.

  5. Matt says:

    Absolutely wonderful! I’m really happy to read this and to see the page with the strategy generator. Would love to see more things on Farkle. It’s quite fascinating. Thank you for this.

Leave a Reply

Your email address will not be published. Required fields are marked *


Your comments will not appear until I've had a chance to screen them. This usually takes a day or less, but could be longer if I'm canoeing or camping or am otherwise beyond the reach of the internet. I respond to all questions.