Cover Story / Ken Regan
the College Board uses to normalize its scoring on standardized tests. For exam - ple, if the College Board wanted to catch a cheater on the SAT, it could easily do so by analyzing a small sample of suspi - cious answers to questions it knows to be diffi cult. Cheaters would perform un - char ac ter istically well on these questions. The same red flags go up when a cheating chess player consistently receives more partial credit on each move than his Elo would predict he deserves. Because the proper construction of
statistical evidence against alleged cheaters requires such technical expertise, Regan believes that it’s necessary to establish a centralized authority responsible for the administration of anti- cheating protocol. Eventually he would like to oversee the conversion of his 35,000 lines of C++ code into a Windows- driven program or portable app. “I see other people using my methods but not necessarily using my program,” he says. Regan also believes that a cen tralized authority can best fix public confusion about what constitutes scientific versus unscientific procedure. It’s too easy for people with a poor methodology to spread rumors online. The most notorious public cheating case
to date has been that of the then-26-year- old Bulgarian Borislav Ivanov. He was first accused of using computer assistance in December, 2012, at the Zadar Open in Croatia, where, barely a 2200-player, he scored six out of nine in the Open section, including wins over four grandmasters. Allegedly he had cheated in at least three open tournaments before that, too. Finally, Ivanov was disqualified from both the Bladoevgrad Open, in October, 2013 and the Navalmoral de la Mata Open in December, 2013, after both times refusing the inspec tion of his shoes, where he had allegedly hid a wireless communications device. The Ivanov case was widely publi cized
in the Bulgarian media and at the news site
ChessBase.com, which prompted ama - teur bloggers and You Tube aficionados to post their own move “matching” analysis, but none of it was worthy enough or contained high enough confidence inter - vals to persuade the Bulgarian Chess Federation to take action. Regan’s analysis, however, found that Ivanov’s moves earned a z-score of 5.09, which translates to the odds of him independently making these moves to less than one chance in five million. Regan’s statistical evidence, along with Ivanov’s refusal to submit to a search, resulted in the Bulgarian Chess Federation suspending Ivanov for four months.
26 June 2014 | Chess Life Statistical evidence is immune to con ceal ment. No matter how clever a cheater is in
communicating with collaborators, no mat ter how small the wire less communica tions device, the actual moves produced by a cheater cannot be hidden. Nevertheless, non-cheat ing outliers hap pen from time to time, the inevitable false
positives. In any large open tournament with at least a thousand non-cheating players, the chances are very high that at least one of those honest players will earn a z-score of 3.0 or more, an ostensibly sus picious value. Tamal Biswas, one of Regan’s two graduate stu dents and a class-A player, has used a database of previously played games to run simulations of large open tournaments and verify these num bers. By the summer of 2014, the ACP-FIDE anti-cheating committee hopes to work out
the logistical details about what a mounts and combinations of statistical, physical, and behavioral evidence should be considered conclusive if an alleged cheater is not caught red-handed. Regan proposes that a single z-score above 5.0 (the threshold for scientific discovery) or multiple instances of slightly lower z-scores should be enough statistical ev i dence on their own. But in other cases, one would need supporting behavioral or physical evidence, such as suspicious behavior in the restroom or tournament hall.
Regan grew up a chess prodigy during the
1960s and early 1970s, a few miles outside New York City, in Paramus, New Jersey. This area swarmed with chess opportu- nities and, in 1973, at the age of 13, Regan earned the master title, the youngest American at the time to do so since Bobby Fischer. A photo of Regan from that time shows a boyish round face and the thick, black eyebrows he main tains today. But before Regan finished high school,
mathematics proved too alluring, and he decided he didn’t want to make chess a career. His final two competitive triumphs came in 1976, when he was the only non- Soviet to win a gold medal at the now- defunct Student Chess Olympics, and in 1977 when he co-won the U.S. Junior Championship. After graduating from Princeton and Oxford, and then serving a post-doc at Cornell, Regan was hired by the University at Buffalo in 1989, where he has worked ever since. During the 1990s to 2006 Regan didn’t think much about chess. His kids were young, and he was busy immersing himself into the study of P versus NP, the holy grail of computer science problems. He now “leads three lives” as he likes to say: his main research and teaching duties, his anti-cheating work, and as co-author (with Richard J. Lipton) of the blog, “Godel’s Lost Letter and P=NP.” In December of 2013, Springer published a book Regan co- wrote with Lipton about the blog, titled People, Prob lems, and Proofs. The blog publishes not only technical amusements but occasional fodder about
coincidences. “[MIT Professor] Scott Aaronson bet $100,000 that scalable quantum computing can be done,” says Regan. “The media picked up on this. The impetus for this bet was my post entitled ‘Perpetual Motion of the 21st Century.’ But my post was edited by Lipton. Lipton, Lance Fortnow, and I co-wrote some papers in the early 1990s, and Fortnow co-writes his own blog with Bill Gasarch; and Bill Gasarch is a friend of mine and one of my confidants because he is also Chris tian.” At times Regan goes on like this, and it can be argued that his advanced research requires less energy to follow than his personal connections. P versus NP stands for Polynomial time versus Nondeterministic Polyno mial time. A
P-type problem requires relatively few computations, like the solution to tic-tac-toe or 8x8 checkers. Computations for an NP-type problem scale up extremely quickly, however—too quickly to find a solution based on the current theories of computer science. (An example would be the Travelling Salesman problem, where the goal is to find the shortest tour between a large number of cities.) Regan’s research includes ways to reduce the number of computations in an NP-type problem, so it behaves more like a P-type. If Regan manages to prove the theoretical equiv alence of P- and NP-type problems—
the meaning of “P=NP” in his blog title but an unlikely event, not be cause of a lack of technical proficiency on Regan’s part but because of the general consensus in the field that the relationship is false—then the result would change the world: cryptographic techniques would become obsolete, perfect language transla tion and facial recognition algorithms would become possible, and there would be a tremendous leap in artificial intelli gence. For good reason, such a discovery would earn him the $1 million Millennium Prize. The solution to chess is not defined as an NP-type problem (although some vari -
Page 1 |
Page 2 |
Page 3 |
Page 4 |
Page 5 |
Page 6 |
Page 7 |
Page 8 |
Page 9 |
Page 10 |
Page 11 |
Page 12 |
Page 13 |
Page 14 |
Page 15 |
Page 16 |
Page 17 |
Page 18 |
Page 19 |
Page 20 |
Page 21 |
Page 22 |
Page 23 |
Page 24 |
Page 25 |
Page 26 |
Page 27 |
Page 28 |
Page 29 |
Page 30 |
Page 31 |
Page 32 |
Page 33 |
Page 34 |
Page 35 |
Page 36 |
Page 37 |
Page 38 |
Page 39 |
Page 40 |
Page 41 |
Page 42 |
Page 43 |
Page 44 |
Page 45 |
Page 46 |
Page 47 |
Page 48 |
Page 49 |
Page 50 |
Page 51 |
Page 52 |
Page 53 |
Page 54 |
Page 55 |
Page 56 |
Page 57 |
Page 58 |
Page 59 |
Page 60 |
Page 61 |
Page 62 |
Page 63 |
Page 64 |
Page 65 |
Page 66 |
Page 67 |
Page 68 |
Page 69 |
Page 70 |
Page 71 |
Page 72 |
Page 73 |
Page 74 |
Page 75 |
Page 76