A few weeks ago I published here a fairly long text in which I presented a retrocausal interpretation of the universe. I explained the reasoning that had led me to it and reasoned briefly about the consequences of it from a philosophical point of view.
I mentioned the article in an Internet forum and the critical reaction of some physicist convinced me to withdraw it. Apparently I, a “layman” (yes: some physicists use that word to refer to those of us who are not physicists), was spreading a rehash of all the misconceptions of “pop science”. Worse: I was pretending to “teach” from my ignorance.
In my defense, I can argue that at the beginning of the article I made it very clear that I am not a physicist and that what I exposed was my opinion.
I still think that the retrocausal interpretation is the most accurate because it recovers the locality while explaining the spooky action from a distance. It just fits, it makes sense.
On September 27, I had the honor of doing a lightning talk in the Meetup Madrid C/C++, in IBM. Mine was the warm-up talk before Raúl Huertas, who was the main speaker with his fantastic talk about Sublime.
My talk was a small preview of a longer one that I want to propose for the next using std::cpp.
It can be downloaded here: Anticipo – Hagamos bibliotecas fáciles de usar
At last! We already have our fractal painting, printed by Art&Vinilo, and we are going to hang it in the living room.
The first step was to decide where would we put it and how big it would be. We decided that it would go to a side wall of the living room, facing the window, and it would be 85cm wide and 60cm tall. This part was easy. At 300 points per inch this means 10039 by 7087 pixels.
But choosing the image was another kettle of fish. We didn’t want to get sick of seeing it in the living room after five days… I spent many hours computing fractals and choosing colors. It took us months to decide.
We ordered the printing to Art&Vinilo and the result is splendid. The gradients are perfect. The level of detail is awesome. You need to look at it very close, with good light and good seeing to distinguish the ink dots.
Here are a couple of photos:
Now we have to hang it :-)
Another day I will upload the candidate fractals that didn’t make it to the print. Now I look at some of them and I hardly believe I could find them beautiful one day. How volatile is this thing of aesthetics.
In a few words, this post explains a presentation template that I made. The special thing about it is that you can generate several PDFs of different aspect ratios from the same sources.
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:
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.
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:
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.
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.
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:
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.
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!
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!)
If every rolled value fatally coincides with something we already put aside, we loose our turn (and the tile earned more recently).
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.
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.
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 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…
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:
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:
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).
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!
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.
In a previous entry I promised to talk about the cases where it makes sense to use your own implementation of a sorting algorithm. I will, but first I want to illustrate how badly twisted it can get.
When I say “fail horribly” I don’t mean the case of “not making it work” but the case of “making it work… until it happens to fail some day”. The latter is much worse.
Ignoring the fine print is a mistake. Grabbing a book on algorithms and implementing your own version of algorithm X without reading the full chapter can be a huge mistake.
Let’s review, as a practical case, the mistakes commonly made while implementing quicksort:
To leave the pivot inside one of the parts (possible infinite recursion).
To use always the first element as pivot (or always the last).
To believe that using as pivot the median of 3 or a random element avoids completely the worst case.
To make two recursive calls instead of using tail recursion.
To use tail recursion, but always on the same side.
To believe that using tail recursion solves all problems. It reduces the memory required in the worst case, but not the time.
To leave all elements equal to the pivot on one side. If you do this, quicksort will show its worst behaviour also in the case where all elements (or many) are equal.
I’ll explain the previous issues one by one:
1. To leave the pivot inside one of the parts
While partitioning, it’s good to leave the pivot in its final place, and not inside one of the parts to be sorted. This might look like a small, unimportant optimization, but it isn’t.
If we leave the pivot inside one of the parts to be sorted, and this part fatally happens to be the whole array to be sorted (being the other part empty), then we provoke an infinite recursion.
Several details determine the impact of this issue, like the choice of the pivot or whether the elements equal to the pivot are distributed or left on one side. Though, the only way to completely solve this problem is to exclude the pivot from both parts, leaving it placed in its final position. This way we guarantee that every recursive call reduces the problem size by at least one element.
2. To use always the first element as pivot (or always the last)
This would be less important if all possible permutations happened with the same probability. But reality is different. The special cases of “already sorted data” (either in straight order or reverse) or “almost sorted data” are quite frequent in comparison with other permutations. And in these cases, the first and last elements are the worst candidates we can choose as pivot.
If we use always the first element (or always the last) as pivot, quicksort degenerates into its worst behaviour with already sorted data, no matter whether they are in ascending or descending order.
This problem is usually attacked in two different ways:
To use as pivot the median of three elements: the fist, the last and the middle one
To use as pivot the element of a position chosen at random
Both methods reduce the probability of the worst case, but they can’t eliminate it completely.
3. To believe that using as pivot the median of 3 or a random element avoids completely the worst case
The worst case can still happen. It might be very unlikely, but it’s still possible. This is the kind of problem that goes through testing undetected and shows up later, when the consequences are serious.
It’s not only a question of probability. An attacker might feed our system with data arranged exactly in the way that provokes quicksort’s worst behaviour.
We must take into account that the worst case can happen. It’s quite convenient that tests exercise it in order to evaluate the consequences regarding the required time and additional memory.
4. To make two recursive calls instead of using tail recursion
Tail recursion is implemented replacing one of the recursive calls with a loop. This way we slightly reduce the execution time.
It looks like a simple optimization, but in reality this is necessary to reduce the additional memory to O(log N), even in the worst case. Though, it is not enough to simply use tail recursion in any way. I’ll explain why.
5. To use tail recursion, but always on the same side
If tail recursion is not used, or if it is used always on the same side, the required additional space in the worst case will be in the order of O(N), that is, proportional to the number of elements to be sorted. This can provoke a stack overflow.
The reason is that, in the worst case, up to O(N) recursive calls will be nested, and every one of them takes some memory.
The only way to solve this is to use tail recursion in the recursive call that corresponds to the largest part. This way we ensure that only O(log N) recursive calls will be nested.
6. To believe that using tail recursion solves all problems
Tail recursion, used correctly, solves the space problem. But there are still other problems. The time of the worst case is still
O(N2)
. As I’ve already pointed out, the choice of the pivot can help in making this case very unlikely in practice. If “very unlikely” is not enough, then we must resort to some other algorithm that takes O(N log N) time also in the worst case, even though the average case takes several times quicksort’s average time.
But this is not the end. There’s still a subtle detail that can turn this “very unlikely” in “embarrassingly common”:
7. To leave all elements equal to the pivot on one side
While partitioning, what should we do with the elements that happen to be equal to the pivot? At first sight this looks like an unimportant detail. We can leave them in any of the two sides. The algorithm will sort properly. In addition, there won’t be too many elements equal to the pivot, will they? Oh! Wait a moment… Maybe there are lots of them!
When we talk about sorting algorithms we tend to think of arrays full of different values. But in real life if happens quite often that many elements have the same value. Suppose that we need to sort the data of 47 million citizens according to their marital status (single, married…). After a couple of recursion levels, chances are that all, or almost all the elements of the fragment to be sorted are equal regarding marital status. What will happen then.
The probability of choosing a pivot with that repeated value is very high. Therefore, many elements will be equal to the pivot. If we put them all at the same side we will have an inefficient partition. The worst partition indeed! Quicksort will exhibit its worst behaviour in a case that, in principle, seemed absurdly easy. This is most certainly the biggest problem because algorithms textbooks don’t emphasize it enough, if they ever mention it.
The solution is to distribute the elements equal to the pivot among both parts, even though it might seem at first sight that we are moving data around unnecessarily. You can find an implementation here.
However, I insist: the best option is almost always to use the sorting method provided by the programming language in its functions library ;-)
Blog about programming and whatever I come up with
