Predictions and Principles
With a year end thank-you to Ken
Ken Regan is the co-editor of GLL and is one of the internationally-ranked chess players in the US. He has won the city championship of Buffalo every time he has played. He is also a great friend and great researcher. His specialty is of course computational complexity.
Today I want to thank Ken personally for joining the GLL team and making this year one of our best.
Ken brings a unique perspective to everything that we do here. He is a wonderful writer—he has it in his DNA—his late dad was a professional writer his whole life. And his wife, Debbie, is an English teacher. Beyond that he is schooled in language: he knows English and its crazy rules better then—oops than—I will ever, and is fluent to various degrees in more languages than I can recall.
If the pieces that we try to write on so many various topics are half-way readable it is all Ken’s doing.
Cheating and Predictions
One of Ken’s many projects outside of GLL is helping track down cases of players alleged to have cheated at chess. The basic point is that a standard laptop running a standard chess machine plays better than anyone in the world. So if a player can get access to a chess program during the match, they have a huge advantage.
Some players get caught “red-handed” using quite obvious methods of relaying moves from someone who has the laptop—one was even caught looking at his game on a smartphone. These cases are not very interesting from a technical point of view. The really interesting ones, the ones that Ken works on, are based at least partially on statistical scoring methods that Ken has developed and is still improving.
The simple idea is to see how often a player makes the same move as the machine. For the moment let’s assume that the machine is always making the best move. The critical question is this:
If the player agrees with the machine too often, does that mean that cheating is happening?
Well the difficulty is yes and no. The problem is many-fold, but here is one very interesting issue. Suppose that the player agrees with the machine in many positions where moves are forced or almost forced? Even I—a very weak player—would recapture a piece or move my king out of check. Of course if there are choices how to recapture or how to move the king, then there is some information available. Sometimes the wrong recapture or king move could be a disaster. But if there is only one, or even if there are several but they all are about equal, you can see how the scoring issue becomes difficult. How to quantify it is Ken’s basic idea.
Ken’s model falls broadly into the category of predictive analytics. This doesn’t mean that Ken tries to predict individual chess moves. Instead his model aims to calculate probabilities for the moves—based on the skill of the player making them—that enable predicting means and variances for large enough aggregates of moves. The rate of agreements with a computer is one stat he can predict—for a non-cheating player. The rate of blunders is another. Predicting the rate of blunders, depending on the player and the positions faced on the board, is like how insurance and planning agencies use predictive analytics for risk assessment. He has posted a two-page non-technical description and a six-page overview.
A Recent Case
Ken has just been dealing yesterday and today with a case he was informed about on New Year’s Eve while on vacation. A player rated about 150 points lower than Ken beat four grandmasters rated 150 or more points higher than Ken. After his third such win he was searched to the skin, on suspicion that he had implanted chips, but no physical evidence was found.
Wow. Now that is getting pretty cool. More on this in the future, but I cannot resist thinking would I have a chip implanted if it helped me? Ken recalls that on his transatlantic flight to attend the 1994 IFIP conference in Hamburg, he was seated next to a Columbia University professor who was experimenting with embedded sending of images to the brains of blind people. Here is an article from last April on the state of this art.
The kind of chip I have in mind—and would love to have in my mind—would help with mathematics. Not only numerical and symbolic calculation, but also inference. We could even go further, as Stephen Wolfram did in progressing from his Mathematica program to his Wolfram Alpha inference engine. We can already put Wolfram Alpha on a chip; can we embed it? And if it were fair to use for math, could we use it for chess? These are interesting questions to think about, but perhaps best left for later.
Wolfram recently gave an interview on using his inference methods to give “A New Kind of Prediction.” The main idea is that rather than try to write the single best formal equations and combine solving and extrapolating from the data you have in hand, ask instead the question,
[What is] the space with all possible models that you can imagine using?
He begins with what one can learn from models expressed by the shortest and simplest computer programs, not necessarily the cellular automata featured in his book A New Kind of Science, but basic like that. I’ve talked with Ken about possible ways to simplify his chess model, but he already thinks it is the simplest one that captures his basic idea.
That said, we have a simple model for the predictions made at GLL: “De Summo Capite,” which Ken’s daughter gives as Latin for “Off the Top of the Head.” Here’s how we did last year, followed by our predictions for 2013.
Review of 2012 Predictions
Can we take credit for predicting that the world wouldn’t end, based on the tenor of last year’s intro? Well, we wouldn’t have been around to pay up if we’d lost.
- No circuit lower bound of or better will be proved for SAT. Of course.
- A Computer Scientist will win a Nobel Prize. Closer, but still a miss. Serge Haroche and David Wineland won in physics for experiments that include stepping stones toward quantum computers. Alvin Roth and Lloyd Shapley won in economics for stable-allocation theory; Shapley has a Mathematics affiliation but not CS.
- Someone other than a Williams will release a headline-making result in November. Since our headlines don’t count, and the -time matrix-flow algorithm really dates to August, a miss.
- A new set-theoretical relation will be found between a class in the general range of or and one just above in the polynomial hierarchy. Apparently not. Closest we find is this paper by Mohammad Mahmoody and David Xiao, “Languages with Efficient Zero-Knowledge PCPs are in ,” while the simplest new complexity-class relation seems to be this paper by Tsuyoshi Ito and Thomas Vidick showing that .
- Tangible new evidence against the Unique Games Conjecture will be posted (i.e., published at least on the arXiv) by Dec. 21, 2012. We claim yes, for this paper with many authors including Aram Harrow.
- Tangible new evidence supporting the Unique Games Conjecture will be posted by Dec. 21, 2012. Again we claim yes, for this FOCS 2012 paper—oh but cheating, it was on the ArXiv in late 2011. Our basis for both claims is this Sept. 2012 survey by Boaz Barak, especially on pages 4–5.
- Tangible new evidence against the Exponential Time Hypothesis will be posted (i.e., published at least on the arXiv) by Dec. 21, 2012. Unclear? We do not know how to interpret this SODA 2013 paper by Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk.
Tangible new evidence supporting the Exponential Time Hypothesis will be posted by Dec. 21, 2012. A miss?
For a general science bent, we offered:
- The Higgs boson will close the year with confidence above from a single team, but strictly less than from any one team. Too conservative. The July 4th announcement had 5.0 and 4.9 sigma from the respective teams, and stock in the Higgs closed the year at .
- An Earth-sized planet will be detected orbiting within the habitable zone of its single star. (Currently “Earth-sized” and “habitable zone” have been achieved by different exo-planets.) Not yet. We quote this December 19, 2012 press release by the University of Hertfordshire:
One of the planets lies in the habitable zone of the star and has a mass around five times that of Earth, making it the smallest planet found to be orbiting in the habitable zone of any Sun-like star.
Five times the Earth is too big. We could of course always claim Earth itself as an instance. Calling the last a miss, and letting partial credit on 7. offset 1. being a “gimme,” we say 3-for-10.
Predictions For 2013
Well we like to have the gimme, so we begin 2013 with the same first two, but expand to ten others. We decided not to repeat the unique-games and exponential-time ones.
- No circuit lower bound of or better will be proved for SAT. Actually let’s raise it to , in the spirit of problems found on the Putnam Exam: You can guess which year this was from.
- A Computer Scientist will win a Nobel Prize.
- An important advance will be made on understanding barriers either to proving or proving the opposite, .
- A new simple group will be discovered. By the classification theorem, such a group should be infinite, but will not be.
- Another gap will be found in Shinichi Mochizuki’s claimed proof of the ABC Conjecture. (Note that Mochizuki released updates to his papers on Dec. 16th, including acknowledgments to Vesselin Dimitrov and Akshay Venkatesh who had found a gap in two of them.)
- The ABC claimed proof will be found to be correct.
- Experiments scaling up boson sampling from to permanents will be published by year’s end.
- A new conditional relation will be found tying the difficulty of scaling up boson sampling to that of scaling up full universal quantum computation.
- A best seller will be published by a noted blogger on the question.
- Work will begin on a major motion picture whose plot is based on finding a polynomial time algorithm for factoring. It will audition Angelina Jolie as the brilliant mathematician who solves the problem and Tom Hanks as the villain.
- Noted progress toward solving another Clay Problem will be released on the ArXiv this year.
- A planet no more than twice Earth’s size will be detected orbiting within the habitable zone of its single star.
So how do you think we did with our predictions? Also make some of your own for the record—you probably will do better than we do.