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

Markus Spiske

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 equity¹. 

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 model². 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!

¹you can get all basics financial information about GmbH and AG German companies from the Bundesanzeiger. 

² I plan to eventually publish a map about this in a reprint of this article, so stay tuned! 

 

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!

Riemann vs Lebesgue (thank you Kia)

For 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!

White King, Red Queen: Machine over Human, part IV

They wanted to write chess programs (I); they did it and brought a chess program in every household (II); we also learned how to write our own chess program (III).

The next step would be to look into what has been repeatedly called one the turning points in the history of artificial intelligence: the two Garry Kasparov vs Deep Blue chess matches.

Indeed, the matches were extremely exciting, back then in 1996-1997. Kasparov was a true legend in the chess community. World champion at the age of 22 in 1985, he held the title until 2000. Already then he was widely recognized as a one of the greatest chess players of all time, featuring a aggressive, appealing playing style.

The challenger, Deep Blue, was a chess-specific supercomputer built by IBM both as research project and a publicity stunt.

The history can be summarized quickly: Deep Blue lost the first match in 1996 and won the revanche in 1997. Last year, Kasparov gave a great interview about that time.

In hindsight, it is clear that the defeat of the world-champion by a chess computer was a well predictable event: the question  should have been not whether but when in the decade between 1995 and 2005.

Strangely, it did not feel like that back in 1996. There were strong feelings about whether it would be really possible that a computer could possibly beat Kasparov. There were strong feelings about what would be the consequences of the defeat of humans by machines. Chess would be dead. Young people would'nt play anymore. And so forth and so on. The old "the world will go the dogs" kind of story.

Deep Blue won and nothing happened, apart of people talking about it for some weeks and then forget about it. Obviously, this would not stop computer scientists from working on the topic. Chess engines still were developed. In 2009, a mobile phone with Hiarcs 13 would win a super chess tournament and reach unprecented Elo ratings. Nowaday, grandmasters play chess engines only with odds.

And still, people would still play chess, new young talents will come to chess clubs, chess instructors will not go out of business. From my very individual perspective: the situation for chess players has improved over time since 1997.

One things changed, though: chess computers would be taken seriously from now on. The field of computer chess would become a competitive field in its own, played by its own rules and igniting a new set of innovations.