An Important Discovery

While puzzling over the results of the Blue Coakley Experiment, I stumbled across an important and unexpected discovery.  When I plotted the cumulative distribution of (correct) solution times, aggregated over the first passes through all the Coakley problem batches, I noticed that it looked like an exponential curve.  (N.B. The cumulative distribution of solution times gives the probability that the solution time will be less than any chosen time value.)  I tried fitting an exponential curve to my results:














I had not expected this!  I thought that the distribution of chess problem solution times would be highly dependent on the distribution in difficulty of the problems.  The problems at the beginning of Coakley’s book are significantly easier than those at the end, but that does not appear to have affected the result.  The green line on the graph is the exponential curve P = 0.764*(1 - exp(-t/21.0)), where t is the time in seconds.  I got much the same result with the Woolum Experiment:













For this graph, the green curve is P = 0.775*(1 - exp(-t/7.22)).  The problems in Woolum vary from mates in one, to mates in three with more than one variation and the King in the middle of the board.  Again, the distribution of difficulty does not appear to have affected the result.

In general, the cumulative distribution of correct solution times appears to be of the form P = a*(1- exp(-t/b)).  If I continue solving an infinite set of problems, in the same way, until I have (correctly or incorrectly) solved them all, a represents the fraction of the problems that I solve correctly, and b represents my average correct solution time.  (N.B. The mathematics of the exponential distribution is summarised by the Wikipedia article http://en.wikipedia.org/wiki/Exponential_distribution.)

I constructed a simple mathematical model to explain the graphs above.  I assumed that I had a fixed probability per unit time 1/b of solving a problem (irrespective of the time that I had already spent on that problem).  It follows that the probability that I will solve the problem (correctly or incorrectly) within time t is given by 1 - exp(-t/b).  I also assumed that I had a fixed probability a that my solution was correct.  The probability that I will find a correct solution within time t is then given by a*(1 - exp(-t/b)).

If I do not stop at the time limit, but continue until I have (correctly or incorrectly) solved all the problems, my average solution time will be b, but a fraction 1-a of the problems will have been solved incorrectly.  If I try again, with these remaining problems, my average solution time will again be b, and a fraction (1-a)^2 of the problems will remain to be solved correctly at the end.  If I repeat this process over and over again, until all the problems have been solved correctly, my average solution time will be:

b + b*(1-a) + b*(1-a)^2 + b*(1-a)^3 +…. = b /(1 - (1-a)) = b/a

This model therefore estimates my average time to find a solution that is always correct as b/a.  (N.B. I have assumed that I have perfect memory of my previous attempts to solve a problem, and I do not benefit unfairly from knowing when my solution is wrong.)  I have assumed that the tail of the distribution continues to follow the same exponential curve.  A more detailed study of my results shows that this assumption is over optimistic. Nonetheless, the model appears to be reasonably accurate for most of the problems in my problem sets.

The expression 1 - exp(-a*t/b) can be interpreted as the probability that I will find a solution that is always correct within t seconds.  Equivalently, it can be viewed as the cumulative probability distribution of the difficulty of the problems as measured by the time that it takes me to solve them correctly.  With this perspective, my failure to solve a problem is simply a consequence of not spending enough time on it.

If I work on randomly selected fraction a of an infinite set of problems until I solve them all correctly, and ignore the others, the probability that I will solve a problem correctly within t seconds is again given by a*(1 - exp(-t/b)).  (N.B. Ignoring a randomly chosen fraction a of the problems reduces both the number of problems that I solve by a fraction a, and the time that I take to solve them by a fraction a.)  This is the same result as I got when I tackled all the problems, with a probability a of getting each one right.  Indeed, because there is fixed probability per unit time that I will solve a problem, I get the exactly same result however I allocate my time between the problems.  Time management is futile here! My time management does, however, affect the distribution of failures.  I can give up solving a problem whenever I choose, and greatly affect the failure distribution, without affecting the distribution of successful solutions.  The distribution of solutions (correct or incorrect) is the sum of the distribution of successes and the distribution of failures, so it too is affected by my time management.

[For a more detailed analysis see my later article: A Three Parameter Model.]

For computer programs, each doubling of the calculation speed increases the Elo rating by about 70 points, but I have not been able to find a corresponding number for human players.  My guess is that each doubling of the time that a human player has on the clock increases his rating by about 200 points (up to about the standard time limit at least). The only evidence that I was able find is a clock simultaneous match between Topalov and the four player Irish team: http://2seeitlive.co.uk/icu/   This match was drawn with a rating difference of 367 Elo points, so having a quarter of the time on the clock appears to have reduced Topalov’s rating by about 400 points.  This result is very interesting, but there were only four games, and data for 2000-2200 players playing clock simultaneous matches against four players rated 400 points lower would be relevant to the average player.

If my time to solve a set of problems correctly goes down from t₁ to t₂, the number of times t₂ needs to be doubled to get to t₁ is log₂(t₁ / t₂).  This number can be fractional.  If each doubling corresponds to 200 rating points, my improvement is 200 * log₂(t₁ / t₂) rating points.  Let t_x be the average time that players rated x take to solve the problem set correctly.  If I take time t, my performance is 200 * log₂(t_x / t) + x = -200 * log₂(t) + 200 * log₂(t_x) + x   (N.B. log₂(t) = ln(t) / ln(2).)

Consider two players, who are identical except that player 2 is 20% faster than player 1. Suppose that their distributions of (successful) solution times are given by P1 = 0.8*(1-exp(-t/20)) and P2 = 0.8*(1-exp(-t/16) respectively.  The Elo formula gives the difference between their respective ratings and the rating of the problem set as -400*log(1/P1 - 1) and -400*log(1/P2 -1).  (See my earlier article Rating Points Revisited.)  Here is a graph showing these rating point differences for solution times between 5 and 60 seconds:














At first sight this graph looks balmy!  The rating difference between the players and the problem set increases as the time limit increases - but this makes sense, because the players’ scores increase when they have more to think.  More surprisingly perhaps, the difference in the players’ ratings relative to the problem set is at a maximum at around 30 seconds and smaller for both longer and shorter time limits.  Again, this makes sense.  If the players both have all day to think, but do not check their solutions any more thoroughly, they are both going to get 80% of the problems right.  It is also not too surprising that if they are both given very little time to think, their scores will be closer. This method can give useful results, but it is less than ideal.

I used the method of least squares to fit exponential curves to my data points (Pi, ti).  I tested the accuracy of the fit by calculating:

E = Sum_i { (P_i - a*x_i)² }

where x_i = 1 - exp(-t_i / b)

For a fixed value of b, E is at its minimum when:

dE/da = Sum_i { 2 * (P_i - a*x_i) * (-x_i) } = 0

Solving for a gives:

a = Sum_i { x_i * P_i  } / Sum_i { x_i² }

I used a spreadsheet to calculate this value of a (and the corresponding value of E) whenever I entered a value for b.  I adjusted b manually until I found the value that minimised E.  This method worked better than the other curve fitting methods that I tried, and I used it to produce the graphs above.