Building Mahjong

Published December 15th, 2021

As the boredom of quarantine sets in, I embarked on a project to build multiplayer Mahjong as a web app so I can play with my friends. Read about the rules, my design, and some challenges of the implementation!

Contents

  1. Introduction
  2. How is Mahjong Played?
  3. Design and Implementation
  4. Conclusion

Introduction

Mahjong is a tile-based game originating in 19th-century China. It's played with 4 players, and is highly strategic. Somewhere down the line, a Solitaire-based version of the game emerged, involving a single player selecting identical uncovered tiles to take them off the board. It was surprisingly difficult to find a good online version of the traditional game. Everywhere I search, I find Mahjong Solitaire. Thus, I set out to build it myself.

How is Mahjong Played?

There are countless variations of Mahjong, so my explanation of the rules is bound to upset at least some portion of the Mahjong community. I will talk about a simple variation that I play and have implemented. I will also only discuss the "practical" aspects of the game, and not any of the complicated formalities in dealing and shuffling.

Tiles

Standard Mahjong tiles. Mahjong tiles by Cangjie6 is licensed under CC BY-SA 4.0.

There are a total of 136 tiles, divided among 5 suits. The dots, characters, and bamboo suits have 9 ranks each, with 4 identical tiles for each rank. The dragon and wind suits have 3 and 4 types of tiles, respecticely, with each type having 4 identical tiles. There are more special tiles used in other variations of Mahjong; check out this page to learn more.

Rules

Mahjong is a turn-based game, with the turn going counter-clockwise. There is an intricate (dare I say, superstitious) shuffling process that I won't go into. A hand is 13 tiles, initially completely concealed. During a player's turn, they draw a tile from the "wall" (deck), and discard one of their choice. The goal is to obtain certain combinations of tiles, called melds.

Melds. Left: pong, right: chow (5, 6, 7).

3 identical tiles forms a pong. 3 tiles of the same suit in consecutive rank forms a chow. Note that dragon and wind suits cannot create chows since those tiles don't have ranks. Finally, 2 identical tiles forms a pair.

The objective of the game is to create a hand with 4 chows/pongs and 1 pair with 14 tiles. In many variations, players can also win with 7 pairs, though this is incredibly rare and is not something I included in my implementation. Notice that because a hand is 13 tiles, players must draw or "steal" a tile to complete a winning hand.

A winning hand. From left to right: chow (5, 6, 7 characters), chow (4, 5, 6 dots), chow (3, 4, 5 dots), pair (4 bamboo), chow (4, 5, 6 bamboo).

Stealing is an integral part of the game. Players can "steal" the discarded tiles from other players if they can create a chow/pong/win by stealing that tile. The stealing player must expose the created meld or victory. Exposed tiles cannot be discarded afterwards.

Since multiple steals may be possible by different players for any discard, there is an order of priority.

  1. Win: stealing to win has highest priority
  2. Pong: since it requires 3 identical tiles and there are only 4 of each tile, there can only be 1 pong for any discard.
  3. Chow: a tile can form a chow with tiles from multiple players. Thus, only the player directly after the discarder is eligible to chow.

Design and Implementation

Architecture

Like any game, the bulk of it involves players making actions and receiving game state updates. I used a hybrid REST + Socket.io API architecture on Express, a React client, all written in Typescript for that sweet ~object-oriented programming~. All server state will be held in memory, no need for a database.

High-level architecture

Game State

I will be holding all state in memory. These games are played in real-time anyways, so there no need to persist data. To maintain the state of lobbies and games, I built several object classes.

export default class Room {
  code: string;
  players: Player[];
  leader?: Player;
  deck: Tile[];
  turn: number;
  pendingAction?: ActionIntent;
  winner: number;
 
  private static rooms: Map = new Map();
 
  // ...
}
export default class Player {
  id: string;
  username: string;
  room?: Room;
  handConcealed: Tile[];
  handExposed: Tile[][];
  discarded: Tile[];
  socket?: Socket;

  private static players: Map = new Map();

  // ...
}

The main role of the server logic itself is to receive requests from users (e.g. play this tile in my hand), update the central game state, and emit updates to other players in the lobby.

Challenges

Win Condition

The first main challenge was determining whether or not a hand is winning. After perusing it for a bit, I decided there was no simple, elegant algorithm for this. For instance, 1, 2, 2, 3, 3, 4 forms 2 melds: 1, 2, 3 and 2, 3, 4. The other challenge is that tiles may participate in multiple melds, but perhaps only one configuration leads to victory. Consider 2, 3, 4, 4, 5, 6. Should the 4's participate in a pair, or should 2 consecutive melds be formed?

I approached this recursively: try every possible meld that we can make with the given hand, and ask whether or not the remaining tiles are enough to finish the winning hand. At face value, the complexity of this algorithm seems atrocious. In practicality, the depth of this recursion never exceeds 4, and each hand likely contains few combinations of tiles that form potential melds. I have also considered memoization for dynamic programming, but it works well enough that I haven't found the need for this optimization.

Window of Opportunity

Mahjong is slightly different from many other games in that after a player discards, there is a time period in which others have the opportunity to steal the tile. There is also a challenge in handling multiple steals in order of priority.

The server maintains an ActionIntent object that represents the current pending action. After a certain amount of time without interruption, the action will be finalized. This allows the pending action to be cancelled if a higher priority action (e.g. pong over chow) overrides it.

export default class ActionIntent {
  username: string;
  action: Action;
  tile: Tile;
  timeout: NodeJS.Timeout;
  executionTime: number;

  ...
}

Conclusion

This project has been a great exercise in both design and algorithms :) I plan on maintaining this in the long term. Feel free to play with friends, check out the code, and let me know if you find any bugs!