Monthly Archives: March 2016

For all audiences

Fractals

In case anyone has not already noticed, I love fractals.

I’ve been a few years (two decades!) perfecting my program to paint the Mandelbrot set, but I’m never totally satisfied. There are still many details to polish and I’m always lacking the same ingredient: time!

What I can share is a few samples of the images it can generate. There goes the first one:

m002_espirales_mejillon_474x356

Download in giant format (beware: 12’6 MB)

Wondering what the Mandelbrot set is?

Thousands of web pages and books try to explain it, but I’ll take the opportunity to mention my book, which contains, among other adventures, my best attempt at explaining it.

For the mathematicians:

The Mandelbrot set is the set of points of the complex plane which, used as constant C in the series Zn+1=Zn2+C , where Z0=0 , do not make the length (the Euclidean norm) of Z tend to infinity. The previous image represents a small region of the complex plane. Almost all the points painted in dark blue (at the left) belong to the Mandelbrot set. The points painted in other colours do not belong to the Mandelbrot set. For these latter points, the colour was chosen depending on the n from which the length of Zn is greater than 2. When this happens, we know that the series will tend to infinity, so we stop calculating it. When this doesn’t happen, since we can’t compute indefinitely, we must fix a maximum value for n. From that moment, if the length of Zn didn’t exceed the value 2, we paint the pixel in dark blue and proceed to compute another pixel.

In fact, if I had read the previous paragraph when I had not yet heard of fractals, I would have stayed exactly like before reading it.

For the rest of mortals:

The Mandelbrot set is a mathematical object, just like the circle, the square and the dodecahedron. Nothing more, nothing less. It belongs to Plato’s world of Ideas (or world of forms). As the rest of mathematical things, it doesn’t need a material universe to “be”. It simply “is”. It’s the material world which seems to work according to mathematical laws.

Perhaps this last statement sounds ridiculous to you. Our culture is full of memes ridiculing the scientist who aspires to calculate everything, to explain everything, to predict the future. I’m not really sure if scientists had such pretensions a century ago, or if there is rather an almost vindictive interest to discredit science. The exaggerated faith in science might seem ridiculous from outside. Seen from the outside, any exaggerated faith seems ridiculous. Especially from the point of view of another faith.

The point is that the mistake was thinking that, if the universe obeys mathematical laws, we’ll be able to explain everything and predict the future. Nothing could be further from reality. In fact, nothing could be further from mathematics. There are a few mathematical truths with a huge transcendental importance, which were discovered in the last century, but have only penetrated our culture as mere anecdotes.

One of these transcendental truths is chaos theory. Perhaps you know about it as the “butterfly effect” but that’s just the anecdote, the shocking example used to try to explain something bigger: that to predict the future we’d have to make an overwhelming amount of calculations, and before that we’d need to know the present at an overwhelming level of detail. So overwhelming, that the most efficient way to predict the future accurately is to sit and wait for it. That is, any machine that calculated the future would be bigger and require more time to try to predict it that the material world itself.

Actually it is not a new idea with respect to the material world. It is what humanity has experienced since it walks the Earth. It is the wall blocking the path of those who seek to calculate the future accurately. The novelty is that this also happens in Plato’s world of Ideas. Unpredictability is not due to anything of the material world nor any other metaphysical and unfathomable world we wish to invent. Unpredictability is inherent in the ideal world of mathematics.

Enough for now. There goes another image:

m001_coliflores_electricas_474x474

Download in giant format (beware: 19’2 MB)

In this second picture there hardly is any area that really belongs to the set. They are only a handful of white pixels here and there. In the reduced version you can’t even see them. However, the Mandelbrot set is connected. That is, these small “islands” in the set area are connected by very fine filaments which also belong to the set. These filaments are so twisted that the boundary of the Mandelbrot set has an infinite length. It is a curious fact, since the area of the set is finite.

In this picture we almost see the filaments as pale green lightnings. What we see are not really the filaments themselves, which in many points are infinitely thin. What we see shine are the points close to them. With these values of C, the series takes longer to step out of the circle of radius 2.

Returning to the subject of unpredictability, I’ll present an example:

We know of many points that belong to the Mandelbrot set. We know it with absolute certainty because, with these values of C, the sequence is cyclic. The easiest example is C=0. With this value of C, every value of Z is zero. Another example is C=-1, with which the series oscillates indefinitely between -1 and 0. And yet another example is C=-2, with which the series soon gets stuck at value Z=2.

We also know that, for every C whose length is greater than 2, the series tends to infinity. For C=3, for instance, the values of Z are: 0, 3, 12, 147, 21612, 467078547, 218162369067631000… I will not go into the details, but it can be proven and it is reasonably intuitive.

Nevertheless, for many of the infinite points inside the circle of radius 2, we don’t have a general method to predict in every case whether the series will tend to infinity or not. The only way to find it out is calculating the series, and this is not always in our hand. In many cases, as the calculation progresses, the numbers have more and more digits.

If any value of Z steps out of the circle of radius 2, it’s done: this C does not belong to the set. On the other hand, if any value of Z is exactly equal to a previous one, it’s done: the series cycles, and this value of C does belong to the set. But, what happens if we go on calculating and none of this things happen? We’ll have to stop at some point. We can’t compute indefinitely!

The theory of chaos states that there are mathematical systems that exhibit this behaviour. They are governed by perfectly defined mathematical laws, but the slightest variation in the initial conditions can decisively affect the outcome much later. Furthermore, there’s no shortcut to predict those behaviour changes. The only way is to calculate everything step by step with absolute precision. So much precision that it escapes our possibilities because it gets infinitely larger than the system we wanted to predict in first place. Translated to a material universe ruled by these laws: the only way to predict the future with absolute precision is to sit and wait for it.

Concluding…

All of this sets a limit to what we can calculate and predict, but it poses no obstacle for the universe being a lot of matter/energy set to spin, obeying with absolute precision some predefined mathematical and physical laws, without any outside influence after the Big Bang.

The question is: can some mathematical and physical laws breed everything we see around us?

In this sense, the Mandelbrot set and other fractals are a surprising discovery. They are purely mathematical objects, like the circle or the dodecahedron, yet their shapes resemble living tissues and landscapes.

All of this and more is wonderfully explained in a beautiful BBC documentary called “The Secret Life of Chaos”. It can be easily found on Youtube.

There goes the last image. Of the three, this is the one I like most:

m003_rayos_verdes_474x296

Download in giant format (beware: 23’3 MB)

One last clarification: these images are in part a creation of mine, but that part is very small. The only creative act is the choice of the colours. The shapes are already there. They simply “are”, like the roundness of a circle “is” without the need of me drawing it or even imagining it.

There’s other part in the generation of these images that might look like a creative act, but it’s only discovery: the choice of which part of the Mandelbrot set to zoom into and compute. The Mandelbrot set is there with its infinite complexity, with its infinite filaments and whirlpools. It simply “is”, without the need of me computing it.

For all audiences, Programming

Pickomino

Index

Introduction

This is something I’ve been delaying for too long. Finally I found some time to sit down and write about this fascinating game, to which I dedicated so many hours. It often happens that the urgent things don’t leave time for the important ones. I’ll take a break and share this experience with you.

I started playing one or two games with my work colleagues at coffee time and I ended developing the Artificial Intelligence of the official App. Well, it’s a long story, so I’ll better start with the beginning.

It all started some years ago, when I taught programming in the University of Alcalá. One day a colleague brought a board game in a small cardboard box. Nowadays board games use to come in small boxes, but when I was a child the boxes were as impressive as the prices. Board games were designed to preside the largest piece of furniture in the living room, and for that purpose, first they had to preside the shop windows. Nobody thought that we would be obliged to get rid of the boxes while moving to a closet in the big city.

Whoops, I’m digressing. Martin, focus! The point is that the little game was a pleasant surprise. It turned out to be very funny and interesting.

Return to index

The rules of the game

Dice and tiles
Dice and tiles of the original game

The box contains 16 tiles and 8 dice.

Every tile has a number painted (and carved), along with one or more worms. The numbers range from 21 to 36. The first four tiles (from 21 to 24) have only one worm each. The next four (from 25 to 28) have two worms each, the next four (from 29 to 32) have three worms each, and the last four tiles (from 33 to 36) have four worms each.

The dice are normal except for the detail of having a worm in the side where normally would be the 6. In this game there are no sixes.

The goal of every player is to accumulate tiles. The more worms the better. At the end of the game each player’s worms are counted, and the player with more worms wins.

The game begins with all the tiles arranged in the center of the table. The players take turns to roll the dice and thus earn the tiles. In short I’ll explain how to roll the dice, which is another kettle of fish. The thing is that, with the points obtained in a turn, the player can grab from the center of the table the tile of that number or, if it’s not available, another tile of less value. But there’s more… Every player stacks the earned tiles by his side of the table. The tile on top of the stack is exposed to be stolen from another player who obtains with the dice the exact points of the tile.

It’s not easy to obtain the exact points to steal a tile from another player, but it’s worth to try. At the end of the day, the game is a race to get worms, and if we take them from the opponent, the advantage is double. The question is whether we’ll dare to steal from that dear relative or friend, who won’t precisely smile and give us a hug.

There’s one more little twist regarding the turn. If the dice roll doesn’t meet the criteria required to get a tile (neither from the center of the table nor from other player’s stack), the player looses the last tile obtained, which must be returned to the center of the table. In addition, every time a tile is returned to the center of the table, the most valuable tile in the center must be turned upside down. The tiles upside down are no longer part of the game.

A failed turn is doubly damaging: the player doesn’t get a new tile and besides that he looses one of the tiles earned previously.

The game ends when no tile remains face up on the center of the table.

The rule of turning upside down the most valuable tile helps avoiding the games to last forever. Dice rolls around 36 points are very unlikely, though perfectly possible. In the particular case where the returned tile is also the most valuable, the rule can be applied equally, or an exception can be made, leaving it face up. It’s convenient to reach an agreement regarding this point before starting the game.

Well, now I’ll go for the dice subject. The faces from 1 to 5 are worth 1 to 5 points respectively. Quite normal. The side of the worm is worth 5 points, but it has an additional value that I’ll explain in short.

The player starts rolling the eight dice at once, but the points are not simply added. He has to choose the dice of one of the rolled values, and put them aside. The rest will have to be rolled again. For instance, let’s say that the roll has been { 1, 2, 2, 2, 2, 2, 4, 5 }. There are neither threes nor worms. We can choose to put aside:

  • 1 = 1 point
  • 2 + 2 + 2 + 2 + 2 = 10 points
  • 4 = 4 points
  • 5 = 5 points

But before choosing we must take into account how the rules affect the remaining dice:

  1. We can roll the remaining dice, put aside the dice of another value to add points, and so on until… well, we’ll see until when.
  2. We can’t put aside the dice of a value that we already put aside in this turn. That is, if we put aside a five and then we roll several fives more, we can’t use those fives. We’ll have to pick some other value… ¡if there’s any other value!
  3. We can decide to settle and stop throwing dice when these two requirements are met:
    • that we have enough points to pick a tile from the center or from another player, and…
    • that we have put aside at least one worm (that’s what makes them so valuable!)
  4. If every rolled value fatally coincides with something we already put aside, we loose our turn (and the tile earned more recently).
  5. If no die remains to be rolled and we didn’t obtain any worm or we didn’t obtain enough points, we loose our turn (and the tile earned more recently).

In case there’s still any doubt, I insist: we can’t put aside just a 2 and roll the seven remaining dice. We must take either all the twos or the dice of some other value. We can’t roll the eight dice again. We must put something aside after every dice roll.

Return to index

Analysis of a dice roll

In light of these rules, the roll { 1, 2, 2, 2, 2, 2, 4, 5 } is dreadful. Let’s see our options one by one:

  • Put { 5 } aside and continue with 7 dice. In principle, this looks like the most attractive option: we get 5 points and go on with many dice. But watch out: after this we won’t be able to use any other 5 in this turn, and this limits the points we can expect to obtain with the remaining 7 dice.
  • Put { 4 } aside and continue with 7 dice. We get one less point. We won’t be able to put aside any more fours, but fives yes. This improves the average of points we can obtain with those seven dice.
  • Put { 2, 2, 2, 2, 2 } aside and continue with 3 dice. We get 10 points! But wait a minute…. We need 21 points at least and only three dice remain. In addition, we still need to roll some worm. In the best scenario we’d get a total of 25 points, which is no big deal, and chances are that we’ll loose this turn.
  • Put { 1 } aside and continue with 7 dice. We only get one point, but we preserve the right to use the fours and fives that we could roll with those 7 dice.

According to my calculations the best choice is to put the 4 aside. The probability of failure is under 4%.

The option of taking the 5 follows with a slightly lesser probability of failure, but also a lower benefit on average.

The option of taking the five twos is dreadful since it carries a failure probability around 38%.

Interestingly, the option of taking the 1 follows closely those of the 4 and 5. The probability of failure taking the 1 is greater, but still under 4%. The average benefit is only a bit lower.

The optimal algorithm for winning the game is not easy at all. Specifically, catching always the dice with higher values usually leads to very poor results. This kind of subtlety was what attracted me at first.

Return to index

Artificial Intelligence

Since the very beginning I thought it would be interesting to compute the probabilities and make a program capable of playing Pickomino. I always found that programming the Artificial Intelligence of games is even more interesting than playing. In fact, I’ve dedicated many hours to some other game… I’ll talk about this another day.

The thing is that, at that point of my life, I couldn’t endeavour to do it just for fun. But a few years later, in 2012, I quit my job at the University to move abroad. For at least one year I’d have plenty of time to program whatever I pleased. In 2013, during one of my visits to Spain, I found the game in “Evolution Store”, Calle Manuel Silvela, 8, 28010 Madrid, Tel. 917582563. Free sponsoring, ladies and gentleman! Watch out: some other time I’ve gone to buy it again as a gift for a friend and they didn’t have it. It’s better to call first and ask to be sure.

Well I started programming and got something quite decent. The initial program chose which dice to put aside and whether it should settle or not, but it didn’t take into account which tiles were available. It only played trying to maximize the number of points obtained in a turn. It simulated around 50000 turns per second on my modest notebook (Atom @ 1.6 GHz), failing about one of every four turns and achieving an average of 26 points in the other three.

The final program beats me almost every time. I’ve won some time because luck is critical in this game, but the program uses to win with an advantage of a bunch of worms. But I’m getting ahead of the story… It took me some time to make the program play so well a full game.

How about a nice game of Pickomino?
How about a nice game of Piko Piko?

I did some research on Internet. To start, the game was named “Piko Piko, el gusanito” in Spain, but in other countries it’s called “Pickomino”, “Heckmeck am Bratwurmeck”, “Regenwormen”, “Kac-Kac Kukac”, “Il verme è tratto”, “Polowanie na Robale”…

I found out that the game was invented by Reiner Knizia. And I also found a video in which he mentioned, in a conference in 2011, that an App of the game would be developed, but apparently it was still unpublished.

I sent an email to offer my collaboration and in January 2014 he put me in contact with United Soft Media (USM), with whom he had reached an agreement to develop the application for mobile phones. Great!

A long series of emails followed until summer 2014. I developed a version of the program capable of playing full games, confronting players with different strategies. I perfected the strategies progressively to take into account the state of the game: which tiles are available on the center of the table, and which ones can be stolen, from whom is it more convenient to steal…

Return to index

The App

Pickomino icon
Icon of the Pickomino App

Finally, in April 2015, after a long wait, the App went on sale at the Apple Store and I can now brag about it to my friends. The illustrations follow the same line of the original board game, which I love, and the music and sound effects are very funny. How bad that they still didn’t make a version for Android! I had an iPhone long ago, but now I’m the happy user of a Samsung Galaxy. For the moment I have to resign myself and just play when I visit my parents and grab my mother’s phone.

The three revisions of the App you can see nowadays in the App store agree that the game is very funny. Though, one of them is quite negative: the user complains that the App crashes every time he selects “Lobby”. I don’t remember experiencing any crash, but the truth is I never got to play “online”. I ignore if this part of the App doesn’t work or if simply there was nobody connected when I tried. Maybe it depends on the country.

Another user complains that he can rarely win, and claims that the dice favour the AI. I do have a say on this subject. The AI wins more often because it plays very well. I ignore the details of how are the random numbers generated in the App, but I’m totally convinced that the dice are not loaded. It’s not necessary!

In fact, I would like the App to include a couple of specific functionalities:

  1. Allow the user to use real dice for both himself and the AI. It’s not even necessary to program an artificial vision module (though it would be very cool). A relatively simple screen would suffice. The user would tap the results after rolling the dice:
    New screen for real dice
    The “weirdnessmeter” would indicate how likely or unlikely is the tapped combination of values. For instance, rolling two dice there’s 1 chance out of 36 to get two worms, but there are 2 chances out of 36 to get a worm and a five, if we don’t care about the order (worm-five and five-worm).
  2. Display the intentions of the AI player who is rolling the dice. For example, to mark lighting or darkening every tile depending on the confidence he has to obtain it, and surround the three most valued with yellow halos of different intensity.

Both functionalities would be optional. Naturally, their use would disable online game and the recording of achievements. The question is: would it be fun? I think it would! Not only to verify that the AI plays well with real dice, but also to learn from it and… to cheat on it some time!

Return to index

Summarizing

Pickomino (“Piko Piko” in Spanish) is a small board game that I love. It’s a great gift, especially for families with children old enough to practice sums.

In addition I have the pride of having programmed the Artificial Intelligence of the official App, which you can find here.

I hope you like it as much as I do.

Return to index