README
¶
go-farkle
Solver for optimal play in the Farkle dice game
How to run
Solve the game
cd cmd/solve-farkle
go build
./solve-farkle -logtostderr -num_players 2 -db 2player.db
Play the game using optimal solution
cd cmd/play-farkle
go build
./play-farkle -num_players 2 -db ../solve-farkle/2player.db
Solution size
Scores are capped at 12,750 (255 * 50) to make the game play finite.
- 2 player: 99,488,250 states, 1.5 GiB
- 3 player: 25,369,503,750 states, 567 GiB
- 4 player: 6.4692235e+12 states, 188 TiB
Documentation
¶
Index ¶
- Constants
- func CalculateScore(held Roll) uint8
- func GetRollID(roll Roll) uint16
- func IsFarkle(roll Roll) bool
- func IsValidHold(roll, held Roll) bool
- func IterGameStates(numPlayers int, path string) (iter.Seq2[uint64, GameState], error)
- func SaveGameStates(states iter.Seq2[uint64, GameState], path string) error
- func SortedGameStates(numPlayers int, workDir string) iter.Seq2[uint64, GameState]
- func UpdateAll(db DB, states iter.Seq2[uint64, GameState], chkpntPath string)
- type Action
- type DB
- type FileDB
- type GameState
- type Roll
- type Trick
- type TrickType
- type WeightedRoll
Constants ¶
const MaxNumDice = 6
Variables ¶
This section is empty.
Functions ¶
func CalculateScore ¶
func IsValidHold ¶
func IterGameStates ¶
Return an iterator over all game states in the given file.
func SaveGameStates ¶
Save all game states from the given iterator to a file.
func SortedGameStates ¶
Return an iterator over all distinct game states and their depth in the game tree. Game states are sorted by depth in descending order such that end game states are enumerated before early game states.
Types ¶
type Action ¶
Action is the choice made by a player after rolling. A zero Action is a Farkle.
func SelectAction ¶
Find the action that maximizes current player win probability.
type FileDB ¶
type FileDB struct {
// contains filtered or unexported fields
}
DB that stores results in a memory-mapped flat file.
func (*FileDB) NumPlayers ¶
type GameState ¶
type GameState struct {
ScoreThisRound uint8
NumDiceToRoll uint8
NumPlayers uint8
PlayerScores [maxNumPlayers]uint8
}
State of the game. The current player is always player 0. Game states can be partially ordered since scores can only go up during game play.
func ApplyAction ¶
func GameStateFromBytes ¶
func GameStateFromID ¶
func NewGameState ¶
func (GameState) CurrentPlayerHasWon ¶
Current player has certainly won if they stop now. This is used as an optimization to avoid further traversing the tree, since there is no reason for the player to continue.
func (GameState) CurrentPlayerScore ¶
Score of the current player.
func (GameState) HighestScore ¶
Highest score of any player.
func (GameState) ID ¶
A unique ID for this game state within the set of all possible games with a certain number of players.
func (GameState) IsGameOver ¶
Whether the game is over, i.e. this is a terminal game state.
func (GameState) SerializeTo ¶
type Roll ¶
type Roll [numSides + 1]uint8
Roll represents an unordered roll of N dice. A roll can hold 1 - maxNumDice dice. Extra entries are at the end of the roll with the value -1.
func CombineRolls ¶
func NewRandomRoll ¶
func RepeatedRoll ¶
func SubtractRolls ¶
type WeightedRoll ¶
WeightedRoll represents an unordered set of rolled dice, and the probability of realizing that combination.
Source Files
Directories