Board games & Distributed Systems

As the monthly gathering with friends, we headed to a board-game cafe to kill the Saturday afternoon. While we lost direction in a variety of games, the staff suggested us to play Cryptid. From the staff, we heard that to be a detective game with the context:

You are all cryptozoologists, trying to be the first to discover definitive proof of a cryptid in the wilds of North America. Each player will be given a unique clue – one piece of crucial information about where the creature lives. When combined, the clues identify a single space on the map – the creature’s habitat. Each player’s clue either states an area where the creature can be found, or where it cannot be found, based on the terrain and structures on the board. The first player to correctly use all of the clues to find the habitat wins the game.

The detective game

Sounds interesting! Opening the box, several large boards were inside to be joined to form the map with hexagon grids. That sums up into 12 x 9 = 108 grids and your clue limit the objective to be within about 40% of the grids. Wile guesses are unlikely to hack it out. What we need is more information but we just can’t disclose our own clue. At the end of the day we are in competitive relation since the first player who find the solution will win the game.

So how do I get other player’s clues? Every player are represented by a distinct color and got a bunch of tokens in disc shape and cubes. These will make up the information to deduce other player’s clues. According to the rule-book:

During the game, you will ask each other questions with the aim of guessing each other’s clues.

To question, place the pawn on a space on the map, and ask any other player ‘Could the creature be here?’ You can choose any space to question, even one which you know could not be the habitat.

The player you questioned must say whether the space could be the habitat according to their clue, and places either a disc or a cube of their color on the selected space, to indicate whether the creature could be there or not. If they placed a cube, you must now also place a cube on a different space which cannot be the habitat according to your clue. The turn now passes to the player on your left.

Sounds reasonable. A player first point to a grid, and ask somebody else. By placing the token on the map, all players can observe the pattern. One extra rule is that if the answer is a cube, then the requester need to place a cube somewhere as well.

The single truth

There must be some additional tokens to be placed, say, a numbered card under each grid so that when we reveal the that card we know whether it is a hit or miss, but there was just nothing remain in the box.

One more question, how does one win the game? I once played Mastermind before, when we make the guess, the host will look at the answer and give the corresponding hints. However, we 5 people are all into this game to search for the cryptid. Nobody even knows the answer. I once thought that there must be some additional tokens to be placed, say, a numbered card under each grid so that when we reveal the that card we know whether it is a hit or miss, but there was just nothing remain in the box. How can we even guess?

To search, place a pawn on a space on the map which could be the habitat according to your clue, and declare a search.

You must immediately place one of your own discs on the space. Moving clockwise, ask each other player whether, according to their clue, the creature could be there. They must place a cube or a disc on the space accordingly, unless one of their discs is already on the space, in which case they pass their turn to the player on their left.

As soon as one player places a cube, everyone stops. No one else makes a declaration, and you must now place a cube on a different space which cannot be the habitat according to your clue. The turn now passes to the player on your left.

If nobody places a cube, you have correctly identified the habitat and won the game!

Since players must be honest in placing either a disc (possible habitat) or a cube (impossible habitat), asking everyone in the game essentially lead to a consensus! This is done without additional cards or tokens to be placed as the single truth! Everyone has their own knowledge and only exchange information by answering yes/ no. It is simply amazing.

The distributed system

We always think distributed system in a very complex way that do not reveal the underlying deadly simple rules. When we are too focused on such as master-follower election and disaster recovery, our brain become overloaded in algorithms or networking.

As what was written in the previous article (Mobx-keystone: Road to domain-driven design), a multiplayer game is essentially a distributed systems. Studying distributed system could be fun. Just move the game on the board to the web by setting up metaphors. Metaphors are the precious medium of abstraction. Compared to generalization, metaphors works subjective rather rationally. I found it easier to project our thoughts to the digital world.

Imagine each player is a server, with each the holds a distinct piece of knowledge. All of them could observe the map consists of grids, which implies that a grid is the unit of resource. These grids are most likely centralized in a master server for coordination. If a player’s turn is represented by a RESTful API call to that master, then it would be either an “ask player” or a “search” request.

The rules for “ask player” request are straight forward. If there is already any cubes on the grid, return 403 bad request. This is done by the master server because it holds the grid status internally. Note that the grid should not contain any token from the target player because there is no reason to ask under such condition.

Once the request is verified, the master server will ask the target player provided the status of that grid by RPC, which return a boolean. Value of true equivalent to the disc and false for the cube to be placed by the master server, updating the map. If the result is a cube, then the player may need to place a cube for him. Note that the master server cannot verify any disc/cube decisions because it do not have that knowledge. On the other hand, the master need to notify all players about the new state of grid to synchronize their view.

Similarly, the “search” request is handled by additional trips of asking and synchronize final state of the grid among all players. It is worthwhile to mention that according the game rules, a pub-sub to let all players to guess does not match with the rule: The asking is done one by one in a predefined order.

The implication

We already confirmed the contract. The contract is implementation-independent: Thousands ways you could think of will functionally converge into the same piece of game. Let’s first talk about the master server. As I discussed only the master server contains the current state of grid, its role is not actually that central indeed. The main difference between the master server and the follower server are:

• Master server places the token on grid
  This may imply that it has the write access to the database
• Master server is able to do RPC to individual server and send global notification

Then we further break down these individual sub-master roles, we could delegate the notification part to a message queue, and then hand over the overall online status to another service. By doing so, the master server is not much difference from a normal follower server. When the master server “go to toilet”, then another master server could be elected by say for example, ZooKeeper. By the game design, once any player leave the game with his/her secret clue than it become logically impossible to find the sole objective, the cryptid, but all of us know that the network is not that stable all of time.

In the context of domain driven design, then the clue represent a piece of domain knowledge, which lead to physically separated bounded contexts, rather thinking of players to be instances of the same server and being laterally expended. They are unique. To restate, we should be considering n players to be n different services. By the way, the clue that is actually given to you is deadly simple – such as “The habitat is within one space of desert”. I would say it is the starting point of the brainstorm as the Least Knowledge Principle popped up in my mine.

Enjoy board games. Enjoy programming!