Visualising complexity

By Gordon Rugg

Note: This article is a slightly edited and updated reblog of one originally posted on the Search Visualizer blog in 2012.

How can you visualise complexity?

It’s a simple-looking question. It invites the response: “That all depends on what you mean by ‘complexity’ and how you measure it”.

This article is about some things that you might mean by “complexity” and about how you can measure them and visualise them. It’s one of those posts that ended up being longer than expected… The core concepts are simple, but unpacking them into their component parts requires a fair number of diagrams. We’ll be exploring the theme of complexity again in later articles, as well as the theme of practical issues affecting visualizations.

This article focuses mainly on board games, to demonstrate the underlying principles. It then looks at real world activities, and some of the issues involved there.

Measuring complexity in board games

There are various well established ways of defining and measuring complexity, such as information theory and Kolmogorov complexity. In this article, I’m focusing on complexity in the sense of the number of possible outcomes from an initial starting point, and how to represent them visually.

Here’s one way you can measure the complexity of chess, without much calculation involved.

You have 32 pieces, plus one board. Some pieces are only represented once on each side (e.g. the king) while others are represented more than once (e.g. bishops and pawns). I’ll ignore that for the first illustration, but return to it later. Here’s a representation of the 32 pieces and the board, with each white box in the illustration representing one piece, and the final plum coloured square representing the board.

There are also rules in chess, whose complexity needs to be factored in. Some rules apply to particular pieces (for example, how knights move) and others don’t (for example, the rule that the white side gets to move first).

We can represent that by adding a box for each rule that applies to a particular piece, and adding another set of boxes for all the other rules.

We’ll start with the four knights, for simplicity. Each knight has the following rules that apply to it.

  1. It moves in a particular way (two squares horizontally or vertically, and then one square at right angles).
  2. It can take an opposing piece if it lands on the square occupied by that piece.

That’s just two rules. We can represent that as follows.

We’ll add two boxes representing these rules above each of the boxes that represents a knight. We’ll use the four boxes on the left to represent the knights; we’ll colour-code them yellow so you can see which ones they are. We’ll colour-code the rules grey.

Next, we can add the bishops. Each bishop also has two rules that apply to it, one about how it moves, and one about how it takes a piece. We’ll colour-code the four bishops light blue.

It’s the same principle for the four rooks, which each have one rule about how they move, and one rule about how they take a piece. (Note for chess players: We’ll treat castling separately, later.)

Next, we’ll add the two kings, which have two rules about directions in which they can move, plus one rule about how they capture pieces. (We’ll treat the rules about check and checkmate separately.)

The two queens also have two rules about how they move, and one rule about how they capture.


Now, the pawns. Each pawn has the following rules which apply to it.

  1. It can move two squares directly forward on its first move.
  2. It can move one square forward if the square in front is empty.
  3. It can take an opposing piece which is one square diagonally away from it and in front of it.
  4. It can take an opposing piece using the en passant move during its first move (I’ve omitted the details for brevity).
  5. If it reaches the far side of the board, it can be promoted to become any type of piece.

That’s five rules, so for each pawn, we’ll add five boxes above it.

We’ll treat the next sixteen white boxes as representing pawns.

The boxes representing rules will be in grey, to distinguish them from the white boxes representing the pawns themselves.

There are also some general rules, about the number of squares on the board, their distribution (alternating between two colours), about castling, about stalemate conditions, about check, etc. Those are shown above the plum coloured square; we’ll assume that there are six of them (the precise number varies depending on whether you treat some of them as being two separate rules or all part of the same rule – for instance, the rules about the colours and distribution of squares).

So chess looks like this.

If you want to be more precise, you can colour code the rules as well as the pieces, so that the rules applying to pawns are coloured differently from the rules applying to knights, and so on.

So that’s one way of showing the complexity of chess.

Using visualisations for comparisons

An advantage of systematic measurement and visualisation is that you are able to compare items directly.

That lets us ask how chess compares to other games.

Here’s what the game of Draughts (“Checkers” in the USA) looks like using the same approach.

This has twelve black pieces and twelve white pieces, with five rules applying to each piece (normal movement, normal capture, promotion if they reach the far side, movement if they are promoted and capture if they are promoted).

The board is the same as a chess board, and there are about as many general rules about which side starts first, etc (again, the precise number depends on which rules you treat as separate and which you treat as parts of the same overall rule).

That shows draughts as much simpler than chess. That’s consistent with what you find if you calculate the possible number of moves in a draughts game compared to the possible number of moves in a chess game – chess is far, far more complex on that metric.

What about the game of Go? Like chess and draughts, it’s a board game, played with black pieces and white pieces. In other respects, though, it’s very different.

There are many more pieces than in chess and draughts:  a total of 361 pieces, consisting of 180 white and 181 black.

The nature of the rules is also different from chess and draughts. In Go, the pieces don’t move once they’ve been put on the board, so there aren’t any rules specific to the individual pieces.

There are about ten overall rules (again, depending on how you structure the definitions, and also on whether you’re using the Chinese or the Japanese version, etc).

So how could we represent this in a diagram? One answer is to use a much bigger diagram, but that leads to logistical difficulties. Another is to use a different notation, but that leads to conceptual difficulties. The next section examines the nature and implications of these difficulties.

Notations, logistics and purposes

One conceptually clean solution is to use exactly the same notation for all three games. That would bring out very vividly the differences in size and in structure between them.

The obvious problem with that is logistical. At the scale we’ve been using so far, the diagram would be about a metre wide.

One obvious response to that problem is to use smaller squares, but that would make the diagrams difficult to read because the squares would need to be tiny – even at half a millimetre per square, the Go diagram wouldn’t fit onto a typical document page.

Another obvious response is to use a different form of scaling – for instance, making each square on the horizontal axis in the diagram represent ten pieces, like this. I’ve only represented the number of pieces, with one square per piece, and not represented the rules, because on that scale they’d be too small to show.

This shows fairly clearly how different the three games are in the number of pieces they use.

However, it’s not completely accurate. One major drawback is that it loses the differences between different types of piece, such as rooks and pawns. Another is that this can’t show the rules, because they’d be too small to see at this scale, and the alternative would be to have an inconsistent scale.

Internal consistency

A cleaner response is to use a different set of conventions – for instance, to have each type of piece represented by a single square – so one square to represent the type “pawn” and another to represent “rook” and so forth. This has the advantage of being internally consistent, rather than being based on nothing more than short-term convenience.

If we do that, then we get some very different diagrams from what we would have got using the two previous responses. As before, the last column represents the “general” rules, and each previous column represents different types of piece (ignoring the distinction between black and white, since each type of white piece obeys the same rules as its white counterpart in these games).

This brings out vividly the minimalism of Go. It only has one type of piece (in two colours, but only one type of piece) and you can’t get much more minimalist than that. However, that doesn’t mean that Go is a simple game. In some ways, it’s very complex. If we measure its complexity in terms of how many different possible games you could play before you run out of new games, then it’s much more complex than either chess or draughts. To represent that, we need to use a different format, because of logistics.

The number of possible games of chess, draughts or Go is enormous. There are various estimates; I’m focusing on the underlying concepts rather than the precise numbers. Some numbers that I’ve seen quoted are as follows.

Draughts: 1020 possible games

Chess: 1040 possible games

Go: 10700 possible games

This is a standard mathematical representation, and it’s unfortunately one which is easy to misunderstand. To non-mathematicians, it looks as if there are twice as many possible chess games as draughts games, and thirty-five times as many possible Go games as draughts games. That’s a misinterpretation. Here’s what those notations actually mean.

Unpacking the numbers from the mathematical notation helps to show that the difference is big. However, even this unpacking doesn’t begin to show how big the difference is. Most human beings have trouble grasping just what that number of zeroes means.

Here’s an example.

We’ll use one of the oak leaves in the foreground of this image to represent the number of possible games of draughts.

Let’s say that each oak leaf is 1/10 mm thick and 10 square centimetres in area.

On that scale, of one oak leaf representing the number of possible games of draughts, the number of possible games of chess is enough to fill the first valley in the picture with oak leaves, in a swathe that stretches across the whole area framed by the branches on each side. If you decided that the number of possible games of chess was actually 1042 instead of 1040 then, on the same scale, you’d be talking about enough leaves to blanket everything visible up to the horizon a kilometre deep in leaves. On the same scale, the complexity of Go is beyond what most humans can envisage. The usual comparisons are along the lines of filling the entire universe with grains of sand, or leaves, or whatever you’re using to represent the games, and still not having enough space.

How to represent such big numbers is a fascinating question, that needs an article in its own right. For the moment, we’ll return to more tractable numbers, and to visualizing the complexity of activities other than games.

Carpentry and complexity

Here’s a demonstration of how the principle works. It involves an old copy of Teach Yourself Carpentry from the local second hand book shop. That book’s list of recommended tools for the beginner contains 23 items. It lists half a dozen different types of wood. Some tools are used to work wood; some are used on other tools and materials (for instance, a screwdriver is used on screws, rather than being used directly on the wood).

We can represent this using the same format as with the games, where each of the bottom row of squares represents a different tool, and the rows of squares above them represent what each tool can be applied to. The book doesn’t spell out which types of tool can be applied to which types of wood; I’ve made the simplifying assumption that all six types of wood mentioned in the book can be worked with all of the tools that can be applied to wood. In reality, some tools would only be used on a limited number of types of wood.

Eighteen of the tools in the beginner’s set are for use directly on wood. These are shown in light yellow. There are five other tools in the set, shown in turquoise.

The oilstone is used to sharpen the chisels and the plane-irons (a total of six tools).

The mallet is used on chisels (two types specified in the set).

The pincers are used on nails.

The hammer is used on nails.

The screwdriver is used on screws.

So does this mean that carpentry is less complex than chess?

The answer is no, because we’ve only shown some of the complexity in carpentry. Chess consists of two sets of variables, namely pieces and rules. Carpentry, however, involves three sets of variables – tools, materials and actions. The diagram above only shows tools and materials.

We can use the same representation to show how many separate activities can be carried out using each tool. The exact number will depend on the level of detail that we want to specify. For instance, we could treat the production of the various types of woodworking joint separately, or we could lump them together under “making a woodworking joint”. This approach fits neatly with well-established methods of task analysis, such as using a Therblig notation. We’ll examine this issue in a separate article.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s