go-farkle: Solving a Push-Your-Luck Dice Game
After Yahtzee and Exploding Kittens, the next game to get this treatment was Farkle. The result is go-farkle, which computes optimal play for the two-player game and will happily tell you that the roll you were about to bank is worth another throw.
The game
Farkle is played with six dice. On your turn you roll all six. Individual 1s are worth 100 and individual 5s are worth 50; three of a kind is worth 100 times the face value, except three 1s, which are worth 300. There is a small zoo of special combinations—a straight, three pairs, or four of a kind plus a pair are each 1500, five of a kind is 2000, two triplets 2500, six of a kind 3000.
You must set aside at least one scoring die from every roll. Then you choose: bank everything you have accumulated this turn, or roll the dice you did not set aside and try for more. If all six dice have scored, you pick them all back up and keep going with a fresh set. And if a roll contains no scoring dice at all, you farkle: everything accumulated this turn evaporates and play passes to the next player. First to 10,000 wins, with everyone else getting one last turn, and you need 500 in a single turn before you can get on the board at all.
That is the whole game, and the whole game is one decision made over and over: roll again, or stop. Greedily maximizing expected points is not the right answer, because points are not what you are trying to maximize. Whether you should take a 1-in-3 chance of losing 2,000 accumulated points depends on whether your opponent is at 1,200 or at 9,650.
The solver
So the value of a position is a probability of winning, not a score, and it depends on the whole table. A state is: the banked score of every player, the points accumulated so far this turn, and the number of dice left to roll. Scores are stored in units of 50 and capped at 12,750 (255 × 50) so each fits in a byte; the current player is always rotated to index 0. The whole state is 7 bytes and maps to a dense integer ID, which indexes a memory-mapped flat file holding, for each state, a win probability per player. With more than two players, the value of a position is a vector rather than a number—it matters not just how likely you are to win, but which opponent is favored if you don’t.
The update is ordinary value iteration. For a given state, average over every possible roll of the remaining dice, weighted by its probability; within each roll, enumerate the legal holds crossed with roll-again-or-bank, and take the action maximizing the current player’s win probability.
The interesting difference from Yahtzee is that this cannot be done with a single backward pass. Yahtzee’s state graph is acyclic—every turn permanently consumes a category, so the game always moves forward and pure backward induction works. Farkle’s graph has cycles: two players can farkle back and forth indefinitely and return to exactly the state they started from, so there is no ordering in which every child is solved before its parent. go-farkle handles this by enumerating states with a depth-first traversal that records each state’s distance from the endgame, using an in-stack bitmask to break the cycles, external-sorting the states by that depth, and then sweeping from the endgame outward, repeatedly, until the values stop moving. The sweeps are parallel across cores and checkpointed by depth, because they take a while.
They also take space. The two-player game has 99,488,250 distinct states, which is a 1.5 GiB table—perfectly reasonable on a laptop. Three players is 25,369,503,750 states and 567 GiB. Four players is 6.5 × 10¹² states and 188 TiB. The table grows roughly as the score range raised to the number of players, which is a compact illustration of why exact solutions run out of room so quickly.
With the two-player database built, play-farkle deals you a game and plays the other side perfectly, and you can watch your win probability move after every decision. As with Yahtzee, the most useful thing it does is disagree with you: the optimal player banks earlier than feels right when it is ahead, and keeps rolling well past the point of comfort when it is behind.
Source is on Github.
