Building tractor (升级) as an online card game

April 19, 2020
software tractor shengji rust typescript react

Introduction

This COVID-19 pandemic has left me with lots of free time spent in front of a computer at home. I’d been spending time with my friends playing various videogames online (the Jackbox Party Pack games work reasonably well over Discord or Zoom), and my fiancée suggested that we try to play tractor online… but I couldn’t find one that was easily available over the internet!

What’s tractor, anyways?

Tractor is a trick-taking card game popular in China, played with four or more players and with multiple decks. It’s commonly known as 升级 (“level-up”), 打百分 (“fighting for 100 points”), 四十分 (“forty points”), 八十分 (“eighty points”), or 拖拉機 (“tractor”). You can even find it on Wikipedia! The rules of the game are pretty complicated, and they vary widely: As far as I know, there isn’t a canonical source of rules for the game, at least in English.

For odd numbers of players, there is a variant of the game called 找朋友 (“finding friends”), which adds a team-building aspect to the game. As part of this project, I wrote up the rules that my friends and I usually play with here.

The core of the game is made up of a few phases:

State machine of the game

Why build a new version?

At first, I had no real interest in writing my own version of the game. I did some initial searching on Google, and found that there were once Flash versions, and that a couple of folks had implemented open-source variants of the game. Unfortunately, none of these projects seemed to actually work, and would have required me to set up my own infrastructure as well. I later learned that there is an iPhone app that lets you play online called 多乐升级, but I didn’t know about it at the time – and, it requires you to pay money to play with your friends. Asking people to go download an app written entirely in Chinese, and without Android or non-mobile support seemed like too high a barrier to entry.

Some of my friends suggested trying to play the game via an online deck simulator, e.g. Tabletop Simulator or playingcards.io. Unfortunately, the structure of the game as commonly played (half a deck of cards per person) makes it pretty unwieldy to play online without assistance from the game itself.

Writing a card game simulator is one of those classic introductory programming tasks, though it’s usually in the form of implementing a rudimentary form of blackjack. I figured writing something pretty janky could get me most of the way there.

Writing a simulator for tractor

I worked on this project over a couple of evenings, each with a specific goal. Like many of my personal projects, this bulk of the project is written in Rust.

The whole project is open source, so you can check it out on GitHub. Or, you can just play the game at https://robertying.com/shengji/!

Building the core

Representing cards

There’s a deceptive amount of complexity involved in correctly modeling cards for a game like tractor: not only are there multiple decks, the ordering of the cards and their grouping into suits changes from round to round… and there are jokers to deal with as well! Plus, it’d be nice to not allow any states which shouldn’t be representable in game.

The resulting enums are a little verbose, but having the compiler help out with stuff is pretty nice! Note: derivations and implementations are mostly elided.

pub enum Card {
    Unknown,
    Suited { suit: Suit, number: Number },
    SmallJoker,
    BigJoker,
}

pub enum Suit {
    Clubs,
    Diamonds,
    Spades,
    Hearts,
}

pub enum Number {
    Two,
    Three,
    Four,
    Five,
    Six,
    Seven,
    Eight,
    Nine,
    Ten,
    Jack,
    Queen,
    King,
    Ace,
}

Trumps add a new complication, though: in tractor, the trump suit is defined by a trump number and an optional suit. If no suit is specified, there are five suits in the game! All jokers and cards of the trump number are also part of the trump suit, and not part of the suit they were originally in.

This means that we have to also include another enum to track the “effective” suit of a card, and the current trump specificaton:

pub enum EffectiveSuit {
    Unknown,
    Clubs,
    Diamonds,
    Spades,
    Hearts,
    Trump,
}

pub enum Trump {
    Standard { suit: Suit, number: Number },
    NoTrump { number: Number },
}

impl Trump {
    pub fn effective_suit(self, card: Card) -> EffectiveSuit {
        // ...
    }

    pub fn successor(self, card: Card) -> Vec<Card> {
        // ...
    }

    pub fn compare(self, card1: Card, card2: Card) -> Ordering {
        self.compare_effective(card1, card2)
            .then(card1.as_char().cmp(&card2.as_char()))
    }

    pub fn compare_effective(self, card1: Card, card2: Card) -> Ordering {
        // ...
    }
}

For example if the trump is Trump::Standard { suit: Spades, number: Four }, the order of cards is from highest to lowest is

Basic operations like sorting and comparing cards can only be done by functions which are trump-aware, either by taking in Trump as a variable or by requiring EffectiveSuit rather than Suit. That way, the compiler can keep you from accidentally sorting cards incorrectly.

It might seem a little odd to see successor and two compare* functions defined on Trump: this is because the ordering of cards in tractor includes cards of equivalent sort-order, but which are not intended to compare equal. compare_effective determines the correct ordering of cards for the purposes of the game, while compare is used for sorting the cards for display to the user.

Game state machine

Modeling state machines via session types is pretty easy in Rust, and the nice thing about card games is that there really isn’t that much state to deal with.

pub enum GameState {
    Initialize(InitializePhase),
    Draw(DrawPhase),
    Exchange(ExchangePhase),
    Play(PlayPhase),
}

Each phase exposes a mechanism to transition it to the next phase, or back to initialize if the game is reset.

State transitions

We also encode game settings (set by the user in Initialize) and pass them through all of the phases as PropagatedState:

pub struct PropagatedState {
    game_mode: GameModeSettings,
    hide_landlord_points: bool,
    kitty_size: Option<usize>,
    num_decks: Option<usize>,
    max_player_id: usize,
    players: Vec<Player>,
    observers: Vec<Player>,
    landlord: Option<PlayerID>,
    chat_link: Option<String>,
    kitty_penalty: KittyPenalty,
    throw_penalty: ThrowPenalty,
    hide_played_cards: bool,
    num_games_finished: usize,
}

That way, when the game is reset or completed, we know which settings were set by the game itself, and which ones were explicit overrides by the user.

Drawing cards and bidding

Once the game has “started” (i.e. entered the draw phase), players have hands containing cards, and a sequence of cards in random order to draw from:

pub struct DrawPhase {
    deck: Vec<Card>,
    hands: Hands,
    bids: Vec<Bid>,
    kitty: Vec<Card>,
    // ...
}

impl DrawPhase {
    pub fn draw_card(&mut self, id: PlayerID) -> Result<(), Error> {
        // ...
    }

    pub fn bid(&mut self, id: PlayerID, card: Card, count: usize) -> bool {
        // ...
    }

    pub fn advance(&self, id: PlayerID) -> Result<ExchangePhase, Error> {
        // ...
    }
}

pub struct Hands {
    hands: HashMap<PlayerID, HashMap<Card, usize>>,
    level: Number,
    trump: Option<Trump>,
}

We represent a player’s hand as a map from card to the number of cards in their hand, since this is a useful representation for computing play-validity.

Cards must be drawn in order – even though the cards that each player gets is fully deterministic, the player doesn’t find out about all of them at the same time, and bids are made with limited information.

There are few enough bids available to each player that we can just enumerate all of the valid ones to check if the proposed bid can be accepted.

We can advance to the exchange phase if the deck is empty and there has been at least one bid made. Note: we’ve already separated out the kitty from the deck, so that the remaining game logic is easier to handle.

There are variants of this game where the exchange phase and the draw phase are commingled, so this state machine might change at some point in the future to support that.

Exchanging cards with the kitty and picking friends

Only the current round leader (determined by the exchange phase, or fixed by the initialize phase) can take actions in the exchange phase.

pub struct ExchangePhase {
    game_mode: GameMode,
    hands: Hands,
    kitty: Vec<Card>,
    kitty_size: usize,
    landlord: PlayerID,
    trump: Trump,
    // ...
}

impl ExchangePhase {
    pub fn move_card_to_kitty(
        &mut self,
        id: PlayerID,
        card: Card
    ) -> Result<(), Error> {
        // ...
    }

    pub fn move_card_to_hand(
        &mut self,
        id: PlayerID,
        card: Card
    ) -> Result<(), Error> {
        // ...
    }

    pub fn set_friends(
        &mut self,
        id: PlayerID,
        iter: impl IntoIterator<Item = Friend>,
    ) -> Result<(), Error> {
        // ...
    }

    pub fn advance(&self, id: PlayerID) -> Result<PlayPhase, Error> {
        // ...
    }
}

pub enum GameMode {
    Tractor,
    FindingFriends {
        num_friends: usize,
        friends: Vec<Friend>,
    },
}

pub struct Friend {
    card: Card,
    skip: usize,
    // ...
}

For tractor, the only thing that they need to do is determine what cards they should keep in the kitty vs. their hand. For finding friends, they’re required to also specify their friends (defined by a specific card, and the number of that card to ignore before assigning the friend).

Playing the game and handling tricks

The bulk of the actual gameplay occurs during the Play phase, so we end up with a bunch more state:

pub struct PlayPhase {
    game_mode: GameMode,
    hands: Hands,
    points: HashMap<PlayerID, Vec<Card>>,
    penalties: HashMap<PlayerID, usize>,
    kitty: Vec<Card>,
    landlord: PlayerID,
    landlords_team: Vec<PlayerID>,
    trick: Trick,
    // ...
}

impl PlayPhase {
    pub fn play_cards(
        &mut self,
        id: PlayerID,
        cards: &[Card],
    ) -> Result<_, Error> {
        // ...
    }

    pub fn take_back_cards(&mut self, id: PlayerID) -> Result<(), Error> {
        // ...
    }

    pub fn finish_trick(&mut self) -> Result<_, Error> {
        // ...
    } 

    pub fn finish_game(&self) -> Result<(InitializePhase, _), Error> {
        // ...
    }
}

We now need to keep track of points and play penalties for each player, and track the trick’s state as each player plays their cards.

Trick state machine

Most of the complexity here comes from determining the trick-format for the trick, and determining whether the cards played are legal within the current game-state.

pub struct Trick {
    player_queue: VecDeque<PlayerID>,
    played_cards: Vec<PlayedCards>,
    trick_format: Option<TrickFormat>,
    // ...
}

impl Trick {
    pub fn play_cards<'a, 'b>(
        &mut self,
        id: PlayerID,
        hands: &'a mut Hands,
        cards: &'b [Card],
    ) -> Result<_, TrickError> {
        // ...
    }

    pub fn take_back(
        &mut self,
        id: PlayerID,
        hands: &'_ mut Hands
    ) -> Result<(), TrickError> {
        // ...
    }

    pub fn complete(&self) -> Result<TrickEnded, TrickError> {
        // ...
    }
}

pub struct PlayedCards {
    id: PlayerID,
    cards: Vec<Card>,
    bad_throw_cards: Vec<Card>,
    better_player: Option<PlayerID>,
}

pub struct TrickEnded {
    winner: PlayerID,
    points: Vec<Card>,
    // ...
}

The trick is initialized with the sequence of players who need to play, and is complete when the player_queue is empty. As players play cards, they are removed from the player_queue and the cards they have played are added to the played_cards, updating the current state of the player’s hand.

Finding the trick format

Unfortunately, determining the trick-format given a set of cards is actually an ambiguous problem. There are two types of trick unit-types, and then there’s the meta-type of a “throw” that combines an arbitrary number of units.

enum UnitLike {
    Tractor { count: usize, length: usize },
    Repeated { count: usize },
}

Repeated units are tuples of identical cards, and tractors are sequences of consecutive tuples of length two or greater. In general, tractors are considered “better” than repeated units, so the parsing problem in the common case of two decks is pretty straightforward: take all of the 1-tuples and 2-tuples, find any 2-tuples that are consecutive, and convert them into tractors.

With more than two decks, though, things get more complicated:

For example, if there are three decks, the interpretation of 2-2-3-3-3 can be either [[2, 2, 3, 3], 3] or [[2, 2], [3, 3, 3]]. To resolve this ambiguity, the implementation does a search through the potential unit-allocations and finds all of the viable possibilities, and then picks the one which has the highest maximum unit size.

This is not ideal, but it keeps the interface simple, and playing ambiguous card-sets is not particularly common.

Matching the trick format

After the trick format is set, all of the other players are required to follow the format as best they can. Validating that they have actually done so is a bit of a tricky problem: in some sense, we want to force the cards which are as close as possible to the desired format to be played.

The current implementation relies on decomposition:

while let Some(mut requirement) = requirements.pop() {
    // If it's a match, we're good!
    let play_matches = UnitLike::check_play(...);
    if play_matches {
        return true;
    }
    // Otherwise, if it could match in the player's hand, it's not OK.
    let hand_can_play = UnitLike::check_play(...);
    if hand_ca_play {
        return false;
    }

    // Otherwise, downgrade the requirements.
    while let Some(unit) = requirement.pop() {
        let decomposed = unit.decompose();
        if !decomposed.is_empty() {
            for subunits in decomposed {
                let mut r = requirement.clone();
                r.extend(subunits);
                requirements.push(r);
            }
            break;
        }
    }
}

// Couldn't meet requirements in either hand or proposed play, so the proposed
// play is legal.

Essentially, the criteria for a “legal” play is one which cannot be better matched by some other combination of cards from the player’s hand. If neither the proposed play nor the player’s hand can match the trick format, the trick format’s requirements are reduced until there are none left.

There’s a fast-path optimization for the case where the proposed player doesn’t have enough cards in the right suit to match the format at all, but in general this computation assumes that players are trying to play legitimately most of the time.

Some variants of the game have “protected” units, e.g. not allowing a pair to draw out a triple. This tends to be difficult to make consistent as the number of decks increases, so it’s not implemented yet.

Finishing the trick

At the end of the trick, the winner is determined by comparing all of the players which successfully matched the trick format. Then, the game updates the friends, points, and penalties appropriately, and initializes the next trick with the winner as the new trick leader.

Finishing the game

At the end of the game, all players’ hands are empty, and the trick is also empty. The game can then total up the points and penalties for each team, and determine the new levels and leader for the next round. It is then set to the Initialize state with new continuation settings.

Backend architecture

The actual server is implemented as a single binary which serves both the static assets (HTML, JS, CSS) and the game API over a websocket, using the warp library as its async service implementation.

Client and server

The client is expected to connect to the websocket and send messages serialized as JSON, and the server responds with full state snapshots for the game that the client is connected to. There’s no direct RPC-like connection between the messages in both directions, which simplifies implementation: the client can effectively just render the current game state at all times.

State management

The server keeps all of its state in a single locked map from room name to the corresponding game state. Each game keeps track of its connected users, and users are identified by their active websocket connection.

type Games = Arc<Mutex<HashMap<String, GameState>>>;

struct GameState {
    game: interactive::InteractiveGame,
    users: HashMap<usize, UserState>,
    // ...
}

The InteractiveGame wrapper effectively just wraps the GameState session type and routes the incoming messages to the appropriate function call using a big match statement:

match (msg, &mut self.state) {
    (Message::ResetGame, _) => {
        // ...
    }
    (Message::SetChatLink(ref link), _) => {
        // ...
    }
    (Message::StartGame, GameState::Initialize(ref mut state)) => {
        // ...
    }
    (Message::ReorderPlayers(ref players), GameState::Initialize(ref mut state)) => {
        // ...
    }
    (Message::MakeObserver(id), GameState::Initialize(ref mut state)) => {
        // ...
    }
    (Message::MakePlayer(id), GameState::Initialize(ref mut state)) => {
        // ...
    }
    // ...
}

As long as at least one user is connected to the game, the game will not be cleaned up. Once all players have left, and some time has passed, games are garbage collected to reduce overall memory usage.

Since the game doesn’t actually use a database, it periodically dumps the current state-map to disk. On startup, it reads in the state dump and loads the corresponding data into the new state-map. This doesn’t preserve player websocket connections, but is simple and reliable enough for the current use cases.

Logging

The server process is set up as a systemd service with a dedicated user, so stdout and stderr are redirected to the systemd journal. In the Rust code, I used slog to provide key-value structured logging, which was fairly painless. The logs are serialized as JSON by default, and as colored console output for debugging if the appropriate feature flag is specified. This helps balance readability against parseability:

lazy_static::lazy_static! {
    static ref ROOT_LOGGER: Logger = {
        #[cfg(not(feature = "dynamic"))]
        let drain = slog_bunyan::default(std::io::stdout());
        #[cfg(feature = "dynamic")]
        let drain = slog_term::FullFormat::new(slog_term::TermDecorator::new().build()).build();

        Logger::root(
            slog_async::Async::new(drain.fuse()).build().fuse(),
            o!("commit" => env!("VERGEN_SHA_SHORT"))
        )
    };
}

The current commit hash of the compiled code is also included in the logs, so that it’s easy to see what version of the code generated any particular log line.

Frontend code

The frontend is pretty simple, and contains only the bare minimum of game logic: it’s effectively a glorified rendered for the current server state.

As a result, it fits pretty well with the React render mechanism… and also that’s the only frontend framework I remembered how to use at the time. While the components have been factored out a lot more now, the first version basically just jammed the entire game state into a global state variable and drew elements appropriately.

Each frontend component maps pretty much directly to the backend state. The entire game state derives Serialize and Deserialize, so this was pretty easy. Unfortunately, I did not find a good way to automatically generate typescript types from the struct definitions, so they’re currently manually translated to give a bit of type safety to the frontend code.

Generating room IDs

The backend supports pretty much any 16-codepoint unicode sequence as a room name. For simplicity, the frontend generates a random 64-bit number and uses the hex representation of that number as the room name, if one wasn’t already provided.

Playing cards exist in Unicode?

One of the things that made building the frontend much, much easier is that it turns out there are playing card characters in unicode! The graphical display of each card is effectively just taking the card character and making the font-size really big. They end up looking something like this (at least, on Macs):

Cards

Most fonts seem to use card characters of the same relative sizes, so it was pretty easy to overlap the cards by setting a bit of negative margin.

Display Settings

Lots of people have different ideas for what kinds of minor frontend features are helpful to them. For example, auto-draw is pretty universally liked (clicks the draw button for you after a couple hundred milliseconds), but four-color suits and beep-on-your-turn are not everyone’s cup of tea.

Settings

Preferences like these are stored in the browser’s Local Storage and available behind the settings pane.

Weird bits

There’s some funky stuff that goes on with setTimeout and setInterval in modern browsers when the tab is backgrounded. This is annoying if you have four tabs open for debugging, since it limits the speed at which auto-draw actually runs. I worked around this by proxying setTimeout and setInterval to a web worker:

const timers = {};

function fireTimeout(id) {
  this.postMessage({id: id, variant: 'timeout'});
  delete timers[id];
}

function fireInterval(id) {
  this.postMessage({id: id, variant: 'interval'});
}

this.addEventListener('message', function(evt) {
  const data = evt.data;
  switch (data.command) {
    case 'setTimeout':
      const time = parseInt(data.timeout || 0, 10);
      const timer = setTimeout(fireTimeout.bind(null, data.id), time);
      timers[data.id] = timer;
      break;
    case 'setInterval':
      const interval = parseInt(data.interval || 0, 10);
      const handle = setInterval(fireInterval.bind(null, data.id), interval);
      timers[data.id] = handle;
      break;
    case 'clearTimeout':
      const clearTimeoutHandle = timers[data.id];
      if (clearTimeoutHandle) {
        clearTimeout(clearTimeoutHandle);
      }
      delete timers[data.id];
      break;
    case 'clearInterval':
      const clearIntervalHandle = timers[data.id];
      if (clearIntervalHandle) {
        clearInterval(clearIntervalHandle);
      }
      delete timers[data.id];
      break;
  }
});

Apparently web workers get to run at full speed. Who knew?

There’s also a thing where the websocket’s onclose method doesn’t always get called, so the UI appears to just stop working entirely. The internet suggests this is because Chrome doesn’t always call onclose when network conditions change, so for now there’s a workaround where we expect a new message from the websocket within a few seconds of any communication, and the connection is presumed dead if it doesn’t appear.

Metrics

It turns out that there’s actually pretty decent demand for an online version of tractor within my extended friend groups! It’s mostly been shared via word of mouth, and I only have data from the last week or so, but it’s fun to see that people are actually playing almost every day:

Number of simultaneous games

and that they’re playing for an extended period of time each day:

Number of games completed per room

Each color in the above chart is unique room, and the y-axis is the number of games they’ve finished in that session.

The structured logging from the backend is ingested into Honeycomb, which makes it easy to see how things are going with the service without any client-side cookies or persistent user accounts.


If you thought all this was interesting, consider contributing on GitHub or playing a few games with your friends!

Silly Formatting 3: readline and canonical input modes

May 4, 2020
software rust sillyfmt readline unix macos

Silly Formatting 2

March 6, 2020
software rust parsers wasm stdweb sillyfmt fuzzing

Silly Formatting

January 31, 2020
software rust parsers sillyfmt