Emergent complexity from simple specs with Hive

Even the simplest specifications, when combined, can give rise to complex behavior and unexpected edge cases. This is the mechanic that both makes testers’ work challenging and board games fun. The game Hive is a great example of this (I recommend the pocket edition). It seemed like a fun exercise to look at each piece, layer on rules one by one, and see how the test cases one might come up with get more and more complex.

The Queen

First piece: the Queen occupies a single hex on a hexagonal grid. She can move one space each turn.

This might be trivial so far, but we can already start coming up with questions (and each question could be a test case):

• Does moving one space mean jumping to any space, or only to adjacent pieces?
• What does “adjacent” mean?
• Can she double back onto the space she just left?
• Does the rotation of the piece matter?
• Is there a limit to how far she can go in any one direction?
• Are all six directions the same?

Even the simplest, least interesting version of this game can generate many questions. This is a good skill for a tester to practice.

Clarifying the rules a bit based on those questions: the Queen can move to any of the six hexes that shares an edge with her current space. She can double back on her next turn,the orientation of the piece doesn’t matter, and she can keep going forever in any direction if she wants.

Adding a second player

Let’s add a second Queen.

Now what questions come up? What has changed? We no longer have symmetry in every direction, so the most obvious ones would be:

• Can one Queen move away from the other, leaving an empty space between them?
• Can one Queen move into the same space as the other?

And, if we’re thinking ahead:

• Does answer to either depend on the other piece being a Queen?

In this game, the answer to all three is “no”. In fact, we can generalize this and say that the hive (the collection of all pieces in play) must remain as a single continuous group at all times. (Are you already thinking of ways to testing what “at all times” means?) Now our queen is much more restricted in where she can move, and we start to have a game on our hands.

Let’s take this further.

Adding more pieces

Even before we start to add other ways of moving, we can start to anticipate questions purely around what movement is valid. Here’s one:

Can the queen move one space directly to the right?

Can the Queen move into the center of that ring in any number of moves?

Can the Queen move out of that ring?

The Beetle

I’m not going to go through every piece in the game, but I will add one more: The Beetle.

The Beetle much moves like the Queen — one space at a time — but an important exception: The Beetle can move into the same space as another piece by climbing on top of it.

This opens up a whole new dimension!

• Can the piece beneath it still move? If so, does it carry the Beetle with it or leave it behind?
• Can the Beetle move from on top of one piece to the top of another?
• Can the Beetle climb from the top of one piece onto a Beetle that is already on top of something else?
• Can the Beetle climb from the ground level directly onto a Beetle on top of something else?
• Is there any height limit on how the Beetle can climb and still count as one move?
• Can the Beetle climb down into an empty space that is otherwise inaccessible?

We start seeing an explosion of possibilities with just the addition of one new variable. This is the sort of change that, if we’re not careful, could end up more than doubling the number of tests we want to do. We actually thought we had explored all the things the Beetle could do, and yet when I starting looking the game up online I found more and more layouts of pieces that I hadn’t yet even thought about.

Can the Beetle climb directly forward into that space?

Even more to consider

What other interactions and clarifications can you think of as you consider adding each one of these new pieces?

• A Spider that can move 3 spaces at a time instead of 1;
• An Ant that can move any number of spaces;
• A Grasshopper that can jump over other tiles to land in an empty space on the other side;
• A ladybug that can move 3 spaces (like a Spider), but the first two must be on top of other bugs (like a Beetle);
• A Pillbug that can pick up a neighbouring piece and put it down in another empty space;
• A Mosquito that takes on the movement rules of any piece it touches.

Play and exploration

With 11 pieces per player, 5 different types of movement, and an infinite grid, how many combinations of play are there? Certainly more than you’d ever be able to check exhaustively. Include the three pieces each from the expansion packs—one of which changes its movement rules depending on where it is—and it gets even more ridiculous.

However, there’s probably a more reasonable number of interesting board states. Various states representing a unique situation and attempted move that you could deem valid or invalid move. Since the game was released almost 20 years ago and is popular enough to have world championships, there are probably no more ambiguous situations that require a rule clarification. Nonetheless, I don’t think you’d be satisfied testing this game by just enumerating all the interesting combinations to check. How would you know when you’ve really thought of all of them?

Even after playing the game dozens of times, even after I had started to think about it in this context of generating test cases, we still discovered scenarios I had not thought of yet. The most interesting ones sneak up on you in the course of play. This is why Exploratory testing is so important.

Here’s a situation that we didn’t discover until a couple weeks in:

The win condition for the game is to surround the opponent’s Queen with a piece of either colour on all six sides. In this case, I could have moved a piece in to fill the last gap, but if I did it would also surround my own queen. Did it mean a stalemate? Did I win by virtue of being the one to land the final blow? Did my opponent win because I effectively killed my own Queen?

Turns out this case eluded the designers as well. There was nothing in the rules resolving this one. Online, the two of us far from the first to discover this, the consensus was that it meant a draw.

Game over.