My iOS game based on the maximum clique problem: Find the Mafia!

Months ago I have read an article about how mathematicians constructed pure mathematical models of some classic video-games, and proved them to be NP-complete. Turns out that most of the most successful classic video games are NP-complete (for example Tetris).

Suddenly an idea came to my mind: What about the other direction? Constructing a video game based on a classic NP-complete problem? As those days I was thinking about learning iOS development, I thought something along the lines of this idea could be my first iOS app.

The obvious candidate was my favourite problem: the maximum clique problem: find the biggest complete subgraph of a graph.


Screenshot from the game

This problem is my favourite because I find it so extremely simple on so many levels.

It is very simple mathematically. The concept of graphs require very few concepts, and the mathematical logical description of the maximum clique is a small expression.

It is also very simple to understand by humans. My five year old daughter could understand the rules of the game I have created based on it!


The rules are so simple that the game feels like a classic. Who knows? Maybe the ancient Greeks already played it in the sand.:)

I knew that because the maximum clique problem is much more simple than the mathematical model of classic games, the game created based on it will be probably the puzzle game with the most simple rules ever created.

But I did not know how challenging and how much fun it will be.

I have created a prototype fast, tested it with some of my friends and family members, and it turned out the game is fun, on the appropriate level it can be just as challenging which is still fun, and can be very addicting. My first personal impression was that I was surprised that the game can be so challenging on what I thought to be relatively low levels. I thought finding a 4 node complete graph in a 10 node graph will be always trivial, while it is not!

It also turned out that the game is most fun when playing it on a level where solving cases one after the other can be done relatively quickly, and the challenge is to shorten your average time. (So a core concept of the game design became measuring time. For me personally the game is most fun somewhere at ‘finding 4 nodes in 10 nodes’ (4/10), or as I become better maybe 4/12. My five-year-old daughter plays on 6/3.

It is interesting how different the difficulty of the randomly generated graphs is. For half of the cases I see the solution immediately. For a quarter of them I need to think for a minute or more. (on 4/10).

It is an interesting question that what kind of ability this game measures? I don’t know what it is (some kind of pattern matching), but it feels something quite fundamental. I can imagine that because of its stripped-down rules this game can be a good tool for cognitive psychologists.

If you became interested click on the website of the game with a gameplay video and appstore link on it.


About nadamhu

I am a Hungrarian programmer interested in programming, math and entrepreneurship.
This entry was posted in Uncategorized. Bookmark the permalink.

One Response to My iOS game based on the maximum clique problem: Find the Mafia!

  1. games trace says:

    Hungrarian programmer interested in programming

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s