mercoledì, settembre 12, 2018

What I learned about cognitive bias when cycling around on a random morning

I live in the same city since seven years. It is not a large one: a small lovely southern German. From time to time, when the time is there, I just love to roam around without a real goal.

Cycling tours


I have two small children, almost as lovely as the German city I live in, when they not busy demolishing our place. I bring them outside, in the forest. Maybe a sheep or two to watch. 
One of these idyllic places is located something around three kilometers away from my place; from spring to autumn, once a month I am there with the children. My oldest is six years old: this makes a grand total of over seventy visits. This place is called Listhof.
One of the problem with the Listhof is the following: you ride on a valley with a gentle slope for maybe ten minutes, and then you have to take a left turn and climb a very sharp hill. Not more than fifty meters altitude difference; but with a trailer can be a challenge. In particular if the trailer content starts complaining about the lack of speed. But I love them: month after month the same route. Until yesterday: at the point in which you take the left turn, you can choose to go right; if you know the geography of the place, it is immediately clear that this is going nowhere.
Or does it? Curious, I took this right turn on one of this exploration tours. After less than minutes of a flat ride, unexpected, the Listhof.  

Geography is simple, other stuff not


When you think of it, the road topology of small city is a simple business. After seven years, you should have learned it. But surprising facts hide just beyond the grasp of mental laziness. If this is true for simple problems, we can only guess what others treasures are hidden in plain sight in more difficult situations. Here an example from chess programs, a field which I like and contribute to.  There is a piece in most of these programs, in which you typically look at all the possible captures of one enemy piece with on yours. In order to save time, it is logical to first check if you can first grab the most valuable enemy piece with the least valuable piece of yours. If you're lucky, you discover that you can safely capture it and don't need to inspect the rest.

This ordering logic is called MVV / LVA (Most Valuable Victim attacks Least Valuable Aggressor). This logic has been used for decades in chess programming. Then, three years ago, in Stockfish, the chess engine to which I contribute, we tested it. And, alas, we discovered that MVV ordering is enough. That was weird. Then we started testing statistically different secondary ordering criteria, searching for improvements; this kind of try random ideas is much more difficult than you can think. Typically, after the five, six idea, you dry up. We were lucky, and I found an improvement after few attempts. Indeed replacing LVA logic by a penalty based on how deep in the enemy lines you are capturing does the job.

Question the assumptions


How many assumptions are you carrying with you all of the time? I give you some questions as an inspiration, and what I discovered over time.

Are you sure you wouldn't like another job, even if you are good at moment?
Some months ago I moved on, and I realized that working with people is at least as good as working with code.

Do you know exactly what your partner likes and what it does not?
I always thought that my wife wants help in finding solutions when she has a big problem. Few years ago, after being married more than five years, I discovered that no, she does not. She typically just wants a kiss and a cup of tea.

How the hell you know you don't like Harry Potter?
I refused to read it till 2009. Then I became addicted.

I can't live without a car!
Two years ago, we had to spend 2000 € on the car for repairs. I was cheap and sold it. We decided, we will wait some time before buying a new one. It turned out, we can live without a car.

Happy exploring!

domenica, agosto 12, 2018

A word about the AI hype in chess

Some months ago, many of you have probably heard how a neural network trained from scratch in an afternoon by Deep Mind defeated the strong chess engine in the world, Stockfish.

Deep Mind get the hype started

This legit hype was started by Deep Mind, a subsidiary of google strong in artificial intelligence, published the paper "Mastering Chess and Shogy by Self-Play with a General Reinforcement Learning Algorithm".
In this paper, they demonstrate a general learning algorithm which was able to train a a neural network which would power a Monte Carlo Treee Search based chess engine to such a level to be competitive in chess with top notch engines. They measured competitiveness in chess by letting their engine playing a 100 games match against the back then latest release of Stockfish, Stockfish 8, the world-leading chess engine, maintained by a team of volunteers (disclaimer: I am part of this team) . It won by a convincing margin of 28 wins, 72 draws and 0 losses, in their own words, 
calling into question the widely held belief that alpha-beta search is inherently superior in these domains

I do now want to dispute this call by the Deep Mind team, but it could be done based on the match condition. It can be observed that, if one of the goals of this claim was to generate a hype, then it succeeded.

Open source takes over

Following this paper, a team of developer decided to start an open-source project to replicate the results. The ultimate goal was (and is) to show that this calling into question is a well-founded claim. They had of course some work to do: the paper by Deep Mind contained many details, but not all of them. Also, one of the criticisms was the Deep Mind engine was not a real UCI-compliant chess engine, and wouldn't have been able to participate in chess computer tournaments. So they had to replicate the scientific part of the paper, and also make a real chess engine out of it, being able to compete in chess tournaments. In that, they were supported by nonetheless than Gary Linscott, the gifted programmer who built Stockfish testing framework, see a previous post.
One very important remark: this neural network based engines need GPUs to work well, as the generic type of neural network used there are specifically designed to make use of the massive matrix multiply capabilities of GPUs.

LC0 go to TCEC

After some weeks in the project, the LC0 team (this is the name of the open-source project) was invited to send their program to TCEC. TCEC stands for top chess engine competition: it is a league where all chess engines can compete on standardized hardware. When invited, they start in division 4 and they can work themselves up to division 3,2,1,premier. The first two engines in division premier fight a titanic superfinal over 100 games. Last season (number 12) was won by Stockfish 9. Since the divisions are played out serially, for an engine it is possible, in principle, to start in division 4 and, in the same season, climb up all the divisions and win the Superfinal. TCEC management, however, decided not to invest in a GPU, yet as they were not sure of whether LC0 would keep existing and also for the speed in which they had to organize it. To make the story short, LC0 finished last.

LC0 hype grows

This did not discourage the team. They knew that the lack of a GPU would seriously cripple the engine and so they continued working, recruiting tester around the world for playing millions of games. In the meanwhile, private people would test the engine and publish the results online. In particular, kingcrusher, a well known and respected chess expert with 100k youtube follower, decided to back the project posting videos and analyses of this awesome new engine. The were invited back to TCEC, which was able to organize access to a server with 2 high-end GPUs. It was predicted that LC0 would rush through the divisions and challenge Stockfish itself. To add more drama, some days before the start of Season 13, it was announced that a second neural network engine would enter division 4. After some speculations it turned out that it was a more or less a derivative of LC0 and arguments followed. Nevertheless, this second engine, DeusX, was allowed to enter TCEC too. Expectations were running high for the new era of computer chess. The hype was at its maximum.

Full power neural network at TCEC

As I write now, division 4 ended some days ago. With a sort of an anticlimax, after some games, it was clear that, although LC0 and DeusX were very strong engines, they would not rush through divisions. LC0 finished first, and DeusX second, qualifying by 0.5 point margin for division 3. Division 3 is in course now: between the divisions, the admin of the site was started, and the new one had some experience with LC0 itself and was able to improve the settings of the dedicated server to give the two neural networks some more power. They also submitted updated engines. In spite of the efforts, after 20% of division 3 played out, they float in the mid-range of the league. It is somewhat expected that the division will be won by Ethereal, another very young, though classical engine, developed by a 2 persons team. The second slot for qualification is still open. Currently it seems plausible though not sure that one of both neural engines will win a ticket.

What do we learn from the hype

Maybe neural networks are the future of computer chess. Maybe not. Time will say. As usual, there is no free lunch and you shouldn't run where they say you get one. And by the way, don't do momentum trading. Avoid diets. And most important, if you start from scratch, don't expect to succeed soon.

lunedì, agosto 06, 2018

The dose makes the democracy

So you want democracy. This is a good thing; remember, though, that the dose makes the poison, as Paracelsus put it.

Democracy as a form of government

What is democracy, for a starter? In classical Athens, it denoted the fact that important decisions were taken by normal citizens, possibly picked by a lottery. Yes, by a lottery. The main parliament in early Athenian direct democracy was not composed of citizens chosen by vote, but by chance. This was thought to be important as it was known (back in 6th century BC, mind you) that elections tend to be dominated by wealthy individuals. Today's typical representative democracy refers to the fact that countries are run by bodies of individuals which are elected among the population. Again, it is well known that, although to candidate for a political role should be open for everybody, in fact a reasonable amount of resources should be invested in it in order to have a realistic chance to be elected. The specific regulations change from country to country, but they do not change the overall view.

Democratic principles all over the place

Given that, it must also be said that often we talk of groups, institutions, communities as to be run by democratic principles. Or not, of course, this latter being considered harmful. A larger participation in decisions is often advocated even in private companies. Many techniques and social hacks from the agility culture aim to improve direct participation in decisional processes, think of planning poker and the like. In general, when we talk about communities, we refer to democratic principles as a cultural meme describing the aim of extending participation to decisional processes to the broader masses. It is thought that this should improve identification with the community, productivity if talking about companies and in general to be a good thing. 
But is it so? 
Although of leftist tendencies myself, I always suspect of things which are always good, even if this is democracy and sharing of power. Nothing can be always good; a standard tactics to prove this claim in different contexts is indirect proof (or reductio ad absurdum). If democracy is always good, then it must also be good to held general votes about what kind of size must be allowed for the southernian kiwi-kale. The latter is obviously false, so the premise must be false, too. I know, this is dirty, more on this in a latter post. For now, let us accept this and consider the fact: what are the criteria which make democratic principles necessary?

Democracy is the more important the less you can walk away 

For the sake of the discussion, let us assume that we are looking at a community whose honest goal is to make possible to its members to be happy. Since its members are nevertheless humans, it makes sense to have somebody running the show to avoid things going to the dogs. Or does it? In fact, if in your community everybody can walk away without any negative effects on her, then you wouldn't need any democracy. This must be intended strictly: if your walking aways damage the remaining members of the community, then it will have a negative influence on you (since they could sue you and so on). I think the most clear example is that of an amateur sport team with a large basis, say football: there is a trainer, and he decides. Since they are amateurs, there is nothing at stake, so if a player walks away and join another team, nothing will actually happen. Such a team can have a concentration of power in the trainer or instructor. In fact, if he messes up, all players will leave and the community will be disbanded. I am in a yoga class in which we experienced this kind of scenario on a significant level some times ago. It was stressful for the teachers, for us it went very smooth. Much different is the case in which members of the community cannot realistically walk away. This is thy typical case of a country: if you are born in a country, you could in principle move to another one, but this comes with much discomfort. Not to have a democracy here is risky: if you have a dictator, and he is bad, people will be forced to stay. Nobody will be happy here, and we missed our goal. What about an average case? Say a team manager in a company making some important decisions. If the decisions impact everybody, you better involve them. If you mess up, they will be unhappy; they could even be unhappy if you don't mess it up, because they were not involved. The amount of autocracy you can allow depends directly on how easily people can actually walk away; interestingly, if you are in a hot market, people will be able to change employer fast, if with a bit discomfort. You can allow some autocracy here; in a stagnant markert autocracy will automatically generate unsatisfactory feelings in everybody. In general, in a company, you will allow less autocracy than in the football team example, but more than in the country example. This of course only takes into account satisfaction of the members, and not quality of the decisions. But this is another story.

domenica, luglio 22, 2018

White King, Red Queen: the matrix. Part VI.

They are coming.
In 2009 Hiarcs 13 on a smartphone dominated a world-class chess tournament with humans. At latest in the moment, it should have became clear that the world of computer chess should get separated by the world of human chess.

Indeed they were: as an example, in 2006 a group of compute chess enthusiasts founded the CCRL rating list, dedicated to testing of chess engines in controlled hardware conditions. They would donate their computers to let engines playing against each other just for the pleasure of compiling a list of the strongest chess computers. This list, still maintained after 12 years, contains 353 engines as of July 22th, 2018, many of them tested in multiple versions.

The arena

We have seen it often: if an appropriate, fair arena is set up, with a meaningful reward, people will gravitate towards it and, given time, the arms race will begin. In the 2000ies, many of such arenas were being made available, in the form of rating lists, computer chess tournaments and the like. The arena was set. As for the reward, chess engines were now very hot even for professional players and you could still sell them as programs for up to 100 $. If you think that you can squeeze a chess engine under 10k-20k lines of code, and you only need to comply with a specified protocol, it sounds like the perfect challenge for algorithms enthusiasts. The realm of nerds, so to speak. And the nerds came. In few years, we had many engines fighting for the title of strongest chess program: Rybka, Houdini, Komodo. And then came Stockfish.

The crowd

Until 2013, Stockfish was a good, but not top open-source chess engine. Until Gary Linscott, one of the contributors, constructed a distributed test framework for the engine. In this framework, anybody would be able to write modifications of the code and test this against the currently best version. How would this be tested? People from all over the world would donate their machine and a program would take care of let those computers playing games of the proposed modification (called patch) against the current best version (called master). After some dozen of thousands of games, it would be decided statistically whether the modification could be applied. A round of human based checks for code quality and you could get your patch included into master in less than a week! In the first 5 years of its life, Stockfish had 16 people contributing code. In the second 5 years, 94. Furthermore, since the patches would be tested with some very high predefined criteria, the risk of introducing errors just dropped to almost 0. Result: in less than 1 year Stockfish was sent to the top of all rating lists.

The arms race

One further piece to the puzzle: Stockfish is an open source engine. This means whoever can go and read the source. Furthermore, all discussion is done in public in a google forum, so everybody can know the background of decision and design. On one hand, we have the sheer amount of ideas and computing power available on the its framework. On the other side, these ideas are public, so all proprietary engines can go a dig for ideas which will work also in their context. In the subsequent years a true arms race between three competitors, Stockfish, Komodo, Houdini, followed. They would continuously exchange the crown of the strongest engine in the world, informally assigned as the winner of the last TCEC tournament. This continues until today.

Clouds on the horizon

Some of you will have known that chess engines were against on the main page some weeks ago. A team from Deep Mind, the AI subsidiary of Google, trained a neural network able to compete with Stockfish on custom hardware. The history repeats: first a year-long quest to have a alpha-beta engine beating the human chess world champion and its biological neural network. Now a year-long quest (to come) for an artificial neural network to regain the crown. We'll see how it ends! In the meanwhile, an open source team is trying to replicate the results of the Google team in an effort call Leela Zero. Again, one of founder of this project is Gary Linscott, the former Stockfish maintainer which created its testing framework.

Why the matrix?

Interestingly, now the challenge is not anymore between persons writing programs. But between engines and their development paradigm. In a way, the engines are using us, the humans, to improve themselves such that they still will be operated in the chess engines arena. As I said: the matrix.

martedì, luglio 17, 2018

Is free will a thing, actually?

If he doesn't have free will, who does?
I always read backreaction with pleasure and one of the latest articles attracted my attention.
It was about free will. Free will is cool, really. This is a slightly, but only slightly, religious concept, so people from all faiths will discuss about it without much arguing. But it also philosophical, so hard core atheists will join the discussion. It has something to physics, since somebody in the room always bring up determinism. Everybody has it (or nobody, depending on who you ask) so everybody is going to discuss it. In the end, it does not matter that much, so discussions do not become too heated. And finally, it is the main topic of The Devil's Advocate, which is a great movie. I love it. Both free will and Al Pacino, of course.

Free-will has nothing to with determinism

That said, I would like to offer my humble contributions to the topic. The first objection to free will which always arise is determinism. What is determinism? The belief that if I would know position, velocity and everything else of all particles in the universe, then you would be able to predict everything which is going to happen in the future. It looks like this strong form of determinism would destroy free will. The first clear formulation in western philosophy of this is due to Laplace. Luckily enough, we don't have to discuss this because it is probably non-true. First, it is non practical due to the amount of chaos available in the world: small perturbations lead to large changes.
It is plainly wrong in the standard interpretation of quantum mechanics, since wave functions collapse contains a randomness. So, no physical determinism. 
Also, if determinism has anything to do with inference, it has been shown that you cannot do complete inference in systems where you can perform standard logics. Interestingly, this mathematical proof requires Cantor's diagonal argument. Which one of the single most important pieces of maths, so make sure to follow the Wikipedia link, please. I will come back to this in the end.
Given that determinism is wrong, we can set it aside in discussing free will. Yes, in a deterministic world, there is no space for free will. In a non deterministic world, we do not know. Maybe we are free, maybe we are random. Maybe we are merely non-computable.

Free-will has nothing to do with predictability of human choices

In the later years, there has been a copious amount of papers about predicting human choices before the reach consciousness, due to continuous improvement in brain imaging methods. See here, for example. This has caused a lot of stir among people. I do not know exactly what about: the will can well be free even if it is not conscious. You can make a free, conscious decision with your own will, but your will could also make a free decision without notifying your consciousness organ in advance. Free will is not the same as rational choice, in the end.

What exactly is free in the free will?

This is the very tough question: I think one important point is the capacity of influence its own choices and the ability of (consciously or not) question one's first (or second or third) guess. In general, when we talk of something which is free, we mean that said something is able to initiate actions out of its own initiative and it is not completely determined by the external forces. We talk about freedom even in physics: how many degrees of freedom has a body? In how many way it can move freely without being constrained? I would claim that free in "free will" denotes the mind's ability of making conscious or non-conscious choices not completely determined by factors external to the mind itself. Similar to a body with a positive number of degrees of freedom can actually move, although it is influenced by external forces and the own inertia, a free-will can pick choices, although these choices are influenced, to large degree, by external factors.

Gödel, our old friend

We already have seen that Mr Wolpert used Cantor's diagonal argument to show that there is no mathematical free will. You cannot say Cantor without's saying Gödel. Gödel's first incompleteness theorem states that any axiomatic system which is has a model of arithmetics will contain a mathematical sentence which is neither true nor false. If you additionally impose that the arithmetics should be standard (in some very specific sense), this sentence will true but non provable. In other words, free will seems to be related to Gödel and to the very nature of natural numbers which is itself quite dubious. By the way, Gödel's theorem proof heavily uses Cantor's diagonal argument, so we are back to where we started.

Summing up

Summing up, we maybe have free will, but then again no. We'll see. In any case, if natural numbers are actually true, we will have to pick infinite number of axioms to avoid problems. And this means a lot of choices, and all of them are free, unless you use standard arithmetics. But you don't need to. Good evening to you.

martedì, luglio 10, 2018

In praise of laziness - in math and in life

 Since around 2000 I have pursued a career in math-related fields. I studied maths, I did my PhD in functional analysis and PDEs, then I moved to stochastic processes. After leaving academia and joining industry, I happened to be involved in a project about non-linear structural mechanics.

All in all, at my venerable age of 37, I am satisfied to have a google scholar profile and I am very grateful to have enjoyed collaborating with many people much more gifted than me.

As years pass, I become more and more convinced that the only way I could achieve this was not mathematical talent but sheer laziness.

Some background on why I was good in math, but not really

I had almost no math education until the age of 18. I went to a humanistic school, learned Latin, Greek, Philosophy and the like. In my last year, I heard rumors about limits and exponential functions from my math teacher. I thought them esoteric mysteries reserved to University students. I decided, this was not interesting enough for me.

However, I was somewhat talented for numbers and I still can calculate very quickly possible figures, on the other side I have never had any intuitive grasp of geometry. I literally hate triangles and congruence criteria, not to mention 3D geometry, which should be prohibited by UNICEF as a perverse mean for teens torture.

So I went to University, and started studying mechanical engineering, just because of good job perspectives, if you want to know it. However, after hearing the introduction of natural numbers according to Peano, I decided to switch in the end. I just enjoyed that so much!

How to survive pages of estimates through laziness

Somehow I got a master degree in math. I was 25 as I finished my studies, I decided that I still could some fun time and did my PhD. Laziness is no good starting point to complete a PhD in maths, though. But it has some advantages. Whilst navigating the treacherous waters of choosing a cool topic for my thesis, I steered clear from everything what promised years of suffering because of excessive calculations. In contrast, after some attempts I settled to a reasonable subject where more or less nothing had be written, so that I could graze on green pastures and produce interesting theorems with limited effort. It was not a conscious effort in that time, but now, years later, I recognize the pattern very clearly.

I had a very good supervisor. He was back then PostDoc in my institute, and he had quite some talent for doing long calculations without errors. He tried to motivate me to learn this skill. Again, I was very bad at this, but had some insights for finding shortcuts and proving theorems with as little effort as possible. Laziness, again. This saved my academic life in similar situations over and over again. Another example: I was once included as an author in my most cited paper for the only reason that I revealed to a very good PhD student the secret of shortening calculations with the judicious use of Fourier transforms and matrix inversion. 

Laziness in life

In the end, I think that laziness helped me in life too. We built a house with my wife some years ago. This is quite a complex endeavor, I can say you. It needs hundreds of decisions, and can become seriously exhausting. Somehow, we decided to settle for a "good enough" strategy. When faced with any decision or option we would always take the first one which was good enough. We talked to friends in the same situation. They were horrified that we planned, chosen and bought our new kitchen in well below 4 hours. When I was a PostDoc, I was struggling to start an academic career. I changed field after the PhD, so I probably would have needed some more stations before becoming settled. Judiciously, I just decided that I would give industry a chance, and I have never regretted this. Academia was just not my path. By the way, the PostDoc which supervised me during my PhD thesis is now a respected Professor. It was his path.

I admit, there are situations in which you have to push and go the extra mile. Can you ever be sure that this is the case now? Burnt energies do not come back for free and if you rush too soon you will not do the run.

And you? Have you already found yourself in situation when healthy laziness helped you succeed?

martedì, luglio 03, 2018

Everything is a team sport

 I have been reading this article on the Rebels At Work tribe site and I would like to share my thoughts on diversity, but taking a different vantage point for looking at this. Let me start with two insights:
1) whatever you do is a team sport and
2) you have to understand the game you're playing

Let me give some example before I dig deeper in this concept.

Example 1: Complex Tooling

Imaging you want to build the tool to design your next cool device. It will need some physics, stats, CAD, circuit design. You're trying to write something like a scientific library. This is a team sport: specifically, it feels like basketball. Since very in-depth discussion are the bread-and-butter here, you need small teams in order not to get lost in group dynamics; also, since in-depth knowledge is very rare, it almost never pays off to have duplicates. If you are trying very hard to get this library for doing multiphysics modeling of microdevices, you dont want to have two fluid dynamics experts and no software engineer.  You would miss one discipline badly. For every role on your team you need exactly one person: one point and one shooting guard. One small and one power forward. One center. You need them all.

Example 2: Hardware Development

You now have your tool to design your devices, with very cool physics implemented, you can do CAD and whatever else. You want to bring now to production. Your team will grow. Deadlines will now feel more important than technical depth. You need redundances; on the other hand, do you really need to have production engineers and software testers in the same meeting? Probably not, so you can enlarge your team, and you speficically need coordination. It feels now more like a football team. You have a goalkeeper, 3-5 defenders, 3-5 midfielders, 2-3 strikers. You typically need a deep-lying midfielder, the project manager, purely in charge of keep the ball moving. Also interestingly, you have reduced interaction between separated roles: although the occasional pass from defense will serve a good scoring chance for a talented striker, this is an exception.

How do I recognize which game I am playing

As usual, there is no easy recipe. I find mapping your environment can help you. If you are doing research on something very innovative and technically challenging, you probably will need small teams to encourage in-depth discussions: we are talking about basketblall. If you are in product development, and you need to meet deadlines, but the technical challenges are solved, maybe you need a football team with redundances.

I think using this model can help you investigate two important aspects: the amount of necessary internal communication and the right level of diversity.

More or less communication?

Imagine a football team in which the goalkeeper always tries to pass to the forwards; passes will be not precise, the goalkeeper will not even see exactly what is going on on the other side of the field. If passes are the communication in ball games, and we use this model in our product development team, it seems that too much of communication could even be detrimental in a product development team. You need the midfielder who let the ball move from defense to offense, so to speak. Ever asked yourself if you really need a weeky meeting with all 50 members of the team?

On the opposite, imagine a basketpall team in which the shooting guard plainly refuses to pass to the center: it sounds like the team is doomed to fail. In small teams with tough challenges is the same. You sometimes really need the combined skills of both the avionics expert and of the software tester to get the reliable library you really need to fine tune your airplane wing!

Right level of diversity

Accordingly, you can use this model to understand on which level to address skill diversity in your team; it does not make sense to insist in having two central defenders with very different passing skills. It does not hurt and it does not help, so you're free to choose using other criteria. On the other hand, make sure to have some defenders and some midfielders and some strikers. Yes, and more than one player which can kick penalties will not harm.  The same at work: in a product dev team, make sure to have some redundancy in every field, but don't get to stressed about lacking skill diversity inside of a position. Lack of diversit will kill you in the mid-term, though, in the research team, as soon as you encounter a problem outside the range of the people there. Ah yes, and they will not even notice that they have a problem, probably.

Hope this helps you, feel free to comment and share you're experience!

giovedì, giugno 21, 2018

White King, Red Queen: a data based sidetrack. Part V.


Our journey has brought us from an original quote from Hofstadter, through Faust and trees until the final victory of machines against humans.
We have repeatedly seen how evolutionary pressure for economic survival, academic prestige and generic coolness pushed further and further on the path of chess automata. We started in a world where it was unthinkable that chess could be played in some acceptable manner by machines, and only 30 years later, we got to know a world in which the world champions would be dominated by smartphones. This took 30 years, some great minds and the direct intervention of the Red Queen, making sure that everyone would be forced to run and run and run, without a single actor being able to hold the crown for more than some years.
Our journey would be incomplete, though, if we would not mention the living fossil, the indomitable crocodile of the digital chess arena: the ecosystem created by ChessBase. So we will shortly sidestep the world of chess engines and chess playing and give a short look to the world of chess databases.

Enter Chessbase

What is ChessBase? It is a German GmbH, based in Hamburg, which sells world-wide mostly one, single digital product and related ecosystem material. This product, a database software and related game collections and training material, can be downloaded or ordered per postal service. In spite of the apparent obsolescence of this business model, it exists since 1985 and features a rock solid € 100 t net income and € 2 m equity1
What they sell exactly, and how did they manage to survive for so long?

Garry, again

If you can read German or possess a copy of Kasparov's Child of Change: An Autobiography (1987, Hutchinson), you will be able to revive the exact moment in which Garry was confronted with the first prototype of the ChessBase software. He describe the festive Christmas atmosphere in a home in Switzerland in which he expressed his wish for a database of games, its later experience with the first version of ChessBase, and how he did use this tool to its advantage in simultaneous matches. This was exactly the period in which Garry was fighting for the world championship against another Russian titan, Anatoly Karpov. Understandably, this boosted the acceptance in the chess community and made possible to expand rapidly and reach widespread diffusion. So they became the leading vendor of chess databases.

Inertia can kill, but must not

This was 1985. If you remember, this was more or less the time in which chess engines were spreading and becoming dominant: H + G, this other German company we met here was making money, too, with a computer based chess product. They were selling hardware-based engines, true, but they had the know-how, they could have moved to PC-based engines and survived. Why did they miss it? We will never get a definite answer. Fact is, ChessBase recognized that they have to diversify their product. They started offering only generic game collections. The more games, the better. They then started to offer specifically tailored and reviewed game collections, typically focused on a single opening. They somehow recognized that the client used to browse and search the game collections could be improved on and used as a training tool. They started selling training material. With time, they became more a publisher of chess material than a seller of a digital product. Chess players are a conservative folk, and often recruit from persons with higher economic status than the average: if they have a product which is good and reasonably priced and serve the goal of comfortably analyzing games and preparing for tournaments, they will not switch to a random competitor. In this way, they could bloom and flourish for more of 30 years.
The Red Queen, however, may tolerate some hesitation, but clouds are already on the horizon, and who does not run will get beheaded faster than he can say "Check!".

The next menace

Using concepts from mapping and co-evolution, it is not difficult to understand what the next threat for ChessBase will be (Mr Wüllenweber, free advice for you here!): the commoditization of their business model2. Commoditization in digital landscapes nowadays almost always happens in form of cloud services or open source, or publishing platforms. What could happen here?
  • Commoditization of analysis: game collection platforms expanding in the analysis region. ChessBase is inherently a home PC product. You have the client, you use your local chess engine to analyze a game, give hints and similar. Given the extremely low cost of cloud-based computing resources, web-based competitors can offer analysis solutions. Indeed, Chessgames, a historical web page offering game collections (more of less a web-based version of ChessBase), offers online analysis on a Stockfish server, too.
  • Commoditization of training: Online game servers offering publisher platforms for chess blogger and freelancers. This is more or less the business model of chess.com. You register for playing, you get some articles and training for free. But if you want the full training experience, you have to pay a subscription.
  • The doomsday device: open source. Stockfish, for instance started some weeks ago publishing high quality training games on google drive. Given that these games exceed grandmaster level by a huge amount and the collection is growing at alarming pace, it will put a big pressure on pure game collection vendors. What will come next is in the stars.
Mr Wüllenweber, be warned!

1you can get all basics financial information about GmbH and AG German companies from the Bundesanzeiger
2 I plan to eventually publish a map about this in a reprint of this article, so stay tuned! 

 

domenica, giugno 17, 2018

Football learns from chess and finally uses Elo!



Finally, we are there after 50 years: the FIFA introduces the Elo rating as a measure of national teams relative strength!

For the chess fans among us, a well-deserved recognition for a classical tool from the chess world. For for the serious football fans a huge opportunity to improve understanding of playing strength and to become more informed about the real performance of the beloved team.

Let us start our journey with the hero of this story Arpad Elo.

Arpad Elo

Let us clear this in the very beginning: Elo is a name, not an acronym. Specifically, Elo is the family name of an US American theoretical physicist and chess player of Hungarian origins, who, in the 1950es, invented a statistics-based system for rating the relative strength of chess players.

As a theoretical physicists is difficult to find traces of him. He seems to have done some research in analytical chemistry, but his activity was clearly focused in chess. Being a strong chess player on his own, he was involved in the United States Chess Federation (USCF) from the very beginning and convinced both USCF and then the international chess federation (FIDE) to adopt his system.
He died in 1992, aged 89.
He has a good wikipedia page, which is as usual a very interesting reading.
By the way, from this short introduction, it should be clear that Elo should be written like Elo, and not like ELO.

How does it work?

The idea behind the Elo-rating is to have for every chess player a number, the rating, with the following property: if we have to players A and B, with ratings r(A) and r(B), the average results of their games should be a function of the rating difference alone. This is very different from other types of ratings. Imagine, for instance, to use the season rankings from a typical football league as your rating. These are calculated by giving each team 3 points on a win, 1 point on a draw, 0 points on a loss. Since these numbers increase with the advancing season, so do their differences, although the relative strengths of the teams do not change (in first approximation).
In practice, the are several different implementations of Elo systems. They usually use some variation of following procedure: when two players have a match, one computes their rating difference, say D, and divide this by a scaling coefficient S. This is the expected result of the game. This is done for each of the two players, so each player will have an expected result. For chess the expected results will sum up to 1. This is because you get 1 point for a win, half for a draw and none for a loss. So always 1 point is awarded. After the game, one compares the expected results with the actual result for each player. This difference is multiplied with another number K and then added to the rating of the player.
There are many variations on this implementation. As usual, every rule calls for problems and exploits.

History of Elo 

Until the 90es the history of Elo rating has been quite straightforward. More countries would adopt it, more decisions in chess would be based on the Elo rating of the players. For instance, chess has titles, both on the national and international level. If you are a good player, you could achieve the title of National Master, awarded by your federation according to own rules: usually they include to have at least a certain Elo and to achieve a given Elo performance on 1 or more tournaments. What is Elo performance? Imagine you play a tournament: since Elo rating is about averages, you could average the Elo rating of the players you play against in the tournament, and consider your average performance in the tournament. If you played 6 games for 4.5 points, this would be 0.75. Comparing this results with the average rating (as we did before) yields the Elo performance for the tournament. Accordingly, FIDE awards the title of FIDE master, International master and International  Grandmaster based on similar criteria. World championship is, in contrast, awarded based on a lineal system.
Until the advent of internet, there was a problem: Elo would get updated rarely. In Italy, the country where I came from, every 6 months. Now, imagine that, for some circumstances, you would lose more Elo than usual in one term. Say, you got sick on the only two tournaments you played, performing way under your standard. You would then start the next term with a very low rating, making very easy for you to make gains by playing weaker players with the same rating as you. It is as if you would punch in a weight category lower than your natural one. If you now happen to play many tournaments in that term, you would be able to boost your rating way above your real strength. Interestingly, this has happened in 1997 in Italy, where Roberto Ricca could climb to the top of the Italian rating list in spite of being an average national master.
Modern online chess platforms, like chess.com updates your rating after each and every game, so this exploit is not possible anymore (just in case you would like to try).
Much research has been done in this topic: what if you want to estimate Elo from a static database of results? What if you want to estimate also the variance of the result and not only the average?

Elo in other disciplines

Football is not the first non-chess discipline to use Elo. Online based game-like platforms are a natural fit for this very easy system. Halo and Tinder seem to use it, too.
In fact, classical Elo implementation in chess is just a very simple data stream compatible machine learning algorithm for estimating the expected result of matches. Also shows that simple algorithms can go a very long way.
Interestingly, non official Elo-like ratings in football have been made available from freelancers since ages (like this), I remember to find one back in 2008, as I moved to computational neuroscience and tried to get an overview about machine learning and similar topics.
I hope you enjoyed this overview over the Elo system, if you would like to know more about Bayes Elo or have me dive into the difficulties of Elo for non-zero sum games like Football, let me know with a comment!

giovedì, giugno 14, 2018

Riemann vs Lebesgue (thank you Kia)

RandLintegralsFor decades now, I have wondered about the true difference between the Riemann and the Lebesgue integrals in analysis. The classical textbook explanation goes more or less like that: "Look, Riemann integrals are bad for commuting with taking the limit, let us try something else: if we subdivide the value space of the function instead of the interval of definition, everything turns well. So let us do it". I accepted this until some times ago. But then something happened.

Some insights from the mind of a know-it-all

I recently changed job. I like to have constructive conversations with my colleagues and I have worked hard at this in the last years. Unfortunately, I live with a heavy burden. There is a constant battle between the "know-it-all" (Kia) section of my brain and the Dr. Henry Jekyll part. She is continuously proposing to show how cool she happens to be and how much better would she run things and how it is possible that you don't see this and so on and so forth. In the course of time, Henry did indeed develop a strategy to cope with this: delayed gratification. He would not let Kia to start its rant immediately, but he generously would allow her a imaginary conversation with the culprit, impersonated by himself. There, Kia is allowed to use all the destructive rhetorics, cynicism, sarcasm and intellectual superiority she can muster. By the way, what does it matter that I changed job? It matters, since Kia get very very excited every time she does meet new persons, in particular in work. So I went through some hard times in the last months. Sometimes, however, Kia gives me insight.

If you are that good, explain me the difference between Riemann and Lebesgue integral

Impersonating a particularly nice and competent new colleague, short of nasty questions to throw at Kia, Henry just decided to resort to a random math question. By the way, note that my current job has nothing to do with academic maths, just to let you gauge the folly of my situation. Here he goes:

H: Well, if you are that good, give me the true difference between Riemann and Lebesgue integral.
K: How can you not know about this? I though you did know about math! Dear me, I will go through it, if this is really necessary.
H: Let me see...
K: Every small child knows that in Riemann integral you partition the definition interval and in Lebesgue integral you partition the range of the values. Already in his doctoral thesis, which I happen to have read, my dear friend, in contrast to you ...
H: Hang on. Why now it should be better to partition the range of values?
K: Ah! You see? You did not learn anything in high school! You don't have any meaningful convergence theorems for Riemann integrals, so you have...
H: Why?
K: Why what?
H: Why you don't have any meaningful convergence theorems for Rimann integral and why it gets better with Lebesgue?

Yes, why?

Functions with bounded variation

There they stopped arguing: it became clear to them at once that they did not really knew why the world is that way. So they started a more intimate conversation in candlelight. The first thing what occurred to them is that by subdividing the interval of definition in equal intervals, I could not really control how much the the true integral of the function on a subinterval will differ from the area of the local approximation of the integral. This is bad. For doing this, in fact, they should make the intervals small when the function changes much and large when the function changes little.

And then I just had an image in my mind of the cover of Riesz functional analysis book, which I happened to be reading in the library of Tübingen university in 2004. They dug deeper, and brought up the fact that there I learned there about functions of bounded variation. Ah! Bounded variation! After 14 years, this small piece of information started to make sense. After 14 years, I understood why functions of bounded variations are so important. After 14 year, I finally discovered that they help controlling how a function changes in a interval and this is of crucial importance when defining the Riemann integral. As this would not be implicit in their very definition, to hell with them!

In fact, functions with bounded variations can be integrated very well in the sense of Riemann, I discovered. Incredibly also this obscure Riemann-Stieltjes integral makes sense suddenly!

But we want the convergence theorems. Go down some lines in Wikipedia: the space of functions with bounded variations form a Banach space in its own right, if endowed with an appropriate norm! Oh my God, why nobody told me that 14 years ago! We actually can have convergence theorems for Riemann integrals. So, why Lebesgue Kia, why Lebesgue?

The problem is, to make the space of functions with bounded variation to a Banach space, the required norm is given by the total variation of the function plus its Lebesgue norm!

So, in order to have converge theorems in the sense of Riemann, you must already know of Lesbegue integrals! Ah! I will not sleep this night because of this I know it...

Thank you Kia!