Computer simulates and predicts Candidates winner

3/9/2016 – Although everyone has an opinion on who will win the Candidates, whether as a pundit or a fan, what if you could enter everything you knew about the players into a computer, not just their ratings and recent results, but their playing tendencies, and more, and ask it to give an answer? Two experts did just that and here are the results of millions of simulations.

ChessBase 14 Download ChessBase 14 Download

Everyone uses ChessBase, from the World Champion to the amateur next door. Start your personal success story with ChessBase 14 and enjoy your chess even more!


Along with the ChessBase 14 program you can access the Live Database of 8 million games, and receive three months of free ChesssBase Account Premium membership and all of our online apps! Have a look today!

More...

Computer simulates and predicts Candidates winner

By James Jorasch and Chris Capobianco

Following chess tournaments online, I often found myself asking the same question - who is most likely to win this tournament? While Kramnik might be leading Dortmund by a full point after three rounds, how likely is he to win it all? And if four players are tied with one round to go, how will tie breaks affect their chances?

I made my best educated guess, but it was little more than that. Out of curiosity, I began to design a tool to help answer these questions. I built a spreadsheet that could simulate the outcomes of chess games, filling in a cross table with hypothetical wins, draws, and losses and tabulating the results over thousands of trials - a prediction engine for chess tournaments. But it soon bogged down, and adding new ideas or algorithms was impractical. What I needed was the power and flexibility of custom software.

Fortunately my friend Chris Capobianco is a software engineer at Google. He agreed to take the coding on as a fun side project, and we started spending some evenings brainstorming and problem solving. We filled whiteboards with equations describing rating calculations, aggression factors, player biases, adjusted draw percentages and more that he eventually turned into dynamic, flexible software.

Given the time and effort required, we were soon reaching out to others to help out. We needed standardized data from a variety of sources and complicated statistical algorithms. We also needed deep learning software to improve the accuracy of the probability of each player ending up the winner from this complex system.

As with any human competition there are naturally factors that don’t easily lend themselves to number crunching. The player who gets a big lead and then slows down with a number of draws to “protect” that lead, or players taking a draw in the last round when they are not in contention for the top prize. Or a player taking a draw in the last round when it will only get him into a tiebreak, rather than taking a risk and playing for the win. But while these factors can be hard to handle algorithmically, we have been modeling some of them and incorporating our findings into the software. We don’t claim our model will ever be perfect. But we are excited by pushing it as far as it will go.

With those caveats aside, we first ran the software in advance of the 2016 Candidates Tournament. We simulated one million tournaments, tracking how many times each player won.

Caruana, Nakamura, and Giri head up the top of our simulated tournaments. But the results are very close, and the winning probabilities range from Caruana’s 19.0% to Svidler’s 5.8%. This was clearly a tournament that any of the eight can win.

With our software, however, a chart like the above is just the beginning. The real fun begins on Friday March 11th, when we start updating the program with actual tournament results. We entered wins in the first two rounds for Nakamura and saw his chances rise from 17.1% to 40.6%. There are a several reasons for this rise, including the fact that one of those two wins is against Caruana, a key rival for first place. The two wins also go a long way toward getting Nakamura through the first two tiebreaks of the tournament. Topalov winning his fifth, sixth, and seventh rounds brings him to 50.2%. His seventh round victim is Nakamura, who plunges to a 5.6% chance of winning the tournament as he then faces an uphill battle to gain back three points - and can no longer win a head-to-head tiebreak against Topalov. What if there are three players tied for first with one round to go? With the press of a button we can now discover the answer.

What one rule change would get Nakamura to become the predicted winner? Keep reading!

Gathering the data

Early in the process of building the software we knew that we would have a lot of data to gather to fuel the algorithms of the software. We started by looking at some of the public resources for data, such as the ages of the players and their recent FIDE ratings.

But all of this data brings up a difficult question. How far back do you go? Do you look at just the most recent ratings? Or do you take an average? And if so, over how many months/years?

We decided to look at many different data sets. One of our main tools in gathering the data was of course Mega Database 2016, which contains 6.4 million games. We used the ‘filter’ tool to create databases of the games of the eight competitors. For example, we created a set of games for each player in which both that player and his opponent were rated 2700 or above. This eliminated games against lower-rated opposition that might not be relevant to the Candidates Tournament, and also eliminated those games played when the candidates were young and not as highly rated.

We then eliminated other games that didn’t seem relevant, like blindfold, chess960, Basque, Advanced Chess, and Thematic tournaments. Once that cleanup was done, we divided the data into classical, rapid, and blitz time controls. Mega Database 2016 made this straightforward, allowing us to spend more time on analysis and less on sorting games.

One of the data sets we looked at was the games played amongst the candidates themselves, filtering down again to only 2700 vs. 2700. The data set included 864 games, though these were not evenly spread out. The most common matchup so far has been Anand/Aronian with 63 games, while the pairing of Svidler/Giri has happened just seven times.

But one of the biggest challenges was working through the issue of how far back to go with these data sets. Recent games offer only a small sample size, but games from too far back may not be relevant. We tried to look at different lengths of time and different sample sizes and then work with the ones that seemed to be the most effective.

Some of the data collection proved challenging. Digging up tiebreak rules from past tournaments, for example, meant scouring the web. Sometimes the official tournament website had no information or the website didn’t even exist. Tournament reports sometimes indicated that tiebreaks were used, but didn’t specify the type. As a result, we had to piece together the information as best we could.

Discovering insights

In many ways we acted like scientists. We came up with a hypothesis, gathered data, and then determined whether or not the hypothesis was supported. How does age factor in? What role do openings play in determining a player’s overall draw percentage? Again, Mega Database 2016 was a key resource.

We have also incorporated recent software advances such as data mining and deep learning as a way to bring fresh insights into our model. To that end, we’ve been working with DDNT, a Sydney-based consultancy founded by Dalibor Frtunik specializing in deep learning and predictive analysis. With deep learning, we could let sophisticated algorithms dig through large data sets to automatically find hidden causative factors.

Feeding the software

Once we had the data and insights, we tuned our model for the eight candidates. We used the data sets to do things like determine the likelihood of a player drawing, and the circumstances in which that should be adjusted upward or downward. We know that the expectation for white is about 54% (i.e. someone playing 100 games with the white pieces would be expected to score about 54 points), but under what circumstances can that vary, player by player, depending on the current tournament result?

Once we were confident in the data, the algorithms, and the code, we were ready to try out the software to see what it could tell us about tournaments.

Tiebreaks

One of the benefits of being able to simulate an entire tournament is that you can begin to see the effects of tiebreak rules at the macro level. For the Candidates Tournament our model calculates the winning scores at the end of the tournament and then applies the tiebreak rules as laid out by FIDE. The first tiebreak is head-to-head score, then number of wins, then Sonneborn-Berger score. We call these the “math” tie breaks, because they are determined simply by applying mathematical rules to the results of the tied players. If the math tiebreaks do not result in a single winner, then there are “game” tiebreaks applied. The first is a round of two rapid games, then if necessary two blitz games, and finally an Armageddon game.

Handling these tiebreaks required application of a lot of algorithms, and required our Player Profiles to include rapid and blitz proficiencies. Without any formal ratings lists for Armageddon, we improvised a bit. Having finished the tiebreak algorithms, we were able to ask some fundamental questions about the impact of tiebreaks on the player win probabilities.

How many tournaments need tiebreaks?

In our million-tournament simulation, about three quarters of them ended with a clear winner. Of the 24% of tournaments ending in a tie, the vast majority were decided by application of the math tiebreaks. Just 0.4% of tournaments required additional games to be played to break the tie. So Nakamura’s well-known rapid and blitz skills are unlikely to help him much in the Candidates Tournament - except of course during time pressure in the classical games.

How would Nakamura’s winning chances improve if the math tiebreaks were removed? We ran a million tournaments under those parameters to see what would happen.

While Caruana, Anand, and Karjakin see modest gains, Nakamura’s chances to win the tournament jump a couple of percentage points - enough to make him co-favorite with Caruana to win the tournament.

Winning score

With an average FIDE rating of about 2775, this is clearly going to be a very difficult tournament to win. But what exactly is it going to take to win? Out of 14 games, would 9.0 points be enough? Or maybe 9.5 points? In his interview with Frederic Friedel, GM Peter Heine Nielsen mentioned that +4 (or 9.0 points) would be a likely winning score. We had our simulation track a million outcomes, with the results shown below.

Peter’s intuition seems to be spot on here, with scores of 8.5/14 and 9.0/14 comprising almost 60% of the simulated tournaments. But when you look at a million runs, there are sometimes some very unusual results. Six times our simulation showed a winning score of 7.0/14 in which everyone ties with the same score and the winner is determined by tiebreaks. At the other end of the spectrum, in three tournaments the winner managed to score an impressive 13.0/14 for a performance rating of about 3200 - enough to get him on the cover of every chess magazine on the planet.

Player profiles

In simulating the 2016 Candidates Tournament, we created a Player Profile for each participant, gathering a number of different factors that could affect their probability of winning and losing. This helped make our simulations more accurate, but it also gave us some intriguing insights into the players.

One example of a factor in our Player Profiles is their probability of drawing a game. It lets us better understand the variance of the player’s final score. Players more likely to draw will get results in a tighter band than players with lower chances to draw.

So when GM Peter Heine Nielsen said in his interview that Karjakin had a high draw percentage, we decided to compare it to the draw percentage of the other candidates.

But in our model, Karjakin falls closer to the middle of the pack. We hypothesized that older players might have higher draw percentages, but in this case we have 21 year old Giri with the most draws and 40 year old Topalov with the fewest!

Bookmakers

There are quite a few Internet bookmakers who will take bets on the 2016 Candidates Tournament. We took the posted odds for nine sites, calculated the implied probabilities of winning, and then averaged those implied probabilities as shown in the graph below.

Conclusion

As the Candidates Tournament heats up, we will no longer have to wonder about each player’s chances. We will be generating simulation results in real time as it unfolds, so that we can enjoy the games and have a better understanding of how the tournament will play out.

About the authors
James Jorasch is the founder of Science House and an inventor named on more than 700 patents. He plays tournament chess, backgammon, Scrabble, and poker. He lives in Manhattan and is a member of the Marshall Chess Club.
Chris Capobianco is a software engineer at Google. He is a two-time finalist at the USA Memory Championships and has consulted on memory for finance, media, advertising and Fortune 500 companies such as Xerox and GE.

Discussion and Feedback Join the public discussion or submit your feedback to the editors


Discuss

Rules for reader comments

 
 

Not registered yet? Register

amosburn amosburn 3/17/2016 04:43
Doing something a million times does not make it any more intelligent
amosburn amosburn 3/17/2016 04:42
Doing something a million times does not make it any more intelligent
chidoznn chidoznn 3/15/2016 06:47
I await your software prediction so far....as we they played four rounds so far
chidoznn chidoznn 3/15/2016 06:45
We still await the results of your software based on the games played so far
perl2ruby perl2ruby 3/12/2016 01:36
Round 1 has already shown where this prediction is headed.
Nelson100765 Nelson100765 3/12/2016 01:33
All are outstanding players, but must take into account the human condition of each. the best this during the tournament will be the winner.
perl2ruby perl2ruby 3/11/2016 02:28
".....We don’t claim our model will ever be perfect"

Oh the arrogance.
thlai80 thlai80 3/11/2016 02:17
I believe the winner will be the one that Kramnik works with, and this man is most likely Peter Svidler. Unfortunately, it takes more than Svidler to beat Carlsen. Go underdogs!
KchessK KchessK 3/11/2016 01:52
My humble guess: Hikaru Nakamura wins the tournament
mehmet gok mehmet gok 3/11/2016 12:16
You are just beating the data to confess.
MortalWombat MortalWombat 3/10/2016 07:39
The fact that it correlates so well with bookmakers' predictions is a good testament of its reliability so far.

I bet the results will be very close to what it says - Google programmers don't mess around!

It would be interesting to see another article after the tournament is over with the analysis of algorithm's performance and any adjustments made to it.

Thanks for doing this, guys.
X iLeon aka DMG X iLeon aka DMG 3/10/2016 06:07
Funny how all people's bias comes out in the comments as usual. For example, indians being the first to point out their surpise at Anand's low odds etc (Americans must be pretty happy with these predictions...). Being as unbiased as possible (as, according to my bias I would like to see Naka and definitely not Giri, who I find boring, and no, I'm not from the US) I have this to say:
Giri has probably higher odds as he has seemed the most solid this passing year.
I'm surprised that Svidler ranks that low - I'd expect slightly better odds for both him and Anand
Finally the spread (19 to 5.8 - a spread of 13.2) seems a little high to me
But I have to stress I'm talking empirically
A final point: whoever wins, will then lose to Magnus, lol ;p
Patrick_Richard8 Patrick_Richard8 3/10/2016 05:22
I think people is sleeping in Topalov while commenting.

One thing I´m sure: I don´t want another Carlsen - Anand (would be another massacre) or a Carlsen - Nakamura match (would be a new massacre).

Any other outcome would be fine for me (where do i sign?).

I believe chances are pretty well placed in the first graphic here.

vodkarov vodkarov 3/10/2016 04:50
I'm sorry, but this kind of simulation doesn't mean anything. Strong players interactions in a such a complex game and all the complex psychological factors involved are far beyond of such superficial quantitative analysis. I'm sorry, but this the pure truth.
ulyssesganesh ulyssesganesh 3/10/2016 01:12
i am sorry ...a compute which gives 13 percent chances for topalov and 6 percent for vishy ....may be ...may be.....suffering from virus!
Pionki Pionki 3/10/2016 10:29
¿Qué sentido tiene eso? Porque no simplemente esperar a los resultados? Han tomado en cuenta El Niño en sus predicciones?
The_Tenant The_Tenant 3/10/2016 05:39
Has this simulation model been used to accurately predict outcomes in other events, or is this the first time?
Raymond Labelle Raymond Labelle 3/10/2016 04:31
And what about style considérations? For example, Giri is very hard to beat, but not losing is not enough for winning this tournament, you have to win games!

Karjakin is very strong, and fights like a lion in apparently lost conditions.

Topalov is not in great form these last six months.

I cannot believe that Topalov has more chances than Karjakin (among the many things which leave me skeptical).

I do recognise the courage of thèses experts - they take the risk of being contradicted by reality.
oputu oputu 3/10/2016 03:36
Can the model predict what the next lottery number would be based on simulations of what they have being in the past? If yes, I would find that more important an information than a 'spoiler' for my much awaited candidates match.
murali100 murali100 3/10/2016 01:02
I predict Aronian...
fons fons 3/9/2016 11:17
Btw: a deep learning program just beat the world champion at Go. (Google DeepMind vs Lee Sedol)
fons fons 3/9/2016 11:04
The higher rated player is most likely to win, but that doesn't also mean he is _guaranteed_ to win.

So this model certainly is valid, but it doesn't also mean the future is already set in stone.
MarriedRhombus MarriedRhombus 3/9/2016 10:29
Funny that after so much complicated computations, the result just coincide with the live FIDE ranking.
camberish camberish 3/9/2016 09:43
Is anyone else surprised with crazy comments listed below. One would think that a site like Chessbase would attract more educated individuals who would articulate reasonable comments?
fixpont fixpont 3/9/2016 09:19
on one hand the candidates is going to be interesting and losts of players can win it, on the other hand, none of these players stand a slightest chance against Carlsen
Karpablanca Karpablanca 3/9/2016 08:33
People commenting on this article: "THIS MODEL DOESN'T CONFIRM MY PERSONAL BIASES SO IT MUST BE WRONG"
bondsergey bondsergey 3/9/2016 08:26
While being Russian I want Nakamura to win. He deserves it more. But of course I will support Sergey and Petr. It will be funny if Anand does it again.
okfine90 okfine90 3/9/2016 08:17
This is an enormous effort, and really a great start!. But surely, a classical "Machine Learning " approach would have been much more exciting and has a high probability to give closer results !?. There is much human flavor in this approach. Please let your algorithms learn themselves from huge data for tournaments, without you guiding them. So basically incorporating your findings into algorithms may have made them risky. Please let your algorithms do the learning part themselves from the rich tournament data, and improving themselves.
phantom2016 phantom2016 3/9/2016 07:40
The foll. is the current rating of the players in this report.

Caruana 2794
Nakamura 2790
Giri 2793
Aronian 2786
Topalov 2780
Anand 2762
Karjakin 2760
Svidler 2757

Their current rating has an exact correlation with the winning probabilities as found by this elaborate exercise. Looks like their current rating is sufficient enough a clue !
emerlion emerlion 3/9/2016 07:36
Please use your model to forecast the previous candidate match. What was Anand's chance ? Now that we know he won, what would your model have forecasted? If he does not get a high percentage, your model may be pretty, but other factors may be more important.
DJones DJones 3/9/2016 07:27
The bookmakers are not in the business of losing money. The quants know what they are doing. Carlsen should stick to chess.
Alain Savard Alain Savard 3/9/2016 07:20
Interesting. If the model uses deep learning, it will be difficult to know exactly what it did.

One factor that was probably taken care of is the fighting spirit of the losers based on previous events. Often, after 2 or 3 rounds, some guys have already no chance to win the event, and might either take greater risks, or according to style just nail some draws.

I can still recall how the impredictable Ivanchuk, after a very bad tournament, eliminated Kramnik on the very last round when Carlsen won his first (and only) Candidate.
ledgar ledgar 3/9/2016 07:07
what would have been the result of the simulation on the last tournament of the candidates in 2014 when Anand had won ?
hominid hominid 3/9/2016 05:26

Why do you need a computer simulation? Can't you just calculate probabilities?
Hawkman Hawkman 3/9/2016 02:59
"He also says that he'd surprised, and it would be strange, if he would meet Anand for a third time, and he'd also be surprised if Topalov or Svidler wins. So he doesn't believe in the veterans of the field. "

The champ should stick to playing chess. One of those 3 will win.
digupagal digupagal 3/9/2016 02:49
Giri will win (Karjakin might be a surprise)

Too much importance given to Naka, Caurana, Aronian

Anand, Topalov, Svidler have outside chances

I think Giri - 25%, Karjakin - 20%, Caruana - 15%, Aronian - 15%, Naka - 10%, Anand - 5%, Topalov - 5%, Svidler - 5%

My basis for putting Naka only at 10% is that he has not proven much in closed Tournaments historically and also i believe in such tournaments nobody will be unbeaten so i would bet on the most solid player (Giri) to come out on top. Karjakin also fits the bill. Anand's form is volatile, though that can be only profitable with 'options' :-)

It is another story that Giri is not popular among chess fans or people are debating about his chances against Carlsen if he wins, he still has the best record compared to others in the fray.

Giri - A Stock which is range bound, don't go up much but don't fall down also
Naka - pretty sensitive to market moving events
Caruana - Fundamental Pick, though his undervaluation is not reflected as yet in mkt. price
Karjakin - Solid Dividend paying stock
Anand - Short call option, unlimited losses but limited gains
Aronian - Speculative, trading pick (not a long term buy)
Topalov - Filing for insolvency
Svidler - Venture Capital, can be highly profitable but high risk of failure
Truls Truls 3/9/2016 02:20
According to the champion himself, you should put your money on Caruana, Aronia and/or Karjakin. to a direct question if Nakamura is the opponent he wants the most, he answers that "that would be fun, but I don't think he'll win." He also says that he'd surprised, and it would be strange, if he would meet Anand for a third time, and he'd also be surprised if Topalov or Svidler wins. So he doesn't believe in the veterans of the field.

http://www.vg.no/sport/magnus-carlsen/magnus-carlsens-tips-disse-kan-bli-min-vm-motstander/a/23633451/
DJones DJones 3/9/2016 02:07
Nakamura will either contend until the end or collapse early. He is in his prime and is coming off two straight event wins which was not taken into this account in this model. If the bookmakers have him as the favorite then he is the favorite. Caruana is the one with the best combined chance to advance and beat Carlsen and for either he or Nakamura to do this in New York would be HUGE for chess in this nation even during election season. Giri does not win consistently enough and is still very very young so I don't expect more than +2 from him. Topalov can go +6 or he can go -2 depending on his mood. Aronian also has great chances IF he is in form.
Angelo Pardi Angelo Pardi 3/9/2016 01:58
You should test your software against passed tournaments, in order to be able to compare your software result with what actually happened.
Stupido Stupido 3/9/2016 01:57
Millions of simulations to find out that Anand as 7% chances of winning, which is obvious non-sense for any (unbiased ^^) chess fan?
Waste of computer time, and that's an understatement.