24 August 2016

When writing my Splendor server, the first thing I worked on was implementing the rules for the actual board game. Since the purpose is to be running on a web server, I needed to make sure that it's possible for the program to suspend a game until the user has given it enough information to proceed (like what their turn should be). This is a problem that you might not have if you're writing a game that runs locally. For example, one of the things I wrote when I first started programming was a simple text-based game of chess. In order to interact with the user, I could just read from stdin. That kind of input doesn't directly work in the setting of a web server, so what does?

Well, before I get to answering that question, let's think about the type of state that is kept over the course of a game of Splendor. If you aren't familiar with the game, you can read the rules and mostly follow along. The most obvious things are what's visible on the board:

  • How many chips of each color are available
  • What cards are available to buy
  • How many cards are in each deck
  • What nobles are available
  • For each player:
    • How many chips of each color they have
    • What cards they've bought
    • What cards they've reserved
    • What nobles they've acquired

Now, what defines a card? It has a price, a color (of the gem it produces), and a point value. Similarly, nobles have a card requirement and a point value. Nobles are always three points, but we'll have that be a property of the noble rather than a property of the rules.

newtype CardId = CardId Int
newtype NobleId = NobleId Int

data Color
    = Red
    | Green
    | Blue
    | White
    | Black

data ChipType
    = Basic Color
    | Gold

data Card
    = Card
        { _cardId :: CardId
        , _cardColor :: Color
        , _cardPoints :: Int
        , _cardCost :: Map Color Int
        }

data Noble
    = Noble
        { _nobleId :: NobleId
        , _nobleRequirement :: Map Color Int
        , _noblePoints :: Int
        }

data PlayerState
    = PlayerState
        { _heldChips :: Map ChipType Int
        , _ownedCards :: [Card]
        , _ownedCardCounts :: Map Color Int
        , _reservedCards :: [Card]
        , _ownedNobles :: [Noble]
        , _currentVP :: Int
        }

data TierState
    = TierState
        { _availableCards :: [Card]
        , _tierDeck :: [Card]
        }

data GameState
    = GameState
        { _numPlayers :: Int
        , _playerStates :: Vector PlayerState
        , _availableChips :: Map ChipType Int
        , _availableNobles :: [Noble]
        , _tier1State :: TierState
        , _tier2State :: TierState
        , _tier3State :: TierState
        }

So now let's think about how we're going to implement game logic. The way that I tend to think about board games is that each player takes their turn in order, and a turn can be composed of several steps. In Splendor, turns are usually a single step, but if you would end your turn with more than ten chips, you need to discard down to ten, and if you qualify for multiple nobles at the same time, you need to select one of them.

If we were writing the game synchronously, we might try something like this (in imperative pseudo-code):

def mainLoop():
    while (not gameEnded()):
        action = getAction(currentPlayer)
        performAction(action)
        if totalChips > 10:
            discards = getDiscards(currentPlayer)
            performDiscards(discards)
        currentPlayer = (currentPlayer+1) % numPlayers
    return determineWinner()

def performAction(action):
    // do stuff
    if length(qualifyingNobles) > 1:
        selectedNoble = getSelectedNoble(currentPlayer)
        acquireNoble(selectedNoble)
    // do more stuff

This code assumes two things. First, that the state of the game is implicitly available and modifiable. Second, that we're able to get input from the user and then continue the code from the same place. Can we make something like that in Haskell?

Accessing and modifying state

The first part isn't too bad. If we had a state of type s (which will look like the GameState type we defined above), then a function taking a value of type a and returning a value of type b as well as using that state can be represented as a function of type a -> s -> (b, s). That is, it takes its input and an initial state, then returns its output along with the new state. A stateful computation with no inputs but returns a value of type b is then a function of type s -> (b, s). In Haskell this type has been given the name State s b.

We'll want to be able to chain stateful computations together. That is, if we have a stateful function that takes a as input and returns b, and another one that takes b as input and returns c, we should be able to combine them into a single function that takes a and returns c, with the state being threaded through as appropriate:

chain :: (a -> s -> (b, s)) -> (b -> s -> (c, s)) -> a -> s -> (c, s)
chain f g a s0 =
    let (b, s1) = f a s0
    in g b s1

You might notice that the a value doesn't really serve a purpose other than to be passed to f, so we might just say that the caller can do that themselves, and simplify the first type to just a State s b value (In actual Haskell, State s b is a newtype around s -> (b, s), so we'll use the explicit functions for ease of illustration):

chain' :: (s -> (b, s)) -> (b -> s -> (c, s)) -> s -> (c, s)
chain' f g s0 =
    let (b, s1) = f s0
    in g b s1

The other thing we might want to do is to think of a plain value as a stateful computation that ignores the state:

pure :: b -> s -> (b, s)
pure b s = (b, s)

These two together make stateful computations a monad, which allows us to use Haskell's do notation. If we define a few helper functions, we can write code like this:

set :: s -> State s ()
set s _ = ((), s)

modify :: (s -> s) -> State s ()
modify f s = ((), f s)

get :: State s s
get s = (s, s)

example :: State Int Int
example = do
    modify (*2)
    modify (+1)
    x <- get
    set (x * x)
    get

With the combinators from lens, we can also easily modify smaller pieces of the state (this is a simplified version of the actual code):

takeChips :: Maybe Color -> Maybe Color -> Maybe Color -> State GameState ()
takeChips c1 c2 c3 = do
    chipSupply <- use availableChips
    let colorSet = nub . catMaybes $ [c1, c2, c3]
    for_ colorSet $ \c -> do
        availableChips . at (Basic c) .= Just (colorSupply - 1)
        playerStates . ix curTurn . heldChips . at (Basic c) %= withDefault 0 (+1)

withDefault :: a -> (a -> b) -> Maybe a -> Maybe b
withDefault def f = Just . f . fromMaybe def

Only allowing legal moves

But there's no legality checking! So in addition to accessing and modifying the state, we also want to be able to abort the computation to signify an illegal action. So instead of s -> (a, s), we want computations of the form s -> Maybe (a, s). How could we chain those together? If the first computation aborts, we should abort without even attempting to run the second computation:

chain'' :: (s -> Maybe (a, s)) -> (a -> s -> Maybe (b, s)) -> s -> Maybe (b, s)
chain'' f g s0 =
    case f s0 of
        Nothing -> Nothing
        Just (a, s1) -> g a s1

This type of stateful computation that can fail also has a name in Haskell already. Instead of s -> Maybe (a, s), we write StateT s Maybe a. just like stateful computations, stateful computations that can fail also form a monad, so again we can use do notation, and all the lens combinators work in this context as well. So we might update takeChips to check that there are enough chips to take:

illegal :: StateT s Maybe a
illegal = lift Nothing

takeChips' :: Maybe Color -> Maybe Color -> Maybe Color -> StateT GameState Maybe ()
takeChips' c1 c2 c3 = do
    chipSupply <- use availableChips
    let colorSet = nub . catMaybes $ [c1, c2, c3]
        availableColorSet =
            filter
                (\c -> fromMaybe 0 (Map.lookup (Basic c) chipSupply) > 0)
                [Red, Green, Blue, White, Black]
    if length colorSet < 3 && length colorSet /= length availableColorSet
    then illegal
    else do
        for_ colorSet $ \c -> do
            let colorSupply = fromMaybe 0 (Map.lookup (Basic c) chipSupply)
            if colorSupply > 0
            then do
                availableChips . at (Basic c) .= Just (colorSupply - 1)
                playerStates . ix curTurn . heldChips . at (Basic c) %= withDefault 0 (+1)
            else illegal

That's pretty nice. We can write code that mostly matches our existing mental model of doing things one after another, with checks every now and then to ensure that the action is a legal play. The techniques so far are good for implementing what happens when an action is taken (the equivalent of performAction in the pseudo-code). Next week we'll take a look at how we might handle getting input from the user.